Ch10.4: Looking Keys Up

1. The Two Questions

Every lookup answers one of two questions, and there is a function for each:

“Is this key present?” — contains(key) returns bool. This is the function you want most of the time.
“Where is this key?” — find(key) returns an iterator, which you compare against cend().

Both take a view, so nothing is allocated and nothing is copied on a lookup. A string literal works directly:


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

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_btree_set s;
	s.insert_key("alpha");
	s.insert_key("beta");

	println(s.contains("alpha"));   // 1
	println(s.contains("gamma"));   // 0
	println(s.count("beta"));       // 1 — count is 0 or 1, never more
}


1
0
1

count exists because the same code shape is written with other containers where a key may repeat; here it is exactly contains with a size as the result. Prefer contains for a yes/no answer.

find_key is a synonym for find. The B-tree containers provide both names. The Swiss-table containers provide only find_key, because find would collide with the plain-container convention of finding an element by value. Since you always know what you are searching for, use find_key and the code stays portable across all six containers.

2. `find` and the Iterator You Get Back

find returns an iterator that is either the element or cend(). Dereferencing the element gives you a ::fast_io::cstring_view — the container’s own copy of the key:


auto it{s.find("beta")};
if (it != s.cend())
{
	println("found: ", *it);
}
else
{
	println("not found");
}


found: beta

Comparing against cend() is the idiom. There is no npos, no index, no nullable pointer: an iterator that equals cend() is the “not found” result.

Do not dereference cend(). The usual if (it == s.cend()) check is not optional politeness — an iterator that is not pointing at an element has nothing to give you.

3. Range Queries (B-tree Family Only)

Because the B-tree keeps its keys sorted, it can answer questions about ranges of keys. The Swiss-table containers cannot, which is the main reason to pick a B-tree.

Call	Returns the position of
`lower_bound(k)`	the first key that is not less than `k`
`upper_bound(k)`	the first key that is greater than `k`
`equal_range(k)`	both, packaged as `.first` and `.second`


::fast_io::str_btree_set s;
for (auto k : {::fast_io::cstring_view("user:101"), ::fast_io::cstring_view("user:42"),
			   ::fast_io::cstring_view("admin:7"), ::fast_io::cstring_view("user:7")})
{
	s.insert_key(k);
}

auto lb{s.lower_bound("user:42")};
auto ub{s.upper_bound("user:42")};
println("lower_bound(user:42) = ", *lb);   // user:42
println("upper_bound(user:42) = ", *ub);   // user:7


lower_bound(user:42) = user:42
upper_bound(user:42) = user:7

Keys are compared as plain byte strings, so "user:101" sorts before "user:42": '1' < '4'. Sort order is lexicographic, not numeric. If you need numbers to sort numerically, pad them to a fixed width or store the numeric part somewhere else.

Scanning a prefix

“All keys starting with user:” is lower_bound plus a loop with an early exit. lower_bound puts you at the first candidate; you keep going while the prefix still matches:


for (auto it{s.lower_bound("user:")}; it != s.cend(); ++it)
{
	::fast_io::string_view k{*it};
	if (!k.starts_with(::fast_io::string_view("user:")))
	{
		break;
	}
	println("  ", *it);
}


  user:101
  user:42
  user:7

The cost of this scan is the lookup plus one step per matching key — you never walk the keys that do not match.

4. Complete Recipe

Put together, a lookup with a sensible fallback looks like this:


bool has_user(::fast_io::str_btree_set const &db, ::fast_io::string_view name) noexcept
{
	return db.contains(name);
}

Two things are worth noticing. First, the parameter is a ::fast_io::string_view, not a ::fast_io::string and not ::fast_io::cstring_view: a lookup never needs ownership, and a plain view is the weakest requirement, so every caller can pass what they have. Second, the function is noexcept — with the default allocators every lookup in all six containers is noexcept, because a lookup cannot allocate and cannot fail (Ch10.11).

When the container is const, the iterators you get are const_iterator — which is also what you get from a non-const set, because a set’s keys are immutable. For a map, a non-const container gives you an iterator whose mapped() can be written to (Ch10.7).

Key takeaways

Lookups take a view: no allocation, no copy, literals work directly.
contains(key) is the yes/no answer; count(key) is 0 or 1.
find / find_key return an iterator; compare with cend(), dereference to get a cstring_view.
Swiss containers have find_key only; use that name everywhere for portable code.
lower_bound / upper_bound / equal_range exist only on the B-tree family.
Prefix scans are lower_bound(prefix) plus a loop that stops when the prefix stops matching.
Keys sort byte-wise: "user:101" comes before "user:42".
All lookups are noexcept with the default allocators.