map

Reference:

1. Name5566: 理解 STL MAP
2. WIKI:Red–black tree
3. stl map删除的时候效率？
4. Stack Overflow: Why is std::map implemented as a red-black tree?

std::map uses Red-Black tree as it gets a reasonable trade-off between the complexity of node insertion/deletion and searching.

A red–black tree is a kind of self-balancing binary search tree.

The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.