best way to define a unordered_map of vectors

Question

Is it the same in term of performance to define a std::unordered_map like this

unordered_map<int, std::vector<ClassA>>

and like this?

unordered_map<int, std::unique_ptr<std::vector<ClassA>>>

for the std::vector<ClassA> part, I am using std::move anyway.

Answer 1

Given that the unordered_map never moves/copies its nodes, they should be equally fast in terms of complexity. But keep in mind that

std::unordered_map<int, std::vector<ClassA>>

has one less indirection when you want to access the vector's data:

std::unordered_map -> [node -> std::vector] -> data

where the internal node probably contains the vector. OTOH:

std::unordered_map<int, std::unique_ptr<std::vector<ClassA>>>

results in

std::unordered_map -> [node -> std::unique_ptr] -> std::vector -> data

where now the node contains only the std::unique_ptr which needs to be actually dereferenced to reach the std::vector.

Answer 2

I think your question can be stated differently and splitted in two part:

• Internaly, when the std::unordered_map<> will copy and not move ?
• Whan inserting/retrieving an element from a std::unordered_map<> is there always a way to avoid copy ?

For the first part of the question, the answer is no. There is not even a move invoked during rehash (see this question). You can be sure that if you inserted/retrieved your elements without copying, there will be no copy.

Now, for the second part of the question.

Every time you insert, emplace, or use operator[] for assignment there is an overload with the rvalue reference, but you have to ensure that your code will allow the use of such a thing. Avoid: my_map[index] = my_vector; or even my_map.insert(std::make_pair(index, my_vector)); because that will not call the rvalue ref oveload. Either use std::moveor pass directly a rvalue, or use initializer lists.

Now, when retrieving the data, with iterators or using for loop, there should be no problem as long as you use references on your element, e.g.:

for (auto& my_element: my_map) { ... }

and not:

for (auto my_element: my_map) { ... }