14.6. The set class

A set refers to any data structure in which every member of the set is unique. The integers define a set, because every number is unique. The values {3, 1, 4, 1, 5, 9} do not define a proper set, because the value 1 is repeated.

In C++, a std::set must also be sorted. Like std::vector, a set is a generic class and declarations must include the object type stored in the class:

#include <set>

std::set<int> x {2,7,1,8,2,8,1,8,2,8,4,5,9};

What will be stored in x after initialization?

Like the sequence containers, each element in a set can be visited one at a time using a range-for loop.

#include <iostream>
#include <set>

int main()
{
  std::set<int> x {2,7,1,8,4,5,9};

  for (const auto& i: x) {
    std::cout << i << ' ';
  }

  return 0;
}

Because set does not provide operator[], traditional for loops using an index are not possible:

std::set<int> x {2,7,1,8,4,5,9};

for (int i=0; i < x.size(); ++i) {  // OK
  std::cout << x[i] << ' ';         // compile error
}

Sets of any type can be created as long as the type is comparable. The comparison operator (comparator) used in sets by default is operator <. Any type used in a set should overload operator <. All of the types are comparable.

Use set::insert to add a new element to a set or replace an existing element:

std::set<int> x {2,7,1,8,4,5,9};
x.insert(6);

Because a set is not an indexed container, every ‘get’ is a search:

std::set<int> x {2,7,1,8,4,5,9};
auto it = x.find(8);

The set::find function returns an iterator to the element with a specific key:

std::set<int> x {2,7,1,8,4,5,9};
auto it = x.find(8);
std::cout << *it;         // print the value returned from find()

The set::erase function is used to remove an element from a set. set::erase takes an iterator as the position in the set to remove:

std::set<int> x {2,7,1,8,4,5,9};
auto it = x.find(8);
if (it != x.end()) {
  x.erase(it);
}

it = x.find(8);
assert ( it == x.end() );  // this should be true

14.6.1. Variations on std::set

The STL provides 3 alternate forms of std::set class:

multiset

A set in which duplicate keys are allowed.

unordered_set

A set of unique objects stored based on the object hash function. Added in C++11.

In order to use a type in an unordered container, the type must override 3 functions:

  • override std::hash

  • override operator==

  • override operator<

before the type will compile when added to an unordered container.

unordered_multiset

An unordered_set in which duplicate keys are allowed.

More to Explore

You have attempted of activities on this page