map_as_vector.h

Go to the documentation of this file.

/* +------------------------------------------------------------------------+
   |                     Mobile Robot Programming Toolkit (MRPT)            |
   |                          https://www.mrpt.org/                         |
   |                                                                        |
   | Copyright (c) 2005-2020, Individual contributors, see AUTHORS file     |
   | See: https://www.mrpt.org/Authors - All rights reserved.               |
   | Released under BSD License. See: https://www.mrpt.org/License          |
   +------------------------------------------------------------------------+ */
#pragma once

#include <map>
#include <vector>

namespace mrpt::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 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() = default;
    /** 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

}  // namespace mrpt::containers