Rust常用集合类型——最全_rust 标准库 队例

在Rust标准库std::collections模块中有以下四种通用集合类型，分别如下：

• 线性序列：向量（Vec）、双端队列（VecDeque）、链表（LinkedList）

• Key-Value影射表：无序哈希表（HashMap）、有序哈希表（BTreeMap）

• 集合类型：无序集合（HashSet）、有序集合（BTreeSet)

• 优先队列：二叉堆（BinaryGeap）

线性序列：向量

与数组的区别是向量可以动态增长

fn main() {
    let mut v1 = vec![];  //使用vec!宏创建向量字面量
    v1.push(1);
    v1.push(2);
    v1.push(3);
    assert_eq!(v1,[1,2,3]);
    assert_eq!(v1[2],2);
    let mut v2 = vec![0;10];   //创建向量
    let mut v3 = Vec::new();   //创建向量
    v3.push(4);
    v3.push(5);
    v3.push(6);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

线性序列：双端队列

Rust中的VecDeque是基于可增长的RingBuffer算法实现的双端队列

use std::collections::VecDeque;
fn main() {
    let mut buf = VecDeque::new();   //创建双端队列
    buf.push_front(1);    //push_front的行为像栈，插入
    buf.push_front(2);
    assert_eq!(buf.get(0),Some(&2));
    assert_eq!(buf.get(1),Some(&1));
    buf.push_back(3);     //push_back的行为像队列，插入
    buf.push_back(4);
    buf.push_back(5);
    assert_eq!(buf.get(2),Some(&3));
    assert_eq!(buf.get(3),Some(&4));
    assert_eq!(buf.get(4),Some(&5));
    buf.push_front(6);
    buf.push_front(7);
    assert_eq!(buf.get(0),Some(&7));
    assert_eq!(buf.get(1),Some(&6));
    //最后的双端队列元素为7、6、2、1、3、4、5
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

线性序列：链表

Rust提供的链表是双向链表。但通常最好使用Vec或VecDeque类型，因为它们比链表更快速，内存访问效率更高，可以更好利用CPU缓存。

use std::collections::LinkedList;
fn main() {
    let mut list1 = LinkedList::new();   //创建队列
    list1.push_back('a');
    let mut list2 = LinkedList::new();
    list2.push_back('b');
    list2.push_back('c');
    list1.append(&mut list2);    //将list2的所有结点移动到list1的队列尾端
    println!("{:?}",list1);     //['a','b','c']
    println!("{:?}",list2);     //[]
    list1.pop_front();          //弹出操作
    println!("{:?}",list1);     //['b','c']
    list1.push_front('e');      //左插入
    println!("{:?}",list1);     //['e','b','c']
    list2.push_front('f');
    println!("{:?}",list2);     //['f']
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Key-Value影射表：HashMap和BTreeMap

use std::collections::BTreeMap;
use std::collections::HashMap;
fn main() {
    let mut hmap = HashMap::new();    //创建一个无序哈希表
    let mut bmap = BTreeMap::new();   //创建一个有序哈希表
    hmap.insert(3,"c");
    hmap.insert(1,"c");
    hmap.insert(2,"c");
    hmap.insert(5,"c");
    hmap.insert(4,"c");
    bmap.insert(3,"c");
    bmap.insert(2,"c");
    bmap.insert(1,"c");
    bmap.insert(5,"c");
    bmap.insert(4,"c");
    println!("{:?}",hmap);  //{4: "c", 5: "c", 3: "c", 1: "c", 2: "c"}  每次key的顺序每次都是随机的
    println!("{:?}",bmap);  //{1: "c", 2: "c", 3: "c", 4: "c", 5: "c"}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

集合：HashSet和BTreeSet

HashSet和BTreeSet其实就是HashMap<K,V>和BTreeMap<K,V>把Value设置为空元组的特定类型，等价于HashSet<K,()>和BTreeSet<K,()>

use std::collections::HashSet;
use std::collections::BTreeSet;
fn main() {
    let mut hbooks = HashSet::new();
    let mut bbooks = BTreeSet::new();
    hbooks.insert("Chrysanthemum and Knife");
    hbooks.insert("Brave New World");
    hbooks.insert("Clockwork Orange");
    if !hbooks.contains("Brave New World"){
        println!("we have {} books,but Brave New World ain't one.",hbooks.len());
    }
    println!("{:?}",hbooks);
    bbooks.insert("Chrysanthemum and Knife");
    bbooks.insert("Brave New World");
    bbooks.insert("Clockwork Orange");
    println!("{:?}",bbooks);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

优先队列：BinaryHeap

Rust提供的优先队列是基于二叉最大堆（Binary Heap）即完全二叉树实现的。

use std::collections::BinaryHeap;
fn main() {
    let mut heap = BinaryHeap::new();    //创建一个空的最大堆
    assert_eq!(heap.peek(),None);      //peek方法：取出堆中的最大值；此时没有最大值
    let arr = [93,80,54,62,73,13,53,64,34,54,23,72,100,99];
    for &i in arr.iter(){
        heap.push(i);
    } 
    assert_eq!(heap.peek(),Some(&100));     
    println!("{:?}",heap);  //[100, 80, 99, 64, 73, 72, 93, 62, 34, 54, 23, 13, 54, 53]
}
1
2
3
4
5
6
7
8
9
10
11

智能指针

Rust中的值默认被分配到栈内存，可以通过Box将值装箱（在堆内存中分配）。
Box的行为像引用，并且可以自动释放内存，所以称为智能指针。

fn main() {
    #[derive(PartialEq,Debug)]    //自动实现PartialEq trait和Debug trait
    struct Point{   //定义一个point结构体
        x:f64,
        y:f64,
    }
    let box_point = Box::new(Point { x: 0.0, y: 0.0});   //将结构体point直接装箱
    let unboxed_point: Point = *box_point;    //使用解引用操作符将其解引用
    assert_eq!(unboxed_point, Point { x: 0.0, y: 0.0});
    println!("{:?}", unboxed_point);   //Point { x: 0.0, y: 0.0 }
}
1
2
3
4
5
6
7
8
9
10
11

泛型

标准库中定义了很多泛型包括：Option、Vec、HashMap<K,V>、Box< T >

enum Option<T>{
        Some(T),
        None,
}
1
2
3
4

trait

trait是对类型行为的抽象,Rust 提供了一些常用的 traits，可以通过 #[derive()] 属性自动为结构体或枚举实现这些 traits。一些常见的可派生 traits 包括：

• Debug：通过实现 Debug trait，可以使用 println!(“{:?}”, my_struct) 来打印结构体的调试信息。
• Clone：通过实现 Clone trait，可以使用 my_struct.clone() 创建结构体的克隆副本。
• PartialEq 和 Eq：通过实现 PartialEq trait，可以进行结构体的部分相等性比较，而 Eq trait 则实现了完全相等性比较。
• PartialOrd 和 Ord：通过实现 PartialOrd trait，可以对结构体进行部分有序性比较，而 Ord trait 实现了完全有序性比较。

struct Duck;
struct Pig;
trait Fly{
    fn fly(&self) -> bool;
}
impl Fly for Duck{
    fn fly(&self) ->bool{
        return true;
    }
}
impl Fly for Pig{
    fn fly(&self) -> bool{
        return false;
    }
}
fn fly_static<T: Fly>(s: T) -> bool{  //静态分发
    s.fly()
}
fn fly_dyn(s:&dyn Fly) -> bool{   //动态分发
    s.fly()
}
fn main() {
    let pig = Pig;
    assert_eq!(fly_static::<Pig>(pig),false);
    let duck = Duck;
    assert_eq!(fly_static::<Duck>(duck),true);
    assert_eq!(fly_dyn(&Pig),false);
    assert_eq!(fly_dyn(&Duck),true);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29