C Map Does Key Need to Be Continuous
Overview
Maps in C++ are container structures that store elements in key-value pairs. This means that for every unique key, there is a data value mapped to it, that can be easily accessed if we know the key. This is why every key has to be unique, and no two keys can be the same(but the values associated to keys can be the same).
Maps in C++ store the key-value pairs in sorted order by default so that the search for any key-value pair can be very quick.
Scope
- This article explores the container data structures map in C++.
- This article also focuses on the STL map in C++, including all the member functions provided in the library as well as their uses.
- This article shows the implementation and syntax of maps in C++.
What is Map in C++?
Have you ever wondered how the mechanism of storing books in a library works? Usually, library management systems make use of something similar to maps to search efficiently where a book must be kept. Each book is assigned a shelf number, which is stored in the computer system, for easy and fast lookup.
This is very similar to how maps work. Maps are container structures that store key-value pairs. This means that each key is unique and points to a specific value. Just like each book is unique and points to a specific shelf in the library.
Not only this but maps can also be used in storing the memory addresses of variables in our code, in fact, it stores the elements in order with respect to the keys, Whenever we need to access a variable's value, we just need to look up its address on the map.
Also, the map in C++ is based on red-black trees which in general are self balanced binary trees.
Let us take a look at the syntax of a map in c++
Syntax
To declare a map in C++, we use the following syntax:
map <key_dataType, value_dataType> mapName;
Here,
- The key_dataType is the data type of the key.
- The value_dataType is the data type of the value.
- mapName is the name of the map.
Note: To declare the map in C++, you need to add a header file containing the template and the functions of the map.
In the C++ Language, the required header for the map data structure is:
Let us now try creating a map to see how we can use it in our codes.
Creating a Map
A map in C++ can be easily created using the header file and the syntax that we discussed above, let us take a look at an example to see how it can be created.
We can create a map to store the roll numbers corresponding to the names of every student in the class.
# include <iostream> // To use the map data structure # include <map> using namespace std; int main () { // Create a map with strings as the key and the integer type as the values // Names of the students will be of the data type string and the roll numbers as the integer types map<string, int > mp; // Assign values to the map mp[ "Asia" ] = 1 ; // Inserts key = "Asia" with value = 1 mp[ "Europe" ] = 2 ; // Inserts key = "Europe" with value = 2 mp[ "Australia" ] = 3 ; // Inserts key = "Australia" with value = 3 mp[ "Antarctica" ] = 4 ; // Inserts key = "Antarctica" with value = 4 // We can retrieve the roll number or the values corresponding to the keys quickly without going through the whole array cout << "The roll number of Antarctica is: " << mp[ "Antarctica" ] << endl; cout << "The roll number of Europe is: " << mp[ "Europe" ] << endl; return 0 ; }
Output
The roll number of Antarctica is: 4 The roll number of Europe is: 2
In the above example, we did not have to go through the whole array to find the student with the name "Antarctica" or "Europe", we just required the key which in this case was the name of the student and the value associated to that key was retrieved quickly, to be accurate the time complexity of the worst case if we had to iterate through the whole array would have been whereas in this case, that is by using the map we have improved it to , where is the number of elements in the array and is the average length of the array.
Member Functions
So far we've learned about how the map works, let us now see how we can make use of the in-built functions of the map in C++ to create our key-value pairs.
For this, we have many predefined member functions, that perform different map operations. We shall look into them one by one and try to understand how they work through examples.
Element Access
| Function Name | Description | Syntax | Time Complexity | Reason |
|---|---|---|---|---|
| operator [] | Operator [] is used to retrieve the element / value associated with the given key | map_name[key_name] | O( log(N) ) | Adding a new element in a self balanced bianry tree takes logarthimic time (O(log(N))) |
| at | at is used to retrieve the element/value associated with the given key | map_name.at(key_name) | O( log(N) ) | Adding a new element in a self balanced binary tree takes logarthimic time (O(log(N))) |
Both the functions are operator [] and at are used to access/retrieve the element/value associated with the key.
The major difference between the two is that at-will throw an exception if the key-value pair is not present in the map whereas the operator [] will insert a key-value pair if the key is not present in the map.
Example: To understand this better.
# include <iostream> # include <map> using namespace std; int main () { // Creating a map map< int , string> mp; // Assigning values to the keys mp[ 1 ] = "Asia" ; mp[ 2 ] = "Europe" ; mp[ 3 ] = "South America" ; mp[ 4 ] = "North America" ; // Retrieving values using the at operator. // Prints the value associated with the key 1 , i.e. Aisa cout << mp. at ( 1 ) << endl; // Retrieving values using the operator [] . // Prints the value associated with the key 3 , i.e. South America cout << mp[ 3 ] << endl; // Chaning values using the at operator. // Changes the value associated with key 1 to Asia-India. mp. at ( 1 ) = "Asia-India" ; // Prints the value associated with the key 2 , i.e. Asia-India using the operator []. cout << mp[ 1 ] << endl; // Since there is no key with value 5 in the map, it will create a key with value 5. mp[ 5 ] = "Australia" ; cout << mp[ 5 ] << endl; // Since there is no key with value 6 in the map, it will throw an exception // mp.at(6) = "Africa"; return 0 ; }
Output
Asia South America Asia-India Australia
In the above code, we create a map with the keys as integers and values as strings and assign the pairs in the map. Then we print and change the values associated with the given key using the at and operator []. The last lines of the code are commented out since uncommenting them will result in an error showcasing the fact that it cannot be used on a key that is not present on the map.
Capacity
| Function Name | Description | Syntax | Time Complexity | Return Type | Reason |
|---|---|---|---|---|---|
| empty | It is used to check if the map is empty or not. It returns true if the map is empty and otherwise False | map_name.empty() | O(1) | Boolean | Need to check the value of the variable which stores the size of the map |
| size | It is used to find the number of elements ( key value pairs ) present in the map | map_name.size() | O(1) | Unsigned Integer | Need to check the value of the variable which stores the size of the map |
| max_size | It is used to find the maximum size of the map that can be possible | map_name.max_size() | O(1) | Unsigned Integer | Need to check the value of the variable which stores the max size of the map |
These functions are used to find the solution to the queries related to the size of the map in general. The empty() function returns a boolean value, if the map is empty that is it does not contain any key-value pair in it, otherwise it returns . The size() function is used to return the number of key-value pairs in the map that is the number of entries in the map, whereas, the max_size() returns the upper bound of the entries that can contain based on the memory that the map has been allocated.
Let us take a look at an example to understand these functions.
# include <iostream> # include <map> using namespace std; int main () { // Creating a map map< int , int > mp; // Check if the map is empty or not if (mp. empty ()) cout << "The map is empty" << endl; else cout << "The map is not empty" << endl; // Find the size of the map cout << "The size of the map is: " << mp. size () << endl; // Assigning values to the keys mp[ 1 ] = 14 ; mp[ 2 ] = 45 ; mp[ 3 ] = 69 ; mp[ 4 ] = 25 ; // Check if the map is empty or not if (mp. empty ()) cout << "The map is empty" << endl; else cout << "The map is not empty" << endl; // Find the size of the map cout << "The size of the map is: " << mp. size () << endl; // Find the maximum size of the map that is possible cout << "The max size of the map is: " << mp. max_size () << endl; return 0 ; }
Output
The map is empty The size of the map is: 0 The map is not empty The size of the map is: 4 The max size of the map is: 230584300921369395
In the above code, we create a map with the keys as integers and values also as integers and then check if the map is empty or not ( the map is empty initially) and print the size of the map ( using the size() ) as well which is 0. We then assign the key-value pairs in the map, due to which the size of the map changes. Then we again check if the map is empty (the map is now not empty) and print the size as well as the maximum size (using the max_size()) that the map can hold up to.
Modifiers
| Function Name | Description | Syntax | Time Complexity | Reason |
|---|---|---|---|---|
| insert | It is used to insert an element in the map | map_name.insert({ key, value }) | O(log(n)) | Adding a new element in a self balanced binary tree takes logarthimic time (O(log(N))) |
| erase | It is used to erase an element in the map using the given key | map_name.erase( key ) | O(log(n)) | Removing an element in a self balanced binary tree takes logarthimic time (O(log(N))) |
| clear | It is used to delete all the elments of the map | map_name.clear() | O(n) | Removing all the elements from a self balanced binary tree takes linear time (O(N)) |
These functions are known as modifiers. They are used to modify the content of the map/maps they're used on. We use the insert() function to insert or add a new key-value pair to the map. The erase function is used to erase the pair with a key value that is passed as the parameter to it whereas the clear() function removes all the key-value pairs from the map.
Note: We can also use the operator [] and at to insert and modify the values of the elements present in the map, but the insert operator will return a pair of iterator and boolean which denotes whether the key-value pair has been inserted that is true otherwise it is already present in the map that is it returns false.
The erase() function works similarly that is if the element is present it will erase the key - value pair otherwise return a pair in which the boolean value is set to false
Let us try to understand better using an example.
# include <iostream> # include <map> using namespace std; int main () { // Creating a map map< int , int > mp; // Assigning values to the keys mp[ 1 ] = 14 ; mp[ 2 ] = 33 ; // Insert in the map using the insert operator mp. insert ({ 3 , 65 }); // Erase an entry from the map using the erase operator mp. erase ( 1 ); // Printing all the key value pairs for ( auto it : mp) cout << "The key is " << it.first << " and the value is " << it.second << endl; // Clear the map mp. clear (); cout << "The size of the map is: " << mp. size () << endl; return 0 ; }
Output
The key is 2 and the value is 33 The key is 3 and the value is 65 The size of the map is: 0
In the above code, we create a map and assign some elements to it. We insert a new key-value pair with the key as 2 and the value as 65. We call the erase() function to remove the element with the key as 1 that is {1,14} gets removed. We then print all the remaining elements. In the end, we delete all the elements from the map using the clear() function.
There are some more modifiers, such as:
| Function Name | Description | Syntax | Time Complexity | Reason |
|---|---|---|---|---|
| swap | It is used to swap the contents of two different maps. | swap( map_name1, map_name2 ) | O(1) | Swapping the content of two maps require to change the address location of both maps which take constant time O(1) |
| emplace | It us used to insert new element (key value pair) | map_name.emplace( key, value ) | O(log(n)) | Adding a new element in a self balanced binary tree takes logarithmic time (O(log(N))) |
| emplace_hint | It is used to insert new element (key value pair) using the hint (position) in the map | map_name.emplace_hint( position, key, element ) | O(log(n)) | Adding a new element in a self balanced binary tree takes logarithmic time (O(log(N))) |
These functions are also known as advanced modifiers. The swap() function is used to swap the content of the two maps that are passed to it as the parameters. The emplace() function is used to insert a key-value pair in the map, If the key is being repeated then it will only store the first key-value pair of a specified key ( which is being repeated ). The emplace_hint() works exactly like the emplace() but at times it is faster than emplace() since it provides a hint which basically works as a starting position after which it searches for the correct position where it is required to be inserted.
Iterators
Before we move on to what iterators are there in the map class let us have a recap of what iterators are in C++.
Iterators are provided by the C++ STL to make traversing the STL containers more efficient. The memory address of the elements contained in the container is returned by these iterators. The iterators may be used to conduct a variety of pre-defined tasks in STL. This also reduces the time complexity of the program.
| Function Name | Description | Syntax | Time Complexity |
|---|---|---|---|
| begin | It returns an iterator pointing to the first element of the map. | map_name.begin() | O(1) |
| end | It returns an iterator pointing to the last element of the map. | map_name.end() | O(1) |
| rbegin | It returns a reverse iterator pointing to the last element of the map. | map_name.rbegin() | O(1) |
| rend | It returns a reverse iterator pointing to the first element of the map. | map_name.rend() | O(1) |
| cbegin | It returns a constant iterator pointing to the first element of the map. | map_name.cbegin() | O(1) |
| cend | It returns a constant iterator pointing to the last element of the map. | map_name.cend() | O(1) |
| crbegin | It returns a reverse constant iterator pointing to the last element of the map. | map_name.crbegin() | O(1) |
| crend | It returns a reverse constant iterator pointing to the first element of the map. | map_name.crend() | O(1) |
Note: All of the above function return iterators, that is, pointers pointing to an element of the cointainer map.
These functions are used to return iterators pointing to the first or the last element ( key value pair ) of the map.
The begin() and the end() are used to return the iterator pointing to the first and last element ( key-value pair ) of the map. Now the r in rbegin() and rend() stands for reverse, similary c stands for constant that the value they are pointing to doesnot change using them. Similarly, the cr in crbegin() and crend() stands for constant reverse begin and constant reverse end which are combinations of constant and reverse iterators.
# include <iostream> # include <map> using namespace std; int main () { // Creating a map map< int , int > mp; // Create an iterator for the map map< int , int > :: iterator it ; // Assigning values to the keys mp[ 1 ] = 14 ; mp[ 2 ] = 45 ; mp[ 3 ] = 69 ; mp[ 4 ] = 25 ; // Printing the first element it = mp. begin (); cout << "The key is " << it->first << " and the value is " << it->second << endl; // Printing the last element it = mp. end (); // Note: mp.end() points to the next place after the last element so we need to decrease it by one place --it; cout << "The key is " << it->first << " and the value is " << it->second << endl; // Printing all elements in the reverse order using rbegin and rend cout << "Elements in Reverse Order are:" << endl; for ( auto itr = mp. rbegin (); itr != mp. rend (); itr++) { cout << "The key is " << itr->first << " and the value is " << itr->second << endl; } return 0 ; }
Output
The key is 1 and the value is 14 The key is 4 and the value is 25 Elements in Reverse Order are: The key is 4 and the value is 25 The key is 3 and the value is 69 The key is 2 and the value is 45 The key is 1 and the value is 14
In the above code, we declare an iterator for the map and then assign that iterator to the beginning of the map using the function mp.begin() and print the key-value pair it is pointing towards. Similarly, we, later on, assign that iterator to the end of the map using the mp.end(), here however we have to decrease it by one place since mp.end() points to one place more than the last element, we then print the value it is pointing towards. rbegin() and rend() can be similarly used as shown in the above code, we iterate the iterator itr through the map starting from rbegin() up till rend() printing all the key-value pairs between them.
Searching and Counting
| Function Name | Description | Syntax | Time Complexity | Return Type | Reason |
|---|---|---|---|---|---|
| find | It searches for a given key-value pair using the key. It returns the iterator pointing to that element if the element is present otherwise returns an iterator equal to the end iterator of the map. | map_name.find(key) | O( log n ) | Iterator | It works on the principle of balanced binary search tree that os in worst case it will take time equivalent ot height of the tree that is O( log(n) ) |
| count | It returns the number of key-value pairs matching the given key. | map_name.count(key k) | O( log n ) | Integer | It works on the principle of balanced binary search tree that os in worst case it will take time equivalent ot height of the tree that is O( log(n) ) |
| lower_bound | It returns an iterator pointing to the lower bound of the key that is passed to it. | map_name.lower_bound(key) | O( log n ) | Iterator | It works on the principle of balanced binary search tree that os in worst case it will take time equivalent ot height of the tree that is O( log(n) ) |
| upper_bound | It returns an iterator pointing to the upper bound of the key that is passed to it. | map_name.upper_bound(key) | O( log n ) | Iterator | It works on the principle of balanced binary search tree that is the worst case it will take time equivalent of the height of the tree that is O( log(n) |
| equal_range | It returns the range of key-value pairs matching with a given key passed to it, in other words, returns a pair of iterators pointing to the lower bound and upper bound of the given key. | map_name.equal_range(key) | O( log n ) | Pair of Iterator | It finds the lower bound and upper bound and then combines both the answers that is it takes O( log(n) ) |
The above functions are used for searching and counting a given key. The find() function is used to find and return the iterator pointing to the address of the key-value pair matching the given key. Similarly, the count function returns the number of occurrences of the key-value pair matching the given key. The lower_bound() is a concept from binary search which return the iterator pointing to the first occurrence of a key-value pair matching the given key, similar to lower_bound(), the upper_bound() returns the iterator pointing to the key-value pair just after the matching value of the given key. The last function that is equal_range() returns a pair of iterators containing the iterators of the lower bound and upper bound of the given key.
Let us understand these functions better using an example.
# include <iostream> # include <map> using namespace std; int main () { // Creating a map map< int , int > mp; // Assigning values to the keys mp[ 3 ] = 54 ; mp[ 7 ] = 63 ; mp[ 6 ] = 16 ; mp[ 8 ] = 60 ; // Check if an element is present or not if (mp. find ( 3 ) != mp. end ()) cout << "The element with key " << 3 << " is present in the map" << endl; // Count the number of occurence of the key 5 cout << "The occurrence of the key " << 5 << " is " << mp. count ( 5 ) << endl; // Find the lower bound for key 6 auto it1 = mp. lower_bound ( 6 ); cout << "The key is " << it1->first << " and the value is " << it1->second << endl; // Find the upper bound for key 6 auto it2 = mp. upper_bound ( 6 ); cout << "The key is " << it2->first << " and the value is " << it2->second << endl; // Find the equal range for key 6 auto it3 = mp. equal_range ( 6 ); cout << "The lower bound for key 6 is " << it3.first->second << " and the upper bound for key 6 is " << it3.second->second << endl; return 0 ; }
Output
The element with key 3 is present in the map The occurrence of the key 5 is 0 The key is 6 and the value is 16 The key is 7 and the value is 63 The lower bound for key 6 is 16 and the upper bound for key 6 is 63
In the above code, we create a map and assign the key-value pairs to it. Using the find() function we find if the element with the key 6 is present or not, similarly using the count() function we check how many occurrences of key 5 are present on the map. Using the lower_bound() and upper_bound() we get the iterator pointing towards the lower bound and upper bound element with the key 6, similarly, we can also use the equal_range() function to get the lower and upper bound of the element with key 6.
Why Use std::map?
There are many reasons to use a map, some of them are:
- The map in C++ stores only unique keys in sorted order based on the default or chosen sorting criteria.
- The map in C++ is fast, easy to use, and able to search for elements using a key.
- Only one element is attached to each key in the map.
- The map in C++ is implementable using the balanced binary trees.
There are many more reasons to use the Map data structure in C++ but let us also look at some reasons to not use the Map in C++.
When Not to Use a Map in C++?
A map in C++ is a very useful data structure, especially when it comes to fast lookups based on a key, a map can provide the data element associated with a particular key very quickly. But, if in your code you want to iterate over all elements, or perform some operation that requires traversing over all pairs, a map may not be the best choice.
We cannot access elements in a map like we can access them in a vector or an array using indexes, instead, we have to start with the begin iterator and keep incrementing it until we reach the end of the map. This process can be cumbersome, especially if you have a map of a large size. If in your code you find that you have to iterate through the map to search for a particular element, the map may not be the best data structure for that particular code.
Use a map in C++ when you want fast lookups based on a key value.
Let's take a look at an example to understand this better
# include <iostream> # include <map> using namespace std; int main () { // Creating a map map<string, int > mp; // Assigning values to the keys mp[ "Asia" ] = 1 ; mp[ "Europe" ] = 2 ; mp[ "Australia" ] = 3 ; mp[ "South America" ] = 4 ; mp[ "North America" ] = 5 ; // Finding if there is any key with the value "Antarctica" if (mp. find ( "Antarctica" ) != mp. end ()) cout << "It is present" << endl; else cout << "It is not present" << endl; return 0 ; }
Output
In the above code one might think that the time complexity is where is the numeber of elements present in the map but that would be incorrect the actual time complexity of the above code is where is the average length of all the string as keys and is the number of elements
Does Order Matter in Maps in C++?
We already saw that maps in C++ store elements in the form of key-value pairs. A valid question now is but how are these pairs ordered? Are they ordered in the way they are inserted, just like in a vector or is there some other ordering followed in maps?
The answer to this question is that a map in C++ keeps the key-value pairs in sorted order, to be precise, in increasing order of the key values. This means that the order in which you insert the elements in a map does not matter, as the map internally stores all elements in sorted order. This is done to provide a quick lookup operation for any key value.
If you don't want the elements to be ordered in a sorted manner, or if your code doesn't require ordering the elements sorted according to the key values, you can consider using an unordered map in C++.
An unordered map in C++, as suggested by the name, is similar to a map except that it doesn't order the pairs in any particular order, and hence results in a better insertion and access time than a normal map.
Storing a Map in a Map in C++?
You can store a map inside a map. Usually, when we have both the key and value as integers we declare a map as
If we want the value to be another map, we can declare it as
This means that now we have a map where the key is an integer while the value elements will be another map that can store integer key-value pairs. You can modify the map according to your program needs and even have a vector or map inside a map.
For example, we can have something like:
map<vector< int >,map< int , int >> mp;
or something like
map<set< int >,string>> mp;
Let us take a look at an example to understand this concept better.
# include <iostream> # include <map> using namespace std; int main () { //create map inside a map map< int , map< int , int >>mp; //assign values to the map elements for ( int i = 1 ; i <= 4 ; i++) { for ( int j = 1 ; j <= 4 ; j++) { //mp[i][j] refers to the key for the first map being i and the second key being j mp[i][j] = i * j; } } //access values just like in ordinary map using the [] operator twice cout << mp[ 1 ][ 2 ] << endl; cout << mp[ 2 ][ 3 ] << endl; //you can also access the map corresponding to a given first key for ( auto it : mp[ 1 ]) { cout << it.second << " " ; } return 0 ; }
Output
In the above code, we have created a map inside a map, i.e. for each key in the map the corresponding value element is also a map. To access the values we can use the [] operator as usual, but keep in mind that this time we have a map inside a map. So, to access the map stored with the key i, we can use mp[i], while if we want to access the value of the key j in the map stored in key i, we use mp[i][j].
Conclusion
- Maps in C++ are container structures that store elements in sorted key-value pairs. Each key is unique.
- A map in C++ has the following inbuilt functions:
- Access -
- Operator []
- at()
- Capacity -
- empty()
- size()
- max_size()
- Modifiers
- insert()
- erase()
- clear()
- swap()
- emplace()
- emplace_hint()
- Iterators
- begin()
- end()
- rbegin()
- rend()
- cbegin()
- cend()
- crbegin()
- crend()
- Searching and Counting
- find()
- count()
- lower_bound()
- upper_bound()
- equal_range()
- Access -
- Map in C++ helps makes searching elements faster since it is based on red - black trees and is easy to use.
- It can be cumbersome to iterate the map and may even require more time if the size of the map is big, do don't use a map in C++ if you have to iterate through the map to search for an element.
Source: https://www.scaler.com/topics/cpp/map-in-cpp/
0 Response to "C Map Does Key Need to Be Continuous"
Post a Comment