关联容器与适配器：
查找、唯一性与访问顺序。

11.1 pair和结构化绑定：把两项结果一起交回来

已经会在vector里逐项查找，为什么还要换容器？先看两个任务：按ID查一条记录，需要“这个键对应什么”；按到达顺序处理工作，需要“下一条轮到谁”。这两种问题需要的访问方式不同。本章先学把两项信息放在一起，再分别选择按键组织和按顺序处理的容器。先完成第10章的算法与lambda。

std::pair<int, int>是标准库提供的“一对值”类型，头文件为<utility>。尖括号的两个类型依次规定第一项和第二项，沿用08.1“给现成库类型填实参”的读法；这里不定义模板。对象values的两项分别叫values.first和values.second，可以像07章的普通成员一样读取。它们不必类型相同，例如键为string、计数为int时可写std::pair<std::string, int>。

花括号中的值按这两个位置初始化。std::pair<int, int> values{2,5};建立一个pair对象，其两项为2和5；它不是长度可以继续增加的vector。

两个好读的名字，是否仍在访问原对象

auto [left, right] = values;叫结构化绑定（structured binding），C++17起可用，本书使用C++20。这里先由values建立一份pair副本，再让left和right分别命名这份副本的两项。不是按变量名去找成员，也不是将原values拆坏。名字可以自己取，但位置顺序不能猜反。

auto& [first, second] = values;则借用原values；first和second对应原对象的成员，写first会改变values.first。const auto& [a,b] = values;通过只读路径借用两项，不能用a或b写入；它不会冻结原对象的其他合法访问路径。这里借用的都是仍在作用域内的values，期限继续遵守05章的规则。const auto [a,b] = values;则建立只读的pair副本；它没有&，不是对原pair的只读借用。

#include <iostream>
#include <utility>

int main() {
    std::pair<int, int> values{2, 5};
    auto [left, right] = values;
    left = 7;
    std::cout << left << ' ' << right << '\n';
    std::cout << values.first << ' ' << values.second << '\n';
    auto& [first, second] = values;
    first = 9;
    std::cout << first << ' ' << second << '\n';
    const auto& [read_first, read_second] = values;
    std::cout << read_first << ' ' << read_second << '\n';
    return 0;
}

先将副本的left改成7：副本两项是7和5，原values仍为2和5。随后通过引用绑定把原第一项改成9，原对象成为9和5。区别在声明有没有借用原对象，不能因为变量名都来自同一份输入就推断它们自动同步。

以后见到for (const auto& [key,value] : table)，把已经会的两件事组合起来读：范围for逐次拿到一个元素，结构化绑定给这个元素的两项取名。是否复制、是否只读仍由声明决定；本章下一节会提供真实table。

11.2 map和set：键是什么，查询会不会改变内容

先认键和值，再读接口

std::map<std::string, int>需要<map>和<string>。它存放键（key）到值（mapped value）的关联：例如red对应2，blue对应1。map中的每个元素是一对键值，读作std::pair<const std::string, int>。键在元素中是const，计数可以修改；不能直接改元素的键来“换一个位置”，那会破坏容器按键组织的关系。

对本章的默认比较方式，键按大小顺序组织；这些小写字符串按内容比较，blue排在red前面，与插入先后无关。对于map和set，更一般的“同一个键”由比较器决定：两边都不排在对方前面，就视为等价，沿用10.3的严格弱序。当前的整数和普通string例子与按值相等一致，不需要自己写比较器。

容器名字后花括号中的{"red",2}、{"blue",1}各表示一条键值初值。这里的键类型明确是std::string；传入"red"这样的字符串字面量时，按本例接口构造string键来查询，不是拿字符指针地址当键。size()数的是已经存储的键值条目，不是所有计数的总和。

缺失时，你希望得到什么

at的错误传播和捕获在错误处理章再展开；本章只在已经确认键存在时调用它，不借异常做存在性检查。没有把“缺失”和“已有键的值恰好为0”区分开的接口，不适合用来判断存在性。map的[]也不接收“第几项”的序号；方括号里的参数是键。

find返回的迭代器仍遵守09章的读取规则：先确认不等于end，再解引用。(*position).second先取得位置上的键值pair，再读取它的第二项。外面这对圆括号让成员访问发生在解引用之后；得到end时不能读取first或second。

#include <iostream>
#include <map>
#include <string>

int main() {
    const std::map<std::string, int> counts{{"red", 2}, {"blue", 1}};
    std::cout << counts.contains("green") << ' ' << counts.count("green")
              << ' ' << counts.size() << '\n';
    const auto missing = counts.find("green");
    if (missing == counts.end()) {
        std::cout << "missing\n";
    }
    const auto red = counts.find("red");
    if (red != counts.end()) {
        std::cout << (*red).second << '\n';
    }
    std::cout << counts.size() << '\n';
    return 0;
}

初始两个键。查询green失败后，键数仍是2；查询red成功，取到值2。contains问“有没有”，count给匹配数量，find提供继续读取的具体位置；它们的返回类型和用途不同。

一个看起来只读、实际上插入的表达式

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> counts{{"red", 2}, {"blue", 1}};
    std::cout << counts.size() << '\n';
    const int observed = counts["green"];
    std::cout << observed << '\n';
    std::cout << counts.size() << '\n';
    return 0;
}

读counts["green"]之前，只有red和blue。green缺失，所以下标操作先建立green对应的int零值，再把这个0交给读取者。即使把结果保存进一个普通副本、之后从未修改它，插入也已经发生，键数从2变成3。

要修复的是查询方式：先find，再比较end；只需要真假时用contains。不要在查询完以后删掉green来伪装成没有副作用，也不要用“读取结果等于0”推断键不存在。

set只有键，没有单独的计数值

std::set<int>来自<set>，只保存唯一的整数键。用3初始化，两个3对应同一个键，最终只有1和3，按升序遍历；它不会自动记录3出现过两次。要记录次数，应该使用map的映射值。set没有map那样的[]，它提供find、contains和count等按键接口。values.insert(x)尝试加入一个整数键，已有等价键时集合不变；本节只观察集合内容，不读取这次调用的返回值。

#include <iostream>
#include <set>

int main() {
    std::set<int> values{3, 1, 3};
    values.insert(1);
    for (const int value : values) {
        std::cout << value << '\n';
    }
    std::cout << "size " << values.size() << '\n';
    std::cout << values.count(3) << ' ' << values.contains(2) << '\n';
    return 0;
}

初始集合已含1，额外的insert(1)不增加条目；所以size仍为2，count(3)为1，contains(2)为false。通过set迭代器也不能改键值。map/set的迭代器可逐项前进，但不支持vector那样的任意整数偏移和双迭代器减法；不能把它们的begin/end交给要求随机访问的std::sort。容器已经按自己的键比较规则组织顺序。

以键比较次数看，map/set的这类查找有O(log n)的增长上界，而不必扫描所有n项。这个说法不指定某一种树的节点布局，也不是实际耗时；字符串比较本身也有成本。当前先把“有序、唯一、查询是否写入”说准确。

11.3 unordered容器：按键查找不意味着按键排列

std::unordered_map<std::string,int>来自<unordered_map>。它同样把一个键对应到一个值，同样不保存重复等价键，但不承诺升序，也不承诺插入顺序。contains、count、find、下标和at在本章的存在性/插入行为上按上节读法使用；不要顺手把map的遍历顺序和位置稳定性也搬过来。

哈希先缩小查找范围，相等判断确认是不是那个键

哈希（hash）把键计算成用于组织查找的数值，容器再据此选择桶（bucket）。不同键可能落到同一个桶，也可能得到同一哈希值，这叫碰撞（collision）。碰撞不表示两条记录必须覆盖：还要比较键是否相等，才能确定究竟是哪条记录。

可以在纸上把red和blue放进同一个示意桶：查red时，不能遇到blue就返回它的值，要继续按字符串内容确认。这只是解释合同的教学模型，不声称本机标准库真的采用这些桶编号、存储布局或检查顺序。本章不实现哈希表，也不编造一个std::hash的固定输出。

需要记住的方向是：键相等，必须得到相同哈希值；哈希值相同，不足以证明键相等。若以后定制哈希与相等规则，两者要一致，同一存储期间对同一键的判断也要稳定。现在使用标准库为string提供的默认规则，不能把它误读成字符指针地址比较。

在常见的平均情形下，按键查找的复杂度为O(1)，最坏可能退化到O(n)。这是按表中键数量n讨论的增长，实际还要支付哈希/相等判断的成本；长字符串、分配和缓存都可能影响耗时。“平均常数”既不保证每次只检查一个键，也不保证一定比小vector更快。

跟踪计数表，但明确指定输出键

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    const std::vector<std::string> words{"red", "blue", "red"};
    std::unordered_map<std::string, int> counts{};
    for (const auto& word : words) {
        ++counts[word];
    }
    const auto red = counts.find("red");
    const auto blue = counts.find("blue");
    std::cout << "red " << (red == counts.end() ? 0 : (*red).second) << '\n';
    std::cout << "blue " << (blue == counts.end() ? 0 : (*blue).second) << '\n';
    std::cout << "keys " << counts.size() << '\n';
    return 0;
}

从空表开始，处理red时先建立red=0再加一，得到red=1；处理blue后增加blue=1；再次处理red时已有该键，只把其计数从1改为2。最后是red=2、blue=1、键数2。

代码按指定键查找并输出结果，查到合法位置后才读取second。这里复用03.6的条件运算符：位置等于end时只向输出提供0，否则才读取对应计数；这个显示用的0不会建立键，也不能单独证明键缺失，存在性由end比较判断。没有通过一次哈希表遍历去猜“哪一行先打印”。如果输入为空，表仍为空；输出缺失状态时不要为了打印0而对表使用下标，除非你确实希望创建那些零计数键。

std::unordered_set<int>来自<unordered_set>，对应只保留唯一键的无序集合。它没有单独的映射值、没有下标接口；是否包含某个整数用contains/find/count。与set相比，唯一性用途相近，但它不提供升序遍历的承诺，本章独立任务需要有序结果时会选择set。

try_emplace：只在没有该键时建立值

counts.try_emplace("red",2)表示：没有red就用后面的参数建立它的值；已经有red则保留旧值，不用2覆盖。map与unordered_map都提供这个接口。它也会返回插入位置及真假结果，11.4马上学习怎样读取；当前先观察表本身，调用语句不使用返回值并不影响插入动作。

“没有覆盖”也不表示实参没有计算。make_count是一个普通函数：调用时先增加calls再返回9。把它写进重复red的插入实参里，它仍在这次函数调用之前执行，所以calls为1，而red仍为2。try_emplace不会替调用者把实参表达式变成一个延后才执行的任务。

#include <iostream>
#include <string>
#include <unordered_map>

int make_count(int& calls) {
    ++calls;
    return 9;
}

int main() {
    std::unordered_map<std::string, int> counts{};
    int calls{0};
    counts.try_emplace("red", 2);
    counts.try_emplace("red", make_count(calls));
    counts.try_emplace("blue", 1);
    std::cout << counts.at("red") << ' ' << counts.at("blue")
              << ' ' << counts.size() << '\n';
    std::cout << "calls " << calls << '\n';
    return 0;
}

先建立red=2，再对red提出值9的插入请求，red仍是2；随后加入blue=1，最终键数为2。与counts["red"] = 9明确写回旧值不同，try_emplace把“已存在”当作保留原记录。

阅读哈希计数完整源码之前，补清其中范围的拥有者：for右侧直接建立的完整临时vector会存活到这次范围循环结束，每轮word借用其中仍存活的string元素。这条说明只针对眼前完整临时容器，不推广到由临时对象返回的view或其他临时链。单语句for体沿用09.2，固定存在的red/blue使用刚学的at；输出应为red=2 blue=1 green=0 keys=2，green没有被插入。

11.4 插入结果与位置：刚才新建了，还是原本就有

只知道表最后是什么样，有时还不够。处理重复ID时，往往还需要知道“这次是否接收了一条新记录”。本节这些没有位置提示参数的map/unordered_map插入调用返回一个pair：第一项是元素位置，第二项是bool，true表示本次确实插入；false表示已有等价键。false不是“没有得到可读记录”，位置仍指向那条已有记录。

先解包返回结果，再读位置上的pair

auto [position, inserted] = table.try_emplace(key,value);用11.1的结构化绑定取得两个返回信息。这里有两层：返回pair的第一项是迭代器；迭代器所指的容器元素本身又是键值pair。不要把position误当成那个整数value。

对本章关联容器中可解引用的迭代器，position->second访问它所指键值pair的第二项，效果与(*position).second对应。这是库迭代器提供的成员访问写法；与07章原生指针的箭头外观相同，不表示迭代器本身一定是裸指针。也不能因为用了箭头就省掉有效性检查：find得到end仍不可读取；当前插入返回的位置则按上面的合同指向新条目或已存在条目。

insert与emplace分别接收什么

table.insert(entry)接收准备好的一条键值pair；table.emplace(key,value)接收用于在容器中构造键值元素的参数。当前都是简单string/int，并且只讨论唯一键容器的不带提示位置版本，别把这些返回类型推广到其他重载。二者遇到等价键均不覆盖旧值。下面准备的候选pair类型为std::pair<std::string,int>；insert按其中的键和值建立容器条目，存储元素的键仍是const string，不要求候选pair的类型文字与容器元素完全相同。

emplace表示一种构造接口，不是无条件的性能承诺。不能据名字断言从不产生中间对象，也不能保证失败插入时完全没有做构造工作；实际成本需要在具体类型和实现上测量。当前只需准确读出输入、插入真假和最终元素。

#include <iostream>
#include <map>
#include <string>
#include <utility>

int main() {
    std::map<std::string, int> counts{};
    const auto [where, inserted] = counts.try_emplace("red", 2);
    std::cout << inserted << ' ' << where->second << '\n';
    const auto [same, duplicate] = counts.emplace("red", 9);
    std::cout << duplicate << ' ' << same->second << '\n';
    const std::pair<std::string, int> candidate{"blue", 1};
    const auto result = counts.insert(candidate);
    std::cout << result.second << ' ' << result.first->second << '\n';
    std::cout << "size " << counts.size() << '\n';
    return 0;
}

第一步新建red=2，插入结果为true，返回位置读取2。第二步emplace再次提出red=9，结果为false，返回位置读取的仍是旧值2。第三步把准备好的blue=1交给insert，它是新键，结果为true，位置读取1，最终键数2。把false分支一概当成“无值可读”会丢掉处理重复记录所需的信息。

用完位置，再改变容器；不要默认所有位置都一样稳定

map/set的普通插入不会使原有元素迭代器失效，删除元素则会使指向被删元素的位置失效。unordered容器插入时可能重新组织桶，称为rehash；一旦发生，它会使原有迭代器失效，但已有元素的引用不会因为这次rehash而失效。它们不是vector扩容的同一套规则。

本例对每次返回的位置立即读取，之后不跨下一次修改复用旧迭代器。需要长期保存位置时，必须按具体操作的合同判断；本章最简单的方式是在修改之后重新find。map的键是const，拿到可写迭代器也不能直接改first；set的整个元素就是键，同样不通过迭代器改它。

11.5 deque、queue与stack：下一项从哪一端拿

按ID去重解决不了处理顺序。现在给同样几条工作选定规则：先到先做，或者最后加入的先取出。

deque：两端都能添加和移除

std::deque<int>来自<deque>，是双端序列。它可以使用合法下标访问，但不承诺所有元素像vector那样连续存储；不能从“支持下标”推断出“可把整组当作连续span”。

push_front(x)在前端加入，push_back(x)在后端加入；front()和back()分别访问两端元素。pop_front()和pop_back()移除相应端点，返回void，不顺便把被移除的值交回来。需要保存旧值时先读取成一个副本，再pop。访问或移除端点前必须确认非空，empty()为true时不能继续front/back/pop。

本例先完成两次push，此时至少有两个元素，保证接下来的端点读取和两次pop合法；删除之后再用empty检查是否还有元素。最后的范围for沿用09.2，deque也提供逐项遍历所需的begin/end。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> values{2, 5};
    values.push_front(1);
    values.push_back(8);
    std::cout << values.front() << ' ' << values.back()
              << ' ' << values.size() << '\n';
    values.pop_front();
    values.pop_back();
    if (!values.empty()) {
        std::cout << values.front() << ' ' << values.back()
                  << ' ' << values.size() << '\n';
    }
    for (const int value : values) {
        std::cout << value << '\n';
    }
    return 0;
}

从[2,5]开始，前端加1、后端加8，得到[1,2,5,8]：front为1，back为8，size为4。随后各移除一个端点，回到[2,5]：两端为2和5，size为2。这里每次都重新查询端点，不把旧端点引用保留到删除之后。deque的端部插入会使已有迭代器失效，但不会因此使已有元素的引用失效；被删除元素的引用仍然不能再用。不要照搬vector或map的规则。

queue：FIFO，先进入的先处理

std::queue<int>来自<queue>，默认使用deque保存元素，但只公开符合队列规则的接口。FIFO是first in, first out：push从后端加入，front看最早未取走的一项，pop移除前端。size数等待项，empty回答是否没有等待项。

queue叫容器适配器（container adaptor），意思是用底层容器保存数据，再提供一种受限制的访问接口。它不是deque的另一个名字；没有公开begin/end供范围for任意遍历，也没有提供下标访问。需要依次处理时，在while中先判非空，再front，最后pop。

stack：LIFO，最后加入的先取出

std::stack<int>来自<stack>，同样是适配器，默认底层也可以由deque保存。LIFO是last in, first out：push把元素放在顶端，top看最新加入且尚未取走的项，pop移除顶端。stack使用top而不是front；它也不提供下标或范围for遍历接口。

#include <iostream>
#include <queue>
#include <stack>
#include <vector>

int main() {
    const std::vector<int> arrivals{2, 5, 7};
    std::queue<int> fifo{};
    std::stack<int> lifo{};
    for (const int value : arrivals) {
        fifo.push(value);
        lifo.push(value);
    }
    std::cout << "queue\n";
    while (!fifo.empty()) {
        std::cout << fifo.front() << '\n';
        fifo.pop();
    }
    std::cout << "stack\n";
    while (!lifo.empty()) {
        std::cout << lifo.top() << '\n';
        lifo.pop();
    }
    std::cout << "empty " << fifo.empty() << ' ' << lifo.empty() << '\n';
    return 0;
}

同样按2、5、7加入：queue依次取出2、5、7，stack依次取出7、5、2。每次读取前都有非空检查；最终两者都为空。输出与pop分成明确的两个步骤，避免把返回void的pop当作一个可以打印的整数。

“最后加入”不等于“优先级最高”。堆与priority_queue算法在后面的算法章节再学习；本章不把名称相似当作同一种访问规则。

四步练习：从计数表到小工作清单

1. 预测：关闭hash-count的运行结果，对red、blue、red逐步写出已有键、各值、size。不要写哈希遍历的固定顺序。
2. 补全：用find/contains完成green的缺失查询和red的命中读取。查询前后键数必须仍为2，不能用下标补出缺失键。
3. 找错：解释subscript-side-effect为什么让键数从2变3。只替换错误的查询方式，重测green缺失与已有值为0的两种输入。
4. 独立迁移：从空文件开始，将[4,2,4,1]放进适合有序去重的容器，得到1、2、4；另建FIFO队列，先加入2再加入5，按2、5取出并确认最终为空。解释为什么去重和排队分别需要两种行为。

#include <iostream>
#include <queue>
#include <set>

int main() {
    const std::set<int> unique{4, 2, 4, 1};
    std::queue<int> work{};
    work.push(2);
    work.push(5);
    std::cout << "unique\n";
    for (const int value : unique) {
        std::cout << value << '\n';
    }
    std::cout << "queue\n";
    while (!work.empty()) {
        std::cout << work.front() << '\n';
        work.pop();
    }
    std::cout << "empty " << work.empty() << '\n';
    return 0;
}