CODEWITHSUNDEEP
c++
Hemant Bhargava
Hemant Bhargava

Reputation: 3585

Faster way to insert into an unordered map

I have an unordered map, exactly like:

std::unordered_map < std::string, std::vector<std::string> > m_unordered_map;

While inserting values into it, which of the following would be faster and why?

Approach 1 (Skeleton):

std:string key = "key";
for (int i = 0; i < n; ++i) {
  std::string value = std::to_string(i); // Value would be acually an big string.
  m_unordered_map[key].push_back(value1);
}

Approach 2 (Skeleton)

std:string key = "key";
std::vector<std::string> vec;
for (int i = 0; i < n; ++i) {
  std::string value = std::to_string(i); // Value would be acually an big string.
  vec.insert(value);
}
m_unordered_map.insert({key, vec});

Or is there a better approach to do this?

Upvotes: 0

Views: 1450

Answers (2)

Jarod42
Jarod42

Reputation: 218323

Amelioration of your 2 approaches:

Approach 1(Skeleton):

std:string key = "key";
auto& vec = m_unordered_map[key];
vec.reserve(n);
for (int i = 0; i != n; ++i) {
    vec.push_back(std::to_string(i));
}

Approach 2(Skeleton)

std:string key = "key";
std::vector<std::string> vec;
vec.reserve(n);
for (int i = 0; i != n; ++i) {
    vec.push_back(std::to_string(i));
}
m_unordered_map[key] = std::move(vec));

So

  • do only one lookup
  • Use move instead of copy.

On my side, I would create a method to build the vector, something like:

std::vector<std::string> create_iota_strings(std::size_t n)
{
    std::vector<std::string> vec;
    vec.reserve(n);
    for (std::size_t i = 0; i != n; ++i) {
        vec.push_back(std::to_string(i));
    }
    return vec;
}

and then simply

m_unordered_map[key] = create_iota_strings(n);

insert/emplace might be more appropriate than operator[] if you know key doesn't already exist. If key might exist try_emplace would be the solution to avoid to construct the empty vector (when key doesn't exist).

Upvotes: 1

Fire Lancer
Fire Lancer

Reputation: 30165

Assuming you know the key in advance for a batch of things, then the second of the versions you have is significantly better, as it avoids doing a map lookup on every iteration.

You may further improve it by moving instead of copying the string and vectors. e.g.

std::string key = "key";
std::vector<std::string> vec;
for (int i = 0; i < 10; ++i) {
    vec.emplace_back(std::to_string(i));
}
m_unordered_map.emplace(key, std::move(vec));

In general:

  • Accessing an unordered_map is still fairly slow, especially with keys like std::string. For a "hit" it costs you a O(n) hash on the keys length, and a O(n) string comparison. Not just O(1) for the hash table itself. If you can access it just once, maybe keep an iterator/reference that will be faster (check the iterator invalidation rules. insert may invalidate other iterators in an unordered_map, so be careful, but it won't invalidate references to values). If you can replace the string entirely with say an integer ID that will also normally be faster.
  • Avoid copying objects like maps, strings, and vectors. When possible move them. As well as the cost of copying the data, copying containers can cause a lot of comparatively expensive memory allocations.

Upvotes: 4

Related Questions