Struct std::collections::VecDeque

pub struct VecDeque<T> { /* fields omitted */ }

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

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

extend append 以这种方式推向后部，并且在 VecDeque 上进行迭代从前到后。

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

Implementations

impl<T> VecDeque<T>

pub fn new() -> VecDeque<T>

创建一个空的 VecDeque。

Examples

use std::collections::VecDeque;

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

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

创建一个空的 VecDeque，其中至少有 capacity 元素的空间。

Examples

use std::collections::VecDeque;

let vector: 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);
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);
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

返回 VecDeque 无需重新分配即可容纳的元素数。

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)

保留最小容量，以便在给定的 VecDeque 中精确插入 additional 个元素。 如果容量已经足够，则不执行任何操作。

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

Panics

如果新容量溢出 usize，则为 Panics。

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
buf.reserve_exact(10);
assert!(buf.capacity() >= 11);

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

为给定的 VecDeque 至少保留 additional 个要插入的元素保留容量。 该集合可以保留更多空间，以避免频繁的重新分配。

Panics

如果新容量溢出 usize，则为 Panics。

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
buf.reserve(10);
assert!(buf.capacity() >= 11);

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

🔬 This is a nightly-only experimental API. (try_reserve #48043)

new API

尝试保留最小容量，以便在给定的 VecDeque<T> 中精确插入 additional 个元素。

调用 try_reserve_exact 后，容量将大于或等于 self.len() + additional。 如果容量已经足够，则不执行任何操作。

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

Errors

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

Examples

#![feature(try_reserve)]
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>

🔬 This is a nightly-only experimental API. (try_reserve #48043)

new API

尝试为给 VecDeque<T> 至少插入 additional 个元素保留容量。 该集合可以保留更多空间，以避免频繁的重新分配。 调用 try_reserve 后，容量将大于或等于 self.len() + additional。 如果容量已经足够，则不执行任何操作。

Errors

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

Examples

#![feature(try_reserve)]
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)

尽可能缩小 VecDeque 的容量。

它将 drop 到尽可能接近长度的位置，但分配器仍可能通知 VecDeque 还有空间容纳更多的元素。

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)

🔬 This is a nightly-only experimental API. (shrink_to #56431)

new API

降低 VecDeque 的容量。

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

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

Examples

#![feature(shrink_to)]
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)

缩短 VecDeque，保留第一个 len 元素，然后丢弃其余的元素。

如果 len 大于 `VecDeque’ 的当前长度，则无效。

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

返回一对切片，这些切片按顺序包含 VecDeque 的内容。

如果先前调用了 make_contiguous，则 VecDeque 的所有元素都将位于第一个切片中，而第二个切片将为空。

Examples

use std::collections::VecDeque;

let mut vector = VecDeque::new();

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

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

vector.push_front(10);
vector.push_front(9);

assert_eq!(vector.as_slices(), (&[9, 10][..], &[0, 1, 2][..]));

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

返回一对切片，这些切片按顺序包含 VecDeque 的内容。

如果先前调用了 make_contiguous，则 VecDeque 的所有元素都将位于第一个切片中，而第二个切片将为空。

Examples

use std::collections::VecDeque;

let mut vector = VecDeque::new();

vector.push_back(0);
vector.push_back(1);

vector.push_front(10);
vector.push_front(9);

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

pub fn len(&self) -> usize

返回 VecDeque 中的元素数。

Examples

use std::collections::VecDeque;

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

pub fn is_empty(&self) -> bool

如果 VecDeque 为空，则返回 true。

Examples

use std::collections::VecDeque;

let mut v = VecDeque::new();
assert!(v.is_empty());
v.push_front(1);
assert!(!v.is_empty());

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

创建一个覆盖 VecDeque 中指定范围的迭代器。

Panics

如果起点大于终点或终点大于 vector 的长度，则为 Panics。

Examples

use std::collections::VecDeque;

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

// 全方位涵盖所有内容
let all = v.range(..);
assert_eq!(all.len(), 3);

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

创建一个覆盖 VecDeque 中指定的可变范围的迭代器。

Panics

如果起点大于终点或终点大于 vector 的长度，则为 Panics。

Examples

use std::collections::VecDeque;

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

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

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

创建一个 draining 迭代器，该迭代器将删除 VecDeque 中的指定范围并产生已删除的项。

注意 1: 即使直到最后才消耗迭代器，元素范围也会被删除。

注意 2: 如果 Drain 值没有被丢弃，但持有的借用已过期 (例如，由于 mem::forget)，则未指定从双端队列中删除了多少个元素。

Panics

如果起点大于终点或终点大于 vector 的长度，则为 Panics。

Examples

use std::collections::VecDeque;

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

// 全系列清除所有内容
v.drain(..);
assert!(v.is_empty());

pub fn clear(&mut self)

清除 VecDeque，删除所有值。

Examples

use std::collections::VecDeque;

let mut v = VecDeque::new();
v.push_back(1);
v.clear();
assert!(v.is_empty());

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

如果 VecDeque 包含等于给定值的元素，则返回 true。

Examples

use std::collections::VecDeque;

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

vector.push_back(0);
vector.push_back(1);

assert_eq!(vector.contains(&1), true);
assert_eq!(vector.contains(&10), false);

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

提供对前元素的引用，如果 VecDeque 为空，则为 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>

为前元素提供可变引用，如果 VecDeque 为空，则为 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>

提供对 back 元素的引用，如果 VecDeque 为空，则提供 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>

提供对 back 元素的可变引用，如果 VecDeque 为空，则提供 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>

删除第一个元素并返回它，如果 VecDeque 为空，则返回 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>

从 VecDeque 中删除最后一个元素并返回它; 如果它为空，则返回 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)

将元素添加到 VecDeque。

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)

在 VecDeque 的后面附加一个元素。

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>

从 VecDeque 的任何位置删除一个元素并返回，并用第一个元素替换它。

这不会保留顺序，而是 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>

从 VecDeque 中的任何位置删除元素，然后将其返回，并用最后一个元素替换。

这不会保留顺序，而是 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)

在 VecDeque 内的 index 处插入一个元素，将所有索引大于或等于 index 的元素向后移动。

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

Panics

如果 index 大于 VecDeque 的长度，则为 Panics

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>

从 VecDeque 删除 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]);

#[must_use = "use `.truncate()` if you don't need the other half"]

pub fn split_off(&mut self, at: usize) -> VecDeque<T>

在给定的索引处将 VecDeque 拆分为两个。

返回新分配的 VecDeque。 self 包含元素 [0, at)，返回的 VecDeque 包含元素 [at, len)。

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

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

Panics

如果为 at > len，则为 Panics。

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
let buf2 = buf.split_off(1);
assert_eq!(buf, [1]);
assert_eq!(buf2, [2, 3]);

pub fn append(&mut self, other: &mut VecDeque<T>)

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

Panics

Panics，如果 self 中新的元素数量溢出 usize。

Examples

use std::collections::VecDeque;

let mut buf: VecDeque<_> = vec![1, 2].into_iter().collect();
let mut buf2: VecDeque<_> = vec![3, 4].into_iter().collect();
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, 

仅保留谓词指定的元素。

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

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 i = 0;
buf.retain(|_| (keep[i], i += 1).0);
assert_eq!(buf, [2, 3, 5]);

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

在原位修改 VecDeque，以使 len() 等于 new_len，方法是从后面移除多余的元素，或者通过在后面附加调用 generator 生成的元素。

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 方法将在单个切片中返回 VecDeque 的全部内容。

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, 

Binary 在此排序的 VecDeque 上搜索给定的元素。

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

另请参见 binary_search_by，binary_search_by_key 和 partition_point。

Examples

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

use std::collections::VecDeque;

let deque: VecDeque<_> = vec![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)));

如果要在已排序的 VecDeque 上插入项目，同时保持排序顺序:

use std::collections::VecDeque;

let mut deque: VecDeque<_> = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
let num = 42;
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, 

Binary 使用比较器函数搜索此排序的 VecDeque。

比较器函数应实现与基础 VecDeque 的排序顺序一致的顺序，并返回指示其参数比所需目标高 Less，Equal 或 Greater 的顺序代码。

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

另请参见 binary_search，binary_search_by_key 和 partition_point。

Examples

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

use std::collections::VecDeque;

let deque: VecDeque<_> = vec![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, 

Binary 使用关键字提取函数搜索此排序的 VecDeque。

假设 VecDeque 是按键排序的，例如 make_contiguous().sort_by_key() 使用相同的键提取函数。

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

另请参见 binary_search，binary_search_by 和 partition_point。

Examples

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

use std::collections::VecDeque;

let deque: VecDeque<_> = vec![(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) -> usize where
    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<_> = vec![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)));

impl<T> VecDeque<T> where
    T: Clone, 

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

通过从后面移除多余的元素或在后面附加 value 的克隆，就地修改 VecDeque，以使 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 for VecDeque<T> where
    T: Clone, 

pub fn clone(&self) -> VecDeque<T>

返回值的副本。

pub fn clone_from(&mut self, other: &VecDeque<T>)

从 source 执行复制分配。

impl<T> Debug for VecDeque<T> where
    T: Debug, 

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

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

impl<T> Default for VecDeque<T>

pub fn default() -> VecDeque<T>

创建一个空的 VecDeque<T>。

impl<T> Drop for VecDeque<T>

pub fn drop(&mut self)

执行此类型的析构函数。

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

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

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

pub fn extend_one(&mut self, &T)

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

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

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

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

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

impl<A> Extend<A> for VecDeque<A>

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

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

pub fn extend_one(&mut self, elem: A)

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

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

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

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

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

impl<T> From<Vec<T, Global>> for VecDeque<T>

pub fn from(other: Vec<T, Global>) -> VecDeque<T>

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

这样可以避免在可能的情况下进行重新分配，但是这样做的条件很严格，并且随时可能更改，因此除非 Vec<T> 来自 From<VecDeque<T>> 并且尚未重新分配，否则不应依赖它。

impl<T> From<VecDeque<T>> for Vec<T, Global>

pub fn from(other: VecDeque<T>) -> Vec<T, Global>

将 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<A> FromIterator<A> for VecDeque<A>

pub fn from_iter<T>(iter: T) -> VecDeque<A> where
    T: IntoIterator<Item = A>, 

从迭代器创建一个值。

impl<A> Hash for VecDeque<A> where
    A: Hash, 

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

将该值输入给定的 Hasher。

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

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

impl<A> Index<usize> for VecDeque<A>

type Output = A

索引后返回的类型。

pub fn index(&self, index: usize) -> &A

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

impl<A> IndexMut<usize> for VecDeque<A>

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

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

impl<T> IntoIterator for VecDeque<T>

pub fn into_iter(self) -> IntoIter<T>

将 VecDeque 消费为从前到后的迭代器，按值产生元素。

type Item = T

被迭代的元素的类型。

type IntoIter = IntoIter<T>

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

impl<'a, T> IntoIterator for &'a VecDeque<T>

type Item = &'a T

被迭代的元素的类型。

type IntoIter = Iter<'a, T>

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

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

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

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

type Item = &'a mut T

被迭代的元素的类型。

type IntoIter = IterMut<'a, T>

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

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

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

impl<A> Ord for VecDeque<A> where
    A: Ord, 

pub fn cmp(&self, other: &VecDeque<A>) -> Ordering

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

#[must_use]

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

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

#[must_use]

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

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

#[must_use]

fn clamp(self, min: Self, max: Self) -> Self

将值限制为一定的时间间隔。

impl<'_, A, B, const N: usize> PartialEq<&'_ [B; N]> for VecDeque<A> where
    A: PartialEq<B>, 

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

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

#[must_use]

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

此方法测试 !=。

impl<'_, A, B> PartialEq<&'_ [B]> for VecDeque<A> where
    A: PartialEq<B>, 

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

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

#[must_use]

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

此方法测试 !=。

impl<'_, A, B, const N: usize> PartialEq<&'_ mut [B; N]> for VecDeque<A> where
    A: PartialEq<B>, 

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

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

#[must_use]

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

此方法测试 !=。

impl<'_, A, B> PartialEq<&'_ mut [B]> for VecDeque<A> where
    A: PartialEq<B>, 

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

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

#[must_use]

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

此方法测试 !=。

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

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

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

#[must_use]

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

此方法测试 !=。

impl<A, B> PartialEq<Vec<B, Global>> for VecDeque<A> where
    A: PartialEq<B>, 

pub fn eq(&self, other: &Vec<B, Global>) -> bool

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

#[must_use]

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

此方法测试 !=。

impl<A> PartialEq<VecDeque<A>> for VecDeque<A> where
    A: PartialEq<A>, 

pub fn eq(&self, other: &VecDeque<A>) -> bool

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

#[must_use]

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

此方法测试 !=。

impl<A> PartialOrd<VecDeque<A>> for VecDeque<A> where
    A: PartialOrd<A>, 

pub fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering>

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

#[must_use]

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

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

#[must_use]

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

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

#[must_use]

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

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

#[must_use]

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

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

impl<A> Eq for VecDeque<A> where
    A: Eq,