Open Model Railroad Network (OpenMRN)
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
SortedListSet< D, CMP > Class Template Reference

An mostly std::set<> compatible class that stores the internal data in a sorted vector. More...

#include <SortedListMap.hxx>

Public Types

typedef D data_type
 Type of data stored in the set.
 
typedef container_type::iterator iterator
 Iterator type.
 
typedef container_type::const_iterator const_iterator
 Const Iterator type.
 

Public Member Functions

template<typename... Args>
 SortedListSet (Args &&...args)
 
void reserve (size_t sz)
 Ensures that a given size can be reached without memory allocation.
 
iterator begin ()
 
iterator end ()
 
size_t size ()
 
template<class key_type >
iterator lower_bound (key_type key)
 
template<class key_type >
iterator upper_bound (key_type key)
 
template<class key_type >
iterator find (key_type key)
 Searches for a single entry.
 
template<class key_type >
std::pair< iterator, iterator > equal_range (key_type key)
 
void insert (data_type &&d)
 Adds new entry to the vector.
 
void erase (const iterator &it)
 Removes an entry from the vector, pointed by an iterator.
 
void erase (const iterator &it_b, const iterator &it_e)
 Removes a sequence of entries from the vector, pointed by a pair of iterators.
 
void clear ()
 Removes all entries.
 

Private Types

typedef std::vector< data_type > container_type
 Type that we store data in internally.
 

Private Member Functions

void lazy_init ()
 Reestablishes sorted order in case anything was inserted or removed.
 

Private Attributes

container_type container_
 Holds the actual data elements.
 
CMP cmp_
 Comparator instance.
 
size_t sortedCount_ {0}
 The first this many elements in the container are already sorted.
 

Detailed Description

template<class D, class CMP>
class SortedListSet< D, CMP >

An mostly std::set<> compatible class that stores the internal data in a sorted vector.

Has low memory overhead; insertion cost is pretty high and lookup cost is logarithmic. Useful when a few insertions happen (for example only during initialization) and then lots of lookups are made.

Definition at line 46 of file SortedListMap.hxx.

Member Typedef Documentation

◆ const_iterator

template<class D , class CMP >
typedef container_type::const_iterator SortedListSet< D, CMP >::const_iterator

Const Iterator type.

Definition at line 60 of file SortedListMap.hxx.

◆ container_type

template<class D , class CMP >
typedef std::vector<data_type> SortedListSet< D, CMP >::container_type
private

Type that we store data in internally.

Definition at line 54 of file SortedListMap.hxx.

◆ data_type

template<class D , class CMP >
typedef D SortedListSet< D, CMP >::data_type

Type of data stored in the set.

Definition at line 50 of file SortedListMap.hxx.

◆ iterator

template<class D , class CMP >
typedef container_type::iterator SortedListSet< D, CMP >::iterator

Iterator type.

Definition at line 58 of file SortedListMap.hxx.

Constructor & Destructor Documentation

◆ SortedListSet()

template<class D , class CMP >
template<typename... Args>
SortedListSet< D, CMP >::SortedListSet ( Args &&...  args)
inline

Definition at line 63 of file SortedListMap.hxx.

Member Function Documentation

◆ begin()

template<class D , class CMP >
iterator SortedListSet< D, CMP >::begin ( )
inline
Returns
first iterator.

Definition at line 76 of file SortedListMap.hxx.

◆ clear()

template<class D , class CMP >
void SortedListSet< D, CMP >::clear ( )
inline

Removes all entries.

Definition at line 155 of file SortedListMap.hxx.

◆ end()

template<class D , class CMP >
iterator SortedListSet< D, CMP >::end ( )
inline
Returns
last iterator.

Definition at line 83 of file SortedListMap.hxx.

◆ equal_range()

template<class D , class CMP >
template<class key_type >
std::pair< iterator, iterator > SortedListSet< D, CMP >::equal_range ( key_type  key)
inline
Parameters
keywhat to search for
Returns
iterators, see std::equal_range.

Definition at line 125 of file SortedListMap.hxx.

◆ erase() [1/2]

template<class D , class CMP >
void SortedListSet< D, CMP >::erase ( const iterator &  it)
inline

Removes an entry from the vector, pointed by an iterator.

Definition at line 139 of file SortedListMap.hxx.

◆ erase() [2/2]

template<class D , class CMP >
void SortedListSet< D, CMP >::erase ( const iterator &  it_b,
const iterator &  it_e 
)
inline

Removes a sequence of entries from the vector, pointed by a pair of iterators.

Definition at line 148 of file SortedListMap.hxx.

◆ find()

template<class D , class CMP >
template<class key_type >
iterator SortedListSet< D, CMP >::find ( key_type  key)
inline

Searches for a single entry.

Parameters
keyis what to search for.
Returns
end() if search key was not found; else the first entry that is == key.

Definition at line 114 of file SortedListMap.hxx.

◆ insert()

template<class D , class CMP >
void SortedListSet< D, CMP >::insert ( data_type &&  d)
inline

Adds new entry to the vector.

Definition at line 133 of file SortedListMap.hxx.

◆ lazy_init()

template<class D , class CMP >
void SortedListSet< D, CMP >::lazy_init ( )
inlineprivate

Reestablishes sorted order in case anything was inserted or removed.

Definition at line 163 of file SortedListMap.hxx.

◆ lower_bound()

template<class D , class CMP >
template<class key_type >
iterator SortedListSet< D, CMP >::lower_bound ( key_type  key)
inline
Parameters
keywhat to search for
Returns
iterator, see std::lower_bound.

Definition at line 95 of file SortedListMap.hxx.

◆ reserve()

template<class D , class CMP >
void SortedListSet< D, CMP >::reserve ( size_t  sz)
inline

Ensures that a given size can be reached without memory allocation.

Parameters
szthe number of entries to prepare for.

Definition at line 70 of file SortedListMap.hxx.

◆ size()

template<class D , class CMP >
size_t SortedListSet< D, CMP >::size ( )
inline
Returns
the number of entries in the map.

Definition at line 89 of file SortedListMap.hxx.

◆ upper_bound()

template<class D , class CMP >
template<class key_type >
iterator SortedListSet< D, CMP >::upper_bound ( key_type  key)
inline
Parameters
keywhat to search for
Returns
iterator, see std::upper_bound.

Definition at line 104 of file SortedListMap.hxx.

Member Data Documentation

◆ cmp_

template<class D , class CMP >
CMP SortedListSet< D, CMP >::cmp_
private

Comparator instance.

Definition at line 176 of file SortedListMap.hxx.

◆ container_

template<class D , class CMP >
container_type SortedListSet< D, CMP >::container_
private

Holds the actual data elements.

Definition at line 173 of file SortedListMap.hxx.

◆ sortedCount_

template<class D , class CMP >
size_t SortedListSet< D, CMP >::sortedCount_ {0}
private

The first this many elements in the container are already sorted.

Definition at line 179 of file SortedListMap.hxx.

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