Associative Containers

Associative containers in C++: ordered and unordered

The associative containers place their elements based on the element itself. For example, it's not possible to add an element at the back or front in an associative container as we do with std::vector::push_back() or std::list::push_front(). Instead, the elements are added in a way that makes it possible to find the element without the need to scan the entire container. Therefore, the associative containers have some requirements for the objects we want to store in a container. We will look at these requirements later.

There are two main categories of associative containers:

• Ordered associative containers: These containers are based on trees; the containers use a tree for storing their elements. They require that the elements are ordered by the less than operator (<). The functions for adding, deleting, and finding elements are all $O(log n)$ in the tree-based containers. The containers are named std::set, std::map, std::multiset, and std::multimap.

• Unordered associative containers: These containers are based on hash tables; the containers use a hash table for storing their elements. They require that the elements are compared with the equality operator (==) and that there is a way to compute a hash value based on an element. More on that later. The functions for adding, deleting, and finding elements are all $O(1)$ in the hash table-based containers. The containers are named std::unordered_set, std::unordered_map, std::unordered_multiset, and std::unordered_ multimap.

Since C++20, all associative containers are equipped with a function named contains(), which should be used when we want to know whether a container contains some specific elements. In earlier versions of C++, it was necessary to use count() or find() to find out whether a container contained an element.