multiset Class

The Standard Template Library multiset class is used for the storage and retrieval of data from a collection in which the values of the elements contained need not be unique and in which they serve as the key values according to which the data is automatically ordered. The key value of an element in a multiset may not be changed directly. Instead, old values must be deleted and elements with new values inserted.

template < 
   class Key,  
   class Compare=less<Key>,  
   class Allocator=allocator<Key>  
> 
class multiset

Parameters

• Key
  The element data type to be stored in the multiset.

• Compare
  The type that provides a function object that can compare two element values as sort keys to determine their relative order in the multiset. The binary predicate less<Key> is the default value.

• Allocator
  The type that represents the stored allocator object that encapsulates details about the multiset's allocation and deallocation of memory. The default value is allocator*<Key>.*

Remarks

The STL multiset class is:

• An associative container, which is a variable size container that supports the efficient retrieval of element values based on an associated key value.

• Reversible, because it provides bidirectional iterators to access its elements.

• Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.

• Multiple in the sense that its elements do not need to have unique keys, so that one key value can have many element values associated with it.

• A simple associative container because its element values are its key values.

• A template class, because the functionality it provides is generic and so independent of the specific type of data contained as elements. The data type to be used is, instead, specified as a parameter in the class template along with the comparison function and allocator.

The iterator provided by the multiset class is a bidirectional iterator, but the class member functions insert and multiset have versions that take as template parameters a weaker input iterator, whose functionality requirements are more minimal than those guaranteed by the class of bidirectional iterators. The different iterator concepts form a family related by refinements in their functionality. Each iterator concept has its own set of requirements and the algorithms that work with them must limit their assumptions to the requirements provided by that type of iterator. It may be assumed that an input iterator may be dereferenced to refer to some object and that it may be incremented to the next iterator in the sequence. This is a minimal set of functionality, but it is enough to be able to talk meaningfully about a range of iterators [First, Last) in the context of the class's member functions.

The choice of container type should be based in general on the type of searching and inserting required by the application. Associative containers are optimized for the operations of lookup, insertion and removal. The member functions that explicitly support these operations are efficient, performing them in a time that is on average proportional to the logarithm of the number of elements in the container. Inserting elements invalidates no iterators, and removing elements invalidates only those iterators that had specifically pointed at the removed elements.

The multiset should be the associative container of choice when the conditions associating the values with their keys are satisfies by the application. The elements of a multiset may be multiple and serve as their own sort keys, so keys are not unique. A model for this type of structure is an ordered list of, say, words in which the words may occur more than once. Had multiple occurrences of the words not been allowed, then a set would have been the appropriate container structure. If unique definitions were attached as values to the list of unique key words, then a map would be an appropriate structure to contain this data. If instead the definitions were not unique, then a multimap would be the container of choice.

The multiset orders the sequence it controls by calling a stored function object of type Compare. This stored object is a comparison function that may be accessed by calling the member function key_comp. In general, the elements need be merely less than comparable to establish this order: so that, given any two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements. On a more technical note, the comparison function is a binary predicate that induces a strict weak ordering in the standard mathematical sense. A binary predicate f(x,y) is a function object that has two argument objects x and y and a return value of true or false. An ordering imposed on a set is a strict weak ordering if the binary predicate is irreflexive, antisymmetric, and transitive and if equivalence is transitive, where two objects x and y are defined to be equivalent when both f(x,y) and f(y,x) are false. If the stronger condition of equality between keys replaces that of equivalence, then the ordering becomes total (in the sense that all the elements are ordered with respect to each other) and the keys matched will be indiscernible from each other.

Constructors

multiset

Constructs a multiset that is empty or that is a copy of all or part of a specified multiset.

Typedefs

allocator_type	A typedef for the allocator class for the multiset object.
const_iterator	A typedef for a bidirectional iterator that can read a const element in the multiset.
const_pointer	A typedef for a pointer to a const element in a multiset.
const_reference	A typedef for a reference to a const element stored in a multiset for reading and performing const operations.
const_reverse_iterator	A typedef for a bidirectional iterator that can read any const element in the multiset.
difference_type	A signed integer typedef for the number of elements of a multiset in a range between elements pointed to by iterators.
iterator	A typedef for a bidirectional iterator that can read or modify any element in a multiset.
key_compare	A typedef for a function object that can compare two keys to determine the relative order of two elements in the multiset.
key_type	A typedef for a function object that can compare two sort keys to determine the relative order of two elements in the multiset.
pointer	A typedef for a pointer to an element in a multiset.
reference	A typedef for a reference to an element stored in a multiset.
reverse_iterator	A typedef for a bidirectional iterator that can read or modify an element in a reversed multiset.
size_type	An unsigned integer type that can represent the number of elements in a multiset.
value_compare	The typedef for a function object that can compare two elements as sort keys to determine their relative order in the multiset.
value_type	A typedef that describes an object stored as an element as a multiset in its capacity as a value.

Member Functions

begin	Returns an iterator that points to the first element in the multiset.
cbegin	Returns a const iterator that addresses the first element in the multiset.
cend	Returns a const iterator that addresses the location succeeding the last element in a multiset.
clear	Erases all the elements of a multiset.
count	Returns the number of elements in a multiset whose key matches the key specified as a parameter.
crbegin	Returns a const iterator addressing the first element in a reversed set.
crend	Returns a const iterator that addresses the location succeeding the last element in a reversed set.
emplace	Inserts an element constructed in place into a multiset.
emplace_hint	Inserts an element constructed in place into a multiset, with a placement hint.
empty	Tests if a multiset is empty.
end	Returns an iterator that points to the location after the last element in a multiset.
equal_range	Returns a pair of iterators. The first iterator in the pair points to the first element in a multiset with a key that is greater than a specified key. The second iterator in the pair points to first element in the multiset with a key that is equal to or greater than the key.
erase	Removes an element or a range of elements in a multiset from specified positions or removes elements that match a specified key.
find	Returns an iterator that points to the first location of an element in a multiset that has a key equal to a specified key.
get_allocator	Returns a copy of the allocator object that is used to construct the multiset.
insert	Inserts an element or a range of elements into a multiset.
key_comp	Provides a function object that can compare two sort keys to determine the relative order of two elements in the multiset.
lower_bound	Returns an iterator to the first element in a multiset with a key that is equal to or greater than a specified key.
max_size	Returns the maximum length of the multiset.
rbegin	Returns an iterator that points to the first element in a reversed multiset.
rend	Returns an iterator that points to the location succeeding the last element in a reversed multiset.
size	Returns the number of elements in a multiset.
swap	Exchanges the elements of two multisets.
upper_bound	Returns an iterator to the first element in a multiset with a key that is greater than a specified key.
value_comp	Retrieves a copy of the comparison object that is used to order element values in a multiset.

Operators

operator=

Replaces the elements of a multiset with a copy of another multiset.

Requirements

Header: <set>

Namespace: std

See Also

Reference

Thread Safety in the C++ Standard Library

Standard Template Library

Concepts

Containers

Other Resources

<set> Members