Coding gotchas: C++ maps

Hey guys! Today I am going to talk about something that infuriates me every time I see it: People using ordered maps in C++. Please. Just. Don't. I have created a very basic test code and run it with both ordered and unordered maps:

template <class mapType>
void map_it(int num_keys, mapType& mymap) {
    for (int i = 0; i < num_keys; i++) {
        mymap[i] = std::string("Number: ") + std::to_string(i);
    }
}

template <class mapType>
bool query_it(int num_keys, mapType& mymap) {
    bool all_found = true;
    typename mapType::iterator search = mymap.end();
    for (int i = 0; i < num_keys; i++) {
        search = mymap.find(i);
        if (search == mymap.end()) {
            all_found = false;
            break;
        }
    }
    return all_found; //To make sure the compiler doesn't optimize away
}

I tested the code with num_elements being 10000, 100000, 1000000, 10000000 and 100000000:

std::map<int, std::string> mymap;
std::unordered_map<int, std::string> myunorderedmap;

map_it(num_elements, mymap);
bool ordered_goodness = query_it(num_elements, mymap);

And here are the timing results.

% g++ -O3 maps.cpp -o maps.out
% ./maps.out 
Ordered took: 0.0024. Unordered took: 0.0016. Number of elements: 10000.
Ordered took: 0.0331. Unordered took: 0.0152. Number of elements: 100000.
Ordered took: 0.3880. Unordered took: 0.1629. Number of elements: 1000000.
Ordered took: 5.5381. Unordered took: 1.7777. Number of elements: 10000000.
Ordered took: 82.1141. Unordered took: 19.0146. Number of elements: 100000000.
./maps.out  110.75s user 5.88s system 99% cpu 1:56.79 total

Unordered map is faster in every case and with the increase of number of elements, the discrepancy gets larger. The reason is that the std::map uses a tree like structure and has logarithmic time complexity O(log(n)) for its operations, whereas std::unordered_map uses bucketing to store and access elements based on their hashes and therefore has constant time complexity O(1).

Unfortunately std::unordered_map appeared in C++11 and as it doesn't offer the exact functionality of std::map it couldn't supersede it and had to use a different name. As a result people new to C++ frequently end up using std::map in their code because the search engine result to "C++ map" would point to it. While there are genuine cases where one would want to use std::map over std::unordered_map, such as actually using the ordering or frequent full traversal of the map, in the majority of time std::unordered_map is vastly superior.

So don't be one those people, get on the fast train!

Nick