Ch10.3: contains(): Membership Testing

1. The Function You Will Use Most

contains(key) answers one question: is this key in the container? It returns bool, it never allocates, and with the default allocators it is noexcept. All six containers have it, with the same name and the same behaviour.

#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
}

1
0

In a real program most of the code that touches a set looks exactly like this: a filter, a guard, a validation step. That is why contains comes first and everything else after.

2. It Takes a View, So Nothing Is Copied

The parameter is a ::fast_io::string_view — a pointer plus a length. No allocation, no copy, no temporary string. Anything that can produce a view works:

The last row is the one that makes contains worth having on a string set. You can test a piece of a buffer you are scanning — a token, a field between delimiters, a line minus its newline — without building a ::fast_io::string just to look it up:

::fast_io::str_btree_set dict;
dict.insert_key("the");
dict.insert_key("quick");
dict.insert_key("fox");

::fast_io::string_view line{"the quick brown fox"};
::std::size_t pos{};
while (pos < line.size())
{
	auto space{line.find(::fast_io::string_view(" "), pos)};
	if (space == ::fast_io::containers::npos)
	{
		space = line.size();
	}
	auto token{line.subview(pos, space - pos)};
	println("[", token, "] known: ", dict.contains(token));
	pos = space + 1;
}

[the] known: 1
[quick] known: 1
[brown] known: 0
[fox] known: 1

3. contains vs find vs count

The three answer related questions. Choosing the right one keeps the intent of the code visible:

There is no way for find to fail “quietly”: the iterator either points at an element or equals cend(). If a yes/no answer is all you need, if (s.find(k) != s.cend()) is if (s.contains(k)) with more room for mistakes.

4. Patterns

Deduplicating input

Two ways to keep only the first occurrence. Either look first:

for (auto word : words)
{
	if (!seen.contains(word))
	{
		seen.insert_key(word);
		unique.push_back(word);
	}
}

or let the insert tell you, which is one lookup instead of two:

for (auto word : words)
{
	if (seen.insert_key(word))   // true only the first time
	{
		unique.push_back(word);
	}
}

Both are correct; the second is the one to prefer when you insert anyway. contains is the right tool when the container must not be modified.

Guarding with early return

void handle(::fast_io::str_swiss_set const &allowed, ::fast_io::string_view name) throws
{
	if (!allowed.contains(name))
	{
		println("rejected: ", name);
		return;
	}
	println("accepted: ", name);
}

Note the parameter: ::fast_io::str_swiss_set const & plus a view. Nothing is copied into the function call, and the const reference says “this call only reads the set”.

Membership of a map

On a map, contains asks about the key only, never the value. That is the check you need before reading a value whose key you are not sure exists:

::fast_io::str_btree_map<::std::size_t> age{{"ada", 36zu}};
println(age.contains("ada"));     // 1
println(age.contains("alan"));    // 0 — no such key

5. What “Contains” Means Exactly

The comparison is on the key bytes, exactly as given: case-sensitive, no trimming, no Unicode folding. "Alpha" and "alpha" are two different keys.

The empty string is an ordinary key. It is not in an empty container, and it can be inserted like anything else:

println(dict.contains(""));   // 0
dict.insert_key("");
println(dict.contains(""));   // 1

0
1

6. Cost and Error Specification

contains is noexcept with the default allocators, on all six containers, and that is measured at compile time:

::fast_io::str_btree_set s;
::fast_io::str_swiss_set ss;
static_assert(noexcept(s.contains("x")));
static_assert(noexcept(ss.contains("x")));

A lookup cannot allocate (it takes a view) and cannot fail (a missing key is an answer, not an error), so there is nothing to report and nothing to handle. This is why membership tests can be called from any noexcept function, including destructors and constexpr code.

In algorithmic terms, the B-tree family compares the key along one root-to-leaf path, and the Swiss-table family hashes the key once and probes. Neither walks the elements, which is what makes a set a set.

Key takeaways

• contains(key) returns bool; it is the default way to ask about membership.
• It takes a view, so no string is allocated or copied — not even for a token sliced out of a larger buffer.
• Use find/find_key only when you need the element, not just the answer.
• count is contains as a number; prefer contains.
• When you insert anyway, the insert’s bool gives you the answer without a second lookup.
• Keys are compared as exact bytes: case-sensitive, no normalisation; the empty string is a legal key.
• A char const * must be wrapped as ::fast_io::mnp::os_c_str(p) — this is a compile error by design.
• contains is noexcept with the default allocators, so it is safe in noexcept functions and at compile time.