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_type >	vector_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 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.

              :
    _sorted(false)
  {}

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.

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

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

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

  {
    if (!_sorted)
      const_cast<vectormap<Key, Tp> *>(this)->sort();

    libmesh_assert (_sorted);

    value_type to_find;
    to_find.first = key;

    const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());

    // If we didn't find the key, the count is 0.
    if (lb == this->end() || lb->first != key)
      return 0;

    return 1;
  }

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

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

  {
    if (!_sorted)
      this->sort();

    libmesh_assert (_sorted);

    value_type to_find;
    to_find.first = key;

    iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());

    // If we didn't find the key, return end()
    if (lb == this->end() || lb->first != key)
      return this->end();

    return lb;
  }

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

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

  {
    // This function isn't really const, we might have to sort the
    // underlying container before we can search in it.
    if (!_sorted)
      const_cast<vectormap<Key, Tp> *>(this)->sort();

    libmesh_assert (_sorted);

    value_type to_find;
    to_find.first = key;

    const_iterator lb = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());

    // If we didn't find the key, return end()
    if (lb == this->end() || lb->first != key)
      return this->end();

    return lb;
  }

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.

  {
    _sorted = false;
    this->push_back(x);
  }

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

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

  {
    if (!_sorted)
      const_cast<vectormap<Key, Tp> *>(this)->sort();

    libmesh_assert (_sorted);

    value_type to_find;
    to_find.first = key;

    const_iterator lower_bound = std::lower_bound (this->begin(), this->end(), to_find, FirstOrder());

    if (lower_bound == this->end() || lower_bound->first != key)
      libmesh_error_msg("Error in vectormap::operator[], key not found. "
                        "If you are searching for values you aren't sure exist, try vectormap::find() instead.");

    return lower_bound->second;
  }

sort()

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.

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

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

  {
    std::sort (this->begin(), this->end(), FirstOrder());

    this->erase (std::unique (this->begin(), this->end(), FirstCompare()), this->end());

    _sorted = true;
  }

Member Data Documentation

_sorted

template<typename Key, typename Tp>

bool libMesh::vectormap< Key, Tp >::_sorted

private

Definition at line 232 of file vectormap.h.

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

---

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

• vectormap.h