Detailed explanation of C++ map and unordered_map

Detailed explanation of C++ map and unordered_map

Overview

  The map and unordered_map in C++ provide a key-value pair container, which is often used in actual development. It is very similar to the Python dictionary. All data appears in pairs, the first of each pair The value is called a key, and each key can only appear once in the map; the second is called the corresponding value of the key.

map and unordered_map

  A map is an ordered container. The bottom layer is implemented by a red-black tree (what is a red-black tree?). The red-black tree is a self-balancing binary tree that can guarantee the worst-case running time. It can do O(logn) time to complete the operations of finding, inserting, and deleting elements. unordered_map is an unordered container. The bottom layer is implemented by a hash table (Hash Table-Wikipedia). The biggest advantage of a hash table is that it greatly reduces the time for data search and storage.

Intuitive comparison

map

unordered_map

advantage

1. Orderliness, can be used in applications with order requirements 2. Runtime under worst-case conditions can be guaranteed

The hash table ensures that the search and storage of elements are very fast

Disadvantage

The space occupancy rate is high, each node of the red-black tree needs to save the parent node, the child node and the red-black nature, which increases the use space

The establishment of the hash table is time-consuming

  Regarding their application scenarios, map must be used when there is a sequence requirement; if we only operate it once, in order to ensure the worst-case running time, it is best to apply map; and if we need to operate frequently, map It is definitely not as fast as unordered_map. Therefore, in addition to the use of map in scenarios with order requirements and word operation time requirements, other scenarios use unordered_map.

How to use map

  head File:include <map>   std is included in the following code:using namespace std;

Create a map object

//Method1
map<char, int> map1;
map1['a'] = 88;
map1['b'] = 90;
map1['c'] = 85;

//Method2
map<char, int> map2(map1.begin(), map1.end());

//Method3
map<char, int> map3(map2);

Iterators

Name

Description

begin

Returns an iterator pointing to the first element of the iterator

end

Returns an iterator pointing to the last element of the iterator

rbegin

An iterator that returns the first element of the iterator in reverse order

rend

Iterator that returns the last element of the iterator in reverse order

cbegin

An iterator that returns the first element of a constant iterator

cend

Iterator that returns the first element of a constant iterator

crbegin

Iterator that returns the first element of the constant iterator in reverse order

crend

Iterator that returns the last element of the constant iterator in reverse order

int main() {
    map<char, int>map1;
    map1['a'] = 10;
    map1['b'] = 20;
    map1['c'] = 30;

    map<char, int>::iterator it1;
    for (it1 = map1.begin(); it1 != map1.end(); ++it1) {
        cout << it1->first << "=>" << it1->second << endl;
    }

    for (auto it2 = map1.rbegin(); it2 != map1.rend(); ++it2) {
        cout << it2->first << "=>" << it2->second << endl;
    }

    return 0;
}

Capacity

Returns the size of the data used by the current vector

The max_size is related to the actual hardware, but not all memory space is available. The following code is the result of running on a 32GB computer

cout << map1.size() << endl;//3
cout << map1.max_size() << endl;//178956970

Element access

  Get elements can be applied []and at, if we index is keynot in the map object, then

  • []This will be keysaved in the map object, corresponding valueto the initialization value corresponding to the type;
  • atWill throw an exception
map1['a'] = 10;
map1['b'] = 20;
map1['c'] = 30;
cout << map1['d'] << endl;//Add map1['d']=0 to the object
cout << map1.at('e') << endl;//throw an exception

Operations

Name

Description

find

If the key is found, it returns the iterator of the position; otherwise, it returns the iterator of map::end

count

Contains element count, return value is 0 or 1

lower_bound

Returns an iterator to the fetched element

upper_bound

Returns an iterator to the next element of the selected element

equal_range

Return a pair, the first content of the pair is the result of lower_bound The second content of the pair is the result of upper_bound

findThe usage is as follows:

map<char, int>::iterator it;
it = map1.find('b');
cout << it->second << endl;//20
cout << map1.count('a') << endl;//1
cout << map1.count('e') << endl;//0

We redefine map1as:

map1['a'] = 10; map1['b'] = 20; map1['c'] = 30; map1['d'] = 40; map1['e'] = 50;

Let's test lower_boundand upper_bound:

map<char, int>::iterator itlow, itup;
itlow = map1.lower_bound('b');//itlow points to b
itup = map1.upper_bound('d');//itup points to e
map1.erase(itlow, itup);//a and e are left

equal_rangeThe returned result also contains the result of the lower_boundsumupper_bound

map1['a'] = 10; map1['b'] = 20; map1['c'] = 30; map1['d'] = 40; map1['e'] = 50;
pair<map<char, int>::iterator, map<char, int>::iterator> ret;
ret = map1.equal_range('b');
cout << ret.first->first << "=>" << ret.first->second << endl;//b=>20
cout << ret.second->first << "=>" << ret.second->second << endl;//c=>30 

Modifiers

Name

Description

insert

Insert element

erase

Delete element

swap

Swap the contents of the two containers

clear

Empty the contents of the container, the size value is 0, but the storage space has not changed

emplace

Insert element (different from insert)

emplace_hint

Insert elements by hint position

insertIs to insert elements, there are many uses

  • Insert an element
map<char, int>map1;
map1['a'] = 10;
map1['b'] = 20;
map1['c'] = 30;
map1.insert(pair<char, int>('d', 40));
  • Insert elements by hint position
map<char, int>::iterator it = map1.begin();
map1.insert(it, pair<char, int>('x', 100));
  • Insert range
map<char, int> map2;
map2.insert(map1.begin(), map1.find('c'));

eraseThere are three usages:

  • By keydeleting an element
 map1.erase('a');
  • Delete an element through an iterator
it = map1.find('a')
map1.erase(it);
  • Delete elements in a certain range
 it = map1.find('c')
 map1.erase(it, map1.end());

swapUsed to exchange the contents of two map objects

  map<char, int> foo, bar;
  foo['x'] = 100;
  foo['y'] = 200;
  bar['a'] = 10;
  bar['b'] = 20;
  bar['c'] = 30;
  foo.swap(bar);

clearUsed to clear the content of the map object. After clearing, the size becomes 0, but the actual storage space remains unchanged

map1.clear();

emplaceIt is also to insert an element. insertThere is a difference. emplaceThere insertare many usages. Only one element can be inserted. It creates this element directly behind the map object, so the speed

map1.emplace('x',100);
map1.emplace('y',200);

emplace_hintThe emplacehint position parameter is added on the basis of

map<char, int> map1;
auto it = map1.end();
it = map1.emplace_hint(it,'b', 10);
map1.emplace_hint(it,'a', 20);
map1.emplace_hint(map1.end(),'c', 30);

How to use unordered_map

  Header file: include <unordered_map>   std is included in the following code:, using namespace std;header file is also included#include<string>

Create a map object

typedef unordered_map<string, int> strIntMap;
strIntMap map1;
strIntMap map2({ {"Tom", 80}, {"Lucy", 85} });
strIntMap map3(map2);
strIntMap map4(map3.begin(), map3.end());

Iterators

Since unordered_map is unordered, there is no such thing as a reverse order

Name

Description

begin

Returns an iterator pointing to the first element of the iterator

end

Returns an iterator pointing to the last element of the iterator

cbegin

An iterator that returns the first element of a constant iterator

cend

Iterator that returns the first element of a constant iterator

The usage is the same as map, so I won’t give an example here.

Capacity

Returns the size of the data used by the current vector

These are the same with the map usage, no more examples

Element access

  Get elements can be applied []and at, if we index is keynot in the map object, then

  • []This will be keysaved in the map object, corresponding valueto the initialization value corresponding to the type;
  • atWill throw an exception

Same as map usage

Element lookup

Name

Description

find

If the key is found, it returns the iterator of the position; otherwise, it returns the iterator of map::end

count

Contains element count, return value is 0 or 1

equal_range

Returns an iterator to the fetched element

The usage of these three functions is the same as map

Modifiers

Name

Description

insert

Insert element

erase

Delete element

swap

Swap the contents of the two containers

clear

Empty the contents of the container, the size value is 0, but the storage space has not changed

emplace

Insert element (different from insert)

emplace_hint

Insert elements by hint position

insertThe usage of is a insertlittle different from that in map :

unordered_map<string, int>stu_score;
unordered_map<string, int> score2 = {{"Lily", 92}, {"Tom", 91}};
pair<string, int> stu1("Lucy", 88);
stu_score.insert(stu1);//copy insertion
stu_score.insert(make_pair<string, int>("Jim", 96));//move insertion
stu_score.insert(score2.begin(), score2.end());//range insertion
stu_score.insert({{"Hanmei", 99}, {"Lilei", 88}});//initializer list insertion

Other functions are the same as map usage

The following two sets of functions are related to the underlying hash table

Buckets

Name

Description

bucket_count

Return the number of buckets

max_bucket_count

Return the maximum number of buckets

bucket_size

Return bucket size

bucket

Returns the sequence number of the bucket where the key value is located

Hash_policy

Name

Description

load_factor

Return load factor

max_load_factor

Set or return the maximum value of load factor

rehash

Set the number of buckets

reserve

Control reserved space

Reference: https://cloud.tencent.com/developer/article/1652272 C++ map and unordered_map Detailed Explanation-Cloud + Community-Tencent Cloud