Map, Multimap, Unordered Map

/********************************* Maps ***********************************/

Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have same key values.

Some basic functions associated with 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
max_size() – Returns the maximum number of elements that the map can hold
empty()  – Returns whether the map is empty

pair 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

============================================================

Example

#include <iostream> 
#include <iterator> 
#include <map> 
using namespace std; 
int main() 
{ 
// empty map container 
map<int, int> gquiz1; 
// insert elements in random order 
gquiz1.insert(pair<int, int>(1, 40)); 
gquiz1.insert(pair<int, int>(2, 30)); 
gquiz1.insert(pair<int, int>(3, 60)); 
gquiz1.insert(pair<int, int>(4, 20)); 
gquiz1.insert(pair<int, int>(5, 50)); 
gquiz1.insert(pair<int, int>(6, 50)); 
gquiz1.insert(pair<int, int>(7, 10)); 
// printing map gquiz1 
map<int, int>::iterator itr; 
cout << "\nThe map gquiz1 is : \n"; cout << "\tKEY\tELEMENT\n"; 
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) { 
cout << '\t' << itr->first << '\t' << itr->second << '\n'; 
} 
cout << endl; 
// assigning the elements from gquiz1 to gquiz2 
map<int, int> gquiz2(gquiz1.begin(), gquiz1.end()); 

// print all elements of the map gquiz2 
cout << "\nThe map gquiz2 after"
<< " assign from gquiz1 is : \n"; 
cout << "\tKEY\tELEMENT\n"; 
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
cout << '\t' << itr->first 
<< '\t' << itr->second << '\n'; 
} 
cout << endl; 
// remove all elements up to 
// element with key=3 in gquiz2 
cout << "\ngquiz2 after removal of"
" elements less than key=3 : \n"; 
cout << "\tKEY\tELEMENT\n"; 
gquiz2.erase(gquiz2.begin(), gquiz2.find(3)); 
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
cout << '\t' << itr->first 
<< '\t' << itr->second << '\n'; 
} 
// remove all elements with key = 4 
int num; 
num = gquiz2.erase(4); 
cout << "\ngquiz2.erase(4) : "; 
cout << num << " removed \n"; 
cout << "\tKEY\tELEMENT\n"; 
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
cout << '\t' << itr->first 
<< '\t' << itr->second << '\n'; 
} 
cout << endl; 
// lower bound and upper bound for map gquiz1 key = 5 
cout << "gquiz1.lower_bound(5) : "
<< "\tKEY = "; 
cout << gquiz1.lower_bound(5)->first << '\t'; 
cout << "\tELEMENT = "
<< gquiz1.lower_bound(5)->second << endl; 
cout << "gquiz1.upper_bound(5) : "
<< "\tKEY = "; 
cout << gquiz1.upper_bound(5)->first << '\t'; 
cout << "\tELEMENT = "
<< gquiz1.upper_bound(5)->second << endl; 
return 0; 
} 


=======================================================
Output:
The map gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    20
    5    50
    6    50
    7    10

The map gquiz2 after assign from gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    20
    5    50
    6    50
    7    10

gquiz2 after removal of elements less than key=3 : 
    KEY    ELEMENT
    3    60
    4    20
    5    50
    6    50
    7    10
gquiz2.erase(4) : 1 removed 
    KEY    ELEMENT
    3    60
    5    50
    6    50
    7    10
gquiz1.lower_bound(5) :     KEY = 5        ELEMENT = 50
gquiz1.upper_bound(5) :     KEY = 6        ELEMENT = 50

=======================================================


/********************************* MultiMaps ***********************************/

Multimaps are part of the C++ STL (Standard Template Library). Multimaps are the associative containers like map that stores sorted key-value pair, but unlike maps which store only unique keys, multimap can have duplicate keys. By default it uses < operator to compare the keys.

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

using namespace std;

int main()
{
multimap <int, int> gquiz1; // empty multimap container

// insert elements in random order
gquiz1.insert(pair <int, int> (1, 40));
gquiz1.insert(pair <int, int> (2, 30));
gquiz1.insert(pair <int, int> (3, 60));
gquiz1.insert(pair <int, int> (6, 50));
gquiz1.insert(pair <int, int> (6, 10));

// printing multimap gquiz1
multimap <int, int> :: iterator itr;
cout << "\nThe multimap gquiz1 is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr)
{
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;

//adding elements randomly,
// to check the sorted keys property
gquiz1.insert(pair <int, int> (4, 50));
gquiz1.insert(pair <int, int> (5, 10));
// printing multimap gquiz1 again
cout << "\nThe multimap gquiz1 after adding extra elements is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr)
{
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;



// assigning the elements from gquiz1 to gquiz2
multimap <int, int> gquiz2(gquiz1.begin(),
gquiz1.end());

// print all elements of the multimap gquiz2
cout << "\nThe multimap gquiz2 after assign from gquiz1 is : \n";
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}
cout << endl;

// remove all elements up to
// key with value 3 in gquiz2
cout << "\ngquiz2 after removal of elements less than key=3 : \n";
cout << "\tKEY\tELEMENT\n";
gquiz2.erase(gquiz2.begin(), gquiz2.find(3));
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}

// remove all elements with key = 4
int num;
num = gquiz2.erase(4);
cout << "\ngquiz2.erase(4) : ";
cout << num << " removed \n" ;
cout << "\tKEY\tELEMENT\n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << itr->first
<< '\t' << itr->second << '\n';
}

cout << endl;

//lower bound and upper bound for multimap gquiz1 key = 5
cout << "gquiz1.lower_bound(5) : " << "\tKEY = ";
cout << gquiz1.lower_bound(5)->first << '\t';
cout << "\tELEMENT = " << gquiz1.lower_bound(5)->second << endl;
cout << "gquiz1.upper_bound(5) : " << "\tKEY = ";
cout << gquiz1.upper_bound(5)->first << '\t';
cout << "\tELEMENT = " << gquiz1.upper_bound(5)->second << endl;

return 0;
}

//-----------------------------------
Output
The multimap gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    6    50
    6    10


The multimap gquiz1 after adding extra elements is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    50
    5    10
    6    50
    6    10


The multimap gquiz2 after assign from gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    50
    5    10
    6    50
    6    10


gquiz2 after removal of elements less than key=3 : 
    KEY    ELEMENT
    3    60
    4    50
    5    10
    6    50
    6    10

gquiz2.erase(4) : 1 removed 
    KEY    ELEMENT
    3    60
    5    10
    6    50
    6    10

gquiz1.lower_bound(5) :     KEY = 5        ELEMENT = 10
gquiz1.upper_bound(5) :     KEY = 6        ELEMENT = 50
//-----------------------------------







/********************************* UnOrderedMaps ****************************/

unordered_map is an associated container that stores elements formed by the combination of key-value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined. 

Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O(1). 

// C++ program to demonstrate functionality of unordered_map
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
// Declaring umap to be of <string, int> type
// key will be of string type and mapped value will
// be of int type
unordered_map<string, int> umap;

// inserting values by using [] operator
umap["GeeksforGeeks"] = 10;
umap["Practice"] = 20;
umap["Contribute"] = 30;

// Traversing an unordered map
for (auto x : umap)
cout << x.first << " " << x.second << endl;

}




Difference : 

                  | map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |  

search time     | log(n)              | O(1) -> Average 
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search
                      
Deletion time   | log(n) + Rebalance  | Same as search
















unordered_map vs map : 
map (like set) is an ordered sequence of unique keys whereas in unordered_map key can be stored in any order, so unordered. 
The map is implemented as a balanced tree structure that is why it is possible to maintain order between the elements (by specific tree traversal). The time complexity of map operations is O(log n) while for unordered_map, it is O(1) on average. 








Comments

Post a Comment

Popular posts from this blog

Difference between Structure and Array in C

  On the basis of internal implementation following are some basic differences between both. Sr. No. Key Structure Array 1 Definition Structure can be defined as a data structure used as container which can hold variables of different types. On other hand Array is a type of data structure used as container which can hold variables of same type and do not support multiple data type variables. 2 Memory Allocation Memory allocation for input data in structure does not necessary to be in consecutive memory location. While in case of array the input data stored in contiguous memory allocation which implies that array stores data in such memory model where it assigns consecutive memory blocks (that is, memory blocks having consecutive addresses). 3 Accessibility In order to access the element in Structure we require to have the name of that element i.e it is mandatory to have element name for its retrieval from Structure. On other hand in case of Array we can access the element by index....
Read more

new operator

 new operator The new operator denotes a request for memory allocation on the Heap. If sufficient memory is available, new operator initializes the memory and returns the address of the newly allocated and initialized memory to the pointer variable. Syntax to use new operator: To allocate memory of any data type, the syntax is: pointer-variable = new data-type; Here, pointer-variable is the pointer of type data-type. Data-type could be any built-in data type including array or any user defined data types including structure and class. Example: // Pointer initialized with NULL // Then request memory for the variable int *p = NULL;  p = new int;                OR // Combine declaration of pointer  // and their assignment int *p = new int;  Initialize memory: We can also initialize the memory using new operator: pointer-variable = new data-type(value); Example: int *p = new int(25); float *q = new float(75.25); Allocate block of m...
Read more