第10.5章: 遍历

1. range-for，以及你会拿到什么

遍历就是用 begin()/end() 写 range-for，和其他容器一样。元素是什么，在集合和映射之间不同：

容器	`*it` 给出	读键	读/写值
`str_btree_set`、`str_ranked_btree_set`	`::fast_io::cstring_view`	值本身就是键	没有值
`str_swiss_set`	`::fast_io::cstring_view`	值本身就是键	没有值
`str_btree_map<M>`、`str_ranked_btree_map<M>`	带 `key()` / `mapped()` 的代理对象	`e.key()`	`e.mapped()`（可写）
`str_swiss_map<M>`	对键/值对的引用	`e.key()`	`e.mapped()`（通过非 const 迭代器可写）


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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_btree_map<::std::size_t> m{{"c", 3zu}, {"a", 1zu}, {"b", 2zu}};

	for (auto const &e : m)
	{
		println("  ", e.key(), " = ", e.mapped());
	}
}


  a = 1
  b = 2
  c = 3

没有 first 和 second。映射元素不是 pair。它有 key() 和 mapped()，仅此而已。写成 e.key()，代码就说清了读的是什么；写成 e.first，你就得记着哪一半是哪一半。

2. 顺序

B 树家族按键升序遍历，一贯如此。这是你可以依赖的保证，而不是实现细节：依次插入 "c"、"a"、"b" 之后，上面的循环会打印 a、b、c。

Swiss 表家族不作任何顺序保证。顺序由键的哈希决定，所以对相同输入它是可复现的 — 但它不是有序的，并且会在表增长或你删除元素时改变。绝不要写出依赖这个序列的代码：


::fast_io::str_swiss_set s;
s.insert_key("hello");
s.insert_key("world");
s.insert_key("foo");
for (auto const &e : s) { println(e); }   // some order; not sorted

如果你需要从 Swiss 表得到有序结果，就把键复制到一个 vector 里再排序；不要指望遍历顺序。

3. 反向遍历

要倒着走元素，把容器包进 ::std::ranges::reverse_view。它是一个视图，因此不复制任何东西，并且对六个容器都适用：


for (auto const &e : ::std::ranges::reverse_view(m))
{
	println("  ", e.key(), " = ", e.mapped());
}


  c = 3
  b = 2
  a = 1

对 B 树来说这意味着键降序。对 Swiss 表来说它只是“同样的任意顺序，反过来”。

同一个视图也能用在集合上，那里元素本身就是键：


::fast_io::str_btree_set s{{::fast_io::string_view("a"), ::fast_io::string_view("b")}};
for (auto const &e : ::std::ranges::reverse_view(s))
{
	println("  ", e);
}


  b
  a

优先用这个视图，而不是手动调用 rbegin()。写成 for (auto it{m.crbegin()}; it != m.crend(); ++it) 的循环也能用，但视图在使用范围的地方就表达了“把它倒着遍历”，并且不会把 crend() 的比较写错。当你想把迭代器写出来时，用 crbegin()/crend()：它们是 const 的那一对，因此对 const 和非 const 容器都适用。

4. 第一个与最后一个元素

B 树家族有 front() 和 back()，分别给出最小和最大的键，且是常数时间 — 不需要遍历：


println("first key: ", m.front().key());
println("last key:  ", m.back().key());

对集合来说它们直接返回键视图：println(s.front());。两者都是带检查的：在空容器上调用它们是违反契约，会终止程序（如果你选择了会抛异常的分配器，则抛出 ::std::errc::invalid_argument — 第10.11章）。

Swiss 表没有 front()/back()，因为离开顺序，“第一个”和“最后一个”毫无意义。它的 begin() 指向按表顺序第一个被占用的槽位。

5. 统计 B 树中的元素个数

B 树容器不保存元素总数，因此没有 size()。如果你写了，编译器会告诉你：


error: 'fast_io::str_btree_set' {aka 'class fast_io::containers::basic_str_btree_set<char, ...>'}
       has no member named 'size'

这不是疏忽。在每次插入、删除和结点合并时都维护一个计数器，会在热路径上付出代价，而大多数程序从不需要这个数字。当你确实需要时，就遍历：


auto n{::std::ranges::distance(m)};   // walks every element
println("elements: ", n);

如果“一共有多少元素”是你的程序经常问的问题，那就用会保存这个答案的容器：str_ranked_btree_set / str_ranked_btree_map 有 size()（第10.8章），Swiss 表容器也有（第10.9章）。

容器	`is_empty()`	`size()`	`front()`/`back()`
`str_btree_set` / `str_btree_map`	有	没有	有
`str_ranked_btree_set` / `str_ranked_btree_map`	有	有	有
`str_swiss_set` / `str_swiss_map`	有	有	没有

要点

用 range-for 遍历；集合给出 cstring_view，映射给出带 key() 与 mapped() 的元素。
映射元素里没有 first/second。
B 树的遍历按键升序 — 有保证。Swiss 表的遍历无序 — 绝不要依赖。
用 ::std::ranges::reverse_view 反向遍历；它对六个容器都适用。
B 树家族的 front()/back() 给出最小/最大的键，带检查、常数时间。
B 树容器没有 size()；用 ::std::ranges::distance 统计，或者选一个会记录它的容器。