[C++] The use and underlying principles of map, set, multiset and multimap [Full version]

Table of Contents

1. The use of map and set

1. Sequential containers and associative containers

2. Explanation on the use of set

3. Explanation on the use of map

2. Multiset and multimap

1. Use of multiset and multimap

2. OJ question: top k high-frequency words

---

1. The use of map and set

1. Serial containers and associative containers

Sequential container: vector/list/string/deque

Only sequential containers support operations such as push, but associative containers do not.

Associative container: map/set/unordered_map/unordered_set

The underlying implementation of set and map is balanced search binary tree

2. Explanation on the use of set

• set is the key model in the search tree
• Characteristics of set: ①. Inserted data will be automatically sorted. ②. Values are not allowed to be modified in set. ③. Duplicate values are not allowed in set. Even if they exist, only one will be left.
• Set traversal: ①, iterator traversal ②, range for traversal (because iterator traversal is supported, range for must be supported)
• Copy construction of set
• The insertion of set is only insert, it does not have push, pop, etc., because it is an associative container
• set’s find, if find finds it, it will return the iterator of the element being found. If it is not found, it returns end(), so you should check whether it is found.
• What is the difference between set’s find and the find provided in the library?
• Both can be searched, the difference lies in efficiency
• set searches a binary tree: time complexity: O(logN), while the algorithm is O(N)
• The find in the algorithm is a template, and its implementation is so that all containers can use it universally, so set tries to use its own find.
• Deletion of set
• ①, erase (iterator of the position to be deleted) ②, erase (data to be deleted) ③, erase(s.begin(), s.end()) [i.e., iterator head and tail, its effect is equivalent to clear]

Because set is a key model, it depends on whether the information of everyone in China is stored in the set, the maximum number of searches is only 31, because search The efficiency of binary tree: O(logN)2^31 = more than 2 billion, this efficiency is very good

The code is as follows:

void test_set()
{
set<int> s;
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(3);
s.insert(7);

//set: sorting + deduplication
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
+ + it;
}
cout << endl;

//If it supports iterator, it supports range for
for (auto e : s)
{
cout << e << " ";
}
cout << endl;

set<int> copy(s);//deep copy of set
for (auto & e : copy)
{
cout << e << " ";
}
cout << endl;

//auto pos = s.find(3);//Available auto derivation types
//set<int>::iterator pos = s.find(3);//find returns the iterator
find finds the iterator that will return the element, but returns end() if it does not find it.
//if (pos != s.end())
//{//Delete only when found
// s.erase(pos); //erase will delete the data at the iterator position
//}
//If erase directly gives the value, if the value does not exist, no error will be reported, but the iterator must exist at that location

set<int>::iterator pos = find(s.begin(), s.end(), 3);//Use find in the algorithm
if (pos != s.end())
{
s.erase(pos);
}

for (auto & e : s)
{
cout << e << " ";
}
cout << endl;
}

Run results:

3. Explanation on the use of map

• map is the key/value model in the search tree
• Map traversal: ①, iterator traversal ②, range for traversal
• The type of map is pair, andpairis stored >One is of key type, and the other is of value type
• Constructor of map: ①, pair constructor ②, make_pair function template constructs a pair object

void test_map1()
{
map<int, int> m;
//m.insert(1, 1);//Compilation fails
m.insert(pair<int, int>(1, 1));//pair constructor, constructs an anonymous object
m.insert(pair<int, int>(3, 3));
m.insert(pair<int, int>(2, 2));
m.insert(make_pair(4, 4)); //Function template constructs a pair object

map<int, int>::iterator it = m.begin();
while (it != m.end())
{ //*it is equivalent to pair, and you need to access its members
cout << it->first << ":" << it->second << " " << endl;
//You can also use (*it).first (*it).second
//operator* The return value is a reference to the value in the node
//operator->The return value is the pointer to the value in the node, that is, the pair<k,v> pointer
//Essentially for readability, one -> is omitted here
+ + it;
}
cout << endl;

for (auto & e : m)
{//first is the key value, that is, the first value in the pair, second is the value value, that is, the second value in the pair
cout << e.first << ":" << e.second << endl;
}

}

• The difference between the two methods of map constructor

void test_map2()
{
//Generally when writing projects, you will not import everything in the std library, but the following code, make_pair is obviously more concise
std::map<std::string, std::string> dict;
dict.insert(pair<std::string, std::string>("metric", "metric"));
dict.insert(make_pair("potent", "powerful"));
dict.insert(make_pair("deplete", "massive reduction"));


std::map<std::string, std::string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
+ + it;
}
cout << endl;
}

It can be seen that using make_pair will make the code more concise

The following is the application of map: Counting the number of times fruit appears [Essentially it is the application of key/value model]

Method 1: Use map’s find (use key value to find, but not value value)

void test_map3()
{
//How to count the number of times fruits appear using map in STL?
string strs[] = { "watermelon","cherry","apple","watermelon","watermelon","watermelon","watermelon"," apple" };
map<string, int> countMap;
for (auto & str : strs)
{
map<string, int>::iterator ret = countMap.find(str);
if (ret != countMap.end())
{
ret->second + + ;//Equivalent to value + +
}
else
{
//The first time it appears, directly insert value 1
countMap.insert(make_pair(str, 1));
}
}

for (auto & e : countMap)
{
cout << e.first << ":" << e.second << endl;
}
}

Method 2, map operator[ ] solution

The containers we learned before only have operator[] for string, vector and deque, but the operator[] of map here is different.

The following is the bottom layer of operator[ ]

It can be seen that operator[] is given a key value and it returns a reference to the corresponding value

Then you can use operator[ ] to further optimize the code for finding the number of times fruit appears.

void test_map3()
{
//How to count the number of times fruits appear using map in STL?
string strs[] = { "watermelon","cherry","apple","watermelon","watermelon","watermelon","watermelon"," apple" };
map<string, int> countMap;
for (auto & str : strs)
{
//Method 2, operator[] implementation
countMap[str] + + ;//Give key value: string, return reference to corresponding value: number of times
}

for (auto & e : countMap)
{
cout << e.first << ":" << e.second << endl;
}
}

Method 3: Map insert solution

The bottom layer of operator[ ] is implemented by calling insert, so if you want to understand operator[ ], you must first understand insert

One version of insert is

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

Itsreturn value means:

Single-element version: (1) Returns pair, whose member pair::first is set to an iterator that points to the newly inserted element or an element with an equivalent key in the map. The second element of pair:: is set to true if a new element is inserted, or false if an equivalent key already exists.

Understanding:

insert acts as an insertion for inserting non-existing data, first of pair points to the newly inserted element, second is set to true, but if inserting an existing data, insert acts as a search, and pair is first Points to the element that existed before, second is set to false

Using the characteristics of this version of insert, we can write another version of insert based on the number of times the fruit appears.

void test_map3()
{
//How to count the number of times fruits appear using map in STL?
string strs[] = { "watermelon","cherry","apple","watermelon","watermelon","watermelon","watermelon"," apple" };
map<string, int> countMap;
for (auto & str : strs)
{
//Method 3, insert implementation
pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
//It can also be written as auto ret = countMap.insert(make_pair(str, 1));
//If the insertion is successful, it means that it has not appeared in the map before, and the value is 1.
if (ret.second == false)
{//Insertion failed, indicating that this data existed before, and the iterator points to the element that appeared before
ret.first->second + + ;//Use an iterator to access the value of this element
}
}

for (auto & e : countMap)
{
cout << e.first << ":" << e.second << endl;
}
}

How does insert implement map’s operator[]?

• If the fruit is not in the map, [ ] will insert insert pair which is equivalent to pair, then the reference to the returned mapping object (number of times) is + + 1
• If the fruit is in the map, then operator[ ] returns a reference to the mapping object (number of times) corresponding to the fruit, and it + +

The following explains the various functions of map’s operator[ ]

void test_map3()
{
//How to count the number of times fruits appear using map in STL?
string strs[] = { "watermelon","cherry","apple","watermelon","watermelon","watermelon","watermelon"," apple" };
map<string, int> countMap;
for (auto & str : strs)
{
//Method 2, operator[] implementation
countMap[str] + + ;//Give key value: string, return reference to corresponding value: number of times
}

countMap["banana"]; //Insert because it appears for the first time
countMap["banana"] = 1; //Modify, because operator[] returns a reference to value, so it can be modified
cout << countMap["Banana"] << endl;//Search, because banana already exists
countMap["Hamimelon"] = 5; //Insert + Modify, Hamimelon appears for the first time, and its value is modified

map<string, string> dict;
dict.insert(make_pair("sort", "sort"));
dict["string"];//key is string, value is the constructor of string type [because it is the default value], that is, empty string //Insertion (generally not used this way)
dict["string"] = "string";//Returns a reference to value, which can be modified. It can be modified because it returns a reference to value //Modification does not count as insertion because it already exists
dict["left"] = "left";//Insert + Modify, because "left" appears for the first time, so it is inserted, and its value is modified after insertion.
\t
for (auto & e : countMap)
{
cout << e.first << ":" << e.second << endl;
}
}

Note: Passing parameters can only pass key, not just value but not key, because the bottom layer is a search tree, and the search tree needs to use the key to compare the size. As long as the key is entered It cannot be modified

Generally useoperator[] to

• Insert + Modify
• Revise

Generally, you don’t use it to search, because if the key is not there, data will be inserted

Summary:

Second, multiset and multimap

1. The use of multiset and multimap

There is no difference between multiset and multimap except that they support the recurrence of data on the basis of set and map

void test_multi()
{
//The difference from set is that key value key redundancy (duplication) is allowed
multiset<int> ms;
ms.insert(3);
ms.insert(2);
ms.insert(3);
ms.insert(1);
ms.insert(4);
ms.insert(5);

for (auto e : ms)
{
cout << e << " ";
}
cout << endl;

auto pos = ms.find(3);
cout << *pos << endl;
+ + pos;
cout << *pos << endl;
+ + pos;

//The difference between multi_map and map is the same as the difference between set and multi_set
//An additional difference is that muti_map does not have operator[], because when there are multiple identical ones, it is not known which key corresponds to the value returned.
multimap<string, int> mm;
mm.insert(make_pair("Apple", 1));
mm.insert(make_pair("Apple", 1));
mm.insert(make_pair("Apple", 3));
mm.insert(make_pair("Watermelon", 2));
mm.insert(make_pair("Watermelon", 1));

 }

2. OJ question: top k high-frequency words

Ideas:

① First create a map object, and use operator[ ] to sort the strings in it (it will be sorted according to ASCII code), then Key value should be string, because map is sorted according to key value from low to high

②. Because the ones with the highest frequency appear first and there are duplicate data, use multimap and functor

Insert the data in countMap into multimap. The key value of multimap is of type int, which is equivalent to Multimap is sorted by frequency of occurrence. Those with higher frequency of occurrence will be first. Those with the same frequency of occurrence have been sorted by operator[ ] before. Those that appear in dictionary order are smaller ASCII code first

③. Because vector is returned, only the string in multimap is stored in the result, and its string< strong>That is, the iterator position->second

class Solution {
public:
vector<string> topKFrequent(vector<string> & amp; words, int k) {
map<string, int> countMap;
//Count how many times each string appears
for (auto & e : words)
{
countMap[e] + + ;//map will automatically sort the key values, that is, sort the strings, and modify the corresponding value values
}
//But now we need to sort the value values, that is, sort the ints, because we need to find the ones with high frequency.
\t\t
//Method 1. Put the pair<string, int> key-value pairs into the vector, sort them with sort, and write a
//Functions that compare by int, because sort is implemented by quick sort, which is unstable. After sorting, you still need to sort the items with the same number of times by letters, and store them in vector.
//sort is only used by containers that support random access, such as vector and deque

//Method 2, use multimap to sort by number, and use functors to control the sorting from large to small
multimap<int, string,greater<int>> sortMap;//multimap can ensure the recurrence of data
for (auto & amp; kv : countMap)
{
sortMap.insert(make_pair(kv.second, kv.first));//After sorting, insert it into the multimap, which will be sorted from large to small according to int
//After finishing
//Things with a higher number of occurrences are in front, and those with the same number of occurrences have been sorted by string using operator[] before.
}

vector<string> v;
auto it = sortMap.begin();
while (it != sortMap.end())
{
if(k==0)
break;
v.push_back(it->second);//Insert string
+ + it;
--k;//After inserting one--
}

return v;
}
};

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 54743 people are learning the system