Set、Map、Unordered

Posted on Edited on Symbols count in article: 3.7k Reading time ≈ 3 mins.

Map和Set

  • Map是<key, value>结构；Set是<key>结构，天然具有去重功能
  • 自定义类放入Map或Set需要实现bool operator<(const MyClass& ano) const，注意里面的两个const是必备的，不能漏
  • 不用实现operator=，因为a<b == false && a>b == false会自动推断出等于

0、示范图

1
2
3
4
5
6
7
8
9
         0
         |
        (1)
         |
2 —(1)—  1  —(1)— 3
   \           /
   (3)       (2)
      \     /
         4

1、错误代码示例

  • 下面Node类，利用Set来实现Dijkstra是不对的，因为在operator<中参与返回结果的只有val因此，两个不一样的Node在Set中会被认为是相同的。即Node a = Node({1,1})和Node b = Node({2,1})，由于(a<b==false && b>a==false)所以被判定为相等，与我们的目的南辕北辙。 
    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
    #include <iostream>
    #include <vector>
    #include <set>
    using namespace std;
    const int inf = INT_MAX;
    struct Node {
        Node(int _p, int _v):pos(_p), val(_v){}
        int pos;
        int val;
        bool operator<(const Node& ano) const {
            return this->val < ano.val;
        }
    };

    int main() {
        vector<vector<int>> g = {
            {0,   1,   inf, inf, inf},
            {1,   0,   1,   1,   inf},
            {inf, 1,   0,   inf, 3  },
            {inf, 1,   inf, 0,   2  },
            {inf, inf, 3,   2,   0  },
        };
        int n = (int)g.size();
        // ------------------------------------
        vector<int> dist(n, INT_MAX);
        dist[0] = 0;
        set<Node> pq;
        pq.insert(Node(0, 0));
        while (!pq.empty()) {
            Node cur = *pq.begin(); pq.erase(pq.begin());
            int from = cur.pos;
            int dis = cur.val;
            cout << from << " " << cur.val << endl;
            for (int to = 0; to < n; ++to) {
                if (g[from][to] < inf && dist[to] > dis + g[from][to]) {
                    dist[to] = dis + g[from][to];
                    pq.insert(Node(to, dist[to]));
                }
            }
        }
        for (auto e : dist)
            cout << e << " ";
        cout << endl;

        return 0;
    }
    输出结果为： 
    1
    2
    3
    4
    5
    6
    0 0
    1 1
    2 2
    4 5
    0 1 2 2 5 // 错误，应该是4
    // 原因是插入Node{3,2}时发现已经有了，所以就取消插入，因此无法利用{3,2}来更新最小边

2、正确用法priority_queue

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int inf = INT_MAX;
struct Node {
    Node(int _p, int _v):pos(_p), val(_v){}
    int pos;
    int val;
    bool operator>(const Node& ano) const {
        return this->val > ano.val;
    }
};

int main() {
    vector<vector<int>> g = {
        {0,   1,   inf, inf, inf},
        {1,   0,   1,   1,   inf},
        {inf, 1,   0,   inf, 3  },
        {inf, 1,   inf, 0,   2  },
        {inf, inf, 3,   2,   0  },
    };
    int n = (int)g.size();
    // ------------------------------------
    vector<int> dist(n, INT_MAX);
    dist[0] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push(Node(0, 0));
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int from = cur.pos;
        int dis = cur.val;
        cout << from << " " << cur.val << endl;
        for (int to = 0; to < n; ++to) {
            if (g[from][to] < inf && dist[to] > dis + g[from][to]) {
                dist[to] = dis + g[from][to];
                pq.push(Node(to, dist[to]));
            }
        }
    }
    for (auto e : dist)
        cout << e << " ";
    cout << endl;

    return 0;
}

输出结果为： 

1
2
3
4
5
6
7
0 0
1 1
2 2
3 2 // OK
4 4
4 5
0 1 2 2 4 // OK

总之，以后写Dijkstra不要妄图用set和map来替换优先队列!!!

Unordered_set和unordered_map

  1. 需要定义一个仿函数operator(...)用来计算hash_value，并在定义时传入模板参数
  2. 重载operator== 
    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
    #include <iostream>
    using namespace std;

    #include <string>
    #include <unordered_map>
    struct node {
        node(int _id, double _val) : id(_id), val(_val) {}
        int id;
        double val;
        bool operator==(const node& ano) const { // 判断两个对象是否相等（自动加上key匹配再判断相等）
            return val == ano.val;
        }
    };

    struct node_hash {
        size_t operator()(const node& v) const { // 生成hash value，必须返回 [无符号整数] 用来进行映射
            return v.id; // 生成hash value的方式都可以灵活自定义
            //return hash<double>()(v.val);
        }
    };

    int main() {
        unordered_map<node, string, node_hash> ms;
        node a = { 1, 1.1111 };
        node b = { 2, 1.1111 };
        ms[a] = "aaaa";
        ms[b] = "bbbb";
        cout << ms[a] << endl;
        cout << ms[b] << endl;
        return 0;
    }