第10.6章: 删除

1. 按键删除

erase_key(key) 删除键为指定值的元素，并返回删掉了多少个元素 — 1 或 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

删除一个不存在的键不是错误。如果你需要知道它原本在不在，就看返回值，或者在那样写更易读时先调用 contains。删除本身从不需要迭代器，也从不分配内存。

2. 按迭代器删除

erase(it) 删除迭代器所指的元素，并返回指向下一个元素的迭代器 — 即在顺序中接替被删位置的那个元素：


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

返回下一个位置，正是“边遍历边删除”的循环无需手动自增就安全的原因。下面的循环删除所有以 "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;
	}
}

在 erase(it) 之后绝不要 ++it。你传进去的迭代器在元素销毁的那一刻就失效了，只有返回的迭代器可用。写成 s.erase(it); ++it; 是释放后使用，而且没有任何机制会替你发现它。

删除一个范围

erase(first, last) 删除左闭范围 [first, last) — 从 first 开始、到但不包括 last 的每个元素 — 并返回指向 last 原本所指元素的迭代器：


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

当 last == cend() 时，从 first 到末尾的全部被删除，返回的迭代器是 cend()。

3. 删除全部


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

两者都是 noexcept，在空容器上也安全。在 clear() 之后的插入行为与在新容器里完全一样；clear_destroy() 还会额外释放容器为自身管理信息分配的内存，这正是让一个大容器长时间闲置之前该做的事。

4. 一条语句，一次修改

C++ 没有规定函数参数的求值顺序。这会让下面这行变成 bug：


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

你先拿到的是删除前还是删除后的大小，取决于编译器。把修改和查看拆成两条语句，问题就消失了：


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

这不是容器特有的问题。任何既修改状态又报告状态的调用都会遇到同样的问题。“一条语句，一次修改”这条风格规则不花代价，却能消除整整一类问题。

5. 删除会使什么失效

删除会销毁元素，所以所有指向那个元素的东西都失效了：它的迭代器，以及你从它那里取得的任何键视图或映射值引用。在 B 树家族中，从其他元素取得的视图不受删除影响，因为插入与删除搬移的是整棵子树，而不是把元素挪来挪去。

在 Swiss 表家族中，一次删除可能把某个元素搬进它留下的空洞，因此一旦你修改了表，就把任何指向表内的引用视为已失效。对六个容器都成立的那条规则是：

迭代器、键视图或映射值引用，在该元素被删除之前都有效；或者在容器被清空、被移动之后（Swiss 表则在表增长/重构之后）失效。
在 erase 之后，只有返回的迭代器是已知可用的。
如果你又需要一个迭代器，就重新查一次键 — 查找很便宜。

要点

erase_key(key) 按键删除并返回 0 或 1；删一个不存在的键是无害的。
erase(it) 按位置删除并返回指向下一个元素的迭代器。
erase(first, last) 删除左闭范围并返回 last 的位置。
边遍历边删除：把结果赋回去，之后绝不再自增。
clear() 与 clear_destroy() 都是 noexcept，任何时候都能调用。
绝不要在同一条语句里混合修改与查询 — 实参求值顺序是未指定的。
删除之后只有返回的迭代器有效；指向被删元素的视图都已失效。