C++中unordered_map调用push_back方法插入元素的原因解析

涉及示例代码 #

#include<iostream>
#include<unordered_map>
#include<list>
#include<cstring>

using namespace std;
class Graph {
    unordered_map<string, list<pair<string, int>>> l;
public:
    void addedge(string x, string y, bool bidir, int wt) {
        l[x].push_back(make_pair(y, wt));
        if (bidir) {
            l[y].push_back(make_pair(x, wt));
        }
    }
};

int main()
{
    Graph g;
    g.addedge("A", "B", true, 20);
    return 0;
}

问题解答 #

为什么可以调用push_back() #

push_back()根本不是unordered_map对象调用的。成员变量l的类型是unordered_map<string, list<pair<string, int>>>，也就是键为字符串、值为存储边信息的链表的哈希表：

• 表达式l[x]调用的是unordered_map重载的下标运算符，返回值是键x对应的值的引用，类型为list<pair<string, int>>&
• 后续的.push_back()是这个返回的list对象的成员方法，和外层的unordered_map没有关系。

调用的实际执行逻辑 #

l[x].push_back(...)的执行分为两个阶段：

1. 下标访问阶段：执行l[x]时，哈希表会先查找是否存在键为x的条目
   • 如果存在，直接返回该条目对应链表的引用
   • 如果不存在，会自动在哈希表中插入一个新条目：键为传入的x，值为默认构造的空链表，之后返回这个新插入的空链表的引用
2. 链表插入阶段：拿到链表的引用后，调用list的push_back()方法，将传入的边信息（邻接节点名、边权重）插入到链表尾部。

以示例中g.addedge("A", "B", true, 20)的执行为例：

• 第一次执行l["A"]时，哈希表无"A"键，自动插入"A"对应空链表，随后将("B",20)插入该链表
• 因为是双向边，接着执行l["B"]，哈希表无"B"键，自动插入"B"对应空链表，随后将("A",20)插入该链表

注意：unordered_map的下标运算符存在自动插入键的副作用，如果仅需要判断键是否存在、不希望修改哈希表结构，应该使用find()方法而非下标访问，避免插入冗余的空条目。

内容的提问来源于stack exchange，提问作者havoc_jas