Hash Sets

c++17 containers intermediate

Related: Hash Maps

Hash sets are known as unordered_sets in C++. The C++ standard library’s implementation of hash set is called std::unordered_set. std::unordered_set makes no guarantees about the order of its keys and their order can depend on when they are inserted into the set. This means when iterating the keys of std::unordered_set we cannot know the order of iteration. This allows std::unordered_set to optimize for the usage of element insertion and search, or the finding of individual values by key, when compared to std::set.

#include <array>
#include <unordered_set>
#include <iostream>

int main() {
  std::array numbers{1, 2, 42, 8, 0, -7, 2, 5, 10, 3, -100, 5};

  std::unordered_set<int> uniqueNumbers;
  for (auto n : numbers) {
    uniqueNumbers.insert(n);
  }

  std::cout << uniqueNumbers.size() << " unique numbers\n";
}

10 unique numbers

Element Lookup

To find an element in a std::unordered_set we use the find() method. The find() method returns an iterator to a key, meaning an iterator to Key. If nothing was found, the end() iterator is returned from the unordered_set.

#include <unordered_set>
#include <string>
#include <iostream>

int main() {
  std::unordered_set<std::string> planets{
    {"Venus"},
    {"Earth"},
    {"Mars"},
  };

  auto it = planets.find("Earth");
  if (it != planets.end()) {
    std::cout << *it << "\n";
  } else {
    std::cout << "No such planet.\n";
  }
  
  it = planets.find("PlanetX");
  if (it != planets.end()) {
    std::cout << *it << "\n";
  } else {
    std::cout << "No such planet.\n";
  }
}

Earth
No such planet.

Storing Custom Types

std::unordered_set requires that the keys of the set are able to be compared for equality, meaning the keys should support the equality operator (==). The keys of std::unordered_set are also required to be able to be hashable meaning you need to write a specialization of std::hash for the key type. To learn more click here.

Another Set Container

There’s another ordered key container in C++: std::set. While technically not a hash set, std::set is a container that maintains its keys in sorted order at all times. Click here to learn more.