Search trees

Whenever objects have a natural order so that they can be sorted using some notion of the mathematical smaller < relation, they can be maintained in that order using search trees. As the name suggests, search trees can easily be searched for specific items using a search key, which allows O(log(n)) search times.

The STL provides such trees in different flavors, where std::set is the simplest one of them, storing just unique, sortable objects in a tree structure.

std::map is different in that regard, that it stores data in pairs. A pair consists of a key, and a value. The search tree uses the key part for sorting the items, which enables for using std::map as an associative container. As in std::set, all key items must only exist once in the whole tree.

std::multiset and std::multimap are specializations, which drop the requirement for uniqueness of the key objects.