第10.8章: 有序统计 B 树：size() 与 nth_element()

1. 会计数的 B 树

str_ranked_btree_set 与 str_ranked_btree_map 就是第10.4–10.6章里的 B 树容器，外加一份额外的记账：每棵子树都记住自己含有多少个键。这换来普通 B 树没有的两样东西。

• size() — 常数时间得到元素个数，不需要遍历（对比第10.5章）。
• nth_element(n) — 指向有序顺序中排名第 n 的元素的迭代器，而不必走过它前面那 n 个元素。

其他一切完全相同：同样的头文件组织形式，同样的 insert_key / contains / find_key / erase_key / 有序遍历。你只为排名记账付代价，所以需要排名时用带排名的版本，否则用普通版本。

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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_ranked_btree_set s;
	for (auto k : {::fast_io::cstring_view("delta"), ::fast_io::cstring_view("alpha"),
				   ::fast_io::cstring_view("charlie"), ::fast_io::cstring_view("bravo"),
				   ::fast_io::cstring_view("echo")})
	{
		s.insert_key(k);
	}

	println("size: ", s.size());
	for (auto const &e : s) { println("  ", e); }
}

size: 5
  alpha
  bravo
  charlie
  delta
  echo

2. 排名是有序顺序中从 0 开始的位置

nth_element(0) 是最小的键，nth_element(1) 是第二小的，nth_element(size() - 1) 是最大的。它是排序序列中的位置，不是插入顺序：

println(s.nth_element(0));   // alpha
println(s.nth_element(2));   // charlie
println(s.nth_element(4));   // echo

alpha
charlie
echo

代价是树的高度，而不是排名：在每个结点上，容器把 n 与各个子树的规模比较，然后只下降到其中一棵。在一百万个键里问第 900,000 个，并不需要走过 900,000 个键。

询问一个不存在的排名是违反契约。在空容器上，或者 n >= size() 时，程序会终止 — 如果你选择了会抛异常的分配器，则抛出 ::std::errc::invalid_argument：

try
{
	auto it{ts.nth_element(5zu)};   // ts has one element
	println(*it);
}
catch throws (::std::error e)
{
	perrln(e);                      // [posix](22)Invalid argument
}

这就是你在 vector 上熟悉的“带检查/`_unchecked`”之分（第9.5章）：nth_element(n) 做检查，nth_element_unchecked(n) 不做。

3. 中位数与其他分位数

经典用法是中位数。有了 size() 和 nth_element，只要两行：

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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_ranked_btree_map<::std::size_t> m;
	m.insert_key("d", 4zu);
	m.insert_key("a", 1zu);
	m.insert_key("c", 3zu);
	m.insert_key("b", 2zu);

	auto mid{m.nth_element(m.size() / 2u)};
	println("median key: ", mid->key(), " value: ", mid->mapped());
}

median key: c value: 3

元素个数为偶数时没有唯一的中间元素，所以 size() / 2 取两个候选中的靠后者。这是一种选择，不是定律：按你的问题需要挑一种约定。

任何分位数都是同样的形状 — 一百万个元素的第 90 百分位是 nth_element(size() * 90u / 100u)。因为返回的是迭代器，你还可以读它的邻居，或者从那里开始遍历：

auto p90{m.nth_element(m.size() * 90u / 100u)};
for (auto it{p90}; it != m.cend(); ++it)
{
	println("  ", it->key());
}

4. 什么时候不该用它

排名记账不是免费的：每次插入和删除都要修正所经路径上的计数，而且每个结点都多带一个字段。如果你从不需要 size() 或 nth_element()，普通的 str_btree_* 用每次操作更少的工作量就能干同样的活。

要点

• str_ranked_btree_* 是记录子树规模的 B 树家族。
• size() 是常数时间；普通 B 树根本没有 size()。
• nth_element(n) 返回指向第 n 小键（从 0 开始）的迭代器，时间与树高成正比。
• nth_element(n) 带检查（终止 / 抛出 errc::invalid_argument）；nth_element_unchecked(n) 不带。
• 中位数和百分位查询各只需一次调用。
• 不需要排名时就用普通 B 树 — 那份记账不是免费的。