Ch10.5: Iterating

1. The Range-For, and What You Get Out

Iteration is a range-for over begin()/end(), same as every other container. What an element is differs between sets and maps:

Container	`*it` gives	Read a key	Read/write the value
`str_btree_set`, `str_ranked_btree_set`	`::fast_io::cstring_view`	the value itself	there is no value
`str_swiss_set`	`::fast_io::cstring_view`	the value itself	there is no value
`str_btree_map<M>`, `str_ranked_btree_map<M>`	a proxy with `key()` / `mapped()`	`e.key()`	`e.mapped()` (writable)
`str_swiss_map<M>`	a reference to a key/value pair	`e.key()`	`e.mapped()` (writable via non-const iterator)


#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

There is no first and second. A map element is not a pair. It has key() and mapped(), and that is all. Written e.key(), the code says what it reads; written e.first, you would have to remember which half is which.

2. Order

The B-tree family iterates in ascending key order. Always. That is a guarantee you can rely on, not an implementation detail: after inserting "c", "a", "b" in that order, the loop above prints a, b, c.

The Swiss-table family makes no ordering promise. The order is determined by the hash of the keys, so it is reproducible for the same input — but it is not sorted, and it changes when the table grows or when you erase. Never write code that depends on the sequence:


::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

If you need a sorted result out of a Swiss table, copy the keys into a vector and sort that; do not hope for iteration order.

3. Reverse Iteration

To walk the elements backwards, wrap the container in ::std::ranges::reverse_view. It is a view, so nothing is copied, and it works on all six containers:


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


  c = 3
  b = 2
  a = 1

For a B-tree that means descending key order. For a Swiss table it is just “the same arbitrary order, backwards”.

The same view works on sets, where the element is the key itself:


::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

Prefer the view over calling rbegin() by hand. A loop written as for (auto it{m.crbegin()}; it != m.crend(); ++it) also works, but the view says “iterate this backwards” at the point where the range is used and cannot get the crend() comparison subtly wrong. Use crbegin()/crend() when you want to spell the iterators out: they are the const pair and therefore work on const and non-const containers alike.

4. First and Last Element

The B-tree family has front() and back() for the smallest and largest key, in constant time — no iteration needed:


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

For a set they return the key view directly: println(s.front());. Both are checked: calling them on an empty container is a contract violation, which terminates the program (or throws ::std::errc::invalid_argument if you opted into throwing allocators — Ch10.11).

The Swiss table has no front()/back(), since “first” and “last” mean nothing without an order. Its begin() points at the first occupied slot in table order.

5. Counting Elements in a B-tree

The B-tree containers do not store a total element count, so they have no size(). If you write one, the compiler says so:


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

That is not an oversight. Keeping a counter up to date on every insert, erase and node merge costs work on the hot path, and most programs never need the number. When you do need it, iterate:


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

If “how many elements are there” is a question your program asks often, use a container that stores the answer: str_ranked_btree_set / str_ranked_btree_map have size() (Ch10.8), and so do the Swiss-table containers (Ch10.9).

Container	`is_empty()`	`size()`	`front()`/`back()`
`str_btree_set` / `str_btree_map`	yes	no	yes
`str_ranked_btree_set` / `str_ranked_btree_map`	yes	yes	yes
`str_swiss_set` / `str_swiss_map`	yes	yes	no

Key takeaways

Iterate with a range-for; sets yield cstring_view, maps yield elements with key() and mapped().
There is no first/second in a map element.
B-tree iteration is ascending by key — guaranteed. Swiss-table iteration is unordered — never rely on it.
Use ::std::ranges::reverse_view to iterate backwards; it works on every one of the six containers.
front()/back() give the smallest/largest key on the B-tree family, checked, constant time.
B-tree containers have no size(); count with ::std::ranges::distance or pick a container that tracks it.