15.6.1. multiset Associative Container

The multiset ordered associative container (from header <set>) provides fast storage and retrieval of keys and allows duplicate keys. The elements’ ordering is determined by a so-called comparator function object. For example, in an integer multiset, elements can be sorted in ascending order by ordering the keys with comparator function object less<int>. We discuss function objects in detail in Section 16.4. For this chapter, we’ll simply show how to use less<int> when declaring ordered associative containers. The data type of the keys in all ordered associative containers must support comparison based on the comparator function object—keys sorted with less<T> must support comparison with operator<. If the keys used in the ordered associative containers are of user-defined data types, those types must supply the appropriate comparison operators. A multiset supports bidirectional iterators (but not random-access iterators). In if the order of the keys is not important, you can use unordered_multiset (header <unordered_set>) instead.

Figure 15.15 demonstrates the multiset ordered associative container for a multiset of ints with keys that are sorted in ascending order. Containers multiset and set (Section 15.6.2) provide the same basic functionality.

Click here to view code image

Fig. 15.15. Standard Library multiset class template.

Creating a multiset

Line 14 creates a multiset of ints ordered in ascending order, using the function object less<int>. Ascending order is the default for a multiset, so less<int> can be omitted. C++11 fixes a compiler issue with spacing between the closing > of less<int> and the closing > of the multiset type. Before C++11, if you specified this multiset’s type as

the compiler would treat >> at the end of the type as the >> operator and generate a compilation error. For this reason, you were required to put a space between the closing > of less<int> and the closing > of the multiset type (or any other similar template type, such as vector<vector<int>>). As of C++11, the preceding declaration compiles correctly.

multiset Member Function count

Line 17 uses function count (available to all associative containers) to count the number of occurrences of the value 15 currently in the multiset.

multiset Member Function insert

Lines 20–21 use one of the several overloaded versions of function insert to add the value 15 to the multiset twice. A second version of insert takes an iterator and a value as arguments and begins the search for the insertion point from the iterator position specified. A third version of insert takes two iterators as arguments that specify a range of values to add to the multiset from another container.

multiset Member Function find

Line 26 uses function find (available to all associative containers) to locate the value 15 in the multiset. Function find returns an iterator or a const_iterator pointing to the location at which the value is found. If the value is not found, find returns an iterator or a const_iterator equal to the value returned by calling end on the container. Line 32 demonstrates this case.

Inserting Elements of Another Container into a multiset

Line 38 uses function insert to insert the elements of array a into the multiset. In line 40, the copy algorithm copies the elements of the multiset to the standard output in ascending order.

multiset Member Functions lower_bound and upper_bound

Lines 44 and 45 use functions lower_bound and upper_bound (available in all associative containers) to locate the earliest occurrence of the value 22 in the multiset and the element after the last occurrence of the value 22 in the multiset. Both functions return iterators or const_iterators pointing to the appropriate location or the iterator returned by end if the value is not in the multiset.

pair Objects and multiset Member Function equal_range

Line 49 creates and intializes a pair object called p. Once again, we use C++11’s auto keyword to infer the variable’s type from its initializer—in this case, the return value of multiset member function equal_range, which is a pair object. Such objects associate pairs of values. The contents of a p will be two const_iterators for our multiset of ints. The multiset function equal_range returns a pair containing the results of calling both lower_bound and upper_bound. Type pair contains two public data members called first and second. Line 49 uses function equal_range to determine the lower_bound and upper_bound of 22 in the multiset. Line 52 uses p.first and p.second to access the lower_bound and upper_bound. We dereferenced the iterators to output the values at the locations returned from equal_range. Though we did not do so here, you should always ensure that the iterators returned by lower_bound, upper_bound and equal_range are not equal to the container’s end iterator before dereferencing the iterators.

C++11: Variadic Class Template tuple

C++ also includes class template tuple, which is similar to pair, but can hold any number of items of various types. As of C++11, class template tuple has been reimplemented using variadic templates—templates that can receive a variable number of arguments. We discuss tuple and variadic templates in Chapter 24, C++11: Additional Features.