Ch10.9: Swiss Tables: Unordered and Resizable

1. What Makes It Different

str_swiss_set and str_swiss_map are hash tables. They compute a hash of the key and store the element in a slot chosen by that hash, instead of keeping the keys sorted. Three consequences shape how you use them:

• No order. Iteration order is determined by the hashes. It is reproducible for the same input, but it is not sorted and it is not insertion order. Never build logic on it.
• A size that is known. size() and capacity() are exact and cheap, and reserve() lets you size the table up front.
• Only key operations. contains, find_key, insert_key, erase_key. No lower_bound, no front()/back(): those need an order that a hash table does not have.

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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_swiss_set s;
	for (auto k : {::fast_io::cstring_view("hello"), ::fast_io::cstring_view("world"),
				   ::fast_io::cstring_view("foo")})
	{
		s.insert_key(k);
	}

	println("size: ", s.size(), " capacity: ", s.capacity());
	println("contains foo: ", s.contains("foo"));
	for (auto const &e : s) { println("  ", e); }
}

size: 3 capacity: 15
contains foo: 1
  world
  hello
  foo

Note the iteration order: not sorted, and not the insertion order either.

2. size(), capacity(), reserve()

A hash table has to know how full it is — that is how it decides to grow. So the count is already there, and you get it for free:

println(s.size());       // elements currently stored
println(s.capacity());   // slots currently allocated
println(s.is_empty());   // size() == 0

capacity() is not the same number as size(): a table keeps a fraction of its slots free so that probing stays short. When the table fills up it grows and rehashes every key into a bigger table.

If you know how many keys are coming, reserve(n) grows the table once, up front, so the inserts that follow do not trigger repeated growth:

println(s.capacity());   // 15
s.reserve(100zu);
println(s.capacity());   // 127 — big enough for 100 keys
println(s.size());       // 3 — reserve never changes the elements

15
127
3

3. Insert and Erase

The insert functions return a small struct instead of a bare bool, because a hash table knows the slot it touched and hands you the iterator:

auto r{s.insert_key("alpha")};
println(r.inserted);      // 1 — the key was new
println(*r.position);     // alpha — iterator to the element

auto dup{s.insert_key("alpha")};
println(dup.inserted);    // 0 — already present, nothing changed

Erasing is the same erase_key / erase(it) / erase(first, last) family as the B-tree containers, and the erase-while-iterating loop has the same shape (Ch10.6):

for (auto it{s.cbegin()}; it != s.cend();)
{
	::fast_io::string_view k{*it};
	if (k.starts_with(::fast_io::string_view("w")))
	{
		it = s.erase(it);   // returns the next occupied slot
	}
	else
	{
		++it;
	}
}

size after erase: 2
  foo
  hello

Erasing from a hash table can move an element into the hole it leaves behind, so any iterator or key view you kept from before the erase is gone (Ch10.11).

4. Reading and Writing Map Values

A read is find_key; a write is an assign function. Two calls, two meanings:

::fast_io::str_swiss_map<::std::size_t> m;
m.emplace_key("a", 1zu);                       // insert if new
m.insert_key_or_assign("a", 100zu);            // replace either way
println(m.find_key("a")->mapped());            // 100
println(m.size());                             // 1

To update a value in place rather than replace it, iterate with a non-const map — the non-const iterator exposes a writable mapped():

for (auto &e : m)
{
	e.mapped() += 1zu;
}
println(m.find_key("a")->mapped());   // 101

find_key returns a const_iterator even on a non-const map, so m.find_key(k)->mapped() reads but does not write. That is the whole rule: lookups read, and every mutation is one of the insert/assign functions or an iteration.

The hasher is part of the type (::fast_io::native_swiss_hasher by default). You rarely need to name it; if you do, it is the third template parameter, and hash_function() returns a copy of it.

5. When a Swiss Table Is the Right Choice

Reach for the Swiss table when the answer to every question is “this exact key”:

• Membership: is this token in the table?
• Value lookup: what record belongs to this name?
• Deduplication while streaming input.
• Caches and indexes keyed by string.

And stay with a B-tree when the question is about ranges or order: “all keys with this prefix”, “the smallest”, “the next one after this”. A hash table cannot answer any of those without scanning everything.

Key takeaways

• str_swiss_set / str_swiss_map are hash tables: exact-key operations only, no order.
• Iteration order is arbitrary but reproducible; never depend on it.
• size(), capacity() and is_empty() are cheap; reserve(n) sizes the table once so a bulk insert does not rehash repeatedly.
• insert_key returns {position, inserted}; inserted tells you whether the key was new.
• erase_key, erase(it), erase(first, last) behave as in the B-tree family.
• Writes go through insert_key_or_assign / emplace_key, or through a non-const iterator; reads go through find_key.
• find_key gives a const_iterator: read-only.