第10.4章: 按键查找

1. 两个问题

每次查找都在回答两个问题中的一个，各有一个函数对应：

“这个键在不在？” — contains(key) 返回 bool。大多数时候你要的就是这个。
“这个键在哪里？” — find(key) 返回一个迭代器，你拿它与 cend() 比较。

两者都接受视图，所以查找时既不分配也不复制。字符串字面量可以直接用：


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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_btree_set s;
	s.insert_key("alpha");
	s.insert_key("beta");

	println(s.contains("alpha"));   // 1
	println(s.contains("gamma"));   // 0
	println(s.count("beta"));       // 1 — count is 0 or 1, never more
}


1
0
1

count 之所以存在，是因为同样的代码形状也会用在键可能重复的其他容器上；在这里它就是结果类型为大小的 contains。只要“有/没有”，就用 contains。

find_key 是 find 的同义词。B 树容器两个名字都提供。Swiss 表容器只提供 find_key，因为 find 会与“按值查找元素”的普通容器约定冲突。既然你总是知道自己找的是什么，那就用 find_key，代码就能在六个容器之间通用。

2. `find` 和它返回的迭代器

find 返回的迭代器要么指向该元素，要么是 cend()。解引用元素得到 ::fast_io::cstring_view — 容器自己那份键的副本：


auto it{s.find("beta")};
if (it != s.cend())
{
	println("found: ", *it);
}
else
{
	println("not found");
}


found: beta

与 cend() 比较就是惯用法。没有 npos、没有下标、没有可空指针：等于 cend() 的迭代器就是“未找到”的结果。

不要解引用 cend()。那句 if (it == s.cend()) 检查不是可有可无的礼貌 — 没有指向元素的迭代器什么也给不了你。

3. 范围查询（仅 B 树家族）

因为 B 树保持键有序，它能回答关于键的范围的问题。Swiss 表容器做不到，这也是选择 B 树的主要理由。

调用	返回什么的位置
`lower_bound(k)`	第一个不小于 `k` 的键
`upper_bound(k)`	第一个大于 `k` 的键
`equal_range(k)`	两者，打包在 `.first` 与 `.second` 中


::fast_io::str_btree_set s;
for (auto k : {::fast_io::cstring_view("user:101"), ::fast_io::cstring_view("user:42"),
			   ::fast_io::cstring_view("admin:7"), ::fast_io::cstring_view("user:7")})
{
	s.insert_key(k);
}

auto lb{s.lower_bound("user:42")};
auto ub{s.upper_bound("user:42")};
println("lower_bound(user:42) = ", *lb);   // user:42
println("upper_bound(user:42) = ", *ub);   // user:7


lower_bound(user:42) = user:42
upper_bound(user:42) = user:7

键按纯字节串比较，所以 "user:101" 排在 "user:42" 之前：'1' < '4'。排序是字典序，不是数值序。如果你需要数字按数值排序，就把它们补齐到固定宽度，或者把数值部分存到别处。

扫描前缀

“所有以 user: 开头的键”就是 lower_bound 加一个带提前退出的循环。lower_bound 把你放到第一个候选处；只要前缀仍然匹配就继续：


for (auto it{s.lower_bound("user:")}; it != s.cend(); ++it)
{
	::fast_io::string_view k{*it};
	if (!k.starts_with(::fast_io::string_view("user:")))
	{
		break;
	}
	println("  ", *it);
}


  user:101
  user:42
  user:7

这次扫描的代价是查找加上每个匹配键一步 — 你永远不会走过不匹配的键。

4. 完整配方

把上面组合起来，一次带合理兜底的查找长这样：


bool has_user(::fast_io::str_btree_set const &db, ::fast_io::string_view name) noexcept
{
	return db.contains(name);
}

有两点值得注意。第一，参数是 ::fast_io::string_view，不是 ::fast_io::string，也不是 ::fast_io::cstring_view：查找从不需要所有权，而普通视图是要求最弱的形式，任何调用者都能把手里有的东西传进来。第二，函数是 noexcept — 在默认分配器下，六个容器中的所有查找都是 noexcept，因为查找既不能分配也不能失败（第10.11章）。

当容器是 const 时，你得到的是 const_iterator — 从非 const 的集合上得到的也是它，因为集合的键是不可变的。对映射来说，非 const 容器给出的 iterator 的 mapped() 是可以写入的（第10.7章）。

要点

查找接受视图：不分配、不复制，字面量可直接使用。
contains(key) 回答“有/没有”；count(key) 是 0 或 1。
find / find_key 返回迭代器；与 cend() 比较，解引用得到 cstring_view。
Swiss 容器只有 find_key；为了代码通用，请处处使用这个名字。
lower_bound / upper_bound / equal_range 只存在于 B 树家族。
前缀扫描就是 lower_bound(prefix) 加一个在前缀不再匹配时停止的循环。
键按字节排序："user:101" 在 "user:42" 之前。
在默认分配器下所有查找都是 noexcept。