map_as_vector.h

Go to the documentation of this file.

/* +------------------------------------------------------------------------+
   |                     Mobile Robot Programming Toolkit (MRPT)            |
   |                          http://www.mrpt.org/                          |
   |                                                                        |
   | Copyright (c) 2005-2018, Individual contributors, see AUTHORS file     |
   | See: http://www.mrpt.org/Authors - All rights reserved.                |
   | Released under BSD License. See details in http://www.mrpt.org/License |
   +------------------------------------------------------------------------+ */
#ifndef mrpt_map_as_vector_H
#define mrpt_map_as_vector_H
 
#include <mrpt/core/aligned_std_vector.h>
#include <map>
#include <vector>
 
namespace mrpt
{
namespace containers
{
/** 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 accesing 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 <code> std::pair<K,V> </code> (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 <b>fundamental difference</b> 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
 * <b>undefined</b>. 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 \a VECTOR_T.
  *
  * \note Defined in #include <mrpt/containers/map_as_vector.h>
  * \ingroup mrpt_containers_grp
  */
template <typename KEY, typename VALUE,
                  typename VECTOR_T =
                          typename mrpt::aligned_std_vector<std::pair<KEY, VALUE>>>
class map_as_vector
{
   public:
        /** @name Iterators stuff and other types
                @{ */
        using key_type = KEY;
        using value_type = std::pair<KEY, VALUE>;
        using vec_t = VECTOR_T;
        using size_type = typename vec_t::size_type;
        using iterator = typename vec_t::iterator;
        using const_iterator = typename vec_t::const_iterator;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
        inline iterator begin() { return m_vec.begin(); }
        inline iterator end() { return m_vec.end(); }
        inline const_iterator begin() const { return m_vec.begin(); }
        inline const_iterator end() const { return m_vec.end(); }
        inline reverse_iterator rbegin() { return reverse_iterator(end()); }
        inline const_reverse_iterator rbegin() const
        {
                return const_reverse_iterator(end());
        }
        inline reverse_iterator rend() { return reverse_iterator(begin()); }
        inline const_reverse_iterator rend() const
        {
                return const_reverse_iterator(begin());
        }
        /** @} */
   private:
        /** The actual container */
        vec_t m_vec;
 
   public:
        /** @name Constructors, read/write access and other operations
                @{ */
        //!< Default constructor - does nothing */
        inline map_as_vector() {}
        /** Copy constructor */
        inline map_as_vector(const map_as_vector<KEY, VALUE>& o) : m_vec(o.m_vec) {}
        inline size_t size() const { return m_vec.size(); }
        inline bool empty() const { return m_vec.empty(); }
        /** 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 */
        inline size_type count(const key_type i) const
        {
                return (i < m_vec.size()) ? 1 : 0;
        }
 
        /** Maximum size due to system limits */
        inline size_type max_size() const { return m_vec.max_size(); }
        /** Return a read-only reference to the internal vector */
        inline const vec_t& getVector() const { return m_vec; }
        /** Clear the contents of this container */
        inline void clear() { m_vec.clear(); }
        /** Efficient swap with another object */
        inline void swap(map_as_vector<KEY, VALUE>& o) { m_vec.swap(o.m_vec); }
        /** Write/read via [i] operator, that creates all elements up to (and
         * including) the i'th if they didn't exist already. */
        inline VALUE& operator[](const size_t i)
        {
                if (m_vec.size() <= i) m_vec.resize(i + 1);
                m_vec[i].first = i;
                return m_vec[i].second;
        }
 
        /** Insert pair<key,val>, as in std::map (guess_point is actually ignored in
         * this class) */
        inline void insert(
                const iterator& guess_point, const value_type& keyvalpair)
        {
                this->operator[](keyvalpair.first) = keyvalpair;
        }
        /** Insert pair<key,val>, as in std::map */
        inline void insert(const value_type& keyvalpair)
        {
                this->operator[](keyvalpair.first) = keyvalpair;
        }
 
        /** 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) */
        inline iterator find(const size_t i)
        {
                if (i < m_vec.size())
                        return m_vec.begin() + i;
                else
                        return m_vec.end();
        }
        /** 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) */
        inline const_iterator find(const size_t i) const
        {
                if (i < m_vec.size())
                        return m_vec.begin() + i;
                else
                        return m_vec.end();
        }
 
        /** @} */
 
};  // end class map_as_vector
 
}  // End of namespace
}  // End of namespace
#endif