Multiset

Definition

The multiset template is defined in the standard header <set>, and in the nonstandard backward-compatibility header <multiset.h>.

#include <set>
namespace std{
       template < class T,
                 class Compare = less<T>,
                 class Allocator = allocator<T> >
       class multiset;
}

Description

Multiset is a Sorted Associative Container with the same properties as a set container with the difference that if an item is already present is inserted into the set, nothing happens. (That's why multiset is also a Multiple Associative Container.)

The default operation for key comparison is the < operator.

A short example declaring a multiset is:

multiset<double> msetDb; // declar a double multiset

The sequence is represented in a way that permits lookup, insertion, and removal of an element with a number of operations proportional to the logarithm of the number of elements in the sequence. Even more, erasing an element from a multiset does not invalidate any iterators, only those iterators which point at the removed element.

Performance

A multiset is very useful when you must rapidly look up if an element is contained or not into a collection of elements.

Multisets are typically implemented using self-balancing binary search trees and support bidirectional iterator. The major advantage of automatic sorting is that a binary tree performs well when elements with a certain value are searched. The standard does not specify this, but it follows from the complexity of multiset operations.

Note! You cannot refer to a multiset element directly given its numerical position -- that requires a random-access iterator.

Multiset Operations

Create, Copy, and Destroy Operations

Operation	Effect
set ms	Creates an empty multiset without any elements
set ms(op)	Creates an empty multiset that uses op as the sorting criterion
set ms1(ms2)	Creates a copy of another multiset of the same type (all elements are copied)
set ms(beg,end)	Creates a multiset initialized by the elements of the range [beg,end)
set ms(beg,end,op)	Creates a multiset with the sorting criterion op initialized by the elements of the range [beg,end)
ms.~set()	Destroys all elements and frees the memory

Multiset	Effect
multiset<el>	A multiset that sorts with less<> (operator <)
multiset<el,op>	A multiset that sorts with op

Nonmodifying Operations of Multisets

Operation	Effect
ms.size()	Returns the actual number of elements
ms.empty()	Returns if the container is empty (equivalent to size()==0)
ms.max_size()	Returns the maximum number of elements possible
ms1==ms2	Returns if ms1 is equal to ms2
ms1!=ms2	Returns if ms1 is not equal to ms2 (equivalent to !(ms1==ms2))
ms1<ms2	Returns if ms1 is less than ms2
ms1>ms2	Returns if ms1 is greater than ms2 (equivalent to ms2<ms1)
ms1<=ms2	Returns if ms1 is less than or equal to ms2 (equivalent to !(ms2<ms1))
ms1>=ms2	Returns if ms1 is greater than or equal to ms2 (equivalent to !(ms1<ms2))

Special Search Operations of Multisets

Operation	Effect
count(el)	Returns the number of elements with value el
find(el)	Returns the position of the first element with value el or end()
lower_bound(el)	Returns the first position, where el would get inserted (the first element >= el)
upper_bound(el)	Returns the last position, where el would get inserted (the first element > el)
equal_range(el)	Returns the first and last position, where el would get inserted (the range of elements == el)

Assignment Operations of Multisets

Operation	Effect
ms1=ms2	Assigns all elements of ms2 to ms1
ms1.swap(ms2)	Swaps the data of ms1 and ms2
swap(ms1,ms2)	Same (as global function)

Iterator Operations of Multisets

Operation	Effect
ms.begin()	Returns a bidirectional iterator for the first element (elements are considered const)
ms.end()	Returns a bidirectional iterator for the position after the last element (elements are considered const)
ms.rbegin()	Returns a reverse iterator for the first element of a reverse iteration
ms.rend()	Returns a reverse iterator for the position after the last element of a reverse iteration

Inserting and Removing Elements of Multisets

Operation	Effect
ms.insert(el)	Inserts a copy of el and returns the position of the new element
ms.insert(pos, el)	Inserts a copy of el and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
ms.insert(beg,end)	Inserts a copy of all elements of the range [beg,end) (returns nothing)
ms.erase(el)	Removes all elements with value el and returns the number of removed elements
ms.erase(pos)	Removes the element at iterator position pos (returns nothing)
ms.erase(beg,end)	Removes all elements of the range [beg,end) (returns nothing)
ms.clear()	Removes all elements