Struct alloc::collections::vec_deque::VecDeque

pub struct VecDeque<T, A: Allocator = Global> { /* private fields */ }

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

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

extend 和 append 以这种方式推到后面，并从前到后迭代 VecDeque。

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

use std::collections::VecDeque;

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

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

Implementations

impl<T> VecDeque<T>

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

创建一个空的双端队列。

Examples

use std::collections::VecDeque;

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

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

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

Examples

use std::collections::VecDeque;

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

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

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

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);

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));

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);

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

交换索引为 i 和 j 的元素。

i 和 j 可能是相等的。

索引为 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]);

pub fn capacity(&self) -> usize

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

Examples

use std::collections::VecDeque;

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

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);

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);

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)
}

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)
}

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);

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);

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]);

pub fn allocator(&self) -> &A

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

返回底层分配器的引用。

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);

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);

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][..]));

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][..]));

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);

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

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);

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]);

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

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

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

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

这个操作是 O(n)。

请注意，如果您有一个排序的 VecDeque，binary_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);

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));

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));

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));

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));

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);

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));

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));

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

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]);

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]);

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']);

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]);

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

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

返回新分配的 VecDeque。 self 包含元素 [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]);

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, []);

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]);

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

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]);

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]);

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]);

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

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

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

一旦内部存储是连续的，as_slices 和 as_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 &[_]));

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

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 &[_]);
}

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]);

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]);

pub fn binary_search(&self, x: &T) -> Result<usize, usize>where T: Ord,

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

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

另请参见 binary_search_by，binary_search_by_key 和 partition_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)));

如果要在已排序的双端队列中插入项，同时保持排序顺序，请考虑使用 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]);

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

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

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

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

另请参见 binary_search，binary_search_by_key 和 partition_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)));

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_search，binary_search_by 和 partition_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)));

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_search，binary_search_by 和 binary_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)));

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

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]);

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

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]);

Trait Implementations

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

fn clone(&self) -> Self

返回值的副本。

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

从 source 执行复制分配。

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

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

使用给定的格式化程序格式化该值。

impl<T> Default for VecDeque<T>

fn default() -> VecDeque<T>

创建一个空的双端队列。

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

fn drop(&mut self)

执行此类型的析构函数。

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

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

使用迭代器的内容扩展集合。

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

🔬This is a nightly-only experimental API. (extend_one #72631)

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)

在集合中为给定数量的附加元素保留容量。

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

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

使用迭代器的内容扩展集合。

fn extend_one(&mut self, elem: T)

🔬This is a nightly-only experimental API. (extend_one #72631)

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)

在集合中为给定数量的附加元素保留容量。

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

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);

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

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

将 Vec<T> 变成 VecDeque<T>。

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

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

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);

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

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

从迭代器创建一个值。

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

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

将该值输入给定的 Hasher。

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

将这种类型的切片送入给定的 Hasher 中。

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

type Output = T

索引后返回的类型。

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

执行索引 (container[index]) 操作。

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

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

执行可变索引 (container[index]) 操作。

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

type Item = &'a T

被迭代的元素的类型。

type IntoIter = Iter<'a, T>

我们将其变成哪种迭代器？

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

从一个值创建一个迭代器。

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

type Item = &'a mut T

被迭代的元素的类型。

type IntoIter = IterMut<'a, T>

我们将其变成哪种迭代器？

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

从一个值创建一个迭代器。

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

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

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

type Item = T

被迭代的元素的类型。

type IntoIter = IntoIter<T, A>

我们将其变成哪种迭代器？

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

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

此方法返回 self 和 other 之间的 Ordering。

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

比较并返回两个值中的最大值。

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

比较并返回两个值中的最小值。

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

将值限制在某个时间间隔内。

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

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

此方法测试 self 和 other 值是否相等，并由 == 使用。

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

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

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

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

此方法测试 self 和 other 值是否相等，并由 == 使用。

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

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

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

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

此方法测试 self 和 other 值是否相等，并由 == 使用。

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

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

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

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

此方法测试 self 和 other 值是否相等，并由 == 使用。

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

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

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

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

此方法测试 self 和 other 值是否相等，并由 == 使用。

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

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

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

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

此方法测试 self 和 other 值是否相等，并由 == 使用。

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

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

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

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

此方法测试 self 和 other 值是否相等，并由 == 使用。

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

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

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

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

如果存在，则此方法返回 self 和 other 值之间的顺序。

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

此方法测试的内容少于 (对于 self 和 other)，并且由 < 操作员使用。

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

此方法测试小于或等于 (对于 self 和 other)，并且由 <= 运算符使用。

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

此方法测试大于 (对于 self 和 other)，并且由 > 操作员使用。

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

此方法测试是否大于或等于 (对于 self 和 other)，并且由 >= 运算符使用。

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