Ch10.6: Erasing

1. Erasing by Key

erase_key(key) removes the element whose key you name and returns how many elements it removed — 1 or 0:

#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.erase_key("alpha"));   // 1: removed
	println(s.erase_key("alpha"));   // 0: nothing to remove
	println(s.erase_key("nope"));    // 0
}

1
0
0

Erasing a key that is not there is not an error. If you need to know whether it was there, look at the return value, or call contains first when the branch is easier to read that way. The removal itself never needs an iterator and never allocates.

2. Erasing by Iterator

erase(it) removes the element the iterator points at and returns an iterator to the next element — the element that took the removed one’s place in the order:

auto it{s.find("beta")};
it = s.erase(it);          // it now points at the element after "beta"
if (it != s.cend())
{
	println("next: ", *it);
}

next: c

Returning the next position is what makes the erase-while-iterating loop safe without incrementing anything by hand. The loop below removes every key that starts with "tmp":

for (auto it{s.cbegin()}; it != s.cend();)
{
	::fast_io::string_view k{*it};
	if (k.starts_with(::fast_io::string_view("tmp")))
	{
		it = s.erase(it);   // already advanced
	}
	else
	{
		++it;
	}
}

Erasing a range

erase(first, last) removes the left-inclusive range [first, last) — every element from first up to, but not including, last — and returns an iterator to the element last pointed at:

auto first{s.find("c")};
auto last{s.find("d")};
auto after{s.erase(first, last)};   // removes "c" only
println("next: ", *after);          // d

next: d

With last == cend() everything from first to the end is removed, and the returned iterator is cend().

3. Erasing Everything

s.clear();                  // remove all elements, keep the object usable
println(s.is_empty());      // 1
s.insert_key("again");      // fine

s.clear_destroy();          // remove all elements and release the container's storage

Both are noexcept and both are safe on an empty container. After clear() the following inserts behave exactly as in a fresh container; clear_destroy() additionally drops whatever the container had allocated for its own bookkeeping, which is what you want before letting a large container sit idle.

4. One Statement, One Mutation

C++ does not specify the order in which function arguments are evaluated. That turns this line into a bug:

println(s.erase_key("beta"), s.size());   // WRONG: size() may run before the erase

Whether you get the size before or after the removal depends on the compiler. Split mutation and inspection into separate statements and the question disappears:

auto n{s.erase_key("beta")};
println("removed ", n, ", size now ", s.size());

5. What Erasing Invalidates

Erasing destroys an element, so everything that referred to that element is dead: its iterator, and any key view or mapped reference you took from it. Views taken from other elements are not affected by an erase in the B-tree family, because inserting and erasing moves whole subtrees rather than shuffling elements around.

In the Swiss-table family, an erase can move an element into the hole it leaves behind, so treat any reference into the table as gone once you modify it. The rule that always holds, for all six containers:

• An iterator, key view or mapped reference is valid until that element is erased, or until the container is cleared, moved from, or (Swiss) grows/reshapes.
• After erase, only the returned iterator is known-good.
• Re-look the key up if you need an iterator again — lookups are cheap.

Key takeaways

• erase_key(key) removes by key and returns 0 or 1; removing a missing key is harmless.
• erase(it) removes by position and returns the iterator to the next element.
• erase(first, last) removes a left-inclusive range and returns the position of last.
• Erase-while-iterating: assign the result back, never increment afterwards.
• clear() and clear_destroy() are noexcept and can be called at any time.
• Never mix a mutation and a query in one statement — argument evaluation order is unspecified.
• After an erase, only the returned iterator is valid; views into erased elements are gone.