STL associative container overview

Reference link

Associative container

While storing the element value, the associated container will be equipped with an additional value for each element (also known as "key", which is essentially an element of C + + basic data type or user-defined type). Its function is to find the target element directly through the key if the key value of the target element is known in the process of using the associated container, Instead of traversing the entire container.

The elements stored in associative containers are "key value pairs" (< key, value >), which is the biggest difference from sequential containers. In addition, the elements stored in sequential containers are not sorted by default, while the elements stored in associative containers are sorted in ascending order according to the size of the key value of each element by default.

When implementing this type of container in STL standard library, the bottom layer selects the data structure of "red black tree" to organize and store each key value pair.

Associative container namecharacteristic
mapDefined in the < Map > header file, the key of each element of the data stored in the container must be unique (i.e. cannot be repeated). The container will sort in ascending order by default according to the size of the key of each element (call STD:: less < T >).
setDefined in the < set > header file, using the data stored in the container, the keys and values of each element are exactly the same, and the values of each element cannot be repeated (ensuring the uniqueness of each element key). The container will automatically sort in ascending order according to the size of each element's key (in fact, the element value) (call STD:: less < T >).
multimapDefined in the < Map > header file, the only difference from the map container is that the keys for storing elements in the multimap container can be repeated.
multisetDefined in the < set > header file, the only difference from the set container is that the values of the elements stored in the multiset container can be repeated (once the values are repeated, it means that the keys are also repeated).
#include <iostream>
#Include < Map > / / to use the map container, you must import the header file
#include <string>
using namespace std;
int main()
{
    //Create an empty map relational container that stores key value pairs, where the key is a string and the value is also a string type
    map<string, string> mymap;
    //Add data to the mymap container
    mymap["http://c.biancheng. Net / C / "] =" C language tutorial ";
    mymap["http://c.biancheng. Net / Python / "] =" Python tutorial ";
    mymap["http://c.biancheng. Net / Java / "] =" java tutorial ";
    //Use the iterator of the map container to traverse the mymap container and output each key value pair stored in it
    for (map<string, string>::iterator it = mymap.begin(); it != mymap.end(); ++it) {
        //Output the keys and values in each element
        cout << it->first << " => " << it->second << '\n';
    }
    return 0;
}

pair usage

Associative containers store data in the form of "key value pairs".

Considering that the "key value pair" is not ordinary type data, the C++ STL standard library provides a pair class template, which is specially used to create two ordinary elements first and second (which can be C + + basic data type, structure and class self-defined type) into a new element < first, second >.

The pair class template is defined in the < utility > header file, so you need to import this header file before using this class template.

#1) The default constructor is to create an empty pair object
pair();
#2) Directly initialize the pair object with 2 elements
pair (const first_type& a, const second_type& b);
#3) Copy (copy) constructor, that is, create a new pair object with the help of another pair object
template<class U, class V> pair (const pair<U,V>& pr);

#4) Move constructor
template<class U, class V> pair (pair<U,V>&& pr);
#5) Use the right value reference parameter to create a pair object
template<class U, class V> pair (U&& a, V&& b);
#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {
    // Call constructor 1, which is the default constructor
    pair <string, double> pair1;
    // Call the second constructor
    pair <string, string> pair2("STL course","http://c.biancheng.net/stl/");  
    // Call copy constructor
    pair <string, string> pair3(pair2);
    //Call the move constructor
    pair <string, string> pair4(make_pair("C++course", "http://c.biancheng.net/cplus/"));
    // Call the 5th constructor
    pair <string, string> pair5(string("Python course"), string("http://c.biancheng.net/python/"));  
   
    cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    cout << "pair2: "<< pair2.first << " " << pair2.second << endl;
    cout << "pair3: " << pair3.first << " " << pair3.second << endl;
    cout << "pair4: " << pair4.first << " " << pair4.second << endl;
    cout << "pair5: " << pair5.first << " " << pair5.second << endl;
    return 0;
}

The above program called make when creating pair4 object_ pair() function, which is also provided by < utility > header file. Its function is to generate a pair object. So when we make_ When the return value of the pair() function (which is a temporary object) is passed as a parameter to the pair() constructor, it calls the move constructor instead of the copy constructor. The creation process of pair4 object in the above program can also be written in the following forms, which are completely equivalent:

pair <string, string> pair4 = make_pair("C++course", "http://c.biancheng.net/cplus/");
cout << "pair4: " << pair4.first << " " << pair4.second << endl;

Manually assign a value to the pair1 object

pair1.first = "Java course";
pair1.second = "http://c.biancheng.net/java/";
cout << "new pair1: " << pair1.first << " " << pair1.second << endl;

The < utility > header file not only provides the method of creating pair objects, but also overloads <, < =, >, > =, = == The operation rule of these 6 operators is: for the two pair objects to be compared, compare pair first The size of the first element. If it is equal, continue to compare pair The size of the second element.

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {
    pair <string, int> pair1("STL course", 20);
    pair <string, int> pair2("C++course", 20);
    pair <string, int> pair3("C++course", 30);
    //pair1 and pair2 have different key s and the same value
    if (pair1 != pair2) {
        cout << "pair != pair2" << endl;
    }
    //pair2 and pair3 have the same key but different value
    if (pair2 != pair3) {
        cout << "pair2 != pair3" << endl;
    }
    return 0;
}

The pair class template also provides a swap() member function, which can exchange the key value pairs of two pair objects. The premise of successful operation is that the key and value types of the two pair objects should be the same.

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {
    pair <string, int> pair1("pair", 10);                   
    pair <string, int> pair2("pair2", 20);
    //Exchange the key value pairs of pair1 and pair2
    pair1.swap(pair2);
    cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    cout << "pair2: " << pair2.first << " " << pair2.second << endl;
    return 0;
}

Keywords: C++

Added by joyser on Fri, 18 Feb 2022 07:05:38 +0200