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 all_yours
{
    /// <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 directly
        /// </summary>
        const std::vector<std::pair<K, V>>& vec() const
        {
            return m_vec;
        }

        /// <summary>
        /// Access the map directly
        /// </summary>
        const std::unordered_map<K, V>& map() const
        {
            return m_map;
        }

        /// <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
        {
            if (!contains(key))
                throw std::runtime_error("key not found");
            return m_map.find(key)->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)
        {
            if (!contains(key))
            {
                m_map.insert({ key, val });
                m_vec.push_back({ key, val });
                return;
            }

            m_map[key] = val;

            for (auto& kvp : m_vec)
            {
                if (kvp.first == key)
                {
                    kvp.second = val;
                    break;
                }
            }
        }

        /// <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
        {
            auto it = m_map.find(key);
            if (it == m_map.end())
                return false;

            val = it->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, V> 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.

The only gotcha is the set() function used for adding and updating, which costs a lookup before adding an item, then a loop over the vector for updating an item. In the past, I've had this data structure not have a set() function and only have an insert() function, but that was too inflexible for the project I was working on. So you get set(). It's trivial to add an insert() function separate from or instead of set().

Conclusion

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

History

• 15th February, 2022: Initial version