map usage details
Map is an associated container of STL. It provides one-to-one data processing capability. Due to this feature, it may provide a fast channel in programming when we process one-to-one data. Let's talk about the organization of data in the map. A red black tree (a balanced binary tree in a non strict sense) is built in the map. This tree has the function of automatic sorting of data, so all data in the map is orderly. Later, we will see the advantages of order.
1. map introduction
map is a kind of relational container (similar to dict in python). Its characteristic is that adding and deleting nodes have little impact on the iterator. Except for the operation node, it has no impact on other nodes.
For iterators, real values can be modified, not key s.
2. Functions of map
The key value correspondence is automatically created. Key and value can be any type you need.
Quickly search records according to the key value. The search complexity is basically Log(N). If there are 1000 records, search 10 times at most, and 1000000 records, search 20 times at most.
Insert key value record quickly.
Quick delete record
Modify the value record according to the Key.
Traverse all records.
3. Use map
Use the header file #include containing the map class of map, and the STL header file has no extension h!
The map object is a template class and requires two template parameters: keyword and storage object:
std:map<int,string> personnel;
This defines an index with int and an associated pointer to string
For ease of use, you can define the type of template class,
typedef map<int,CString> UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumMap;
4. Constructor for map
Map provides 6 constructors in total. This involves memory allocators. Skip the table. We will touch some map construction methods below. What we want to say here is that we usually use the following methods to construct a map:
map<int, string> mapStudent;
5. Data insertion
After constructing the map container, we can insert data into it. Here are three ways to insert data:
The first method: insert pair data with the insert function. The following example is given (although the following code is written casually, it should be compiled under VC and GCC. You can run it to see the effect. Please add this statement under VC to mask the 4786 warning pragma warning (disable:4786))
1. Inserting pair data with insert function
#include
#include
#include
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(3, "student_three"));
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<first<<' '<second<<endl;
}
2. Insert value with insert function_ Type data
#include
#include
#include
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
mapStudent.insert(map<int, string>::value_type (2, "student_two"));
mapStudent.insert(map<int, string>::value_type (3, "student_three"));
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<first<<' '<second<<endl;
}
3. Insert data in array mode
#include
#include
#include
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent[1] = "student_one";
mapStudent[2] = "student_two";
mapStudent[3] = "student_three";
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<first<<' '<second<<endl;
}
Although the above three usages can realize data insertion, they are different. Of course, the first one and the second one are the same in effect. Inserting data with the insert function involves the concept of set uniqueness, that is, when there is this keyword in the map, the insert operation cannot insert data, However, the array method is different. It can overwrite the previous value corresponding to the keyword, which is explained by the program
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
mapStudent.insert(map<int, string>::value_type (1, "student_two"));
After the above two statements are executed, the value corresponding to the keyword 1 in the map is "student_one", and the second statement does not take effect, so this involves how to know whether the insert statement is successfully inserted. You can use pair to obtain whether the insert statement is successful. The procedure is as follows:
pair<map<int, string>::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(map<int, string>::value_type (1,"student_one"));
We know whether the insertion is successful through the second variable of pair. Its first variable returns a map iterator. If the insertion is successful, Insert_Pair.second should be true, otherwise it is false.
The completion code is given below to demonstrate whether the insertion is successful or not
//Verify the effect of the insertion function
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
pair<map<int, string>::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_one"));
if(Insert_Pair.second == true)
cout<<"Insert Successfully"<<endl;
else
cout<<"Insert Failure"<<endl;
Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_two"));
if(Insert_Pair.second == true)
cout<<"Insert Successfully"<<endl;
else
cout<<"Insert Failure"<<endl;
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<<iter->first<<' '<<iter->second<<endl;
}
You can use the following program to see the effect of inserting arrays into data coverage
//Verify the effect of inserting data in array form
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent[1] = "student_one";
mapStudent[1] = "student_two";
mapStudent[2] = "student_three";
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<<iter->first<<' '<<iter->second<<endl;
}
6. Size of map
After inserting data into the map, how do we know how much data has been inserted? You can use the size function. The usage is as follows:
Int nSize = mapStudent.size();
7. Traversal of data
There are also three methods to traverse the map
The first is to apply the forward iterator. The above example is everywhere in the program, and the table is not omitted.
The second: apply the inverse iterator. The following examples are given. To experience the effect, please run the program yourself.
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(3, "student_three"));
map<int, string>::reverse_iterator iter;
for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
cout<<iter->first<<" "<<iter->second<<endl;
}
Third, in the form of array, the program is described as follows:
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(3, "student_three"));
int nSize = mapStudent.size();
for(int nindex = 1; nindex <= nSize; nindex++) //nindex = 1 instead of nindex = 0
cout<<mapStudent[nindex]<<endl;
}
8. Find and get the elements in the map (including determining whether this keyword appears in the map)
Here we will see the benefits of map in ensuring order when inserting data.
There are many methods to determine whether a data (keyword) appears in the map. Although the title here is the search of data, there will be a large number of basic map usages interspersed here.
Here are three data search methods
1. The disadvantage of using the count function to determine whether a keyword appears is that it cannot locate the location where the data appears. Due to the characteristics of map and the one-to-one mapping relationship, the return value of the count function is only two, either 0 or 1. In case of occurrence, of course, 1 is returned
2. The find function is used to locate the location where the data appears. It returns an iterator. When the data appears, it returns the iterator where the data is located. If there is no data to find in the map, the iterator it returns is equal to the iterator returned by the end function.
The find() method is used to find whether a keyword entry is included in the map. The passed parameter is the key to be found. Here, we need to mention the two members of begin() and end(),
Represents the first entry and the last entry in the map object respectively. The type of these two data is iterator
Program description
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(3, "student_three"));
map<int, string>::iterator iter;
iter = mapStudent.find(1);
if(iter != mapStudent.end())
cout<<"Find, the value is "<<iter->second<<endl;
else
cout<<"Do not Find"<<endl;
return 0;
}
The iterator data type obtained through the method of the map object is an std::pair object, including two data types. Iterator - > first and iterator - > second represent keywords and stored data respectively.
3. This method is a little stupid to determine whether the data appears, but I'm going to explain it here
lower_ Usage of the bound function, which is used to return the lower bound (an iterator) of the keyword to be searched
upper_ Usage of bound function, which is used to return the upper bound of the keyword to be searched (an iterator)
For example, if 1, 2, 3 and 4 have been inserted into the map, if lower_ If bound (2), it returns 2, while if upper bound (2), it returns 3
Equal_ The range function returns a pair. The first variable in pair is lower_ The iterator returned by bound. The second iterator in pair is upper_ The iterator returned by bound. If the two iterators are equal, this keyword does not appear in the map,
Program description
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent[1] = "student_one";
mapStudent[3] = "student_three";
mapStudent[5] = "student_five";
map<int, string>::iterator iter;
iter = mapStudent.lower_bound(1); //Returns an iterator with a lower bound of 1
cout<<iter->second<<endl;
iter = mapStudent.lower_bound(2); //Returns the iterator of lower bound 3
cout<<iter->second<<endl;
iter = mapStudent.lower_bound(3); //Returns the iterator of lower bound 3
cout<<iter->second<<endl;
iter = mapStudent.upper_bound(2); //Returns the iterator of upper bound 3
cout<<iter->second<<endl;
iter = mapStudent.upper_bound(3); //Returns the iterator of the upper bound 5
cout<<iter->second<<endl;
pair<map<int, string>::iterator, map<int, string>::iterator> mappair;
mappair = mapStudent.equal_range(2);
if(mappair.first == mappair.second)
cout<<"Do not Find"<<endl;
else
cout<<"Find"<<endl;
mappair = mapStudent.equal_range(3);
if(mappair.first == mappair.second)
cout<<"Do not Find"<<endl;
else
cout<<"Find"<<endl;
return 0;
}
9. Delete element from map
Remove an entry in a map with erase()
The member method is defined as follows:
iterator erase(iterator it);// Delete through an entry object
iterator erase (iterator first, iterator last) / / delete a range
size_ type erase(const Key&key);// Delete by keyword
clear() is equivalent to enummap erase(enumMap.begin(),enumMap. end());
Here we will use the erase function, which has three overloaded functions. Their usage is described in detail in the example below
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(3, "student_three"));
//If you want to demonstrate the output effect, please choose one of the following, and you will see a better effect
//If you want to delete 1, delete it with an iterator
map<int, string>::iterator iter;
iter = mapStudent.find(1);
mapStudent.erase(iter);
//If you want to delete 1, delete with keyword
int n = mapStudent.erase(1);//If deleted, it will return 1, otherwise it will return 0
//Use iterators to delete pieces
//Click the code to clear the entire map
mapStudent.erase( mapStudent.begin(), mapStudent.end() );
//It should be noted that slice deletion is also a characteristic of STL. The deletion interval is a set that is closed before and open after
//Add the traversal code and print it out
}
10. swap usage in map
The swap in map is not the exchange of elements in one container, but the exchange of all elements in two containers.
11. sort problem in sorting · map
The elements in the map are automatically sorted in ascending order by Key, so the sort function cannot be used for the map;
What I want to talk about here is a bit of advanced usage. For the sorting problem, the less than sign is used by default in STL. There is no problem in the sorting of the above codes, because the above keyword is of type int, which itself supports the less than sign operation. In some special cases, for example, the keyword is a structure, which will cause problems when it comes to sorting, Because it has no less than sign operation, functions such as insert cannot pass during compilation. The following two methods are given to solve this problem.
1. Less than overload, program example.
#include <iostream>
#include <string>
#include <map>
using namespace std;
typedef struct tagStudentinfo
{
int niD;
string strName;
bool operator < (tagStudentinfo const& _A) const
{ //This function specifies the sorting strategy, sort by niD, and sort by strName if niD is equal
if(niD < _A.niD) return true;
if(niD == _A.niD)
return strName.compare(_A.strName) < 0;
return false;
}
}Studentinfo, *PStudentinfo; //Student information
int main()
{
int nSize; //Mapping scores with student information
map<Studentinfo, int>mapStudent;
map<Studentinfo, int>::iterator iter;
Studentinfo studentinfo;
studentinfo.niD = 1;
studentinfo.strName = "student_one";
mapStudent.insert(pair<Studentinfo, int>(studentinfo, 90));
studentinfo.niD = 2;
studentinfo.strName = "student_two";
mapStudent.insert(pair<Studentinfo, int>(studentinfo, 80));
for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)
cout<<iter->first.niD<<' '<<iter->first.strName<<' '<<iter->second<<endl;
return 0;
}
2. For the application of imitation function, there is no direct overload of less than sign in the structure at this time. Program description
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef struct tagStudentinfo
{
int niD;
string strName;
}Studentinfo, *PStudentinfo; //Student information
class sort
{
public:
bool operator() (Studentinfo const &_A, Studentinfo const &_B) const
{
if(_A.niD < _B.niD)
return true;
if(_A.niD == _B.niD)
return _A.strName.compare(_B.strName) < 0;
return false;
}
};
int main()
{ //Mapping scores with student information
map<Studentinfo, int, sort>mapStudent;
map<Studentinfo, int>::iterator iter;
Studentinfo studentinfo;
studentinfo.niD = 1;
studentinfo.strName = "student_one";
mapStudent.insert(pair<Studentinfo, int>(studentinfo, 90));
studentinfo.niD = 2;
studentinfo.strName = "student_two";
mapStudent.insert(pair<Studentinfo, int>(studentinfo, 80));
for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)
cout<<iter->first.niD<<' '<<iter->first.strName<<' '<<iter->second<<endl;
}
Since STL is a unified whole, many uses of map are combined with other things in STL. For example, in sorting, the less than sign is used by default, that is, less < >. If you want to sort from large to small, there are many things involved here, which cannot be explained one by one here.
It should also be noted that because the map is internally ordered and guaranteed by the red black tree, the execution time complexity of many functions is log2N. If the map function can be used to realize the function, and the STL Algorithm can also complete the function, it is recommended to use the map function, which is more efficient.
Let's talk about the spatial characteristics of map. Otherwise, it is estimated that you will sometimes be depressed when using it. Because each data of map corresponds to a node on the red black tree, this node occupies 16 bytes when it does not save your data, a parent node pointer and left and right child pointers, There is also an enumeration value (marked red and black, which is equivalent to the balance factor in the balanced binary tree). I think you should know that these places are very memory consuming. Don't say
12. Basic operation functions of map:
C++ maps is an associative container that contains keyword / value pairs:
begin() returns an iterator that points to the map header
clear() deletes all elements
count() returns the number of occurrences of the specified element
empty() returns true if the map is empty
end() returns the iterator that points to the end of the map
equal_range() returns an iterator pair of special entries
erase() deletes an element
find() finds an element
get_allocator() returns the configurator of the map
insert() insert element
key_comp() function that returns the comparison element key
lower_bound() returns the key value > = the first position of the given element
max_size() returns the maximum number of elements that can be accommodated
rbegin() returns an inverse iterator that points to the tail of the map
rend() returns an inverse iterator that points to the map header
size() returns the number of elements in the map
swap() swaps two map s
upper_bound() returns the key value > the first position of a given element
value_comp() returns a function that compares the element value