第10.11章: 元素类型、错误规格与有效性

English

1. 键可以是什么

键的类型参数被约束为整型字符类型。实践中就是别名所覆盖的那五种：

类型 别名前缀
charstr_
wchar_twstr_
char8_tu8str_
char16_tu16str_
char32_tu32str_

键就是这些单元的序列，按字节比较。它不感知任何编码：u32str_btree_map 比较码点，str_ 容器比较 UTF-8 字节。对 UTF-8 来说，逐字节的顺序恰好与码点顺序一致，这就是为什么即使是 UTF-8 文本，str_ 家族也是正确的默认选择。

2. 映射值可以是什么

映射的值必须是移动构造不抛异常且移动赋值不抛异常的。这是类级别的约束，在你写出这个类型的那一刻就会被检查： 


error: template constraint failure for
  'template<class chtype, class mappedtype, class Allocator, long unsigned int keys_number>
   requires (integral<chtype>) && (keys_number != 0 && (keys_number & 1) == 0 &&
   (is_nothrow_move_constructible_v<mappedtype>) &&
   (is_nothrow_move_assignable_v<mappedtype>))
   class fast_io::containers::basic_str_btree_map'
note: constraints not satisfied

理由与 fast_io 所有容器背后的理由相同：结点分裂时值要被搬移。会失败的搬移会让容器处于“挪了一半”的状态且无法描述它，因此这个要求被挪到了编译期。带 noexcept 移动的类型 — ::std::size_t、::fast_io::string、::fast_io::vector，也就是你会存放的绝大多数东西 — 自动满足它。

复制仍然可能抛异常。这个约束只针对移动。复制构造函数会抛的值类型是可以的，它只会让“复制式插入”的重载变成 throws — 见第3节。

3. 错误规格

在默认分配器下，存放“移动不抛”的值的容器完全是 noexcept：每次插入、每次删除、每次查找、每个迭代器操作。你可以在编译期验证这一点，而不必相信文档： 


::fast_io::str_btree_map<::std::size_t> m;

static_assert(noexcept(m.insert_key("x", 1zu)));
static_assert(noexcept(m.insert_key_or_assign("x", 1zu)));
static_assert(noexcept(m.emplace_key("x", 1zu)));
static_assert(noexcept(m.find("x")));
static_assert(noexcept(m.erase_key("x")));
static_assert(noexcept(m.clear()));

在这种配置下分配失败会终止程序，而不是抛异常。这是刻意的默认：内存耗尽不是字符串容器能够恢复的状况，所以运行时也不会假装可以。

有两样东西能让某个成员变成 throws，而两者都体现在类型里，而不是注释里：

  1. 值类型在该操作构造它的地方可能抛。会抛的复制构造函数让 insert_key(key, lvalue) 成为 throws 函数；会抛的构造函数让它所调用的那个 emplace_key 重载成为 throws。
  2. 你选择了会抛异常的分配器。用标志包装分配器会把分配失败与契约违反变成赫布异常。 

using throwing_alloc = ::fast_io::generic_allocator_adapter<
	::fast_io::native_global_allocator,
	::fast_io::allocator_adapter_flags::throws_on_allocation_failure |
	::fast_io::allocator_adapter_flags::throws_on_violations>;

::fast_io::containers::basic_str_btree_set<char, throwing_alloc> ts;
static_assert(!noexcept(ts.insert_key("x")));   // may throw on allocation failure
static_assert(!noexcept(ts.front()));           // may throw on an empty container

有意思的是带检查的操作报告什么。读取空容器的 front() 是你程序里的 bug，不是一种运行时状况 — 但如果你要求错误可被报告，它会在 POSIX 域中以 ::std::errc::invalid_argument 报告： 


try
{
	perrln(ts.front());   // ts is empty
}
catch throws (::std::error e)
{
	perrln("caught");
	perrln(e);
}


caught
[posix](22)Invalid argument
你不需要处理任何东西。在默认分配器下 — 也就是 ::fast_io::str_btree_map 及其伙伴所使用的 — 容器是 noexcept 的，你的代码里任何地方都不需要 try/catch throws。会抛异常的分配器是给需要可恢复路径的程序准备的，必须显式选择。

4. 自己写函数签名

由于这些规格是有条件的，第6.16章里的规则就替你干了活：只从容器读取的函数是 noexcept，而插入的函数也是 noexcept — 除非容器能抛。 


// reads only: contains/find/iteration are noexcept
bool is_known(::fast_io::str_btree_set const &s, ::fast_io::string_view w) noexcept
{
	return s.contains(w);
}

// inserts: still noexcept with the default allocator
void remember(::fast_io::str_btree_set &s, ::fast_io::string_view w) noexcept
{
	s.insert_key(w);
}

当映射类型能抛时，编译器会拒绝第二种写法并告诉你原因： 


error: an unhandled herbceptions failure cannot leave a function without a
       herbceptions specification

把那个函数标成 throws，错误就消失了 — 从来没有理由退回传统异常或 catch (...)。

5. 什么会保持有效

迭代器、键视图和映射值引用都指向容器自己的存储。下面的规则很短，照着做就覆盖了使用这些类型时的全部内存安全。

操作 对迭代器和视图的影响
查找（contains、find、lower_bound、遍历） 什么都不失效。查找只读。
插入（B 树家族） 被插入元素自己的迭代器是新的；已有键保持各自的标识，因此指向其他元素的视图仍然有效。
插入（Swiss 表家族） 增长会重新哈希每个键。一旦表增长，就把所有迭代器和视图视为失效。
删除 所有指向被删元素的东西都失效。只有返回的迭代器是已知可用的。
clear()、clear_destroy()、析构 一切都失效。
移动、复制赋值、swap 指向被移出容器的迭代器失效；重新查一次键。

实践上就是：不要跨一次修改持有迭代器或键视图。重新查一次键 — 查找很便宜，而这正是你当初选这个容器的原因。 


// safe: the view is used immediately
println(s.contains("alpha"));

// unsafe: the view outlives the modification it was taken before
::fast_io::cstring_view kept{*s.find("alpha")};
s.insert_key("something else");
// kept may be dangling here

当然，被复制出来的键永远是安全的 — 由 e.key() 构造出的 ::fast_io::string 是你自己的存储，已经与容器无关了。

要点

← 第10.10章: 如何选择容器 ↑ 主页 第11章: I/O →