$extrastylesheet
Classes | Public Types | Public Member Functions | Private Attributes
libMesh::vectormap< Key, Tp > Class Template Reference

#include <vectormap.h>

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

List of all members.

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

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
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 in particular 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::difference_type libMesh::vectormap< Key, Tp >::difference_type

Definition at line 70 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 99 of file vectormap.h.

              :
    _sorted(false)
  {}
template<typename Key, typename Tp>
libMesh::vectormap< Key, Tp >::vectormap ( const vectormap< Key, Tp > &  other) [inline]

Copy constructor.

Definition at line 106 of file vectormap.h.

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

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 occurances of key. For a map-like object, this should be 1 or 0.

Definition at line 164 of file vectormap.h.

Referenced by libMesh::MetisPartitioner::_do_partition(), libMesh::ParmetisPartitioner::assign_partitioning(), libMesh::ParmetisPartitioner::build_graph(), and libMesh::ParmetisPartitioner::initialize().

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

    libmesh_assert (_sorted);

    value_type to_find;
    to_find.first = key;

    FirstOrder order;

    std::pair<typename vectormap<Key,Tp>::const_iterator,
      typename vectormap<Key,Tp>::const_iterator>
      bounds = std::equal_range (this->begin(), this->end(), to_find, order);

    return std::distance (bounds.first, bounds.second);
  }
template<typename Key, typename Tp>
void libMesh::vectormap< Key, Tp >::insert ( const value_type &  x) [inline]

Inserts x into the vectormap.

Definition at line 114 of file vectormap.h.

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

  {
    _sorted = false;
    this->push_back(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 138 of file vectormap.h.

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

    libmesh_assert (_sorted);

    value_type to_find;
    to_find.first = key;

    FirstOrder order;

    typename vectormap<Key,Tp>::const_iterator
      lower_bound = std::lower_bound (this->begin(), this->end(), to_find, order);

    libmesh_assert (lower_bound != this->end());
    libmesh_assert_equal_to (lower_bound->first, key);

    return lower_bound->second;
  }
template<typename Key, typename Tp>
void libMesh::vectormap< Key, Tp >::sort ( ) [inline]

Sort & unique the vectormap, preparing for use.

Definition at line 123 of file vectormap.h.

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

  {
    FirstOrder   order;
    FirstCompare comp;

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

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

    _sorted = true;
  }

Member Data Documentation

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

Definition at line 186 of file vectormap.h.

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

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