libMesh::vectormap< Key, Tp > Class Template Reference

#include <vectormap.h>

Inheritance diagram for libMesh::vectormap< Key, Tp >:

Classes

struct  FirstCompare
 
struct  FirstOrder
 

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 ()
 
 vectormap (const vectormap< Key, Tp > &other)
 
void insert (const value_type &x)
 
void sort ()
 
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 insersion 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

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

Definition at line 72 of file vectormap.h.

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

Definition at line 70 of file vectormap.h.

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

Definition at line 71 of file vectormap.h.

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

Definition at line 66 of file vectormap.h.

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

Definition at line 67 of file vectormap.h.

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

Definition at line 68 of file vectormap.h.

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

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  {}
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

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 210 of file vectormap.h.

Referenced by libMesh::ParmetisPartitioner::initialize(), and libMesh::MetisPartitioner::partition_range().

211  {
212  if (!_sorted)
213  const_cast<vectormap<Key, Tp> *>(this)->sort();
214 
216 
217  value_type to_find;
218  to_find.first = key;
219 
220  const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
221 
222  // If we didn't find the key, the count is 0.
223  if (lb == this->end() || lb->first != key)
224  return 0;
225 
226  return 1;
227  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
vector_type::const_iterator const_iterator
Definition: vectormap.h:72
IterBase * end
libmesh_assert(j)
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 160 of file vectormap.h.

Referenced by libMesh::MetisPartitioner::partition_range().

161  {
162  if (!_sorted)
163  this->sort();
164 
166 
167  value_type to_find;
168  to_find.first = key;
169 
170  iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
171 
172  // If we didn't find the key, return end()
173  if (lb == this->end() || lb->first != key)
174  return this->end();
175 
176  return lb;
177  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
IterBase * end
libmesh_assert(j)
vector_type::iterator iterator
Definition: vectormap.h:71
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 183 of file vectormap.h.

184  {
185  // This function isn't really const, we might have to sort the
186  // underlying container before we can search in it.
187  if (!_sorted)
188  const_cast<vectormap<Key, Tp> *>(this)->sort();
189 
191 
192  value_type to_find;
193  to_find.first = key;
194 
195  const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
196 
197  // If we didn't find the key, return end()
198  if (lb == this->end() || lb->first != key)
199  return this->end();
200 
201  return lb;
202  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
vector_type::const_iterator const_iterator
Definition: vectormap.h:72
IterBase * end
libmesh_assert(j)
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.

Referenced by libMesh::ParmetisPartitioner::initialize(), and libMesh::MetisPartitioner::partition_range().

117  {
118  _sorted = false;
119  this->push_back(x);
120  }
PetscErrorCode Vec x
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 137 of file vectormap.h.

138  {
139  if (!_sorted)
140  const_cast<vectormap<Key, Tp> *>(this)->sort();
141 
143 
144  value_type to_find;
145  to_find.first = key;
146 
147  const_iterator lower_bound = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());
148 
149  if (lower_bound == this->end() || lower_bound->first != key)
150  libmesh_error_msg("Error in vectormap::operator[], key not found. "
151  "If you are searching for values you aren't sure exist, try vectormap::find() instead.");
152 
153  return lower_bound->second;
154  }
std::pair< Key, Tp > value_type
Definition: vectormap.h:68
vector_type::const_iterator const_iterator
Definition: vectormap.h:72
IterBase * end
libmesh_assert(j)
template<typename Key, typename Tp>
void libMesh::vectormap< Key, Tp >::sort ( )
inline

Sort & unique the vectormap, preparing for use.

Definition at line 125 of file vectormap.h.

Referenced by libMesh::vectormap< dof_id_type, dof_id_type >::count(), libMesh::vectormap< dof_id_type, dof_id_type >::find(), and libMesh::vectormap< dof_id_type, dof_id_type >::operator[]().

126  {
127  std::sort (this->begin(), this->end(), FirstOrder());
128 
129  this->erase (std::unique (this->begin(), this->end(), FirstCompare()), this->end());
130 
131  _sorted = true;
132  }
IterBase * end

Member Data Documentation


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