libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
Public Types | Public Member Functions | List of all members
jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont > Class Template Reference

#include <multimap.hpp>

Public Types

typedef _Cont base_container
 
typedef base_container::allocator_type allocator_type
 
typedef _Key key_type
 
typedef _Val mapped_type
 
typedef _Pred key_compare
 
typedef std::pair< const key_type, mapped_type > value_type
 
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 Member Functions

__stdcall multimap (const _Pred &pr=_Pred(), const allocator_type &al=allocator_type()) FORCE_INLINE
 
__stdcall multimap (const size_type, const value_type &v=value_type(), const _Pred &pr=_Pred(), const allocator_type &al=allocator_type()) FORCE_INLINE
 
__stdcall multimap (const multimap &) FORCE_INLINE
 
__stdcall multimap (const const_iterator &, const const_iterator &, const _Pred &pr=_Pred(), const allocator_type &al=allocator_type()) FORCE_INLINE
 
__stdcall ~multimap (void) FORCE_INLINE
 
multimap &__fastcall operator= (const multimap &m) FORCE_INLINE
 
const_iterator __fastcall begin (void) const noexcept(true) FORCE_INLINE
 
iterator __fastcall begin (void) noexcept(true) FORCE_INLINE
 
const_reverse_iterator __fastcall rbegin (void) const noexcept(true) FORCE_INLINE
 
reverse_iterator __fastcall rbegin (void) noexcept(true) FORCE_INLINE
 
const_iterator __fastcall end (void) const noexcept(true) FORCE_INLINE
 
iterator __fastcall end (void) noexcept(true) FORCE_INLINE
 
const_reverse_iterator __fastcall rend (void) const noexcept(true) FORCE_INLINE
 
reverse_iterator __fastcall rend (void) noexcept(true) FORCE_INLINE
 
const size_type __fastcall size (void) const noexcept(true) FORCE_INLINE
 
const size_type __fastcall max_size (void) const noexcept(true) FORCE_INLINE
 
bool __fastcall empty (void) const noexcept(true) FORCE_INLINE
 
void __fastcall clear (void) FORCE_INLINE
 
void __fastcall resize (const size_type, const value_type &v=value_type()) FORCE_INLINE
 
void __fastcall reserve (const size_type) FORCE_INLINE
 
allocator_type __fastcall get_allocator (void) const FORCE_INLINE
 
InsertItr_ __fastcall insert (const value_type &) FORCE_INLINE
 
iterator __fastcall insert (const iterator &, const value_type &) FORCE_INLINE
 
void __fastcall insert (const const_iterator &, const const_iterator &) FORCE_INLINE
 
iterator __fastcall erase (const iterator &) FORCE_INLINE
 
iterator __fastcall erase (const iterator &, const iterator &) FORCE_INLINE
 
const size_type __fastcall erase (const key_type &) FORCE_INLINE
 
mapped_type &__fastcall operator[] (const key_type &) FORCE_INLINE
 
const_iterator __fastcall find (const key_type &) const FORCE_INLINE
 
iterator __fastcall find (const key_type &) FORCE_INLINE
 

Detailed Description

template<typename _Key, typename _Val, typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
class jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >

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):

  1. Copy: O(n), worst-case.

More notes:

  1. After sorting, non-unique keys are guaranteed to be adjacent in the multimap.
  2. The base container can be pretty much any STL container. The obvious candidates are 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 44 of file multimap.hpp.

Member Typedef Documentation

◆ allocator_type

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::allocator_type jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::allocator_type

Definition at line 47 of file multimap.hpp.

◆ base_container

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef _Cont jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::base_container

Definition at line 46 of file multimap.hpp.

◆ const_iterator

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::const_iterator jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::const_iterator

Definition at line 56 of file multimap.hpp.

◆ const_reference

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::const_reference jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::const_reference

Definition at line 54 of file multimap.hpp.

◆ const_reverse_iterator

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::const_reverse_iterator jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::const_reverse_iterator

Definition at line 59 of file multimap.hpp.

◆ difference_type

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::difference_type jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::difference_type

Definition at line 52 of file multimap.hpp.

◆ InsertItr_

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef std::pair<iterator,bool> jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::InsertItr_

Definition at line 60 of file multimap.hpp.

◆ iterator

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::iterator jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::iterator

Definition at line 57 of file multimap.hpp.

◆ key_compare

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef _Pred jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::key_compare

Definition at line 50 of file multimap.hpp.

◆ key_type

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef _Key jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::key_type

Definition at line 48 of file multimap.hpp.

◆ mapped_type

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef _Val jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::mapped_type

Definition at line 49 of file multimap.hpp.

◆ reference

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::reference jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::reference

Definition at line 53 of file multimap.hpp.

◆ reverse_iterator

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::reverse_iterator jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::reverse_iterator

Definition at line 58 of file multimap.hpp.

◆ size_type

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef base_container::size_type jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::size_type

Definition at line 55 of file multimap.hpp.

◆ value_type

template<typename _Key , typename _Val , typename _Pred = std::less<_Key>, typename _Cont = std::vector<std::pair<_Key,_Val> >>
typedef std::pair<const key_type,mapped_type> jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::value_type

Definition at line 51 of file multimap.hpp.

Constructor & Destructor Documentation

◆ multimap() [1/4]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
__stdcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::multimap ( const _Pred &  pr = _Pred(),
const allocator_type &  al = allocator_type() 
)
inlineexplicit

Definition at line 24 of file multimap_impl.hpp.

◆ multimap() [2/4]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
__stdcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::multimap ( const size_type  n,
const value_type &  v = value_type(),
const _Pred &  pr = _Pred(),
const allocator_type &  al = allocator_type() 
)
inline

Definition at line 29 of file multimap_impl.hpp.

◆ multimap() [3/4]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
__stdcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::multimap ( const multimap< _Key, _Val, _Pred, _Cont > &  m)
inline

Definition at line 34 of file multimap_impl.hpp.

◆ multimap() [4/4]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
__stdcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::multimap ( const const_iterator &  b,
const const_iterator &  e,
const _Pred &  pr = _Pred(),
const allocator_type &  al = allocator_type() 
)
inline

Definition at line 39 of file multimap_impl.hpp.

◆ ~multimap()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
__stdcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::~multimap ( void  )
inline

Definition at line 44 of file multimap_impl.hpp.

Member Function Documentation

◆ begin() [1/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::const_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::begin ( void  ) const
inlinenoexcept

Definition at line 67 of file multimap_impl.hpp.

◆ begin() [2/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::begin ( void  )
inlinenoexcept

Definition at line 75 of file multimap_impl.hpp.

◆ clear()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
void __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::clear ( void  )
inline

Definition at line 146 of file multimap_impl.hpp.

◆ empty()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
bool __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::empty ( void  ) const
inlinenoexcept

Definition at line 141 of file multimap_impl.hpp.

◆ end() [1/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::const_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::end ( void  ) const
inlinenoexcept

Definition at line 99 of file multimap_impl.hpp.

◆ end() [2/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::end ( void  )
inlinenoexcept

Definition at line 107 of file multimap_impl.hpp.

◆ erase() [1/3]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::erase ( const iterator &  i)
inline

Erase: O(n).

Definition at line 197 of file multimap_impl.hpp.

◆ erase() [2/3]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::erase ( const iterator &  f,
const iterator &  l 
)
inline

Erase: O(n).

Definition at line 202 of file multimap_impl.hpp.

◆ erase() [3/3]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
const multimap< _Key, _Val, _Pred, _Cont >::size_type __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::erase ( const key_type &  key)
inline

Erase: O(nlog(n)). All keys with same value are erased. Collection remains sorted.

Definition at line 233 of file multimap_impl.hpp.

◆ find() [1/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::const_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::find ( const key_type &  key) const
inline

Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multimap or not. Are guaranteed to return the first key if they are not unique in the multimap.

Definition at line 261 of file multimap_impl.hpp.

◆ find() [2/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::find ( const key_type &  key)
inline

Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multimap or not. Are guaranteed to return the first key if they are not unique in the multimap.

Definition at line 275 of file multimap_impl.hpp.

◆ get_allocator()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::allocator_type __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::get_allocator ( void  ) const
inline

Definition at line 168 of file multimap_impl.hpp.

◆ insert() [1/3]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
void __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::insert ( const const_iterator &  f,
const const_iterator &  l 
)
inline

Insert: (with insert()) constant time. (But unsorts the multimap.) Allows the insertion of multiple keys with the same value, but different referents.

Definition at line 190 of file multimap_impl.hpp.

◆ insert() [2/3]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::insert ( const iterator &  i,
const value_type &  v 
)
inline

Insert: (with insert()) constant time. (But unsorts the multimap.) Allows the insertion of multiple keys with the same value, but different referents.

Definition at line 182 of file multimap_impl.hpp.

◆ insert() [3/3]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::InsertItr_ __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::insert ( const value_type &  val)
inline

Insert: (with insert()) constant time. (But unsorts the multimap.) Allows the insertion of multiple keys with the same value, but different referents.

Definition at line 173 of file multimap_impl.hpp.

◆ max_size()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
const multimap< _Key, _Val, _Pred, _Cont >::size_type __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::max_size ( void  ) const
inlinenoexcept

Definition at line 136 of file multimap_impl.hpp.

◆ operator=()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont > &__fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::operator= ( const multimap< _Key, _Val, _Pred, _Cont > &  m)
inline

Definition at line 48 of file multimap_impl.hpp.

◆ operator[]()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::mapped_type &__fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::operator[] ( const key_type &  key)
inline

Lookup: O(log(n)+(complexity of sorting a vector)), if unsorted, O(log(n)) if sorted, irrespective if the element is in the multimap or not. Will only insert the key if it is not in the map, i.e. it will ensure keys are unique, but will be slower. Are guaranteed to return the first key if they are not unique in the multimap.

Definition at line 247 of file multimap_impl.hpp.

◆ rbegin() [1/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::const_reverse_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::rbegin ( void  ) const
inlinenoexcept

Definition at line 83 of file multimap_impl.hpp.

◆ rbegin() [2/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::reverse_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::rbegin ( void  )
inlinenoexcept

Definition at line 91 of file multimap_impl.hpp.

◆ rend() [1/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::const_reverse_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::rend ( void  ) const
inlinenoexcept

Definition at line 115 of file multimap_impl.hpp.

◆ rend() [2/2]

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
multimap< _Key, _Val, _Pred, _Cont >::reverse_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::rend ( void  )
inlinenoexcept

Definition at line 123 of file multimap_impl.hpp.

◆ reserve()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
void __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::reserve ( const size_type  new_sz)
inline

Definition at line 160 of file multimap_impl.hpp.

◆ resize()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
void __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::resize ( const size_type  new_sz,
const value_type &  v = value_type() 
)
inline

Definition at line 152 of file multimap_impl.hpp.

◆ size()

template<typename _Key , typename _Val , typename _Pred , typename _Cont >
const multimap< _Key, _Val, _Pred, _Cont >::size_type __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multimap< _Key, _Val, _Pred, _Cont >::size ( void  ) const
inlinenoexcept

Definition at line 131 of file multimap_impl.hpp.

The documentation for this class was generated from the following files: