VecDeque in std::collections - Rust
source link: https://doc.rust-lang.org/stable/std/collections/struct.VecDeque.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
allocator_api
#32838)Creates an empty VecDeque
.
Examples
use std::collections::VecDeque;
let vector: VecDeque<u32> = VecDeque::new();
Runallocator_api
#32838)Creates an empty VecDeque
with space for at least capacity
elements.
Examples
use std::collections::VecDeque;
let vector: VecDeque<u32> = VecDeque::with_capacity(10);
RunProvides a reference to the element at the given index.
Element at index 0 is the front of the queue.
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));
RunProvides a mutable reference to the element at the given index.
Element at index 0 is the front of the queue.
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);
RunSwaps elements at indices i
and j
.
i
and j
may be equal.
Element at index 0 is the front of the queue.
Panics
Panics if either index is out of bounds.
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]);
RunReturns the number of elements the VecDeque
can hold without
reallocating.
Examples
use std::collections::VecDeque;
let buf: VecDeque<i32> = VecDeque::with_capacity(10);
assert!(buf.capacity() >= 10);
Runpub fn reserve_exact(&mut self, additional: usize)
Reserves the minimum capacity for exactly additional
more elements to be inserted in the
given VecDeque
. Does nothing if the capacity is already sufficient.
Note that the allocator may give the collection more space than it requests. Therefore
capacity can not be relied upon to be precisely minimal. Prefer reserve
if future
insertions are expected.
Panics
Panics if the new capacity overflows usize
.
Examples
use std::collections::VecDeque;
let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
buf.reserve_exact(10);
assert!(buf.capacity() >= 11);
RunReserves capacity for at least additional
more elements to be inserted in the given
VecDeque
. The collection may reserve more space to avoid frequent reallocations.
Panics
Panics if the new capacity overflows usize
.
Examples
use std::collections::VecDeque;
let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
buf.reserve(10);
assert!(buf.capacity() >= 11);
Runtry_reserve
#48043)Tries to reserve the minimum capacity for exactly additional
more elements to
be inserted in the given VecDeque<T>
. After calling try_reserve_exact
,
capacity will be greater than or equal to self.len() + additional
.
Does nothing if the capacity is already sufficient.
Note that the allocator may give the collection more space than it
requests. Therefore, capacity can not be relied upon to be precisely
minimal. Prefer reserve
if future insertions are expected.
Errors
If the capacity overflows usize
, or the allocator reports a failure, then an error
is returned.
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();
// Pre-reserve the memory, exiting if we can't
output.try_reserve_exact(data.len())?;
// Now we know this can't OOM(Out-Of-Memory) in the middle of our complex work
output.extend(data.iter().map(|&val| {
val * 2 + 5 // very complicated
}));
Ok(output)
}
Runtry_reserve
#48043)Tries to reserve capacity for at least additional
more elements to be inserted
in the given VecDeque<T>
. The collection may reserve more space to avoid
frequent reallocations. After calling try_reserve
, capacity will be
greater than or equal to self.len() + additional
. Does nothing if
capacity is already sufficient.
Errors
If the capacity overflows usize
, or the allocator reports a failure, then an error
is returned.
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();
// Pre-reserve the memory, exiting if we can't
output.try_reserve(data.len())?;
// Now we know this can't OOM in the middle of our complex work
output.extend(data.iter().map(|&val| {
val * 2 + 5 // very complicated
}));
Ok(output)
}
Runpub fn shrink_to_fit(&mut self)
Shrinks the capacity of the VecDeque
as much as possible.
It will drop down as close as possible to the length but the allocator may still inform the
VecDeque
that there is space for a few more elements.
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);
RunShrinks the capacity of the VecDeque
with a lower bound.
The capacity will remain at least as large as both the length and the supplied value.
If the current capacity is less than the lower limit, this is a no-op.
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);
RunShortens the VecDeque
, keeping the first len
elements and dropping
the rest.
If len
is greater than the VecDeque
’s current length, this has no
effect.
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]);
Runallocator_api
#32838)Returns a reference to the underlying allocator.
Returns a front-to-back iterator.
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);
RunReturns a front-to-back iterator that returns mutable references.
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);
RunReturns a pair of slices which contain, in order, the contents of the
VecDeque
.
If make_contiguous
was previously called, all elements of the
VecDeque
will be in the first slice and the second slice will be empty.
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][..]));
RunReturns a pair of slices which contain, in order, the contents of the
VecDeque
.
If make_contiguous
was previously called, all elements of the
VecDeque
will be in the first slice and the second slice will be empty.
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][..]));
RunReturns the number of elements in the 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);
RunReturns true
if the VecDeque
is empty.
Examples
use std::collections::VecDeque;
let mut v = VecDeque::new();
assert!(v.is_empty());
v.push_front(1);
assert!(!v.is_empty());
Runpub fn range<R>(&self, range: R) -> Iter<'_, T>ⓘ where
R: RangeBounds<usize>,
Creates an iterator that covers the specified range in the VecDeque
.
Panics
Panics if the starting point is greater than the end point or if the end point is greater than the length of the vector.
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]);
// A full range covers all contents
let all = v.range(..);
assert_eq!(all.len(), 3);
Runpub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T>ⓘ where
R: RangeBounds<usize>,
Creates an iterator that covers the specified mutable range in the VecDeque
.
Panics
Panics if the starting point is greater than the end point or if the end point is greater than the length of the vector.
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]);
// A full range covers all contents
for v in v.range_mut(..) {
*v *= 2;
}
assert_eq!(v, vec![2, 4, 12]);
Runpub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>ⓘ where
R: RangeBounds<usize>,
Creates a draining iterator that removes the specified range in the
VecDeque
and yields the removed items.
Note 1: The element range is removed even if the iterator is not consumed until the end.
Note 2: It is unspecified how many elements are removed from the deque,
if the Drain
value is not dropped, but the borrow it holds expires
(e.g., due to mem::forget
).
Panics
Panics if the starting point is greater than the end point or if the end point is greater than the length of the vector.
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]);
// A full range clears all contents
v.drain(..);
assert!(v.is_empty());
Runpub fn clear(&mut self)
Clears the VecDeque
, removing all values.
Examples
use std::collections::VecDeque;
let mut v = VecDeque::new();
v.push_back(1);
v.clear();
assert!(v.is_empty());
RunReturns true
if the VecDeque
contains an element equal to the
given value.
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);
RunProvides a reference to the front element, or None
if the VecDeque
is
empty.
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));
RunProvides a mutable reference to the front element, or None
if the
VecDeque
is empty.
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));
RunProvides a reference to the back element, or None
if the VecDeque
is
empty.
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));
RunProvides a mutable reference to the back element, or None
if the
VecDeque
is empty.
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));
RunRemoves the first element and returns it, or None
if the VecDeque
is
empty.
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);
RunRemoves the last element from the VecDeque
and returns it, or None
if
it is empty.
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));
Runpub fn push_front(&mut self, value: T)
Prepends an element to the 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));
Runpub fn push_back(&mut self, value: T)
Appends an element to the back of the 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());
RunRemoves an element from anywhere in the VecDeque
and returns it,
replacing it with the first element.
This does not preserve ordering, but is O(1).
Returns None
if index
is out of bounds.
Element at index 0 is the front of the queue.
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]);
RunRemoves an element from anywhere in the VecDeque
and returns it, replacing it with the
last element.
This does not preserve ordering, but is O(1).
Returns None
if index
is out of bounds.
Element at index 0 is the front of the queue.
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]);
RunInserts an element at index
within the VecDeque
, shifting all elements with indices
greater than or equal to index
towards the back.
Element at index 0 is the front of the queue.
Panics
Panics if index
is greater than VecDeque
’s length
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']);
RunRemoves and returns the element at index
from the VecDeque
.
Whichever end is closer to the removal point will be moved to make
room, and all the affected elements will be moved to new positions.
Returns None
if index
is out of bounds.
Element at index 0 is the front of the queue.
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]);
RunSplits the VecDeque
into two at the given index.
Returns a newly allocated VecDeque
. self
contains elements [0, at)
,
and the returned VecDeque
contains elements [at, len)
.
Note that the capacity of self
does not change.
Element at index 0 is the front of the queue.
Panics
Panics if at > len
.
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]);
RunMoves all the elements of other
into self
, leaving other
empty.
Panics
Panics if the new number of elements in self overflows a 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, []);
RunRetains only the elements specified by the predicate.
In other words, remove all elements e
such that f(&e)
returns false.
This method operates in place, visiting each element exactly once in the
original order, and preserves the order of the retained elements.
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]);
RunBecause the elements are visited exactly once in the original order, external state may be used to decide which elements to keep.
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]);
Runpub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T)
Modifies the VecDeque
in-place so that len()
is equal to new_len
,
either by removing excess elements from the back or by appending
elements generated by calling generator
to the back.
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]);
RunRearranges the internal storage of this deque so it is one contiguous slice, which is then returned.
This method does not allocate and does not change the order of the inserted elements. As it returns a mutable slice, this can be used to sort a deque.
Once the internal storage is contiguous, the as_slices
and
as_mut_slices
methods will return the entire contents of the
VecDeque
in a single slice.
Examples
Sorting the content of a deque.
use std::collections::VecDeque;
let mut buf = VecDeque::with_capacity(15);
buf.push_back(2);
buf.push_back(1);
buf.push_front(3);
// sorting the deque
buf.make_contiguous().sort();
assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));
// sorting it in reverse order
buf.make_contiguous().sort_by(|a, b| b.cmp(a));
assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));
RunGetting immutable access to the contiguous slice.
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() {
// we can now be sure that `slice` contains all elements of the deque,
// while still having immutable access to `buf`.
assert_eq!(buf.len(), slice.len());
assert_eq!(slice, &[3, 2, 1] as &[_]);
}
Runpub fn rotate_left(&mut self, mid: usize)
Rotates the double-ended queue mid
places to the left.
Equivalently,
- Rotates item
mid
into the first position. - Pops the first
mid
items and pushes them to the end. - Rotates
len() - mid
places to the right.
Panics
If mid
is greater than len()
. Note that mid == len()
does not panic and is a no-op rotation.
Complexity
Takes *O*(min(mid, len() - mid))
time and no extra space.
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]);
Runpub fn rotate_right(&mut self, k: usize)
Rotates the double-ended queue k
places to the right.
Equivalently,
- Rotates the first item into position
k
. - Pops the last
k
items and pushes them to the front. - Rotates
len() - k
places to the left.
Panics
If k
is greater than len()
. Note that k == len()
does not panic and is a no-op rotation.
Complexity
Takes *O*(min(k, len() - k))
time and no extra space.
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]);
RunBinary searches this sorted VecDeque
for a given element.
If the value is found then Result::Ok
is returned, containing the
index of the matching element. If there are multiple matches, then any
one of the matches could be returned. If the value is not found then
Result::Err
is returned, containing the index where a matching
element could be inserted while maintaining sorted order.
See also binary_search_by
, binary_search_by_key
, and partition_point
.
Examples
Looks up a series of four elements. The first is found, with a
uniquely determined position; the second and third are not
found; the fourth could match any position in [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)));
RunIf you want to insert an item to a sorted VecDeque
, while maintaining
sort order:
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]);
RunBinary searches this sorted VecDeque
with a comparator function.
The comparator function should implement an order consistent
with the sort order of the underlying VecDeque
, returning an
order code that indicates whether its argument is Less
,
Equal
or Greater
than the desired target.
If the value is found then Result::Ok
is returned, containing the
index of the matching element. If there are multiple matches, then any
one of the matches could be returned. If the value is not found then
Result::Err
is returned, containing the index where a matching
element could be inserted while maintaining sorted order.
See also binary_search
, binary_search_by_key
, and partition_point
.
Examples
Looks up a series of four elements. The first is found, with a
uniquely determined position; the second and third are not
found; the fourth could match any position in [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)));
Runpub 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 searches this sorted VecDeque
with a key extraction function.
Assumes that the VecDeque
is sorted by the key, for instance with
make_contiguous().sort_by_key()
using the same key extraction function.
If the value is found then Result::Ok
is returned, containing the
index of the matching element. If there are multiple matches, then any
one of the matches could be returned. If the value is not found then
Result::Err
is returned, containing the index where a matching
element could be inserted while maintaining sorted order.
See also binary_search
, binary_search_by
, and partition_point
.
Examples
Looks up a series of four elements in a slice of pairs sorted by
their second elements. The first is found, with a uniquely
determined position; the second and third are not found; the
fourth could match any position in [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)));
Runpub fn partition_point<P>(&self, pred: P) -> usize where
P: FnMut(&T) -> bool,
Returns the index of the partition point according to the given predicate (the index of the first element of the second partition).
The deque is assumed to be partitioned according to the given predicate. This means that all elements for which the predicate returns true are at the start of the deque and all elements for which the predicate returns false are at the end. For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0 (all odd numbers are at the start, all even at the end).
If this deque is not partitioned, the returned result is unspecified and meaningless, as this method performs a kind of binary search.
See also binary_search
, binary_search_by
, and 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)));
RunRecommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK