Unordered Sets

Anonymous contributor's avatar
Anonymous contributor
Published Oct 23, 2024
Contribute to Docs

In C++, unordered sets are associative containers that store unique elements in no particular order, offering fast look-ups, insertions, and deletions through a hash table. Unlike std::set, which maintains elements in sorted order using a binary tree, unordered sets provide better performance with average constant time complexity for key operations. If elements are needed in a sorted order, std::set can be used, although it comes with higher overhead due to its tree-based structure.

Syntax

#include <unordered_set>
std::unordered_set<data_type> set_name;
  • data_type: The data type of the elements to be stored in the unordered set (e.g., int, string). Each element in the unordered set will be of this type.
  • set_name: The name of the unordered set being defined.

Example

In this example, an unordered set is initiated and elements are inserted using the .insert() method. The elements are then printed:

#include <iostream>
#include <unordered_set>
int main() {
// Initiate an unordered set of elements (integers in this example)
std::unordered_set<int> numSet;
// Insert the elements
numSet.insert(10);
numSet.insert(20);
numSet.insert(30);
numSet.insert(40);
// Print out the set elements
std::unordered_set<int> :: iterator iter;
for (iter = numSet.begin(); iter != numSet.end(); iter++) {
std::cout<< *iter << " ";
}
}

The output would be:

20 40 30 10

Note: The element order is not guaranteed to be consistent across executions.

Ordered vs Unordered Sets

Feature Ordered Set (std::set) Unordered Set (std::unordered_set)
Order Elements in sorted order No particular order
Structure Tree-based Hash table
Time O(log n) O(1)
Memory More efficient memory usage Higher memory usage as a result of hashing
Performance Consistent performance across all cases Can degrade to O(n) if hashing is poor
Usage Use when element ordering is useful or required Use when efficiency is required and ordering is not important

Note: Neither std::set nor std::unordered_set allows duplicate elements.

Codebyte Example

This example builds on the previous example, adding a duplicate element to show it won’t be included, and then checking if an element exists:

Code
Output
Loading...

All contributors

Contribute to Docs

Learn C++ on Codecademy