Struct alloc::collections::vec_deque::VecDeque

1.0.0 · source ·
pub struct VecDeque<T, A: Allocator = Global> { /* private fields */ }
Expand description

使用可增长的环形缓冲区实现的双端队列。

“default” 作为队列的这种用法是使用 push_back 添加到队列,使用 pop_front 从队列中删除。

extendappend 以这种方式推到后面,并从前到后迭代 VecDeque

可以从数组初始化具有已知项列表的 VecDeque

use std::collections::VecDeque;

let deq = VecDeque::from([-1, 0, 1]);
Run

由于 VecDeque 是环形缓冲区,因此它的元素在内存中不一定是连续的。 如果要以单个切片的形式访问元素 (例如为了进行有效的排序),则可以使用 make_contiguous。 它旋转 VecDeque,以使其元素不环绕,并向当前连续的元素序列返回可变切片。

Implementations§

source§

impl<T> VecDeque<T>

const: 1.68.0 · source

pub const fn new() -> VecDeque<T>

创建一个空的双端队列。

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::new();
Run
source

pub fn with_capacity(capacity: usize) -> VecDeque<T>

为至少 capacity 个元素创建一个空的双端队列。

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::with_capacity(10);
Run
source§

impl<T, A: Allocator> VecDeque<T, A>

source

pub const fn new_in(alloc: A) -> VecDeque<T, A>

🔬This is a nightly-only experimental API. (allocator_api #32838)

创建一个空的双端队列。

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::new();
Run
source

pub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A>

🔬This is a nightly-only experimental API. (allocator_api #32838)

为至少 capacity 个元素创建一个空的双端队列。

Examples
use std::collections::VecDeque;

let deque: VecDeque<u32> = VecDeque::with_capacity(10);
Run
source

pub fn get(&self, index: usize) -> Option<&T>

提供给定索引处元素的引用。

索引为 0 的元素在队列的最前面。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
buf.push_back(6);
assert_eq!(buf.get(1), Some(&4));
Run
source

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

提供给定索引处元素的可变引用。

索引为 0 的元素在队列的最前面。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
buf.push_back(6);
assert_eq!(buf[1], 4);
if let Some(elem) = buf.get_mut(1) {
    *elem = 7;
}
assert_eq!(buf[1], 7);
Run
source

pub fn swap(&mut self, i: usize, j: usize)

交换索引为 ij 的元素。

ij 可能是相等的。

索引为 0 的元素在队列的最前面。

Panics

如果任一索引越界,就会出现 panics。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
assert_eq!(buf, [3, 4, 5]);
buf.swap(0, 2);
assert_eq!(buf, [5, 4, 3]);
Run
source

pub fn capacity(&self) -> usize

返回双端队列在不重新分配的情况下可以容纳的元素数。

Examples
use std::collections::VecDeque;

let buf: VecDeque<i32> = VecDeque::with_capacity(10);
assert!(buf.capacity() >= 10);
Run
source

pub fn reserve_exact(&mut self, additional: usize)

为至少 additional 多个要插入给定双端队列的元素保留最小容量。 如果容量已经足够,则不执行任何操作。

请注意,分配器可能会给集合提供比其请求更多的空间。 因此,不能依靠容量来精确地将其最小化。 如果预计将来会插入,则最好使用 reserve

Panics

如果新容量溢出 usize,就会出现 panics。

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<i32> = [1].into();
buf.reserve_exact(10);
assert!(buf.capacity() >= 11);
Run
source

pub fn reserve(&mut self, additional: usize)

为至少 additional 多个要插入给定双端队列的元素保留容量。 集合可以保留更多空间来推测性地避免频繁的重新分配。

Panics

如果新容量溢出 usize,就会出现 panics。

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<i32> = [1].into();
buf.reserve(10);
assert!(buf.capacity() >= 11);
Run
1.57.0 · source

pub fn try_reserve_exact( &mut self, additional: usize ) -> Result<(), TryReserveError>

尝试为至少 additional 多个要插入给定双端队列的元素保留最小容量。 调用 try_reserve_exact 后,如果返回 Ok(()),则容量将大于或等于 self.len() + additional

如果容量已经足够,则不执行任何操作。

请注意,分配器可能会给集合提供比其请求更多的空间。 因此,不能依靠容量来精确地最小化。 如果希望将来插入,则首选 try_reserve

Errors

如果容量溢出 usize,或者分配器报告失败,则返回错误。

Examples
use std::collections::TryReserveError;
use std::collections::VecDeque;

fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    let mut output = VecDeque::new();

    // 预先保留内存,如果不能,则退出
    output.try_reserve_exact(data.len())?;

    // 现在我们知道这不能 OOM(Out-Of-Memory) 完成我们复杂的工作
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // 非常复杂
    }));

    Ok(output)
}
Run
1.57.0 · source

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>

尝试为要插入给定双端队列的至少 additional 更多元素保留容量。 集合可以保留更多空间来推测性地避免频繁的重新分配。 调用 try_reserve 后,如果返回 Ok(()),容量将大于等于 self.len() + additional

如果容量已经足够,则不执行任何操作。 即使发生错误,此方法也会保留内容。

Errors

如果容量溢出 usize,或者分配器报告失败,则返回错误。

Examples
use std::collections::TryReserveError;
use std::collections::VecDeque;

fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    let mut output = VecDeque::new();

    // 预先保留内存,如果不能,则退出
    output.try_reserve(data.len())?;

    // 现在我们知道在我们复杂的工作中这不能 OOM
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // 非常复杂
    }));

    Ok(output)
}
Run
1.5.0 · source

pub fn shrink_to_fit(&mut self)

尽可能缩小双端队列的容量。

它将尽可能接近长度丢弃,但分配器仍可能通知双端队列有空间容纳更多元素。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);
buf.extend(0..4);
assert_eq!(buf.capacity(), 15);
buf.shrink_to_fit();
assert!(buf.capacity() >= 4);
Run
1.56.0 · source

pub fn shrink_to(&mut self, min_capacity: usize)

用下限缩小双端队列的容量。

容量将至少保持与长度和提供的值一样大。

如果当前容量小于下限,则为无操作。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);
buf.extend(0..4);
assert_eq!(buf.capacity(), 15);
buf.shrink_to(6);
assert!(buf.capacity() >= 6);
buf.shrink_to(0);
assert!(buf.capacity() >= 4);
Run
1.16.0 · source

pub fn truncate(&mut self, len: usize)

缩短双端队列,保留前 len 个元素并丢弃其余元素。

如果 len 大于双端队列的当前长度,则无效。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);
buf.truncate(1);
assert_eq!(buf, [5]);
Run
source

pub fn allocator(&self) -> &A

🔬This is a nightly-only experimental API. (allocator_api #32838)

返回底层分配器的引用。

source

pub fn iter(&self) -> Iter<'_, T>

返回从前到后的迭代器。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(3);
buf.push_back(4);
let b: &[_] = &[&5, &3, &4];
let c: Vec<&i32> = buf.iter().collect();
assert_eq!(&c[..], b);
Run
source

pub fn iter_mut(&mut self) -> IterMut<'_, T>

返回从前到后的迭代器,该迭代器返回可变引用。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(3);
buf.push_back(4);
for num in buf.iter_mut() {
    *num = *num - 2;
}
let b: &[_] = &[&mut 3, &mut 1, &mut 2];
assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
Run
1.5.0 · source

pub fn as_slices(&self) -> (&[T], &[T])

返回一对按顺序包含双端队列内容的切片。

如果之前调用了 make_contiguous,则双端队列的所有元素都将在第一个切片中,而第二个切片将为空。

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();

deque.push_back(0);
deque.push_back(1);
deque.push_back(2);

assert_eq!(deque.as_slices(), (&[0, 1, 2][..], &[][..]));

deque.push_front(10);
deque.push_front(9);

assert_eq!(deque.as_slices(), (&[9, 10][..], &[0, 1, 2][..]));
Run
1.5.0 · source

pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T])

返回一对按顺序包含双端队列内容的切片。

如果之前调用了 make_contiguous,则双端队列的所有元素都将在第一个切片中,而第二个切片将为空。

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();

deque.push_back(0);
deque.push_back(1);

deque.push_front(10);
deque.push_front(9);

deque.as_mut_slices().0[0] = 42;
deque.as_mut_slices().1[0] = 24;
assert_eq!(deque.as_slices(), (&[42, 10][..], &[24, 1][..]));
Run
source

pub fn len(&self) -> usize

返回双端队列中的元素数。

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();
assert_eq!(deque.len(), 0);
deque.push_back(1);
assert_eq!(deque.len(), 1);
Run
source

pub fn is_empty(&self) -> bool

如果双端队列为空,则返回 true

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();
assert!(deque.is_empty());
deque.push_front(1);
assert!(!deque.is_empty());
Run
1.51.0 · source

pub fn range<R>(&self, range: R) -> Iter<'_, T> where R: RangeBounds<usize>,

创建一个覆盖双端队列中指定范围的迭代器。

Panics

如果起点大于终点或终点大于双端队列的长度,则会出现 panic。

Examples
use std::collections::VecDeque;

let deque: VecDeque<_> = [1, 2, 3].into();
let range = deque.range(2..).copied().collect::<VecDeque<_>>();
assert_eq!(range, [3]);

// 全方位涵盖所有内容
let all = deque.range(..);
assert_eq!(all.len(), 3);
Run
1.51.0 · source

pub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T> where R: RangeBounds<usize>,

创建一个迭代器,覆盖双端队列中指定的无效范围。

Panics

如果起点大于终点或终点大于双端队列的长度,则会出现 panic。

Examples
use std::collections::VecDeque;

let mut deque: VecDeque<_> = [1, 2, 3].into();
for v in deque.range_mut(2..) {
  *v *= 2;
}
assert_eq!(deque, [1, 2, 6]);

// 全方位涵盖所有内容
for v in deque.range_mut(..) {
  *v *= 2;
}
assert_eq!(deque, [2, 4, 12]);
Run
1.6.0 · source

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A> where R: RangeBounds<usize>,

从双端队列中批量删除指定范围,并以迭代器的形式返回所有删除的元素。如果迭代器在被完全消耗之前被丢弃,它会丢弃剩余的已删除元素。

返回的迭代器在队列上保留一个可变借用以优化其实现。

Panics

如果起点大于终点或终点大于双端队列的长度,则会出现 panic。

Leaking

如果返回的迭代器离开作用域而没有被丢弃 (例如,由于 mem::forget),则双端队列可能会任意丢失和泄漏元素,包括范围之外的元素。

Examples
use std::collections::VecDeque;

let mut deque: VecDeque<_> = [1, 2, 3].into();
let drained = deque.drain(2..).collect::<VecDeque<_>>();
assert_eq!(drained, [3]);
assert_eq!(deque, [1, 2]);

// 全范围清除所有内容,就像 `clear()` 一样
deque.drain(..);
assert!(deque.is_empty());
Run
source

pub fn clear(&mut self)

清除双端队列,删除所有值。

Examples
use std::collections::VecDeque;

let mut deque = VecDeque::new();
deque.push_back(1);
deque.clear();
assert!(deque.is_empty());
Run
1.12.0 · source

pub fn contains(&self, x: &T) -> boolwhere T: PartialEq<T>,

如果双端队列包含等于给定值的元素,则返回 true

这个操作是 O(n)。

请注意,如果您有一个排序的 VecDequebinary_search 可能会更快。

Examples
use std::collections::VecDeque;

let mut deque: VecDeque<u32> = VecDeque::new();

deque.push_back(0);
deque.push_back(1);

assert_eq!(deque.contains(&1), true);
assert_eq!(deque.contains(&10), false);
Run
source

pub fn front(&self) -> Option<&T>

提供对前面元素的引用,如果双端队列为空,则为 None

Examples
use std::collections::VecDeque;

let mut d = VecDeque::new();
assert_eq!(d.front(), None);

d.push_back(1);
d.push_back(2);
assert_eq!(d.front(), Some(&1));
Run
source

pub fn front_mut(&mut self) -> Option<&mut T>

提供对前面元素的,可变引用,如果双端队列为空,则为 None

Examples
use std::collections::VecDeque;

let mut d = VecDeque::new();
assert_eq!(d.front_mut(), None);

d.push_back(1);
d.push_back(2);
match d.front_mut() {
    Some(x) => *x = 9,
    None => (),
}
assert_eq!(d.front(), Some(&9));
Run
source

pub fn back(&self) -> Option<&T>

提供对后退元素的引用,如果双端队列为空,则为 None

Examples
use std::collections::VecDeque;

let mut d = VecDeque::new();
assert_eq!(d.back(), None);

d.push_back(1);
d.push_back(2);
assert_eq!(d.back(), Some(&2));
Run
source

pub fn back_mut(&mut self) -> Option<&mut T>

如果双端队列为空,则为后面的元素提供一个,可变引用,或 None

Examples
use std::collections::VecDeque;

let mut d = VecDeque::new();
assert_eq!(d.back(), None);

d.push_back(1);
d.push_back(2);
match d.back_mut() {
    Some(x) => *x = 9,
    None => (),
}
assert_eq!(d.back(), Some(&9));
Run
source

pub fn pop_front(&mut self) -> Option<T>

删除第一个元素并返回它,如果双端队列为空,则返回 None

Examples
use std::collections::VecDeque;

let mut d = VecDeque::new();
d.push_back(1);
d.push_back(2);

assert_eq!(d.pop_front(), Some(1));
assert_eq!(d.pop_front(), Some(2));
assert_eq!(d.pop_front(), None);
Run
source

pub fn pop_back(&mut self) -> Option<T>

从双端队列中移除最后一个元素并返回它,如果为空则返回 None

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
assert_eq!(buf.pop_back(), None);
buf.push_back(1);
buf.push_back(3);
assert_eq!(buf.pop_back(), Some(3));
Run
source

pub fn push_front(&mut self, value: T)

将元素添加到双端队列。

Examples
use std::collections::VecDeque;

let mut d = VecDeque::new();
d.push_front(1);
d.push_front(2);
assert_eq!(d.front(), Some(&2));
Run
source

pub fn push_back(&mut self, value: T)

将一个元素追加到双端队列的后面。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(1);
buf.push_back(3);
assert_eq!(3, *buf.back().unwrap());
Run
1.5.0 · source

pub fn swap_remove_front(&mut self, index: usize) -> Option<T>

从双端队列中的任何位置移除一个元素并返回它,用第一个元素替换它。

这不会保留顺序,而是 O(1)。

如果 index 越界,则返回 None

索引为 0 的元素在队列的最前面。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
assert_eq!(buf.swap_remove_front(0), None);
buf.push_back(1);
buf.push_back(2);
buf.push_back(3);
assert_eq!(buf, [1, 2, 3]);

assert_eq!(buf.swap_remove_front(2), Some(3));
assert_eq!(buf, [2, 1]);
Run
1.5.0 · source

pub fn swap_remove_back(&mut self, index: usize) -> Option<T>

从双端队列中的任何位置移除一个元素并返回它,用最后一个元素替换它。

这不会保留顺序,而是 O(1)。

如果 index 越界,则返回 None

索引为 0 的元素在队列的最前面。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
assert_eq!(buf.swap_remove_back(0), None);
buf.push_back(1);
buf.push_back(2);
buf.push_back(3);
assert_eq!(buf, [1, 2, 3]);

assert_eq!(buf.swap_remove_back(0), Some(1));
assert_eq!(buf, [3, 2]);
Run
1.5.0 · source

pub fn insert(&mut self, index: usize, value: T)

在双端队列中的 index 处插入一个元素,将所有索引大于或等于 index 的元素向后移动。

索引为 0 的元素在队列的最前面。

Panics

如果 index 大于双端队列的长度,则会产生 panic

Examples
use std::collections::VecDeque;

let mut vec_deque = VecDeque::new();
vec_deque.push_back('a');
vec_deque.push_back('b');
vec_deque.push_back('c');
assert_eq!(vec_deque, &['a', 'b', 'c']);

vec_deque.insert(1, 'd');
assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
Run
source

pub fn remove(&mut self, index: usize) -> Option<T>

从双端队列中移除并返回 index 处的元素。 靠近移除点的任意一端将被移动以腾出空间,所有受影响的元素将被移动到新位置。

如果 index 越界,则返回 None

索引为 0 的元素在队列的最前面。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(1);
buf.push_back(2);
buf.push_back(3);
assert_eq!(buf, [1, 2, 3]);

assert_eq!(buf.remove(1), Some(2));
assert_eq!(buf, [1, 3]);
Run
1.4.0 · source

pub fn split_off(&mut self, at: usize) -> Selfwhere A: Clone,

在给定索引处将双端队列拆分为两个。

返回新分配的 VecDequeself 包含元素 [0, at),返回的双端队列包含元素 [at, len)

请注意,self 的容量不会改变。

索引为 0 的元素在队列的最前面。

Panics

如果为 at > len,就会出现 panics。

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<_> = [1, 2, 3].into();
let buf2 = buf.split_off(1);
assert_eq!(buf, [1]);
assert_eq!(buf2, [2, 3]);
Run
1.4.0 · source

pub fn append(&mut self, other: &mut Self)

other 的所有元素移到 self,将 other 留空。

Panics

如果 self 中的新元素数溢出了一个 usize,就会出现 panics。

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<_> = [1, 2].into();
let mut buf2: VecDeque<_> = [3, 4].into();
buf.append(&mut buf2);
assert_eq!(buf, [1, 2, 3, 4]);
assert_eq!(buf2, []);
Run
1.4.0 · source

pub fn retain<F>(&mut self, f: F)where F: FnMut(&T) -> bool,

仅保留谓词指定的元素。

换句话说,删除 f(&e) 返回 false 的所有元素 e。 此方法在原位运行,以原始顺序恰好一次访问每个元素,并保留保留元素的顺序。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..5);
buf.retain(|&x| x % 2 == 0);
assert_eq!(buf, [2, 4]);
Run

由于按原始顺序仅对元素进行过一次访问,因此可以使用外部状态来确定要保留哪些元素。

use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..6);

let keep = [false, true, true, false, true];
let mut iter = keep.iter();
buf.retain(|_| *iter.next().unwrap());
assert_eq!(buf, [2, 3, 5]);
Run
1.61.0 · source

pub fn retain_mut<F>(&mut self, f: F)where F: FnMut(&mut T) -> bool,

仅保留谓词指定的元素。

换句话说,删除 f(&e) 返回 false 的所有元素 e。 此方法在原位运行,以原始顺序恰好一次访问每个元素,并保留保留元素的顺序。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.extend(1..5);
buf.retain_mut(|x| if *x % 2 == 0 {
    *x += 1;
    true
} else {
    false
});
assert_eq!(buf, [3, 5]);
Run
1.33.0 · source

pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T)

通过从后面删除多余的元素或通过将调用 generator 生成的元素,追加,到后面,就地修改双端队列,使 len() 等于 new_len

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);

buf.resize_with(5, Default::default);
assert_eq!(buf, [5, 10, 15, 0, 0]);

buf.resize_with(2, || unreachable!());
assert_eq!(buf, [5, 10]);

let mut state = 100;
buf.resize_with(5, || { state += 1; state });
assert_eq!(buf, [5, 10, 101, 102, 103]);
Run
1.48.0 · source

pub fn make_contiguous(&mut self) -> &mut [T]

重新排列此双端队列的内部存储,使其成为一个连续的切片,然后将其返回。

此方法不分配也不更改插入元素的顺序。当它返回可变切片时,可用于对双端队列进行排序。

一旦内部存储是连续的,as_slicesas_mut_slices 方法将在单个切片中返回双端队列的全部内容。

Examples

对双端队列的内容进行排序。

use std::collections::VecDeque;

let mut buf = VecDeque::with_capacity(15);

buf.push_back(2);
buf.push_back(1);
buf.push_front(3);

// 排序双端队列
buf.make_contiguous().sort();
assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));

// 反向排序
buf.make_contiguous().sort_by(|a, b| b.cmp(a));
assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));
Run

不可变地访问连续的切片。

use std::collections::VecDeque;

let mut buf = VecDeque::new();

buf.push_back(2);
buf.push_back(1);
buf.push_front(3);

buf.make_contiguous();
if let (slice, &[]) = buf.as_slices() {
    // 现在,我们可以确定 `slice` 包含了双端队列的所有元素,同时仍具有对 `buf` 的不可变访问权限。
    assert_eq!(buf.len(), slice.len());
    assert_eq!(slice, &[3, 2, 1] as &[_]);
}
Run
1.36.0 · source

pub fn rotate_left(&mut self, mid: usize)

将双端队列 mid 放置到左侧。

Equivalently,

  • 将项 mid 旋转到第一个位置。
  • 弹出第一个 mid 项并将其推到末尾。
  • 向右旋转 len() - mid 位置。
Panics

如果 mid 大于 len()。 请注意,mid == len() 执行 not panic,并且是无操作旋转。

Complexity

花费 *O*(min(mid, len() - mid)) 的时间,没有多余的空间。

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<_> = (0..10).collect();

buf.rotate_left(3);
assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);

for i in 1..10 {
    assert_eq!(i * 3 % 10, buf[0]);
    buf.rotate_left(3);
}
assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
Run
1.36.0 · source

pub fn rotate_right(&mut self, k: usize)

向右旋转 k 位置的双端队列。

Equivalently,

  • 将第一个项旋转到位置 k
  • 弹出最后一个 k 项并将其推到前面。
  • len() - k 位置向左旋转。
Panics

如果 k 大于 len()。 请注意,k == len() 执行 not panic,并且是无操作旋转。

Complexity

花费 *O*(min(k, len() - k)) 的时间,没有多余的空间。

Examples
use std::collections::VecDeque;

let mut buf: VecDeque<_> = (0..10).collect();

buf.rotate_right(3);
assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);

for i in 1..10 {
    assert_eq!(0, buf[i * 3 % 10]);
    buf.rotate_right(3);
}
assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
Run

二进制搜索在这个 VecDeque 中搜索给定的元素。 如果 VecDeque 没有排序,返回的结果是不确定的,没有意义。

如果找到该值,则返回 Result::Ok,其中包含匹配元素的索引。 如果有多个匹配项,则可以返回任何一个匹配项。 如果找不到该值,则返回 Result::Err,其中包含在保留排序顺序的同时可以在其中插入匹配元素的索引。

另请参见 binary_search_bybinary_search_by_keypartition_point

Examples

查找一系列四个元素。 找到第一个,具有唯一确定的位置; 没有找到第二个和第三个; 第四个可以匹配 [1, 4] 中的任何位置。

use std::collections::VecDeque;

let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();

assert_eq!(deque.binary_search(&13),  Ok(9));
assert_eq!(deque.binary_search(&4),   Err(7));
assert_eq!(deque.binary_search(&100), Err(13));
let r = deque.binary_search(&1);
assert!(matches!(r, Ok(1..=4)));
Run

如果要在已排序的双端队列中插入项,同时保持排序顺序,请考虑使用 partition_point:

use std::collections::VecDeque;

let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
let idx = deque.partition_point(|&x| x < num);
// 以上等价于 `let idx = deque.binary_search(&num).unwrap_or_else(|x| x);`
deque.insert(idx, num);
assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
Run
1.54.0 · source

pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>where F: FnMut(&'a T) -> Ordering,

二进制搜索使用比较器函数搜索这个 VecDeque

比较器函数应返回一个命令代码,指示其参数是 LessEqual 还是 Greater 所需的目标。 如果 VecDeque 未排序或比较器函数未实现与底层 VecDeque 的排序顺序一致的顺序,则返回结果未指定且无意义。

如果找到该值,则返回 Result::Ok,其中包含匹配元素的索引。如果有多个匹配项,则可以返回任何一个匹配项。 如果找不到该值,则返回 Result::Err,其中包含在保留排序顺序的同时可以在其中插入匹配元素的索引。

另请参见 binary_searchbinary_search_by_keypartition_point

Examples

查找一系列四个元素。找到第一个,具有唯一确定的位置; 没有找到第二个和第三个; 第四个可以匹配 [1, 4] 中的任何位置。

use std::collections::VecDeque;

let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();

assert_eq!(deque.binary_search_by(|x| x.cmp(&13)),  Ok(9));
assert_eq!(deque.binary_search_by(|x| x.cmp(&4)),   Err(7));
assert_eq!(deque.binary_search_by(|x| x.cmp(&100)), Err(13));
let r = deque.binary_search_by(|x| x.cmp(&1));
assert!(matches!(r, Ok(1..=4)));
Run
1.54.0 · source

pub fn binary_search_by_key<'a, B, F>( &'a self, b: &B, f: F ) -> Result<usize, usize>where F: FnMut(&'a T) -> B, B: Ord,

二进制搜索使用键提取函数搜索此 VecDeque

假设双端队列按键排序,例如 make_contiguous().sort_by_key() 使用相同的键提取函数。 如果 deque 不是 key 排序的,返回的结果是不确定的,没有意义。

如果找到该值,则返回 Result::Ok,其中包含匹配元素的索引。 如果有多个匹配项,则可以返回任何一个匹配项。 如果找不到该值,则返回 Result::Err,其中包含在保留排序顺序的同时可以在其中插入匹配元素的索引。

另请参见 binary_searchbinary_search_bypartition_point

Examples

在成对的切片中按其第二个元素排序的一系列四个元素中查找。 找到第一个,具有唯一确定的位置; 没有找到第二个和第三个; 第四个可以匹配 [1, 4] 中的任何位置。

use std::collections::VecDeque;

let deque: VecDeque<_> = [(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)].into();

assert_eq!(deque.binary_search_by_key(&13, |&(a, b)| b),  Ok(9));
assert_eq!(deque.binary_search_by_key(&4, |&(a, b)| b),   Err(7));
assert_eq!(deque.binary_search_by_key(&100, |&(a, b)| b), Err(13));
let r = deque.binary_search_by_key(&1, |&(a, b)| b);
assert!(matches!(r, Ok(1..=4)));
Run
1.54.0 · source

pub fn partition_point<P>(&self, pred: P) -> usizewhere P: FnMut(&T) -> bool,

根据给定的谓词返回分区点的索引 (第二个分区的第一个元素的索引)。

假定双端队列根据给定的谓词进行了分区。 这意味着谓词返回 true 的所有元素都在双端队列的开头,而谓词返回 false 的所有元素都在末尾。

例如,[7, 15, 3, 5, 4, 12, 6] 在谓词 x % 2 != 0 下进行分区 (所有奇数都在开头,所有偶数都在结尾)。

如果双端队列没有分区,则返回的结果是未指定且无意义的,因为此方法执行一种二分查找。

另请参见 binary_searchbinary_search_bybinary_search_by_key

Examples
use std::collections::VecDeque;

let deque: VecDeque<_> = [1, 2, 3, 3, 5, 6, 7].into();
let i = deque.partition_point(|&x| x < 5);

assert_eq!(i, 4);
assert!(deque.iter().take(i).all(|&x| x < 5));
assert!(deque.iter().skip(i).all(|&x| !(x < 5)));
Run

如果要在已排序的双端队列中插入项,同时保持排序顺序:

use std::collections::VecDeque;

let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
let idx = deque.partition_point(|&x| x < num);
deque.insert(idx, num);
assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
Run
source§

impl<T: Clone, A: Allocator> VecDeque<T, A>

1.16.0 · source

pub fn resize(&mut self, new_len: usize, value: T)

通过从后面删除多余的元素或将 value 的克隆,追加,到后面,就地修改双端队列以使 len() 等于 new_len。

Examples
use std::collections::VecDeque;

let mut buf = VecDeque::new();
buf.push_back(5);
buf.push_back(10);
buf.push_back(15);
assert_eq!(buf, [5, 10, 15]);

buf.resize(2, 0);
assert_eq!(buf, [5, 10]);

buf.resize(5, 20);
assert_eq!(buf, [5, 10, 20, 20, 20]);
Run

Trait Implementations§

source§

impl<T: Clone, A: Allocator + Clone> Clone for VecDeque<T, A>

source§

fn clone(&self) -> Self

返回值的副本。 Read more
source§

fn clone_from(&mut self, other: &Self)

source 执行复制分配。 Read more
source§

impl<T: Debug, A: Allocator> Debug for VecDeque<T, A>

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

使用给定的格式化程序格式化该值。 Read more
source§

impl<T> Default for VecDeque<T>

source§

fn default() -> VecDeque<T>

创建一个空的双端队列。

source§

impl<T, A: Allocator> Drop for VecDeque<T, A>

source§

fn drop(&mut self)

执行此类型的析构函数。 Read more
1.2.0 · source§

impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A>

source§

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

使用迭代器的内容扩展集合。 Read more
source§

fn extend_one(&mut self, elem: &'a T)

🔬This is a nightly-only experimental API. (extend_one #72631)
用一个元素扩展一个集合。
source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)
在集合中为给定数量的附加元素保留容量。 Read more
source§

impl<T, A: Allocator> Extend<T> for VecDeque<T, A>

source§

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

使用迭代器的内容扩展集合。 Read more
source§

fn extend_one(&mut self, elem: T)

🔬This is a nightly-only experimental API. (extend_one #72631)
用一个元素扩展一个集合。
source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)
在集合中为给定数量的附加元素保留容量。 Read more
1.56.0 · source§

impl<T, const N: usize> From<[T; N]> for VecDeque<T>

source§

fn from(arr: [T; N]) -> Self

[T; N] 转换为 VecDeque<T>

use std::collections::VecDeque;

let deq1 = VecDeque::from([1, 2, 3, 4]);
let deq2: VecDeque<_> = [1, 2, 3, 4].into();
assert_eq!(deq1, deq2);
Run
1.10.0 · source§

impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A>

source§

fn from(other: Vec<T, A>) -> Self

Vec<T> 变成 VecDeque<T>

此转换保证在 O(1) 时间内运行,并且不会重新分配 Vec 的缓冲区或分配任何额外的内存。

1.10.0 · source§

impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A>

source§

fn from(other: VecDeque<T, A>) -> Self

VecDeque<T> 变成 Vec<T>

这永远不需要重新分配,但是如果循环缓冲区恰好不在分配开始时,则确实需要进行 O(n) 数据移动。

Examples
use std::collections::VecDeque;

// 这是 *O*(1)。
let deque: VecDeque<_> = (1..5).collect();
let ptr = deque.as_slices().0.as_ptr();
let vec = Vec::from(deque);
assert_eq!(vec, [1, 2, 3, 4]);
assert_eq!(vec.as_ptr(), ptr);

// 这一项需要重新整理数据。
let mut deque: VecDeque<_> = (1..5).collect();
deque.push_front(9);
deque.push_front(8);
let ptr = deque.as_slices().1.as_ptr();
let vec = Vec::from(deque);
assert_eq!(vec, [8, 9, 1, 2, 3, 4]);
assert_eq!(vec.as_ptr(), ptr);
Run
source§

impl<T> FromIterator<T> for VecDeque<T>

source§

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T>

从迭代器创建一个值。 Read more
source§

impl<T: Hash, A: Allocator> Hash for VecDeque<T, A>

source§

fn hash<H: Hasher>(&self, state: &mut H)

将该值输入给定的 HasherRead more
1.3.0 · source§

fn hash_slice<H>(data: &[Self], state: &mut H)where H: Hasher, Self: Sized,

将这种类型的切片送入给定的 Hasher 中。 Read more
source§

impl<T, A: Allocator> Index<usize> for VecDeque<T, A>

§

type Output = T

索引后返回的类型。
source§

fn index(&self, index: usize) -> &T

执行索引 (container[index]) 操作。 Read more
source§

impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A>

source§

fn index_mut(&mut self, index: usize) -> &mut T

执行可变索引 (container[index]) 操作。 Read more
source§

impl<'a, T, A: Allocator> IntoIterator for &'a VecDeque<T, A>

§

type Item = &'a T

被迭代的元素的类型。
§

type IntoIter = Iter<'a, T>

我们将其变成哪种迭代器?
source§

fn into_iter(self) -> Iter<'a, T>

从一个值创建一个迭代器。 Read more
source§

impl<'a, T, A: Allocator> IntoIterator for &'a mut VecDeque<T, A>

§

type Item = &'a mut T

被迭代的元素的类型。
§

type IntoIter = IterMut<'a, T>

我们将其变成哪种迭代器?
source§

fn into_iter(self) -> IterMut<'a, T>

从一个值创建一个迭代器。 Read more
source§

impl<T, A: Allocator> IntoIterator for VecDeque<T, A>

source§

fn into_iter(self) -> IntoIter<T, A>

将双端队列消耗到一个从前到后的迭代器中,按值产生元素。

§

type Item = T

被迭代的元素的类型。
§

type IntoIter = IntoIter<T, A>

我们将其变成哪种迭代器?
source§

impl<T: Ord, A: Allocator> Ord for VecDeque<T, A>

source§

fn cmp(&self, other: &Self) -> Ordering

此方法返回 selfother 之间的 OrderingRead more
1.21.0 · source§

fn max(self, other: Self) -> Selfwhere Self: Sized,

比较并返回两个值中的最大值。 Read more
1.21.0 · source§

fn min(self, other: Self) -> Selfwhere Self: Sized,

比较并返回两个值中的最小值。 Read more
1.50.0 · source§

fn clamp(self, min: Self, max: Self) -> Selfwhere Self: Sized + PartialOrd<Self>,

将值限制在某个时间间隔内。 Read more
1.17.0 · source§

impl<T, U, A: Allocator> PartialEq<&[U]> for VecDeque<T, A>where T: PartialEq<U>,

source§

fn eq(&self, other: &&[U]) -> bool

此方法测试 selfother 值是否相等,并由 == 使用。
source§

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的,并且不应在没有充分理由的情况下被覆盖。
1.17.0 · source§

impl<T, U, A: Allocator, const N: usize> PartialEq<&[U; N]> for VecDeque<T, A>where T: PartialEq<U>,

source§

fn eq(&self, other: &&[U; N]) -> bool

此方法测试 selfother 值是否相等,并由 == 使用。
source§

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的,并且不应在没有充分理由的情况下被覆盖。
1.17.0 · source§

impl<T, U, A: Allocator> PartialEq<&mut [U]> for VecDeque<T, A>where T: PartialEq<U>,

source§

fn eq(&self, other: &&mut [U]) -> bool

此方法测试 selfother 值是否相等,并由 == 使用。
source§

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的,并且不应在没有充分理由的情况下被覆盖。
1.17.0 · source§

impl<T, U, A: Allocator, const N: usize> PartialEq<&mut [U; N]> for VecDeque<T, A>where T: PartialEq<U>,

source§

fn eq(&self, other: &&mut [U; N]) -> bool

此方法测试 selfother 值是否相等,并由 == 使用。
source§

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的,并且不应在没有充分理由的情况下被覆盖。
1.17.0 · source§

impl<T, U, A: Allocator, const N: usize> PartialEq<[U; N]> for VecDeque<T, A>where T: PartialEq<U>,

source§

fn eq(&self, other: &[U; N]) -> bool

此方法测试 selfother 值是否相等,并由 == 使用。
source§

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的,并且不应在没有充分理由的情况下被覆盖。
1.17.0 · source§

impl<T, U, A: Allocator> PartialEq<Vec<U, A>> for VecDeque<T, A>where T: PartialEq<U>,

source§

fn eq(&self, other: &Vec<U, A>) -> bool

此方法测试 selfother 值是否相等,并由 == 使用。
source§

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的,并且不应在没有充分理由的情况下被覆盖。
source§

impl<T: PartialEq, A: Allocator> PartialEq<VecDeque<T, A>> for VecDeque<T, A>

source§

fn eq(&self, other: &Self) -> bool

此方法测试 selfother 值是否相等,并由 == 使用。
source§

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的,并且不应在没有充分理由的情况下被覆盖。
source§

impl<T: PartialOrd, A: Allocator> PartialOrd<VecDeque<T, A>> for VecDeque<T, A>

source§

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

如果存在,则此方法返回 selfother 值之间的顺序。 Read more
source§

fn lt(&self, other: &Rhs) -> bool

此方法测试的内容少于 (对于 selfother),并且由 < 操作员使用。 Read more
source§

fn le(&self, other: &Rhs) -> bool

此方法测试小于或等于 (对于 selfother),并且由 <= 运算符使用。 Read more
source§

fn gt(&self, other: &Rhs) -> bool

此方法测试大于 (对于 selfother),并且由 > 操作员使用。 Read more
source§

fn ge(&self, other: &Rhs) -> bool

此方法测试是否大于或等于 (对于 selfother),并且由 >= 运算符使用。 Read more
source§

impl<T: Eq, A: Allocator> Eq for VecDeque<T, A>

Auto Trait Implementations§

§

impl<T, A> RefUnwindSafe for VecDeque<T, A>where A: RefUnwindSafe, T: RefUnwindSafe,

§

impl<T, A> Send for VecDeque<T, A>where A: Send, T: Send,

§

impl<T, A> Sync for VecDeque<T, A>where A: Sync, T: Sync,

§

impl<T, A> Unpin for VecDeque<T, A>where A: Unpin, T: Unpin,

§

impl<T, A> UnwindSafe for VecDeque<T, A>where A: UnwindSafe, T: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

获取 selfTypeIdRead more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

从拥有的值中一成不变地借用。 Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

从拥有的值中借用。 Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

返回未更改的参数。

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

调用 U::from(self)

也就是说,这种转换是 From<T> for U 实现选择执行的任何操作。

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

获得所有权后的结果类型。
source§

fn to_owned(&self) -> T

从借用的数据创建拥有的数据,通常是通过克隆。 Read more
source§

fn clone_into(&self, target: &mut T)

使用借来的数据来替换拥有的数据,通常是通过克隆。 Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

发生转换错误时返回的类型。
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

执行转换。
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

发生转换错误时返回的类型。
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

执行转换。