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 presentThe 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).
No comments