第10.10章: 如何选择容器

1. 三个问题

选容器是问三个关于你的程序的问题，而不是关于实现的问题。

你需要顺序吗？有序输出、前缀扫描、最小的键、“这个之后的下一个”。如果需要，你就需要 B 树，Swiss 表出局。
你需要计数还是排名？“一共有多少个键？”还是“中位数是多少？”。如果需要，你需要 str_ranked_btree_*（两者都支持）或 str_swiss_*（只支持 size()）。
你需要预先定好表大小吗？已知大小的批量装载，在能一次调用 reserve() 时最便宜，而这是 Swiss 表家族提供的。

2. 决策表

你的程序需要	使用
只要成员判断：“这个字符串我见过吗？”	`str_swiss_set`
每个键有一个值，按精确键查找	`str_swiss_map<M>`
按键有序打印	`str_btree_set` / `str_btree_map<M>`
范围查询：某前缀的所有键、两个键之间的所有键	`str_btree_set` / `str_btree_map<M>`
最小 / 最大的键	`str_btree_*`（`front()`、`back()`）
对每个键计数或累加一个值	报告需要有序时用 `str_btree_map<M>`，否则用 `str_swiss_map<M>`
便宜地取得元素个数	`str_ranked_btree_` 或 `str_swiss_`
第 n 小的键、中位数、百分位	`str_ranked_btree_set` / `str_ranked_btree_map<M>`
批量装载前预先定好大小	`str_swiss_*`（`reserve(n)`）
非 `char` 的键	上面任一项的 `wstr_` / `u8str_` / `u16str_` / `u32str_` 变体

默认是 str_swiss_set / str_swiss_map。大多数代码只问“这个键在吗？”或“它的值是什么？”。从这里开始，等你发现确实需要顺序时再换到 B 树 — 而不是提前换。

3. 把选择集中在一个地方

你不必在每个调用处都绑定某个具体容器。给这个类型起一次名字，然后针对六个家族共有的操作写程序其余部分：


#include <fast_io_dsal/str_swiss_set.h>
#include <fast_io.h>

using namespace ::fast_io::io;

using word_set = ::fast_io::str_swiss_set;   // the only line to change later

bool is_known(word_set const &s, ::fast_io::string_view w) noexcept
{
	return s.contains(w);
}

int main()
{
	word_set s;
	s.insert_key("alpha");
	s.insert_key("beta");
	println(is_known(s, "alpha"));   // 1
	println(is_known(s, "gamma"));   // 0
}

这样改成 ::fast_io::str_btree_set 就只是一行编辑。上面的代码原样编译，因为 insert_key、contains、erase_key、find/find_key、is_empty、clear 以及遍历在每个家族上都有相同的名字和含义。

这样切换时坏掉的，正是本章警告过的那些：size()（普通 B 树上没有）、nth_element()（只有有序统计 B 树有）、reserve() / capacity()（只有 Swiss 表有）、以及 lower_bound / upper_bound / front / back（只有 B 树家族有）。那些就是容器特有的能力 — 如果你用到它们，说明你有意选定了一个家族。

4. 六个容器都成立的事实

键是 ::std::integral 的字符序列；容器为每个键保存自己那份以空字符结尾的副本。
查找接受视图，因此查找永不分配。
遍历给出键视图（::fast_io::cstring_view），对映射则是带 key() 与 mapped() 的元素。
不可能出现重复键：插入已存在的键要么什么都不做，要么覆盖，绝不重复。
它们都可复制、可移动、可 clear，并且都支持 wstr_/u8str_/u16str_/u32str_ 别名。
增长与收缩都通过分配器分配；分配失败会终止程序，除非你选择了会抛异常的分配器（第10.11章）。
映射的值必须是移动构造与移动赋值都不抛异常的（第10.11章）。

5. 常见错误

错误	实际会发生什么	应该这样做
用循环在一个 `::fast_io::vector<::fast_io::string>` 里查找	每次查找都要完整扫一遍。	把字符串插进集合，然后调用 `contains`。
依赖 Swiss 表的遍历顺序	那是哈希顺序；换一组键、表增长或一次删除都会打乱它。	需要顺序就用 B 树。
在一次 Swiss 映射插入前后一直持有迭代器	增长会重新哈希，迭代器悬空。	需要时重新查一次键。 56b\|
对 `str_btree_set` 写 `s.size()`	不能编译：没有 `size()`。	`::std::ranges::distance(s)`、`str_ranked_btree_set`，或者 `str_swiss_set`。
为了查一个键而先构造一个 `::fast_io::string`	每次查找都多一次分配和复制。	把你已经有的视图传进去，例如 `line.subview(pos, len)`。
在 `insert_key` 之前用 `contains` 做预检查	本来一次查找就够，却查了两次。	使用 `insert_key` 返回的 `bool`。

要点

需要顺序或范围？B 树。只需要精确键？Swiss 表。需要计数或排名？有序统计 B 树。
默认用 str_swiss_set / str_swiss_map；当顺序成为需求时再换到 B 树。
计数就是一次查找加一次赋值；映射家族只影响报告是否有序。
size() 在有序统计 B 树和 Swiss 表上有，普通 B 树上没有。
用 using 把容器类型命名一次，然后一行编辑就能切换整个程序。
六个容器共享同一套 insert / contains / find_key / erase / 遍历接口，所以大部分代码与容器无关。