Hashing in C++  STL is implemented using these following containers:

set

unordered_set

map

unordered_map

## set

in sets all elements are unique.

elements are always in sorted order.

functions on sets:

begin() – Returns an iterator to the first element in the set.

end() – Returns an iterator to the theoretical element that follows last element in the set.

size() – Returns the number of elements in the set.

insert(val) – Inserts a new element val in the Set.

find(val) - Returns an iterator pointing to the element val in the set if it is present.

empty() – Returns whether the set is empty.

```
// C++ program to illustrate hashing using
// set in CPP STL

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main()
{
// empty set container
set <int> s;
set <int> :: iterator itr;
set <int, greater <int> > :: iterator ptr;
// List of elements
int arr[5] = {56,77,4,13,89};

// Insert the elements of the List
// to the set
for(int i = 0; i < 5; i++)
s.insert(arr[i]);

// Print the content of the set
// The elements of the set will be sorted
// without any duplicates
cout<<"The elements in the set are: \n";
for( itr=s.begin(); itr!=s.end(); itr++)
{
cout<<*itr<<" ";
}
cout<<"The elements in the set in reverse order are: \n";
for( ptr=s.begin(); ptr!=s.end(); ptr++)
{
cout<<*ptr<<" ";
}
// Check if 13 is present in the set
if(s.find(13)!=s.end())
{
cout<<"\n\n13 is present";
}
else
{
cout<<"\n\n13 is not present";
}

return 0;
}
```
output:
```The elements in the set are:
4,13,56,77,89
The elements in the set in reverse order are:
89,77,56,13,4

13 is present```
The time complexity of set operations is O(Log n).

## unordered_set

in unordered_set all elements are unique.

functions on unordered_sets are same as of sets.

```// C++ program to illustrate hashing using
// set in CPP STL

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main()
{
// empty unordered_set  container
unordered_set <int> s;
unordered_set <int> :: iterator itr;

// List of elements
int arr[5] = {56,77,4,13,89};

// Insert the elements of the List
// to the unordered_set
for(int i = 0; i < 5; i++)
s.insert(arr[i]);

// Print the content of the unordered_set
// The elements of the set will be sorted
// without any duplicates
cout<<"The elements in the set are: \n";
for( itr=s.begin(); itr!=s.end(); itr++)
{
cout<<*itr<<" ";
}

// Check if 13 is present in the unordered_set
if(s.find(13)!=s.end())
{
cout<<"\n\n13 is present";
}
else
{
cout<<"\n\n13 is not present";
}

return 0;
}
```
output:
```The elements in the unordered_set are:

13 is present ```
The time complexity of unordered_set operations is O(1).

## Map container

Maps store elements in a mapped fashion.
Each element has a key and a value.
value can be same but key can never be same (key should be unique).
the order is sorted according to keys.

example:
map<int,int>m;
m[5]=10;
here 5 is key and 10 is value

functions on Map:
begin() – Returns an iterator to the first element in the map.
end() – Returns an iterator to the theoretical element that follows last element in the map.
size() – Returns the number of elements in the map.
empty() – Returns whether the map is empty.
insert({keyvalue, mapvalue}) – Adds a new element to the map.
erase(iterator position) – Removes the element at the position pointed by the iterator
erase(const g)– Removes the key value ‘g’ from the map.
clear() – Removes all the elements from the map.

```
// C++ program to illustrate Map container

#include <iostream>
#include <iterator>
#include <map>

using namespace std;

int main()
{
// empty map container
map<int, int> mp;

// Insert elements in random order
// First element of the pair is the key
// second element of the pair is the value
mp.insert(pair<int, int>(1, 45));
mp.insert(pair<int, int>(2, 33));
mp.insert(pair<int, int>(3, 67));
mp.insert(pair<int, int>(4, 28));
mp.insert(pair<int, int>(5, 51));
mp.insert(pair<int, int>(6, 78));
mp.insert(pair<int, int>(7, 45));

// printing map mp
map<int, int>::iterator itr;
cout << "The map mp is : \n";
cout << "KEY\tELEMENT\n";
for (itr = mp.begin(); itr != mp.end(); ++itr) {
cout << itr->first
<< '\t' << itr->second << '\n';
}

return 0;
} ```
output:
```The map mp is :
KEY    ELEMENT
1    45
2    33
3    67
4    28
5    51
6    78
7    45
```
The time complexity of map operations is O(Log n).

## unordered_map Container

unordered_Map store elements in a mapped fashion.
Each element has a key and a value.
value can be same but key can never be same (key should be unique).
they dont follow any specific order.

functions on unordered_maps are same as of maps.

example:
unordered_map<int,int>m;
m[5]=10;
here 5 is key and 10 is value

```// C++ program to illustrate Map container

#include <iostream>
#include <iterator>
#include <unordered_map>

using namespace std;

int main()
{
// empty map container
unordered_map<int, int> mp;

// Insert elements in random order
// First element of the pair is the key
// second element of the pair is the value
mp.insert(pair<int, int>(1, 45));
mp.insert(pair<int, int>(2, 33));
mp.insert(pair<int, int>(3, 67));
mp.insert(pair<int, int>(4, 28));
mp.insert(pair<int, int>(5, 51));
mp.insert(pair<int, int>(6, 78));
mp.insert(pair<int, int>(7, 45));

// printing map mp
unordered_map<int, int>::iterator itr;
cout << "The unordered_map mp is : \n";
cout << "KEY\tELEMENT\n";
for (itr = mp.begin(); itr != mp.end(); ++itr) {
cout << itr->first
<< '\t' << itr->second << '\n';
}

return 0;
} ```

output:
```The unordered_map mp is :
KEY    ELEMENT
2    33
7    45
4    28
1    45
5    51
3    67
6    78```
The time complexity of unordered_map operations is O(1).

darkmode