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 ...