multiset, hash_multiset

A multiset is a container optimized for fast associative lookup. Items are matched using operator==. Unlike a set , a multiset can contain multiple copies of the same item.

Items in a multiset are ordered according to a user-defined Comparator function object. A typical user-supplied function object is less() , which causes the items to be ordered in ascending order.

Care must be taken to use compare operations required by the comparator. For example, the less function object requires items to be comparable using operator<.

A hash_multiset is similar to a multiset , except a hash_multiset uses a user-supplied hash function to order the items. Both multiset and hash_multiset have similar interfaces, but their performance at runtime can vary depending on the types of objects they store. Hash containers are only a proposed addition to the ANSI/ISO Standard Template Library, and have not been accepted for inclusion in the final specification. Hash containers are included in Standards<ToolKit> to provide the latest STL technology available.

This section provides an overview of both multiset and hash_multiset .

Iterator Type

A multiset has bidirectional iterators. A hash_multiset has forward iterators.

Implementation

There are many different approaches to implementing an associative container. Two of these are listed below.

• Hash scheme-Mechanism that many libraries use for positioning and retrieving items.
• Red-black tree-Binary search tree that uses an extra field in every node to store the node's color. Most STL implementations use this data structure.

The multiset container is implemented using a red-black tree. Red-black trees constrain the way nodes can be colored so that the tree remains reasonably balanced. This property is important for ensuring a good overall performance. Red-black trees guarantee that the worst case performance for the most common dynamic set operations is O(log N).

One consequence of using a binary tree for storage of data is that items remain in a sorted order. STL users can therefore iterate through an associative container and access its elements in a sequenced manner.

The hash_multiset container relies on a hashing scheme to store and retrieve items. Although hashing mechanisms are capable of producing the fastest transaction times, they typically require more developer involvement. A specialized hash function must be written for each type of object stored in the hash_multiset , and the function should return a unique value for each object instance. When two different objects have the same hash values, collisions occur in the hash table and runtime performance decreases.

Standards<ToolKit> includes hash functions for primitive data types and the ANSI/ISO string class. Examples are included illustrating how to build hash functions.

Insertion Notes

When inserting a single item, the copy constructor is called one time. When inserting multiple items, the copy constructor is called once for each item inserted. Insertion does not affect iterators or references to elements.

Erasure Notes

When erasing a single item, the destructor is called once. When erasing a range of items, the destructor is called once for each item in the range. Erasure only invalidates the iterators and references to the erased items.

Common Uses

The multiset container is useful when fast associate lookup is important, when index based lookup is unnecessary, and when duplicates are allowed.

Interface

A comparison object must be specified when a multiset is instantiated so the multiset knows how to order its items. Most of the examples in this section use the less function object to order the elements. For more information about function objects, consult Auxiliary Classes in this manual.

Both a hash object and a comparison object must be specified when a hash_multiset is instantiated. The hash objects are often user-defined, although the hash function object can be used for primitive data types. The comparison object used with hash_multiset is almost always equal_to , although custom comparators are often used when the container stores pointers to objects.

Following is a list of the most basic multiset operations that insert, find, count, and erase items. To avoid redundancy, the interface for hash_multiset is not repeated.

Constructor

multiset()

Constructs an empty multiset that orders elements using the compare function specified when the multiset template was instantiated.

count

size_type count( const Key& key ) const

Returns the number of elements the multiset contains that match key .

erase

size_type erase( const Key& key )

Erases all elements that match key and returns the number of elements that were erased.

find

iterator find( const Key& key ) const

If the multiset contains an element that matches key , returns an iterator positioned at the matching element; otherwise, returns an iterator positioned at end() .

insert

iterator insert( const Key& key )

Inserts a copy of key and returns an iterator positioned at the new element.

The following example illustrates all of these operations.

#include <iostream>
#include <functional>
#include <set>

void
main()
  {
  multiset< int, less< int > >::iterator i;
  multiset< int, less< int > > s;
  cout << "count( 42 ) = " << s.count( 42 ) << "\n";

  s.insert( 42 );
  cout << "count( 42 ) = " << s.count( 42 ) << "\n";

  s.insert( 42 );
  cout << "count( 42 ) = " << s.count( 42 ) << "\n";

  i = s.find( 40 );
  if ( i == s.end() )
    cout << "40 Not found\n";
  else
    cout << "Found " << *i << "\n";

  i = s.find( 42 );
  if ( i == s.end() )
    cout << "Not found\n";
  else
    cout << "Found " << *i << "\n";

  int count = s.erase( 42 );
  cout << "Erased " << count << " instances\n";
  }

count( 42 ) = 0
count( 42 ) = 1
count( 42 ) = 2
40 not found
Found 42
Erased 2 instances

#include <iostream>
#include <functional>
#include <ospace/osstd/hashset.h>

void
main()
  {
  hash_multiset< int, hash< int >, equal_to< int > >::iterator i;
  hash_multiset< int, hash< int >, equal_to< int > > s;
  cout << "count( 42 ) = " << s.count( 42 ) << "\n";

  s.insert( 42 );
  cout << "count( 42 ) = " << s.count( 42 ) << "\n";

  s.insert( 42 );
  cout << "count( 42 ) = " << s.count( 42 ) << "\n";

  i = s.find( 40 );
  if ( i == s.end() )
    cout << "40 Not found\n";
  else
    cout << "Found " << *i << "\n";

  i = s.find( 42 );
  if ( i == s.end() )
    cout << "Not found\n";
  else
    cout << "Found " << *i << "\n";

  int count = s.erase( 42 );
  cout << "Erased " << count << " instances\n";
  }

count( 42 ) = 0
count( 42 ) = 1
count( 42 ) = 2
40 not found
Found 42
Erased 2 instances

#include <iostream>
#include <functional>
#include <set>
#include <ospace/helper.h>

char* names[] = { "dave", "alf", "chas", "bob", "ed", "chas" };

void
main()
  {
  multiset< char*, less_s > s;
  s.insert( names, names + 6 );

  multiset< char*, less_s >::iterator i;
  for ( i = s.begin(); i != s.end(); ++i )
    cout << *i << "\n";
  }

alf
bob
chas
chas
dave
ed

#include <iostream>
#include <set>
#include <functional>

bool
less_than( int a, int b )
  {
  return a < b;
  }

bool
greater_than( int a, int b )
  {
  return a > b;
  }

int array[] = { 3, 6, 1, 9 };

typedef pointer_to_binary_function< int, int, bool > fn_type;

void
main()
  {
  fn_type f( less_than );
  multiset< int, fn_type > s1( array, array + 4, f );
  multiset< int, fn_type >::const_iterator i = s1.begin();
  cout << "Using less_than: \n";
  while ( i != s1.end() )
    cout << *i++ << "\n";
  fn_type g( greater_than );
  multiset< int, fn_type > s2( array, array + 4, g );
  i = s2.begin();
  cout << "Using greater_than: \n";
  while ( i != s2.end() )
    cout << *i++ << "\n";
  }

Using less_than:
1
3
6
9
Using greater_than:
9
6
3
1

#include <iostream>
#include <set>

int array[] = { 3, 6, 1, 2, 3, 2, 6, 7, 9 };

void
main()
  {
  multiset< int, less< int > > s( array, array + 9 );
  multiset< int, less< int > >::iterator i;

  // Return location of first element that is not less than 3
  i = s.lower_bound( 3 );
  cout << "lower bound = " << *i << "\n";

  // Return location of first element that is greater than 3
  i = s.upper_bound( 3 );
  cout << "upper bound = " << *i << "\n";
  }

lower bound = 3
upper bound = 6

#include <iostream>
#include <set>
#include <utility>

int array[] = { 3, 6, 1, 2, 3, 2, 6, 7, 9 };

typedef multiset< int, less< int > > mset;

void
main()
  {
  mset s( array, array + 9 );
  pair< mset::iterator, mset::iterator > p = s.equal_range( 3 );
  cout << "lower bound = " << *( p.first ) << "\n";
  cout << "upper bound = " << *( p.second ) << "\n";
  }

lower bound = 3
upper bound = 6

Copyright©1994-2026 Recursion Software LLC
All Rights Reserved - For use by licensed users only.