The trees: std::set<T> and std::map<K, V>

The class template std::set<T> provides the interface of a "unique set" for any T that implements operator<. As always with STL operations that involve comparison, there is a version taking a comparator: std::set<T, Cmp> provides "unique set" functionality using Cmp(a,b) instead of (a < b) to sort the data elements.

A std::set is conceptually a binary search tree, analogous to Java's TreeSet. In all popular implementations it's specifically a red-black tree, which is a particular kind of self-balancing binary search tree: even if you are constantly inserting and removing items from the tree, it will never get too unbalanced, which means that insert and find will always run in O(log n) time on average. ...

Get Mastering the C++17 STL now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.