Ch10: Associative Containers

Overview

A sequential container (Chapter 9) stores elements at the positions where you put them: index 0, index 1, and so on. An associative container does not care about positions. You give it a key, and it finds the element again later, without you remembering where it went.

The containers in this chapter all use a string key. This is the case that matters in real programs: counting words, mapping names to records, looking up settings, caching results, checking membership of a token. fast_io gives you two families for it, each in a set flavour (the key is the whole element) and a map flavour (the key is attached to a value):

Family	Set	Map	Order of elements
B-tree	`::fast_io::str_btree_set`	`::fast_io::str_btree_map<M>`	Always sorted by key.
Ranked B-tree	`::fast_io::str_ranked_btree_set`	`::fast_io::str_ranked_btree_map<M>`	Sorted by key, and knows how many elements come before each one.
Swiss table (hash)	`::fast_io::str_swiss_set`	`::fast_io::str_swiss_map<M>`	Unordered — the order is an artefact of the hashing.

All six types share the same style of interface, so what you learn for one mostly carries over to the others: insert_key, contains, find, erase_key, and iteration with begin()/end(). The differences are what each family can do beyond that (order, rank, capacity) and how much bookkeeping it does per element.

The keys own their characters. When you insert "alpha", the container keeps its own null-terminated copy. When you look a key up, you only pass a view (::fast_io::string_view / ::fast_io::cstring_view), so a lookup never allocates. This is covered in Ch10.1.

Ch10: Associative Containers

Overview

Contents