Associative Containers
In this lesson, we will learn about ordered and unordered associative containers.
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
.
Get hands-on with 1400+ tech skills courses.