C++ Unordered Set

The STL unordered_set is an unordered associative container that provides the functionality of an unordered set data structure.

In contrast to a regular set, the order of values in an unordered set is undefined.

Also, the unordered set is implemented as a hash table data structure whereas the regular set is implemented as a binary search tree data structure.

Create C++ STL unordered_set

In order to create an unordered set in C++, we first need to include the unordered_set header file.

#include <unordered_set>

Once we import this file, we can create an unordered set using the following syntax:

unordered_set<data_type> ust;

Here, data_type indicates the data type for the values of the unordered set.

For example,

// create an unordered_set of integers
unordered_set<int> ust_integer;

// create an unordered_set of strings
unordered_set<string> ust_string;

Initialize an Unordered Set

We can initialize a C++ unordered set in the following ways:

// Initializer List
unordered_set<int> unordered_set1 = {1, 100, 2, 9};

// Uniform Initialization
unordered_set<int> unordered_set2 {1, 100, 2, 9};

Here, we have initialized the unordered set by providing values directly to them.

Now, both unordered_set1 and unordered_set2 are initialized with {1, 100, 2, 9}.

Example: C++ unordered_set

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  // uniform initialization
  unordered_set<int> numbers {1, 100, 10, 70, 100};

  // loop across the unordered set
  // display the value
  cout << "numbers = ";
  for(auto &num: numbers) {
    cout << num << ", ";
  }

  return 0;
}

Output

numbers = 70, 10, 100, 1, 

In the above example, we have declared and initialized an unordered set named numbers using uniform initialization.

unordered_set<int> numbers {1, 100, 10, 70, 100};

Then, we have displayed the contents of the unordered set using a ranged for loop.

for(auto &num: numbers) {
  cout << num << ", ";
}

Here, we have initialized the unordered set in the order 1, 100, 10, 70, 100. Notice that we have a duplicate value 100.

But in the output, we only get the distinct numbers in no particular order (ascending, descending, insertion).

// output numbers
70, 10, 100, 1,

unordered_set<string> unordered_set1 {"One", "Two", "Three"};

unordered_set<string> unordered_set2(unordered_set_1.begin(), unordered_set_1.end());

C++ unordered_set Methods

In C++, the unordered_set class provides various methods to perform different operations on an unordered set.

Insert Element to an Unordered Set

We can insert an element into an unordered set using the insert() method. For example,

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  unordered_set<string> countries;

  // inserts "Nepal" into countries
  countries.insert("Nepal");

  // inserts "Nepal" , "India", "USA", "Korea" into countries
  countries.insert({"Nepal", "India", "USA", "Korea"});

  cout << "Countries = ";
  // display elements of countries
  for(const auto& country: countries) {
    cout << country << ", ";
  }
  return 0;
}

Output

Countries = Korea, USA, India, Nepal, 

In the above example, we have initialized an empty unordered set to store strings.

Then, we have inserted the element "Nepal" using:

countries.insert("Nepal");

We have then inserted multiple elements using:

countries.insert({"Nepal", "India", "USA", "Korea"});

Remove Elements From an Unordered Set

We can remove the element with the specified value of an unordered set using the erase() method. For example,

#include <iostream>
#include <unordered_set>
using namespace std;

// function prototype for display_unordered_set()
void display_unordered_set(const unordered_set<string> &);

int main() {

  unordered_set<string> languages {"C++", "Python", "Java", "PHP"};

  cout << "Initial unordered set:\n";
  display_unordered_set(languages);

  // remove element with value: "Python"  
  languages.erase("Python");

  cout << "\n\nFinal unordered set: \n";
  display_unordered_set(languages);

  return 0;
}

// utility function to print unordered_set elements
void display_unordered_set(const unordered_set<string> &uset) {
  for(const auto& value: uset) {
    cout << value << ", ";
  }
}

Output

Initial unordered set:
PHP, Java, Python, C++, 

Final unordered set: 
PHP, Java, C++,

In the above example, we have used the erase() method to remove an element from the unordered set.

Initially, the unordered set languages is {"C++", "Python", "Java", "PHP"}.

Then, we have used the erase() method to remove the element with value "Python".

// remove element with value: "Python"  
languages.erase("Python");

So the final unordered set becomes {"PHP", "Java", "C++"}.

Note: We can use the clear() method to remove all the elements of the unordered set.

Check If a Value Exists in the Unordered Set

We can use the following methods to check if the element exists in the unordered set.

• find() - returns the iterator to the element if the value is found, else returns the end() iterator
• count() - returns 1 if the value exists and 0 if not

For example,

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  unordered_set<int> primes {2, 3, 5, 7, 11, 13};

  cout << "Using find():" << endl;
  cout << "Does number " << 12 << " exist? ";

  // find() returns primes.end() if the value is not found 
  if (primes.find(12) != primes.end()) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  cout << "\n\nUsing count():" << endl;
  cout << "Does number " << 7 << " exist? ";

  // count() returns 0 if the value doesn't exist
  if (primes.count(7)) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  return 0;
}

Output

Using find():
Does number 12 exist? No

Using count():
Does number 7 exist? Yes

In the above example, we have used find() and count() to check if a given value exists in the unordered set.

Initially, we have used the find() method to check if the value 12 exists.

// checks if value 12 exists
if (primes.find(12) != primes.end()) {
  cout << "Yes";
}
else {
  cout << "No";
}

The find() method returns an iterator pointing to the element if it exists. If the value doesn't exist, it points to the end() iterator.

Then, we have used the count() method to check if the value 7 exists.

// checks if value 7 exists
if (primes.count(7)) {
  cout << "Yes";
}
else {
  cout << "No";
}

Get the Size of the Unordered Set

We can get the size of an unordered set using the size() method. This gives the total number of distinct elements. For example,

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  unordered_set<int> numbers {1, 100, 10, 70, 100};
  
  cout << "Size: " << numbers.size();
  
  return 0;
}

Output

Size: 4

In the above example, we have used the size() method to get the total number of distinct elements.

Notice that we have initialized the unordered set with the elements 1, 100, 10, 70, 100. But the size of the unordered list is 4.

This is because there is a duplicate of the element 100, so there are actually 4 distinct elements, not 5.