ch16-集合.md

集合(Collections)

我们都像麦克斯韦妖一样.生物组织.在日常生活中,两个世纪以来清醒的物理学家们让这个卡通幻想继续存在的原因就在于此.我们把邮件分类,建造沙子城堡,玩拼图游戏,把麦粒和谷壳分开,重新排列棋子,收集邮票,按字母顺序排列书籍,创造对称性,创作十四行诗和奏鸣曲,把我们的房间收拾整齐,我们所做的一切都不需要很大的精力,只要我们能运用智慧. --James Gleick, The Information: A History, a Theory, a Flood

原文

We all behave like Maxwell's demon. Organisms organize. In everyday experience lies the reason sober physicists across two centuries kept this cartoon fantasy alive. We sort the mail, build sand castles, solve jigsaw puzzles, separate wheat from chaff, rearrange chess pieces, collect stamps, alphabetize books, create symmetry, compose sonnets and sonatas, and put our rooms in order, and all this we do requires no great energy, as long as we can apply intelligence. --James Gleick, The Information: A History, a Theory, a Flood

Rust标准库包含几个 集合(collections) ,用于在内存中存储数据的泛型类型.我们已经在本书中使用了诸如Vec和HashMap之类的集合.在本章中,我们将详细介绍这两种类型的方法,以及其他六种标准集合.在开始之前,让我们来解决Rust的集合与其他语言集合之间的一些系统差异.

首先,移动和借用无处不在.Rust使用移动来避免深复制(deep-copying)值.这就是为什么方法Vec<T>::push(item)通过值而不是通过引用接受其参数.该值被移动到向量中.第4章中的图表显示了这在实践中是如何工作的:将RustString推入到Vec<String>很快,因为Rust不必复制字符串的字符数据,并且字符串的所有权始终是清晰的.

其次,Rust没有失效错误--当程序持有指向其内数据的指针时,调整集合或以其他方式更改集合的情况下的悬空指针错误.失效错误是C++中未定义行为的另一个来源,即使在内存安全语言中,它们也会偶尔导致ConcurrentModificationException.Rust的借用检查器在编译时将它们排除在外.

最后,Rust没有null,所以我们会在其他语言使用null的地方看到Option.

除了这些差异,Rust的集合也与你的期望有关.如果你是一个经验丰富的程序员,你可以在这里浏览,但不要错过第381页的"条目(Entries)".

概述(Overview)

表16-1展示了Rust的八个标准集合.所有这些都是泛型类型.

表16-1. 标准集合摘要 后三列为其它语言中类似的集合类型...

集合	描述	C++	Java	Python
Vec<T>	可增长数组	vector	ArrayList	list
VecDeque<T>	双端队列(可增长环形缓冲区)	deque	ArrayDeque	collections.deque
LinkedList<T>	双向链表	list	LinkedList	-
BinaryHeap<T> where T: Ord	最大堆	priority_queue	PriorityQueue	heapq
HashMap<K, V> where K: Eq + Hash	键值哈希表	unordered_map	HashMap	dict
BTreeMap<K, V> where K: Ord	排序键值表	map	TreeMap	-
HashSet<T> where T: Eq + Hash	哈希表	unordered_set	HashSet	set
BTreeSet<T> where T: Ord	有序集	set	TreeSet	-

Vec<T>,HashMap<K, V>,和HashSet<T>是最常用的集合类型.其余的都有特殊用途.本章依次讨论每种集合类型:

• Vec<T>是一个可增长的,堆分配的T类型值的数组.本章的大约一半专门介绍Vec及其许多有用的方法.

• VecDeque<T>与Vec<T>类似,但更适合用作先进先出队列.它支持在列表前面和后面高效地添加和删除值.代价是使所有其他操作稍微慢一些.

• LinkedList<T>支持快速访问列表的前面和后面,,类似VecDeque<T>,并添加快速连接.但是,通常,LinkedList<T>比Vec<T>和VecDeque<T>慢.

• BinaryHeap<T>是优先级队列.BinaryHeap中的值被组织起来,以便始终高效地查找和删除最大值.

• HashMap<K, V>是键-值对的表.按键查找值很快.条目以任意顺序存储.

• BTreeMap<K, V>类似于HashMap<K, V>,但它保持条目按键排序.BTreeMap<String, i32>以String比较顺序存储其条目.除非你需要对条目进行排序,否则HashMap更快.

• HashSet<T>是T类型值的集.添加和删​​除值很快,并且可以快速询问给定值是否在集中.

• BTreeSet<T>与HashSet<T>类似,但它保持元素按值排序.同样,除非你需要对数据进行排序,否则HashSet更快.

Vec<T>(Vec<T>)

我们假设对Vec有一定的了解,因为我们一直在使用它.有关介绍,请参见第59页的"向量(Vectors)".在这里,我们将最终深入描述其方法及其内部工作原理.

创建向量的最简单方法是使用vec!宏:

// Create an empty vector
let mut numbers: Vec<i32> = vec![];

// Create a vector with given contents
let words = vec!["step", "on", "no", "pets"];
let mut buffer = vec![0u8; 1024];  
// 1024 zeroed-out bytes

如第4章所述,向量有三个字段:长度,容量和指向存储元素的堆分配的指针.图16-1展示了上面创建的向量出现在内存中是怎样的.空向量(number)最初的容量为0.在添加第一个元素之前,不会为其分配堆内存.

与所有集合一样,Vec实现了std::iter::FromIterator,因此你可以使用迭代器的.collect()方法从任何迭代器创建向量,如"构建集合:collect和FromIterator"(第351页)中所述:

// Convert another collection to a vector.
let my_vec = my_set.into_iter().collect::<Vec<String>>();

表16-1. 在内存中的向量布局.words的每个元素都是一个&str值,由指针和长度组成.

访问元素(Accessing Elements)

通过索引获取数组,切片或向量的元素非常简单:

// Get a reference to an element
let first_line = &lines[0];

// Get a copy of an element
let fifth_number = numbers[4];       // requires Copy
let second_line = lines[1].clone();  // requires Clone

// Get a reference to a slice
let my_ref = &buffer[4..12];

// Get a copy of a slice
let my_copy = buffer[4..12].to_vec();  // requires Clone

如果索引超出范围,所有这些都会形成恐慌.

Rust对数字类型很挑剔,向量也不例外.向量长度和索引的类型为usize.尝试使用u32,u64或isize作为向量索引是一个错误.你可以使用n as usize来根据需要进行强制转换;请参阅第139页的"类型强制转换(Type Casts)".

有几种方法可以方便地访问向量或切片的特定元素(请注意,所有切片方法也可用于数组和向量):

• slice.first()返回对slice的第一个元素的引用(如果有).

返回类型是Option<&T>,因此如果slice为空则返回值为None,而如果它不为空则返回Some(&slice [0]).

if let Some(item) = v.first() {
    println!("We got one! {}", item);
}

• slice.last()类似,但返回对最后一个元素的引用.

• slice.get(index)返回对slice[index]的Some引用,如果存在.如果slice具有少于index+1个元素,则返回None.

let slice = [0, 1, 2, 3];
assert_eq!(slice.get(2), Some(&2));
assert_eq!(slice.get(4), None);

• slice.first_mut(),slice.last_mut()和slice.get_mut(index)是借用mut引用的变体.

let mut slice = [0, 1, 2, 3];
{
    let last = slice.last_mut().unwrap();   // type of last: &mut i32
    assert_eq!(*last, 3);
    *last = 100;
}
assert_eq!(slice, [0, 1, 2, 100]);

因为通过值返回T意味着移动它,所以访问元素的方法通常通过引用返回这些元素.

一个例外是.to_vec()方法,它创建副本:

• slice.to_vec()克隆整个切片,返回一个新的向量.

let v = [1, 2, 3, 4, 5, 6, 7, 8, 9];
assert_eq!(v.to_vec(),
           vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
assert_eq!(v[0..6].to_vec(),
           vec![1, 2, 3, 4, 5, 6]);

仅当元素是可克隆的,即where T：Clone时,此方法才可用.

迭代(Iteration)

向量和切片是可迭代的,通过值或通过引用,遵循"IntoIterator实现"(第325页)中描述的模式:

• 迭代Vec<T>会生成类型T的项.元素逐个移出向量,消耗它.

• 迭代类型&[T; N],&[T]或&Vec<T>的值--即对数组,切片或向量的引用--生成类型&T的项,对各个元素的引用,而非移动.

• 迭代类型&mut [T; N],&mut [T]或&mut Vec<T>的值产生类型&mut T的项.

数组,切片和向量也有.iter()和.iter_mut()方法(在第324页的"iter和iter_mut方法"中描述),用于创建生成对其元素的引用的迭代器.

我们将在第368页的"拆分(Splitting)"中介绍一些更好的方式来迭代切片.

增长和收缩向量(Growing and Shrinking Vectors)

数组,切片或向量的 长度(length) 是它包含的元素数.

• slice.len()返回slice的长度,作为usize.

• slice.is_empty()为true,如果slice不包含任何元素(即slice.len() == 0).

本节中的其余方法是关于向量的增长和缩小.它们不存在于数组和切片上,数组和切片一旦创建就无法调整大小.

所有向量的元素都存储在一个连续的,堆分配的内存块中.向量的 容量(capacity) 是适合此块的最大元素数.Vec通常会为你管理容量,在需要更多空间时自动分配更大的缓冲区并将元素移入其中.还有一些显式管理容量的方法:

• Vec::with_capacity(n)创建一个容量为n的新的空向量.

• vec.capacity()返回vec的容量,作为usize.vec.capacity() >= vec.len()总是如此.

• vec.reserve(n)确保向量至少有足够的剩余容量用于n个元素:也就是说,vec.capacity()至少是vec.len() + n.如果已经有足够的空间,这什么都不做.如果不是,则分配更大的缓冲区并将向量的内容移动到其中.

• vec.reserve_exact(n)就像vec.reserve(n),但告诉vec不要为未来的增长分配任何额外的容量(超过n的).之后,vec.capacity()正好是vec.len() + n.

• vec.shrink_to_fit(),如果vec.capacity()大于vec.len(),则它会尝试释放额外的内存.

Vec<T>有许多方法可以添加或删除元素,从而改变向量的长度.这些中的每一个都通过mut引用来接受self参数.

这两个方法在向量的末尾添加或删除单个值:

• vec.push(value)将给定value添加到vec的末尾.

• vec.pop()删除并返回最后一个元素.返回类型是Option<T>.如果弹出的元素是x,则返回Some(x),如果向量已经为空,则返回None.

请注意,.push()通过值接受其参数,而不是通过引用.同样,.pop()返回弹出的值,而不是引用.本节中大多数其余方法也是如此.它们将值移入和移出向量.

这两个方法在向量中的任何位置添加或删除值:

• vec.insert(index, value)在vec[index]处插入给定value,将vec[index ..]中的任何现有值滑动到右边的一个点以腾出空间.

如果index > vec.len(),则会发生恐慌.

• vec.remove(index)删除并返回vec[index],将vec[index + 1 ..]中的任何现有值滑动到左边一个点以缩小差距.

如果index >= vec.len()则会发生恐慌.因为在这种情况下,没有要删除的元素vec[index].

向量越长,此操作越慢.如果你发现自己做了很多vec.remove(0)可以考虑使用VecDeque(在第374页的"VecDeque<T>"中解释)而不是Vec.

.insert()和.remove()都是必须移动的元素越多越慢.

三种方法将向量的长度更改为特定值:

• vec.resize(new_len, value)将vec的长度设置为new_len.如果这增加了vec的长度,则添加value的副本以填充新空间.元素类型必须实现Clonetrait.

• vec.truncate(new_len)将vec的长度减少到new_len,删除vec[new_len ..]范围内的任何元素.

如果vec.len()已经小于或等于new_len,则什么也不发生.

• vec.clear()从vec中删除所有元素.它与vec.truncate(0)相同.

四种方法一次添加或删除多个值:

• vec.extend(iterable)在vec末尾按顺序添加给定iterable值中的所有项.它就像是.push()的多值版本.iterable参数可以是实现IntoIterator<Item=T>的任何东西.

这个方法非常有用,它有一个标准trait,即Extendtrait,所有标准集合都实现了它.不幸的是,这导致rustdoc将.extend()和其他trait方法混在生成的HTML的底部,因此在需要的时候很难找到它们.你只需要记住它就在那里!有关更多信息,请参见第353页的"The Extend Trait".

• vec.split_off(index)与vec.truncate(index)类似,不同之处在于它返回包含从vec末尾删除的值的Vec<T>.它就像.pop()的多值版本.

• vec.append(&mut vec2),其中vec2是Vec<T>类型的另一个向量,将所有元素从vec2移动到vec.之后,vec2为空.

这就像vec.extend(vec2),只不过vec2之后仍然存在,其容量不受影响.

• vec.drain(range),其中range是范围值,如..或0..4,从vec中删除范围vec[range]并返回在已删除的元素上的迭代器.

还有一些奇怪的方法可以有选择地删除一些向量的元素:

• vec.retain(test)删除所有未通过给定测试的元素.test参数是一个实现FnMut(&T) -> bool的函数或闭包.对于vec的每个元素,这将调用test(&element),如果返回false,则从向量中删除该元素并将其删除.

除了性能,这就像写作:

vec = vec.into_iter().filter(test).collect();

• vec.dedup()删除重复的元素.这就像Unixuniqshell实用程序.它扫描vec以查找相邻元素相等的位置并删除额外的相等值,这样只剩下一个:

let mut byte_vec = b"Misssssssissippi".to_vec();
byte_vec.dedup();
assert_eq!(&byte_vec, b"Misisipi");

请注意,输出中仍然有两个's'.此方法仅删除 相邻的(adjacent) 重复项.要消除所有重复项,你有三个选择:在调用.dedup()之前对向量进行排序;将数据移动到一个集(set)中;或者(为了保持元素的原始顺序)使用这个.retain()技巧:

let mut byte_vec = b"Misssssssissippi".to_vec();

let mut seen = HashSet::new();
byte_vec.retain(|r| seen.insert(*r));

assert_eq!(&byte_vec, b"Misp");

这是有效的,因为.insert()在集已经包含我们正在插入的项时返回false.

• vec.dedup_by(same)与vec.dedup()相同,但它使用函数或闭包same (&mut elem1, &mut elem2),而不是==运算符来检查,两个元素是否应该被视为相等.

• vec.dedup_by_key(key)与vec.dedup()相同,但如果key(&mut elem1) == key(&mut elem2),它会将两个元素视为相等.

例如,如果错误是Vec<Box<Error>>,你可以编写:

// Remove errors with redundant messages.
errors.dedup_by_key(|err| err.description().to_string());

在本节所涉及的所有方法中,只有.resize()才能克隆值.其他的通过将值从一个地方移动到另一个地方来工作.

连接(Joining)

两个方法适用于 数组的数组(arrays of arrays) .我们指的是任何数组,切片或向量,其元素本身就是数组,切片或向量.

• slices.concat()返回通过连接所有切片而生成的新向量.

assert_eq!([[1, 2], [3, 4], [5, 6]].concat(),
           vec![1, 2, 3, 4, 5, 6]);

• slices.join(&separator)是相同的,除了在切片之间插入值separator的副本:

assert_eq!([[1, 2], [3, 4], [5, 6]].join(&0),
           vec![1, 2, 0, 3, 4, 0, 5, 6]);

拆分(Splitting)

很容易将许多非mut引用同时放入数组,切片或向量中:

let v = vec![0, 1, 2, 3];
let a = &v[i];
let b = &v[j];

let mid = v.len() / 2;
let front_half = &v[..mid];
let back_half = &v[mid..];

获得多个mut引用并不容易:

let mut v = vec![0, 1, 2, 3];
let a = &mut v[i];
let b = &mut v[j];  // error: cannot borrow `v` as mutable
                    //        more than once at a time

Rust禁止这样做,因为如果i == j,则a和b将是对同一整数的两个mut引用,这违反了Rust的安全规则.(请参见第114页的"共享对比可变(Sharing Versus Mutation)".)

Rust有几种方法可以同时借用对数组,切片或向量的两个或多个部分的mut引用.与上面的代码不同,这些方法是安全的,因为通过设计,它们将数据拆分为 非重叠(nonoverlapping) 区域.这些方法中的许多方法对于使用非mut切片也很方便,因此每个方法都有mut和非mut版本.

图16-2说明了这些方法.它们都不直接修改数组,切片或向量;它们只返回对内部数据部分的新引用.

• slice.iter()和slice.iter_mut()生成对slice的每个元素的引用.我们在第364页的"迭代(Iteration)"中介绍了它们.

• slice.split_at(index)和slice.split_at_mut(index)将切片分成两部分,返回一对.slice.split_at(index)等价于(&slice[.. index], &slice[index ..]).如果index超出范围,这些方法会发生恐慌.

• slice.split_first()和slice.split_first_mut()也返回一对:对第一个元素(slice[0])的引用和对所有其余元素(slice[1 ..])的引用的切片.

.split_first()的返回类型是Option<(&T, &[T])>;如果slice为空,则结果为None.

• slice.split_last()和slice.split_last_mut()是类似的,但是拆分最后一个元素而不是第一个元素.

.split_last()的返回类型是Option<(&[T], &T)>.

• slice.split(is_sep)和slice.split_mut(is_sep)将切片分割成一个或多个子切片,使用函数或闭包is_sep来确定拆分的位置.它们返回子切片上的一个迭代器.

在使用迭代器时,它会为切片中的每个元素调用is_sep(&element).如果is_sep(&element)为true,则该元素为分隔符.分隔符不包含在任何输出子片中.

输出始终包含至少一个子切片,每个分隔符加一个子切片.每当分隔符彼此相邻或与slice的末端相邻时,都会包含空子切片.

• slice.splitn(n,is_sep)和slice.splitn_mut(n,is_sep)相同,但它们最多产生n个子切片.找到第一个n-1个切片后,不会再次调用is_sep.最后一个子元素包含所有剩余元素.

• slice.rsplitn(n,is_sep)和slice.rsplitn_mut(n,is_sep)就像.splitn()和.splitn_mut(),只是切片以相反的顺序扫描.也就是说,这些方法在切片中的 最后(last) n-1个分隔符上进行分割,而不是在第一个上进行分割,并且从末尾开始生成子切片.

• slice.chunks(n)和slice.chunks_mut(n)返回在长度为n的非重叠子切片上的迭代器.

如果slice.len()不是n的倍数,则最后一个子切片的长度小于n.

图16-2. 拆分方法说明.slice.split()输出中的小矩形是一个空切片,由两个相邻的分隔符引起.另请注意,rsplitn以末尾到开始的(end-to-start)顺序生成其输出,与其他所有不同.

还有一种迭代子切片的方法:

• slice.windows(n)返回一个迭代器,其行为类似于切片中数据上的"滑动窗口(sliding window)".它生成跨越n个连续slice元素的子切片.产生的第一个值是&slice[0..n];第二个是&slice[1..n+1];等等.

如果n大于slice的长度,则不产生切片.如果n为0,则该方法会发生恐慌.

例如,如果days.len() == 31,那么我们可以通过调用days.windows(7)来生成所有七天的跨度.

大小为2的滑动窗口非常便于探索数据系列如何从一个数据点更改为下一个数据点:

let changes = daily_high_temperatures
                  .windows(2)             // get adjacent days' temps
                  .map(|w| w[1] - w[0])   // how much did it change?
                  .collect::<Vec<_>>();

因为子切片重叠,所以此方法没有返回mut引用的变体.

交换(Swapping)

交换两个元素有一种方便的方法:

• slice.swap(i, j)交换两个元素slice[i]和slice[j].

向量具有高效删除任何元素的相关方法:

• vec.swap_remove(i)删除并返回vec[i].这就像vec.remove(i),除了不是将向量元素的其余部分滑动以封闭间隙,它只是将vec的最后一个元素移动到间隙中.当你不关心向量中剩余项目的顺序时,它很有用.

排序和搜索(Sorting and Searching)

切片提供三种排序方法:

• slice.sort()将元素按递增顺序排序.仅当元素类型实现Ord时才存在此方法.

• slice.sort_by(cmp)使用函数或闭包cmp对切片的元素以指定排序顺序进行排序.cmp必须实现Fn(&T, &T) -> std::cmp::Ordering.

除非你委托给.cmp()方法,否则手动实现cmp会很痛苦:

students.sort_by(|a, b| a.last_name.cmp(&b.last_name));

要按一个字段排序,使用第二个字段作为决胜局.请比较元组:

students.sort_by(|a, b| {
    let a_key = (&a.last_name, &a.first_name);
    let b_key = (&b.last_name, &b.first_name);
    a_key.cmp(&b_key)
});

• slice.sort_by_key(key)通过由函数或闭包key给出的排序键将slice的元素按递增顺序排序.key的类型必须实现Fn(&T) -> K,其中K: Ord.

当T包含一个或多个有序字段时,这很有用,因此可以多种方式对其进行排序.

// Sort by grade point average, lowest first.
students.sort_by_key(|s| s.grade_point_average());

请注意,这些排序键(sort-key)的值在排序期间不会被缓存,因此key函数可能会被调用n次以上.

由于技术原因,key(element)不能返回从元素中借用的任何引用.这不起作用:

students.sort_by_key(|s| &s.last_name);  // error: can't infer lifetime

Rust无法弄清楚生命周期.但在这些情况下,很容易回到.sort_by().

这三种方法都执行稳定的排序.

要以相反的顺序排序,可以使用sort_by和一个交换两个参数的cmp闭包.接受参数|b, a|而不是|a, b|有效地产生相反的顺序.或者,你可以在排序后调用.reverse()方法:

• slice.reverse()适当地将切片反转.

切片排序后,可以有效地搜索:

• slice.binary_search(&value),slice.binary_search_by(&value, cmp),slice.binary_search_by_key(&value, key)全部搜索给定有序slice中的value.请注意,value通过引用传递.

这些方法的返回类型是Result<usize, usize>.如果slice[index]等于指定排序顺序下的value,则返回Ok(index).如果没有这样的索引,则它们返回Err(insertion_point),以便在insertion_point处插入value将保留顺序.

当然,二分搜索仅在切片实际按指定顺序排序时才有效. 否则,结果是任意的--垃圾输入,垃圾输出.

由于f32和f64具有NaN值,因此它们不实现Ord,并且不能直接用作排序和二分搜索方法的键.要获得适用于浮点数据的类似方法,请使用ord_subsetcrate.

有一种方法可以搜索未排序的向量:

• slice.contains(&value),如果slice的任意元素等于value,则返回true.这只是检查切片的每个元素,直到找到匹配为止.同样,value通过引用传递.

要在切片中查找值的位置,例如JavaScript中的array.indexOf(value),请使用迭代器:

slice.iter().position(|x| *x == value)

这将返回Option<usize>.

比较切片(Comparing Slices)

如果类型T支持==和!=运算符(PartialEqtrait,在第272页的"相等性测试(Equality Tests)"描述),则数组[T; N],切片[T]和向量Vec<T>也支持它们.如果它们具有相同的长度并且它们的相应元素相等,则两个切片是相等的.数组和向量也是如此.

如果T支持运算符<,<=,>和>=(PartialOrdtrait,在第275页的"有序比较(Ordered Comparisons)"描述),那么T的数组,切片和向量也支持.切片比较是字典式的.

两种方便的方法进行普通切片比较:

• slice.starts_with(other),如果slice以一系列等于切片other的元素的值开始,那么它返回true:

assert_eq!([1, 2, 3, 4].starts_with(&[1, 2]), true);
assert_eq!([1, 2, 3, 4].starts_with(&[2, 3]), false);

• slice.ends_with(other)类似但检查slice的结尾:

assert_eq!([1, 2, 3, 4].ends_with(&[3, 4]), true);

随机元素(Random Elements)

随机数没有内置到Rust标准库中.提供它们的rand crate提供了这两个从数组,切片或向量中获取随机输出的方法:

• rng.choose(slice)返回对切片的随机元素的引用.与slice.first()和slice.last()一样,返回Option<&T>,只有切片为空时,才为None.

• rng.shuffle(slice)随机重新排序切片的元素.切片必须通过mut引用传递.

这些是rand::Rngtrait的方法,所以你需要一个Rng,一个随机数生成器,以便调用它们.幸运的是,通过调用rand::thread_rng()很容易得到一个.要随机改变向量my_vec,我们可以写:

use rand::{Rng, thread_rng};

thread_rng().shuffle(&mut my_vec);

Rust排除失效错误(Rust Rules Out Invalidation Errors)

大多数主流编程语言都有集合和迭代器,它们都对此规则有一些变化:在迭代时不要修改集合.例如,Python和向量等效的是列表:

my_list = [1, 3, 5, 7, 9]

假设我们尝试从my_list中删除大于4的所有值:

for index, val in enumerate(my_list):
    if val > 4:
        del my_list[index]  # bug: modifying list while iterating

print(my_list)

(enumerate函数相当于Python的Rust.enumerate()方法,在第341页的"枚举(enumerate)"中有描述.)

令人惊讶的是,该程序打印[1, 3, 7].但7大于4.这是怎么回事?这是一个失效错误:程序在迭代数据时修改数据,使迭代器 失效(invalidating) .在Java中,结果将是一个异常;在C++中,是未定义行为.在Python中,虽然行为定义明确,但它不直观:迭代器会跳过一个元素.val永远不会是7.

让我们尝试在Rust中重现这个错误:

fn main() {
    let mut my_vec = vec![1, 3, 5, 7, 9];
    for (index, &val) in my_vec.iter().enumerate() {
        if val > 4 {
            my_vec.remove(index);  // error: can't borrow `my_vec` as mutable
        }
    }
    println!("{:?}", my_vec);
}

当然,Rust在编译时拒绝这个程序.当我们调用my_vec.iter()时,它借用了对向量的共享(非mut)引用.引用与迭代器活得一样长,直到for循环结束.当存在非mut引用时,我们无法通过调用my_vec.remove(index)来修改向量.

指出你有一个错误很好,但当然,你仍然需要找到一种方法来获得所需的行为!这里最简单的解决方法是写:

my_vec.retain(|&val| val <= 4);

或者,你可以使用在Python或任何其他语言中执行的操作:使用filter创建新的向量.

VecDeque<T>(VecDeque<T>)

Vec仅支持在末尾高效地添加和删除元素.当程序需要一个存储"排队等待(waiting in line)"值的地方时,Vec可能很慢.

Rust的std::collections::VecDeque<T>是一个 deque (发音为"deck"),一个双端队列.它支持在前面和后面的高效添加和删除操作.

• deque.push_front(value)在队列的前面添加一个值.

• deque.push_back(value)在末尾添加一个值.(此方法的使用远远超过.push_front(),因为队列的通常惯例是在后面添加值并在前面删除,就像排队等待的人一样.)

• deque.pop_front()删除并返回队列的前面的值,返回Option<T>,如果队列为空,则为None,类似vec.pop().

• deque.pop_back()删除并返回后面的值,再次返回Option<T>.

• deque.front()和deque.back()的工作方式类似于vec.first()和vec.last().它们返回对队列的前面或后面元素的引用.返回值是Option<&T>,如果队列为空,则为None.

• deque.front_mut()和deque.back_mut()的工作方式类似于vec.first_mut()和vec.last_mut(),返回Option<&mut T>.

VecDeque的实现是一个环形缓冲区,如图16-3所示.

与Vec一样,它具有单个堆分配,其中存储元素.与Vec不同,数据并不总是从该区域的开头开始,并且它可以"环绕(warp around)"结束,如图所示.这个双端队列的元素依次是['A', 'B', 'C', 'D', 'E'].VecDeque具有私有字段,在图中标记为start和stop,用于记住数据开始和结束的缓冲区.

在任一端向队列添加值意味着声明其中一个未使用的插槽(以深灰色显示),环绕或分配更大的内存块(如果需要).

VecDeque管理包装(warping),所以你不必考虑它.图16-3是Rust如何快速实现.pop_front()的幕后视图(behind-the-scenes).

16-3. VecDeque在内存中如何存储.

通常,当你需要双端队列时,.push_back()和.pop_front()是你唯一需要的两个方法.静态方法VecDeque::new()和VecDeque::with_capacity(n),用于创建队列,就像它们在Vec中的对应物一样.许多Vec方法也为VecDeque实现:.len()和.is_empty(),.insert(index, value)和.remove(index),.exteng(iterable)等.

像向量一样,双端队列可以通过值,通过共享引用或通过mut引用进行迭代.它们有三个迭代器方法.into_iter(),.iter()和.iter_mut().它们可以以通常的方式索引:deque[index].

但是,因为双端队列不会将其元素连续存储在内存中,所以它们不会继承切片的所有方法.对双端队列数据执行向量和切片操作的一种方式是将VecDeque转换为Vec,执行这些操作,然后将其更改回来:

• Vec<T>实现From<VecDeque<T>>,因此Vec::from(deque)将双端队列转换为向量.这花费O(n)时间,因为它可能需要重新排列元素.

• VecDeque<T>实现From<Vec<T>>,因此VecDeque::from(vec)将向量转换为双端队列.这也是O(n),但它通常很快,即使向量很大,因为向量的堆分配可以简单地移动到新的双端队列.

此方法使得即使没有标准的vec_deque![]宏,也可以轻松创建具有指定元素的双端队列:

use std::collections::VecDeque;

let v = VecDeque::from(vec![1, 2, 3, 4]);

LinkedList<T>(LinkedList<T>)

链表(linked list) 是另一种存储值序列的方式.每个值都存储在单独的堆分配中,如图16-4所示.

图16-4. 内存中的LinkedList<char>

std::collections::LinkedList<T>是Rust的双向链表.它支持VecDeque方法的一个子集.在序列的front和back操作的方法都有;迭代器方法也有,LinkedList::new()和其他一些方法也是如此.但是,通常会省略通过索引访问元素的方法,因为通过索引访问链表元素本身效率很低.

从Rust1.17开始,Rust的LinkedList类型没有方法用于从列表中删除一系列元素或在列表中的特定位置插入元素.API似乎不完整.

目前,LinkedList优于VecDeque的主要优点是合并两个列表非常快.list.append(&mut list2)方法,将所有元素从一个列表移动到另一个列表的,只涉及更改几个指针,这可以在常量时间内完成.Vec和VecDeque的append方法有时必须将许多值从一个堆数组移动到另一个堆数组.

BinaryHeap<T>(BinaryHeap<T>)

BinaryHeap是一个集合,其元素保持松散组织,最大值始终冒泡到队列的前面.以下是三个最常用的BinaryHeap方法:

• heap.push(value)向堆中添加值.

• heap.pop()从堆中删除并返回最大值.它返回Option<T>,如果堆为空,则为None.

• heap.peek()返回对堆中最大值的引用.返回类型是Option<&T>.

BinaryHeap也支持Vec上的方法的一个子集,包括BinaryHeap::new(),.len(),.is_empty(),.capacity(),.clear()和.append(&mut heap2).

例如,如果我们用一堆数字填充BinaryHeap:

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::from(vec![2, 3, 8, 6, 9, 5, 4]);

那么值9位于堆的顶部:

assert_eq!(heap.peek(), Some(&9));
assert_eq!(heap.pop(), Some(9));

删除值9还会略微重新排列其他元素,以便8现在位于前面.依此类推:

assert_eq!(heap.pop(), Some(8));
assert_eq!(heap.pop(), Some(6));
assert_eq!(heap.pop(), Some(5));
...

当然,BinaryHeap不仅限于数字.它可以包含实现Ord内置trait的任何类型的值.

这使得BinaryHeap可用作工作队列.你可以根据优先级定义一个实现Ord的任务结构,以便优先级较高的任务Greater(大于)优先级较低的任务.然后,创建一个BinaryHeap来保存所有挂起的任务.它的.pop()方法将始终返回最重要的项目,即你的程序下一步应该处理的任务.

注意:BinaryHeap是可迭代的,它有一个.iter()方法,但是迭代器以任意顺序生成堆的元素,而不是从最大到最小.要按优先级顺序使用BinaryHeap中的值,请使用while循环:

while let Some(task) = heap.pop() {
    handle(task);
}

HashMap<K, V>和BTreeMap<K, V>(HashMap<K, V> and BTreeMap<K, V>)

map是键-值对(称为 entries(条目))的集合.没有两个条目具有相同的键,并且条目是有组织的,因此如果你有键,则可以高效地在映射中查找相应的值.简而言之,映射是查找表.

Rust提供两种映射类型:HashMap<K, V>和BTreeMap<K, V>.两者共享许多相同的方法;不同之处在于两者如何安排条目进行快速查找.

HashMap将键和值存储在哈希表中,因此它需要一个实现Hash和Eq的键类型K,Hash和Eq是哈希和相等性的标准traits.

图16-5显示了如何在内存中安排HashMap.深灰色区域未使用.所有键,值和缓存的哈希码都存储在单个堆分配表中.添加条目最终会强制HashMap分配更大的表并将所有数据移入其中.

图16-5. 内存中的HashMap.

BTreeMap按键在树结构中按顺序存储条目,因此它需要一个实现Ord的键类型K.图16-6显示了BTreeMap.同样,深灰色区域是未使用的备用容量.

16-6. 内存中的BtreeMap.

BTreeMap将其条目存储在 节点(nodes) 中.BTreeMap中的大多数节点仅包含键-值对.非叶节点(如此图中显示的根节点)也有指向子节点的空间.(20, 'q')和(30, 'r')之间的指针指向包含20到30之间的键的子节点.添加条目通常需要将某些节点的现有条目向右滑动,以使它们保持排序,并且偶尔会涉及分配新节点.

这张图片有点简化以适合页面.例如,真正的BTreeMap节点有11个条目的空间,而不是4个.

Rust标准库使用B树(B-trees)而不是平衡二叉树,因为B树在现代硬件上更快.二叉树每次搜索可能使用比B树更少的比较,但是搜索B树具有更好的 局部性(locality) --也就是说,存储器访问被组合在一起而不是分散在整个堆中.这使得CPU缓存未命中更少.这是一个显着的速度提升.

有几种方法可以创建映射:

• HashMap::new()和BTreeMap::new()创建新的,空的映射.

• iter.collect()可用于从键-值对创建和填充新的HashMap或BTreeMap,,iter必须是Iterator<Item=(K, V)>.

• HashMap::with_capacity(n)创建一个新的空的哈希映射,其中至少有n个条目的空间.HashMap与向量一样,将它们的数据存储在单个堆分配中,因此它们具有容量和相关方法hash_map.capacity(),hash_map.reserve(additional)和hash_map.shrink_to_fit().BTreeMap没有.

HashMap和BTreeMap具有相同的核心方法来处理键和值:

• map.len()返回条目数.

• map.is_empty(),如果映射没有条目,它返回true.

• map.contains_key(&key),如果映射有给定键的条目,则返回true.

• map.get(&key)搜索map具有给定key的条目.如果找到匹配的条目,则返回Some(r),其中r是对应值的引用.否则,返回None.

• map.get_mut(&key)类似,但它返回值的mut引用.

通常,映射允许你对存储在其中的值进行mut访问,但键不允许.这些值由你随意修改.键属于映射本身;它需要确保它们不会改变,因为条目是由它们的键组织的.就地修改键将是一个错误.

• map.insert(key, value)将条目(key, value)插入到map中.如果映射中已有key条目,则新插入的value将覆盖旧值.

返回旧值(如果有).返回类型是Option<V>.

• map.extend(iterable)迭代iterable的(K, V)项,并将每个键-值对插入到map中.

• map.append(&mut map2)将map2中的所有条目移动到map中.之后,map2为空.

• map.remove(&key)从map中查找和删除具有给定key的任何条目.

返回已删除的值(如果有).返回类型是Option<V>.

• map.clear()删除所有条目.

也可以使用方括号查询映射:map[&key].也就是说,m映射实现了Index内置trait.但是,如果没有给定key的条目(类似越界数组访问),则会发生恐慌,因此仅当你要查找的条目确实已填充时才使用此语法.

.contains_key(),.get(),.get_mut()和.remove()的key参数不必具有确切的类型&K. 这些方法对于可以从K借用的类型是通用的.可以在HashMap<String, Fish>上调用fish_map.contains_key("conger"),即使"conger"并不是String,因为String实现了Borrow<&str>.有关详细信息,请参见296页的"Borrow和BorrowMut(Borrow and BorrowMut)".

因为BTreeMap保持条目按键排序,所以它支持额外的操作:

• btree_map.split_at(&key)将btree_map分成两部分.键小于key的条目留在btree_map中.返回一个包含其他条目的新的BTreeMap<K, V>.

条目(Entries)

HashMap和BTreeMap都有相应的Entry类型.条目的要点是消除冗余映射查找.例如,以下是获取或创建学生记录的一些代码:

// Do we already have a record for this student?
if !student_map.contains_key(name) {
    // No: create one.
    student_map.insert(name.to_string(), Student::new());
}
// Now a record definitely exists.
let record = student_map.get_mut(name).unwrap();
...

这工作正常,但它访问student_map两次或三次,每次执行相同的查找.

条目的想法是我们只进行一次查找,产生一个Entry值,然后用于所有后续操作.这个单行代码相当于上面的所有代码,只是它只执行一次查找:

let record = student_map.entry(name.to_string()).or_insert_with(Student::new);

student_map.entry(name.to_string())返回的Entry值就像一个对映射中某个位置的可变引用,这个位置要么被键-值对 占用(occupied) ,要么是 空的(vacant) ,这意味着这里还没有条目.如果为空,条目的.or_insert_with()方法会插入一个新的Student.条目的大多数用法是这样的:简短而甜蜜.

所有Entry值都是通过相同的方法创建的:

• map.entry(key)返回给定键的Entry.如果映射中没有这样的键,则返回空Entry.

此方法通过mut引用获取其self参数,并返回具有匹配生命周期的Entry:

pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>

Entry类型具有生命周期参数'a,因为它实际上是对映射的借用的mut引用.只要Entry存在,它就可以独占访问映射.

在第109页的"包含引用的结构(Structs Containing References)"中,我们了解了如何在类型中存储引用,以及它如何影响生命周期.现在我们从用户的角度看看它是什么样子.这就是Entry正在发生的事情.

不幸的是,如果映射具有String键,则无法将类型&str的引用传递给此方法.在这种情况下,.entry()方法需要一个真正的String.

Entry值提供两个填写空条目的方法:

• map.entry(key).or_insert(value)确保map包含具有给定key的条目,如果需要,插入具有给定默认value的新条目.它返回对新值或现有值的mut引用.

假设我们需要计算投票数.我们可以写:

let mut vote_counts: HashMap<String, usize> = HashMap::new();
for name in ballots {
    let count = vote_counts.entry(name).or_insert(0);
    *count += 1;
}

.or_insert()返回一个mut引用,因此count的类型是&mut usize.

• map.entry(key).or_insert_with(default_fn)是相同的,只不过如果它需要创建一个新条目,它调用default_fn()来产生默认值.如果地图中已有key条目,则不使用default_fn.

假设我们想知道哪些单词出现在哪些文件中.我们可以写:

// This map contains, for each word, the set of files it appears in.
let mut word_occurrence: HashMap<String, HashSet<String>> =
    HashMap::new();
for file in files {
    for word in read_words(file)? {
        let set = word_occurrence
            .entry(word)
            .or_insert_with(HashSet::new);
        set.insert(file.clone());
    }
}

Entry类型是一个枚举,为HashMap定义(对于BTreeMap类似):

// (in std::collections::hash_map)
pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>)
}

OccupiedEntry和VacantEntry类型具有插入,删除和访问条目的方法,而无需重复初始查找.你可以在在线文档中找到它们.额外的方法偶尔可以用于消除一个冗余查找或两个,但.or_insert()和.or_insert_with()涵盖常见情况.

映射迭代(Map Iteration)

迭代映射有几种方法:

• 按值迭代("for (k, v) in map")生成(K, V)对.这会消耗映射.

• 迭代共享引用("for (k, v) in &map")生成(&K, &V)对.

• 迭代mut引用("for (k, v) in &mut map")生成(&K, &V)对.(同样,没有办法对存储在映射中的key进行mut访问,因为条目是按其键组织的.)

与向量一样,映射具有.iter()和.iter_mut()方法,这些方法通过引用返回迭代器,就像迭代&map或&mut map一样.此外:

• map.keys()通过引用仅返回键上的迭代器.

• map.values()通过引用返回值上的迭代器.

• map.values_mut()通过mut引用返回值上的迭代器.

所有HashMap迭代器都以任意顺序访问映射的条目.BTreeMap迭代器按键顺序访问它们.

HashSet<T>和BTreeSet<T>(HashSet<T> and BTreeSet<T>)

Sets 是为快速成员资格测试而安排的值集合.

let b1 = large_vector.contains("needle");    // slow, checks every element
let b2 = large_hash_set.contains("needle");  // fast, hash lookup

集永远不会包含相同值的多个副本.

映射和集有不同的方法,但在幕后,集就像只有键而不是键-值对的映射.事实上,Rust的两个集类型HashSet<T>和BTreeSet<T>实现为围绕HashMap<T, ()>和BTreeMap<T, ()>的薄包装器.

• HashSet::new()和BTreeSet::new()创建新集.

• iter.collect()可用于从任何迭代器创建新集.如果iter多次生成任何值,则删除重复项.

• HashSet::with_capacity(n)创建一个空的HashSet,其空间至少为n个值.

HashSet<T>和BTreeSet<T>具有所有常见方法:

• set.len()返回set中的值数.

• set.is_empty(),如果集不包含任何元素,则返回true.

• set.contains(&value),如果集合包含给定value,则返回true.

• set.insert(value)为集添加value.如果添加了值,则返回true;如果已经是该集的成员,则返回false.

• set.remove(&value)从集合中删除value.如果删除了值,则返回true;如果已经不是该集合的成员,则返回false.

与映射一样,通过引用查找值的方法对于可以从T借用的类型是通用的.有关详细信息,请参见第296页的"Borrow和BorrowMut(Borrow and BorrowMut)".

集迭代(Set Iteration)

迭代集有两种方法:

• 按值迭代("for set in set")会生成集的成员(并消耗集).

• 通过共享引用迭代("for set in &set")生成对s集的成员的共享引用.

不支持通过mut引用对集进行迭代.没有办法获得对存储在集中的值的mut引用.

• set.iter()通过引用返回set成员上的迭代器.

HashSet迭代器与HashMap迭代器一样,以任意顺序生成它们的值.BTreeSet迭代器按顺序生成值,就像排序向量一样.

当相等的值不同时(When Equal Values Are Different)

集有一些奇怪的方法,只有在关心"相等"值之间的差异时才需要使用它们.

这种差异经常存在.例如,两个相同的String值将其字符存储在内存中的不同位置:

let s1 = "hello".to_string();
let s2 = "hello".to_string();
println!("{:p}", &s1 as &str);  // 0x7f8b32060008
println!("{:p}", &s2 as &str);  // 0x7f8b32060010

通常,我们不在乎.

但是如果你曾经这样做,你可以使用以下方法访问存储在集中的实际值.每一个都返回Option,如果set不包含匹配值,则返回None.

• set.get(&value)返回对set成员的共享引用,等于value的成员(如果有).返回Option<&T>.

• set.take(&value)与set.remove(&value)类似,但它返回已删除的值(如果有).返回Option<T>.

• set.replace(value)与set.insert(value)类似,但如果set已经包含一个等于value的值,则替换并返回旧值.返回Option<T>.

整集操作(Whole-Set Operations)

到目前为止,我们看到的大多数集方法都集中在单个集合中的单个值.集还具有对整个集合进行操作的方法.

• set1.intersection(&set2)返回同时在set1和set2中所有值的迭代器.

例如,如果我们要打印所有同时参加脑外科和火箭科学课程的学生的姓名，我们可以写:

for student in brain_class {
    if rocket_class.contains(&student) {
        println!("{}", student);
    }
}

或者简写:

for student in brain_class.intersection(&rocket_class) {
    println!("{}", student);
}

令人惊讶的是,为此有一个运算符.

&set1 & &set2返回一个新集,它是set1和set2的交集.这是二进制按位AND运算符,应用于两个引用.这将查找同时在set1 AND set2中的值.

let overachievers = &brain_class & &rocket_class;

• set1.union(&set2)返回在set1或set2或同时在两者中的值上的迭代器.

&set1 | &set2返回包含所有这些值的新集.它找到set1 OR set2中的值.

• set1.difference(&set2)返回一个在set而不在set2中的值上的迭代器.

&set1 - &set2返回一个包含所有这些值的新集.

• set1.symmetric_difference(&set2)返回在set1或set2中的,但不是同时在两者中的值上的迭代器.

&set1 ^ &set2返回包含所有这些值的新集.

测试集之间的关系有三种方法:

• set1.is_disjoint(set2),如果set1和set2没有共同的值,则为true--它们之间的交集为空.

• set1.is_subset(set2),如果set1是set2的子集,则为true,即set1中的所有值也在set2中.

• set1.is_superset(set2)是相反的:如果set1是set2的超集.则为true.

集合也支持使用==和!=进行相等性测试;如果它们包含相同的值,则两集相等.

哈希(Hashing)

std::hash::Hash是可哈希的类型的标准库trait.HashMap键和HashSet元素必须同时实现Hash和Eq.

实现Eq的大多数内置类型也实现了Hash.整数类型,char和String都是可哈希的;元组,数组,切片和向量也是如此,只要它们的元素是可哈希的.

标准库的一个原则是一个值应该具有相同的哈希码,无论你将它存储在哪儿或如何指向它.因此,引用具有与其引用的值相同的哈希码,并且Box具有与装箱值相同的哈希码.向量vec与包含其所有数据的切片(&vec[..])具有相同的哈希码.String与具有相同字符的&str具有相同的哈希码.

默认情况下,结构和枚举不实现Hash,但可以派生实现:

/// The ID number for an object in the British Museum's collection.
#[derive(Clone, PartialEq, Eq, Hash)]
enum MuseumNumber {
    ...
}

只要类型的字段都是可哈希的,这就可以工作.

如果手动为类型实现PartialEq,则还应手动实现Hash.例如,假设我们有一种代表无价历史宝藏的类型:

struct Artifact {
    id: MuseumNumber,
    name: String,
    cultures: Vec<Culture>,
    date: RoughTime,
    ...
}

如果两个Artifact具有相同的ID,则认为它们是相同的:

impl PartialEq for Artifact {
    fn eq(&self, other: &Artifact) -> bool {
        self.id == other.id
    }
}

impl Eq for Artifact {}

因为我们纯粹基于它们的ID来比较artifacts,所以我们必须以相同的方式对它们进行哈希:

impl Hash for Artifact {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        // Delegate hashing to the MuseumNumber.
        self.id.hash(hasher);
    }
}

(否则,HashSet<Artifact>将无法正常工作;与所有哈希表一样,如果a == b,则需要hash(a) == hash(b).)

这允许我们创建一个Artifacts的HashSet:

let mut collection = HashSet::<Artifact>::new();

正如此代码所示,即使你手动实现Hash,也不需要了解任何有关哈希算法的知识..hash()接收对Hasher的引用,Hasher表示哈希算法.你只需向Hasher提供与==运算符相关的所有数据.Hasher根据你提供的任何内容计算哈希码.

使用自定义哈希算法(Using a Custom Hashing Algorithm)

hash方法是通用的,因此上面显示的Hash实现可以将数据提供给实现Hasher的任何类型.这就是Rust支持可插拔哈希算法的方式.Hash和Hasher是伙伴trait,如第258页的"Buddy Traits(或rand::random()如何工作)"中所述.

第三个traitstd::hash::BuildHasher是表示哈希算法初始状态的类型的trait.每个Hasher都是一次性使用的,就像迭代器一样:你使用它一次就扔掉它.BuildHasher是可重用的.

每个HashMap都包含一个BuildHasher,每次需要计算哈希码时都会使用它.BuildHasher值包含哈希算法每次运行时所需的密钥,初始状态或其他参数.

用于计算哈希码的完整协议如下所示:

use std::hash::{Hash, Hasher, BuildHasher};

fn compute_hash<B, T>(builder: &B, value: &T) -> u64
    where B: BuildHasher, T: Hash
{
    let mut hasher = builder.build_hasher();  // 1. start the algorithm
    value.hash(&mut hasher);                  // 2. feed it data
    hasher.finish()                           // 3. finish, producing a u64
}

每次需要计算哈希码时,HashMap都会调用这三个方法.所有方法都是可以内联的,所以速度非常快.

Rust的默认哈希算法是一种众所周知的算法,称为SipHash-1-3.SipHash很快,并且非常适合最小化哈希冲突.事实上,它是一种加密算法:没有已知的有效方法来生成SipHash-1-3冲突.只要每个哈希表使用不同的,不可预测的密钥,Rust就可以抵御一种名为HashDoS的拒绝服务(denial-of-service)攻击,攻击者故意使用哈希冲突来触发服务器中的最坏情况性能.

但也许你的应用程序不需要那个.如果要存储许多小键,例如整数或非常短的字符串,则可以实现更快的哈希函数,但代价是HashDoS安全性.fnvcrate实现了一种这样的算法,即Fowler-Noll-Vo哈希.要试用它,请将此行添加到你的 Cargo.toml :

[dependencies]
fnv = "1.0"

然后从fnv导入映射和集类型:

extern crate fnv;

use fnv::{FnvHashMap, FnvHashSet};

你可以将这两种类型用作HashMap和HashSet的插件替换.在fnv源代码中查看它们是如何定义的:

/// A `HashMap` using a default FNV hasher.
pub typeFnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;

/// A `HashSet` using a default FNV hasher.
pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;

标准HashMap和HashSet集合接受指定哈希算法的可选额外类型参数;FnvHashMap和FnvHashSet是HashMap和HashSet的泛型类型别名,为该参数指定FNV哈希.

超越标准集合(Beyond the Standard Collections)

在Rust中创建一个新的,自定义的集合类型与任何其他语言都是一样的.你可以通过组合语言提供的部分来排列数据:结构和枚举,标准集合,Option,Box等.有关示例,请参阅第218页的"泛型枚举(Generic Enums)"中定义的BinaryTree<T>类型.

如果你习惯于在C++中实现数据结构,使用原始指针,手动内存管理,放置new和显式析构函数调用来获得最佳性能,那么毫无疑问,你会发现Rust安全而非限制.所有这些工具本质上都是不安全的.它们在Rust中可用,但仅限于你选择使用不安全的代码.第21章说明了如何做到;它包含一个使用一些不安全代码来实现安全自定义集合的示例.

目前,我们只是沉浸在标准集合的温暖光芒中,以及它们安全,高效的API中.与Rust标准库的大部分内容一样,它们旨在确保编写"unsafe"的需求尽可能少.