Nugget
|
#include <vector_multiset.h>
Public Types | |
typedef RandomAccessContainer | base_type |
typedef vector_multiset< Key, Compare, Allocator, RandomAccessContainer > | this_type |
typedef Allocator | allocator_type |
typedef Key | key_type |
typedef Key | value_type |
typedef Compare | key_compare |
typedef Compare | value_compare |
typedef value_type * | pointer |
typedef const value_type * | const_pointer |
typedef value_type & | reference |
typedef const value_type & | const_reference |
typedef base_type::size_type | size_type |
typedef base_type::difference_type | difference_type |
typedef base_type::iterator | iterator |
typedef base_type::const_iterator | const_iterator |
typedef base_type::reverse_iterator | reverse_iterator |
typedef base_type::const_reverse_iterator | const_reverse_iterator |
Public Types inherited from eastl::vector< Key, EASTLAllocatorType > | |
typedef Key | value_type |
typedef Key * | pointer |
typedef const Key * | const_pointer |
typedef Key & | reference |
typedef const Key & | const_reference |
typedef Key * | iterator |
typedef const Key * | const_iterator |
typedef eastl::reverse_iterator< iterator > | reverse_iterator |
typedef eastl::reverse_iterator< const_iterator > | const_reverse_iterator |
typedef base_type::size_type | size_type |
typedef base_type::difference_type | difference_type |
typedef base_type::allocator_type | allocator_type |
Public Types inherited from eastl::VectorBase< Key, EASTLAllocatorType > | |
typedef EASTLAllocatorType | allocator_type |
typedef eastl_size_t | size_type |
typedef ptrdiff_t | difference_type |
Public Member Functions | |
vector_multiset (const allocator_type &allocator) | |
vector_multiset (const key_compare &comp, const allocator_type &allocator=EASTL_VECTOR_MULTISET_DEFAULT_ALLOCATOR) | |
vector_multiset (const this_type &x) | |
vector_multiset (this_type &&x) | |
vector_multiset (this_type &&x, const allocator_type &allocator) | |
vector_multiset (std::initializer_list< value_type > ilist, const key_compare &compare=key_compare(), const allocator_type &allocator=EASTL_VECTOR_MULTISET_DEFAULT_ALLOCATOR) | |
template<typename InputIterator > | |
vector_multiset (InputIterator first, InputIterator last) | |
template<typename InputIterator > | |
vector_multiset (InputIterator first, InputIterator last, const key_compare &compare) | |
this_type & | operator= (const this_type &x) |
this_type & | operator= (std::initializer_list< value_type > ilist) |
this_type & | operator= (this_type &&x) |
void | swap (this_type &x) |
const key_compare & | key_comp () const |
key_compare & | key_comp () |
const value_compare & | value_comp () const |
value_compare & | value_comp () |
template<class... Args> | |
iterator | emplace (Args &&... args) |
template<class... Args> | |
iterator | emplace_hint (const_iterator position, Args &&... args) |
iterator | insert (const value_type &value) |
iterator | insert (const_iterator position, const value_type &value) |
iterator | insert (const_iterator position, value_type &&value) |
void | insert (std::initializer_list< value_type > ilist) |
template<typename P > | |
iterator | insert (P &&otherValue) |
template<typename InputIterator > | |
void | insert (InputIterator first, InputIterator last) |
iterator | erase (const_iterator position) |
iterator | erase (const_iterator first, const_iterator last) |
size_type | erase (const key_type &k) |
reverse_iterator | erase (const_reverse_iterator position) |
reverse_iterator | erase (const_reverse_iterator first, const_reverse_iterator last) |
iterator | find (const key_type &k) |
const_iterator | find (const key_type &k) const |
template<typename U , typename BinaryPredicate > | |
iterator | find_as (const U &u, BinaryPredicate predicate) |
template<typename U , typename BinaryPredicate > | |
const_iterator | find_as (const U &u, BinaryPredicate predicate) const |
size_type | count (const key_type &k) const |
iterator | lower_bound (const key_type &k) |
const_iterator | lower_bound (const key_type &k) const |
iterator | upper_bound (const key_type &k) |
const_iterator | upper_bound (const key_type &k) const |
eastl::pair< iterator, iterator > | equal_range (const key_type &k) |
eastl::pair< const_iterator, const_iterator > | equal_range (const key_type &k) const |
eastl::pair< iterator, iterator > | equal_range_small (const key_type &k) |
eastl::pair< const_iterator, const_iterator > | equal_range_small (const key_type &k) const |
void | push_back (const value_type &value)=delete |
reference | push_back ()=delete |
void * | push_back_uninitialized ()=delete |
template<class... Args> | |
reference | emplace_back (Args &&...)=delete |
template<typename... Args> | |
decltype(auto) | push_back_unsorted (Args &&... args) |
template<typename... Args> | |
decltype(auto) | emplace_back_unsorted (Args &&... args) |
Public Member Functions inherited from eastl::vector< Key, EASTLAllocatorType > | |
vector (const allocator_type &allocator) EA_NOEXCEPT | |
vector (size_type n, const allocator_type &allocator=EASTL_VECTOR_DEFAULT_ALLOCATOR) | |
vector (size_type n, const value_type &value, const allocator_type &allocator=EASTL_VECTOR_DEFAULT_ALLOCATOR) | |
vector (const this_type &x) | |
vector (const this_type &x, const allocator_type &allocator) | |
vector (this_type &&x) EA_NOEXCEPT | |
vector (this_type &&x, const allocator_type &allocator) | |
vector (std::initializer_list< value_type > ilist, const allocator_type &allocator=EASTL_VECTOR_DEFAULT_ALLOCATOR) | |
vector (InputIterator first, InputIterator last, const allocator_type &allocator=EASTL_VECTOR_DEFAULT_ALLOCATOR) | |
this_type & | operator= (const this_type &x) |
this_type & | operator= (std::initializer_list< value_type > ilist) |
this_type & | operator= (this_type &&x) |
void | swap (this_type &x) |
void | assign (size_type n, const value_type &value) |
void | assign (InputIterator first, InputIterator last) |
void | assign (std::initializer_list< value_type > ilist) |
iterator | begin () EA_NOEXCEPT |
const_iterator | begin () const EA_NOEXCEPT |
const_iterator | cbegin () const EA_NOEXCEPT |
iterator | end () EA_NOEXCEPT |
const_iterator | end () const EA_NOEXCEPT |
const_iterator | cend () const EA_NOEXCEPT |
reverse_iterator | rbegin () EA_NOEXCEPT |
const_reverse_iterator | rbegin () const EA_NOEXCEPT |
const_reverse_iterator | crbegin () const EA_NOEXCEPT |
reverse_iterator | rend () EA_NOEXCEPT |
const_reverse_iterator | rend () const EA_NOEXCEPT |
const_reverse_iterator | crend () const EA_NOEXCEPT |
bool | empty () const EA_NOEXCEPT |
size_type | size () const EA_NOEXCEPT |
size_type | capacity () const EA_NOEXCEPT |
void | resize (size_type n, const value_type &value) |
void | resize (size_type n) |
void | reserve (size_type n) |
void | set_capacity (size_type n=base_type::npos) |
void | shrink_to_fit () |
pointer | data () EA_NOEXCEPT |
const_pointer | data () const EA_NOEXCEPT |
reference | operator[] (size_type n) |
const_reference | operator[] (size_type n) const |
reference | at (size_type n) |
const_reference | at (size_type n) const |
reference | front () |
const_reference | front () const |
reference | back () |
const_reference | back () const |
void | push_back (const value_type &value) |
reference | push_back () |
void | push_back (value_type &&value) |
void * | push_back_uninitialized () |
void | pop_back () |
iterator | emplace (const_iterator position, Args &&... args) |
reference | emplace_back (Args &&... args) |
iterator | insert (const_iterator position, const value_type &value) |
iterator | insert (const_iterator position, size_type n, const value_type &value) |
iterator | insert (const_iterator position, value_type &&value) |
iterator | insert (const_iterator position, std::initializer_list< value_type > ilist) |
iterator | insert (const_iterator position, InputIterator first, InputIterator last) |
iterator | erase_first (const Key &value) |
iterator | erase_first_unsorted (const Key &value) |
reverse_iterator | erase_last (const Key &value) |
reverse_iterator | erase_last_unsorted (const Key &value) |
iterator | erase (const_iterator position) |
iterator | erase (const_iterator first, const_iterator last) |
reverse_iterator | erase (const_reverse_iterator position) |
reverse_iterator | erase (const_reverse_iterator first, const_reverse_iterator last) |
iterator | erase_unsorted (const_iterator position) |
reverse_iterator | erase_unsorted (const_reverse_iterator position) |
void | clear () EA_NOEXCEPT |
void | reset_lose_memory () EA_NOEXCEPT |
bool | validate () const EA_NOEXCEPT |
int | validate_iterator (const_iterator i) const EA_NOEXCEPT |
size_type | GetNewCapacity (size_type currentCapacity) |
Key * | DoAllocate (size_type n) |
void | DoFree (Key *p, size_type n) |
Key *& | internalCapacityPtr () EA_NOEXCEPT |
Key *const & | internalCapacityPtr () const EA_NOEXCEPT |
allocator_type & | internalAllocator () EA_NOEXCEPT |
const allocator_type & | internalAllocator () const EA_NOEXCEPT |
Public Member Functions inherited from eastl::VectorBase< Key, EASTLAllocatorType > | |
VectorBase (const allocator_type &allocator) | |
VectorBase (size_type n, const allocator_type &allocator) | |
const allocator_type & | get_allocator () const EA_NOEXCEPT |
allocator_type & | get_allocator () EA_NOEXCEPT |
void | set_allocator (const allocator_type &allocator) |
Protected Attributes | |
value_compare | mCompare |
Protected Attributes inherited from eastl::VectorBase< Key, EASTLAllocatorType > | |
Key * | mpBegin |
-1 is reserved for 'npos'. It also happens to be slightly beneficial that kMaxSize is a value less than -1, as it helps us deal with potential integer wraparound issues. | |
Key * | mpEnd |
eastl::compressed_pair< Key *, allocator_type > | mCapacityAllocator |
Additional Inherited Members | |
Public Attributes inherited from eastl::vector< Key, EASTLAllocatorType > | |
Key * | mpBegin |
-1 is reserved for 'npos'. It also happens to be slightly beneficial that kMaxSize is a value less than -1, as it helps us deal with potential integer wraparound issues. | |
Key * | mpEnd |
eastl::compressed_pair< Key *, allocator_type > | mCapacityAllocator |
Static Public Attributes inherited from eastl::vector< Key, EASTLAllocatorType > | |
static const size_type | npos |
Static Public Attributes inherited from eastl::VectorBase< Key, EASTLAllocatorType > | |
static const size_type | npos |
static const size_type | kMaxSize |
'npos' means non-valid position or simply non-position. | |
Protected Types inherited from eastl::vector< Key, EASTLAllocatorType > | |
using | should_copy_tag = should_move_or_copy_tag< false > |
using | should_move_tag = should_move_or_copy_tag< true > |
Protected Member Functions inherited from eastl::vector< Key, EASTLAllocatorType > | |
pointer | DoRealloc (size_type n, ForwardIterator first, ForwardIterator last, should_copy_tag) |
pointer | DoRealloc (size_type n, ForwardIterator first, ForwardIterator last, should_move_tag) |
void | DoInit (Integer n, Integer value, true_type) |
void | DoInit (InputIterator first, InputIterator last, false_type) |
void | DoInitFromIterator (InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag) |
void | DoInitFromIterator (ForwardIterator first, ForwardIterator last, EASTL_ITC_NS::forward_iterator_tag) |
void | DoAssign (Integer n, Integer value, true_type) |
void | DoAssign (InputIterator first, InputIterator last, false_type) |
void | DoAssignValues (size_type n, const value_type &value) |
void | DoAssignFromIterator (InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag) |
void | DoAssignFromIterator (RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag) |
void | DoInsert (const_iterator position, Integer n, Integer value, true_type) |
void | DoInsert (const_iterator position, InputIterator first, InputIterator last, false_type) |
void | DoInsertFromIterator (const_iterator position, InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag) |
void | DoInsertFromIterator (const_iterator position, BidirectionalIterator first, BidirectionalIterator last, EASTL_ITC_NS::bidirectional_iterator_tag) |
void | DoInsertValues (const_iterator position, size_type n, const value_type &value) |
void | DoInsertValuesEnd (size_type n) |
void | DoInsertValuesEnd (size_type n, const value_type &value) |
void | DoInsertValue (const_iterator position, Args &&... args) |
void | DoInsertValueEnd (Args &&... args) |
void | DoClearCapacity () |
void | DoGrow (size_type n) |
void | DoSwap (this_type &x) |
Protected Member Functions inherited from eastl::VectorBase< Key, EASTLAllocatorType > | |
Key *& | internalCapacityPtr () EA_NOEXCEPT |
Key *const & | internalCapacityPtr () const EA_NOEXCEPT |
allocator_type & | internalAllocator () EA_NOEXCEPT |
const allocator_type & | internalAllocator () const EA_NOEXCEPT |
Key * | DoAllocate (size_type n) |
void | DoFree (Key *p, size_type n) |
size_type | GetNewCapacity (size_type currentCapacity) |
Implements a multiset via a random access container such as a vector. This container is also known as a sorted_vector. We choose to call it vector_multiset, as that is a more consistent universally applicable name for it in this library.
Note that with vector_set, vector_multiset, vector_map, vector_multimap that the modification of the container potentially invalidates all existing iterators into the container, unlike what happens with conventional sets and maps.
To consider: std::multiset has the limitation that values in the set cannot be modified, with the idea that modifying them would change their sort order. We have the opportunity to make it so that values can be modified via changing iterators to be non-const, with the downside being that the container can get screwed up if the user screws up. Alternatively, we can do what std STL does and require the user to make their stored classes use 'mutable' as needed. See the C++ standard defect report #103 (DR 103) for a discussion of this.
Note that the erase functions return iterator and not void. This allows for more efficient use of the container and is consistent with the C++ language defect report #130 (DR 130)
|
inline |
equal_range_small This is a special version of equal_range which is optimized for the case of there being few or no duplicated keys in the tree.