第10.3章: contains()：成员测试

1. 你最常用的函数

contains(key) 只回答一个问题：这个键在容器里吗？它返回 bool，从不分配内存，并且在默认分配器下是 noexcept。六个容器全都有它，名字相同、行为也相同。

#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
}

1
0

在真实程序里，接触集合的大部分代码都长这样：一个过滤器、一个守卫、一步校验。这就是为什么先讲 contains，其他都放在后面。

2. 它接受视图，所以什么都不复制

参数是 ::fast_io::string_view — 一个指针加一个长度。没有分配、没有复制、没有临时字符串。任何能产生视图的东西都可以用：

最后一行正是“字符串集合上值得有 contains”的理由。你可以在不构造 ::fast_io::string 的情况下，测试正在扫描的缓冲区中的一小段 — 一个 token、分隔符之间的一段字段、去掉换行的一行：

::fast_io::str_btree_set dict;
dict.insert_key("the");
dict.insert_key("quick");
dict.insert_key("fox");

::fast_io::string_view line{"the quick brown fox"};
::std::size_t pos{};
while (pos < line.size())
{
	auto space{line.find(::fast_io::string_view(" "), pos)};
	if (space == ::fast_io::containers::npos)
	{
		space = line.size();
	}
	auto token{line.subview(pos, space - pos)};
	println("[", token, "] known: ", dict.contains(token));
	pos = space + 1;
}

[the] known: 1
[quick] known: 1
[brown] known: 0
[fox] known: 1

3. contains、find 与 count 的分工

这三者回答相关的问题。选对那个能让代码的意图更清楚：

find 没有办法“悄悄地”失败：迭代器要么指向某个元素，要么等于 cend()。如果你只需要一个“有/没有”的答案，if (s.find(k) != s.cend()) 就是更容易出错的 if (s.contains(k))。

4. 常见模式

输入去重

只保留第一次出现，有两种写法。要么先查一下：

for (auto word : words)
{
	if (!seen.contains(word))
	{
		seen.insert_key(word);
		unique.push_back(word);
	}
}

要么让插入过程告诉你，这样只查一次而不是两次：

for (auto word : words)
{
	if (seen.insert_key(word))   // true only the first time
	{
		unique.push_back(word);
	}
}

两种都对；如果你反正要插入，就选第二种。当容器不能被修改时，contains 才是正确的工具。

用提前返回来做守卫

void handle(::fast_io::str_swiss_set const &allowed, ::fast_io::string_view name) throws
{
	if (!allowed.contains(name))
	{
		println("rejected: ", name);
		return;
	}
	println("accepted: ", name);
}

注意参数：::fast_io::str_swiss_set const & 加一个视图。函数调用时没有复制任何东西，而 const 引用表明“这次调用只读取这个集合”。

映射的成员判断

在映射上，contains 只问键，从不问值。当你不确定某个键是否存在、却又想读它的值时，这正是你需要的检查：

::fast_io::str_btree_map<::std::size_t> age{{"ada", 36zu}};
println(age.contains("ada"));     // 1
println(age.contains("alan"));    // 0 — no such key

5. “包含”的确切含义

比较的是键的字节，完全按原样：区分大小写、不修剪、不做 Unicode 折叠。"Alpha" 与 "alpha" 是两个不同的键。

空字符串也是普通的键。它不在空容器里，但可以像其他键一样被插入：

println(dict.contains(""));   // 0
dict.insert_key("");
println(dict.contains(""));   // 1

0
1

6. 代价与错误规格

在默认分配器下，六个容器上的 contains 都是 noexcept，而且这一点是在编译期测量的：

::fast_io::str_btree_set s;
::fast_io::str_swiss_set ss;
static_assert(noexcept(s.contains("x")));
static_assert(noexcept(ss.contains("x")));

查找不可能分配（它只接受视图），也不可能失败（键不存在是一个答案，不是错误），所以没有需要报告的东西，也没有需要处理的东西。这就是为什么成员测试可以从任何 noexcept 函数里调用，包括析构函数和 constexpr 代码。

从算法角度说，B 树家族沿一条从根到叶的路径比较键，Swiss 表家族则把键哈希一次并做探测。两者都不遍历元素，这正是集合之所以为集合的原因。

要点

• contains(key) 返回 bool；这是询问成员关系的默认方式。
• 它接受视图，因此不分配、不复制任何字符串 — 即使是从更大缓冲区里切出的一个 token 也一样。
• 只有当你需要元素本身（而不只是答案）时才用 find/find_key。
• count 就是写成数字的 contains；请用 contains。
• 当你反正要插入时，插入返回的 bool 就给出了答案，无需第二次查找。
• 键按精确字节比较：区分大小写、不做规范化；空字符串是合法的键。
• char const * 必须包成 ::fast_io::mnp::os_c_str(p) — 这是刻意设计的编译错误。
• 在默认分配器下 contains 是 noexcept，因此在 noexcept 函数和编译期代码中都安全。