Skip to main content
caution

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class Key, /* ... */ >
class multiset;

The std::multiset is a sorted associative container that contains a sorted set of objects. Unlike set, multiple keys with equivalent values are allowed.

Technical details

Technical definition of a set

std::multiset is an associative container that contains a sorted set of objects of type Key. Unlike set, multiple keys with equivalent values are allowed. Sorting is done using the key comparison function Compare.

Search, insertion, and removal operations have logarithmic complexity (O(size())).

Everywhere the standard library uses the Compare requirements, equivalence is determined by using the equivalence relation as described on Compare. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

The order of the elements that compare equivalent is the order of insertion and does not change.

std::multiset meets the requirements of Container, AllocatorAwareContainer, AssociativeContainer and ReversibleContainer.

std::multiset

Defined inset

Template parameters

pubKeyThe type of stored keys.
pubCompareA comparator type satisfying Compare.
pubAllocatorAn allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubvalue_typeKey
pubsize_typeUnsigned integer type (usually
std::size_t
).
pubdifference_typeSigned integer type (usually
std::ptrdiff_t
).
pubkey_compareCompare
pubvalue_compareCompare
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer(until C++11)
std::allocator_traits<Allocator>::pointer(since C++11)
pubconst_pointerAllocator::const_pointer(until C++11)
std::allocator_traits<Allocator>::const_pointer(since C++11)
pubiterator

Constant LegacyBidirectionalIterator to value_type

pubconst_iterator

LegacyBidirectionalIterator to const value_type

pubreverse_iterator
std::reverse_iterator<iterator>
pubconst_reverse_iterator
std::reverse_iterator<const_iterator>
pubnode_type (since C++17) A specialization of node handle representing a container node.

Multiset's iterators

iterator is said to be constant because it is impossible to modify the values it's pointing to. This is because modyfing a value the iterator is pointing to could possibly invalidate the internal structure of the multiset, which could then lead to all kinds of incorrect and unexpected behaviours.

The member type aliases iterator and const_iterator may be the same. This is left entirely to the implementation. This means that any overloaded functions/specializations differing only in the iterator types may be incorrect and may lead to ODR violation.

Member functions

pub(constructor)

Constructs a new set.

pub(destructor)

Destructs a set.

puboperator=

Assigns one set to another.

pubget_allocator

Returns an associated allocator.

Iterators

pubbegin
cbegin (since C++11)

Returns an iterator to the beginning.

pubend
cend (since C++11)

Returns an iterator to the end.

pubrbegin
crbegin (since C++11)

Returns a reverse iterator to the beginning.

pubrend
crend (since C++11)

Returns a reverse iterator to the end.

Capacity

pubempty

Returns true if a set is empty, otherwise false.

pubsize

Returns the number of elements in a set.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of a set.

pubinsert

Inserts elements or nodes (extracted with .extract()) (since C++17).

pubemplace (since C++11)

Constructs a new element in place.

pubemplace_hint (since C++11)

Constructs elements in-place using a hint (iterator).

puberase

Erases elements.

pubswap

Swaps two sets.

pubextract (since C++17)

Extracts nodes from a set (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two sets together.

Lookup

pubcount

Returns the number of elements matching a specific key.

pubfind

Searches for an element and returns an iterator to it, or an end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside a set, otherwise false.

pubequal_range

Returns a range of elements matching a specific key.

publower_bound

Returns an iterator to the first element not less than the given key.

pubupper_bound

Returns an iterator to the first element greater than the given key.

Observers

pubkey_comp

Returns an internal function object that compares keys.

pubvalue_comp

Returns an internal function object that compares keys in objects of type value_type.

Non-member functions

puboperator==
operator!= (removed in C++20)
operator< (removed in C++20)
operator> (removed in C++20)
operator<= (removed in C++20)
operator>= (removed in C++20)
operator<=> (since C++20)
Lexicographically compares the values in a set.
pubstd::swap (std::multiset)An overload for a std::swap algorithm.
pubstd::erase_if (std::multiset) (since C++20)Overload for a std::erase_if algorithm.

Deduction guides (since C++17)

Click to expand

Deduction guides

// (1)
template<class InputIt,
class Comp = std::less<typename std::iterator_traits<InputIt>::value_type>,
class Alloc = std::allocator<typename std::iterator_traits<InputIt>::value_type>>
multiset(InputIt, InputIt, Comp = Comp(), Alloc = Alloc())
-> multiset<typename std::iterator_traits<InputIt>::value_type, Comp, Alloc>;
// (2)
template<class InputIt, class Alloc>
multiset(InputIt, InputIt, Alloc)
-> multiset<typename std::iterator_traits<InputIt>::value_type,
std::less<typename std::iterator_traits<InputIt>::value_type>, Alloc>;

(1) and (2) allow for deduction from an iterator range

// (3)
template<class Key, class Comp = std::less<Key>, class Alloc = std::allocator<Key>>
multiset(std::initializer_list<Key>, Comp = Comp(), Alloc = Alloc())
-> multiset<Key, Comp, Alloc>;
// (4)
template<class Key, class Alloc>
multiset(std::initializer_list<Key>, Alloc)
-> multiset<Key, std::less<Key>, Alloc>;

(3) and (4) allow for deduction from a std::initializer_list

Overload resolution

In order for any of the deduction guides to participate in overload resolution, the folllowing requirements must be met:

note

The extent to which the library determines that a type does not satisfy LegacyInputIterator is unspecified, except that as a minimum:

  • Integral types do not qualify as input iterators.

Likewise, the extent to which it determines that a type does not satisfy Allocator is unspecified, except that as a minimum:

More examples

Basic manipulation

#include <iostream>
#include <set>

int main() {
std::multiset<int> items = {3, 3, 1};

items.insert(12);
items.insert(12);

std::cout << "Items: \n";
for (const auto elem : items)
std::cout << elem << '\n';

return 0;
}
Result
Items: 1
3
3
12
12
#include <iostream>
#include <set>

int main() {
std::multiset<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};

for (auto i = numbers.begin(); i != numbers.end();) {
if (*i % 2 == 0)
i = numbers.erase(i);
else
++i;
}

for (const auto i : numbers)
std::cout << i << std::endl;

return 0;
}
Result
1
3
5
7
9
#include <iostream>
#include <set>

int main() {
std::multiset<char> letters = {'A', 'C', 'B'};
std::multiset<char> letters2 = {'E', 'D', 'C'};

letters.merge(letters2);

for (const auto i : letters)
std::cout << i << ' ';

std::cout << '\n';

for (const auto i : letters2)
std::cout << i << ' ';

return 0;
}
Result
A B C C D E 
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.
caution

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class Key, /* ... */ >
class multiset;

The std::multiset is a sorted associative container that contains a sorted set of objects. Unlike set, multiple keys with equivalent values are allowed.

Technical details

Technical definition of a set

std::multiset is an associative container that contains a sorted set of objects of type Key. Unlike set, multiple keys with equivalent values are allowed. Sorting is done using the key comparison function Compare.

Search, insertion, and removal operations have logarithmic complexity (O(size())).

Everywhere the standard library uses the Compare requirements, equivalence is determined by using the equivalence relation as described on Compare. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

The order of the elements that compare equivalent is the order of insertion and does not change.

std::multiset meets the requirements of Container, AllocatorAwareContainer, AssociativeContainer and ReversibleContainer.

std::multiset

Defined inset

Template parameters

pubKeyThe type of stored keys.
pubCompareA comparator type satisfying Compare.
pubAllocatorAn allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubvalue_typeKey
pubsize_typeUnsigned integer type (usually
std::size_t
).
pubdifference_typeSigned integer type (usually
std::ptrdiff_t
).
pubkey_compareCompare
pubvalue_compareCompare
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer(until C++11)
std::allocator_traits<Allocator>::pointer(since C++11)
pubconst_pointerAllocator::const_pointer(until C++11)
std::allocator_traits<Allocator>::const_pointer(since C++11)
pubiterator

Constant LegacyBidirectionalIterator to value_type

pubconst_iterator

LegacyBidirectionalIterator to const value_type

pubreverse_iterator
std::reverse_iterator<iterator>
pubconst_reverse_iterator
std::reverse_iterator<const_iterator>
pubnode_type (since C++17) A specialization of node handle representing a container node.

Multiset's iterators

iterator is said to be constant because it is impossible to modify the values it's pointing to. This is because modyfing a value the iterator is pointing to could possibly invalidate the internal structure of the multiset, which could then lead to all kinds of incorrect and unexpected behaviours.

The member type aliases iterator and const_iterator may be the same. This is left entirely to the implementation. This means that any overloaded functions/specializations differing only in the iterator types may be incorrect and may lead to ODR violation.

Member functions

pub(constructor)

Constructs a new set.

pub(destructor)

Destructs a set.

puboperator=

Assigns one set to another.

pubget_allocator

Returns an associated allocator.

Iterators

pubbegin
cbegin (since C++11)

Returns an iterator to the beginning.

pubend
cend (since C++11)

Returns an iterator to the end.

pubrbegin
crbegin (since C++11)

Returns a reverse iterator to the beginning.

pubrend
crend (since C++11)

Returns a reverse iterator to the end.

Capacity

pubempty

Returns true if a set is empty, otherwise false.

pubsize

Returns the number of elements in a set.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of a set.

pubinsert

Inserts elements or nodes (extracted with .extract()) (since C++17).

pubemplace (since C++11)

Constructs a new element in place.

pubemplace_hint (since C++11)

Constructs elements in-place using a hint (iterator).

puberase

Erases elements.

pubswap

Swaps two sets.

pubextract (since C++17)

Extracts nodes from a set (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two sets together.

Lookup

pubcount

Returns the number of elements matching a specific key.

pubfind

Searches for an element and returns an iterator to it, or an end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside a set, otherwise false.

pubequal_range

Returns a range of elements matching a specific key.

publower_bound

Returns an iterator to the first element not less than the given key.

pubupper_bound

Returns an iterator to the first element greater than the given key.

Observers

pubkey_comp

Returns an internal function object that compares keys.

pubvalue_comp

Returns an internal function object that compares keys in objects of type value_type.

Non-member functions

puboperator==
operator!= (removed in C++20)
operator< (removed in C++20)
operator> (removed in C++20)
operator<= (removed in C++20)
operator>= (removed in C++20)
operator<=> (since C++20)
Lexicographically compares the values in a set.
pubstd::swap (std::multiset)An overload for a std::swap algorithm.
pubstd::erase_if (std::multiset) (since C++20)Overload for a std::erase_if algorithm.

Deduction guides (since C++17)

Click to expand

Deduction guides

// (1)
template<class InputIt,
class Comp = std::less<typename std::iterator_traits<InputIt>::value_type>,
class Alloc = std::allocator<typename std::iterator_traits<InputIt>::value_type>>
multiset(InputIt, InputIt, Comp = Comp(), Alloc = Alloc())
-> multiset<typename std::iterator_traits<InputIt>::value_type, Comp, Alloc>;
// (2)
template<class InputIt, class Alloc>
multiset(InputIt, InputIt, Alloc)
-> multiset<typename std::iterator_traits<InputIt>::value_type,
std::less<typename std::iterator_traits<InputIt>::value_type>, Alloc>;

(1) and (2) allow for deduction from an iterator range

// (3)
template<class Key, class Comp = std::less<Key>, class Alloc = std::allocator<Key>>
multiset(std::initializer_list<Key>, Comp = Comp(), Alloc = Alloc())
-> multiset<Key, Comp, Alloc>;
// (4)
template<class Key, class Alloc>
multiset(std::initializer_list<Key>, Alloc)
-> multiset<Key, std::less<Key>, Alloc>;

(3) and (4) allow for deduction from a std::initializer_list

Overload resolution

In order for any of the deduction guides to participate in overload resolution, the folllowing requirements must be met:

note

The extent to which the library determines that a type does not satisfy LegacyInputIterator is unspecified, except that as a minimum:

  • Integral types do not qualify as input iterators.

Likewise, the extent to which it determines that a type does not satisfy Allocator is unspecified, except that as a minimum:

More examples

Basic manipulation

#include <iostream>
#include <set>

int main() {
std::multiset<int> items = {3, 3, 1};

items.insert(12);
items.insert(12);

std::cout << "Items: \n";
for (const auto elem : items)
std::cout << elem << '\n';

return 0;
}
Result
Items: 1
3
3
12
12
#include <iostream>
#include <set>

int main() {
std::multiset<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};

for (auto i = numbers.begin(); i != numbers.end();) {
if (*i % 2 == 0)
i = numbers.erase(i);
else
++i;
}

for (const auto i : numbers)
std::cout << i << std::endl;

return 0;
}
Result
1
3
5
7
9
#include <iostream>
#include <set>

int main() {
std::multiset<char> letters = {'A', 'C', 'B'};
std::multiset<char> letters2 = {'E', 'D', 'C'};

letters.merge(letters2);

for (const auto i : letters)
std::cout << i << ' ';

std::cout << '\n';

for (const auto i : letters2)
std::cout << i << ' ';

return 0;
}
Result
A B C C D E 
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.