动态数组 Vector
此笔记记录于Rust Course,大多数为其中的摘要,少数为笔者自己的理解
动态数组允许你存储多个值,这些值在内存中一个紧挨着另一个排列,因此访问其中某个元素的成本非常低。动态数组只能存储相同类型的元素,如果你想存储不同类型的元素,可以使用之前讲过的枚举类型或者特征对象。
总之,当我们想拥有一个列表,里面都是相同类型的数据时,动态数组将会非常有用。
创建动态数组
1)Vec::new()
let v: Vec<i32> = Vec::new();
这里,v
被显式地声明了类型 Vec<i32>
,这是因为 Rust 编译器无法从 Vec::new()
中得到任何关于类型的暗示信息,因此也无法推导出 v
的具体类型
但是当你向里面增加一个元素后,一切又不同了:
let mut v = Vec::new();
v.push(1);
此时,v
就无需手动声明类型,因为编译器通过 v.push(1)
,推测出 v
中的元素类型是 i32
,因此推导出 v
的类型是 Vec<i32>
。
如果预先知道要存储的元素个数,可以使用
Vec::with_capacity(capacity)
创建动态数组,这样可以避免因为插入大量新数据导致频繁的内存分配和拷贝,提升性能
2)vec![]
需要在创建时赋予初始值:
let v = vec![1, 2, 3];
更新 Vector
let mut v = Vec::new();
v.push(1);
从 Vector 中读取数据
- 通过下标索引访问。
- 使用
get
方法。
let v = vec![1, 2, 3, 4, 5];
let third: &i32 = &v[2];
println!("第三个元素是 {}", third);
match v.get(2) {
Some(third) => println!("第三个元素是 {third}"),
None => println!("去你的第三个元素,根本没有!"),
}
v.get(2)
也是访问第三个元素,但是有所不同的是,它返回了 Option<&T>
,因此还需要额外的 match
来匹配解构出具体的值。
下标索引与.get
的区别
let v = vec![1, 2, 3, 4, 5];
let does_not_exist = &v[100];
let does_not_exist = v.get(100);
- 运行以上代码,
&v[100]
的访问方式会导致程序无情报错退出,因为发生了数组越界访问。 但是v.get
就不会,它在内部做了处理,有值的时候返回Some(T)
,无值的时候返回None
,因此v.get
的使用方式非常安全。 - 既然如此,为何不统一使用
v.get
的形式?因为实在是有些啰嗦,Rust 语言的设计者和使用者在审美这方面还是相当统一的:简洁即正义,何况性能上也会有轻微的损耗。
同时借用多个数组元素
let mut v = vec![1, 2, 3, 4, 5];
let first = &v[0];
v.push(6);
println!("The first element is: {first}");
先不运行,来推断下结果,首先 first = &v[0]
进行了不可变借用,v.push
进行了可变借用,如果 first
在 v.push
之后不再使用,那么该段代码可以成功编译(原因见引用的作用域)。
可是上面的代码中,first
这个不可变借用在可变借用 v.push
后被使用了,那么妥妥的,编译器就会报错
按理来说,这两个引用不应该互相影响的:一个是查询元素,一个是在数组尾部插入元素,完全不相干的操作,为何编译器要这么严格呢?
原因在于:数组的大小是可变的,当旧数组的大小不够用时,Rust 会重新分配一块更大的内存空间,然后把旧数组拷贝过来。这种情况下,之前的引用显然会指向一块无效的内存
迭代遍历 Vector 中的元素
如果想要依次访问数组中的元素,可以使用迭代的方式去遍历数组,这种方式比用下标的方式去遍历数组更安全也更高效(每次下标访问都会触发数组边界检查):
let v = vec![1, 2, 3];
for i in &v {
println!("{i}");
}
let mut v = vec![1, 2, 3];
for i in &mut v {
*i += 10
}
存储不同类型的元素
通过枚举实现:
#[derive(Debug)]
enum IpAddr {
V4(String),
V6(String)
}
fn main() {
let v = vec![
IpAddr::V4("127.0.0.1".to_string()),
IpAddr::V6("::1".to_string())
];
for ip in v {
show_addr(ip)
}
}
fn show_addr(ip: IpAddr) {
println!("{:?}",ip);
}
数组 v
中存储了两种不同的 ip
地址,但是这两种都属于 IpAddr
枚举类型的成员,因此可以存储在数组中。
通过特征对象实现:
trait IpAddr {
fn display(&self);
}
struct V4(String);
impl IpAddr for V4 {
fn display(&self) {
println!("ipv4: {:?}",self.0)
}
}
struct V6(String);
impl IpAddr for V6 {
fn display(&self) {
println!("ipv6: {:?}",self.0)
}
}
fn main() {
let v: Vec<Box<dyn IpAddr>> = vec![
Box::new(V4("127.0.0.1".to_string())),
Box::new(V6("::1".to_string())),
];
for ip in v {
ip.display();
}
}
比枚举实现要稍微复杂一些,我们为 V4
和 V6
都实现了特征 IpAddr
,然后将它俩的实例用 Box::new
包裹后,存在了数组 v
中,需要注意的是,这里必须手动地指定类型:Vec<Box<dyn IpAddr>>
,表示数组 v
存储的是特征 IpAddr
的对象,这样就实现了在数组中存储不同的类型。
在实际使用场景中,特征对象数组要比枚举数组常见很多,主要原因在于特征对象非常灵活,而编译器对枚举的限制较多,且无法动态增加类型。
Vector 的排序
在 rust 里,实现了两种排序算法,分别为稳定的排序 sort
和 sort_by
,以及非稳定排序 sort_unstable
和 sort_unstable_by
。
- 这个所谓的
非稳定
并不是指排序算法本身不稳定,而是指在排序过程中对相等元素的处理方式。 - 在
稳定
排序算法里,对相等的元素,不会对其进行重新排序。而在不稳定
的算法里则不保证这点。
总体而言,非稳定
排序的算法的速度会优于 稳定
排序算法,同时,稳定
排序还会额外分配原数组一半的空间。
整数数组的排序
fn main() {
let mut vec = vec![1, 5, 10, 2, 15];
vec.sort_unstable();
assert_eq!(vec, vec![1, 2, 5, 10, 15]);
}
浮点数数组的排序
如果直接使用上述整数数组的排序方式,会直接报错。
在浮点数当中,存在一个 NAN
的值,这个值无法与其他的浮点数进行对比,因此,浮点数类型并没有实现全数值可比较 Ord
的特性,而是实现了部分可比较的特性 PartialOrd
。
如此,如果我们确定在我们的浮点数数组当中,不包含 NAN
值,那么我们可以使用 partial_cmp
来作为大小判断的依据。
fn main() {
let mut vec = vec![1.0, 5.6, 10.3, 2.0, 15f32];
vec.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(vec, vec![1.0, 2.0, 5.6, 10.3, 15f32]);
}
对结构体数组进行排序
#[derive(Debug)]
struct Person {
name: String,
age: u32,
}
impl Person {
fn new(name: String, age: u32) -> Person {
Person { name, age }
}
}
fn main() {
let mut people = vec![
Person::new("Zoe".to_string(), 25),
Person::new("Al".to_string(), 60),
Person::new("John".to_string(), 1),
];
// 定义一个按照年龄倒序排序的对比函数
people.sort_unstable_by(|a, b| b.age.cmp(&a.age));
println!("{:?}", people);
}
从上面我们学习过程当中,排序需要我们实现 Ord
特性,那么如果我们把我们的结构体实现了该特性,是否就不需要我们自定义对比函数了呢?
是,但不完全是,实现 Ord
需要我们实现 Ord
、Eq
、PartialEq
、PartialOrd
这些属性。好消息是,你可以 derive
这些属性:
#[derive(Debug, Ord, Eq, PartialEq, PartialOrd)]
struct Person {
name: String,
age: u32,
}
impl Person {
fn new(name: String, age: u32) -> Person {
Person { name, age }
}
}
fn main() {
let mut people = vec![
Person::new("Zoe".to_string(), 25),
Person::new("Al".to_string(), 60),
Person::new("Al".to_string(), 30),
Person::new("John".to_string(), 1),
Person::new("John".to_string(), 25),
];
people.sort_unstable();
println!("{:?}", people);
}
需要 derive
Ord
相关特性,需要确保你的结构体中所有的属性均实现了 Ord
相关特性,否则会发生编译错误。derive
的默认实现会依据属性的顺序依次进行比较