unordered_map vs unordered_set

Introduction

Before solving any challenges regarding Hash Tables, it is necessary to look at the implementations of unordered_map, and unordered_set and see how they are different. Both are implemented in C++ STL. It is also a common misconception that these two structures are the same, but they are very different from each other.

🔍 unordered_map

unordered_map is a container which is implemented using the Map interface. It stores an element in the form of key-value pairs; it maps the values to keys.

It provides the basic functionality of hashing along with some helper functions that help in the process of insertion, deletion, and search.

Some of the key features of unordered_map are given below:

• An unordered_map stores key-value pairs (examples given below) to map a key to the value:

$$abc->123$$

$$xyz->456$$

• unordered_map cannot contain duplicate keys. It can, however, have duplicate values.

• unordered_map does not store elements in any order either by the key or the value.

• unordered_map uses a hash table for its implementation. It takes the key and then maps it into the range of hash table using the hash function.

• On average, the complexity of the basic operation is $O(1)$. It will go up to $O(n)$ in the worst-case.

🔍 unordered_set

unordered_set is a container in C++ which is implemented using the Set interface. It is also built in the same way as unordered_map, i.e., using the Hash Table, but it is still quite different from the unordered_map.

Some of the key features of unordered_set are listed below:

• unordered_set is a container that implements the Set interface, and this interface only stores values, not a key-value pair. The value of an element will be its key at the same time.

$$1->1$$

$$abc->abc$$

• unordered_set does not allow storing duplicate elements as a set can only contain unique elements.

• On average, the complexity of the basic operation is $O(1)$. It will go up to $O(n)$ in the worst-case.

Member Functions

Some of the commonly used member functions of unordered_map and unordered_set are given below:

Function	Definition
end()	Returns an iterator that is pointing to the position following the last element of the container
erase(iterator/key)	Remove the element pointed by the iterator/ corresponding to the given key
find(key)	Search element with the given key. If the element is present, it will return an iterator to it. If not, it will return an iterator to the end
insert(key) / insert(key,value)	Insert new element in the container. It does not insert element with duplicate key in the container

---