The problem with automatic sorting (std::map)

The problem with automatic sorting (std::map)

Do you want to store data in C++ that requires mapping that data to a string or other type of key? Is the order of that data important? Well then, don’t use std::map.

“wha?” I hear you ask, well:

std::map is an ordered data type

What is meant by “ordered data type”? It means that std::map tries to sort the data it contains, most crucially it means that whatever you store in it will most likely not be in the same insertion order, for example here’s some numbers in insertion order and how std::map actually stores it:

9 0
8 1
5 2
7 3
6 4
3 5
1 6
4 7
2 8
0 9

“well ok then, I’ll just use std::unordered_map instead. surely the “unordered” part of that is self-explanatory?”

Despite its name, std::unordered_map is still an ordered data type for some reason (hey, I didn’t design the STL!).

What can I do?

You have a few options:

  1. Use a library that offers an unordered std::map (such as Boost or nlohmann’s fifo map header-only library– the latter I’ve used while the former I haven’t [the fifo map library can be used as a drop-in replacement for std::map])
  2. Use an std::vector to store the actual data and then use the std::map to map the location of said data in the std::vector to its key:

std::vector<somedata_type> data_storage;
std::map<std::string, int> data_map;

data_map.insert(std::make_pair("some data", data_storage.size() - 1));

Note that for the above code depending on your implementation you may need to static_cast<unsigned int>(data_storage.size()) .


No Comments

Add your comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.