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
从队列中删除。
extend
和 append
以这种方式推到后面,并从前到后迭代 VecDeque
。
可以从数组初始化具有已知项列表的 VecDeque
:
use std::collections::VecDeque;
let deq = VecDeque::from([-1, 0, 1]);
Run由于 VecDeque
是环形缓冲区,因此它的元素在内存中不一定是连续的。
如果要以单个切片的形式访问元素 (例如为了进行有效的排序),则可以使用 make_contiguous
。
它旋转 VecDeque
,以使其元素不环绕,并向当前连续的元素序列返回可变切片。
Implementations§
source§impl<T, A: Allocator> VecDeque<T, A>
impl<T, A: Allocator> VecDeque<T, A>
sourcepub const fn new_in(alloc: A) -> VecDeque<T, A>
🔬This is a nightly-only experimental API. (allocator_api
#32838)
pub const fn new_in(alloc: A) -> VecDeque<T, A>
allocator_api
#32838)sourcepub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A>
🔬This is a nightly-only experimental API. (allocator_api
#32838)
pub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A>
allocator_api
#32838)sourcepub fn reserve_exact(&mut self, additional: usize)
pub fn reserve_exact(&mut self, additional: usize)
1.57.0 · sourcepub fn try_reserve_exact(
&mut self,
additional: usize
) -> Result<(), TryReserveError>
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)
}
Run1.57.0 · sourcepub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>
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)
}
Run1.5.0 · sourcepub fn shrink_to_fit(&mut self)
pub fn shrink_to_fit(&mut self)
sourcepub fn allocator(&self) -> &A
🔬This is a nightly-only experimental API. (allocator_api
#32838)
pub fn allocator(&self) -> &A
allocator_api
#32838)返回底层分配器的引用。
sourcepub fn iter_mut(&mut self) -> IterMut<'_, T> ⓘ
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);
Run1.5.0 · sourcepub fn as_slices(&self) -> (&[T], &[T])
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][..]));
Run1.5.0 · sourcepub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T])
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][..]));
Run1.51.0 · sourcepub fn range<R>(&self, range: R) -> Iter<'_, T> ⓘwhere
R: RangeBounds<usize>,
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);
Run1.51.0 · sourcepub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T> ⓘwhere
R: RangeBounds<usize>,
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]);
Run1.6.0 · sourcepub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A> ⓘwhere
R: RangeBounds<usize>,
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());
Run1.12.0 · sourcepub fn contains(&self, x: &T) -> boolwhere
T: PartialEq<T>,
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);
Runsourcepub fn push_front(&mut self, value: T)
pub fn push_front(&mut self, value: T)
1.5.0 · sourcepub fn swap_remove_front(&mut self, index: usize) -> Option<T>
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]);
Run1.5.0 · sourcepub fn swap_remove_back(&mut self, index: usize) -> Option<T>
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]);
Run1.5.0 · sourcepub fn insert(&mut self, index: usize, value: T)
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']);
Runsourcepub fn remove(&mut self, index: usize) -> Option<T>
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]);
Run1.4.0 · sourcepub fn split_off(&mut self, at: usize) -> Selfwhere
A: Clone,
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]);
Run1.4.0 · sourcepub fn retain<F>(&mut self, f: F)where
F: FnMut(&T) -> bool,
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]);
Run1.61.0 · sourcepub fn retain_mut<F>(&mut self, f: F)where
F: FnMut(&mut T) -> bool,
pub fn retain_mut<F>(&mut self, f: F)where F: FnMut(&mut T) -> bool,
1.33.0 · sourcepub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T)
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]);
Run1.48.0 · sourcepub fn make_contiguous(&mut self) -> &mut [T]
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 &[_]));
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 &[_]);
}
Run1.36.0 · sourcepub fn rotate_left(&mut self, mid: usize)
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]);
Run1.36.0 · sourcepub fn rotate_right(&mut self, k: usize)
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]);
Run1.54.0 · sourcepub fn binary_search(&self, x: &T) -> Result<usize, usize>where
T: Ord,
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)));
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]);
Run1.54.0 · sourcepub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>where
F: FnMut(&'a T) -> Ordering,
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)));
Run1.54.0 · sourcepub 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,
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)));
Run1.54.0 · sourcepub fn partition_point<P>(&self, pred: P) -> usizewhere
P: FnMut(&T) -> bool,
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)));
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]);
Runsource§impl<T: Clone, A: Allocator> VecDeque<T, A>
impl<T: Clone, A: Allocator> VecDeque<T, A>
1.16.0 · sourcepub fn resize(&mut self, new_len: usize, value: T)
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]);
RunTrait Implementations§
1.2.0 · source§impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A>
impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A>
source§fn extend_one(&mut self, elem: &'a T)
fn extend_one(&mut self, elem: &'a T)
extend_one
#72631)source§impl<T, A: Allocator> Extend<T> for VecDeque<T, A>
impl<T, A: Allocator> Extend<T> for VecDeque<T, A>
source§fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
source§fn extend_one(&mut self, elem: T)
fn extend_one(&mut self, elem: T)
extend_one
#72631)1.10.0 · source§impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A>
impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A>
source§fn from(other: VecDeque<T, A>) -> Self
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