unordered_map 的使用

本文主要写法参考C++ STL函数库

std::unordered_map(C++11)

unordered_map是一个关联容器，内部采用的是hash表结构，拥有快速检索的功能。

特性

  1. 关联性：通过key去检索value，而不是通过绝对地址（和顺序容器不同）
  2. 无序性：使用hash表存储，内部无序
  3. Map : 每个值对应一个键值
  4. 键唯一性：不存在两个元素的键一样
  5. 动态内存管理：使用内存管理模型来动态管理所需要的内存空间

模版

1
2
3
4
5
6
template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

一般只使用模板前2个参数<KEY, T> 即unordered_map<const Key, T> map;

迭代器

unordered_map的迭代器是一个指针，指向这个元素，通过迭代器来取得它的值。

1
2
3
4
5
6
7
unordered_map<Key, T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>) 
   
it -> first;  key       // 它的键值分别是迭代器的first和second属性。
it -> second; T

构造函数

unordered_map的构造方式有几种：
- 构造空的容器
- 复制构造
- 范围构造
- 用数组构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

typedef unordered_map<string, string> stringmap;

stringmap merge(stringmap a, stringmap b)
{
    stringmap temp(a);
    temp.insert(b.begin(), b.end());
    return temp;
}

int main()
{
    stringmap first;                                                // 空
    
    stringmap second({{"apple", "red"}, {"lemon", "yellow"}});      // 用数组初始
    
    stringmap third({{"orange", "orange"}, {"strawberry", "red"}}); // 用数组初始
    
    stringmap fourth(second);                                       // 复制初始化
    
    stringmap fifth(merge(third, fourth));                          // 移动初始化
    
    stringmap sixth(fifth.begin(), fifth.end());                    // 范围初始化

    cout << "sixth contains:";
    
    for (auto &x : sixth)
        cout << " " << x.first << ":" << x.second;
    cout << endl;

    return 0;
}

输出结果：

1
sixth contains: apple:red lemon:yellow orange:orange strawberry:red

size()

返回unordered_map的大小

empty()

为空返回true

不为空返回false，和用size() == 0判断一样。

find();

查找key所在的元素。

找到：返回元素的迭代器。通过迭代器的second属性获取值

没找到：返回unordered_map::end

insert()

复制插入(复制一个已有的pair的内容)
数组插入（直接插入一个二维数组）
范围插入（复制一个起始迭代器和终止迭代器中间的内容）
数组访问模式插入(和数组的[]操作很相似)

具体的例子可以看后面示例代码。

at();

查找key所对应的值
如果存在：返回key对应的值，可以直接修改，和[]操作一样。
如果不存在：抛出 out_of_range 异常.

erase()

通过位置（迭代器）

通过key

通过范围（两个迭代器

clear()

清空unordered_map

swap()

void swap(unordered_map& ump);

交换两个unordered_map(整个交换两个map中的所有元素）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

void display(unordered_map<string, double> myrecipe, string str)
{
    cout << str << endl;
    for (auto &x : myrecipe)
        cout << x.first << ": " << x.second << endl;
    cout << endl;
}

int main()
{
    unordered_map<string, double> myrecipe, mypantry = {
        {"milk", 2.0},                                                     		 
        {"flour", 1.5}
    };
    
    pair<string, double> myshopping("baking powder", 0.3);
    
    myrecipe.insert(myshopping);                             // 复制插入
    
    myrecipe.insert(make_pair<string, double>("eggs", 6.0)); // 移动插入
    
    myrecipe.insert(mypantry.begin(), mypantry.end());       // 范围插入
    
    myrecipe.insert({{"sugar", 0.8}, {"salt", 0.1}});        // 初始化数组插入
    
    myrecipe["coffee"] = 10.0;                               // 数组形式插入
    

    display(myrecipe, "myrecipe contains:");

    /****************查找*****************/
    
    unordered_map<string, double>::const_iterator got = myrecipe.find("coffee");

    if (got == myrecipe.end())
        cout << "not found";
    else
        cout << "found " << got->first << " is " << got->second << "\n\n";
    
    /****************修改*****************/
    
    myrecipe.at("coffee") = 9.0;
    
    myrecipe["milk"] = 3.0;
    
    display(myrecipe, "After modify myrecipe contains:");

    /****************擦除*****************/
    
    myrecipe.erase(myrecipe.begin()); //通过位置
    
    myrecipe.erase("milk");           //通过key
    
    display(myrecipe, "After erase myrecipe contains:");

    /****************交换*****************/
    
    myrecipe.swap(mypantry);
    
    display(myrecipe, "After swap with mypantry, myrecipe contains:");

    /****************清空*****************/
    
    myrecipe.clear();
    display(myrecipe, "After clear, myrecipe contains:");
    return 0;
}

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
myrecipe contains:
salt: 0.1
milk: 2
flour: 1.5
coffee: 10
eggs: 6
sugar: 0.8
baking powder: 0.3

found coffee is 10

After modify myrecipe contains:
salt: 0.1
milk: 3
flour: 1.5
coffee: 9
eggs: 6
sugar: 0.8
baking powder: 0.3

After erase myrecipe contains:
flour: 1.5
coffee: 9
eggs: 6
sugar: 0.8
baking powder: 0.3

After swap with mypantry, myrecipe contains:
flour: 1.5
milk: 2

After clear, myrecipe contains:

begin()

begin() : 返回开始的迭代器

begin(int n) : 返回n号bucket的第一个迭代器

end()

end(): 返回结束位置的迭代器

end(int n) : 返回n号bucket的最后一个迭代器

bucket()

返回通过哈希计算key所在的bucket

此处仅使用哈希计算确定bucket，不保证key一定存在bucket中！

bucket_count()

返回bucket的总数

bucket_size()

返回第i个bucket的大小

此位置的桶子里的元素数量，但是函数并不会判断n是否在count范围内）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<string, string> mymap =
    {
            {"house", "maison"},
            {"apple", "pomme"},
            {"tree", "arbre"},
            {"book", "livre"},
            {"door", "porte"},
            {"grapefruit", "pamplemousse"}
    };
    
    /************begin和end迭代器***************/
    
    cout << "mymap contains:";
    for (auto it = mymap.begin(); it != mymap.end(); ++it)
        cout << " " << it->first << ":" << it->second;
    cout << endl;
    
    /************bucket操作***************/
    
    unsigned n = mymap.bucket_count();

    cout << "mymap has " << n << " buckets.\n";

    for (unsigned i = 0; i < n; ++i)
    {
        cout << "bucket #" << i << "'s size:" 
             << mymap.bucket_size(i) << " contains: ";
        
        for (auto it = mymap.begin(i); it != mymap.end(i); ++it)
            cout << "[" << it->first << ":" << it->second << "] ";
        cout << "\n";
    }

    cout << "\nkey:'apple' is in bucket #" << mymap.bucket("apple") << endl;
    cout << "\nkey:'computer' is in bucket #" << mymap.bucket("computer") << endl;

    return 0;
}

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
mymap contains: door:porte grapefruit:pamplemousse tree:arbre apple:pomme book:livre house:maison
mymap has 7 buckets.
bucket #0's size:2 contains: [book:livre] [house:maison]
bucket #1's size:0 contains:
bucket #2's size:0 contains:
bucket #3's size:2 contains: [grapefruit:pamplemousse] [tree:arbre]
bucket #4's size:0 contains:
bucket #5's size:1 contains: [apple:pomme]
bucket #6's size:1 contains: [door:porte]

key:'apple' is in bucket #5

key:'computer' is in bucket #6
cpp
#STL #unordered_map
unordered_map 的使用
https://chaggle.github.io/2021/01/08/cpp/unordered_map/
作者
chaggle
发布于
2021年1月8日
许可协议