Set、Map、Unordered

Map和Set

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

0、示范图

         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)所以被判定为相等，与我们的目的南辕北辙。

#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;
}

输出结果为：

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

2、正确用法priority_queue

#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;
}

输出结果为：

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==

#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;
}