Some summaries of the map container in the STL

I. introduction to map

Map is a container of STL, and like set, map is an associative container. It provides one-to-one (where the first keyword can be called a keyword, each keyword can only appear once in the map, and the second keyword can be called a value for that keyword) data processing capability, which helps us to process one-to-one data due to this feature. Here is the organization of the internal data of the map. The internal map is a self-built red-black tree (a balanced binary tree in a non-strict sense), which has the function of automatically sorting the data, so all the data inside the map is in order. To learn map we have to understand what is one-to-one data mapping? For example, in a class, there is a one-to-one mapping relationship between each student's student number and his name. This model may be easily described by map. Obviously, the student number is described by int and the name is described by string < Int, string > Student;

Here's the difference between a map and a set container.

For each node in the map, a pair of information is stored, including a key and a value, and key values cannot be repeated between nodes.

Each node in a set stores one piece of information, with only one key, but each key value is unique. Set represents the concept of a set.

For the learning of map, or containers in STL, it is the key to know the implementation principle of each container and what problems each container is suitable to solve

2. Commonly used operations in map

2.1 constructors in map

map(); //Default constructor
map(const map& m) //Copy constructor
map(iterator begin, iterator end ); //Interval constructor
map(iterator begin, iterator end, const traits& _compare) //Constructor with comparison predicate
map(iterator begin, iterator end, const traits& _compare, const allocator& all) //With distributor

After analysis, we found that the constructor of map mainly calls the "copy constructor" and initializes with the "iterator". I think the reason is simple, because each node in the map consists of a pair of values. Do I still have to write a program to demonstrate the map constructor?

2.2 some of the basic functions in the map
Begin, end, rbegin, rend, empty, clear, size, max_size. Eight commonly used functions, see the name should know how to use it, look at the code:

#pragma warning (disable:4786)
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
    map<int,string> studentMessage;
    map<int,string>::iterator iter;
    studentMessage.insert(pair<int , string>(54090101,"Mike"));
    studentMessage.insert(pair<int , string>(54090102,"Sam"));
    studentMessage.insert(pair<int , string>(54090103,"Jake"));
    //Begin gets the iterator for the first element in the map and is equal to rend
    //End gets the iterator at the next location of the last element in the map and is equal to rbegin
    cout<<" The elements in the iterator are as follows: "<<endl;
    for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)
    {
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    //Look at the value of max_size and size
    cout<<"map  the  max_size  Value: "<<studentMessage.max_size()<<endl;
    cout<<"map  the  size  Value: "<<studentMessage.size()<<endl;
    //Look at the use of empty and clear
    studentMessage.clear();
    if(studentMessage.empty())
    {
        cout<<"The map is Empty !!"<<endl;
    }
    else
    {
        cout<<"The map is not Empty !!"<<endl;
    }
    return 0;
}

Operation results:

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/20130924093831.png ">

2.3 find elements in the map

Map is used to find the function in the find, but to complete the function of lookup and more than this one, also can search such as count, because the keys in the map is not allowed to repeat, so a key value can only appear once, that means the count returned value can only be 0 or 1, so obviously it can find the completed, but the count to do find is not the optimal choice, because the original intention is to use the count to complete count, in the sequential containers, such as vector is very useful, The reason for the count function in the map is to provide a uniform interface for STL, so the upper_bound, lower_bound, equel_range and other functions in the map can be combined to do the lookup function (think about how to do it). Here's a question: are count and find consistent in the efficiency of completion?

Let's look at the use of find and count to find:

#pragma warning (disable:4786)
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
    map<int,string> studentMessage;
    studentMessage.insert(map<int,string>::value_type(54090101,"Mike"));
    studentMessage.insert(map<int,string>::value_type(54090102,"Sam"));
    studentMessage.insert(map<int,string>::value_type(54090103,"Jake"));
    if(studentMessage.find(54090101) != studentMessage.end())
    {
        cout<<"find success !!"<<endl;
    }
    if(studentMessage.count(54090101))
    {
        cout<<"count success !!"<<endl;
    }
    return 0;
}

Operation results:
The find success!!!!!
The count success!!!!!

See, there's a difference between count and find, which is that count simply looks for the presence of an element, and find looks for the location of the element to look for. There is a point to note that the search parameter is the key value oh!!

2.4 insertion and deletion of data in map

Insert and delete are very important operations for any container. First, there are three ways to insert data in map. The first one is insert (pair) < T1, T2, > (key1, value1)). The second type: insert(map) < T1, T2 > ::value_type(key1,value1)), this insertion is basically similar to the first one. The third way is to insert an array, which will be demonstrated in a program later.

There are roughly three ways to delete data: the first is to erase (map) < T1, T2 > ::iterator iter) to delete the node referred to by the iterator. The second: erase (key k), which is deleted based on the key value, and the node referred to by the key value k is deleted. Type 3: erase (map) < T1, T2 > : : iteratormap iter1, < T1, T2 > ::iteratoriter2), delete the data between iter1 and iter2.

#pragma warning(disable:4786)
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
    
    map<int,string> studentMessage;
    map<int,string>::iterator iter;
    //Insert data into the map
    studentMessage.insert(pair<int,string>(54090101,"Mike"));
    studentMessage.insert(pair<int,string>(54090101,"MIKE"));//Repeated injection
    studentMessage.insert(map<int,string>::value_type(54090102,"Sam"));
    studentMessage.insert(map<int,string>::value_type(54090102,"SAM"));//Repeated injection
    studentMessage[54090103] = "Jake";
    studentMessage[54090103] = "JAKE";//Repeated injection
    //To test the deletion, insert two data first, see the insert result and mainly look at the insert mode above
    studentMessage[54090104] = "Bob";
    studentMessage[54090105] = "Ben";
    cout<<" After insertion map Data in: "<<endl;
    for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)
    {
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    //Delete data from the map
    iter = studentMessage.begin();
    studentMessage.erase(iter);
    cout<<" Delete with iterator map The first element in: "<<endl;
    for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)
    {
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    studentMessage.erase(54090102);
    cout<<" Delete using key values map The first element in: "<<endl;
    for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)
    {
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    studentMessage.erase(studentMessage.begin(),studentMessage.end());
    cout<<" Remove with scope iterator map All data in: "<<endl;
    for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)
    {
        cout<<iter->first<<" "<<iter->second<<endl;
    }
    return 0;
}

Operation results:

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/20130924093847.png ">

Note: By observing the output result, the data is overwritten by inserting into the array, while the other two methods of insertion are not overwritten, which is actually an insertion failure. Also notice that the subscript of inserting into the array is actually the key value.

2.5 some other commonly used functions or operators

Such as swap and key_comp, and the operator: ==,! =, < . < =, > . > =, etc. For the == operator, two maps are equal only if all the elements in the two maps are exactly the same, and < . < =, > . > = it is the first different element of the two maps that determines, similar to STRCMP in the string library. I won't say much about these things.