Module std::collections

集合类型。

Rust 的标准集合库提供了最常见的通用编程数据结构的有效实现。通过使用标准实现，两个库在不进行大量数据转换的情况下就可以进行通信。

为了避免这种情况: 您可能应该只使用 Vec 或 HashMap。 这两个集合涵盖了泛型数据存储和处理的大多数用例。他们非常擅长于做自己的工作。标准库中的所有其他集合都具有特定的用例，在这些用例中它们是最佳选择，但相比之下，这些用例是边缘性的。 即使 Vec 和 HashMap 在技术上不是最佳选择，它们也可能是入门的足够好选择。

Rust 的集合可以分为四个主要类别:

• Sequences: Vec, VecDeque, LinkedList
• Maps: HashMap, BTreeMap
• Sets: HashSet, BTreeSet
• Misc: BinaryHeap

什么时候应该使用哪个集合?

这些是应该何时考虑每个集合的较高层次且快速的细分。各个集合的优缺点的详细讨论可以在他们自己的文档页面上找到。

在以下情况下，请使用 Vec:

• 您想要收集项以供以后处理或发送到其他地方，而不必关心所存储的实际值的任何属性。
• 您需要按特定顺序排列的元素序列，并且只会附加到末尾 (或接近末尾)。
• 您想要一个栈。
• 您需要一个可调整大小的数组。
• 您需要一个堆分配的数组。

在以下情况下，请使用 VecDeque:

• 您需要 Vec 支持序列两端的有效插入。
• 您想要一个队列。
• 您需要一个双端队列 (deque)。

在以下情况下，请使用 LinkedList:

• 您需要一个未知大小的 Vec 或 VecDeque，并且不能容忍摊销。
• 您想有效地拆分和追加列表。
• 您确实，想要一个双向链表。

在以下情况下，请使用 HashMap:

• 您想要将任意键与任意值相关联。
• 您需要一个缓存。
• 您需要一个没有额外功能的 map。

在以下情况下，请使用 BTreeMap:

• 您需要一个按其键排序的 map。
• 您希望能够按需获取一系列条目。
• 您对最小或最大键值对是什么感兴趣。
• 您想要找到小于或大于某项的最大或最小键。

在以下情况下，请使用任何 Map 的 Set 成员:

• 您只想记住您所看到的键。
• 与您的键关联没有任何有意义的值。
• 您只想要一个 set。

在以下情况下，请使用 BinaryHeap:

• 您想存储一堆元素，但只想在任何给定时间处理 “biggest” 或 “most important”。
• 您需要一个优先级队列。

Performance

为工作选择合适的集合需要了解每个集合的特长。在这里，我们简要总结了某些重要操作的不同集合的性能。 有关更多详细信息，请参见每种类型的文档，并请注意，实际方法的名称可能与某些集合中的下表有所不同。

在整个文档中，我们将遵循一些约定。对于所有操作，集合的大小用 n 表示。如果该操作涉及另一个集合，则它包含 m 个元素。具有 amortized 成本的操作以 * 为后缀。具有 expected 成本的操作以 ~ 为后缀。

所有摊销成本均用于容量耗尽时可能需要调整的大小。如果发生调整大小，则将花费 O(n) 时间。我们的集合永远不会自动收缩，因此移除操作不会摊销。在足够多的工序系列中，每次工序的平均成本将确定性地等于给定成本。

由于哈希的概率性质，只有 HashMap 具有预期的成本。 从理论上讲，HashMap 可能会出现性能下降的情况，尽管可能性很小。

Sequences

	get(i)	insert(i)	remove(i)	append	split_off(i)
Vec	O(1)	O(n-i)*	O(n-i)	O(m)*	O(n-i)
VecDeque	O(1)	O(min(i, n-i))*	O(min(i, n-i))	O(m)*	O(min(i, n-i))
LinkedList	O(min(i, n-i))	O(min(i, n-i))	O(min(i, n-i))	O(1)	O(min(i, n-i))

请注意，在发生联系的地方，Vec 通常比 VecDeque 快，而 VecDeque 通常比 LinkedList 快。

Maps

对于集合，所有操作的成本均等价于 Map 操作。

	get	insert	remove	range	append
HashMap	O(1)~	O(1)~*	O(1)~	N/A	N/A
BTreeMap	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n+m)

正确有效地使用集合

当然，知道哪种集合最适合该工作并不能立即使您正确使用它。以下是一般有效和正确使用标准集合的一些快速技巧。如果您特别对如何使用特定集合感兴趣，请查阅其文档以获取详细的讨论和代码示例。

容量管理

许多集合提供了一些引用 “capacity” 的构造函数和方法。这些集合通常构建在数组的顶部。 理想情况下，此数组的大小恰好适合仅适合存储在集合中的元素，但是对于集合而言，这样做效率很低。如果支持数组始终正确大小，则每次插入元素时，集合都必须增大数组以适合它。 由于在大多数计算机上分配和管理内存的方式，几乎肯定需要分配一个全新的数组，并将每个元素从旧元素复制到新元素中。 希望您能看到这样做并不是在每个操作上都非常有效。

因此，大多数集合使用 amortized 分配策略。它们通常让自己拥有大量的空闲空间，因此它们仅需要偶尔增长。当它们确实增长时，它们会分配一个更大的数组来将元素移入，以便需要一段时间才能进行另一个增长。 尽管此策略总体上不错，但如果必须 * 绝不调整其支持数组的大小，那就更好了。 不幸的是，集合本身没有足够的信息来执行此操作。 因此，由我们的程序员来提供提示。

任何 with_capacity 构造函数都将指示该集合为指定数量的元素分配足够的空间。理想情况下，这将恰好适用于许多元素，但是某些实现细节可能会阻止这种情况。有关详细信息，请参见特定于集合的文档。通常，当您确切知道要插入多少个元素，或者至少在该数目上具有合理的上限时，请使用 with_capacity。

当预期大量元素涌入时，reserve 系列方法可用于向集合暗示应该为即将到来的项目腾出多少空间。与 with_capacity 一样，这些方法的精确行为将特定于感兴趣的集合。

为了获得最佳性能，集合通常会避免自身收缩。如果您认为某个集合将很快不再包含任何其他元素，或者仅真的需要内存，则 shrink_to_fit 方法将提示该集合将后备数组缩小到能够容纳其元素的最小大小。

最后，如果您对集合的实际容量感兴趣，则大多数集合都会提供 capacity 方法来按需查询此信息。这对于调试目的或与 reserve 方法一起使用可能很有用。

Iterators

迭代器是 Rust 的标准库中使用的强大而强大的机制。 迭代器以泛型，安全，有效和方便的方式提供一系列值。 迭代器的内容通常是惰性求值的，因此只有实际需要的值才会实际产生，而不需要进行任何分配来临时存储它们。迭代器主要通过 for 循环使用，尽管许多函数也将迭代器用于需要集合或值序列的地方。

所有标准集合都提供了几个用于对其内容进行批量操作的迭代器。几乎每个集合应提供的三个主要迭代器是 iter，iter_mut 和 into_iter。 其中的某些未在集合中提供，因此提供它们是不合理的或不合理的。

iter 提供一个以 “natural” 最高顺序对集合的所有内容进行不可变变量引用的迭代器。 对于像 Vec 这样的序列集合，这意味着该项将以索引从 0 开始的递增顺序产生。对于 BTreeMap 之类的有序集合，这意味着该项将按排序顺序产生。 对于 HashMap 之类的无序集合，将以内部表示最方便的任何顺序产生该项。这对于通读集合的所有内容非常有用。

let vec = vec![1, 2, 3, 4];
for x in vec.iter() {
   println!("vec contained {}", x);
}

iter_mut 提供与 iter 相同的 变量 引用的迭代器。这对于更改集合的所有内容非常有用。

let mut vec = vec![1, 2, 3, 4];
for x in vec.iter_mut() {
   *x += 1;
}

into_iter 将实际的集合转换为按其内容按值的迭代器。当不再需要集合本身并且在其他地方需要这些值时，这非常好。将 extend 与 into_iter 一起使用是将一个集合的内容移入另一个集合的主要方法。 extend 自动调用 into_iter，并使用任何 T: IntoIterator。 在迭代器本身上调用 collect 也是将一个集合转换为另一个集合的好方法。这两种方法都应在内部使用上一节中讨论的容量管理工具来尽可能高效地执行此操作。

let mut vec1 = vec![1, 2, 3, 4];
let vec2 = vec![10, 20, 30, 40];
vec1.extend(vec2);

use std::collections::VecDeque;

let vec = vec![1, 2, 3, 4];
let buf: VecDeque<_> = vec.into_iter().collect();

迭代器还提供了一系列 adapter 方法，用于对序列执行通用线程。 在适配器中，有功能最喜欢的适配器，例如 map，fold，skip 和 take。集合特别令人感兴趣的是 rev 适配器，它可以反转支持该操作的所有迭代器。大多数集合都提供可逆迭代器，作为以相反顺序对其进行迭代的方式。

let vec = vec![1, 2, 3, 4];
for x in vec.iter().rev() {
   println!("vec contained {}", x);
}

其他几种集合方法还返回迭代器以产生结果序列，但避免分配整个集合来存储结果。 这提供了最大的灵活性，因为可以根据需要将 collect 或 extend 调用到 “pipe” 序列中的任何集合中。否则，可以使用 for 循环将序列循环。迭代器在部分使用后也可以丢弃，从而避免了未使用项的计算。

Entries

entry API 旨在提供一种有效的机制，用于根据是否存在键来有条件地操纵 map 的内容。这样做的主要动机是提供有效的累加器 maps。例如，如果希望保持对每个键被看到的次数的计数，则他们将必须执行一些条件逻辑来确定这是否是第一次被看到。

通常，这需要先插入 find，然后再插入 insert，以有效地重复每次插入时的搜索工作。

当用户调用 map.entry(&key) 时，map 将搜索键，然后产生 Entry 枚举的成员。

如果产生 Vacant(entry)，则没有找到键。在这种情况下，唯一有效的操作是将值 insert 放入条目中。完成此操作后，将使用空条目并将其转换为所插入值的变量引用。这允许对超出搜索本身生命周期的值进行进一步操作。 如果无论是否插入值，都需要对值执行复杂的逻辑，这将很有用。

如果产生 Occupied(entry)，则找到键 *。 在这种情况下，用户有几个选项: 他们可以 get，insert 或 remove 占用的条目的值。此外，他们可以将占用的条目转换为其值的变量引用，从而为空缺的 insert 情况提供对称性。

Examples

这是使用 entry 的两种主要方法。首先，一个简单的示例，其中对值执行的逻辑很简单。

计算字符串中每个字符出现的次数

use std::collections::btree_map::BTreeMap;

let mut count = BTreeMap::new();
let message = "she sells sea shells by the sea shore";

for c in message.chars() {
    *count.entry(c).or_insert(0) += 1;
}

assert_eq!(count.get(&'s'), Some(&8));

println!("Number of occurrences of each character");
for (char, count) in &count {
    println!("{}: {}", char, count);
}

当要对该值执行的逻辑比较复杂时，我们可以简单地使用 entry API 来确保该值已初始化，然后再执行该逻辑。

跟踪酒吧顾客的醉酒情况

use std::collections::btree_map::BTreeMap;

// 酒吧客户端。他们有血液中的酒精含量。
struct Person { blood_alcohol: f32 }

// 所有的订单都是按客户 ID 送到酒吧的。
let orders = vec![1, 2, 1, 2, 3, 4, 1, 2, 2, 3, 4, 1, 1, 1];

// 我们的客户。
let mut blood_alcohol = BTreeMap::new();

for id in orders {
    // 如果这是我们第一次见到此客户，请在不使用酒精的情况下初始化他们。
    // 否则，只需检索它们。
    let person = blood_alcohol.entry(id).or_insert(Person { blood_alcohol: 0.0 });

    // 降低他们的血液酒精含量。订购和喝啤酒需要时间!
    person.blood_alcohol *= 0.9;

    // 检查他们是否足够清醒，可以再喝一杯啤酒。
    if person.blood_alcohol > 0.3 {
        // 太醉了... 目前。
        println!("Sorry {}, I have to cut you off", id);
    } else {
        // 有另外一个!
        person.blood_alcohol += 0.1;
    }
}

插入复杂的键

如果我们拥有更复杂的键，则对 insert 的调用将不会更新键的值。例如:

use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct Foo {
    a: u32,
    b: &'static str,
}

// 我们将仅通过它们的 `a` 值来比较 `Foo`。
impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool { self.a == other.a }
}

impl Eq for Foo {}

// 我们将仅通过 `a` 值对 Foo 进行哈希处理。
impl Hash for Foo {
    fn hash<H: Hasher>(&self, h: &mut H) { self.a.hash(h); }
}

impl PartialOrd for Foo {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.a.partial_cmp(&other.a) }
}

impl Ord for Foo {
    fn cmp(&self, other: &Self) -> Ordering { self.a.cmp(&other.a) }
}

let mut map = BTreeMap::new();
map.insert(Foo { a: 1, b: "baz" }, 99);

// 我们已经有一个 a 等于 1 的 Foo，因此这将更新该值。
map.insert(Foo { a: 1, b: "xyz" }, 100);

// 该值已更新...
assert_eq!(map.values().next().unwrap(), &100);

// ... 但是键没有变。b 仍然是 "baz"，而不是 "xyz"。
assert_eq!(map.keys().next().unwrap().b, "baz");

Modules

binary_heap	用二进制堆实现的优先级队列。
btree_map	基于 B 树的 map。
btree_set	基于 B 树的集合。
hash_map	通过二次探测和 SIMD 查找实现的哈希 map。
hash_set	实现为 HashMap 的哈希集，其中值为 ()。
linked_list	具有所属节点的双向链表。
vec_deque	使用可增长的环形缓冲区实现的双端队列。

Structs

BTreeMap	基于 B-Tree 的 map。
BTreeSet	基于 B 树的集合。
BinaryHeap	用二进制堆实现的优先级队列。
HashMap	通过二次探测和 SIMD 查找实现的 hash map。
HashSet	hash set，实现为 HashMap，其中值为 ()。
LinkedList	具有所属节点的双向链表。
VecDeque	使用可增长的环形缓冲区实现的双端队列。

Enums

TryReserveError

Experimental try_reserve 方法的错误类型。