The order of elements in std :: unordered_multimap

Question

If I have the following code snippet

std::unordered_multimap<std::string, std::vector<double>> myMap; std::vector<double> v1, v2, v3; // init v1, v2, v3.... myMap.insert(std::make_pair<std::string, std::vector<double>("vec", v1)); myMap.insert(std::make_pair<std::string, std::vector<double>("vec", v2)); myMap.insert(std::make_pair<std::string, std::vector<double>("vec", v3)); 

If I access the values ​​using an iterator, they will always be in the following order: v1, v2, v3

So basically, if I insert elements of the same key, but with different values, do they always keep the insertion order?

Answer 1

I assume this is a specific implementation. In unordered_multimap elements with the same key are stored in the same bucket if the implementation is a bucket hash map, in which case they can be in the same insertion order (this is probably your situation).

But in unordered_map , implemented, for example, using the open addressing method, the order may change. I don’t know if there are STL implementations that use different ones when implementing the hood, but the class contract does not make any assumptions about the order of values ​​for the same key, so I don’t think you can take it for granted.

Taken from here :

Internally, elements in unordered_map are not sorted in any particular order with respect to their key or display values

Answer 2

The whole point of “disordered” in the name is that you cannot rely on an order. Someday.

If you find any order emanating from an iteration of the container, this is a match or implementation artifact. You should never count on it.

Answer 3

If the documentation does not indicate that they will always be returned in the input order, you will not do what you rely on it. The STL implementation that you use today may change. It may also be that the implementation you are using will work differently if there were many entries on the map.