slow std::map for large entries

Question

We have 48,16,703 entries in this format.

1 abc
2 def
...
...
4816702 blah
4816703 blah_blah

Since the number of entries are quite big, I am worried that std::map would take much time during insertion since it need to do the balancing as well for each insertion.

Only inserting these entries into the map takes a lot of time. I am doing

map[first] = second;

Two questions: 1. Am I correct in using std::map for these kind of cases? 2. Am I correct in inserting like the above way. OR Should I use map.insert()

I am sorry for not doing the experiments and writing the absolute numbers but we want an general consensus if we are doing the right thing or not.

Also, they keys are not consecutive always..

P.S. Of-course, later we will need to access that map as well to get the values corresponding to the keys.

Answer 1

If you don’t need to insert into the map afterwards, you can construct an unsorted vector of your data, sort it according to the key, and then search using functions like std::equal_range.
It’s the same complexity as std::map, but far less allocations.