hasing in c++ using stl ,set,unordered_set,map,unordered_map

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.

elements dont follow any order


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: 
77,4,56,89,13     //dont follow any order

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