template class mrpt::containers::map_as_vector

Overview

A STL-like container which looks and behaves (almost exactly) like a std::map<> but is implemented as a linear std::vector<> indexed by KEY.

Note that KEY must be integer types only (size_t, uint32_t, etc.) This implementation is much more efficient than std::map<> when the most common operation is accessing elements by KEY with find() or [], and the range of KEY values starts at 0 (or a reasonable low number).

This container is internally implemented as a linear array (std::vector) of the same fundamental type than the equivalent std::map<K,V>, that is, elements are std::pair<K,V> (note that K is NOT const as in std::map). I know, I know… this implementation wastes a lot of useless key elements in the pair.first when indices are already implicit in the std::vector<> order… but I promise I’ll pay a beer to whoever show me an efficient alternative. If failed, update this comment: COUNTER OF WASTED HOURS WITH THIS: 3h

Note that there is one fundamental difference wrt std::map<>: if you start with an empty map_as_vector<> and insert one element at the i’th position (with either [] or insert), the elements [0,i-1] will also exist then, but both their first & second entries (for the corresponding std::pair) will be undefined. This was intentional in order to gain efficiency (in particular, each std::pair<> doesn’t have a constructor when resizing the underlying std::vector).

The default underlying non-associative container is a “memory-aligned std::vector<>”, but it can be changed to a standard vector<> or to a deque<> (to avoid memory reallocations) by changing the template parameter VECTOR_T.

Defined in #include <mrpt/containers/map_as_vector.h>

#include <mrpt/containers/map_as_vector.h>

template <
    typename KEY,
    typename VALUE,
    typename VECTOR_T = typename std::vector<std::pair<KEY, VALUE>>
    >
class map_as_vector
{
public:
    // typedefs

    typedef KEY key_type;
    typedef std::pair<KEY, VALUE> value_type;
    typedef VECTOR_T vec_t;
    typedef typename vec_t::size_type size_type;
    typedef typename vec_t::iterator iterator;
    typedef typename vec_t::const_iterator const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    // construction

    map_as_vector();

    // methods

    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;
    size_t size() const;
    bool empty() const;
    size_type count(const key_type i) const;
    size_type max_size() const;
    const vec_t& getVector() const;
    void clear();
    void swap(map_as_vector<KEY, VALUE>& o);
    VALUE& operator [] (size_t i);
    const VALUE& at(size_t i) const;
    VALUE& at(size_t i);
    void insert(const iterator& guess_point, const value_type& keyvalpair);
    void insert(const value_type& keyvalpair);
    iterator find(size_t i);
    const_iterator find(size_t i) const;
};

Construction

map_as_vector()

< Default constructor - does nothing * /

Methods

size_t size() const

Copy constructor & operator= -> default.

size_type count(const key_type i) const

Count how many entries have a given key value - unlike std::map<K,V>, recall that this class will say an element i<N-1 exists just due to an insertion of element at N.

size_type max_size() const

Maximum size due to system limits.

const vec_t& getVector() const

Return a read-only reference to the internal vector.

void clear()

Clear the contents of this container.

void swap(map_as_vector<KEY, VALUE>& o)

Efficient swap with another object.

VALUE& operator [] (size_t i)

Write/read via [i] operator, that creates all elements up to (and including) the i’th if they didn’t exist already.

const VALUE& at(size_t i) const

Read-only operator, throws exception if the given key index does not exist.

VALUE& at(size_t i)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

void insert(const iterator& guess_point, const value_type& keyvalpair)

Insert pair<key,val>, as in std::map (guess_point is actually ignored in this class)

void insert(const value_type& keyvalpair)

Insert pair<key,val>, as in std::map.

iterator find(size_t i)

Constant-time find, returning an iterator to the <key,val> pair or to end() if not found (that is, if it’s above the maximum index in the vector)

const_iterator find(size_t i) const

Constant-time find, returning an iterator to the <key,val> pair or to end() if not found (that is, if it’s above the maximum index in the vector)