Rust常用数据结构教程 序列

一、Vec

可变数组(vector)数组存储在heap上,在运行时(runtime)可以增加或减少数组

长度

• 有人把Vector翻译为矢量
• 注意默认还是不可变

1.Vec与堆栈

Vec的buf是存储在heap上的，其他存储在栈上

pub struct Vec<T, #[unstable(feature = "allocator_api'", issue = "32838")] A:Alocator=Global>
{
buf: RawVec<T, A>,
len: usize, //长度
}pub(crate) struct RawVec<T, A: Allocator = Global> {
ptr: Unique<T>, // 指向
cap: usize, // capacity
alloc: A,
}

2.什么时候需要Vec

·首选Vec:当你不知道用什么的时候，试试Vec，性能强悍有保证
·当你想要一个长度实时变化的数据存储单元时
·当你希望自己的存储单元有序时
·当你希望内存中各个元素的存储地址是连续时

#[derive(Debug, Clone)]
struct Car {id: i32,name: String,
}fn main() {// 初始化方法let my_vec = vec![2, 3, 4];println!("{:#?}: {}", my_vec, my_vec.capacity());// /这里的语法表示创建一个长度为 3 的向量，并用 2 填充每个元素let my_vec = vec![2; 3];println!("{:#?}: {}", my_vec, my_vec.capacity());// 可以显示声明类型，也可以不显示声明类型let my_vec: Vec<i32> = Vec::new();println!("{:#?}: {}", my_vec, my_vec.capacity());let my_vec: Vec<i32> = Vec::with_capacity(5);println!("{:#?}: {}", my_vec, my_vec.capacity());// pushlet mut cars = Vec::new();for i in 1..11 {let car_type = if i % 2 == 0 { "car" } else { "bus" };cars.push(Car {id: i,name: format!("{}-{}", car_type, i),});}println!("{:?}", cars);//删除poplet car = cars.pop().unwrap();println!("{:?}", cars);println!("{:?}", car);//删除：固定index删除let car = cars.remove(0);println!("{:?}", cars);println!("{:?}", car);//队尾插入：pushcars.push(car.clone());println!("{:?}", cars);// 队首插入：insertcars.insert(0, car.clone());println!("{:?}", cars);// get set// 不推荐cars[9] = Car {id: 11,name: "car-11".to_string(),};println!("{:?}", cars);// 推荐let item = cars.get(0);println!("{:?}", item);let item = cars.get_mut(9).unwrap();*item = Car {id: 10,name: "car-10".to_owned(),};println!("{:?}", cars);let mut cars2 = vec![car.clone(), car.clone()];cars.append(&mut cars2);println!("{:?}", cars);println!("{:?}", cars2);let car_slice = cars.as_slice();println!("{:?}", car_slice);// 清理cars.clear();println!("{:?}", cars);println!("{:?}", cars.is_empty());
}

编译及运行

 cargo runCompiling data_struct v0.1.0 (/home/wangji/installer/rust/data_struct/data_struct)
warning: fields `id` and `name` are never read--> src/main.rs:3:5|
2 | struct Car {|        --- fields in this struct
3 |     id: i32,|     ^^
4 |     name: String,|     ^^^^|= note: `Car` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis= note: `#[warn(dead_code)]` on by defaultwarning: `data_struct` (bin "data_struct") generated 1 warningFinished `dev` profile [unoptimized + debuginfo] target(s) in 5.81sRunning `target/debug/data_struct`
[2,3,4,
]: 3
[2,2,2,
]: 3
[]: 0
[]: 5
[Car { id: 1, name: "bus-1" }, Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }, Car { id: 10, name: "car-10" }]
[Car { id: 1, name: "bus-1" }, Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }]
Car { id: 10, name: "car-10" }
[Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }]
Car { id: 1, name: "bus-1" }
[Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }, Car { id: 1, name: "bus-1" }]
[Car { id: 1, name: "bus-1" }, Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }, Car { id: 1, name: "bus-1" }]
[Car { id: 1, name: "bus-1" }, Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }, Car { id: 11, name: "car-11" }]
Some(Car { id: 1, name: "bus-1" })
[Car { id: 1, name: "bus-1" }, Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }, Car { id: 10, name: "car-10" }]
[Car { id: 1, name: "bus-1" }, Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }, Car { id: 10, name: "car-10" }, Car { id: 1, name: "bus-1" }, Car { id: 1, name: "bus-1" }]
[]
[Car { id: 1, name: "bus-1" }, Car { id: 2, name: "car-2" }, Car { id: 3, name: "bus-3" }, Car { id: 4, name: "car-4" }, Car { id: 5, name: "bus-5" }, Car { id: 6, name: "car-6" }, Car { id: 7, name: "bus-7" }, Car { id: 8, name: "car-8" }, Car { id: 9, name: "bus-9" }, Car { id: 10, name: "car-10" }, Car { id: 1, name: "bus-1" }, Car { id: 1, name: "bus-1" }]
[]
true

3.get()方法

#![allow(unused)]
fn main() {
let v = vec![1, 2, 3, 4, 5];let third: &i32 = &v[2];
println!("The third element is {}", third);match v.get(2) {Some(third) => println!("The third element is {}", third),None => println!("There is no third element."),
}
}

~/installer/rust/bobo/abc master 
 cargo runCompiling abc v0.1.0 (/home/wangji/installer/rust/bobo/abc)Finished `dev` profile [unoptimized + debuginfo] target(s) in 7.48sRunning `target/debug/abc`
The third element is 3
The third element is 3
~/installer/rust/bobo/abc master 
 

4.与枚举的结合

#![allow(unused)]
fn main() {enum SpreadsheetCell {Int(i32),Float(f64),Text(String),}let row = vec![SpreadsheetCell::Int(3),SpreadsheetCell::Text(String::from("blue")),SpreadsheetCell::Float(10.12),];match &row[1] {SpreadsheetCell::Int(i) => println!("Found an int: {}", i),_ => println!("No int found"),}
}

编译及运行

 cargo runCompiling abc v0.1.0 (/home/wangji/installer/rust/bobo/abc)Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.29sRunning `target/debug/abc`
No int found

二、VecDeque

一个双向的动态数组

与Vec 类似，与Vec 不同的是,它对容器的两端进行 移除和插入

VecDeque的两端插入、删除都是O（1）级别的

VecDeque并一定是连续的

1.什么情况适合VecDeque

有双端插入和删除需求的

双向需求queue

2.VecDeque的方法

继承了Vec的所有方法

自身的方法

push_back\push_front (取代了push)
pop_frontlpop_back(取代了pop)
contains
frontifront_mut
back\back_mut

Example：

use std::collections::VecDeque;
#[derive(Debug, Clone)]
struct Car {id: i32,name: String,
}fn main() {let mut int_queue: VecDeque<i32> = VecDeque::new();println!("{:?} cap {}", int_queue, int_queue.capacity());int_queue.push_back(3);println!("{:?} cap {}", int_queue, int_queue.capacity());let mut int_queue: VecDeque<i32> = VecDeque::with_capacity(20);println!("{:?} cap {}", int_queue, int_queue.capacity());let mut cars = VecDeque::from([Car {id: 1,name: String::from("Car-1"),},Car {id: 2,name: String::from("Car-2"),},Car {id: 3,name: String::from("Car-3"),},]);println!("{:?} cap {}", cars, cars.capacity());// VecDeque// pushcars.push_back(Car {id: 4,name: "Car-4".to_string(),});println!("{:?} cap {}", cars, cars.capacity());cars.push_front(Car {id: 0,name: "Car-0".to_string(),});println!("{:?} cap {}", cars, cars.capacity());// poplet back_car = cars.pop_back();println!("{:?}", back_car);println!("{:?} cap {}", cars, cars.capacity());let front_car = cars.pop_front();println!("{:?} ", front_car);println!("{:?} cap {}", cars, cars.capacity());// front// backprintln!("{:?}", cars.front());println!("{:?}", cars.back());// getprintln!("car{:?}", cars[1]); //不安全操作let car = cars.get(1).unwrap(); //安全操作println!("car{:?}", car);let car = cars.get_mut(1).unwrap();*car = Car {id: 10,name: "Car-n".to_owned(),};println!("car{:?}", cars);cars.clear();println!("{:?}", cars.is_empty());
}

编译及运行

 cargo runBlocking waiting for file lock on build directoryCompiling data_struct v0.1.0 (/home/wangji/installer/rust/data_struct/data_struct)
warning: variable does not need to be mutable--> src/main.rs:13:9|
13 |     let mut int_queue: VecDeque<i32> = VecDeque::with_capacity(20);|         ----^^^^^^^^^|         ||         help: remove this `mut`|= note: `#[warn(unused_mut)]` on by defaultwarning: fields `id` and `name` are never read--> src/main.rs:4:5|
3 | struct Car {|        --- fields in this struct
4 |     id: i32,|     ^^
5 |     name: String,|     ^^^^|= note: `Car` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis= note: `#[warn(dead_code)]` on by defaultwarning: `data_struct` (bin "data_struct") generated 2 warnings (run `cargo fix --bin "data_struct"` to apply 1 suggestion)Finished `dev` profile [unoptimized + debuginfo] target(s) in 8.30sRunning `target/debug/data_struct`
[] cap 0
[3] cap 4
[] cap 20
[Car { id: 1, name: "Car-1" }, Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }] cap 3
[Car { id: 1, name: "Car-1" }, Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }, Car { id: 4, name: "Car-4" }] cap 6
[Car { id: 0, name: "Car-0" }, Car { id: 1, name: "Car-1" }, Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }, Car { id: 4, name: "Car-4" }] cap 6
Some(Car { id: 4, name: "Car-4" })
[Car { id: 0, name: "Car-0" }, Car { id: 1, name: "Car-1" }, Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }] cap 6
Some(Car { id: 0, name: "Car-0" }) 
[Car { id: 1, name: "Car-1" }, Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }] cap 6
Some(Car { id: 1, name: "Car-1" })
Some(Car { id: 3, name: "Car-3" })
carCar { id: 2, name: "Car-2" }
carCar { id: 2, name: "Car-2" }
car[Car { id: 1, name: "Car-1" }, Car { id: 10, name: "Car-n" }, Car { id: 3, name: "Car-3" }]
true

三、LinkedList

通过链式存储数据的一种序列数据结构

A double-linked with owned nodes

1.什么时候用LinkedList

·根据Rust文档，LinkedList数据结构在分割/追加方面是高效的

如果您希望对分配多少内存以及何时分配内存有非常细粒度的控制，那么链表是一个不错的选择。但是绝大多数你用不到，而且你要考虑成本

use std::collections::LinkedList;#[derive(Debug, Clone)]
struct Car {id: i32,name: String,
}
// vecque 方法都有
// vec 无
fn main() {let mut int_link: LinkedList<i32> = LinkedList::new();let mut cars = LinkedList::from([Car {id: 1,name: "Car-1".to_string(),},Car {id: 2,name: "Car-2".to_string(),},Car {id: 3,name: "Car-3".to_string(),},]);cars.push_back(Car {id: 4,name: "Car-4".to_string(),});println!("back: {:?}", cars.back());cars.push_front(Car {id: 0,name: "Car-0".to_string(),});println!("front: {:?}", cars.front());println!("{:?}", cars);let car = cars.pop_back().unwrap();println!("{:?}", car);let car = cars.pop_front().unwrap();println!("{:?}", car);/*** split_off 是一个方法，用于将 Vec 切成两部分。它会将 cars 向量从指定的索引位置分成两部分，并返回从该位置开始的所有元素，同时将这些元素从原向量中移除。*/let mut car_list = cars.split_off(cars.len() - 2);println!("---{:?}", car_list);println!("{:?}", cars);cars.append(&mut car_list);println!("{:?}", cars);println!("{:?}", car_list);cars.clear();println!("{}", cars.is_empty());
}

编译及运行：

 cargo runCompiling data_struct v0.1.0 (/home/wangji/installer/rust/data_struct/data_struct)
warning: unused doc comment--> src/main.rs:44:5|
44 | /     /**
45 | |      * split_off 是一个方法，用于将 Vec 切成两部分。它会将 cars 向量从指定的索引位置分成两部分，并返回从该位置开始的所有元素，同时将这些元素从原向量中移除。
46 | |      */| |_______^
47 |       let mut car_list = cars.split_off(cars.len() - 2);|       -------------------------------------------------- rustdoc does not generate documentation for statements|= help: use `/* */` for a plain comment= note: `#[warn(unused_doc_comments)]` on by defaultwarning: unused variable: `int_link`--> src/main.rs:11:13|
11 |     let mut int_link: LinkedList<i32> = LinkedList::new();|             ^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_int_link`|= note: `#[warn(unused_variables)]` on by defaultwarning: variable does not need to be mutable--> src/main.rs:11:9|
11 |     let mut int_link: LinkedList<i32> = LinkedList::new();|         ----^^^^^^^^|         ||         help: remove this `mut`|= note: `#[warn(unused_mut)]` on by defaultwarning: fields `id` and `name` are never read--> src/main.rs:5:5|
4 | struct Car {|        --- fields in this struct
5 |     id: i32,|     ^^
6 |     name: String,|     ^^^^|= note: `Car` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis= note: `#[warn(dead_code)]` on by defaultwarning: `data_struct` (bin "data_struct") generated 4 warnings (run `cargo fix --bin "data_struct"` to apply 1 suggestion)Finished `dev` profile [unoptimized + debuginfo] target(s) in 6.13sRunning `target/debug/data_struct`
back: Some(Car { id: 4, name: "Car-4" })
front: Some(Car { id: 0, name: "Car-0" })
[Car { id: 0, name: "Car-0" }, Car { id: 1, name: "Car-1" }, Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }, Car { id: 4, name: "Car-4" }]
Car { id: 4, name: "Car-4" }
Car { id: 0, name: "Car-0" }
---[Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }]
[Car { id: 1, name: "Car-1" }]
[Car { id: 1, name: "Car-1" }, Car { id: 2, name: "Car-2" }, Car { id: 3, name: "Car-3" }]
[]
true

参考

• Rust常用数据结构教程