当前位置：网站首页>【Rust 笔记】14-集合（上）

【Rust 笔记】14-集合（上）

2022-07-05 05:50:00 【phial03】

14 - 集合（上）

14.1 - 概述

集合：集合性的泛型类型。
Rust 集合与其他语言中集合的差异：
- Rust 使用转移来避免深复制。
- 借用
  检查器可以使得 Rust 在编译时，排除无效错误。无效错误如下：
  - 在集合中保存数据指针，当在集合缩放或被修改后，会出现悬空指针。
  - C++ 中的未定义行为。
  - 在内存安全中的语言，无效错误可能导致 ConcurrentModificationException。
- Rust 没有null
  - 在其他语言中出现 null 的地方，Rust 用 Option 代替。

标准集合：

Rust 集合	说明	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>：【常见集合】是可增长的、分配在堆上的类型 T 的值的数组。
VecDeque<T>：与 Vec<T> 类似，但适合作为先进先出队列使用。
- 支持在列表前端和后端高效地添加和移除值。
- 会导致其他所有操作变慢。
LinkedList<T>：支持在列表前、后端快速存取。
- 与 VecDeque<T> 功能类似，但是增加了快速连接。
- 通常来说，稍慢于 Vec<T> 和 VecDeque<T>。
BinaryHeap<T>：优先队列。值的组织方式始终适合查找和移除最大值。
HashMap<K, V>：【常见集合】是一个键 — 值对的表，按键查值很快。条目以任意顺序存储。
BTreeMap<K, V>：与 HashMap<K, V> 功能类似，但条目以键的顺序存储。
- 比如：BTreeMap<String, i32> 按字符串比较顺序存储器条目。
- 除非需要按序存储条目，否则 HashMap<K, V> 更快。
HashSet<T>：【常见集合】是一组类型 T 的值。常用于：
- 快速添加和移除值。
- 快速检查给定值是否在集合中存在。
BTreeSet<T>：与 HashSet<T> 功能类似，但值是按顺序存储的。同样，除非需要保证数据的顺序，否则 HashSet<T> 更快。

14.2-`Vec<T>`

创建向量的最简单方式是使用 vec! 宏：

// 创建空向量
let mut numbers: Vec<i32> = vec![];

// 创建包含给定内容的向量
let words = vec!["step", "on", "no", "pets"];
let mut buffer = vec![0u8; 1024];  // 1024个填充0的字节

向量有 3 个字段：长度、容量和指向存储其元素的堆内存的指针。

Vec 和所有集合一样，实现了 std::iter::FromIterator，因此可以使用迭代器的.collect() 方法，基于任何迭代器创建向量：

// 把另一个集合转换为向量
let my_vec = my_set.into_iter().collect::<Vec<String>>();

// 等效于
let my_vec: Vec<String> = my_set.into_iter().collect();

14.2.1 - 访问元素

通过索引可以直观地获取数组、切片或向量的元素：

// 取得一个元素的引用
let first_line &lines[0];

// 取得一个元素的副本
let fifth_number = numbsers[4];        // 实现Copy
let second_line = lines[1].clone();    // 实现Clone

// 取得一个切片的引用
let my_ref = &buffer[4..12];

// 取得一个切片的副本
let my_copy = buffer[4..12].to_vec();  // 实现Clone

如果索引越界，那么上述所有访问形式都会诧异。
向量的长度和索引是 usized 类型。必要时可以使用 n as usize 转换。
所有切片的方法也可在数组和向量上使用。

slice.first()：返回对 slice 第一个元素的引用。返回值类型是 Option<T>：
- 如果 slice 为空，则返回 None。
- 如果不为空，则返回 Some(&slice[0])。
slice.last()：返回最后一个元素的引用。
slice.get(index)：返回 slice[index] 的引用。
- 如果越界，则返回 None。
- 如果成功，则返回 Some（&index）引用。
slice.first_mut()、slice.last_mut() 和 slice.get_mut()：是上面几个方法的变体，返回 mut 引用。
- 返回 T 值意味着转移，所以就地访问元素的方法通常都返回元素的引用。
- 下面的.to_vec() 方法是个例外，它返回元素的副本。
slice.to_vec()：克隆整个切片，翻译一个新向量。
- 只在元素是可以克隆（where T: Clone）的情况下才有效。

14.2.2 - 迭代

向量和切片是可以迭代的：既可以按值迭代，也可以按引用迭代。
- 迭代 Vec<T> 产生 T 类型的项：元素逐个从向量中转移出来，并被消费。
- 迭代 &[T; N]、&[T] 或 &Vec<T> 类型的值：即对数组、切片或向量的引用，产生 &T 类型的项。对个别元素的引用，不会发生转移。
- 迭代 &mut [T: N]、&mut [T] 或 &mut Vec<T> 类型的值：产生 &mut T 类型的项。
数组、切片和向量还有.iter() 和.iter_mut() 方法：创建的迭代器产生对它们元素的引用。

14.2.3 - 增长和收缩向量

数组、切片和向量的长度：表示它们包含元素的数量。
- slice.len()：返回 slice 的长度，类型为 usize。
- slice.is_empty()：在 slice 不包含元素时，即 slice.len() == 0 时，返回 true。
数组和切片的大小是不可变的，所以不支持下面的增大和收缩方法。
向量的特点：
- 向量的所有元素都存储在分配在堆上的连续内存块中。
- 向量的容量是这个块中可以容纳的最大元素数量。
- 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 分配的空间不能超过 n，不考虑未来是否增长。vec.capacity() = vec.len() + n。
- vec.shrink_to_fit()：当 vec.capacity() > vec.len() 时，会尝试释放额外的内存。
Vec<T> 有很多以向量的可修改引用（&mut self）为参数的方法，可以添加和移除元素，以改变向量的长度。
在向量末尾添加或移除一个值：
- vec.push(value)：在 vec 末尾添加给定的 value 值。该方法取得参数的值，而不是引用。
- vec.pop()：移除并返回最后一个元素。返回值的类型是 Option<T>：如果最后一个元素是 x，则返回 Some(x)；如果向量为空，则返回 None。该方法返回元素的值，而非引用。
在向量的任何地方添加或移除值：要移动的元素越多，.insert() 和.remove() 的速度越慢。
- vec.insert(index, value)：在 vec[index] 中插入 value，并将 vec[index..] 中的值向右顺移一个位置。如果 index > vec.len() 则发生诧异。
- vec.remove(index)：移除并返回 vec[index]，并将 vec[index+1..] 中的值向左顺移一个位置。如果 index >= vec.len() 则发生诧异。如果要经常使用该方法，那么建议使用 VecDeque<T> 来操作数据，而不是 Vec<T>。
将向量的长度修改为指定值：
- vec.resize(new_len, value)：将向量长度设置为 new_len，如果长度增长，那么将 value 值放在新增长的位置。要求元素的类型必须实现 Clone 特型。只有这个方法会克隆值，其他的方法都是把值从一个地方转移到另一个地方。
- vec.truncate(new_len)：将向量长度减少为 new_len，并消除范围在 vec[new_len..] 之内的元素。如果 vec.len() <= new_len，则保持向量现状。
- vec.clear()：从 vec 中移除所有元素，相当于 vec.truncate(0)。
一次添加或移除多个值：
- vec.extend(iterable)：按顺序将 iterable 的所有项添加到 vec 末尾。类似给.push() 传入多个值。iterable 参数是可以实现 IntoIterator<Item=T> 的任何值。所有集合都实现了 Extend 特型，其中包含了这个方法。
- vec.split_off(index)：与 vec.truncate(index) 功能类似，但它会返回一个包含从 vec 末尾移除值的 Vec<T>。相当于是多个值版的.pop()。
- vec1.append(&mut vec2)：把 vec2（Vec<T> 类型的向量）的所有元素转移到 vec1。vec2 会变为空。与 vec1.extend(vec2) 不同的是，vec2 在转移后仍然存在，且容量不受影响。
- vec.drain(range)：从 vec 中移除范围 vec[range]。返回被移除元素的迭代器。range 是一个范围值，如.. 或 0..4。
从向量中选择性地移除元素：
- vec.retain(test)：移除所有没有通过给定测试的元素。test 参数是一个实现了 FnMut(&T) -> bool 的函数或闭包。对 vec 的每个元素，都会调用 test(&element)：如果返回 false，则从向量中移除 element，并将其清除。原理上等同于下述代码，但是性能要更好：
```
vec = vec.into_iter().filter(test).collect();
```
- vec.dedup()：清除重复的元素。扫描 vec，对比相邻的元素，如果发现相等，则清除额外相等的值，值保留一个。
```
let mut byte_vec = b"Missssssissippi".to_vec();
byte_vec.dedup();
assert_eq!(&byte_vec, b"Misisipi");
```
  如结果所示，这个方法只清除连续的重复值。如果要去掉所有的重复值，那么有三种方法：
  1、调用.dedup 之前把向量排序；
  2、把数据转移到集合中；
  3、使用.retain() 方法，可以保持元素原始的顺序：
```
let mut byte_vec = b"Missssssissippi".to_vec();

let mut seen = HashSet::new();
byte_vec.retain(|r| seen.insert(*r)); // .insert()在集中包含要插入项时会返回false。

assert_eq!(&byte_vec, b"Misp");
```
- vec.dedup_by(same)：与 vec.dedup() 功能类似，不同的是它使用函数或闭包 same(&mut elem1, &mut elem2)，而不是 == 操作符判断两个元素是不是重复。
- vec.dedup_by_key(key)：与 vec.dedup() 功能类似，不同的是它判断两个元素重复的依据是 key(&mut elem1) == key(&mut elem2)。举例：如果 error 是一个 Vec<Box<Error>> 类型的值：
```
// 移除消息内容重复的错误
errors.dedup_by_key(|err| err.description().to_string());
```

14.2.4 - 连接

数组的数组：包括任何数组、切片或向量，其元素本身也是数组、切片或向量。
对于数组的数组有以下两个特殊的方法：
- slices.concat()：返回拼接所有切片得到的新向量。
```
assert_eq!([[1, 2], [3, 4], [5, 6]].concat(), vec![1, 2, 3, 4, 5, 6]);
```
- slices.join(&separator)：与 slices.concat() 类似，不通的是会把 separator 的副本插入到切片之间。
```
assert_eq!([[1, 2], [3, 4], [5, 6]].join(&0), vec![1, 2, 0, 3, 4, 0, 5, 6]);
```

14.2.5 - 拆分

Rust 通过索引方式操作数组、切片或向量的注意事项：

支持同时取得多个不可修改引用的数组、切片或向量：

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..];

不支持同时取得多个可修改引用的数组、切片或向量：

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
// 如果i == j，那么相当于两个可修改引用操作了相同的整数。

Rust 支持许多方法，可以不直接修改数组、切片或向量，而是返回对其中部分数据的新的引用，用来实现拆分操作：保证了把数据拆分为不重叠的区块，有许多方法分为 mut 和非 mut 两个版本。
- slice.iter() 和 slice.iter_mut()：返回的迭代器产生 slice 中每个元素的引用。
- 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_firt() 返回值的类型是 Option<(&T, &[T])>。如果切片为空，则返回 None。
- slice.split_last() 和 slice.split_last_mut()：返回一个元组，包含最后一个元素的引用和对所有剩余元素切片的引用。
  .split_last() 返回值的类型是 Option<(&[T], &T)>。
- slice.split(is_sep) 和 slice.split_mut(is_sep)：基于函数或闭包 is_sep，将 slice 拆分为一个或多个子切片，返回子切片的迭代器。
  在消费返回的迭代器时，会对切片中的每个元素调用 is_sep(&element)。如果返回 true，则这个元素就是分隔符。分隔符元素不包含在输出的任何子切片中。
  输出始终包含至少一个子切片，多一个分隔符元素就会多出一个子切片。
  如果多个分隔符相邻或者分隔符是 slice 的最后一个元素，则输出会包含空子切片。
- slice.splitn(n, is_sep) 和 slice.splitn_mut(n, is_sep)：基于函数或闭包 is_sep，将 slice 拆分为 n 个子切片，返回子切片的迭代器。在找到前n-1 个切片后，就不会再调用 is_sep，最后一个子切片包含所有剩余元素。
- slice.rsplitn(n, is_sep) 和 slice.rsplitn_mut(n, is_sep)：反向扫描切片。基于函数或闭包 is_sep，将 slice 拆分为 n 个子切片，返回子切片的迭代器。在找到后n-1 个切片后，就不会再调用 is_sep。
- slice.chunks(n) 和 slice.chunks_mut(n)：返回的迭代器是一个长度为 n 的非重叠子切片。如果 slice.len() 不是 n 的倍数，则最后一个子切片长度小于 n。
- 针对子切片的迭代方法 slice.windows(n)：返回的迭代器类似 slice 数据的滑动窗口。这个迭代器产生包含 slice 中 n 个连续元素的子切片（重叠的籽切片，没有返回 mut 引用的变体）。
  产生的第一个子切片是 &slice[0..n]，第二个子切片是 &slice[1..n+1]，以此类推。
  如果 n > slice.len()，则不会产生切片；如果 n == 0，则这个方法会诧异。
  技巧：大小为 2 的滑动窗口，可用于检测数据序列中两个数据点的变化：
```
let changes = daily_high_temperatures
    .windows(2)             // 取得相邻两天的温度
    .map(|w| w[1] - w[0])   // 计算温差
    .collect::<Vec<_>>();
```

14.2.6 - 交换

slice.swap(i, j)：交换 slice[i] 和 slice[j] 这两个元素。
```
vec.swap_remove(i)
```
：对于向量，支持高效移除任意元素的项对方法。
- 移除并返回 vec[i]，跟 vec.remove(i) 类似。
- 但不会把后面的元素向前移动，以填补空缺，而是简单地把 vec 的最后一个元素移到空位上。
- 在不关心向量剩余元素顺序的情况下可以使用。

14.2.7 - 排序和搜索

常用的排序方法：
- slice.sort()：对元素进行递增排序。需要保证元素类型实现了 Ord 特型。
- slice.sort_by(cmp)：使用指定排序方式的函数或闭包 cmp，对 slice 的元素进行排序。
  cmp 必须实现了 Fn(&T, &T) -> std::cmp::Ordering。
  Rust 支持.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)：按照排序键对 slice 的元素递增排序，排序键可以使用函数或闭包 key 给出。key 的类型必须实现了 Fn(&T) -> K where K: Ord 特型。执行排序期间，不会缓存排序键的值，因此 key 可能会被调用多次。
  如果 T 包含一个或多个可排序字段时，可以选择多种排序方式：
```
// grade_point_average()实现了一种排序方法：
// 按年级平均分排序，最低分排前面
students.sort_by_key(|s| s.grade_point_average())
```
  key(element) 不能返回从元素借用的引用。如下面的调用，但可以使用.sort_by()：
```
students.sort_by_key(|s| &s.last_name);  // 错误，不能推断生命期
```
反向排序方法：
- 使用.sort_by，并传入两次参数调换了次序的 cmp 闭包。比如 |b, a|，而不是 |a, b|，那么就会执行反向排序。
- slice.reverse()：对切片元素就地反向排序。
排序完成后，可以执行高效的搜索方法：二分查找
- slice.binary_search(&value)、slice.binary_search_by(&value, cmp) 和 slice.binary_search_by_key(&value, key)：从排序后的切片中搜索 value 值，value 传的是引用。
- 它们的返回类型是 Result<usize, usize>。如果在指定的排序下，slice[index] == value，那么它们就返回 Ok(index)。如果没有找到这个索引值，那么就返回 Err(insertion_point)，此时在 insertion_point 位置插入 value 会保持顺序。
- f32 和 f64 有 NaN 值，所以它们都未实现 Ord，因此不能直接作为键用于排序和二分查找。如果一定要对浮点数操作，那么可以选择使用 ord_subset 包。
搜索未排序向量的方法：
- slice.contains(&value)：在 slice 的任意元素等于 value 时，返回 true。此方法会逐个检切片的元素。
- 如果要查找值在切片中的位置，实现类似 JavaScript 中的 array.indexOf(value) 的效果，则可以使用以下迭代器：
```
slice.iter().position(|x| *x == value);
// 这个迭代器返回的是`Option<usize>`
```

14.2.8 - 比较切片

如果类型 T 支持 == 和 != 操作符，那么数组 [T; N]、切片 [T]、向量 Vec<T> 也会支持。
- 如果切片的长度项对，对应的每个元素也相等，那么它们就会相等。
- 数组和向量也遵循上述规则。
如果类型 T 支持 <、<=、> 和 >= 操作符，那么数组 [T; N]、切片 [T]、向量 Vec<T> 也会支持。切片的比较是按照词典顺序进行的。
常用的切片比较方法
- slice.starts_with(other)：在 slice 开头的一系列值等于另一个切片 oterh 的元素时，此方法会返回 true：
```
assert_eq!([1, 2, 3, 4].start_with(&[1, 2]), true);
assert_eq!([1, 2, 3, 4].start_with(&[2, 3]), false);
```
- slice.ends_with(other)：针对 slice 末尾的一系列值进行比较。
```
assert_eq!([1, 2, 3, 4].start_with(&[3, 4]), true);
```

14.2.9 - 随机元素

随机数没有内置在标准库中。rand 包提供了以下方法，用于从数组、切片或向量中取得随机输出。
- rng.choose(slice)：返回对 slice 中随机元素的引用。返回值为 Option<&T>，只有在切片为空时会返回 None。
- rng.shuffle(slice)：对 slice 元素就地随机排序。必须传入 slice 的可修改引用。
上述方法出自 rand::Rng 特型，调用他们需要一个 Rng（随机数生成器）。
- 通过调用 rand::thread_rng() 可以获取 Rng；
- 要打乱 my_vec 的顺序，可以执行：
```
use rand::{
        Rng, thread_rng};
thread_rng().shuffle(&mut my_vec);
```

14.2.10-Rust 排除无效错误的原理

不要在迭代集合的时候修改它。
在 Python 中会遇到这样的无效错误：在迭代期间修改数据导致了迭代器无效。
```
my_list = [1, 3, 5, 7, 9]
for index, val in enumerate(my_list):
    if val > 4:
        del my_list[index]  # bug: 迭代过程中修改列表
print(my_list)
# 输出结果：[1, 3, 7]，7大于4。
```
- 在 Java 中，上面的实现会产生异常；
- 在 C++ 中，这是一个未定义行为；
- 在 Python 中，虽然这个行为有明确定义，但是不直观：迭代器跳过一个元素。
Python 或其他语言，可以使用 filter 创建一个新向量来修复上述问题。

使用 Rust 复现上述错误：

fn main() {
      
    let mut my_vec = vec![1, 3, 5, 6, 8];
    for (index, &val) in my_vec.iter().enumerate() {
      
        if val > 4 {
      
            my_vec.remove(index);   // bug：不能借用my_vec的可修改引用
            // my_vec.retain(|&val| val <= 4); // 修复上述bug的方法
        }
    }
    println!("{:?}", my_vec);
}