libjmmcg  build_2783
A C++ library containing an eclectic mix of useful, advanced components.
jmmcg::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 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, boolInsertItr_
 

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
 

Public Attributes

const typedef key_type value_type
 

Detailed Description

template<typename _Key, typename _Pred = std::less<_Key>, typename _Cont = std::vector<_Key>>
class jmmcg::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 212 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::allocator_type

Definition at line 215 of file multimap.hpp.

◆ base_container

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

Definition at line 214 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::const_iterator

Definition at line 223 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::const_reference

Definition at line 221 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::const_reverse_iterator

Definition at line 226 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::difference_type

Definition at line 219 of file multimap.hpp.

◆ InsertItr_

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

Definition at line 227 of file multimap.hpp.

◆ iterator

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

Definition at line 224 of file multimap.hpp.

◆ key_compare

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

Definition at line 217 of file multimap.hpp.

◆ key_type

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

Definition at line 216 of file multimap.hpp.

◆ reference

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

Definition at line 220 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::reverse_iterator

Definition at line 225 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::size_type

Definition at line 222 of file multimap.hpp.

Constructor & Destructor Documentation

◆ multiset() [1/4]

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

Definition at line 326 of file multimap_impl.hpp.

◆ multiset() [2/4]

template<typename _Key , typename _Pred , typename _Cont >
__stdcall jmmcg::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 331 of file multimap_impl.hpp.

◆ multiset() [3/4]

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

Definition at line 336 of file multimap_impl.hpp.

◆ multiset() [4/4]

template<typename _Key , typename _Pred , typename _Cont >
__stdcall jmmcg::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 341 of file multimap_impl.hpp.

◆ ~multiset()

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

Definition at line 346 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::rapid_insert_lookup::multiset< _Key, _Pred, _Cont >::begin ( void  ) const
inlinenoexcept

Definition at line 369 of file multimap_impl.hpp.

◆ begin() [2/2]

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

Definition at line 377 of file multimap_impl.hpp.

◆ clear()

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

Definition at line 448 of file multimap_impl.hpp.

◆ empty()

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

Definition at line 443 of file multimap_impl.hpp.

◆ end() [1/2]

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

Definition at line 401 of file multimap_impl.hpp.

◆ end() [2/2]

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

Definition at line 409 of file multimap_impl.hpp.

◆ erase() [1/3]

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

Erase: O(n).

Definition at line 499 of file multimap_impl.hpp.

◆ erase() [2/3]

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

Erase: O(n).

Definition at line 504 of file multimap_impl.hpp.

◆ erase() [3/3]

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

◆ find() [1/2]

template<typename _Key , typename _Pred , typename _Cont >
multiset< _Key, _Pred, _Cont >::const_iterator __fastcall jmmcg::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 549 of file multimap_impl.hpp.

◆ find() [2/2]

template<typename _Key , typename _Pred , typename _Cont >
multiset< _Key, _Pred, _Cont >::iterator __fastcall jmmcg::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 563 of file multimap_impl.hpp.

◆ get_allocator()

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

Definition at line 470 of file multimap_impl.hpp.

◆ insert() [1/3]

template<typename _Key , typename _Pred , typename _Cont >
void __fastcall jmmcg::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 492 of file multimap_impl.hpp.

◆ insert() [2/3]

template<typename _Key , typename _Pred , typename _Cont >
multiset< _Key, _Pred, _Cont >::iterator __fastcall jmmcg::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 484 of file multimap_impl.hpp.

◆ insert() [3/3]

template<typename _Key , typename _Pred , typename _Cont >
multiset< _Key, _Pred, _Cont >::InsertItr_ __fastcall jmmcg::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 475 of file multimap_impl.hpp.

◆ max_size()

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

Definition at line 438 of file multimap_impl.hpp.

◆ operator=()

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

Definition at line 350 of file multimap_impl.hpp.

◆ rbegin() [1/2]

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

Definition at line 385 of file multimap_impl.hpp.

◆ rbegin() [2/2]

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

Definition at line 393 of file multimap_impl.hpp.

◆ rend() [1/2]

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

Definition at line 417 of file multimap_impl.hpp.

◆ rend() [2/2]

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

Definition at line 425 of file multimap_impl.hpp.

◆ reserve()

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

Definition at line 462 of file multimap_impl.hpp.

◆ resize()

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

Definition at line 454 of file multimap_impl.hpp.

◆ size()

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

Definition at line 433 of file multimap_impl.hpp.

Member Data Documentation

◆ value_type

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

Definition at line 218 of file multimap.hpp.


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