unordered_map vs unordered_set
This lesson will discuss the difference between unordered_map and unordered_set and look at some of their key features.
We'll cover the following
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
storeskey-value
pairs (examples given below) to map a key to the value:
unordered_map
cannot contain duplicate keys. It can, however, have duplicate values.
-
unordered_map
does not store elements in any order either by thekey
or thevalue
. -
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 . It will go up to 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 theSet
interface, and this interface only stores values, not akey-value
pair. Thevalue
of an element will be itskey
at the same time.
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 . It will go up to 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 |
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.