Multiset — Associative

A multiset is an associative container with the same properties as a set,but allowing storage of duplicate keys.

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 a multiset allows multiple elements to have the same value: inserting an element that is already present adds another copy of it, instead of being rejected as it would be for a set. (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; // declare 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

References

http://www.sgi.com
Nicolai M. Josuttis: "The C++ Standard Library"
http://www.java2s.com
http://www.smu.ca/academic/science/compsci

Example 1

Problem

This example of program shows how we can determine lower bound of a value in a multiset.

Workings

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

using namepace std;

int main()
{
  int a[5] = { 11, 10, 85, 11, 23 };
  std::multiset< int, std::less< int > > intMs;
  std::ostream_iterator< int > output(cout, " " );

  // insert elements of array a into intMs
  intMs.insert(a, a+5);
  cout << "\nThe multiset contains:\n";
  std::copy( intMs.begin(), intMs.end(), output);

  // determine lower bound of 11 in intMs
  cout <<"\n\nLower bound of 11: "<<*(intMs.lower_bound(11));
  cout<<endl;

  return 0;
}

Solution

Output:

The multiset contains:
10 11 11 23 85

Lower bound of 11: 11

Example 2

Problem

This example of program shows how we can determine upper bound of a value in a multiset.

Workings

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
  int a[5] = { 11, 10, 85, 11, 23};
  std::multiset< int, std::less< int > > intMs;
  std::ostream_iterator< int > output( cout, " " );

  // insert elements of array a into intMs
  intMultiset.insert(a, a+5);
  cout <<"\nThe multiset contains:\n";
  std::copy(intMs.begin(), intMs.end(), output);

  // determine upper bound of 11 in intMs
  cout <<"\nUpper bound of 11: "<<*(intMs.upper_bound(11));
  cout<<endl;

  return 0;
}

Solution

Output:

The multiset contains:
10 11 11 23 85

Upper bound of 11: 23

Example 3

Problem

This program illustrates the difference between sets and multisets. First we create an empty set of integers, then we try to insert multiple copies of the same value into that set. Only a single copy of each value goes into the set, thus showing that the values stored in a set are unique.

Workings

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main()
{
  set<int> s;
  pair<set<int>:: iterator, bool> result;
 
  // try to insert 1 twice and 2 once, ignoring the return value of the call to insert()
  s.insert(1);
  s.insert(1);
  s.insert(2);
  cout<<"\nThe values in the set are: ";
  set<int>:: iterator it=s.begin();
  while(it!=s.end())
   cout <<*it++<<" ";

  // try to insert 3, then 4 twice, and 5, each time using the return value of insert()
  result=s.insert(3);
  cout <<"\n3 "<<(result.second ? "" : "not ")<<"inserted\n";
  result=s.insert(4);
  cout <<"4 "<<(result.second ? "" : "not ")<<"inserted\n";
  result=s.insert(4);
  cout <<"4 "<<(result.second ? "" : "not ")<<"inserted\n";
  result=s.insert(5);
  cout <<"5 "<<(result.second ? "" : "not ")<<"inserted\n";

  cout<<"\nThe set contains: ";
  it=s.begin();
  while(it!=s.end())
   cout <<*it++<<" ";

  // create an empty multiset of integers and try to insert, copies of the same value
  // this time all values are actually inserted, showing that multiset can hold duplicates values
  multiset<int> ms;
  ms.insert(1);
  ms.insert(1);
  ms.insert(2);
  ms.insert(3);
  ms.insert(4);
  ms.insert(4);
  ms.insert(4);
  ms.insert(5);
  cout<<"\nThe multiset contains: "
  multiset<int>::iterator itt = ms.begin();
  while(itt!=ms.end())
   cout <<*itt++<<" ";

  return 0;
}

Solution

Output:

The values in the set are: 1, 2

3 inserted
4 inserted
4 not inserted
5 inserted

The set contains: 1 2 3 4 5

The multiset contains: 1 1 2 3 4 4 4 5

Example 4

Problem

This example of program displays first a set, then a multiset, of positive integer values.
In each case, the user is permitted to enter values of the user's choice and the program provides the lower and upper bound of each value entered, relative to the set of values, or the multiset of values, as the case may be.

Workings

#include <iostream>
#include <set>

using namespace std;

int main()
{
  int a[] ={0, 2, 4, 6, 8};
  set<int> s(a, a+5);
  cout <<"\nThe set contains:\n";
  ostream_iterator<int> os_it(cout," "); 
  copy(s.begin(), s.end(), os_it); 
   cout << endl;
  
  int value;
  cout <<"\nEnter a value to see his upper and lower bound in the above set "
         "(or end-of-file to quit): ";
  
  while(cin>>value)
  {
    cin.ignore(80, '\n');
    set<int>::iterator lower=s.lower_bound(value);
    set<int>::iterator upper=s.upper_bound(value);
    cout <<"\nLower bound of "<<value<<" = ";
    if(lower==s.end())
      cout <<"the end of the range";
    else
      cout <<*upper;
    cout <<"\nEnter a value to see his upper and lower bound in the above sequence"
           "(or end-of-file to quit): ";
  }

  cin.clear();
  // we do the same for a multiset of values

  int b[] = {2, 2, 2, 4, 4, 4, 6, 6, 6, 8, 8, 8, 10, 10, 10};
  multiset<int> ms(b, b+15);
  cout<<"\nThe multiset contains:\n";
  copy(ms.begin(), ms.end(), os_it);
  cout << endl;
  cout <<"\nEnter a value to see his upper and lower bound in the above multiset "
         "(or end-of-file to quit): ";

  while(cin>>value)
  {
    cin.ignore(80, '\n');
    set<int>::iterator lowerMs=ms.lower_bound(value);
    set<int>::iterator upperMs=ms.upper_bound(value);
    cout <<"\nLower bound of "<<value<<" = ";
    if(lowerMs==ms.end())
      cout <<"the end of the range";
    else
      cout <<*upperMs;
    cout <<"\nEnter a value to see his upper and lower bound in the above sequence "
           "(or end-of-file to quit): ";
  }

  return 0;
}

Solution

Output:

The set contains:
2 4 6 8 10

Enter a value to see its lower and upper bound in the above set (or end-of-file to quit): 6

Lower bound of 6 = 6
Upper bound of 6 = 8

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): 2

Lower bound of 2 = 2
Upper bound of 2 = 4

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): 10

Lower bound of 10 = 10
Upper bound of 10 = the end of the range

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): 1

Lower bound of 1 = 2
Upper bound of 1 = 2

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): 12

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): ^Z

The multiset contains:
2 2 2 4 4 4 6 6 6 8 8 8 10 10 10

Enter a value to see its lower and upper bound in the above multiset (or end-of-file to quit): 2

Lower bound of 2 = 2
Upper bound of 2 = 4

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): 6

Lower bound of 6 = 6
Upper bound of 6 = 8

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): 10

Lower bound of 10 = 10
Upper bound of 10 = the end of the range

Enter a value to see its lower and upper bound in the above sequence (or end-of-file to quit): ^Z