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::multiset< _Key, _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 _Pred key_compare
 
typedef const key_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 multiset (const _Pred &pr=_Pred(), const allocator_type &al=allocator_type()) FORCE_INLINE
 
__stdcall multiset (const size_type, const value_type &v=value_type(), const _Pred &pr=_Pred(), const allocator_type &al=allocator_type()) FORCE_INLINE
 
__stdcall multiset (const multiset &) FORCE_INLINE
 
__stdcall multiset (const const_iterator &, const const_iterator &, const _Pred &pr=_Pred(), const allocator_type &al=allocator_type()) FORCE_INLINE
 
__stdcall ~multiset (void) FORCE_INLINE
 
multiset &__fastcall operator= (const multiset &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
 
const_iterator __fastcall find (const key_type &) const FORCE_INLINE
 
iterator __fastcall find (const key_type &) FORCE_INLINE
 

Detailed Description

template<typename _Key, typename _Pred = std::less<_Key>, typename _Cont = std::vector<_Key>>
class jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multiset< _Key, _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 multiset.
  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 179 of file multimap.hpp.

Member Typedef Documentation

◆ allocator_type

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

Definition at line 182 of file multimap.hpp.

◆ base_container

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

Definition at line 181 of file multimap.hpp.

◆ const_iterator

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

Definition at line 190 of file multimap.hpp.

◆ const_reference

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

Definition at line 188 of file multimap.hpp.

◆ const_reverse_iterator

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

Definition at line 193 of file multimap.hpp.

◆ difference_type

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

Definition at line 186 of file multimap.hpp.

◆ InsertItr_

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

Definition at line 194 of file multimap.hpp.

◆ iterator

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

Definition at line 191 of file multimap.hpp.

◆ key_compare

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

Definition at line 184 of file multimap.hpp.

◆ key_type

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

Definition at line 183 of file multimap.hpp.

◆ reference

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

Definition at line 187 of file multimap.hpp.

◆ reverse_iterator

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

Definition at line 192 of file multimap.hpp.

◆ size_type

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

Definition at line 189 of file multimap.hpp.

◆ value_type

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

Definition at line 185 of file multimap.hpp.

Constructor & Destructor Documentation

◆ multiset() [1/4]

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

Definition at line 291 of file multimap_impl.hpp.

◆ multiset() [2/4]

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

Definition at line 296 of file multimap_impl.hpp.

◆ multiset() [3/4]

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

Definition at line 301 of file multimap_impl.hpp.

◆ multiset() [4/4]

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

Definition at line 306 of file multimap_impl.hpp.

◆ ~multiset()

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

Definition at line 311 of file multimap_impl.hpp.

Member Function Documentation

◆ begin() [1/2]

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

Definition at line 334 of file multimap_impl.hpp.

◆ begin() [2/2]

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

Definition at line 342 of file multimap_impl.hpp.

◆ clear()

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

Definition at line 413 of file multimap_impl.hpp.

◆ empty()

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

Definition at line 408 of file multimap_impl.hpp.

◆ end() [1/2]

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

Definition at line 366 of file multimap_impl.hpp.

◆ end() [2/2]

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

Definition at line 374 of file multimap_impl.hpp.

◆ erase() [1/3]

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

Erase: O(n).

Definition at line 464 of file multimap_impl.hpp.

◆ erase() [2/3]

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

Erase: O(n).

Definition at line 469 of file multimap_impl.hpp.

◆ erase() [3/3]

template<typename _Key , typename _Pred , typename _Cont >
const multiset< _Key, _Pred, _Cont >::size_type __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multiset< _Key, _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 500 of file multimap_impl.hpp.

◆ find() [1/2]

template<typename _Key , typename _Pred , typename _Cont >
multiset< _Key, _Pred, _Cont >::const_iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multiset< _Key, _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 multiset or not. Are guaranteed to return the first key if they are not unique in the multiset.

Definition at line 514 of file multimap_impl.hpp.

◆ find() [2/2]

template<typename _Key , typename _Pred , typename _Cont >
multiset< _Key, _Pred, _Cont >::iterator __fastcall jmmcg::LIBJMMCG_VER_NAMESPACE::rapid_insert_lookup::multiset< _Key, _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 multiset or not. Are guaranteed to return the first key if they are not unique in the multiset.

Definition at line 528 of file multimap_impl.hpp.

◆ get_allocator()

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

Definition at line 435 of file multimap_impl.hpp.

◆ insert() [1/3]

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

Insert: (with insert()) constant time. (But unsorts the multiset.) Allows the insertion of multiple keys with the same value.

Definition at line 457 of file multimap_impl.hpp.

◆ insert() [2/3]

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

Insert: (with insert()) constant time. (But unsorts the multiset.) Allows the insertion of multiple keys with the same value.

Definition at line 449 of file multimap_impl.hpp.

◆ insert() [3/3]

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

Insert: (with insert()) constant time. (But unsorts the multiset.) Allows the insertion of multiple keys with the same value.

Definition at line 440 of file multimap_impl.hpp.

◆ max_size()

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

Definition at line 403 of file multimap_impl.hpp.

◆ operator=()

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

Definition at line 315 of file multimap_impl.hpp.

◆ rbegin() [1/2]

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

Definition at line 350 of file multimap_impl.hpp.

◆ rbegin() [2/2]

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

Definition at line 358 of file multimap_impl.hpp.

◆ rend() [1/2]

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

Definition at line 382 of file multimap_impl.hpp.

◆ rend() [2/2]

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

Definition at line 390 of file multimap_impl.hpp.

◆ reserve()

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

Definition at line 427 of file multimap_impl.hpp.

◆ resize()

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

Definition at line 419 of file multimap_impl.hpp.

◆ size()

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

Definition at line 398 of file multimap_impl.hpp.

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