stdmultiset

stdmultiset, in the C++ standard library, is an associative container that stores multiple elements with equivalent keys in sorted order. It is defined as a template with parameters Key, Compare, and Allocator, defaulting to std::less<Key> for ordering and std::allocator<Key> for memory management. The type stored is Key, and the key type is the same as the value type.

Elements in a multiset are ordered according to the comparator and are kept in a balanced binary search tree (commonly a red–black tree) to support efficient operations. Unlike std::set, a multiset allows multiple elements to have identical keys, which appear consecutively in the container. Because the ordering is defined by the value itself, you should not modify an element in place in a way that could affect its ordering; instead, erase and insert as needed.

Key operations include insert, find, erase, and count. Insertion may insert duplicates and returns an iterator to the inserted element in multiset, with an optional hint version to potentially improve performance. Erase supports removing a single element by iterator, removing all elements with a given key, or erasing a range of elements. Lookup facilities include find, count, lower_bound, upper_bound, and equal_range, which enable accessing the range of elements with a given key.

Iterators are bidirectional and traverse elements in sorted order. Complexity for insertion, erasure, and search is logarithmic in size (O(log n)) on average, while erasing a range is proportional to the number of elements removed plus log factors for traversals. Multisets are useful for storing sorted collections with duplicates, such as frequency counts, while benefiting from automatic ordering without manual sorting. They differ from std::set primarily in supporting duplicates.