Iterating through an unordered multimap

Question

I have inserted some elements in my unordered_multimap and I am finding all the values mapped to a key k using equal range. Now I want to traverse these mapped values by their order of insertion. Look at the code for better understanding.

#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
    unordered_multimap<int,int> m;
    m.insert(make_pair(1,2));
    m.insert(make_pair(1,3));
    m.insert(make_pair(1,4));
    auto it = m.equal_range(1);
    for(auto it1 = it.first; it1 != it.second; it1++) {
        cout<<it1->second<<endl;
    }
}

output:

4
3
2

But I want to traverse in the order in which keys and mapped values were inserted. So, I want to traverse in order 2,3,4. Is it possible?

Answer 1

There is not a straghtforward way to do what you are asking for. When elements are inserted in an ordered or an unordered multimap they are actually placed in the internal structure and it is not known in which order they have been placed.

You should have an auxiliary e.g. an std::queue container for this where you append the iterator to the inserted element. The iterator can be obtained from the insertion as:

auto inserted_pos = m.insert(make_pair(1,4));

Keep in mind that iterators are not invalidated during insertion. They are invalidated if the element is removed, and only for the concerned element.