A Simple Performance Comparison

Before we take a deeper look into associative containers, let’s examine the interface of the hash tables, which are called unordered associative containers. We will first compare the performance of the associative containers.

Admittedly, the eight variations of associative containers can be confusing. In addition, the unordered name component of the new variations is not easy to read or write. On the one hand, the unordered associative containers were too late for the C++98 standard. On the other hand, they were missed so badly that most of the architectures implemented them by themselves. Therefore, the simple names have already been used, and the C++ standardization committee must use more elaborate names, that follow a simple pattern.

The table below shows the entire system. It includes the access time for the ordered containers (logarithmic) and the unordered container (amortized constant).

We can also look at the table from a different perspective. A std::unordered_set supports the interface of a std::set. The same holds for the pairs std::unordered_map and std::map, std::unordered_multiset as wel as std::multiset, std::unordered_multimap and std::multimap as well. This means, if an std::map is too slow, we can quite easily use an std::unordered_map.