详解Rust标准库：VecDeque 队列

theme: github
highlight: an-old-hope

查看本地官方文档

安装rust后运行

rustup doc

查看The Standard Library即可获取标准库内容

std::connections::VecDeque定义

队列是遵循先入先出规则的线性数据结构，在内存中不一定连续

VecDeque定义：可增长的环形缓冲区实现的双端队列

pub struct VecDeque<T, A: Allocator = Global> {
    // 队列头部在内部缓冲区中的索引位置
    head: usize,
    // 当前队列中的元素数量
    len: usize,
    // 管理内存分配和释放，确保有足够的空间来存储队列中的元素
    buf: RawVec<T, A>,
}

方法

with_capacity：用于创建一个具有指定初始容量的VecDeque

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.get(1) {
        println!("Element at index 1: {}", element);
        // Element at index 1: 2
    }
}

get：获取指定索引位置的元素的不可变引用

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.get(1) {
        println!("Element at index 1: {}", element);
        // Element at index 1: 2
    }
}

get_mut：获取指定索引位置的元素的可变引用

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.get_mut(1) {
        *element = 4;
    }
    println!("Modified deque: {:?}", deque);
    // Modified deque: [1, 4, 3]
}

swap：交换VecDeque中两个指定索引位置的元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    deque.swap(0, 2);
    println!("Swapped deque: {:?}", deque);
    // Swapped deque: [3, 2, 1]
}

capacity：返回VecDeque当前的容量

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::with_capacity(5);
    println!("Initial capacity: {}", deque.capacity());
    // Initial capacity: 5

    deque.push_back(1);
    println!("Capacity after adding an element: {}", deque.capacity());
    // Capacity after adding an element: 5
}

reserve_exact：精确地预留足够的空间以容纳指定数量的额外元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.reserve_exact(3);
    println!("Capacity after reserve_exact: {}", deque.capacity());
    // Capacity after reserve_exact: 3
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
}

reserve：预留足够的空间以容纳指定数量的额外元素（空间不够自动增长）

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.reserve(5);
    println!("Capacity after reserve: {}", deque.capacity());
    // Capacity after reserve: 5
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    deque.push_back(4);
    deque.push_back(5);
    deque.push_back(6);
    println!("Capacity after reserve: {}", deque.capacity());
    // Capacity after reserve: 10
}

try_reserve_exact：尝试精确地预留足够的空间以容纳指定数量的额外元素，如果预留成功则返回Ok(())，否则返回错误

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    if let Ok(()) = deque.try_reserve_exact(3) {
        println!("Reserved successfully. Capacity: {}", deque.capacity());
        // Reserved successfully. Capacity: 3
    } else {
        println!("Reserve failed.");
    }
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    deque.push_back(4);
    println!("Reserved successfully. Capacity: {}", deque.capacity());
    // Reserved successfully. Capacity: 6
}

try_reserve：尝试预留足够的空间以容纳指定数量的额外元素，如果预留成功则返回Ok(())，否则返回错误

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    if let Ok(()) = deque.try_reserve(3) {
        println!("Reserved successfully. Capacity: {}", deque.capacity());
        // Reserved successfully. Capacity: 4
    } else {
        println!("Reserve failed.");
    }
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    deque.push_back(4);
}

shrink_to_fit：将VecDeque的容量收缩到与当前元素数量相同

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::with_capacity(10);
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    deque.shrink_to_fit();
    println!("Capacity after shrink_to_fit: {}", deque.capacity());
    // Capacity after shrink_to_fit: 3
}

shrink_to：将VecDeque的容量收缩到指定大小

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::with_capacity(10);
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    deque.shrink_to(5);
    println!("Capacity after shrink_to: {}", deque.capacity());
    // Capacity after shrink_to: 5
}

truncate：将VecDeque截断到指定长度

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    deque.truncate(3);
    println!("Truncated deque: {:?}", deque);
    // Truncated deque: [1, 2, 3]
}

iter：返回一个不可变的迭代器，用于遍历VecDeque中的元素

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3]);
    for element in deque.iter() {
        println!("Element: {}", element);
    }
    // Element: 1
    // Element: 2
    // Element: 3
}

iter_mut：返回一个可变的迭代器，允许在遍历过程中修改VecDeque中的元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    for element in deque.iter_mut() {
        *element *= 2;
    }
    println!("Modified deque: {:?}", deque);
    // Modified deque: [2, 4, 6]
}

as_slice：将VecDeque分成不可变的切片

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3, 4, 5]);
    let (front_slice, back_slice) = deque.as_slices();
    println!("Front slice: {:?}", front_slice);
    // Front slice: [1, 2, 3, 4, 5]
    println!("Back slice: {:?}", back_slice);
    // Back slice: []
}

as_mut_slices：将VecDeque分成可变的切片

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    let (front_slice, back_slice) = deque.as_mut_slices();
    for element in front_slice {
        *element *= 2;
    }
    for element in back_slice {
        *element *= 3;
    }
    println!("Modified deque: {:?}", deque);
    // Modified deque: [2, 4, 6, 8, 10]
}

len：返回VecDeque中元素的数量

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3]);
    println!("Length of deque: {}", deque.len());
    // Length of deque: 3
}

is_empty：判断VecDeque是否为空

use std::collections::VecDeque;

fn main() {
    let deque:VecDeque<i32> = VecDeque::new();
    println!("Is deque empty? {}", deque.is_empty());
    // Is deque empty? true
    let deque2 = VecDeque::from([1]);
    println!("Is deque2 empty? {}", deque2.is_empty());
    // Is deque2 empty? false
}

range：返回一个指定范围内的不可变迭代器

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3, 4, 5]);
    for element in deque.range(1..3) {
        println!("Element: {}", element);
        // Element: 2
        // Element: 3
    }
}

range_mut：返回一个指定范围内的可变迭代器

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    for element in deque.range_mut(1..3) {
        *element *= 2;
    }
    println!("Modified deque: {:?}", deque);
    // Modified deque: [1, 4, 6, 4, 5]
}

drain：移除并返回一个迭代器，用于遍历被移除的元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    let drained = deque.drain(1..3).collect::<Vec<i32>>();
    println!("Drained elements: {:?}", drained);
    // Drained elements: [2, 3]
    println!("Remaining deque: {:?}", deque);
    // Remaining deque: [1, 4, 5]
}

clear：清空VecDeque，移除所有元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    println!("Before clearing: {:?}", deque);
    // Before clearing: [1, 2, 3]
    deque.clear();
    println!("After clearing: {:?}", deque);
    // After clearing: []
}

contains：判断VecDeque中是否包含特定元素

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3]);
    println!("Does deque contain 2? {}", deque.contains(&2));
    // Does deque contain 2? true
    println!("Does deque contain 4? {}", deque.contains(&4));
    // Does deque contain 4? false
}

front：返回VecDeque头部元素的不可变引用，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.front() {
        println!("Front element: {}", element);
        // Front element: 1
    }
}

front_mut：返回VecDeque头部元素的可变引用，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.front_mut() {
        *element = 4;
    }
    println!("Modified deque: {:?}", deque);
    // Modified deque: [4, 2, 3]
}

back：返回VecDeque尾部元素的不可变引用，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.back() {
        println!("Back element: {}", element);
        // Back element: 3
    }
}

back_mut：返回VecDeque尾部元素的可变引用，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.back_mut() {
        *element = 4;
    }
    println!("Modified deque: {:?}", deque);
    // Modified deque: [1, 2, 4]
}

pop_front：移除并返回VecDeque头部元素，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.pop_front() {
        println!("Popped element: {}", element);
        // Popped element: 1
    }
    println!("Remaining deque: {:?}", deque);
    // Remaining deque: [2, 3]
}

pop_back：移除并返回VecDeque尾部元素，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.pop_back() {
        println!("Popped element: {}", element);
        // Popped element: 3
    }
    println!("Remaining deque: {:?}", deque);
    // Remaining deque: [1, 2]
}

push_front：在VecDeque头部插入一个元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_front(1);
    deque.push_front(2);
    println!("Modified deque: {:?}", deque);
    // Modified deque: [2, 1]
}

push_back：在VecDeque尾部插入一个元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(1);
    deque.push_back(2);
    println!("Modified deque: {:?}", deque);
    // Modified deque: [1, 2]
}

swap_remove_front：移除并返回VecDeque头部开始的元素索引，同时用其后的第一个元素替换它，避免移动其后的所有元素，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4]);
    if let Some(element) = deque.swap_remove_front(2) {
        println!("Swapped and removed element: {}", element);
        // Swapped and removed element: 3
    }
    println!("Remaining deque: {:?}", deque);
    // Remaining deque: [2, 1, 4]
}

swap_remove_back：移除并返回VecDeque尾部开始的元素索引，同时用前一个元素替换它，避免移动前面的所有元素，如果为空则返回None

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4]);
    if let Some(element) = deque.swap_remove_back(2) {
        println!("Swapped and removed element from back: {}", element);
        // Swapped and removed element from back: 3
    }
    println!("Remaining deque: {:?}", deque);
    // Remaining deque: [1, 2, 4]
}

insert：在指定索引位置插入一个元素。如果索引超出范围，会导致程序 panic（元素为[1,2,3]时容量为3，插入索引1不改变容量，插入4时由于索引是连续的，会开辟原队列的两倍容量6，后续插入索引5可以成功，如果直接插入5索引不连续不会开辟新空间会panic）

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    println!("deque capacity: {}", deque.capacity());
    // deque capacity: 3
    deque.insert(1, 9);
    // deque.insert(4, 5); // 这一行存在以下操作成功，不存在 panic!
    deque.insert(5, 6); // panic!'
    println!("deque capacity: {}", deque.capacity());
    // deque capacity: 6
    println!("After insertion: {:?}", deque);
    // After insertion: [1, 9, 2, 4, 3, 6]
    println!("deque capacity: {}", deque.capacity());
    // deque capacity: 6
}

remove：移除指定索引位置的元素，并返回该元素。如果索引超出范围，会导致程序 panic

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    if let Some(element) = deque.remove(1) {
        println!("Removed element: {}", element);
        // Removed element: 2
    }
    println!("Remaining deque: {:?}", deque);
    // Remaining deque: [1, 3]
}

split_off：在指定索引位置将VecDeque分割成两个，返回从指定索引开始的后半部分

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    let deque2 = deque.split_off(2);

    println!("{:?}", deque2);
    // [3, 4, 5]
}

append：将另一个VecDeque的所有元素追加到当前VecDeque的末尾

use std::collections::VecDeque;

fn main() {
    let mut deque1 = VecDeque::from([1, 2, 3]);
    let mut deque2 = VecDeque::from([4, 5, 6]);
    deque1.append(&mut deque2);
    println!("Appended deque: {:?}", deque1);
    // Appended deque: [1, 2, 3, 4, 5, 6]
}

retain：保留满足给定谓词的元素，移除不满足的元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    deque.retain(|&x| x % 2 == 0);
    println!("After retain: {:?}", deque);
    // After retain: [2, 4]
}

retain_mut：与retain类似，但可以对元素进行可变操作

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    deque.retain_mut(|x| {
        *x *= 2;
        *x % 3 == 0
    });
    println!("After retain_mut: {:?}", deque);
    // After retain_mut: [6]
}

resize_with：调整VecDeque的大小到指定长度，使用给定的函数生成新元素填充额外的空间或者截断多余的元素

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2]);
    deque.resize_with(5, || 0);
    println!("Resized deque: {:?}", deque);
    // Resized deque: [1, 2, 0, 0, 0]
}

make_contiguous：尝试使VecDeque在内存中连续存储，可能会导致重新分配内存

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3]);
    deque.make_contiguous();
    println!("After make_contiguous: {:?}", deque);
    // After make_contiguous: [1, 2, 3]
}

rotate_left：将VecDeque向左旋转指定的步数

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    deque.rotate_left(2);
    println!("After rotate_left: {:?}", deque);
    // After rotate_left: [3, 4, 5, 1, 2]
}

rotate_right：将VecDeque向右旋转指定的步数

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from([1, 2, 3, 4, 5]);
    deque.rotate_right(2);
    println!("After rotate_right: {:?}", deque);
    // After rotate_right: [4, 5, 1, 2, 3]
}

binary_search：在已排序的VecDeque中进行二分查找指定元素，返回一个Result类型，表示查找结果。如果找到元素，返回Ok(index)，默认最后一个结果；如果未找到返回Err()；在未排序的队列进行查找会返回unspecified，这个结果没有意义

当查找的元素不存在时返回查找元素应当插入位置有序队列位置的索引

当查找的元素存在时返回最后一个匹配的元素

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3, 3, 4, 5]);
    let result = deque.binary_search(&3);
    println!("{:?}", result);
    // Ok(3)

    // 有序且不存在
    let deque = VecDeque::from([3, 3, 3, 3, 3, 4, 4, 7, 8]);
    let result = deque.binary_search(&5);
    println!("{:?}", result);
    // Err(7)

    // 有序且存在
    let deque = VecDeque::from([3, 3, 3, 3, 3, 4, 4, 7, 8]);
    let result = deque.binary_search(&3);
    println!("{:?}", result);
    // Ok(4)

    // 注意以下结果没有意义

    // 无序且不存在
    let deque = VecDeque::from([3, 9, 3, 3, 8, 4, 3, 7, 3]);
    let result = deque.binary_search(&5);
    println!("{:?}", result);
    // Err(4)

    // 无序且存在
    let deque = VecDeque::from([3, 9, 3, 3, 8, 4, 3, 7, 3]);
    let result = deque.binary_search(&3);
    println!("{:?}", result);
    // Ok(2)
}

binary_search_by：使用自定义的比较函数在已排序的VecDeque中进行二分查找

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([1, 2, 3, 3, 4, 6]);
    // 找到最后一个等于3的元素索引
    let result = deque.binary_search_by(|x| x.cmp(&3));
    println!("{:?}", result);
    // Ok(3)

    // 找到最后一个等于5de的元素索引,不存在返回应当插入位置的索引
    let result = deque.binary_search_by(|x| x.cmp(&5));
    println!("{:?}", result);
    // Err(5)
}

binary_search_by_key：如果队列是以元组键的顺序排序的，使用自定义的键提取函数在已排序的VecDeque中进行二分查找

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from([
        (0, 0),
        (2, 1),
        (4, 1),
        (5, 1),
        (3, 1),
        (1, 2),
        (2, 3),
        (4, 5),
        (5, 8),
        (3, 13),
        (1, 21),
        (2, 34),
        (4, 55),
    ]);
    // 按元组第二个键值排序
    let result = deque.binary_search_by_key(&13, |&(a, b)| b);
    println!("{:?}", result);
    // Ok(9)
}

partition_point：在已排序的VecDeque中找到满足给定谓词的元素的分界点。即返回第一个不满足谓词的元素的索引

use std::collections::VecDeque;

fn main() {
    let deque: VecDeque<i32> = VecDeque::from([1, 2, 3, 3, 5, 6, 7]);
    // 按小于5的元素划分，返回第一个大于等于5的索引
    let result = deque.partition_point(|&x| x < 5);
    println!("{:?}", result);
    // 4
}