vectormap: A C++ Map Class with Order-added Iteration

• Download source code - 1.1 KB

Introduction

New programmers might assume that when they add multiple key-value pairs to a map data structure that the order items were added would be the order you get iterating over the data structure.

Not so!

The C++ Standard Library provides two map data structures, one named, get this, map, the other, unordered_map.

The map class is implemented using a red-black tree, a binary tree that balances itself when items are added to or removed. When you iterate over a map, you get the sort order of the keys. So if you add C, A, B, or any other order, when you iterate, you will always get A, B, C. If that ordering is what you want, you've got it for free...almost. Searching for an item takes O(log(n)) time, so you pay a price for that ordering by keys.

The unordered_map class is implemented as a hash table. As the name implies, there is no ordering for iteration provided at all. Instead, you get sort of a random order, as the items added scatter across the buckets of the hash table. The benefit of unordered_map over map is that searching for items takes O(1).

So what's to be done if you want fast searches and order-added iteration? Read on!

Enter vectormap

#pragma once

#include <stdexcept>
#include <unordered_map>
#include <vector>

namespace mscript
{
    /// <summary>
    /// A vectormap combines a map with its fast key->value lookups
    /// with a vector to preserve the order that key-value pairs were added
    /// </summary>
    /// <typeparam name="K">Key type of the map</typeparam>
    /// <typeparam name="V">Value type of the map</typeparam>
    template <typename K, typename V>
    class vectormap
    {
    public:
        /// <summary>
        /// Access the vector of pairs directly for index access or iteration
        /// </summary>
        const std::vector<std::pair<K, V>>& vec() const
        {
            return m_vec;
        }

        /// <summary>
        /// What is the value for a given key?
        /// NOTE: By returning the value by, well, value
        ///       this function can stay const
        ///       and users of the class can use pointers
        ///       if they want side effects down the line.
        /// </summary>
        V get(const K& key) const
        {
            const auto& it = m_map.find(key);
            if (it == m_map.end())
                throw std::runtime_error("key not found");
            return m_vec[it->second].second;
        }

        /// <summary>
        /// What is the value at a given index?
        /// NOTE: By returning the value by, well, value
        ///       this function can stay const
        ///       and users of the class can use pointers
        ///       if they want side effects down the line.
        /// </summary>
        V getAt(size_t index) const
        {
            if (index >= m_vec.size())
                throw std::runtime_error("index out of range");
            return m_vec[index].second;
        }

        /// <summary>
        /// How many key-value pairs are in this?
        /// </summary>
        size_t size() const
        {
            return m_vec.size();
        }

        /// <summary>
        /// Does this map contain this key?
        /// </summary>
        bool contains(const K& key) const
        {
            return m_map.find(key) != m_map.end();
        }

        /// <summary>
        /// Associate a value with a key
        /// </summary>
        void set(const K& key, const V& val)
        {
            auto it = m_map.find(key);
            if (it == m_map.end())
            {
                m_map.insert({ key, m_vec.size() });
                m_vec.push_back({ key, val });
            }
            else
                m_vec[it->second].second = val;
        }

        /// <summary>
        /// Get a value, checking if it exists first
        /// </summary>
        /// <param name="key">Key value to look up</param>
        /// <param name="val">Value to populate</param>
        /// <returns>true if a value exists for the key, false otherwise</returns>
        bool tryGet(const K& key, V& val) const
        {
            const auto& it = m_map.find(key);
            if (it == m_map.end())
                return false;

            val = m_vec[it->second].second;
            return true;
        }

        /// <summary>
        /// Get a list of the keys of this map
        /// </summary>
        std::vector<K> keys() const
        {
            std::vector<K> retVal;
            retVal.reserve(m_vec.size());
            for (size_t k = 0; k < m_vec.size(); ++k)
                retVal.push_back(m_vec[k].first);
            return retVal;
        }

        /// <summary>
        /// Get a list of the values of this map
        /// </summary>
        std::vector<V> values() const
        {
            std::vector<V> retVal;
            retVal.reserve(m_vec.size());
            for (size_t v = 0; v < m_vec.size(); ++v)
                retVal.push_back(m_vec[v].second);
            return retVal;
        }

    private:
        std::unordered_map<K, size_t> m_map;
        std::vector<std::pair<K, V>> m_vec;
    };
}

A pretty straightforward unordered_map + vector wrapper class. Just use the vec() function to walk the items in the order in which they were added, and use contains() and get/tryGet() for fast item lookups.

Update February 15, 2022: Per Paulo Zemek's feedback about set() making a poor bargain with the programmer, I took his advice and stashed the vector's indexes into the map's value entries.  Now when you update the map, you know which vector element to update.  The updated class passed good unit tests and the calling application's unit and smoke tests all pass, too, with no modificiation to application or tests. Good times.

Update February 18, 2020: Upon further reflection, having the map values in both the unordered_map and the vector was duplicating the memory usage.  Now the map values are just indexes into the vector which has the values.

Conclusion

If you ever need a data structure with fast searching and order-added iteration, look no further than vectormap. Enjoy!

History

• 15^th February, 2022: Initial version and first revision
• 18th February, 2022: Second revision