Unordered Set in C++ STL

Filed Under: C++
Unordered Sets Featured Image

The C++ Standard Template Library supports several data structures that play an important role in any programmer’s life. One such data container is the “Unordered Set in C++. Unlike the STL Sets, these types of sets are unordered in their way of storing elements.

Properties of Unordered Sets

The following are the properties of unordered sets in C++ STL.

  • Uniqueness – Every element inside an unordered set is unique.
  • Unindexed – The elements in an unordered set can not be indexed by position, like in vectors and maps.
  • Immutable – We cannot modify or change the elements in unordered sets. A set only supports the addition and deletion of its elements.
  • Internal Implementation – We use hash tables to implement unordered sets

Initialization of Unordered Sets

There can be multiple ways to initialize unordered sets in C++.

// For the usage of unordered set
#include<unordered_set>

// For input output
#include<iostream>
using namespace std;


int main(){

	// Method - 1
	// An empty unordered set of integers
	unordered_set<int> s1;

	// Method - 2	
	// Hard-coded unordered set
	unordered_set<int> s2 = {1, 4, 8, 3, 2};

	// Method - 3
	// Initializing an unordered set using another unordered set
	unordered_set<int> s4(s2);
	// s4 = {1, 4, 8, 3, 2}

	// Method - 4
	// Initializing an unordered set using arrays
	int arr[] = {6, 2, 4, 5, 1};
	unordered_set<int> s5(arr, arr+3);
	// s4 = {4, 2, 6}

}

The fourth method saves the elements in a reversed manner. That’s because the elements are inserted at the beginning of the unordered set.


Traversing an Unordered Set

We must initialize an iterator which will be responsible for traversing the set and accessing each element. Unordered sets support two built-in functions that return an iterator.

  • begin() – Returns an iterator to the first element of the set.
  • end() – Returns an iterator past the last element of the set.

We will know the starting and ending of the set with the help of these two functions.

// For the usage of unordered set
#include<unordered_set>

// For input output
#include<iostream>
using namespace std;

int main(){

	// Hard-coded unordered set
	unordered_set<int> s1 = {1, 4, 8, 3, 2};

	// Initializing an iterator for unordered set
	unordered_set<int> :: iterator it;

	// Printing each element
	for(it=s1.begin(); it != s1.end(); it++)
		cout<<*it<<" ";
	cout<<endl;
}

Output:

2 3 4 8 1 

The iterator can be used to fetch the value it points using '*' operator.


Adding elements to an unordered set

The insertion of elements happens when the insert() function is used.

// For the usage of unordered set
#include<unordered_set>

// For input output
#include<iostream>
using namespace std;


int main(){

	// Hard-coded unordered set
	unordered_set<int> s1 = {1, 4, 8, 3, 2};

	// Inserting elements in the set 
	s1.insert(5);
	s1.insert(10);
	s1.insert(4);

	// Initializing an iterator for unordered set
	unordered_set<int> :: iterator it;

	// Printing each element
	for(it=s1.begin(); it != s1.end(); it++)
		cout<<*it<<" ";

	cout<<endl;
}

Output:

10 1 8 4 3 2 5 

If we try to insert an element already present in the unordered set, we won’t receive an error. The average time complexity of insertion in an unordered set is O(1), which may tend to reach O(n) in the worst case.


Deleting elements from an unordered set

The deletion process is very simple. We can search the hash tables that were initally created to delete specific elements. The erase() function takes in the value to be removed from the set.

// For the usage of unordered set
#include<unordered_set>

// For input output
#include<iostream>
using namespace std;


int main(){

	// Hard-coded unordered set
	unordered_set<int> s1 = {1, 4, 8, 3, 2};

	// Deleting elements from the set 
	s1.erase(8);
	s1.erase(1);
	s1.erase(5);

	// Initializing an iterator for unordered set
	unordered_set<int> :: iterator it;

	// Printing each element
	for(it=s1.begin(); it != s1.end(); it++)
		cout<<*it<<" ";

	cout<<endl;
}

Output:

2 3 4 

Similar to the insert() function, no error is raised when we attempt to remove elements not present in the set. The complexities of adding and removing elements are alike.


Searching an element in an unordered set in C++

Searching an element in an unordered set is time-efficient as it done by hash tables. It only takes O(1) time, in average case, to check whether an element is present inside the set or not.

This is a huge improvement to the O(logN) time complexity for ordered sets, that use balanced BSTs for internal implementation.

The searching mechanism is abstracted by the find() fucntion, that takes in the value to be searched and returns an iterator to the position. In case, the value is not present, it returns the iterator past the last element of the set.

// For the usage of unordered set
#include<unordered_set>

// For input output
#include<iostream>
using namespace std;


int main(){

	// Hard-coded unordered set
	unordered_set<int> s1 = {1, 4, 8, 3, 2};

	int value = 8;

	// Searching 'value' in the unordered set
	if(s1.find(value) != s1.end())
		cout<<value<<" is present in the set"<<endl;
	else
		cout<<value<<" is not present in the set"<<endl;

	value = 7;

	// Searching 'value' in the unordered set
	if(s1.find(value) != s1.end())
		cout<<value<<" is present in the set"<<endl;
	else
		cout<<value<<" is not present in the set"<<endl;

}

Output:

8 is present in the set
7 is not present in the set

This sums up the basic operations on an unordered set in C++ STL.


Other useful set functions

A few useful functions that may come in handy:

  • size() – Returns the number of elements in the unordered set.
  • empty() – Returns true if the set is empty, otherwise false.
  • clear() – Empties the entire set.
  • swap(set1, set2) – Swaps complete sets passed as arguments.
  • emplace(value) – Inserts the value passed as argument, into the set.
  • count(value) – Returns the frequency of a value in the set, which can be either 1 or 0.

Conclusion

Both the ordered and unordered set support similar kinds of operations, with a trade-off of complexities. The main reason behind such difference in complexities is the type of internal implementation.

It is up to your decision to select the type of set to be used in the algorithms. We hope this article was easy to comprehend. Feel free to comment below for any follow-up question.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages