libMesh
Classes | Public Types | Public Member Functions | Private Attributes | List of all members
libMesh::vectormap< Key, Tp > Class Template Reference


This vectormap templated class is intended to provide the performance characteristics of a sorted std::vector with an interface more closely resembling that of a std::map, for use in particular when memory is tight. More...

#include <vectormap.h>

Inheritance diagram for libMesh::vectormap< Key, Tp >:
[legend]

Classes

struct  FirstCompare
 Equality comparison, based solely on first element in a pair. More...
 
struct  FirstOrder
 Strict weak ordering, based solely on first element in a pair. More...
 

Public Types

typedef Key key_type
 
typedef Tp mapped_type
 
typedef std::pair< Key, Tp > value_type
 
typedef std::vector< value_typevector_type
 
typedef vector_type::difference_type difference_type
 
typedef vector_type::iterator iterator
 
typedef vector_type::const_iterator const_iterator
 

Public Member Functions

 vectormap ()
 Default constructor. More...
 
 vectormap (const vectormap< Key, Tp > &other)
 Copy constructor. More...
 
void insert (const value_type &x)
 Inserts x into the vectormap. More...
 
template<class... Args>
void emplace (Args &&... args)
 Inserts x into the vector map, using "args" to construct it in-place. More...
 
void sort ()
 Sort & unique the vectormap, preparing for use. More...
 
const Tp & operator[] (const key_type &key) const
 
iterator find (const key_type &key)
 
const_iterator find (const key_type &key) const
 
difference_type count (const key_type &key) const
 

Private Attributes

bool _sorted
 

Detailed Description

template<typename Key, typename Tp>
class libMesh::vectormap< Key, Tp >


This vectormap templated class is intended to provide the performance characteristics of a sorted std::vector with an interface more closely resembling that of a std::map, for use in particular when memory is tight.

This class is limited in its applicability. The typical use case is:

* vectormap<KeyType,ValType> vmap;
* for ( ; ;)
* vmap.insert (std::make_pair(key,val));
*
* val1 = vmap[key1];
* val2 = vmap[key2];
* 
Note
The two-phase usage. It is not advised to do intermediate insert/lookups, as each time an insertion is done the sort is invalidated, and must be reperformed. Additionally, during the insertion phase, there is no accounting for duplicate keys. Each insertion is accepted regardless of key value, and then duplicate keys are removed later.
Author
Benjamin S. Kirk

Definition at line 61 of file vectormap.h.

Member Typedef Documentation

◆ const_iterator

template<typename Key, typename Tp>
typedef vector_type::const_iterator libMesh::vectormap< Key, Tp >::const_iterator

Definition at line 72 of file vectormap.h.

◆ difference_type

template<typename Key, typename Tp>
typedef vector_type::difference_type libMesh::vectormap< Key, Tp >::difference_type

Definition at line 70 of file vectormap.h.

◆ iterator

template<typename Key, typename Tp>
typedef vector_type::iterator libMesh::vectormap< Key, Tp >::iterator

Definition at line 71 of file vectormap.h.

◆ key_type

template<typename Key, typename Tp>
typedef Key libMesh::vectormap< Key, Tp >::key_type

Definition at line 66 of file vectormap.h.

◆ mapped_type

template<typename Key, typename Tp>
typedef Tp libMesh::vectormap< Key, Tp >::mapped_type

Definition at line 67 of file vectormap.h.

◆ value_type

template<typename Key, typename Tp>
typedef std::pair<Key, Tp> libMesh::vectormap< Key, Tp >::value_type

Definition at line 68 of file vectormap.h.

◆ vector_type

template<typename Key, typename Tp>
typedef std::vector<value_type> libMesh::vectormap< Key, Tp >::vector_type

Definition at line 69 of file vectormap.h.

Constructor & Destructor Documentation

◆ vectormap() [1/2]

template<typename Key, typename Tp>
libMesh::vectormap< Key, Tp >::vectormap ( )
inline

Default constructor.

Initializes sorted member to false.

Definition at line 101 of file vectormap.h.

101  :
102  _sorted(false)
103  {}

◆ vectormap() [2/2]

template<typename Key, typename Tp>
libMesh::vectormap< Key, Tp >::vectormap ( const vectormap< Key, Tp > &  other)
inline

Copy constructor.

Definition at line 108 of file vectormap.h.

108  :
109  std::vector<std::pair<Key, Tp>> (other),
110  _sorted(other._sorted)
111  {}

Member Function Documentation

◆ count()

template<typename Key, typename Tp>
difference_type libMesh::vectormap< Key, Tp >::count ( const key_type key) const
inline
Returns
The number of occurrences of key.

For a map-like object, this should be 1 or 0.

Definition at line 221 of file vectormap.h.

References libMesh::vectormap< Key, Tp >::_sorted, libMesh::libmesh_assert(), and libMesh::vectormap< Key, Tp >::sort().

Referenced by VectormapTest::iterate(), and VectormapTest::testFind().

222  {
223  if (!_sorted)
224  const_cast<vectormap<Key, Tp> *>(this)->sort();
225 
227 
228  value_type to_find;
229  to_find.first = key;
230 
231  const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
232 
233  // If we didn't find the key, the count is 0.
234  if (lb == this->end() || lb->first != key)
235  return 0;
236 
237  return 1;
238  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
vector_type::const_iterator const_iterator
Definition: vectormap.h:72
void sort()
Sort & unique the vectormap, preparing for use.
Definition: vectormap.h:136
libmesh_assert(ctx)

◆ emplace()

template<typename Key, typename Tp>
template<class... Args>
void libMesh::vectormap< Key, Tp >::emplace ( Args &&...  args)
inline

Inserts x into the vector map, using "args" to construct it in-place.

Definition at line 127 of file vectormap.h.

References libMesh::vectormap< Key, Tp >::_sorted.

Referenced by VectormapTest::emplace().

128  {
129  _sorted = false;
130  this->emplace_back(args...);
131  }

◆ find() [1/2]

template<typename Key, typename Tp>
iterator libMesh::vectormap< Key, Tp >::find ( const key_type key)
inline
Returns
An iterator corresponding to key, or the end iterator if not found.

Definition at line 171 of file vectormap.h.

References libMesh::vectormap< Key, Tp >::_sorted, libMesh::libmesh_assert(), and libMesh::vectormap< Key, Tp >::sort().

Referenced by VectormapTest::testFind().

172  {
173  if (!_sorted)
174  this->sort();
175 
177 
178  value_type to_find;
179  to_find.first = key;
180 
181  iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
182 
183  // If we didn't find the key, return end()
184  if (lb == this->end() || lb->first != key)
185  return this->end();
186 
187  return lb;
188  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
void sort()
Sort & unique the vectormap, preparing for use.
Definition: vectormap.h:136
libmesh_assert(ctx)
vector_type::iterator iterator
Definition: vectormap.h:71

◆ find() [2/2]

template<typename Key, typename Tp>
const_iterator libMesh::vectormap< Key, Tp >::find ( const key_type key) const
inline
Returns
An iterator corresponding to key, or the end iterator if not found.

Definition at line 194 of file vectormap.h.

References libMesh::vectormap< Key, Tp >::_sorted, libMesh::libmesh_assert(), and libMesh::vectormap< Key, Tp >::sort().

195  {
196  // This function isn't really const, we might have to sort the
197  // underlying container before we can search in it.
198  if (!_sorted)
199  const_cast<vectormap<Key, Tp> *>(this)->sort();
200 
202 
203  value_type to_find;
204  to_find.first = key;
205 
206  const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
207 
208  // If we didn't find the key, return end()
209  if (lb == this->end() || lb->first != key)
210  return this->end();
211 
212  return lb;
213  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
vector_type::const_iterator const_iterator
Definition: vectormap.h:72
void sort()
Sort & unique the vectormap, preparing for use.
Definition: vectormap.h:136
libmesh_assert(ctx)

◆ insert()

template<typename Key, typename Tp>
void libMesh::vectormap< Key, Tp >::insert ( const value_type x)
inline

Inserts x into the vectormap.

Definition at line 116 of file vectormap.h.

References libMesh::vectormap< Key, Tp >::_sorted.

Referenced by VectormapTest::insert(), VectormapTest::iterate(), and VectormapTest::testFind().

117  {
118  _sorted = false;
119  this->push_back(x);
120  }

◆ operator[]()

template<typename Key, typename Tp>
const Tp& libMesh::vectormap< Key, Tp >::operator[] ( const key_type key) const
inline
Returns
The value corresponding to key

Definition at line 148 of file vectormap.h.

References libMesh::vectormap< Key, Tp >::_sorted, libMesh::libmesh_assert(), and libMesh::vectormap< Key, Tp >::sort().

149  {
150  if (!_sorted)
151  const_cast<vectormap<Key, Tp> *>(this)->sort();
152 
154 
155  value_type to_find;
156  to_find.first = key;
157 
158  const_iterator lower_bound = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
159 
160  libmesh_error_msg_if(lower_bound == this->end() || lower_bound->first != key,
161  "Error in vectormap::operator[], key not found. "
162  "If you are searching for values you aren't sure exist, try vectormap::find() instead.");
163 
164  return lower_bound->second;
165  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
vector_type::const_iterator const_iterator
Definition: vectormap.h:72
void sort()
Sort & unique the vectormap, preparing for use.
Definition: vectormap.h:136
libmesh_assert(ctx)

◆ sort()

template<typename Key, typename Tp>
void libMesh::vectormap< Key, Tp >::sort ( )
inline

Sort & unique the vectormap, preparing for use.

Definition at line 136 of file vectormap.h.

References libMesh::vectormap< Key, Tp >::_sorted.

Referenced by libMesh::vectormap< Key, Tp >::count(), VectormapTest::emplace(), libMesh::vectormap< Key, Tp >::find(), VectormapTest::insert(), VectormapTest::iterate(), and libMesh::vectormap< Key, Tp >::operator[]().

137  {
138  std::sort (this->begin(), this->end(), FirstOrder());
139 
140  this->erase (std::unique (this->begin(), this->end(), FirstCompare()), this->end());
141 
142  _sorted = true;
143  }

Member Data Documentation

◆ _sorted

template<typename Key, typename Tp>
bool libMesh::vectormap< Key, Tp >::_sorted
private

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