1. Basic concepts
First of all, let’s understand a concept. The values used for comparison in Set and Map are called keywords, which are usually called keys in use, and there are also values for storing data in other Maps. , called the value, together with the key form a key-value pair (key_value). The reason for this definition is that the bottom layers of both containers use the KV structure to search for a variant of the binary tree — red-black tree.
1.set (set)
Only the key is stored in the set, which can be abstracted like an array, and can store any type of original value and reference, but the stored key is unique, and generally has the following characteristics:
1.set is an array-like object
2. The value stored in set is not repeated
3. All elements of the set will be automatically sorted (searching the characteristics of the binary tree)
4. The value of the set cannot be changed through the iterator
5. The bottom layer uses a red-black tree as a container
2.map (dictionary)
A map is similar to a set, but it stores key-value pairs in the map. The key must be unique, the value can be modified, and it can be automatically sorted by the key. Generally speaking, it has the following characteristics:
1.map stores data in the form of key-value pairs, namely key_value
2. Do not allow duplicate keys
3. All elements are automatically sorted by key
4. The key cannot be modified, but the value can be modified
5. The bottom layer uses a red-black tree as a container
2. Basic usage
1. Use of set
(1) Initialization
int main()
{
set<int> test({2,1,3,3,1,5,4});
for (auto i : test)
{
cout << i << " ";
}
cout << endl;
cout << "size:" << test. size() << endl;
return 0;
}
operation result:
It can be seen that the insertion of set is similar to vector, and the duplicate data is deduplicated and the data is sorted.
(2) insert-insert
int main()
{
set<int> test;
test.insert(1);
test.insert(1);
test.insert(3);
test.insert(3);
test.insert(2);
\t
for (auto i : test)
{
cout << i << " ";
}
cout << endl;
cout << "size:" << test. size() << endl;
return 0;
}
operation result:
As you can see, the effect of insertion is similar to initialization.
(3) Find-find
//Time complexity: O(logN)----the bottom layer is the search tree
set<int>::iterator pos = s.find(3);
//Time complexity: O(N)----Need to traverse again (not recommended)
set<int>::iterator pos = find(s.begin(), s.end(), 3);
if (pos != s.end())
{
cout << "found" << endl;
}
For search, there are two ways, one is to use the characteristics of the search tree to search, and the other is to use the iterator to treat the search tree as a structure similar to an array, and then traverse the search. Of these two methods, obviously the first one is more efficient.
(4) delete-erase
test.erase(3);//(1) value deletion
test.erase(pos);//(2) iterator delete
cout << "Deleted data:";
for (auto i : test)
{
cout << i << " ";
}
cout << endl;
cout <<"size:" << test. size() << endl;
operation result:
For deletion, there are also two operation methods, one is to delete directly with the value you want to delete, and the other is to cooperate with find to pass the iterator to delete, but it should be noted that when find does not find the deleted value, it will return an empty iterator. Deleting with an empty iterator will result in an error.
(5) Empty-clear
test.clear();//clear all data
cout << "Data after clearing:";
for (auto i : test)
{
cout << i << " ";
}
cout << endl;
cout <<"size:" << test. size() << endl;
Running result:
One-key clear function, easy to use and high efficiency.
2. Use of map
The map is different from the set, and uses the pair container to store the data in the form of key-value pairs. The first in the pair corresponds to the key (key) of the map, and the second corresponds to the value (value) of the map.
(1) Initialization
map<int, string> test({ {3,"End"},{1,"Start"},{2,"Run"},{1,"xxxxxx"} });
cout << "Original data: "<<endl;
for (auto i : test)
{
cout << i.first<<":" <<i.second<< endl;
}
cout << "size:" << test. size() << endl;
operation result:
It can be seen that the map initialization does not look at the value, and the map initialization is roughly the same as the set initialization, so even if the key is the same but the value is different, the data cannot be stored.
(2) operator[]
As for why the [] of map is introduced first, it is mainly because this overload includes insert and modification after search (distinguished from find) two functions, easy to operate, so this method will be introduced first.
*Insert:
test[-1] = "preparation";//[] is an overload, so it only needs to match the type of key, so -1 can be used
cout << "Inserted data:" << endl;
for (auto i : test)
{
cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test. size() << endl;
Running result:
*Find:
cout << test[3] << endl;//print value by key
test[3] = "to be continued";//that is, to modify the value through the key
cout << "Inserted data:" << endl;
for (auto i : test)
{
cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test. size() << endl;
Running result:
It can be seen that the function of [] is roughly: If the key exists, return the value, and if the key does not exist, create a new pair for insertion.
(3) insert-insert
map<int, string> test;
test.insert(pair<int, string>(1, "start"));//Template type pair: Construct an anonymous object to insert into the map
test.insert(make_pair(2, "Run"));//Template function make_pair
test.insert({ 3, "End" });
There are three insertion methods for intert. It should be noted that the insertion of map elements is passed into the pair container for insertion.
(4) Find-find
//Time complexity: O(logN)----the bottom layer is the search tree
map<int,string>::iterator pos = test.find(3);
//Time complexity: O(N)----Need to traverse again (not recommended)
map<int,string>::iterator pos= find(test.begin(), test.end(), 3);
if (pos != test. end())
{
cout << "found" << endl;
}
If it is to modify the value after finding it, it is recommended to use [].
(5) Delete
test.erase(3);//(1) value deletion
test.erase(pos);//(2) iterator delete
cout << "Deleted data: "<<endl;
for (auto i : test)
{
cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test. size() << endl;
(6) Empty
test.clear();//clear all data
cout<<"clear data"<<endl;
for (auto i : test)
{
cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test. size() << endl;
return 0;
3. Introduction to usage scenarios
Set:
1. Array deduplication
2. Quick Find S
3. Sorting (n*logn)
4……
Map:
1. Dictionary operations, mapping values through keys, similar to macro definitions, but more diverse than macros
2. Replication of the complex linked list, the old node and the copied new node form a key-value relationship. When the old node has another point to the 3-node, the new node can get the new 3-node through the map, and then establish the point.
3……
In fact, for map, the use scene map of set can also be realized.
4. Summary
After reading so many operations, in fact, for Set and Map, its superiority is mainly in the operations of insertion, deletion and search, and these characteristics are based on the red and black tree (a type of search binary tree), and other features are extended on the red-black tree.