当前位置： 首页 > article >正文

Rust常用数据结构教程 序列

article 2024/12/25 15:13:03

文章目录

  • 一、Vec
    • 1.Vec与堆栈
    • 2.什么时候需要Vec
  • 二、VecDeque
    • 1.什么情况适合VecDeque
    • 2.VecDeque的方法
  • 三、LinkedList
    • 1.什么时候用LinkedList
  • 参考

一、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());

    // push
    let 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);
    //删除pop
    let car = cars.pop().unwrap();
    println!("{:?}", cars);
    println!("{:?}", car);
    //删除：固定index删除
    let car = cars.remove(0);
    println!("{:?}", cars);
    println!("{:?}", car);
    //队尾插入：push
    cars.push(car.clone());
    println!("{:?}", cars);
    // 队首插入：insert
    cars.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 run
   Compiling 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 default

warning: `data_struct` (bin "data_struct") generated 1 warning
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 5.81s
     Running `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

二、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
    // push
    cars.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());

    // pop
    let 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
    // back
    println!("{:?}", cars.front());
    println!("{:?}", cars.back());

    // get
    println!("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 run
    Blocking waiting for file lock on build directory
   Compiling 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 default

warning: 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 default

warning: `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.30s
     Running `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 run
   Compiling 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 default

warning: 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 default

warning: 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 default

warning: 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 default

warning: `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.13s
     Running `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常用数据结构教程

http://www.kler.cn/a/381658.html

相关文章：

  • Opencv之对图片的处理和运算
  • 5G -- 5G网络架构
  • 【从零开始入门unity游戏开发之——C#篇21】C#面向对象的封装——`this`扩展方法、运算符重载、内部类、`partial` 定义分部类
  • Linux系统安装node.js
  • 图形学笔记 - 5. 光线追踪2 - 加速结构
  • go面试问题
  • [SDX35]SDX35 dtsi配置GPIO_108不生效问题分析及解决方案
  • 使用 AMD GPU 的 ChatGLM-6B 双语语言模型
  • 120. gltf工厂模型设置发光描边
  • SpringBoot2~~~
  • 什么是区块链中的不可能三角？
  • MySQL数据迁移到SQLServer数据库
  • 数据分析的基本过程
  • 数据中台一键大解析！
  • 《常用深度学习神经网络及其原理与应用场景》
  • [出海记录]开发新手的第 11 个站点上线
  • mysql 和 java 对应数据类型
  • 【java】ArrayList与LinkedList的区别
  • 健身中心运营优化：SpringBoot管理系统
  • 华为HarmonyOS打造开放合规的广告生态 - Banner广告
  • 开源ISP（Infinite-ISP）介绍
  • Rust 力扣 - 2841. 几乎唯一子数组的最大和
  • Ubuntu 20.04 部署向量数据库 Milvus + Attu
  • 【数据结构】哈希思想详解
  • 工作流之Flowable
  • 掌握ElasticSearch（八）：聚集、文档间的关系