Ch10.10: Choosing a Container

1. Three Questions

Picking the container is three questions about your program, not about the implementation.

Do you ever need order? Sorted output, a prefix scan, the smallest key, “the next one after this”. If yes, you need a B-tree, and the Swiss table is out.
Do you need a count, or a rank? “How many keys are there?” or “what is the median?”. If yes, you need str_ranked_btree_* (both) or str_swiss_* (size() only).
Do you need to pre-size the table? A bulk load of known size is cheapest when you can call reserve() once, which the Swiss family provides.

2. The Table

What your program needs	Use
Membership only: “have I seen this string?”	`str_swiss_set`
Value per key, looked up by the exact key	`str_swiss_map<M>`
Print the keys in sorted order	`str_btree_set` / `str_btree_map<M>`
Range query: all keys with a prefix, between two keys	`str_btree_set` / `str_btree_map<M>`
Smallest / largest key	`str_btree_*` (`front()`, `back()`)
Counting or accumulating one value per key	`str_btree_map<M>` if the report should come out sorted, `str_swiss_map<M>` otherwise
The element count, cheaply	`str_ranked_btree_` or `str_swiss_`
The n-th smallest key, medians, percentiles	`str_ranked_btree_set` / `str_ranked_btree_map<M>`
Pre-size before a bulk load	`str_swiss_*` (`reserve(n)`)
Non-`char` keys	the `wstr_` / `u8str_` / `u16str_` / `u32str_` variant of any of the above

The default is str_swiss_set / str_swiss_map. Most code only ever asks “is this key there?” or “what is its value?”. Start there, and move to a B-tree when you discover that you need order — not before.

3. Keep the Choice in One Place

You do not have to commit to a container at every call site. Give the type a name once, and write the rest of the program against the operations all six families share:


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

using namespace ::fast_io::io;

using word_set = ::fast_io::str_swiss_set;   // the only line to change later

bool is_known(word_set const &s, ::fast_io::string_view w) noexcept
{
	return s.contains(w);
}

int main()
{
	word_set s;
	s.insert_key("alpha");
	s.insert_key("beta");
	println(is_known(s, "alpha"));   // 1
	println(is_known(s, "gamma"));   // 0
}

Switching to ::fast_io::str_btree_set is then a one-line edit. The code above compiles unchanged, because insert_key, contains, erase_key, find/find_key, is_empty, clear and iteration exist on every family with the same names and meanings.

What breaks on such a switch is exactly what this chapter warned about: size() (not on the plain B-tree), nth_element() (ranked B-tree only), reserve() / capacity() (Swiss only), and lower_bound / upper_bound / front / back (B-tree family only). Those are the container-specific capabilities — if you use them, you have chosen a family on purpose.

4. Things That Are True of All Six

Keys are ::std::integral character sequences; the container stores its own null-terminated copy of each key.
Lookups take a view, so a lookup never allocates.
Iteration yields a key view (::fast_io::cstring_view) or, for maps, an element with key() and mapped().
Duplicate keys are impossible: inserting an existing key either does nothing or overwrites, never duplicates.
All of them are copyable, movable, clear-able, and work with the wstr_/u8str_/u16str_/u32str_ aliases.
Growth and shrinking allocate through an allocator; a failed allocation terminates the program unless you opted into a throwing allocator (Ch10.11).
Map values must be nothrow-move-constructible and nothrow-move-assignable (Ch10.11).

5. Common Mistakes

Mistake	What actually happens	Do this instead
Searching a `::fast_io::vector<::fast_io::string>` with a loop	One full scan per lookup.	Insert the strings into a set and call `contains`.
Depending on the iteration order of a Swiss table	It is hash order; a different key set, growth, or an erase reshuffles it.	Use a B-tree if you need order.
Holding an iterator across an insert into a Swiss map	Growth rehashes; the iterator is dangling.	Look the key up again when you need it.
`s.size()` on `str_btree_set`	Does not compile: no `size()`.	`::std::ranges::distance(s)`, `str_ranked_btree_set`, or `str_swiss_set`.
Building a `::fast_io::string` just to look a key up	An allocation and a copy per lookup.	Pass the view you already have, e.g. `line.subview(pos, len)`.
Using `contains` as a pre-check before `insert_key`	Two lookups where one would do.	Use the `bool` returned by `insert_key`.

Key takeaways

Need order or ranges? B-tree. Need only exact keys? Swiss table. Need counts or ranks? Ranked B-tree.
Default to str_swiss_set / str_swiss_map; move to a B-tree when order becomes a requirement.
Counting is a lookup plus an assign; the map family only changes whether the report is sorted.
size() exists on ranked B-trees and Swiss tables, not on plain B-trees.
Name the container type once with using, then switch the whole program with one edit.
All six share the same insert / contains / find_key / erase / iterate interface, so most code is container-agnostic.