Ch10.1: What an Associative Container Is

1. The Problem It Solves

Programs spend most of their container time asking questions about a name: is this token one I know? what value belongs to this setting? have I already seen this line? With the containers from Chapter 9 you would keep a ::fast_io::vector of names and scan it for every question — an O(n) search each time, so a million questions against a million names is a million times a million comparisons.

An associative container replaces the scan with a lookup. You hand it a key, it hands you the element (or tells you it is not there). The key is a string, and the container decides on its own where to keep it.

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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_btree_map<::std::size_t> port_of{{"http", 80zu}, {"https", 443zu}};

	println("https is known: ", port_of.contains("https"));
	println("its value:      ", port_of.find("https")->mapped());
}

Output:

https is known: 1
its value:      443

That is the whole idea: the string "https" is the address of the element. You never compute an index, and you never search.

2. Set vs Map

Two shapes, and you will use both constantly:

• Set — the key is the element. Use it to answer “have I seen this string before?”. There is nothing else stored.
• Map — every key carries a value of type M. Use it to answer “what is associated with this string?”. Iterating a map yields a pair-like element with key() and mapped() (Ch10.7).

::fast_io::str_btree_set seen;               // set of strings
::fast_io::str_btree_map<::std::size_t> age; // string -> size_t

A key appears at most once. Inserting a duplicate is not an error and does not create a second element; whether it is ignored or overwrites depends on which insert function you call (Ch10.2).

3. Ordered or Hashed

The two families differ in the single most important way: whether the elements are kept in sorted order.

• B-tree family (str_btree_*, str_ranked_btree_*) keeps keys sorted. Iterating walks the keys in ascending order, and you get range queries: lower_bound, upper_bound, equal_range, plus front()/back() for the smallest and largest key.
• Swiss table family (str_swiss_*) computes a hash of the key and drops it in a table. Iteration order is whatever the hash produces — stable while you do not modify the table, but meaningless. In exchange you get size(), capacity(), and reserve(), and no ordering comparisons at all.

If you need “give me all keys between "b" and "d"”, that is a B-tree. If you only need “yes/no” or “value for this key”, a Swiss table is the natural fit. Ch10.10 gives a decision table.

4. How the Types Are Spelled

Each container is a class template over the character type, and each has a convenience alias per character type. You will almost always use the aliases:

The same pattern holds for every one of the six containers — str_, wstr_, u8str_, u16str_, u32str_ — and zu_str_swiss_map is the Swiss-table counterpart of zu_str_btree_map. The full type additionally takes the allocator and, for the B-tree family, the node fan-out (default 16, must be even and non-zero):

// default: global allocator, 16 keys per node
::fast_io::str_btree_set a;

// explicit: 4 keys per node (smaller nodes, deeper tree)
::fast_io::containers::basic_str_btree_set<char, ::fast_io::native_global_allocator, 4> b;

// a thread-local-allocator variant of every container lives in ::fast_io::tlc
::fast_io::tlc::str_swiss_set c;

5. Headers

One header per container, plus <fast_io.h> if you want to print:

#include <fast_io_dsal/str_btree_set.h>        // ::fast_io::str_btree_set
#include <fast_io_dsal/str_btree_map.h>        // ::fast_io::str_btree_map
#include <fast_io_dsal/str_ranked_btree_set.h> // ::fast_io::str_ranked_btree_set
#include <fast_io_dsal/str_ranked_btree_map.h> // ::fast_io::str_ranked_btree_map
#include <fast_io_dsal/str_swiss_set.h>        // ::fast_io::str_swiss_set
#include <fast_io_dsal/str_swiss_map.h>        // ::fast_io::str_swiss_map
#include <fast_io.h>                          // println / print / to

Everything lives in the ::fast_io namespace. Under the hood the class templates are in ::fast_io::containers; you only need that namespace when you spell out an allocator or a fan-out.

6. Keys Are Owned, Lookups Are Views

This is the one design decision that shapes every line of code you will write with these containers, so it is worth being explicit about it.

Inserting copies the key. The container allocates room for the characters plus a terminating '\0' and copies them. It does not keep your pointer. A string local to the loop, a temporary ::fast_io::string, a slice of a file you read earlier — all of them are safe to insert and can then die:

{
	::fast_io::string temporary = ::fast_io::concat_fast_io("session-", 42);
	s.insert_key(::fast_io::string_view(temporary.c_str(), temporary.size()));
}	// temporary is destroyed here; the key inside s is still valid
println(s.contains("session-42"));	// 1

Looking up takes a view. contains, find, erase_key and friends take ::fast_io::string_view (pointer + length). No allocation happens, nothing is copied, and you never wrap a lookup key in a ::fast_io::string:

println(s.contains("session-42"));   // string literal -> view, no allocation
println(s.count("nope"));            // 0
s.erase_key("session-42");           // erase by view

Iteration hands you views too. Dereferencing an iterator of a set gives a ::fast_io::cstring_view pointing at the container’s own copy of the key — null-terminated, cheap to print, and valid only while that element exists (Ch10.11).

char const *p = "alpha";
s.insert_key(p);                               // error: no conversion
s.insert_key(::fast_io::mnp::os_c_str(p));     // fine: null-terminated C string

Key takeaways

• Associative containers find elements by key instead of by position.
• A set stores keys; a map stores keys with values, accessed through key() / mapped().
• B-tree (str_btree_*) keeps keys sorted, so it supports range queries and front()/back().
• Swiss table (str_swiss_*) hashes keys, so it has size(), capacity(), reserve(), but no order.
• Ranked B-tree (str_ranked_btree_*) is a B-tree that also tracks subtree sizes (Ch10.8).
• Inserting copies the key into the container; looking up only passes a view, so lookups never allocate.
• Keys come in str_ / wstr_ / u8str_ / u16str_ / u32str_ variants for every container.