libjmmcg
build_2783
A C++ library containing an eclectic mix of useful, advanced components.
|
#include <multimap.hpp>
Public Types | |
typedef _Cont | base_container |
typedef base_container::allocator_type | allocator_type |
typedef _Key | key_type |
typedef _Pred | key_compare |
typedef base_container::difference_type | difference_type |
typedef base_container::reference | reference |
typedef base_container::const_reference | const_reference |
typedef base_container::size_type | size_type |
typedef base_container::const_iterator | const_iterator |
typedef base_container::iterator | iterator |
typedef base_container::reverse_iterator | reverse_iterator |
typedef base_container::const_reverse_iterator | const_reverse_iterator |
typedef std::pair< iterator, bool > | InsertItr_ |
Public Attributes | |
const typedef key_type | value_type |
This collection implementation is efficient when the inserts()
to the collection come in blocks, then the lookups (find()
or operator[]()
) in blocks, then the inserts()
again. This is because the collection only sorts itself when it is unsorted and a lookup occurs. Non-unique keys are allowed, and the groups of non-unique keys are adjacent (after sorting) then the range of the "unique" key is multiple values.
The complexity is (assuming default container of std::vector
, which affects these complexities):
std::vector
or std:list
. The choice will affect the complexities above. The advantage of std::vector
over std::list
is locality of reference: The data elements are guaranteed to be local to each other, unlike std::list
. Alternatively std:list
has better complexity than std::vector
for some of the operations. Choose wisely. Definition at line 212 of file multimap.hpp.
typedef base_container::allocator_type jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::allocator_type |
Definition at line 215 of file multimap.hpp.
typedef _Cont jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::base_container |
Definition at line 214 of file multimap.hpp.
typedef base_container::const_iterator jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::const_iterator |
Definition at line 223 of file multimap.hpp.
typedef base_container::const_reference jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::const_reference |
Definition at line 221 of file multimap.hpp.
typedef base_container::const_reverse_iterator jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::const_reverse_iterator |
Definition at line 226 of file multimap.hpp.
typedef base_container::difference_type jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::difference_type |
Definition at line 219 of file multimap.hpp.
typedef std::pair<iterator,bool> jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::InsertItr_ |
Definition at line 227 of file multimap.hpp.
typedef base_container::iterator jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::iterator |
Definition at line 224 of file multimap.hpp.
typedef _Pred jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::key_compare |
Definition at line 217 of file multimap.hpp.
typedef _Key jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::key_type |
Definition at line 216 of file multimap.hpp.
typedef base_container::reference jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::reference |
Definition at line 220 of file multimap.hpp.
typedef base_container::reverse_iterator jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::reverse_iterator |
Definition at line 225 of file multimap.hpp.
typedef base_container::size_type jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::size_type |
Definition at line 222 of file multimap.hpp.
|
inlineexplicit |
Definition at line 326 of file multimap_impl.hpp.
|
inline |
Definition at line 331 of file multimap_impl.hpp.
|
inline |
Definition at line 336 of file multimap_impl.hpp.
|
inline |
Definition at line 341 of file multimap_impl.hpp.
|
inline |
Definition at line 346 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 369 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 377 of file multimap_impl.hpp.
|
inline |
Definition at line 448 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 443 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 401 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 409 of file multimap_impl.hpp.
|
inline |
Erase: O(n).
Definition at line 499 of file multimap_impl.hpp.
|
inline |
Erase: O(n).
Definition at line 504 of file multimap_impl.hpp.
|
inline |
Erase: O(nlog(n)). All keys with same value are erased. Collection remains sorted.
Definition at line 535 of file multimap_impl.hpp.
|
inline |
Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multiset or not. Are guaranteed to return the first key if they are not unique in the multiset.
Definition at line 549 of file multimap_impl.hpp.
|
inline |
Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multiset or not. Are guaranteed to return the first key if they are not unique in the multiset.
Definition at line 563 of file multimap_impl.hpp.
|
inline |
Definition at line 470 of file multimap_impl.hpp.
|
inline |
Insert: (with insert()
) constant time. (But unsorts the multiset.) Allows the insertion of multiple keys with the same value.
Definition at line 492 of file multimap_impl.hpp.
|
inline |
Insert: (with insert()
) constant time. (But unsorts the multiset.) Allows the insertion of multiple keys with the same value.
Definition at line 484 of file multimap_impl.hpp.
|
inline |
Insert: (with insert()
) constant time. (But unsorts the multiset.) Allows the insertion of multiple keys with the same value.
Definition at line 475 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 438 of file multimap_impl.hpp.
|
inline |
Definition at line 350 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 385 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 393 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 417 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 425 of file multimap_impl.hpp.
|
inline |
Definition at line 462 of file multimap_impl.hpp.
|
inline |
Definition at line 454 of file multimap_impl.hpp.
|
inlinenoexcept |
Definition at line 433 of file multimap_impl.hpp.
const typedef key_type jmmcg::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::value_type |
Definition at line 218 of file multimap.hpp.