8 集合

有三种常用的集合结构

vector

下面按使用vector的几种重要操作来介绍。

新建

可以调用 Vec::new 函数，或者Vec::from

    let v: Vec<i32> = Vec::new();
    let v2 = Vec::from([0, 0, 0]);

还可以使用 vec! 宏

    let v = vec![1, 2, 3];

vec! 宏，它会创建一个新的 vector，并把你提供的值放进去。

Rust 会通过push或者vec!中的数据推断出你想存储的值的类型，所以很少需要写这种类型注解。

更新

首先使用 mut 关键字让它变成可变的。

通过索引的方式，效率更高，但是容易导致索引越界的问题。
使用get方法会获得Option<T>需要进行额外的匹配，性能也略有消耗，但是更加安全。

获取到元素的可变引用就可以进行修改。

删除

遍历访问

into_iter()是所有权变量的迭代。
iter()是不可变引用的迭代。
iter_mut()是可变引用的迭代。
而for i in v就是for i in v.into_iter()的语法糖。
还有for i in &v 等于 for i in v.iter()
for i in &mut 等于 for i in v.iter_mut()

常用方法

容量操作

初始化时设置容量

Vec::with_capacity(10);

使用时更改容量

 v.reserve(100);        // 调整 v 的容量，至少要有 100 的容量

使用时释放剩余容量

 v.shrink_to_fit();     // 释放剩余的容量，一般情况下，不会主动去释放容量

获取容量大小

v.capacity()

元素操作

数组追加到末尾

 v.extend([1, 2, 3]);    // 附加数据到 v

移动其他vec的元素到自己

v.append(&mut v1);              // 将 v1 中的所有元素附加到 v 中, v1会被清空: []

删除指定范围的元素，同时获取被删除元素的迭代器

let mut m: Vec<_> = v.drain(1..=3).collect();    

截断到指定长度，多余的元素被删除

v.truncate(1);                  // 截断到指定长度，多余的元素被删除, v: len = 1

清空vec

v.clear();                      // 清空 v, v: []

定点插入

v.insert(2, 3);       // 在指定索引插入数据，索引值不能大于 v 的长度

定点删除

assert_eq!(v.remove(1), 2);     // 移除指定位置的元素并返回, v: [1, 3]

末尾弹出元素，为空则None，不空则Some<T>

assert_eq!(v.pop(), Some(3));   // 删除并返回 v 尾部的元素，v: [1]

末尾新增元素

v.push(1);

拆分操作

按索引切分成两个 vec（类似1..5这种，不取末尾5)

let v2 = m.split_off(1);        // 指定索引处切分成两个 vec, m: [22], v2: [33, 44]

排序操作

默认的sort使用的是归并排序 + 插入排序自适应优化，而sort_unstable是超强优化版快速排序，速度：比 sort() 快 20%~40%

但是就是相同排序值的顺序并不稳定。

rust提供的排序方法，只能用于实现了 Ord trait 的类型（i32, String 等），并且只能升序。

sort_by以及sort_unstable_by就是by其他判断元素大小的方法。

需要传入一个函数:

impl<T> [T]  
pub fn sort_by<F>(&mut self, mut compare: F)  
where  
F: FnMut(&T, &T) -> Ordering

// --- odering 是一个枚举
pub enum Ordering {
    Less = -1,
    Equal = 0,
    Greater = 1,
}

只要这个函数符合函数签名即可，可以是fn函数也可以是闭包函数。

我们可以重新组合Ord trait中的方法，来实现降序。Ord中必须要实现的方法是cmp会返回Ording结果，我们只需要将调用cmp的实体换成右实体则能实现降序排列。

let mut v = [4, -5, 1, -3, 2];
v.sort_by(|a, b| b.cmp(a));

另外还有sort_by_key的方法，区别与sort_by，sort_by_key无须确定大小，只需要将元素转换成对应排序的key值即可。

let v = Vec![5,2,3,1,4];
v.sort_by_key(|a,b| (num>3, Reverse(num)));

#[derive(Debug, Ord, Eq, PartialEq, PartialOrd)]

HashMap

hashmap的作用和定义其实已经不必再提，我们只需要了解rust中hashmap的操作方法。

新建

HashMap结构中有关联函数new，可以新建一个HashMap的变量。

let mut scores = HashMap::new();

更新

use std::collections::HashMap;

let mut map = HashMap::new();
assert_eq!(map.insert(37, "a"), None);
assert_eq!(map.is_empty(), false);

map.insert(37, "b");
assert_eq!(map.insert(37, "c"), Some("b"));
assert_eq!(map[&37], "c"); // 赋值不能用 []，只能用于访问确定存在的键

if let Some(val) = map.get_mut("key") {
    *val += 1; // 修改值
}

pub enum Entry<'a, K: 'a, V: 'a, A: Allocator = Global> {
    Occupied(OccupiedEntry<'a, K, V, A>),
    Vacant(VacantEntry<'a, K, V, A>),
}

默认包含两种变体，占用和空置，类似Result一样。

Entry提供了以下函数：

• or_insert → 没有就插入，有就返回可变引用

*map.entry("key").or_insert(0) += 1;

• or_insert_with → 不存在时才执行函数创建值

map.entry("key").or_insert_with(|| expensive_calc());

• and_modify → 存在就修改

map.entry("key").and_modify(|v| *v += 1);

而且很多函数返回的也是entry可以组合使用

map.entry("key")
   .and_modify(|v| *v += 1)  // 存在就+1
   .or_insert(1);            // 不存在就设1

删除

• remove(&k) → 删除元素
• retain(...) → 按条件保留 / 批量删除
• clear 清空所有元素
• drain 清空映射表，以迭代器形式返回所有键值对，保留已分配内存以便重复使用。

若迭代器未遍历完毕就被丢弃，剩余键值对也会随之释放。该迭代器会持有映射表的可变借用，以此优化运行逻辑。

遍历访问

for (key, value) in &map // 常用方式 不拿走所有权
for (key, value) in &mut map // 获得可变的 key, value 引用
for key in map.keys() // 遍历key的不可变引用
for key in map.values() // 遍历value的不可变引用
// 还有keys_mut(),valus_mut()与vec特别类似。

map.get(&key) → 安全，返回 Option<&V>（最推荐）

map.get_mut(&key) → 获取可变引用，可修改值

map[&key] → 直接取值，不存在就 panic（确定 key 存在时用）

map.entry(key) → 高级 API，不存在就插入（最强）

常用方法

容量操作

HashMap同样有容量的概念，我们可以提前指定这个HashMap的容量，来避免后面频繁插入元素导致的内存申请与拷贝。

with_capacity(capacity: usize)

reserve(&mut self, additional: usize)

String

[!todo ] 字符串字面值：它不是栈上变量，也不是堆上变量，而是被硬编码在编译后的可执行文件的只读数据段
运行时内存结构

字符串的理解

字符是一个层次的编码，字符有english，中文，日文，罗马符号，表情符号等等。
而字符编码是另一个层次的编码，是为了将字符转换成二进制的数据，保存在计算机系统中。

Unicode是字符集，将中文，英文，表情符号等等几乎世界上最多的符号集合在一起编了号。

那么如何将这些字符保存在计算机中？如果直接将最大的Unicode字符作为最大表示范围，来让一个字符编码可以容纳所有可能的Unicode字符，那么这个一个编码可能就需要8字节，甚至更多字节。要知道ASCII编码只占一个字节。

所以为了让每个字符编码所占用的字节数最小，有了不同的Unicode编码方案。

UTF-8是使用最广泛的Unicode编码方案，一种变长编码：通过字符的前缀位判断这个字符占用多少字节。

• 0xxxxxxx → 1 字节（ASCII 英文、数字、符号）
• 110xxxxx → 2 字节
• 1110xxxx → 3 字节（汉字、日韩文）
• 11110xxx → 4 字节（超大字符、大部分 emoji）

编程语言内部也要存储字符，而Unicode的字符序号占用太大，所以还是得选用一个字符编码来表示字符。不同的编程语言有不同的选择，Java选择使用UTF-16来存储字符，而Rust、Python3、Go都选择使用Utf-8编码来储存字符。

但是当我们准确表示一个字符概念的时候，char类型中存储是字符集中该字符的码点，也就是序号。每个char都是4字节，没有编码的概念。

而字符串在有编码的概念，当我们获得这个字符串的字节时，可以看到内部的utf-8编码。

两种字符串

事实上 String 被实现为一个带有一些额外保证、限制和功能的字节 vector 的封装。

新建

• String::new()
• 某变量.to_String() 等任何实现了Display trait 的类型，比如字符串字面值。
• String::from(“initial contents”);

更新

let s = String::from("hello") + " world";
// 本质上是调用了add方法
let s = String::add(String::from("hello"), " world");

Rust中String的本质

所以rust并不运行我们直接使用[]通过索引访问String中的元素，因为往往这些元素只是一个字符的一部分。

最后一个 Rust 不允许使用索引获取 String 字符的原因是，索引操作预期总是需要常数时间（O(1)）。但是对于 String 不可能保证这样的性能，因为 Rust 必须从开头到索引位置遍历来确定有多少有效的字符。

相比使用 [] 和单个值的索引，可以使用 [] 和一个 range 来创建含特定字节的字符串 slice，如果range中包含不完全的字符字节，那么就跟访问 vector 中的无效索引时一样程序崩溃。

遍历

for c in "Зд".chars() {
    println!("{c}");
}

for b in "Зд".bytes() {
    println!("{b}");
}