The use of map, set, multimap and multiset in C++

Use of map, set, multimap, multiset

  • associative container
  • key value pair
  • Tree-structured associative container
  • set
    • set introduction
    • Use of set
      • set definition method
      • set various operation functions
    • multiset
  • map
    • Introduction to map
    • Use of map
      • insert function
      • find function
      • erase function
      • [ ] operator overloading
      • map iterator traversal
    • multimap

Associative container

In the initial stage, we have already come into contact with some containers in STL, such as vector, list, deque, forward_list (C++11), etc. These containers are collectively called sequential containers because their underlying layer is a linear sequence data structure. What is stored inside is the element itself.

Associative containers are also used to store data. Different from sequential containers, they store key-value pairs of structures, which are more efficient than sequential containers during data retrieval.

Key-value pairs

Used to represent a structure with a one-to-one correspondence. This structure generally contains only two member variables, key and value. Key represents the key value, and value represents the information corresponding to the key. For example, if you want to build a dictionary for English-Chinese translation, then there must be English words and their corresponding Chinese meanings in the dictionary. Moreover, there is a one-to-one correspondence between English words and their Chinese meanings. That is, through the English words, in the dictionary You can find its corresponding Chinese meaning.

The definition of key-value pairs in SGI-STL:

template <class T1, class T2>
struct pair
{<!-- -->
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair()
: first(T1())
, second(T2())
{<!-- -->}
pair(const T1 & amp; a, const T2 & amp; b)
: first(a)
, second(b)
{<!-- -->}
};

Tree-structured associative container

Depending on the application scenario, STL implements a total of two different structures of managed containers: tree structure and hash structure. There are four main types of tree-structured associative containers: map, set, multimap, and multiset. What these four types of containers have in common is that they use a balanced search tree (i.e., a red-black tree) as their underlying result, and the elements in the container are an ordered sequence.

set

set introduction

  1. Set is a container that stores elements in a certain order;
  2. In the set, the value of the element also identifies it (value is the key, type is T), and each value must be unique. Elements in a set cannot be modified in the container (elements are always const), but they can be inserted or deleted from the container;
  3. Internally, elements in a set are always ordered according to specific strict weak ordering criteria dictated by their internal comparison object (type comparison);
  4. Set containers are generally slower than unordered_set containers in accessing individual elements by key, but they allow direct iteration of subsets based on order;
  5. Set is implemented using a binary search tree (red-black tree) at the bottom level.

Note:

  • Different from map/multimap, map/multimap stores real key-value pairs
  • value>, only value is placed in the set, but what is actually stored at the bottom is the key-value pair composed of ;
  • When inserting an element into a set, you only need to insert the value, and there is no need to construct a key-value pair;
  • Elements in set cannot be repeated (so set can be used for deduplication);
  • Using the iterator of set to traverse the elements in the set, you can get an ordered sequence;
  • By default, elements in a set are compared based on less than;
  • To find an element in set, the time complexity is: logN;
  • The elements in the set are not allowed to be modified;
  • The bottom layer in the set is implemented using a binary search tree (red-black tree);

Usage of set

set definition method

Method 1: Construct an empty container of a certain type

set<int> s1; //Construct an empty container of type int

Method 2: Copy and construct a container of a certain set type

set<int> s2(s1); //Copy and construct a copy of the int type s1 container

Method 3: Use an iterator to copy and construct a certain piece of content.

string str("abcdef");
set<char> s3(str.begin(), str.end()); //Construct a copy of a certain range of the string object

Method 4: Construct an empty container of a certain type, and specify the comparison method as greater than.

set < int, greater<int>> s4; //Construct an empty container of type int, and specify the comparison method as greater than

set various operation functions

Ordinary member functions:

Member function Specified function
insert Insert the specified element
erase Delete the specified element
find Find the specified element
size Get the number of elements in the container
empty Determine whether the container is empty
clear Clear the container
swap Exchange data in two containers
count Get the number of elements with the specified element value in the container

Iterator member functions:

Member functions Specified functions
begin Get the forward iterator of the first element in the container
end Get the forward iterator of the next position of the last element in the container
rbegin Get the reverse iterator of the last element in the container
rend Get the reverse iterator of the previous position of the first element in the container

Usage example:

#include<iostream>
#include<set>
using namespace std;

void Test_set1()
{<!-- -->
int a[] = {<!-- --> 1, 2, 1, 6, 3, 8, 5 };
//Sequence + Deduplication
set<int> s1(a, a + sizeof(a) / sizeof(a[0]));//1,2,3,5,6,8
//Reverse order + remove duplicates
set<int, greater<int>> s2(a, a + sizeof(a) / sizeof(a[0]));//8,6,5,3,2,1

set<int>::iterator it = s1.begin();
//Iterator traverse
while (it != s1.end())
{<!-- -->
cout << *it << " ";
it++;
}
cout << endl;
//Range for
for (auto e : s1)
{<!-- -->
cout << e << " ";
}
cout << endl;
//Reverse iterator traversal
set<int>::reverse_iterator rit = s1.rbegin();
while (rit != s1.rend())
{<!-- -->
cout << *rit << " ";
rit++;
}
cout << endl;
\t//delete
//1.Delete directly
s1.erase(3);
//2. Use find to find and delete
set<int>::iterator pos = s1.find(1);
if (pos != s1.end())
{<!-- -->
s1.erase(1);
}
//The number of elements 1
cout << s1.count(2) << endl;//1
//Calculate the number of valid elements
cout << s2.size() << endl;//4
//Swap two set containers
set<int> s3{<!-- --> 1,2,3,4,5 };
s1.swap(s3);
}
int main()
{<!-- -->
Test_set1();
return 0;
}

multiset

The underlying implementation of the multiset container and the set container are the same, both are balanced search trees (red-black trees). Secondly, the interfaces of the member functions provided by the multiset container and the set container are basically the same. The only difference between the multiset container and the set container is , multiset allows key value redundancy, that is, the elements stored in the multiset container can be repeated.

void Test_set2()
{<!-- -->
int a[] = {<!-- --> 2,2,1,1,1,4,4,5,3,6,6};
multiset<int> s(a, a + sizeof(a) / sizeof(a[0]));

for (auto e : s)
{<!-- -->
cout << e << " ";//1 1 1 2 2 3 4 4 5 6 6
}
cout << endl;
//Quantity of 1
cout << s.count(1) << endl;//3
//Delete all 1
s.erase(1);//2 2 3 4 4 5 6 6

//Looking for the first 1 in in-order traversal
auto pos = s.find(2);
if (pos != s.end())
{<!-- -->
s.erase(pos);
}
}
int main()
{<!-- -->
Test_set2();
return 0;
}

What we should pay attention to is that the find function in multiset searches for the first element in the in-order traversal, the erase function deletes all the elements to be deleted, and the count function records the number of this element.

map

Introduction to map

  1. Map is an associative container that stores elements composed of key and value in a specific order (compared by key).
  2. In a map, the key is usually used to sort and uniquely identify elements, while the value stores the content associated with this key. The types of key and value may be different, and inside the map, key and value are bound together through the member type value_type, and their alias is pair:
    typedef pair value_type;
  3. Internally, elements in a map are always sorted by comparison by key.
  4. Accessing individual elements by key value in a map is generally slower than an unordered_map container, but map allows direct iteration of elements according to order (that is, when iterating over elements in a map, an ordered sequence can be obtained).
  5. Map supports subscript accessors, that is, by putting the key in [], you can find the value corresponding to the key.
  6. Maps are usually implemented as binary search trees (more precisely: balanced binary search trees (red-black trees)).

Method 1: Construct an empty container by specifying the key and value types.

map<int, double> m1; //Construct an empty container with a key of type int and a value of type double.

Method 2: Copy and construct a copy of a container of the same type.

map<int, double> m2(m1); //Copy construction key is of int type and value is a copy of the m1 container of double type

Method 3: Use an iterator to copy and construct a certain piece of content.

map<int, double> m3(m2.begin(), m2.end()); //Use iterator copy to construct a copy of a certain range of the m2 container

Method 4: Construct an empty container by specifying the key and value types, and specify the key comparison method as greater than.

map<int, double, greater<int>> m4; //Construct an empty container with key as int type and value as double type. The key comparison method is specified as greater than

Use of map

insert function

The function prototype of map’s insertion function is as follows:

pair<iterator,bool> insert (const value_type & amp; val);

The parameters of the insert function are shown to be of type value_type. In fact, value_type is an alias of the pair type:

typedef pair<const Key, T> value_type;
  1. Construct anonymous objects for insertion
map<string, string> dict;

dict.insert(pair<string, string>("left", "left"));
dict.insert(pair<string, string>("right", "right"));
dict.insert(pair<string, string>("mid", "middle"));
//Range for traversal
for (const auto & e : dict)
{<!-- -->
cout << e.first << ":" << e.second << endl;
}
cout << endl;
//Iterator traverse
auto it = dict.begin();
while (it != dict.end())
{<!-- -->
cout << it->first << ":" << it->second << endl;
it++;
}
  1. Use the nake_pair template function for insertion:

The following make_pair function templates are provided in the library:

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{<!-- -->
return (pair<T1, T2>(x, y));
}

map<string, string> dict;

dict.insert(make_pair("left", "left"));
dict.insert(make_pair("right", "right"));
dict.insert(make_pair("mid", "middle"));
//Range for traversal
for (const auto & e : dict)
{<!-- -->
cout << e.first << ":" << e.second << endl;
}
cout << endl;
//Iterator traverse
auto it = dict.begin();
while (it != dict.end())
{<!-- -->
cout << it->first << ":" << it->second << endl;
it++;
}

return value of insert function

The return value of the insert function is also a pair object. The type of the first member of the pair object is the iterator type of map, and the type of the second member is a bool type. The specific meaning is as follows:

  • If the key value of the element to be inserted does not exist in the map, the insert function is inserted successfully and returns the iterator and true of the inserted element.
  • If the key value of the element to be inserted already exists in the map, the insert function fails to insert and returns the iterator and false of the element whose key value is key in the map.

find function

The function prototype of map’s search function is as follows:

iterator find (const key_type & amp; k);

The search function of map searches the map according to the given key value. If it is found, it returns the iterator of the corresponding element. If it is not found, it returns the forward iterator of the next position of the last element in the container.

map<string, string> dict;

dict.insert(make_pair("left", "left"));
dict.insert(make_pair("right", "right"));
dict.insert(make_pair("mid", "middle"));

map<string, string>::iterator pos = dict.find("left");
if(pos != dict.end())
{<!-- -->
cout << pos->second << endl;//left
}

erase function

The function prototype of map’s delete function is as follows:

//Delete function 1
size_type erase (const key_type & amp; k);
//Delete function 2
void erase(iterator position);

We can either delete the specified element based on the key value or delete the specified element based on the iterator. If the element is deleted based on the key value, the number of elements actually deleted will be returned.

map<string, string> dict;

dict.insert(make_pair("left", "left"));
dict.insert(make_pair("right", "right"));
dict.insert(make_pair("mid", "middle"));

dict.erase("left");

map<string, string>::iterator pos = dict.find("right");
if (pos != dict.end())
{<!-- -->
dict.erase("right");
}

[ ]Operator overloading

The [ ] operator overloaded function prototype is as follows:

mapped_type & amp; operator[] (const key_type & amp; k);

The parameter of the [ ] operator overloaded function is a key value, and the return value of this function is as follows:

(*((this->insert(make_pair(k, mapped_type()))).first)).second

In fact, the logic of [ ] operator overloading implementation is actually the following three steps:

  1. Call the insert function to insert key-value pairs;
  2. Take out the iterator obtained by the insert function;
  3. Returns the value of the element at this iterator position.
V & amp; operator[](const K & amp; key)
{<!-- -->
//Call the insert function to insert key-value pairs
pair<iterator, bool> ret = insert(make_pair(key, V());
//Take out the iterator obtained by the insert function and return the element value value at the iterator position
return ret.first->second;
}
  • There is no such key in the map, and a reference to the value is returned; (search + modify)
  • If there is this key in the map, a pair(key, V()) will be inserted and a reference to the value will be returned; (insert + modify)
map<string, string> dict;

dict["left"];
dict["left"] = "left";
dict["right"] = "right";
dict["mid"] = "middle";

for (auto & e : dict)
{<!-- -->
cout << e.first << ":" << e.second << endl;
}

Map iterator traversal

The iterator-related functions in map are as follows:

Member functions Function
begin Get the forward iterator of the first element in the container
end Get the forward iterator of the next position of the last element in the container
rbegin Get the reverse iterator of the last element in the container
rend Get the reverse iterator of the previous position of the first element in the container 
map<string, string> dict;

dict.insert(pair<string, string>("left", "left"));
dict.insert(pair<string, string>("right", "right"));
dict.insert(pair<string, string>("mid", "middle"));
//Range for traversal
for (const auto & e : dict)
{<!-- -->
cout << e.first << ":" << e.second << endl;//left: left mid: middle right: right
}
cout << endl;
//Iterator traverse
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{<!-- -->
cout << it->first << ":" << it->second << endl;//left: left mid: middle right: right
it++;
}
cout << endl;
//Reverse iterator traversal
map<string, string>::reverse_iterator rit = dict.rbegin();
while (rit != dict.rend())
{<!-- -->
cout << rit->first << ":" << rit->second << endl;//right: right mid: middle left: left
rit++;
}

Other member functions of map
In addition to the above member functions, set also has the following commonly used member functions:

Member function Function
size Get the number of elements in the container
empty Determine whether the container is empty
clear Empty the container
swap Exchange the data in the two containers
count Get the number of elements with the specified key value in the container

multimap

The underlying implementation of the multimap container and the map container are the same, both are balanced search trees (red-black trees). Secondly, the interfaces of the member functions provided by the multimap container and the map container are basically the same. The difference between the multimap container and the map container is The difference between multiset containers and set containers is the same. Multimap allows key value redundancy, that is, the elements stored in the multimap container can be repeated.

multimap<string, string> dict;

dict.insert(make_pair("left", "left"));
dict.insert(make_pair("right", "right"));
dict.insert(make_pair("left", "left"));
dict.insert(make_pair("mid", "middle"));

for (auto & e : dict)
{<!-- -->
cout << e.first << ":" << e.second << endl;
//left:left left:left mid:middle right:right
}
cout << endl;

//Number of occurrences of left
cout << dict.count("left") << endl;//2

//Delete all left
dict.erase("left");
for (auto & e : dict)
{<!-- -->
cout << e.first << ":" << e.second << endl;//mid: middle right: right
}

Since multimap containers allow key value redundancy, the meanings of the member functions find and count in the two containers are also different:

Member function find Function
map object The return value is an iterator of the element whose key value is key
multimap object Returns the first key value in the order of the underlying search tree Iterator of the element of key
Member function count Function
map object If the element with the key value key exists, 1 is returned, and if it does not exist, 0 is returned (the find member function can be used instead)
multimap object Return The number of elements whose key value is key (find member function cannot be replaced)

We also need to note that there is no [] operator overloading in multimap, because multimap allows redundant key values, and using [] will cause ambiguity.