Ch10.8: Ranked B-trees: `size()` and `nth_element()`

1. A B-tree That Counts

str_ranked_btree_set and str_ranked_btree_map are the B-tree containers from Ch10.4–10.6 plus one extra piece of bookkeeping: every subtree remembers how many keys it holds. That buys you two things the plain B-tree does not have.

size() — the number of elements, in constant time. No iteration needed (compare Ch10.5).
nth_element(n) — an iterator to the element at rank n in sorted order, without walking the n elements before it.

Everything else is identical: same headers shape, same insert_key / contains / find_key / erase_key / ordered iteration. You only pay for the rank bookkeeping, so use the ranked variant when you need ranks and the plain one otherwise.


#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. Ranks Are Zero-Based Positions in Sorted Order

nth_element(0) is the smallest key, nth_element(1) the second smallest, and nth_element(size() - 1) the largest. It is a position in the sorted sequence, not an insertion order:


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


alpha
charlie
echo

The cost is the height of the tree, not the rank: at every node the container compares n against the size of each child subtree and descends into only one of them. Asking for the 900,000th key out of a million does not walk 900,000 keys.

Asking for a rank that does not exist is a contract violation. On an empty container, or with n >= size(), the program terminates — or, if you opted into throwing allocators, throws ::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
}

That is the same checked/`_unchecked` split you know from vectors (Ch9.5): nth_element(n) checks, and nth_element_unchecked(n) does not.

3. The Median, and Other Quantiles

The classic use is the median. With size() and nth_element it is two lines:


#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

With an even number of elements there is no single middle, so size() / 2 picks the upper of the two candidates. That is a choice, not a law: pick whichever convention your problem wants.

Any quantile is the same shape — the 90th percentile of a million elements is nth_element(size() * 90u / 100u). Because you get an iterator back, you can also read the neighbours, or start iterating from there:


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

4. When Not to Use It

Rank tracking is not free: every insert and erase has to fix up the counts along the path it touched, and every node carries the extra field. If you never ask for size() or nth_element(), the plain str_btree_* does the same job with less work per operation.

You need	Use
Sorted iteration, range queries, smallest/largest key	`str_btree_set` / `str_btree_map`
Sorted iteration plus element count, or the n-th key by rank	`str_ranked_btree_set` / `str_ranked_btree_map`
Only membership and value lookup, no order	`str_swiss_set` / `str_swiss_map` (Ch10.9)

size() on a ranked B-tree is exact and cheap. Unlike the plain B-tree, you can call it in a loop condition without turning the loop quadratic.

Key takeaways