Unordered_set C++

What is Unordered_set in C++?

Introduction

An unordered set in C++ is a container data structure. This means that we can store different elements in it. The special thing about an unordered set is that it stores unique elements. So, if you insert a repetitive element in an unordered set in C++, it will still contain only one instance of this element. Another special thing about this container is that it stores elements in no particular order. This makes the unordered set different from the set in C++, which stores elements in increasing order.

Using an example, let us try to understand how an unordered set stores elements in C++. Suppose we insert the elements 1,4,9,2,1,10 in an unordered_set C++. The unordered set will look like this:

As you can see, the duplicate element 1 was removed, and the elements are arranged in no particular order.

Unordered sets are particularly useful when you want to count the number of distinct elements or when you want to find if a particular element occurs at least once in a collection of elements quickly and efficiently. We will discuss the complexity of unordered_set C++ in the upcoming sections.

How to Create Unordered_set in C++?

We now know for what purpose we can utilize an unordered set in C++. Let us look at how we can create an unordered set.

First, the header library that allows us to use an unordered set in C++ is the <unordered_set> header file. This needs to be included at the top of our code to use an unordered set in C++.

The syntax for declaring an empty unordered_set in C++ is:

Here, data_type represents the data type of the elements which will be inserted in the unordered set.

How to Initialize an Unordered_set in C++?

We have looked at creating an empty unordered_set in C++, but if we want to create an unordered set with some elements already present, first, we need to import the <unordered_set> header file. The syntax for initializing an unordered_set C++ is:

OR

Both of these methods will produce the same result. Here, data_type represents the data type of the elements that will be inserted in the unordered set, and e1, e2, e3, e4, ... are the elements that are to be inserted in the unordered_set when it is created.

Let us look at an example code for unordered_set C++.

How is Unordered_set Implemented Internally in C++?

We have seen how to create and initialize an unordered_set C++, but how do these containers store elements internally? The unordered set in C++ is implemented using a hash table. So, whenever we enter an element into our unordered set, it passes through a hash function to generate a hash key which is then stored in the hash table. As this hash key depends on the function and is a randomized process, that is why the unordered set C++ stores elements randomly and in no particular order.

This is also why the complexity of the unordered set depends on the underlying hash function. In average cases, all operations on an unordered set in C++ take O(1) constant time, but they take O(n) time in the worst case, though this worst case is very rare.

Set vs Unordered_set in C++

Another container element in C++, called set, is almost the same as an unordered set in C++. The main difference between an unordered set and a set is that while a set stores unique elements in increasing order of their value, unordered set stores the elements randomly, in no particular order.

As we previously discussed, an unordered set is implemented using a hash table in C++, which is why it stores elements in random order. The set in C++, on the other hand, uses a balanced tree for its implementation, which is why it can store elements in sorted order.

This difference in implementation also leads to a difference in time complexities of different operations of both containers. The unordered_set C++ has a time complexity of O(1) on average for all operations, while the set in C++ has an average time complexity of O(log(n)). But both have a space complexity of O(n), where n is the number of elements stored in them.

Methods of Unordered Set in C++

Let us look at the different methods that can be used along with unordered set in C++ and their syntax and time complexity.

How to Iterate Over the Elements of an Unordered Set in C++?

We can iterate over arrays in C++ using indexes, but there is no such thing as an index in an unordered set in C++. Instead, some iterators point to the different elements in the unordered set. Using these iterators, we can travel the unordered set and all its elements.

As we saw in the previous section, the begin() method will return the iterator, pointing to the beginning of the unordered set where we can start our loop. Similarly, the end() method will return the iterator after the last element of the unordered set, which will make up the terminating condition of our loop.

Let us look at the code for the same.

Output

In the above code, we initialized the iterator to the beginning of the unordered set and iterated until we reached the ending iterator. This is how we can traverse the elements in an unordered set in C++.

Let us now look at an example in which we will use an unordered set in C++.

Unordered Set in C++ Example

Suppose we are given an array of integers and need to output the array of duplicate elements in that array. We can use an unordered set in C++ in such a case. We will iterate over the array and add elements into an unordered set. Before adding an element, we can first check if it already exists in the unordered set by using the count() or the find() function, which was defined in the previous sections, and output it if it already exists, else insert it into the unordered set.

Let us now look at the code for the same.

Ouput