C++ High Performance

Ordered sets and maps

The ordered associative containers guarantee that insert, delete, and search can be done in logarithmic time, O(log n). How that is achieved is up to the implementation of the Standard Library. However, the implementations we know about use some kind of self-balancing binary search tree. The fact that the tree stays approximately balanced is necessary for controlling the height of the tree, and hence also the worst case running time of accessing the elements. There is no need for the tree to pre-allocate memory, so typically a tree will allocate memory on the free store each time an element is inserted and also free up memory whenever elements are erased. Check out the following diagram, which shows that the height of ...