Struct alloc::collections::vec_deque::VecDeque1.0.0[][src]

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

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

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

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

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

Implementations

创建一个空的 VecDeque

Examples

use std::collections::VecDeque;

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

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

Examples

use std::collections::VecDeque;

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

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

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

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

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

交换索引为 ij 的元素。

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

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

Examples

use std::collections::VecDeque;

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

保留最小容量,以便在给定的 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);
Run

为给定的 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);
Run
🔬 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)
}
Run
🔬 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)
}
Run

尽可能缩小 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);
Run
🔬 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);
Run

缩短 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]);
Run

返回从前到后的迭代器。

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

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

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

返回一对切片,这些切片按顺序包含 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][..]));
Run

返回一对切片,这些切片按顺序包含 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][..]));
Run

返回 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);
Run

如果 VecDeque 为空,则返回 true

Examples

use std::collections::VecDeque;

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

创建一个覆盖 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);
Run

创建一个覆盖 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]);
Run

创建一个 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());
Run

清除 VecDeque,删除所有值。

Examples

use std::collections::VecDeque;

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

如果 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);
Run

提供对前元素的引用,如果 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));
Run

为前元素提供可变引用,如果 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));
Run

提供对 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));
Run

提供对 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));
Run

删除第一个元素并返回它,如果 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);
Run

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

将元素添加到 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));
Run

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

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

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

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

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

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

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

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

仅保留谓词指定的元素。

换句话说,删除所有元素 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]);
Run

确切的顺序对于跟踪外部状态 (例如索引) 可能很有用。

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

在原位修改 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]);
Run

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

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

内部存储器连续后,as_slicesas_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 &[_]));
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

将双端队列 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

向右旋转 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

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

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

另请参见 binary_search_bybinary_search_by_keypartition_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)));
Run

如果要在已排序的 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]);
Run

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

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

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

另请参见 binary_searchbinary_search_by_keypartition_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)));
Run

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

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

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

另请参见 binary_searchbinary_search_bypartition_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)));
Run

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

假定双端队列根据给定的谓词进行了分区。 这意味着谓词返回 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<_> = 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)));
Run

通过从后面移除多余的元素或在后面附加 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]);
Run

Trait Implementations

返回值的副本。 Read more

source 执行复制分配。 Read more

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

创建一个空的 VecDeque<T>

执行此类型的析构函数。 Read more

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

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

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

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

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

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

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

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

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

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

Vec<T> 变成 VecDeque<T>

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

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

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

将该值输入给定的 HasherRead more

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

索引后返回的类型。

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

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

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

被迭代的元素的类型。

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

被迭代的元素的类型。

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

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

被迭代的元素的类型。

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

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

此方法返回 selfother 之间的 OrderingRead more

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

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

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

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

此方法测试 !=

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

此方法测试 !=

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

此方法测试 !=

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

此方法测试 !=

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

此方法测试 !=

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

此方法测试 !=

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

此方法测试 !=

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

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

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

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

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

Auto Trait Implementations

Blanket Implementations

获取 selfTypeIdRead more

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

从拥有的值中借用。 Read more

执行转换。

执行转换。

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

通常通过克隆从借用数据中创建拥有的数据。 Read more

🔬 This is a nightly-only experimental API. (toowned_clone_into #41263)

recently added

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

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

执行转换。

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

执行转换。