std::multiset

std::multiset<T> is a sorted associative container that stores keys in order and allows the same key to appear more than once. It uses the same balanced binary search tree as std::set (red-black in every mainstream implementation), so every key-touching operation is O(log n), and iteration walks the keys in sorted order. The defining property is the dropped uniqueness rule: insert 5 three times and the container stores it three times. This chapter covers what changes once duplicates are allowed, the API differences from std::set, the role of equal_range and count, and the workloads where multiset fits well.