A set is a container optimized for fast associative lookup. A set does not allow an item to be inserted if a matching item is already present.

A hash_set is similar to a set , except a hash_set uses a user-supplied hash function to order the items. 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.

Iterator Type

Implementation

A set is implemented as a red-black tree with nodes holding the items of a set .

A hash_set is implemented as a hash table, using a user-specified hash function to position and retrieve items.

Insertion Notes

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

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 elements.

Common Uses

A set or hash_set is useful when fast associative lookup is important, when index based lookup is unnecessary, and when duplicates are not allowed.

Interface

A set has almost the same interface as a multiset . The main difference between a set and a multiset is that a set cannot contain matching items; attempts to add a duplicate item are ignored. This is illustrated by the following example, which attempts to add the number 42 twice into a set .

Example <ospace/osstd/examples/set1.cpp>


  #include <iostream>
#include <set>

void
main()
  {
  set< 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";

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

count( 42 ) = 0
count( 42 ) = 1
count( 42 ) = 1
1 elements erased

Here is the same example using a hash_set in place of a set .

Example <ospace/osstd/examples/hset1.cpp>


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

void
main()
  {
  hash_set< 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";

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

count( 42 ) = 0
count( 42 ) = 1
count( 42 ) = 1
1 elements erased

The insert() function for a set returns a pair object containing the result of the insert operation.

insert

pair<
    const_iterator, bool > insert( const Key&

key )

If the set contains an element that matches key , inserts a copy of key and returns a pair whose first element is an iterator positioned at the new element and second element is true . If the set already contains an element that matches key , returns a pair whose first element is an iterator positioned at the existing element and second element is false .

In the following example, the first insertion succeeds but the second insertion fails.

Example <ospace/osstd/examples/set2.cpp>


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

void
main()
  {
  set< int, less< int > > s;
  pair< set< int, less< int > >::iterator, bool > p;

  p = s.insert( 42 );
  if ( p.second )
    cout << "Inserted new element " << *( p.first ) << "\n";
  else
    cout << "Existing element = " << *( p.first ) << "\n";

  p = s.insert( 42 );
  if ( p.second )
    cout << "Inserted new element " << *( p.first ) << "\n";
  else
    cout << "Existing element = " << *( p.first ) << "\n";
  }

Inserted new element 42
Existing element = 42

set , hash_set