CODEWITHSUNDEEP
c++optimizationmemory
Raym
Raym

Reputation: 61

what is the most efficient way to preallocate unordered_map<string, vector<uint8_t>>?

I work with an unordered_map<string, vector<uint8_t>>. I can know the number of pairs, and the size of all the vectors<uint8_t> are all the same and are known at all times. I was wondering if I could enhance the performance by allocating all the needed memory, before inserting elements. From what I understand I can preallocate the number of string "key/slots" with .reserve(). But is there a way to allocate all the memory that the unordered_map will need from the beginning?

Upvotes: 0

Views: 188

Answers (1)

Pepijn Kramer
Pepijn Kramer

Reputation: 12891

Here is a sketch of such a datastructure. Instead of storing key,value pairs directly, this datastructure first stores data in an array (preallocated), then stores the key + index into the array into the map.

When retrieving data, the map is used to lookup the index in the array for the given key and returns that.

Live demo here : https://onlinegdb.com/zulZwWh3j

#include <array>
#include <cstdint>
#include <unordered_map>
#include <string>
#include <iostream>

// a preallocated map

template<typename key_t, std::size_t number_of_keys_v, typename value_t>
class preallocated_map final
{
public:
    // key value pairs to put into the map
    struct kv_t
    {
        key_t key;
        value_t value;
    };

    template<std::size_t N>
    preallocated_map(const kv_t(&entries)[N]) :
        m_size{ 0ul }
    {
        for (const auto& entry : entries)
        {
            // store a value in the next unused free slot
            m_values[m_size] = entry.value;

            // they map will now hold an index into the m_values array for the key
            m_index_map.insert({ entry.key,m_size });

            // increase stored size
            m_size++;
        }
    }

    const auto& at(const key_t& key)
    {
        return m_values[m_index_map.at(key)];
    }
        
    ~preallocated_map() = default;


private:
    // memory to store values in 
    std::array <value_t, number_of_keys_v> m_values;

    // mapping of key to an index into the array of values.
    std::unordered_map<key_t, std::size_t> m_index_map;

    // number of values in the map
    std::size_t m_size;
};



int main()
{
    preallocated_map<std::string, 4, std::array<std::uint8_t, 4>> map
    { {
        {"one",{'1','2','3','4'}},
        {"two",{'2','4','6','8'}}
    } };

    auto values = map.at("two");
    for (const auto& value : values)
    {
        std::cout << value << " ";
    }

    return 0;
}

Upvotes: 1

Related Questions