第10.2章: 创建容器并插入键

1. 创建一个容器

默认构造出来的容器是空的，除了几个空指针之外不花任何代价 — 在你插入东西之前不会发生分配：


#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;
	println("empty: ", s.is_empty());
}


empty: 1

六个容器上都有 is_empty()。注意它是 is_empty()，不是 empty()。

从一组键构造

集合接受一个视图的初始化列表。因为元素类型是 ::fast_io::string_view，所以每个键都要写成各自的花括号元素：


::fast_io::str_btree_set s{{::fast_io::string_view("gamma"),
                            ::fast_io::string_view("alpha")}};
for (auto e : s) { println(e); }


alpha
gamma

映射接受键/值对，这里字符串字面量可以直接用，因为 pair 类型会为你构造：


::fast_io::str_btree_map<::std::size_t> m{{"b", 2}, {"a", 1}};

从任何范围构造

from_range 接受任何带 begin()/end() 的东西：


::fast_io::vector<::fast_io::cstring_view> words{
	::fast_io::cstring_view("delta"), ::fast_io::cstring_view("alpha")};

::fast_io::str_btree_set s(::std::from_range, words);

在已有容器上，insert_range 做同样的事：


::fast_io::str_btree_set s;
s.insert_range(words);

2. `insert_key` 及其返回值

insert_key 添加一个键。已经存在的键不是错误，也不会产生重复元素。返回值告诉你发生的是哪一种情况，这就是它不返回 void 的原因：


::fast_io::str_btree_set s;
println(s.insert_key("alpha"));   // 1: key was new, container grew
println(s.insert_key("beta"));    // 1
println(s.insert_key("alpha"));   // 0: already there, nothing changed
println(s.contains("beta"));      // 1

把这个布尔值读作“容器变大了吗？”这一条规则覆盖本章所有插入函数：true 表示出现了新元素，false 表示键本来就在。

Swiss 表容器返回的是一个小的结构体，因为它们还能把元素的位置给你：


::fast_io::str_swiss_set ss;
auto r{ss.insert_key("alpha")};
println(r.inserted);          // 1
println(*r.position);         // alpha — r.position is an iterator

忽略返回值完全可以，也很常见：s.insert_key(k);。它故意没有 [[nodiscard]] — 调用处通常并不关心“是否本来就在”。

3. 往映射中插入

映射除了键还需要一个值。三个函数，三种含义：

调用	键已存在	键是新的	返回
`insert_key(k, v)`	什么都不做，保留旧值。	插入 `v`。	`bool`：是否插入了？
`insert_key_or_assign(k, v)`	覆盖旧值。	插入 `v`。	`bool`：是插入（而不是赋值）吗？
`emplace_key(k, args...)`	什么都不做。	用 `args` 就地构造值。	`bool`：是否插入了？


::fast_io::str_btree_map<::std::size_t> m{{"ant", 1zu}};

m.insert_key("ant", 100zu);            // ignored: "ant" is already there
println(m.find("ant")->mapped());      // 1

m.insert_key_or_assign("ant", 7zu);    // overwrites
println(m.find("ant")->mapped());      // 7

m.emplace_key("bee", 42zu);            // constructs the value in place
println(m.find("bee")->mapped());      // 42

“键已存在”比较的是键的字节，不是指针，也不是对象标识的哈希。键按精确字节比较：区分大小写、不做 Unicode 规范化、不修剪空白。如果你想要不区分大小写的键，就在插入之前和每次查找之前把字符串规范化。

4. 批量插入与提示

insert_range 插入整个范围。对 B 树家族还有 insert_key_hint(hint, key)：如果你已经大致知道键该放在哪里，提示能让容器从那里开始搜索，而不是从根开始。

常见的特例是追加按有序顺序到来的键 — 例如读一个已排序的文件。把 cend() 作为提示就是这种情形下的快速路径：


::fast_io::str_btree_set s;
s.insert_key_hint(s.cend(), "b");
s.insert_key_hint(s.cend(), "c");
s.insert_key("a");            // out of order: normal insertion
for (auto e : s) { println(e); }


a
b
c

insert_range 内部已经使用了这个提示，所以通过 insert_range 从有序来源填充 B 树能自动获得同样的好处，你不需要额外写什么。提示给错了也从不是错误 — 容器只是退回普通插入。

5. 复制、移动、清空

六个容器都可复制、可移动。复制会深拷贝每个键（每个键各自分配内存）；移动则转移内部指针，把源容器留空：


::fast_io::str_btree_set a{{::fast_io::string_view("x"), ::fast_io::string_view("y")}};
::fast_io::str_btree_set b{a};        // deep copy
::fast_io::str_btree_set c{::std::move(b)};  // b is now empty

println(a.contains("x"), b.contains("x"), c.contains("x"));  // 1 0 1

clear() 删除所有元素并保持对象可用；clear_destroy() 做同样的事，但还会释放容器自身的存储，使下一次插入从头开始。两者都是 noexcept。对马上要重新填充的容器，优先用 clear()。


s.clear();
println(s.is_empty());   // 1
s.insert_key("again");   // works as before

要点

默认构造是免费的：第一次插入之前不会分配。
用 is_empty() 判断是否为空。
集合可以用 string_view 的初始化列表构造，映射可以用 {key, value} 对构造。
from_range / insert_range 接受任何视图范围。
insert_key 从不产生重复；它的 bool 说明容器是否变大。
映射：insert_key 保留旧值，insert_key_or_assign 覆盖，emplace_key 就地构造。
B 树容器接受 insert_key_hint(cend(), key)，用于按序批量填充。
复制会深拷贝键；移动转移所有权；clear() 清空但保持对象可用。