C++中的map和unordered_map

map

简介

映射表（Map）容器是一个按特定顺序存储以键值对组合而成的元素的关联容器。

类模板

1
2
3
4
5
6

// <map>
template < class Key,
    class T,
    class Compare = less<Key>,
    class Alloc = allocator<pair<const Key,T> >
> class map

模板参数

1. key：主键的类型；
2. T：被映射的值得类型；
3. Compare：一个二元谓词，以两个元素的主键为参数返回一个 bool 值。
4. Alloc：容器内部用来管理内存分配及释放的内存分配器的类型。这个参数是可选的，它的默认值是 std::allocator，这个是一个最简单的非值依赖的（Value-independent）内存分配器。

详细说明

在一个映射表容器中，主键通常被用来排序及唯一标志一个元素，而被映射的值保存了与该主键关联的内容。主键与被映射值的类型可以不同，在模板内部，这两种类型合并绑定成成员类型 value_type。由上述描述可知，value_type 是一个双元组类型（Pair type），具体定义如下：

1

typedef pair<const Key, T> value_type;

map 容器中的所有元素都是按由类型为 Compare 的比较对象指定的严格弱序规则排序的。
在用主键访问单个元素时，map 容器通常比 unordered_map 容器低效，但 map 容器允许按顺序直接对某个子集进行迭代。
map 容器通常被实现为一个二叉搜索树（及其变型），该数据结构具有对数据自动排序的功能。
在所有关联容器中，map 容器唯一具有的一个特点：实现了直接访问操作符（operator[]），使得可以直接访问被映射的值。
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
using namespace std;
struct Node {
    int id;
    int val;
    Node(int id,int val)
    :id(id),val(val){

    }
};

struct compare{
    bool operator()(const Node &a,const Node &b)const{
        return a.val<b.val;
    }
};

bool operator<(const Node &a,const Node &b){
    return a.val<b.val;
}

int main(int argc, const char * argv[]) {
    cout<<"初始化一个map，有序的，默认是升序"<<endl;
    map<string,int> test_map;



    cout<<"添加数据方式一,插入key值一样的pair，不会改变原本pair"<<endl;
    test_map.insert(pair<string, int>("a",2));
    test_map.insert(pair<string, int>("b",3));
    test_map.insert(pair<string, int>("d",4));
    test_map.insert(pair<string, int>("c",6));


    cout<<"添加数据方式二,可以通过[]来修改key对应的值"<<endl;
    test_map["a"] = 2;
    test_map["b"] = 3;
    test_map["d"] = 4;
    test_map["c"] = 6;

    cout<<"传入key值删除元素"<<endl;
    test_map.erase("a");

    cout<<"map的大小"<<endl;
    cout<<test_map.size()<<endl;

    cout<<"遍历map"<<endl;
    for (auto pos = test_map.begin(); pos!=test_map.end(); pos++) {
        cout<<"key:"<<pos->first<<" value:"<<pos->second<<endl;
    }
    cout<<endl;

    cout<<"计算key为d的元素个数，为1即有，为0即没有"<<endl;
    if(test_map.count("d")==1){
        cout<<"find d"<<endl;
    }else{
        cout<<"no find"<<endl;
    }

    cout<<"寻找key为d的元素，若找到的返回对象元素的迭代器，否则返回最后一个元素的迭代器"<<endl;
    if (test_map.find("d")!=test_map.end()) {
        cout<<"find d value is "<<test_map.find("d")->second<<endl;
    }else{
        cout<<"no find"<<endl;
    }

    cout<<"自定义类型的map,需要重新compare函数或者重载<运算符，其他用法参照上面"<<endl;
    map<Node, int, compare> node_map;

    //需要重载<运算符，系统默认的compare是less
    //map<Node, int> node_map;
    Node n1(1,2);
    Node n2(3,1);
    Node n3(4,5);

    node_map.insert(pair<Node, int>(n1,1));
    node_map.insert(pair<Node, int>(n2,2));
    node_map.insert(pair<Node, int>(n3,3));

    for (auto pos = node_map.begin(); pos!=node_map.end(); pos++) {
        cout<<"Node value is "<<pos->second<<endl;
    }
    cout<<endl;

    return 0;
}

unordered_map

简介

无序映射表（Unordered Map）容器是一个存储以键值对组合而成的元素的关联容器，容器中的元素无特别的次序关系。该容器允许基于主键地快速检索各个元素

类模板

1
2
3
4
5
6
7

// <unordered_map>
template < class Key,
    class T,
    class Hash = hash<Key>,
    class Pred = equal_to<Key>,
    class Alloc = allocator< pair<const Key,T> >
> class unordered_map;

模板参数

1. key：主键类型；
2. T：被映射的值的类型；
3. Hash：一元谓词，以一个 Key 类型的对象为参数，返回一个基于该对象的 size_t 类型的唯一值；
4. Pred：二元谓词，以两个 Key 类型的对象为参数，返回一个 bool 值，如果第一个参数等价于第二个参数，该 bool 值为 true，否则为 false。默认为 std::equal_to；
5. Alloc：容器内部用来管理内存分配及释放的内存分配器的类型。这个参数是可选的，它的默认值是 std::allocator，这个是一个最简单的非值依赖的（Value-independent）内存分配器。

详细说明

在一个 unordered_map 容器中，主键通常被用来唯一标志（Uniquely identify）一个元素，而被映射的值保存了与该主键关联的内容。主键与被映射值的类型可以不同，在模板内部，这两种类型合并绑定成成员类型 value_type。由上述描述可知，value_type 是一个双元组类型（Pair type），具体定义如下：

1

typedef pair<const Key, T> value_type;

在 unordered_map 内部，元素不会按任何顺序排序，而是通过主键的 hash 值将元素分组放置到各个槽（Bucket，也可译成“桶”）中，这样就能通过主键快速地访问各个对应的元素（平均耗时为一个常量，即时间复杂度为 O(1)）。
在访问容器中的某个元素时，unordered_map 容器比 map 容器高效，而在迭代容器元素的某个子集时，前者比后者稍微低效了一点。
unordered_map 实现了直接访问操作符（operator[]），使得可以通过主键（Key value）直接访问被映射的值（Mapped value）。
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
using namespace std;
struct Node {
    int id;
    int val;
    Node(int id,int val)
    :id(id),val(val){

    }
};

struct hash_func{
    size_t operator()(const Node &n)const{
        return n.id*99+n.val;
    }
};

struct equal_to_func{
    bool operator()(const Node &a,const Node &b)const{
        return a.id==b.id&&a.val==b.val?true:false;
    }
};

int main(int argc, const char * argv[]) {
    Node n1(1,2);
    Node n2(3,1);
    Node n3(4,5);


    cout<<"初始化一个unordered_map"<<endl;
    unordered_map<string, int> test_unordered_map;
    test_unordered_map["a"] = 1;
    test_unordered_map["b"] = 2;
    test_unordered_map["c"] = 3;
    cout<<"遍历unordered_map"<<endl;
    for (auto pos = test_unordered_map.begin(); pos!=test_unordered_map.end(); pos++) {
        cout<<"key:"<<pos->first<<" value:"<<pos->second<<endl;
    }
    cout<<endl;

    cout<<"初始化一个自定义类型unordered_map，需要重写hash函数和pred函数"<<endl;
    unordered_map<Node, int,hash_func,equal_to_func> node_unordered_map;
    node_unordered_map[n1] = 1;
    node_unordered_map[n2] = 2;
    node_unordered_map[n3] = 3;
    cout<<"遍历node_unordered_map"<<endl;
    for (auto pos = node_unordered_map.begin(); pos!=node_unordered_map.end(); pos++) {
        cout<<"key id:"<<pos->first.id<<" value:"<<pos->second<<endl;
    }
    cout<<endl;


    return 0;
}

Comments