1 //! A double-ended queue (deque) implemented with a growable ring buffer.
3 //! This queue has *O*(1) amortized inserts and removals from both ends of the
4 //! container. It also has *O*(1) indexing like a vector. The contained elements
5 //! are not required to be copyable, and the queue will be sendable if the
6 //! contained type is sendable.
8 #![stable(feature = "rust1", since = "1.0.0")]
10 use core::cmp::{self, Ordering};
12 use core::hash::{Hash, Hasher};
13 use core::iter::{repeat_n, repeat_with, ByRefSized, FromIterator};
14 use core::mem::{ManuallyDrop, SizedTypeProperties};
15 use core::ops::{Index, IndexMut, Range, RangeBounds};
19 // This is used in a bunch of intra-doc links.
20 // FIXME: For some reason, `#[cfg(doc)]` wasn't sufficient, resulting in
21 // failures in linkchecker even though rustdoc built the docs just fine.
22 #[allow(unused_imports)]
25 use crate::alloc::{Allocator, Global};
26 use crate::collections::TryReserveError;
27 use crate::collections::TryReserveErrorKind;
28 use crate::raw_vec::RawVec;
34 #[stable(feature = "drain", since = "1.6.0")]
35 pub use self::drain::Drain;
39 #[stable(feature = "rust1", since = "1.0.0")]
40 pub use self::iter_mut::IterMut;
44 #[stable(feature = "rust1", since = "1.0.0")]
45 pub use self::into_iter::IntoIter;
49 #[stable(feature = "rust1", since = "1.0.0")]
50 pub use self::iter::Iter;
54 use self::spec_extend::SpecExtend;
58 use self::spec_from_iter::SpecFromIter;
65 /// A double-ended queue implemented with a growable ring buffer.
67 /// The "default" usage of this type as a queue is to use [`push_back`] to add to
68 /// the queue, and [`pop_front`] to remove from the queue. [`extend`] and [`append`]
69 /// push onto the back in this manner, and iterating over `VecDeque` goes front
72 /// A `VecDeque` with a known list of items can be initialized from an array:
75 /// use std::collections::VecDeque;
77 /// let deq = VecDeque::from([-1, 0, 1]);
80 /// Since `VecDeque` is a ring buffer, its elements are not necessarily contiguous
81 /// in memory. If you want to access the elements as a single slice, such as for
82 /// efficient sorting, you can use [`make_contiguous`]. It rotates the `VecDeque`
83 /// so that its elements do not wrap, and returns a mutable slice to the
84 /// now-contiguous element sequence.
86 /// [`push_back`]: VecDeque::push_back
87 /// [`pop_front`]: VecDeque::pop_front
88 /// [`extend`]: VecDeque::extend
89 /// [`append`]: VecDeque::append
90 /// [`make_contiguous`]: VecDeque::make_contiguous
91 #[cfg_attr(not(test), rustc_diagnostic_item = "VecDeque")]
92 #[stable(feature = "rust1", since = "1.0.0")]
93 #[rustc_insignificant_dtor]
96 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
98 // `self[0]`, if it exists, is `buf[head]`.
99 // `head < buf.capacity()`, unless `buf.capacity() == 0` when `head == 0`.
101 // the number of initialized elements, starting from the one at `head` and potentially wrapping around.
102 // if `len == 0`, the exact value of `head` is unimportant.
103 // if `T` is zero-Sized, then `self.len <= usize::MAX`, otherwise `self.len <= isize::MAX as usize`.
108 #[stable(feature = "rust1", since = "1.0.0")]
109 impl<T: Clone, A: Allocator + Clone> Clone for VecDeque<T, A> {
110 fn clone(&self) -> Self {
111 let mut deq = Self::with_capacity_in(self.len(), self.allocator().clone());
112 deq.extend(self.iter().cloned());
116 fn clone_from(&mut self, other: &Self) {
118 self.extend(other.iter().cloned());
122 #[stable(feature = "rust1", since = "1.0.0")]
123 unsafe impl<#[may_dangle] T, A: Allocator> Drop for VecDeque<T, A> {
125 /// Runs the destructor for all items in the slice when it gets dropped (normally or
126 /// during unwinding).
127 struct Dropper<'a, T>(&'a mut [T]);
129 impl<'a, T> Drop for Dropper<'a, T> {
132 ptr::drop_in_place(self.0);
137 let (front, back) = self.as_mut_slices();
139 let _back_dropper = Dropper(back);
141 ptr::drop_in_place(front);
143 // RawVec handles deallocation
147 #[stable(feature = "rust1", since = "1.0.0")]
148 impl<T> Default for VecDeque<T> {
149 /// Creates an empty deque.
151 fn default() -> VecDeque<T> {
156 impl<T, A: Allocator> VecDeque<T, A> {
157 /// Marginally more convenient
159 fn ptr(&self) -> *mut T {
163 /// Moves an element out of the buffer
165 unsafe fn buffer_read(&mut self, off: usize) -> T {
166 unsafe { ptr::read(self.ptr().add(off)) }
169 /// Writes an element into the buffer, moving it.
171 unsafe fn buffer_write(&mut self, off: usize, value: T) {
173 ptr::write(self.ptr().add(off), value);
177 /// Returns a slice pointer into the buffer.
178 /// `range` must lie inside `0..self.capacity()`.
180 unsafe fn buffer_range(&self, range: Range<usize>) -> *mut [T] {
182 ptr::slice_from_raw_parts_mut(self.ptr().add(range.start), range.end - range.start)
186 /// Returns `true` if the buffer is at full capacity.
188 fn is_full(&self) -> bool {
189 self.len == self.capacity()
192 /// Returns the index in the underlying buffer for a given logical element
195 fn wrap_add(&self, idx: usize, addend: usize) -> usize {
196 wrap_index(idx.wrapping_add(addend), self.capacity())
200 fn to_physical_idx(&self, idx: usize) -> usize {
201 self.wrap_add(self.head, idx)
204 /// Returns the index in the underlying buffer for a given logical element
205 /// index - subtrahend.
207 fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize {
208 wrap_index(idx.wrapping_sub(subtrahend).wrapping_add(self.capacity()), self.capacity())
211 /// Copies a contiguous block of memory len long from src to dst
213 unsafe fn copy(&mut self, src: usize, dst: usize, len: usize) {
215 dst + len <= self.capacity(),
216 "cpy dst={} src={} len={} cap={}",
223 src + len <= self.capacity(),
224 "cpy dst={} src={} len={} cap={}",
231 ptr::copy(self.ptr().add(src), self.ptr().add(dst), len);
235 /// Copies a contiguous block of memory len long from src to dst
237 unsafe fn copy_nonoverlapping(&mut self, src: usize, dst: usize, len: usize) {
239 dst + len <= self.capacity(),
240 "cno dst={} src={} len={} cap={}",
247 src + len <= self.capacity(),
248 "cno dst={} src={} len={} cap={}",
255 ptr::copy_nonoverlapping(self.ptr().add(src), self.ptr().add(dst), len);
259 /// Copies a potentially wrapping block of memory len long from src to dest.
260 /// (abs(dst - src) + len) must be no larger than capacity() (There must be at
261 /// most one continuous overlapping region between src and dest).
262 unsafe fn wrap_copy(&mut self, src: usize, dst: usize, len: usize) {
264 cmp::min(src.abs_diff(dst), self.capacity() - src.abs_diff(dst)) + len
266 "wrc dst={} src={} len={} cap={}",
273 // If T is a ZST, don't do any copying.
274 if T::IS_ZST || src == dst || len == 0 {
278 let dst_after_src = self.wrap_sub(dst, src) < len;
280 let src_pre_wrap_len = self.capacity() - src;
281 let dst_pre_wrap_len = self.capacity() - dst;
282 let src_wraps = src_pre_wrap_len < len;
283 let dst_wraps = dst_pre_wrap_len < len;
285 match (dst_after_src, src_wraps, dst_wraps) {
286 (_, false, false) => {
287 // src doesn't wrap, dst doesn't wrap
290 // 1 [_ _ A A B B C C _]
291 // 2 [_ _ A A A A B B _]
295 self.copy(src, dst, len);
298 (false, false, true) => {
299 // dst before src, src doesn't wrap, dst wraps
302 // 1 [A A B B _ _ _ C C]
303 // 2 [A A B B _ _ _ A A]
304 // 3 [B B B B _ _ _ A A]
308 self.copy(src, dst, dst_pre_wrap_len);
309 self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len);
312 (true, false, true) => {
313 // src before dst, src doesn't wrap, dst wraps
316 // 1 [C C _ _ _ A A B B]
317 // 2 [B B _ _ _ A A B B]
318 // 3 [B B _ _ _ A A A A]
322 self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len);
323 self.copy(src, dst, dst_pre_wrap_len);
326 (false, true, false) => {
327 // dst before src, src wraps, dst doesn't wrap
330 // 1 [C C _ _ _ A A B B]
331 // 2 [C C _ _ _ B B B B]
332 // 3 [C C _ _ _ B B C C]
336 self.copy(src, dst, src_pre_wrap_len);
337 self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len);
340 (true, true, false) => {
341 // src before dst, src wraps, dst doesn't wrap
344 // 1 [A A B B _ _ _ C C]
345 // 2 [A A A A _ _ _ C C]
346 // 3 [C C A A _ _ _ C C]
350 self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len);
351 self.copy(src, dst, src_pre_wrap_len);
354 (false, true, true) => {
355 // dst before src, src wraps, dst wraps
358 // 1 [A B C D _ E F G H]
359 // 2 [A B C D _ E G H H]
360 // 3 [A B C D _ E G H A]
361 // 4 [B C C D _ E G H A]
364 debug_assert!(dst_pre_wrap_len > src_pre_wrap_len);
365 let delta = dst_pre_wrap_len - src_pre_wrap_len;
367 self.copy(src, dst, src_pre_wrap_len);
368 self.copy(0, dst + src_pre_wrap_len, delta);
369 self.copy(delta, 0, len - dst_pre_wrap_len);
372 (true, true, true) => {
373 // src before dst, src wraps, dst wraps
376 // 1 [A B C D _ E F G H]
377 // 2 [A A B D _ E F G H]
378 // 3 [H A B D _ E F G H]
379 // 4 [H A B D _ E F F G]
382 debug_assert!(src_pre_wrap_len > dst_pre_wrap_len);
383 let delta = src_pre_wrap_len - dst_pre_wrap_len;
385 self.copy(0, delta, len - src_pre_wrap_len);
386 self.copy(self.capacity() - delta, 0, delta);
387 self.copy(src, dst, dst_pre_wrap_len);
393 /// Copies all values from `src` to `dst`, wrapping around if needed.
394 /// Assumes capacity is sufficient.
396 unsafe fn copy_slice(&mut self, dst: usize, src: &[T]) {
397 debug_assert!(src.len() <= self.capacity());
398 let head_room = self.capacity() - dst;
399 if src.len() <= head_room {
401 ptr::copy_nonoverlapping(src.as_ptr(), self.ptr().add(dst), src.len());
404 let (left, right) = src.split_at(head_room);
406 ptr::copy_nonoverlapping(left.as_ptr(), self.ptr().add(dst), left.len());
407 ptr::copy_nonoverlapping(right.as_ptr(), self.ptr(), right.len());
412 /// Writes all values from `iter` to `dst`.
416 /// Assumes no wrapping around happens.
417 /// Assumes capacity is sufficient.
419 unsafe fn write_iter(
422 iter: impl Iterator<Item = T>,
425 iter.enumerate().for_each(|(i, element)| unsafe {
426 self.buffer_write(dst + i, element);
431 /// Writes all values from `iter` to `dst`, wrapping
432 /// at the end of the buffer and returns the number
433 /// of written values.
437 /// Assumes that `iter` yields at most `len` items.
438 /// Assumes capacity is sufficient.
439 unsafe fn write_iter_wrapping(
442 mut iter: impl Iterator<Item = T>,
445 struct Guard<'a, T, A: Allocator> {
446 deque: &'a mut VecDeque<T, A>,
450 impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> {
452 self.deque.len += self.written;
456 let head_room = self.capacity() - dst;
458 let mut guard = Guard { deque: self, written: 0 };
460 if head_room >= len {
461 unsafe { guard.deque.write_iter(dst, iter, &mut guard.written) };
464 guard.deque.write_iter(
466 ByRefSized(&mut iter).take(head_room),
469 guard.deque.write_iter(0, iter, &mut guard.written)
476 /// Frobs the head and tail sections around to handle the fact that we
477 /// just reallocated. Unsafe because it trusts old_capacity.
479 unsafe fn handle_capacity_increase(&mut self, old_capacity: usize) {
480 let new_capacity = self.capacity();
481 debug_assert!(new_capacity >= old_capacity);
483 // Move the shortest contiguous section of the ring buffer
486 // L := last element (`self.to_physical_idx(self.len - 1)`)
489 // [o o o o o o o . ]
491 // A [o o o o o o o . . . . . . . . . ]
493 // [o o o o o o o o ]
495 // B [. . . o o o o o o o . . . . . . ]
497 // [o o o o o o o o ]
499 // C [o o o o o . . . . . . . . . o o ]
501 // can't use is_contiguous() because the capacity is already updated.
502 if self.head <= old_capacity - self.len {
506 let head_len = old_capacity - self.head;
507 let tail_len = self.len - head_len;
508 if head_len > tail_len && new_capacity - old_capacity >= tail_len {
511 self.copy_nonoverlapping(0, old_capacity, tail_len);
515 let new_head = new_capacity - head_len;
517 // can't use copy_nonoverlapping here, because if e.g. head_len = 2
518 // and new_capacity = old_capacity + 1, then the heads overlap.
519 self.copy(self.head, new_head, head_len);
521 self.head = new_head;
524 debug_assert!(self.head < self.capacity() || self.capacity() == 0);
528 impl<T> VecDeque<T> {
529 /// Creates an empty deque.
534 /// use std::collections::VecDeque;
536 /// let deque: VecDeque<u32> = VecDeque::new();
539 #[stable(feature = "rust1", since = "1.0.0")]
540 #[rustc_const_stable(feature = "const_vec_deque_new", since = "1.68.0")]
542 pub const fn new() -> VecDeque<T> {
543 // FIXME: This should just be `VecDeque::new_in(Global)` once that hits stable.
544 VecDeque { head: 0, len: 0, buf: RawVec::NEW }
547 /// Creates an empty deque with space for at least `capacity` elements.
552 /// use std::collections::VecDeque;
554 /// let deque: VecDeque<u32> = VecDeque::with_capacity(10);
557 #[stable(feature = "rust1", since = "1.0.0")]
559 pub fn with_capacity(capacity: usize) -> VecDeque<T> {
560 Self::with_capacity_in(capacity, Global)
564 impl<T, A: Allocator> VecDeque<T, A> {
565 /// Creates an empty deque.
570 /// use std::collections::VecDeque;
572 /// let deque: VecDeque<u32> = VecDeque::new();
575 #[unstable(feature = "allocator_api", issue = "32838")]
576 pub const fn new_in(alloc: A) -> VecDeque<T, A> {
577 VecDeque { head: 0, len: 0, buf: RawVec::new_in(alloc) }
580 /// Creates an empty deque with space for at least `capacity` elements.
585 /// use std::collections::VecDeque;
587 /// let deque: VecDeque<u32> = VecDeque::with_capacity(10);
589 #[unstable(feature = "allocator_api", issue = "32838")]
590 pub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A> {
591 VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) }
594 /// Creates a `VecDeque` from a raw allocation, when the initialized
595 /// part of that allocation forms a *contiguous* subslice thereof.
597 /// For use by `vec::IntoIter::into_vecdeque`
601 /// All the usual requirements on the allocated memory like in
602 /// `Vec::from_raw_parts_in`, but takes a *range* of elements that are
603 /// initialized rather than only supporting `0..len`. Requires that
604 /// `initialized.start` ≤ `initialized.end` ≤ `capacity`.
606 pub(crate) unsafe fn from_contiguous_raw_parts_in(
608 initialized: Range<usize>,
612 debug_assert!(initialized.start <= initialized.end);
613 debug_assert!(initialized.end <= capacity);
615 // SAFETY: Our safety precondition guarantees the range length won't wrap,
616 // and that the allocation is valid for use in `RawVec`.
619 head: initialized.start,
620 len: initialized.end.unchecked_sub(initialized.start),
621 buf: RawVec::from_raw_parts_in(ptr, capacity, alloc),
626 /// Provides a reference to the element at the given index.
628 /// Element at index 0 is the front of the queue.
633 /// use std::collections::VecDeque;
635 /// let mut buf = VecDeque::new();
636 /// buf.push_back(3);
637 /// buf.push_back(4);
638 /// buf.push_back(5);
639 /// buf.push_back(6);
640 /// assert_eq!(buf.get(1), Some(&4));
642 #[stable(feature = "rust1", since = "1.0.0")]
643 pub fn get(&self, index: usize) -> Option<&T> {
644 if index < self.len {
645 let idx = self.to_physical_idx(index);
646 unsafe { Some(&*self.ptr().add(idx)) }
652 /// Provides a mutable reference to the element at the given index.
654 /// Element at index 0 is the front of the queue.
659 /// use std::collections::VecDeque;
661 /// let mut buf = VecDeque::new();
662 /// buf.push_back(3);
663 /// buf.push_back(4);
664 /// buf.push_back(5);
665 /// buf.push_back(6);
666 /// assert_eq!(buf[1], 4);
667 /// if let Some(elem) = buf.get_mut(1) {
670 /// assert_eq!(buf[1], 7);
672 #[stable(feature = "rust1", since = "1.0.0")]
673 pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
674 if index < self.len {
675 let idx = self.to_physical_idx(index);
676 unsafe { Some(&mut *self.ptr().add(idx)) }
682 /// Swaps elements at indices `i` and `j`.
684 /// `i` and `j` may be equal.
686 /// Element at index 0 is the front of the queue.
690 /// Panics if either index is out of bounds.
695 /// use std::collections::VecDeque;
697 /// let mut buf = VecDeque::new();
698 /// buf.push_back(3);
699 /// buf.push_back(4);
700 /// buf.push_back(5);
701 /// assert_eq!(buf, [3, 4, 5]);
703 /// assert_eq!(buf, [5, 4, 3]);
705 #[stable(feature = "rust1", since = "1.0.0")]
706 pub fn swap(&mut self, i: usize, j: usize) {
707 assert!(i < self.len());
708 assert!(j < self.len());
709 let ri = self.to_physical_idx(i);
710 let rj = self.to_physical_idx(j);
711 unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) }
714 /// Returns the number of elements the deque can hold without
720 /// use std::collections::VecDeque;
722 /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
723 /// assert!(buf.capacity() >= 10);
726 #[stable(feature = "rust1", since = "1.0.0")]
727 pub fn capacity(&self) -> usize {
728 if T::IS_ZST { usize::MAX } else { self.buf.capacity() }
731 /// Reserves the minimum capacity for at least `additional` more elements to be inserted in the
732 /// given deque. Does nothing if the capacity is already sufficient.
734 /// Note that the allocator may give the collection more space than it requests. Therefore
735 /// capacity can not be relied upon to be precisely minimal. Prefer [`reserve`] if future
736 /// insertions are expected.
740 /// Panics if the new capacity overflows `usize`.
745 /// use std::collections::VecDeque;
747 /// let mut buf: VecDeque<i32> = [1].into();
748 /// buf.reserve_exact(10);
749 /// assert!(buf.capacity() >= 11);
752 /// [`reserve`]: VecDeque::reserve
753 #[stable(feature = "rust1", since = "1.0.0")]
754 pub fn reserve_exact(&mut self, additional: usize) {
755 let new_cap = self.len.checked_add(additional).expect("capacity overflow");
756 let old_cap = self.capacity();
758 if new_cap > old_cap {
759 self.buf.reserve_exact(self.len, additional);
761 self.handle_capacity_increase(old_cap);
766 /// Reserves capacity for at least `additional` more elements to be inserted in the given
767 /// deque. The collection may reserve more space to speculatively avoid frequent reallocations.
771 /// Panics if the new capacity overflows `usize`.
776 /// use std::collections::VecDeque;
778 /// let mut buf: VecDeque<i32> = [1].into();
780 /// assert!(buf.capacity() >= 11);
782 #[stable(feature = "rust1", since = "1.0.0")]
783 pub fn reserve(&mut self, additional: usize) {
784 let new_cap = self.len.checked_add(additional).expect("capacity overflow");
785 let old_cap = self.capacity();
787 if new_cap > old_cap {
788 // we don't need to reserve_exact(), as the size doesn't have
789 // to be a power of 2.
790 self.buf.reserve(self.len, additional);
792 self.handle_capacity_increase(old_cap);
797 /// Tries to reserve the minimum capacity for at least `additional` more elements to
798 /// be inserted in the given deque. After calling `try_reserve_exact`,
799 /// capacity will be greater than or equal to `self.len() + additional` if
800 /// it returns `Ok(())`. Does nothing if the capacity is already sufficient.
802 /// Note that the allocator may give the collection more space than it
803 /// requests. Therefore, capacity can not be relied upon to be precisely
804 /// minimal. Prefer [`try_reserve`] if future insertions are expected.
806 /// [`try_reserve`]: VecDeque::try_reserve
810 /// If the capacity overflows `usize`, or the allocator reports a failure, then an error
816 /// use std::collections::TryReserveError;
817 /// use std::collections::VecDeque;
819 /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
820 /// let mut output = VecDeque::new();
822 /// // Pre-reserve the memory, exiting if we can't
823 /// output.try_reserve_exact(data.len())?;
825 /// // Now we know this can't OOM(Out-Of-Memory) in the middle of our complex work
826 /// output.extend(data.iter().map(|&val| {
827 /// val * 2 + 5 // very complicated
832 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
834 #[stable(feature = "try_reserve", since = "1.57.0")]
835 pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
837 self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?;
838 let old_cap = self.capacity();
840 if new_cap > old_cap {
841 self.buf.try_reserve_exact(self.len, additional)?;
843 self.handle_capacity_increase(old_cap);
849 /// Tries to reserve capacity for at least `additional` more elements to be inserted
850 /// in the given deque. The collection may reserve more space to speculatively avoid
851 /// frequent reallocations. After calling `try_reserve`, capacity will be
852 /// greater than or equal to `self.len() + additional` if it returns
853 /// `Ok(())`. Does nothing if capacity is already sufficient. This method
854 /// preserves the contents even if an error occurs.
858 /// If the capacity overflows `usize`, or the allocator reports a failure, then an error
864 /// use std::collections::TryReserveError;
865 /// use std::collections::VecDeque;
867 /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
868 /// let mut output = VecDeque::new();
870 /// // Pre-reserve the memory, exiting if we can't
871 /// output.try_reserve(data.len())?;
873 /// // Now we know this can't OOM in the middle of our complex work
874 /// output.extend(data.iter().map(|&val| {
875 /// val * 2 + 5 // very complicated
880 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
882 #[stable(feature = "try_reserve", since = "1.57.0")]
883 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
885 self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?;
886 let old_cap = self.capacity();
888 if new_cap > old_cap {
889 self.buf.try_reserve(self.len, additional)?;
891 self.handle_capacity_increase(old_cap);
897 /// Shrinks the capacity of the deque as much as possible.
899 /// It will drop down as close as possible to the length but the allocator may still inform the
900 /// deque that there is space for a few more elements.
905 /// use std::collections::VecDeque;
907 /// let mut buf = VecDeque::with_capacity(15);
908 /// buf.extend(0..4);
909 /// assert_eq!(buf.capacity(), 15);
910 /// buf.shrink_to_fit();
911 /// assert!(buf.capacity() >= 4);
913 #[stable(feature = "deque_extras_15", since = "1.5.0")]
914 pub fn shrink_to_fit(&mut self) {
918 /// Shrinks the capacity of the deque with a lower bound.
920 /// The capacity will remain at least as large as both the length
921 /// and the supplied value.
923 /// If the current capacity is less than the lower limit, this is a no-op.
928 /// use std::collections::VecDeque;
930 /// let mut buf = VecDeque::with_capacity(15);
931 /// buf.extend(0..4);
932 /// assert_eq!(buf.capacity(), 15);
933 /// buf.shrink_to(6);
934 /// assert!(buf.capacity() >= 6);
935 /// buf.shrink_to(0);
936 /// assert!(buf.capacity() >= 4);
938 #[stable(feature = "shrink_to", since = "1.56.0")]
939 pub fn shrink_to(&mut self, min_capacity: usize) {
940 let target_cap = min_capacity.max(self.len);
943 if T::IS_ZST || self.capacity() <= target_cap {
947 if target_cap < self.capacity() {
948 // There are three cases of interest:
949 // All elements are out of desired bounds
950 // Elements are contiguous, and head is out of desired bounds
951 // Elements are discontiguous, and tail is out of desired bounds
953 // At all other times, element positions are unaffected.
955 // Indicates that elements at the head should be moved.
957 let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len));
958 // Move elements from out of desired bounds (positions after target_cap)
961 } else if self.head >= target_cap && tail_outside {
965 // [. . . . . . . . o o o o o o o . ]
967 // [o o o o o o o . ]
969 // nonoverlapping because self.head >= target_cap >= self.len
970 self.copy_nonoverlapping(self.head, 0, self.len);
973 } else if self.head < target_cap && tail_outside {
977 // [. . . o o o o o o o . . . . . . ]
979 // [o o . o o o o o ]
980 let len = self.head + self.len - target_cap;
982 self.copy_nonoverlapping(target_cap, 0, len);
984 } else if self.head >= target_cap {
988 // [o o o o o . . . . . . . . . o o ]
990 // [o o o o o . o o ]
991 let len = self.capacity() - self.head;
992 let new_head = target_cap - len;
994 // can't use copy_nonoverlapping here for the same reason
995 // as in `handle_capacity_increase()`
996 self.copy(self.head, new_head, len);
998 self.head = new_head;
1001 self.buf.shrink_to_fit(target_cap);
1003 debug_assert!(self.head < self.capacity() || self.capacity() == 0);
1004 debug_assert!(self.len <= self.capacity());
1008 /// Shortens the deque, keeping the first `len` elements and dropping
1011 /// If `len` is greater than the deque's current length, this has no
1017 /// use std::collections::VecDeque;
1019 /// let mut buf = VecDeque::new();
1020 /// buf.push_back(5);
1021 /// buf.push_back(10);
1022 /// buf.push_back(15);
1023 /// assert_eq!(buf, [5, 10, 15]);
1024 /// buf.truncate(1);
1025 /// assert_eq!(buf, [5]);
1027 #[stable(feature = "deque_extras", since = "1.16.0")]
1028 pub fn truncate(&mut self, len: usize) {
1029 /// Runs the destructor for all items in the slice when it gets dropped (normally or
1030 /// during unwinding).
1031 struct Dropper<'a, T>(&'a mut [T]);
1033 impl<'a, T> Drop for Dropper<'a, T> {
1034 fn drop(&mut self) {
1036 ptr::drop_in_place(self.0);
1043 // * Any slice passed to `drop_in_place` is valid; the second case has
1044 // `len <= front.len()` and returning on `len > self.len()` ensures
1045 // `begin <= back.len()` in the first case
1046 // * The head of the VecDeque is moved before calling `drop_in_place`,
1047 // so no value is dropped twice if `drop_in_place` panics
1049 if len >= self.len {
1053 let (front, back) = self.as_mut_slices();
1054 if len > front.len() {
1055 let begin = len - front.len();
1056 let drop_back = back.get_unchecked_mut(begin..) as *mut _;
1058 ptr::drop_in_place(drop_back);
1060 let drop_back = back as *mut _;
1061 let drop_front = front.get_unchecked_mut(len..) as *mut _;
1064 // Make sure the second half is dropped even when a destructor
1065 // in the first one panics.
1066 let _back_dropper = Dropper(&mut *drop_back);
1067 ptr::drop_in_place(drop_front);
1072 /// Returns a reference to the underlying allocator.
1073 #[unstable(feature = "allocator_api", issue = "32838")]
1075 pub fn allocator(&self) -> &A {
1076 self.buf.allocator()
1079 /// Returns a front-to-back iterator.
1084 /// use std::collections::VecDeque;
1086 /// let mut buf = VecDeque::new();
1087 /// buf.push_back(5);
1088 /// buf.push_back(3);
1089 /// buf.push_back(4);
1090 /// let b: &[_] = &[&5, &3, &4];
1091 /// let c: Vec<&i32> = buf.iter().collect();
1092 /// assert_eq!(&c[..], b);
1094 #[stable(feature = "rust1", since = "1.0.0")]
1095 pub fn iter(&self) -> Iter<'_, T> {
1096 let (a, b) = self.as_slices();
1097 Iter::new(a.iter(), b.iter())
1100 /// Returns a front-to-back iterator that returns mutable references.
1105 /// use std::collections::VecDeque;
1107 /// let mut buf = VecDeque::new();
1108 /// buf.push_back(5);
1109 /// buf.push_back(3);
1110 /// buf.push_back(4);
1111 /// for num in buf.iter_mut() {
1112 /// *num = *num - 2;
1114 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
1115 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
1117 #[stable(feature = "rust1", since = "1.0.0")]
1118 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
1119 let (a, b) = self.as_mut_slices();
1120 IterMut::new(a.iter_mut(), b.iter_mut())
1123 /// Returns a pair of slices which contain, in order, the contents of the
1126 /// If [`make_contiguous`] was previously called, all elements of the
1127 /// deque will be in the first slice and the second slice will be empty.
1129 /// [`make_contiguous`]: VecDeque::make_contiguous
1134 /// use std::collections::VecDeque;
1136 /// let mut deque = VecDeque::new();
1138 /// deque.push_back(0);
1139 /// deque.push_back(1);
1140 /// deque.push_back(2);
1142 /// assert_eq!(deque.as_slices(), (&[0, 1, 2][..], &[][..]));
1144 /// deque.push_front(10);
1145 /// deque.push_front(9);
1147 /// assert_eq!(deque.as_slices(), (&[9, 10][..], &[0, 1, 2][..]));
1150 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1151 pub fn as_slices(&self) -> (&[T], &[T]) {
1152 let (a_range, b_range) = self.slice_ranges(..);
1153 // SAFETY: `slice_ranges` always returns valid ranges into
1154 // the physical buffer.
1155 unsafe { (&*self.buffer_range(a_range), &*self.buffer_range(b_range)) }
1158 /// Returns a pair of slices which contain, in order, the contents of the
1161 /// If [`make_contiguous`] was previously called, all elements of the
1162 /// deque will be in the first slice and the second slice will be empty.
1164 /// [`make_contiguous`]: VecDeque::make_contiguous
1169 /// use std::collections::VecDeque;
1171 /// let mut deque = VecDeque::new();
1173 /// deque.push_back(0);
1174 /// deque.push_back(1);
1176 /// deque.push_front(10);
1177 /// deque.push_front(9);
1179 /// deque.as_mut_slices().0[0] = 42;
1180 /// deque.as_mut_slices().1[0] = 24;
1181 /// assert_eq!(deque.as_slices(), (&[42, 10][..], &[24, 1][..]));
1184 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1185 pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
1186 let (a_range, b_range) = self.slice_ranges(..);
1187 // SAFETY: `slice_ranges` always returns valid ranges into
1188 // the physical buffer.
1189 unsafe { (&mut *self.buffer_range(a_range), &mut *self.buffer_range(b_range)) }
1192 /// Returns the number of elements in the deque.
1197 /// use std::collections::VecDeque;
1199 /// let mut deque = VecDeque::new();
1200 /// assert_eq!(deque.len(), 0);
1201 /// deque.push_back(1);
1202 /// assert_eq!(deque.len(), 1);
1204 #[stable(feature = "rust1", since = "1.0.0")]
1205 pub fn len(&self) -> usize {
1209 /// Returns `true` if the deque is empty.
1214 /// use std::collections::VecDeque;
1216 /// let mut deque = VecDeque::new();
1217 /// assert!(deque.is_empty());
1218 /// deque.push_front(1);
1219 /// assert!(!deque.is_empty());
1221 #[stable(feature = "rust1", since = "1.0.0")]
1222 pub fn is_empty(&self) -> bool {
1226 /// Given a range into the logical buffer of the deque, this function
1227 /// return two ranges into the physical buffer that correspond to
1228 /// the given range.
1229 fn slice_ranges<R>(&self, range: R) -> (Range<usize>, Range<usize>)
1231 R: RangeBounds<usize>,
1233 let Range { start, end } = slice::range(range, ..self.len);
1234 let len = end - start;
1239 // `slice::range` guarantees that `start <= end <= self.len`.
1240 // because `len != 0`, we know that `start < end`, so `start < self.len`
1241 // and the indexing is valid.
1242 let wrapped_start = self.to_physical_idx(start);
1244 // this subtraction can never overflow because `wrapped_start` is
1245 // at most `self.capacity()` (and if `self.capacity != 0`, then `wrapped_start` is strictly less
1246 // than `self.capacity`).
1247 let head_len = self.capacity() - wrapped_start;
1249 if head_len >= len {
1250 // we know that `len + wrapped_start <= self.capacity <= usize::MAX`, so this addition can't overflow
1251 (wrapped_start..wrapped_start + len, 0..0)
1253 // can't overflow because of the if condition
1254 let tail_len = len - head_len;
1255 (wrapped_start..self.capacity(), 0..tail_len)
1260 /// Creates an iterator that covers the specified range in the deque.
1264 /// Panics if the starting point is greater than the end point or if
1265 /// the end point is greater than the length of the deque.
1270 /// use std::collections::VecDeque;
1272 /// let deque: VecDeque<_> = [1, 2, 3].into();
1273 /// let range = deque.range(2..).copied().collect::<VecDeque<_>>();
1274 /// assert_eq!(range, [3]);
1276 /// // A full range covers all contents
1277 /// let all = deque.range(..);
1278 /// assert_eq!(all.len(), 3);
1281 #[stable(feature = "deque_range", since = "1.51.0")]
1282 pub fn range<R>(&self, range: R) -> Iter<'_, T>
1284 R: RangeBounds<usize>,
1286 let (a_range, b_range) = self.slice_ranges(range);
1287 // SAFETY: The ranges returned by `slice_ranges`
1288 // are valid ranges into the physical buffer, so
1289 // it's ok to pass them to `buffer_range` and
1290 // dereference the result.
1291 let a = unsafe { &*self.buffer_range(a_range) };
1292 let b = unsafe { &*self.buffer_range(b_range) };
1293 Iter::new(a.iter(), b.iter())
1296 /// Creates an iterator that covers the specified mutable range in the deque.
1300 /// Panics if the starting point is greater than the end point or if
1301 /// the end point is greater than the length of the deque.
1306 /// use std::collections::VecDeque;
1308 /// let mut deque: VecDeque<_> = [1, 2, 3].into();
1309 /// for v in deque.range_mut(2..) {
1312 /// assert_eq!(deque, [1, 2, 6]);
1314 /// // A full range covers all contents
1315 /// for v in deque.range_mut(..) {
1318 /// assert_eq!(deque, [2, 4, 12]);
1321 #[stable(feature = "deque_range", since = "1.51.0")]
1322 pub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T>
1324 R: RangeBounds<usize>,
1326 let (a_range, b_range) = self.slice_ranges(range);
1327 // SAFETY: The ranges returned by `slice_ranges`
1328 // are valid ranges into the physical buffer, so
1329 // it's ok to pass them to `buffer_range` and
1330 // dereference the result.
1331 let a = unsafe { &mut *self.buffer_range(a_range) };
1332 let b = unsafe { &mut *self.buffer_range(b_range) };
1333 IterMut::new(a.iter_mut(), b.iter_mut())
1336 /// Removes the specified range from the deque in bulk, returning all
1337 /// removed elements as an iterator. If the iterator is dropped before
1338 /// being fully consumed, it drops the remaining removed elements.
1340 /// The returned iterator keeps a mutable borrow on the queue to optimize
1341 /// its implementation.
1346 /// Panics if the starting point is greater than the end point or if
1347 /// the end point is greater than the length of the deque.
1351 /// If the returned iterator goes out of scope without being dropped (due to
1352 /// [`mem::forget`], for example), the deque may have lost and leaked
1353 /// elements arbitrarily, including elements outside the range.
1358 /// use std::collections::VecDeque;
1360 /// let mut deque: VecDeque<_> = [1, 2, 3].into();
1361 /// let drained = deque.drain(2..).collect::<VecDeque<_>>();
1362 /// assert_eq!(drained, [3]);
1363 /// assert_eq!(deque, [1, 2]);
1365 /// // A full range clears all contents, like `clear()` does
1366 /// deque.drain(..);
1367 /// assert!(deque.is_empty());
1370 #[stable(feature = "drain", since = "1.6.0")]
1371 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
1373 R: RangeBounds<usize>,
1377 // When the Drain is first created, the source deque is shortened to
1378 // make sure no uninitialized or moved-from elements are accessible at
1379 // all if the Drain's destructor never gets to run.
1381 // Drain will ptr::read out the values to remove.
1382 // When finished, the remaining data will be copied back to cover the hole,
1383 // and the head/tail values will be restored correctly.
1385 let Range { start, end } = slice::range(range, ..self.len);
1386 let drain_start = start;
1387 let drain_len = end - start;
1389 // The deque's elements are parted into three segments:
1390 // * 0 -> drain_start
1391 // * drain_start -> drain_start+drain_len
1392 // * drain_start+drain_len -> self.len
1394 // H = self.head; T = self.head+self.len; t = drain_start+drain_len; h = drain_head
1396 // We store drain_start as self.len, and drain_len and self.len as
1397 // drain_len and orig_len respectively on the Drain. This also
1398 // truncates the effective array such that if the Drain is leaked, we
1399 // have forgotten about the potentially moved values after the start of
1403 // [. . . o o x x o o . . .]
1405 // "forget" about the values after the start of the drain until after
1406 // the drain is complete and the Drain destructor is run.
1408 unsafe { Drain::new(self, drain_start, drain_len) }
1411 /// Clears the deque, removing all values.
1416 /// use std::collections::VecDeque;
1418 /// let mut deque = VecDeque::new();
1419 /// deque.push_back(1);
1421 /// assert!(deque.is_empty());
1423 #[stable(feature = "rust1", since = "1.0.0")]
1425 pub fn clear(&mut self) {
1427 // Not strictly necessary, but leaves things in a more consistent/predictable state.
1431 /// Returns `true` if the deque contains an element equal to the
1434 /// This operation is *O*(*n*).
1436 /// Note that if you have a sorted `VecDeque`, [`binary_search`] may be faster.
1438 /// [`binary_search`]: VecDeque::binary_search
1443 /// use std::collections::VecDeque;
1445 /// let mut deque: VecDeque<u32> = VecDeque::new();
1447 /// deque.push_back(0);
1448 /// deque.push_back(1);
1450 /// assert_eq!(deque.contains(&1), true);
1451 /// assert_eq!(deque.contains(&10), false);
1453 #[stable(feature = "vec_deque_contains", since = "1.12.0")]
1454 pub fn contains(&self, x: &T) -> bool
1458 let (a, b) = self.as_slices();
1459 a.contains(x) || b.contains(x)
1462 /// Provides a reference to the front element, or `None` if the deque is
1468 /// use std::collections::VecDeque;
1470 /// let mut d = VecDeque::new();
1471 /// assert_eq!(d.front(), None);
1475 /// assert_eq!(d.front(), Some(&1));
1477 #[stable(feature = "rust1", since = "1.0.0")]
1478 pub fn front(&self) -> Option<&T> {
1482 /// Provides a mutable reference to the front element, or `None` if the
1488 /// use std::collections::VecDeque;
1490 /// let mut d = VecDeque::new();
1491 /// assert_eq!(d.front_mut(), None);
1495 /// match d.front_mut() {
1496 /// Some(x) => *x = 9,
1499 /// assert_eq!(d.front(), Some(&9));
1501 #[stable(feature = "rust1", since = "1.0.0")]
1502 pub fn front_mut(&mut self) -> Option<&mut T> {
1506 /// Provides a reference to the back element, or `None` if the deque is
1512 /// use std::collections::VecDeque;
1514 /// let mut d = VecDeque::new();
1515 /// assert_eq!(d.back(), None);
1519 /// assert_eq!(d.back(), Some(&2));
1521 #[stable(feature = "rust1", since = "1.0.0")]
1522 pub fn back(&self) -> Option<&T> {
1523 self.get(self.len.wrapping_sub(1))
1526 /// Provides a mutable reference to the back element, or `None` if the
1532 /// use std::collections::VecDeque;
1534 /// let mut d = VecDeque::new();
1535 /// assert_eq!(d.back(), None);
1539 /// match d.back_mut() {
1540 /// Some(x) => *x = 9,
1543 /// assert_eq!(d.back(), Some(&9));
1545 #[stable(feature = "rust1", since = "1.0.0")]
1546 pub fn back_mut(&mut self) -> Option<&mut T> {
1547 self.get_mut(self.len.wrapping_sub(1))
1550 /// Removes the first element and returns it, or `None` if the deque is
1556 /// use std::collections::VecDeque;
1558 /// let mut d = VecDeque::new();
1562 /// assert_eq!(d.pop_front(), Some(1));
1563 /// assert_eq!(d.pop_front(), Some(2));
1564 /// assert_eq!(d.pop_front(), None);
1566 #[stable(feature = "rust1", since = "1.0.0")]
1567 pub fn pop_front(&mut self) -> Option<T> {
1568 if self.is_empty() {
1571 let old_head = self.head;
1572 self.head = self.to_physical_idx(1);
1574 Some(unsafe { self.buffer_read(old_head) })
1578 /// Removes the last element from the deque and returns it, or `None` if
1584 /// use std::collections::VecDeque;
1586 /// let mut buf = VecDeque::new();
1587 /// assert_eq!(buf.pop_back(), None);
1588 /// buf.push_back(1);
1589 /// buf.push_back(3);
1590 /// assert_eq!(buf.pop_back(), Some(3));
1592 #[stable(feature = "rust1", since = "1.0.0")]
1593 pub fn pop_back(&mut self) -> Option<T> {
1594 if self.is_empty() {
1598 Some(unsafe { self.buffer_read(self.to_physical_idx(self.len)) })
1602 /// Prepends an element to the deque.
1607 /// use std::collections::VecDeque;
1609 /// let mut d = VecDeque::new();
1610 /// d.push_front(1);
1611 /// d.push_front(2);
1612 /// assert_eq!(d.front(), Some(&2));
1614 #[stable(feature = "rust1", since = "1.0.0")]
1615 pub fn push_front(&mut self, value: T) {
1620 self.head = self.wrap_sub(self.head, 1);
1624 self.buffer_write(self.head, value);
1628 /// Appends an element to the back of the deque.
1633 /// use std::collections::VecDeque;
1635 /// let mut buf = VecDeque::new();
1636 /// buf.push_back(1);
1637 /// buf.push_back(3);
1638 /// assert_eq!(3, *buf.back().unwrap());
1640 #[stable(feature = "rust1", since = "1.0.0")]
1641 pub fn push_back(&mut self, value: T) {
1646 unsafe { self.buffer_write(self.to_physical_idx(self.len), value) }
1651 fn is_contiguous(&self) -> bool {
1652 // Do the calculation like this to avoid overflowing if len + head > usize::MAX
1653 self.head <= self.capacity() - self.len
1656 /// Removes an element from anywhere in the deque and returns it,
1657 /// replacing it with the first element.
1659 /// This does not preserve ordering, but is *O*(1).
1661 /// Returns `None` if `index` is out of bounds.
1663 /// Element at index 0 is the front of the queue.
1668 /// use std::collections::VecDeque;
1670 /// let mut buf = VecDeque::new();
1671 /// assert_eq!(buf.swap_remove_front(0), None);
1672 /// buf.push_back(1);
1673 /// buf.push_back(2);
1674 /// buf.push_back(3);
1675 /// assert_eq!(buf, [1, 2, 3]);
1677 /// assert_eq!(buf.swap_remove_front(2), Some(3));
1678 /// assert_eq!(buf, [2, 1]);
1680 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1681 pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
1682 let length = self.len;
1683 if index < length && index != 0 {
1684 self.swap(index, 0);
1685 } else if index >= length {
1691 /// Removes an element from anywhere in the deque and returns it,
1692 /// replacing it with the last element.
1694 /// This does not preserve ordering, but is *O*(1).
1696 /// Returns `None` if `index` is out of bounds.
1698 /// Element at index 0 is the front of the queue.
1703 /// use std::collections::VecDeque;
1705 /// let mut buf = VecDeque::new();
1706 /// assert_eq!(buf.swap_remove_back(0), None);
1707 /// buf.push_back(1);
1708 /// buf.push_back(2);
1709 /// buf.push_back(3);
1710 /// assert_eq!(buf, [1, 2, 3]);
1712 /// assert_eq!(buf.swap_remove_back(0), Some(1));
1713 /// assert_eq!(buf, [3, 2]);
1715 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1716 pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
1717 let length = self.len;
1718 if length > 0 && index < length - 1 {
1719 self.swap(index, length - 1);
1720 } else if index >= length {
1726 /// Inserts an element at `index` within the deque, shifting all elements
1727 /// with indices greater than or equal to `index` towards the back.
1729 /// Element at index 0 is the front of the queue.
1733 /// Panics if `index` is greater than deque's length
1738 /// use std::collections::VecDeque;
1740 /// let mut vec_deque = VecDeque::new();
1741 /// vec_deque.push_back('a');
1742 /// vec_deque.push_back('b');
1743 /// vec_deque.push_back('c');
1744 /// assert_eq!(vec_deque, &['a', 'b', 'c']);
1746 /// vec_deque.insert(1, 'd');
1747 /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
1749 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1750 pub fn insert(&mut self, index: usize, value: T) {
1751 assert!(index <= self.len(), "index out of bounds");
1756 let k = self.len - index;
1758 // `index + 1` can't overflow, because if index was usize::MAX, then either the
1759 // assert would've failed, or the deque would've tried to grow past usize::MAX
1762 // see `remove()` for explanation why this wrap_copy() call is safe.
1763 self.wrap_copy(self.to_physical_idx(index), self.to_physical_idx(index + 1), k);
1764 self.buffer_write(self.to_physical_idx(index), value);
1768 let old_head = self.head;
1769 self.head = self.wrap_sub(self.head, 1);
1771 self.wrap_copy(old_head, self.head, index);
1772 self.buffer_write(self.to_physical_idx(index), value);
1778 /// Removes and returns the element at `index` from the deque.
1779 /// Whichever end is closer to the removal point will be moved to make
1780 /// room, and all the affected elements will be moved to new positions.
1781 /// Returns `None` if `index` is out of bounds.
1783 /// Element at index 0 is the front of the queue.
1788 /// use std::collections::VecDeque;
1790 /// let mut buf = VecDeque::new();
1791 /// buf.push_back(1);
1792 /// buf.push_back(2);
1793 /// buf.push_back(3);
1794 /// assert_eq!(buf, [1, 2, 3]);
1796 /// assert_eq!(buf.remove(1), Some(2));
1797 /// assert_eq!(buf, [1, 3]);
1799 #[stable(feature = "rust1", since = "1.0.0")]
1800 pub fn remove(&mut self, index: usize) -> Option<T> {
1801 if self.len <= index {
1805 let wrapped_idx = self.to_physical_idx(index);
1807 let elem = unsafe { Some(self.buffer_read(wrapped_idx)) };
1809 let k = self.len - index - 1;
1810 // safety: due to the nature of the if-condition, whichever wrap_copy gets called,
1811 // its length argument will be at most `self.len / 2`, so there can't be more than
1812 // one overlapping area.
1814 unsafe { self.wrap_copy(self.wrap_add(wrapped_idx, 1), wrapped_idx, k) };
1817 let old_head = self.head;
1818 self.head = self.to_physical_idx(1);
1819 unsafe { self.wrap_copy(old_head, self.head, index) };
1826 /// Splits the deque into two at the given index.
1828 /// Returns a newly allocated `VecDeque`. `self` contains elements `[0, at)`,
1829 /// and the returned deque contains elements `[at, len)`.
1831 /// Note that the capacity of `self` does not change.
1833 /// Element at index 0 is the front of the queue.
1837 /// Panics if `at > len`.
1842 /// use std::collections::VecDeque;
1844 /// let mut buf: VecDeque<_> = [1, 2, 3].into();
1845 /// let buf2 = buf.split_off(1);
1846 /// assert_eq!(buf, [1]);
1847 /// assert_eq!(buf2, [2, 3]);
1850 #[must_use = "use `.truncate()` if you don't need the other half"]
1851 #[stable(feature = "split_off", since = "1.4.0")]
1852 pub fn split_off(&mut self, at: usize) -> Self
1857 assert!(at <= len, "`at` out of bounds");
1859 let other_len = len - at;
1860 let mut other = VecDeque::with_capacity_in(other_len, self.allocator().clone());
1863 let (first_half, second_half) = self.as_slices();
1865 let first_len = first_half.len();
1866 let second_len = second_half.len();
1868 // `at` lies in the first half.
1869 let amount_in_first = first_len - at;
1871 ptr::copy_nonoverlapping(first_half.as_ptr().add(at), other.ptr(), amount_in_first);
1873 // just take all of the second half.
1874 ptr::copy_nonoverlapping(
1875 second_half.as_ptr(),
1876 other.ptr().add(amount_in_first),
1880 // `at` lies in the second half, need to factor in the elements we skipped
1881 // in the first half.
1882 let offset = at - first_len;
1883 let amount_in_second = second_len - offset;
1884 ptr::copy_nonoverlapping(
1885 second_half.as_ptr().add(offset),
1892 // Cleanup where the ends of the buffers are
1894 other.len = other_len;
1899 /// Moves all the elements of `other` into `self`, leaving `other` empty.
1903 /// Panics if the new number of elements in self overflows a `usize`.
1908 /// use std::collections::VecDeque;
1910 /// let mut buf: VecDeque<_> = [1, 2].into();
1911 /// let mut buf2: VecDeque<_> = [3, 4].into();
1912 /// buf.append(&mut buf2);
1913 /// assert_eq!(buf, [1, 2, 3, 4]);
1914 /// assert_eq!(buf2, []);
1917 #[stable(feature = "append", since = "1.4.0")]
1918 pub fn append(&mut self, other: &mut Self) {
1920 self.len += other.len;
1926 self.reserve(other.len);
1928 let (left, right) = other.as_slices();
1929 self.copy_slice(self.to_physical_idx(self.len), left);
1930 // no overflow, because self.capacity() >= old_cap + left.len() >= self.len + left.len()
1931 self.copy_slice(self.to_physical_idx(self.len + left.len()), right);
1933 // SAFETY: Update pointers after copying to avoid leaving doppelganger
1934 // in case of panics.
1935 self.len += other.len;
1936 // Now that we own its values, forget everything in `other`.
1941 /// Retains only the elements specified by the predicate.
1943 /// In other words, remove all elements `e` for which `f(&e)` returns false.
1944 /// This method operates in place, visiting each element exactly once in the
1945 /// original order, and preserves the order of the retained elements.
1950 /// use std::collections::VecDeque;
1952 /// let mut buf = VecDeque::new();
1953 /// buf.extend(1..5);
1954 /// buf.retain(|&x| x % 2 == 0);
1955 /// assert_eq!(buf, [2, 4]);
1958 /// Because the elements are visited exactly once in the original order,
1959 /// external state may be used to decide which elements to keep.
1962 /// use std::collections::VecDeque;
1964 /// let mut buf = VecDeque::new();
1965 /// buf.extend(1..6);
1967 /// let keep = [false, true, true, false, true];
1968 /// let mut iter = keep.iter();
1969 /// buf.retain(|_| *iter.next().unwrap());
1970 /// assert_eq!(buf, [2, 3, 5]);
1972 #[stable(feature = "vec_deque_retain", since = "1.4.0")]
1973 pub fn retain<F>(&mut self, mut f: F)
1975 F: FnMut(&T) -> bool,
1977 self.retain_mut(|elem| f(elem));
1980 /// Retains only the elements specified by the predicate.
1982 /// In other words, remove all elements `e` for which `f(&e)` returns false.
1983 /// This method operates in place, visiting each element exactly once in the
1984 /// original order, and preserves the order of the retained elements.
1989 /// use std::collections::VecDeque;
1991 /// let mut buf = VecDeque::new();
1992 /// buf.extend(1..5);
1993 /// buf.retain_mut(|x| if *x % 2 == 0 {
1999 /// assert_eq!(buf, [3, 5]);
2001 #[stable(feature = "vec_retain_mut", since = "1.61.0")]
2002 pub fn retain_mut<F>(&mut self, mut f: F)
2004 F: FnMut(&mut T) -> bool,
2010 // Stage 1: All values are retained.
2012 if !f(&mut self[cur]) {
2019 // Stage 2: Swap retained value into current idx.
2021 if !f(&mut self[cur]) {
2026 self.swap(idx, cur);
2030 // Stage 3: Truncate all values after idx.
2036 // Double the buffer size. This method is inline(never), so we expect it to only
2037 // be called in cold paths.
2038 // This may panic or abort
2040 fn grow(&mut self) {
2041 // Extend or possibly remove this assertion when valid use-cases for growing the
2042 // buffer without it being full emerge
2043 debug_assert!(self.is_full());
2044 let old_cap = self.capacity();
2045 self.buf.reserve_for_push(old_cap);
2047 self.handle_capacity_increase(old_cap);
2049 debug_assert!(!self.is_full());
2052 /// Modifies the deque in-place so that `len()` is equal to `new_len`,
2053 /// either by removing excess elements from the back or by appending
2054 /// elements generated by calling `generator` to the back.
2059 /// use std::collections::VecDeque;
2061 /// let mut buf = VecDeque::new();
2062 /// buf.push_back(5);
2063 /// buf.push_back(10);
2064 /// buf.push_back(15);
2065 /// assert_eq!(buf, [5, 10, 15]);
2067 /// buf.resize_with(5, Default::default);
2068 /// assert_eq!(buf, [5, 10, 15, 0, 0]);
2070 /// buf.resize_with(2, || unreachable!());
2071 /// assert_eq!(buf, [5, 10]);
2073 /// let mut state = 100;
2074 /// buf.resize_with(5, || { state += 1; state });
2075 /// assert_eq!(buf, [5, 10, 101, 102, 103]);
2077 #[stable(feature = "vec_resize_with", since = "1.33.0")]
2078 pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) {
2082 self.extend(repeat_with(generator).take(new_len - len))
2084 self.truncate(new_len);
2088 /// Rearranges the internal storage of this deque so it is one contiguous
2089 /// slice, which is then returned.
2091 /// This method does not allocate and does not change the order of the
2092 /// inserted elements. As it returns a mutable slice, this can be used to
2095 /// Once the internal storage is contiguous, the [`as_slices`] and
2096 /// [`as_mut_slices`] methods will return the entire contents of the
2097 /// deque in a single slice.
2099 /// [`as_slices`]: VecDeque::as_slices
2100 /// [`as_mut_slices`]: VecDeque::as_mut_slices
2104 /// Sorting the content of a deque.
2107 /// use std::collections::VecDeque;
2109 /// let mut buf = VecDeque::with_capacity(15);
2111 /// buf.push_back(2);
2112 /// buf.push_back(1);
2113 /// buf.push_front(3);
2115 /// // sorting the deque
2116 /// buf.make_contiguous().sort();
2117 /// assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));
2119 /// // sorting it in reverse order
2120 /// buf.make_contiguous().sort_by(|a, b| b.cmp(a));
2121 /// assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));
2124 /// Getting immutable access to the contiguous slice.
2127 /// use std::collections::VecDeque;
2129 /// let mut buf = VecDeque::new();
2131 /// buf.push_back(2);
2132 /// buf.push_back(1);
2133 /// buf.push_front(3);
2135 /// buf.make_contiguous();
2136 /// if let (slice, &[]) = buf.as_slices() {
2137 /// // we can now be sure that `slice` contains all elements of the deque,
2138 /// // while still having immutable access to `buf`.
2139 /// assert_eq!(buf.len(), slice.len());
2140 /// assert_eq!(slice, &[3, 2, 1] as &[_]);
2143 #[stable(feature = "deque_make_contiguous", since = "1.48.0")]
2144 pub fn make_contiguous(&mut self) -> &mut [T] {
2149 if self.is_contiguous() {
2150 unsafe { return slice::from_raw_parts_mut(self.ptr().add(self.head), self.len) }
2153 let &mut Self { head, len, .. } = self;
2154 let ptr = self.ptr();
2155 let cap = self.capacity();
2157 let free = cap - len;
2158 let head_len = cap - head;
2159 let tail = len - head_len;
2160 let tail_len = tail;
2162 if free >= head_len {
2163 // there is enough free space to copy the head in one go,
2164 // this means that we first shift the tail backwards, and then
2165 // copy the head to the correct position.
2167 // from: DEFGH....ABC
2170 self.copy(0, head_len, tail_len);
2172 self.copy_nonoverlapping(head, 0, head_len);
2177 } else if free >= tail_len {
2178 // there is enough free space to copy the tail in one go,
2179 // this means that we first shift the head forwards, and then
2180 // copy the tail to the correct position.
2182 // from: FGH....ABCDE
2185 self.copy(head, tail, head_len);
2187 self.copy_nonoverlapping(0, tail + head_len, tail_len);
2193 // `free` is smaller than both `head_len` and `tail_len`.
2194 // the general algorithm for this first moves the slices
2195 // right next to each other and then uses `slice::rotate`
2196 // to rotate them into place:
2198 // initially: HIJK..ABCDEFG
2199 // step 1: ..HIJKABCDEFG
2200 // step 2: ..ABCDEFGHIJK
2204 // initially: FGHIJK..ABCDE
2205 // step 1: FGHIJKABCDE..
2206 // step 2: ABCDEFGHIJK..
2208 // pick the shorter of the 2 slices to reduce the amount
2209 // of memory that needs to be moved around.
2210 if head_len > tail_len {
2211 // tail is shorter, so:
2212 // 1. copy tail forwards
2213 // 2. rotate used part of the buffer
2214 // 3. update head to point to the new beginning (which is just `free`)
2217 // if there is no free space in the buffer, then the slices are already
2218 // right next to each other and we don't need to move any memory.
2220 // because we only move the tail forward as much as there's free space
2221 // behind it, we don't overwrite any elements of the head slice, and
2222 // the slices end up right next to each other.
2223 self.copy(0, free, tail_len);
2226 // We just copied the tail right next to the head slice,
2227 // so all of the elements in the range are initialized
2228 let slice = &mut *self.buffer_range(free..self.capacity());
2230 // because the deque wasn't contiguous, we know that `tail_len < self.len == slice.len()`,
2231 // so this will never panic.
2232 slice.rotate_left(tail_len);
2234 // the used part of the buffer now is `free..self.capacity()`, so set
2235 // `head` to the beginning of that range.
2239 // head is shorter so:
2240 // 1. copy head backwards
2241 // 2. rotate used part of the buffer
2242 // 3. update head to point to the new beginning (which is the beginning of the buffer)
2245 // if there is no free space in the buffer, then the slices are already
2246 // right next to each other and we don't need to move any memory.
2248 // copy the head slice to lie right behind the tail slice.
2249 self.copy(self.head, tail_len, head_len);
2252 // because we copied the head slice so that both slices lie right
2253 // next to each other, all the elements in the range are initialized.
2254 let slice = &mut *self.buffer_range(0..self.len);
2256 // because the deque wasn't contiguous, we know that `head_len < self.len == slice.len()`
2257 // so this will never panic.
2258 slice.rotate_right(head_len);
2260 // the used part of the buffer now is `0..self.len`, so set
2261 // `head` to the beginning of that range.
2267 unsafe { slice::from_raw_parts_mut(ptr.add(self.head), self.len) }
2270 /// Rotates the double-ended queue `mid` places to the left.
2273 /// - Rotates item `mid` into the first position.
2274 /// - Pops the first `mid` items and pushes them to the end.
2275 /// - Rotates `len() - mid` places to the right.
2279 /// If `mid` is greater than `len()`. Note that `mid == len()`
2280 /// does _not_ panic and is a no-op rotation.
2284 /// Takes `*O*(min(mid, len() - mid))` time and no extra space.
2289 /// use std::collections::VecDeque;
2291 /// let mut buf: VecDeque<_> = (0..10).collect();
2293 /// buf.rotate_left(3);
2294 /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);
2296 /// for i in 1..10 {
2297 /// assert_eq!(i * 3 % 10, buf[0]);
2298 /// buf.rotate_left(3);
2300 /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
2302 #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
2303 pub fn rotate_left(&mut self, mid: usize) {
2304 assert!(mid <= self.len());
2305 let k = self.len - mid;
2307 unsafe { self.rotate_left_inner(mid) }
2309 unsafe { self.rotate_right_inner(k) }
2313 /// Rotates the double-ended queue `k` places to the right.
2316 /// - Rotates the first item into position `k`.
2317 /// - Pops the last `k` items and pushes them to the front.
2318 /// - Rotates `len() - k` places to the left.
2322 /// If `k` is greater than `len()`. Note that `k == len()`
2323 /// does _not_ panic and is a no-op rotation.
2327 /// Takes `*O*(min(k, len() - k))` time and no extra space.
2332 /// use std::collections::VecDeque;
2334 /// let mut buf: VecDeque<_> = (0..10).collect();
2336 /// buf.rotate_right(3);
2337 /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);
2339 /// for i in 1..10 {
2340 /// assert_eq!(0, buf[i * 3 % 10]);
2341 /// buf.rotate_right(3);
2343 /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
2345 #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
2346 pub fn rotate_right(&mut self, k: usize) {
2347 assert!(k <= self.len());
2348 let mid = self.len - k;
2350 unsafe { self.rotate_right_inner(k) }
2352 unsafe { self.rotate_left_inner(mid) }
2356 // SAFETY: the following two methods require that the rotation amount
2357 // be less than half the length of the deque.
2359 // `wrap_copy` requires that `min(x, capacity() - x) + copy_len <= capacity()`,
2360 // but then `min` is never more than half the capacity, regardless of x,
2361 // so it's sound to call here because we're calling with something
2362 // less than half the length, which is never above half the capacity.
2364 unsafe fn rotate_left_inner(&mut self, mid: usize) {
2365 debug_assert!(mid * 2 <= self.len());
2367 self.wrap_copy(self.head, self.to_physical_idx(self.len), mid);
2369 self.head = self.to_physical_idx(mid);
2372 unsafe fn rotate_right_inner(&mut self, k: usize) {
2373 debug_assert!(k * 2 <= self.len());
2374 self.head = self.wrap_sub(self.head, k);
2376 self.wrap_copy(self.to_physical_idx(self.len), self.head, k);
2380 /// Binary searches this `VecDeque` for a given element.
2381 /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
2383 /// If the value is found then [`Result::Ok`] is returned, containing the
2384 /// index of the matching element. If there are multiple matches, then any
2385 /// one of the matches could be returned. If the value is not found then
2386 /// [`Result::Err`] is returned, containing the index where a matching
2387 /// element could be inserted while maintaining sorted order.
2389 /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
2391 /// [`contains`]: VecDeque::contains
2392 /// [`binary_search_by`]: VecDeque::binary_search_by
2393 /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
2394 /// [`partition_point`]: VecDeque::partition_point
2398 /// Looks up a series of four elements. The first is found, with a
2399 /// uniquely determined position; the second and third are not
2400 /// found; the fourth could match any position in `[1, 4]`.
2403 /// use std::collections::VecDeque;
2405 /// let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2407 /// assert_eq!(deque.binary_search(&13), Ok(9));
2408 /// assert_eq!(deque.binary_search(&4), Err(7));
2409 /// assert_eq!(deque.binary_search(&100), Err(13));
2410 /// let r = deque.binary_search(&1);
2411 /// assert!(matches!(r, Ok(1..=4)));
2414 /// If you want to insert an item to a sorted deque, while maintaining
2415 /// sort order, consider using [`partition_point`]:
2418 /// use std::collections::VecDeque;
2420 /// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2422 /// let idx = deque.partition_point(|&x| x < num);
2423 /// // The above is equivalent to `let idx = deque.binary_search(&num).unwrap_or_else(|x| x);`
2424 /// deque.insert(idx, num);
2425 /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
2427 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2429 pub fn binary_search(&self, x: &T) -> Result<usize, usize>
2433 self.binary_search_by(|e| e.cmp(x))
2436 /// Binary searches this `VecDeque` with a comparator function.
2437 /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
2439 /// The comparator function should implement an order consistent
2440 /// with the sort order of the deque, returning an order code that
2441 /// indicates whether its argument is `Less`, `Equal` or `Greater`
2442 /// than the desired target.
2444 /// If the value is found then [`Result::Ok`] is returned, containing the
2445 /// index of the matching element. If there are multiple matches, then any
2446 /// one of the matches could be returned. If the value is not found then
2447 /// [`Result::Err`] is returned, containing the index where a matching
2448 /// element could be inserted while maintaining sorted order.
2450 /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
2452 /// [`contains`]: VecDeque::contains
2453 /// [`binary_search`]: VecDeque::binary_search
2454 /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
2455 /// [`partition_point`]: VecDeque::partition_point
2459 /// Looks up a series of four elements. The first is found, with a
2460 /// uniquely determined position; the second and third are not
2461 /// found; the fourth could match any position in `[1, 4]`.
2464 /// use std::collections::VecDeque;
2466 /// let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2468 /// assert_eq!(deque.binary_search_by(|x| x.cmp(&13)), Ok(9));
2469 /// assert_eq!(deque.binary_search_by(|x| x.cmp(&4)), Err(7));
2470 /// assert_eq!(deque.binary_search_by(|x| x.cmp(&100)), Err(13));
2471 /// let r = deque.binary_search_by(|x| x.cmp(&1));
2472 /// assert!(matches!(r, Ok(1..=4)));
2474 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2475 pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
2477 F: FnMut(&'a T) -> Ordering,
2479 let (front, back) = self.as_slices();
2480 let cmp_back = back.first().map(|elem| f(elem));
2482 if let Some(Ordering::Equal) = cmp_back {
2484 } else if let Some(Ordering::Less) = cmp_back {
2485 back.binary_search_by(f).map(|idx| idx + front.len()).map_err(|idx| idx + front.len())
2487 front.binary_search_by(f)
2491 /// Binary searches this `VecDeque` with a key extraction function.
2492 /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
2494 /// Assumes that the deque is sorted by the key, for instance with
2495 /// [`make_contiguous().sort_by_key()`] using the same key extraction function.
2497 /// If the value is found then [`Result::Ok`] is returned, containing the
2498 /// index of the matching element. If there are multiple matches, then any
2499 /// one of the matches could be returned. If the value is not found then
2500 /// [`Result::Err`] is returned, containing the index where a matching
2501 /// element could be inserted while maintaining sorted order.
2503 /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
2505 /// [`contains`]: VecDeque::contains
2506 /// [`make_contiguous().sort_by_key()`]: VecDeque::make_contiguous
2507 /// [`binary_search`]: VecDeque::binary_search
2508 /// [`binary_search_by`]: VecDeque::binary_search_by
2509 /// [`partition_point`]: VecDeque::partition_point
2513 /// Looks up a series of four elements in a slice of pairs sorted by
2514 /// their second elements. The first is found, with a uniquely
2515 /// determined position; the second and third are not found; the
2516 /// fourth could match any position in `[1, 4]`.
2519 /// use std::collections::VecDeque;
2521 /// let deque: VecDeque<_> = [(0, 0), (2, 1), (4, 1), (5, 1),
2522 /// (3, 1), (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
2523 /// (1, 21), (2, 34), (4, 55)].into();
2525 /// assert_eq!(deque.binary_search_by_key(&13, |&(a, b)| b), Ok(9));
2526 /// assert_eq!(deque.binary_search_by_key(&4, |&(a, b)| b), Err(7));
2527 /// assert_eq!(deque.binary_search_by_key(&100, |&(a, b)| b), Err(13));
2528 /// let r = deque.binary_search_by_key(&1, |&(a, b)| b);
2529 /// assert!(matches!(r, Ok(1..=4)));
2531 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2533 pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
2535 F: FnMut(&'a T) -> B,
2538 self.binary_search_by(|k| f(k).cmp(b))
2541 /// Returns the index of the partition point according to the given predicate
2542 /// (the index of the first element of the second partition).
2544 /// The deque is assumed to be partitioned according to the given predicate.
2545 /// This means that all elements for which the predicate returns true are at the start of the deque
2546 /// and all elements for which the predicate returns false are at the end.
2547 /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0`
2548 /// (all odd numbers are at the start, all even at the end).
2550 /// If the deque is not partitioned, the returned result is unspecified and meaningless,
2551 /// as this method performs a kind of binary search.
2553 /// See also [`binary_search`], [`binary_search_by`], and [`binary_search_by_key`].
2555 /// [`binary_search`]: VecDeque::binary_search
2556 /// [`binary_search_by`]: VecDeque::binary_search_by
2557 /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
2562 /// use std::collections::VecDeque;
2564 /// let deque: VecDeque<_> = [1, 2, 3, 3, 5, 6, 7].into();
2565 /// let i = deque.partition_point(|&x| x < 5);
2567 /// assert_eq!(i, 4);
2568 /// assert!(deque.iter().take(i).all(|&x| x < 5));
2569 /// assert!(deque.iter().skip(i).all(|&x| !(x < 5)));
2572 /// If you want to insert an item to a sorted deque, while maintaining
2576 /// use std::collections::VecDeque;
2578 /// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2580 /// let idx = deque.partition_point(|&x| x < num);
2581 /// deque.insert(idx, num);
2582 /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
2584 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2585 pub fn partition_point<P>(&self, mut pred: P) -> usize
2587 P: FnMut(&T) -> bool,
2589 let (front, back) = self.as_slices();
2591 if let Some(true) = back.first().map(|v| pred(v)) {
2592 back.partition_point(pred) + front.len()
2594 front.partition_point(pred)
2599 impl<T: Clone, A: Allocator> VecDeque<T, A> {
2600 /// Modifies the deque in-place so that `len()` is equal to new_len,
2601 /// either by removing excess elements from the back or by appending clones of `value`
2607 /// use std::collections::VecDeque;
2609 /// let mut buf = VecDeque::new();
2610 /// buf.push_back(5);
2611 /// buf.push_back(10);
2612 /// buf.push_back(15);
2613 /// assert_eq!(buf, [5, 10, 15]);
2615 /// buf.resize(2, 0);
2616 /// assert_eq!(buf, [5, 10]);
2618 /// buf.resize(5, 20);
2619 /// assert_eq!(buf, [5, 10, 20, 20, 20]);
2621 #[stable(feature = "deque_extras", since = "1.16.0")]
2622 pub fn resize(&mut self, new_len: usize, value: T) {
2623 if new_len > self.len() {
2624 let extra = new_len - self.len();
2625 self.extend(repeat_n(value, extra))
2627 self.truncate(new_len);
2632 /// Returns the index in the underlying buffer for a given logical element index.
2634 fn wrap_index(logical_index: usize, capacity: usize) -> usize {
2636 (logical_index == 0 && capacity == 0)
2637 || logical_index < capacity
2638 || (logical_index - capacity) < capacity
2640 if logical_index >= capacity { logical_index - capacity } else { logical_index }
2643 #[stable(feature = "rust1", since = "1.0.0")]
2644 impl<T: PartialEq, A: Allocator> PartialEq for VecDeque<T, A> {
2645 fn eq(&self, other: &Self) -> bool {
2646 if self.len != other.len() {
2649 let (sa, sb) = self.as_slices();
2650 let (oa, ob) = other.as_slices();
2651 if sa.len() == oa.len() {
2652 sa == oa && sb == ob
2653 } else if sa.len() < oa.len() {
2654 // Always divisible in three sections, for example:
2655 // self: [a b c|d e f]
2656 // other: [0 1 2 3|4 5]
2657 // front = 3, mid = 1,
2658 // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
2659 let front = sa.len();
2660 let mid = oa.len() - front;
2662 let (oa_front, oa_mid) = oa.split_at(front);
2663 let (sb_mid, sb_back) = sb.split_at(mid);
2664 debug_assert_eq!(sa.len(), oa_front.len());
2665 debug_assert_eq!(sb_mid.len(), oa_mid.len());
2666 debug_assert_eq!(sb_back.len(), ob.len());
2667 sa == oa_front && sb_mid == oa_mid && sb_back == ob
2669 let front = oa.len();
2670 let mid = sa.len() - front;
2672 let (sa_front, sa_mid) = sa.split_at(front);
2673 let (ob_mid, ob_back) = ob.split_at(mid);
2674 debug_assert_eq!(sa_front.len(), oa.len());
2675 debug_assert_eq!(sa_mid.len(), ob_mid.len());
2676 debug_assert_eq!(sb.len(), ob_back.len());
2677 sa_front == oa && sa_mid == ob_mid && sb == ob_back
2682 #[stable(feature = "rust1", since = "1.0.0")]
2683 impl<T: Eq, A: Allocator> Eq for VecDeque<T, A> {}
2685 __impl_slice_eq1! { [] VecDeque<T, A>, Vec<U, A>, }
2686 __impl_slice_eq1! { [] VecDeque<T, A>, &[U], }
2687 __impl_slice_eq1! { [] VecDeque<T, A>, &mut [U], }
2688 __impl_slice_eq1! { [const N: usize] VecDeque<T, A>, [U; N], }
2689 __impl_slice_eq1! { [const N: usize] VecDeque<T, A>, &[U; N], }
2690 __impl_slice_eq1! { [const N: usize] VecDeque<T, A>, &mut [U; N], }
2692 #[stable(feature = "rust1", since = "1.0.0")]
2693 impl<T: PartialOrd, A: Allocator> PartialOrd for VecDeque<T, A> {
2694 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2695 self.iter().partial_cmp(other.iter())
2699 #[stable(feature = "rust1", since = "1.0.0")]
2700 impl<T: Ord, A: Allocator> Ord for VecDeque<T, A> {
2702 fn cmp(&self, other: &Self) -> Ordering {
2703 self.iter().cmp(other.iter())
2707 #[stable(feature = "rust1", since = "1.0.0")]
2708 impl<T: Hash, A: Allocator> Hash for VecDeque<T, A> {
2709 fn hash<H: Hasher>(&self, state: &mut H) {
2710 state.write_length_prefix(self.len);
2711 // It's not possible to use Hash::hash_slice on slices
2712 // returned by as_slices method as their length can vary
2713 // in otherwise identical deques.
2715 // Hasher only guarantees equivalence for the exact same
2716 // set of calls to its methods.
2717 self.iter().for_each(|elem| elem.hash(state));
2721 #[stable(feature = "rust1", since = "1.0.0")]
2722 impl<T, A: Allocator> Index<usize> for VecDeque<T, A> {
2726 fn index(&self, index: usize) -> &T {
2727 self.get(index).expect("Out of bounds access")
2731 #[stable(feature = "rust1", since = "1.0.0")]
2732 impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A> {
2734 fn index_mut(&mut self, index: usize) -> &mut T {
2735 self.get_mut(index).expect("Out of bounds access")
2739 #[stable(feature = "rust1", since = "1.0.0")]
2740 impl<T> FromIterator<T> for VecDeque<T> {
2741 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T> {
2742 SpecFromIter::spec_from_iter(iter.into_iter())
2746 #[stable(feature = "rust1", since = "1.0.0")]
2747 impl<T, A: Allocator> IntoIterator for VecDeque<T, A> {
2749 type IntoIter = IntoIter<T, A>;
2751 /// Consumes the deque into a front-to-back iterator yielding elements by
2753 fn into_iter(self) -> IntoIter<T, A> {
2758 #[stable(feature = "rust1", since = "1.0.0")]
2759 impl<'a, T, A: Allocator> IntoIterator for &'a VecDeque<T, A> {
2761 type IntoIter = Iter<'a, T>;
2763 fn into_iter(self) -> Iter<'a, T> {
2768 #[stable(feature = "rust1", since = "1.0.0")]
2769 impl<'a, T, A: Allocator> IntoIterator for &'a mut VecDeque<T, A> {
2770 type Item = &'a mut T;
2771 type IntoIter = IterMut<'a, T>;
2773 fn into_iter(self) -> IterMut<'a, T> {
2778 #[stable(feature = "rust1", since = "1.0.0")]
2779 impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
2780 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2781 <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
2785 fn extend_one(&mut self, elem: T) {
2786 self.push_back(elem);
2790 fn extend_reserve(&mut self, additional: usize) {
2791 self.reserve(additional);
2795 #[stable(feature = "extend_ref", since = "1.2.0")]
2796 impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> {
2797 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2798 self.spec_extend(iter.into_iter());
2802 fn extend_one(&mut self, &elem: &T) {
2803 self.push_back(elem);
2807 fn extend_reserve(&mut self, additional: usize) {
2808 self.reserve(additional);
2812 #[stable(feature = "rust1", since = "1.0.0")]
2813 impl<T: fmt::Debug, A: Allocator> fmt::Debug for VecDeque<T, A> {
2814 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2815 f.debug_list().entries(self.iter()).finish()
2819 #[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
2820 impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> {
2821 /// Turn a [`Vec<T>`] into a [`VecDeque<T>`].
2823 /// [`Vec<T>`]: crate::vec::Vec
2824 /// [`VecDeque<T>`]: crate::collections::VecDeque
2826 /// This conversion is guaranteed to run in *O*(1) time
2827 /// and to not re-allocate the `Vec`'s buffer or allocate
2828 /// any additional memory.
2830 fn from(other: Vec<T, A>) -> Self {
2831 let (ptr, len, cap, alloc) = other.into_raw_parts_with_alloc();
2832 Self { head: 0, len, buf: unsafe { RawVec::from_raw_parts_in(ptr, cap, alloc) } }
2836 #[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
2837 impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A> {
2838 /// Turn a [`VecDeque<T>`] into a [`Vec<T>`].
2840 /// [`Vec<T>`]: crate::vec::Vec
2841 /// [`VecDeque<T>`]: crate::collections::VecDeque
2843 /// This never needs to re-allocate, but does need to do *O*(*n*) data movement if
2844 /// the circular buffer doesn't happen to be at the beginning of the allocation.
2849 /// use std::collections::VecDeque;
2851 /// // This one is *O*(1).
2852 /// let deque: VecDeque<_> = (1..5).collect();
2853 /// let ptr = deque.as_slices().0.as_ptr();
2854 /// let vec = Vec::from(deque);
2855 /// assert_eq!(vec, [1, 2, 3, 4]);
2856 /// assert_eq!(vec.as_ptr(), ptr);
2858 /// // This one needs data rearranging.
2859 /// let mut deque: VecDeque<_> = (1..5).collect();
2860 /// deque.push_front(9);
2861 /// deque.push_front(8);
2862 /// let ptr = deque.as_slices().1.as_ptr();
2863 /// let vec = Vec::from(deque);
2864 /// assert_eq!(vec, [8, 9, 1, 2, 3, 4]);
2865 /// assert_eq!(vec.as_ptr(), ptr);
2867 fn from(mut other: VecDeque<T, A>) -> Self {
2868 other.make_contiguous();
2871 let other = ManuallyDrop::new(other);
2872 let buf = other.buf.ptr();
2873 let len = other.len();
2874 let cap = other.capacity();
2875 let alloc = ptr::read(other.allocator());
2877 if other.head != 0 {
2878 ptr::copy(buf.add(other.head), buf, len);
2880 Vec::from_raw_parts_in(buf, len, cap, alloc)
2885 #[stable(feature = "std_collections_from_array", since = "1.56.0")]
2886 impl<T, const N: usize> From<[T; N]> for VecDeque<T> {
2887 /// Converts a `[T; N]` into a `VecDeque<T>`.
2890 /// use std::collections::VecDeque;
2892 /// let deq1 = VecDeque::from([1, 2, 3, 4]);
2893 /// let deq2: VecDeque<_> = [1, 2, 3, 4].into();
2894 /// assert_eq!(deq1, deq2);
2896 fn from(arr: [T; N]) -> Self {
2897 let mut deq = VecDeque::with_capacity(N);
2898 let arr = ManuallyDrop::new(arr);
2900 // SAFETY: VecDeque::with_capacity ensures that there is enough capacity.
2902 ptr::copy_nonoverlapping(arr.as_ptr(), deq.ptr(), N);