第10.1章: 什么是关联容器

1. 它解决的问题

程序在容器上花的大部分时间，都是在就某个名字提问：这个 token 是我认识的吗？这个配置项对应什么值？这一行我之前见过吗？用第9章的容器，你会维护一个名字的 ::fast_io::vector，每次提问都扫一遍 — 每次都是 O(n) 的查找，于是对一百万个名字提一百万个问题，就是一百万乘一百万次比较。

关联容器用查表取代顺序扫描。你交给它一个键，它把元素交还给你（或者告诉你没有这个元素）。键就是一个字符串，而容器自己决定把它放在哪里。


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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_btree_map<::std::size_t> port_of{{"http", 80zu}, {"https", 443zu}};

	println("https is known: ", port_of.contains("https"));
	println("its value:      ", port_of.find("https")->mapped());
}

输出：


https is known: 1
its value:      443

全部想法就是这些：字符串 "https"就是元素的地址。你从不计算下标，也从不需要查找。

2. 集合与映射

两种形态，你会一直用到它们：

集合 — 键就是元素。用它回答“这个字符串我之前见过吗？”，里面不存别的。
映射 — 每个键带有一个 M 类型的值。用它回答“这个字符串关联着什么？”。遍历映射得到的是带 key() 与 mapped() 的、类似 pair 的元素（第10.7章）。


::fast_io::str_btree_set seen;               // set of strings
::fast_io::str_btree_map<::std::size_t> age; // string -> size_t

一个键最多出现一次。插入重复的键不算错误，也不会产生第二个元素；它究竟是被忽略还是被覆盖，取决于你调用哪个插入函数（第10.2章）。

3. 有序还是哈希

两个家族最根本的差别只有一条：元素是否保持有序。

B 树家族（str_btree_*、str_ranked_btree_*）保持键有序。遍历即按键升序遍历，而且你能做范围查询：lower_bound、upper_bound、equal_range，还有取最小/最大键的 front()/back()。
Swiss 表家族（str_swiss_*）计算键的哈希，把它放进一张表里。遍历顺序就是哈希产生什么算什么 — 只要你不修改表，它是稳定的，但没有意义。作为交换，你得到 size()、capacity() 和 reserve()，而且完全不需要排序比较。

如果你需要“把 "b" 和 "d" 之间的所有键都给我”，那就是 B 树。如果你只需要“有/没有”或“这个键对应什么值”，Swiss 表是自然的选择。第10.10章给出一张决策表。

4. 类型是怎么拼写的

每个容器都是按字符类型参数化的类模板，并且每种字符类型都有一个便捷别名。你几乎总是用别名：

别名	键的字符类型	完整类型
`str_btree_set`	`char`	`basic_str_btree_set<char>`
`wstr_btree_set`	`wchar_t`	`basic_str_btree_set<wchar_t>`
`u8str_btree_set`	`char8_t`	`basic_str_btree_set<char8_t>`
`u16str_btree_set`	`char16_t`	`basic_str_btree_set<char16_t>`
`u32str_btree_set`	`char32_t`	`basic_str_btree_set<char32_t>`
`zu_str_btree_map`	`char`，映射到 `::std::size_t`	`basic_str_btree_map<char, ::std::size_t>`

六个容器全都遵循同样的模式 — str_、wstr_、u8str_、u16str_、u32str_ — 而 zu_str_swiss_map 就是 zu_str_btree_map 的 Swiss 表对应物。完整类型还要接受分配器，对 B 树家族还要接受结点扇出（默认 16，必须是非零偶数）：


// default: global allocator, 16 keys per node
::fast_io::str_btree_set a;

// explicit: 4 keys per node (smaller nodes, deeper tree)
::fast_io::containers::basic_str_btree_set<char, ::fast_io::native_global_allocator, 4> b;

// a thread-local-allocator variant of every container lives in ::fast_io::tlc
::fast_io::tlc::str_swiss_set c;

为什么扇出是模板参数。它是 B 树唯一暴露的调优旋钮，而合适的取值取决于你的键和映射值的规模。保持默认值是正确的；只有当你测出了理由才去改它。

5. 头文件

每个容器一个头文件，如果还想打印就再加 <fast_io.h>：


#include <fast_io_dsal/str_btree_set.h>        // ::fast_io::str_btree_set
#include <fast_io_dsal/str_btree_map.h>        // ::fast_io::str_btree_map
#include <fast_io_dsal/str_ranked_btree_set.h> // ::fast_io::str_ranked_btree_set
#include <fast_io_dsal/str_ranked_btree_map.h> // ::fast_io::str_ranked_btree_map
#include <fast_io_dsal/str_swiss_set.h>        // ::fast_io::str_swiss_set
#include <fast_io_dsal/str_swiss_map.h>        // ::fast_io::str_swiss_map
#include <fast_io.h>                          // println / print / to

所有内容都在 ::fast_io 命名空间里。底层实现上，类模板位于 ::fast_io::containers；只有当你需要写出分配器或扇出时才会用到那个命名空间。

6. 键是拥有的，查找只用视图

这是唯一一条决定你写每一行代码的设计决策，所以值得讲清楚。

插入会复制键。容器为这些字符加上一个结尾的 '\0' 分配空间并复制它们，它不会保留你的指针。循环里的局部字符串、一个临时的 ::fast_io::string、你先前读入的文件中的一小段 — 它们都可以安全地插入，然后就可以消亡：


{
	::fast_io::string temporary = ::fast_io::concat_fast_io("session-", 42);
	s.insert_key(::fast_io::string_view(temporary.c_str(), temporary.size()));
}	// temporary is destroyed here; the key inside s is still valid
println(s.contains("session-42"));	// 1

查表只接受视图。contains、find、erase_key 等等都接受 ::fast_io::string_view（指针 + 长度）。不发生任何分配，也不复制任何东西，你永远不需要把查找键包进 ::fast_io::string：


println(s.contains("session-42"));   // string literal -> view, no allocation
println(s.count("nope"));            // 0
s.erase_key("session-42");           // erase by view

遍历交给你的同样是视图。解引用集合的迭代器得到一个 ::fast_io::cstring_view，指向容器自己那份键的副本 — 以空字符结尾、打印便宜，并且只在该元素存在期间有效（第10.11章）。

字符串字面量可以转换，char const * 不行。视图类型有一个从数组（char const (&)[N]）的隐式构造函数，这就是 insert_key("alpha") 能编译的原因。而一个普通的指针变量没有这样的构造函数：


char const *p = "alpha";
s.insert_key(p);                               // error: no conversion
s.insert_key(::fast_io::mnp::os_c_str(p));     // fine: null-terminated C string

打印也是如此：println(p) 不能编译，println(::fast_io::mnp::os_c_str(p)) 可以。这是刻意设计的 — 裸指针并不说明字符串有多长，而两种不同的回答对应两种不同的包装器（os_c_str 用于以空字符结尾的字符串，os_str_known_size_without_null_terminated 用于你已经知道长度的情形）。

要点

关联容器按键查找元素，而不是按位置。
集合存放键；映射存放键和值，通过 key() / mapped() 访问。
B 树（str_btree_*）保持键有序，因此支持范围查询以及 front()/back()。
Swiss 表（str_swiss_*）对键做哈希，因此有 size()、capacity()、reserve()，但没有顺序。
有序统计 B 树（str_ranked_btree_*）是同时记录子树规模的 B 树（第10.8章）。
插入会把键复制进容器；查找只传视图，因此查找永不分配内存。
每个容器的键都有 str_ / wstr_ / u8str_ / u16str_ / u32str_ 变体。