mod.rs - source
Description: Source of the Rust file `library/alloc/src/collections/vec_deque/mod.rs`.

#
alloc/collections/vec_deque/
mod.rs

    1//! A double-ended queue (deque) implemented with a growable ring buffer.
    2//!
    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.
    7
    8#![stable(feature = "rust1", since = "1.0.0")]
    9
    10#[cfg(not(no_global_oom_handling))]
    11use core::clone::TrivialClone;
    12use core::cmp::{self, Ordering};
    13use core::hash::{Hash, Hasher};
    14use core::iter::{ByRefSized, repeat_n, repeat_with};
    15// This is used in a bunch of intra-doc links.
    16// FIXME: For some reason, `#[cfg(doc)]` wasn't sufficient, resulting in
    17// failures in linkchecker even though rustdoc built the docs just fine.
    18#[allow(unused_imports)]
    19use core::mem;
    20use core::mem::{ManuallyDrop, SizedTypeProperties};
    21use core::ops::{Index, IndexMut, Range, RangeBounds};
    22use core::{fmt, ptr, slice};
    23
    24use crate::alloc::{Allocator, Global};
    25use crate::collections::{TryReserveError, TryReserveErrorKind};
    26use crate::raw_vec::RawVec;
    27use crate::vec::Vec;
    28
    29#[macro_use]
    30mod macros;
    31
    32#[stable(feature = "drain", since = "1.6.0")]
    33pub use self::drain::Drain;
    34
    35mod drain;
    36
    37#[unstable(feature = "vec_deque_extract_if", issue = "147750")]
    38pub use self::extract_if::ExtractIf;
    39
    40mod extract_if;
    41
    42#[stable(feature = "rust1", since = "1.0.0")]
    43pub use self::iter_mut::IterMut;
    44
    45mod iter_mut;
    46
    47#[stable(feature = "rust1", since = "1.0.0")]
    48pub use self::into_iter::IntoIter;
    49
    50mod into_iter;
    51
    52#[stable(feature = "rust1", since = "1.0.0")]
    53pub use self::iter::Iter;
    54
    55mod iter;
    56
    57use self::spec_extend::{SpecExtend, SpecExtendFront};
    58
    59mod spec_extend;
    60
    61use self::spec_from_iter::SpecFromIter;
    62
    63mod spec_from_iter;
    64
    65#[cfg(not(no_global_oom_handling))]
    66#[unstable(feature = "deque_extend_front", issue = "146975")]
    67pub use self::splice::Splice;
    68
    69#[cfg(not(no_global_oom_handling))]
    70mod splice;
    71
    72#[cfg(test)]
    73mod tests;
    74
    75/// A double-ended queue implemented with a growable ring buffer.
    76///
    77/// The "default" usage of this type as a queue is to use [`push_back`] to add to
    78/// the queue, and [`pop_front`] to remove from the queue. [`extend`] and [`append`]
    79/// push onto the back in this manner, and iterating over `VecDeque` goes front
    80/// to back.
    81///
    82/// A `VecDeque` with a known list of items can be initialized from an array:
    83///
    84/// ```
    85/// use std::collections::VecDeque;
    86///
    87/// let deq = VecDeque::from([-1, 0, 1]);
    88/// ```
    89///
    90/// Since `VecDeque` is a ring buffer, its elements are not necessarily contiguous
    91/// in memory. If you want to access the elements as a single slice, such as for
    92/// efficient sorting, you can use [`make_contiguous`]. It rotates the `VecDeque`
    93/// so that its elements do not wrap, and returns a mutable slice to the
    94/// now-contiguous element sequence.
    95///
    96/// [`push_back`]: VecDeque::push_back
    97/// [`pop_front`]: VecDeque::pop_front
    98/// [`extend`]: VecDeque::extend
    99/// [`append`]: VecDeque::append
    100/// [`make_contiguous`]: VecDeque::make_contiguous
    101#[cfg_attr(not(test), rustc_diagnostic_item = "VecDeque")]
    102#[stable(feature = "rust1", since = "1.0.0")]
    103#[rustc_insignificant_dtor]
    104pub struct VecDeque<
    105    T,
    106    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
    107> {
    108    // `self[0]`, if it exists, is `buf[head]`.
    109    // `head < buf.capacity()`, unless `buf.capacity() == 0` when `head == 0`.
    110    head: usize,
    111    // the number of initialized elements, starting from the one at `head` and potentially wrapping around.
    112    // if `len == 0`, the exact value of `head` is unimportant.
    113    // if `T` is zero-Sized, then `self.len <= usize::MAX`, otherwise `self.len <= isize::MAX as usize`.
    114    len: usize,
    115    buf: RawVec<T, A>,
    116}
    117
    118#[stable(feature = "rust1", since = "1.0.0")]
    119impl<T: Clone, A: Allocator + Clone> Clone for VecDeque<T, A> {
    120    fn clone(&self) -> Self {
    121        let mut deq = Self::with_capacity_in(self.len(), self.allocator().clone());
    122        deq.extend(self.iter().cloned());
    123        deq
    124    }
    125
    126    /// Overwrites the contents of `self` with a clone of the contents of `source`.
    127    ///
    128    /// This method is preferred over simply assigning `source.clone()` to `self`,
    129    /// as it avoids reallocation if possible.
    130    fn clone_from(&mut self, source: &Self) {
    131        self.clear();
    132        self.extend(source.iter().cloned());
    133    }
    134}
    135
    136#[stable(feature = "rust1", since = "1.0.0")]
    137unsafe impl<#[may_dangle] T, A: Allocator> Drop for VecDeque<T, A> {
    138    fn drop(&mut self) {
    139        /// Runs the destructor for all items in the slice when it gets dropped (normally or
    140        /// during unwinding).
    141        struct Dropper<'a, T>(&'a mut [T]);
    142
    143        impl<'a, T> Drop for Dropper<'a, T> {
    144            fn drop(&mut self) {
    145                unsafe {
    146                    ptr::drop_in_place(self.0);
    147                }
    148            }
    149        }
    150
    151        let (front, back) = self.as_mut_slices();
    152        unsafe {
    153            let _back_dropper = Dropper(back);
    154            // use drop for [T]
    155            ptr::drop_in_place(front);
    156        }
    157        // RawVec handles deallocation
    158    }
    159}
    160
    161#[stable(feature = "rust1", since = "1.0.0")]
    162impl<T> Default for VecDeque<T> {
    163    /// Creates an empty deque.
    164    #[inline]
    165    fn default() -> VecDeque<T> {
    166        VecDeque::new()
    167    }
    168}
    169
    170impl<T, A: Allocator> VecDeque<T, A> {
    171    /// Marginally more convenient
    172    #[inline]
    173    fn ptr(&self) -> *mut T {
    174        self.buf.ptr()
    175    }
    176
    177    /// Appends an element to the buffer.
    178    ///
    179    /// # Safety
    180    ///
    181    /// May only be called if `deque.len() < deque.capacity()`
    182    #[inline]
    183    unsafe fn push_unchecked(&mut self, element: T) {
    184        // SAFETY: Because of the precondition, it's guaranteed that there is space
    185        // in the logical array after the last element.
    186        unsafe { self.buffer_write(self.to_physical_idx(self.len), element) };
    187        // This can't overflow because `deque.len() < deque.capacity() <= usize::MAX`.
    188        self.len += 1;
    189    }
    190
    191    /// Prepends an element to the buffer.
    192    ///
    193    /// # Safety
    194    ///
    195    /// May only be called if `deque.len() < deque.capacity()`
    196    #[inline]
    197    unsafe fn push_front_unchecked(&mut self, element: T) {
    198        self.head = self.wrap_sub(self.head, 1);
    199        // SAFETY: Because of the precondition, it's guaranteed that there is space
    200        // in the logical array before the first element (where self.head is now).
    201        unsafe { self.buffer_write(self.head, element) };
    202        // This can't overflow because `deque.len() < deque.capacity() <= usize::MAX`.
    203        self.len += 1;
    204    }
    205
    206    /// Moves an element out of the buffer
    207    #[inline]
    208    unsafe fn buffer_read(&mut self, off: usize) -> T {
    209        unsafe { ptr::read(self.ptr().add(off)) }
    210    }
    211
    212    /// Writes an element into the buffer, moving it and returning a pointer to it.
    213    /// # Safety
    214    ///
    215    /// May only be called if `off < self.capacity()`.
    216    #[inline]
    217    unsafe fn buffer_write(&mut self, off: usize, value: T) -> &mut T {
    218        unsafe {
    219            let ptr = self.ptr().add(off);
    220            ptr::write(ptr, value);
    221            &mut *ptr
    222        }
    223    }
    224
    225    /// Returns a slice pointer into the buffer.
    226    /// `range` must lie inside `0..self.capacity()`.
    227    #[inline]
    228    unsafe fn buffer_range(&self, range: Range<usize>) -> *mut [T] {
    229        unsafe {
    230            ptr::slice_from_raw_parts_mut(self.ptr().add(range.start), range.end - range.start)
    231        }
    232    }
    233
    234    /// Returns `true` if the buffer is at full capacity.
    235    #[inline]
    236    fn is_full(&self) -> bool {
    237        self.len == self.capacity()
    238    }
    239
    240    /// Returns the index in the underlying buffer for a given logical element
    241    /// index + addend.
    242    #[inline]
    243    fn wrap_add(&self, idx: usize, addend: usize) -> usize {
    244        wrap_index(idx.wrapping_add(addend), self.capacity())
    245    }
    246
    247    #[inline]
    248    fn to_physical_idx(&self, idx: usize) -> usize {
    249        self.wrap_add(self.head, idx)
    250    }
    251
    252    /// Returns the index in the underlying buffer for a given logical element
    253    /// index - subtrahend.
    254    #[inline]
    255    fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize {
    256        wrap_index(idx.wrapping_sub(subtrahend).wrapping_add(self.capacity()), self.capacity())
    257    }
    258
    259    /// Get source, destination and count (like the arguments to [`ptr::copy_nonoverlapping`])
    260    /// for copying `count` values from index `src` to index `dst`.
    261    /// One of the ranges can wrap around the physical buffer, for this reason 2 triples are returned.
    262    ///
    263    /// Use of the word "ranges" specifically refers to `src..src + count` and `dst..dst + count`.
    264    ///
    265    /// # Safety
    266    ///
    267    /// - Ranges must not overlap: `src.abs_diff(dst) >= count`.
    268    /// - Ranges must be in bounds of the logical buffer: `src + count <= self.capacity()` and `dst + count <= self.capacity()`.
    269    /// - `head` must be in bounds: `head < self.capacity()`.
    270    #[cfg(not(no_global_oom_handling))]
    271    unsafe fn nonoverlapping_ranges(
    272        &mut self,
    273        src: usize,
    274        dst: usize,
    275        count: usize,
    276        head: usize,
    277    ) -> [(*const T, *mut T, usize); 2] {
    278        // "`src` and `dst` must be at least as far apart as `count`"
    279        debug_assert!(
    280            src.abs_diff(dst) >= count,
    281            "`src` and `dst` must not overlap. src={src} dst={dst} count={count}",
    282        );
    283        debug_assert!(
    284            src.max(dst) + count <= self.capacity(),
    285            "ranges must be in bounds. src={src} dst={dst} count={count} cap={}",
    286            self.capacity(),
    287        );
    288
    289        let wrapped_src = self.wrap_add(head, src);
    290        let wrapped_dst = self.wrap_add(head, dst);
    291
    292        let room_after_src = self.capacity() - wrapped_src;
    293        let room_after_dst = self.capacity() - wrapped_dst;
    294
    295        let src_wraps = room_after_src < count;
    296        let dst_wraps = room_after_dst < count;
    297
    298        // Wrapping occurs if `capacity` is contained within `wrapped_src..wrapped_src + count` or `wrapped_dst..wrapped_dst + count`.
    299        // Since these two ranges must not overlap as per the safety invariants of this function, only one range can wrap.
    300        debug_assert!(
    301            !(src_wraps && dst_wraps),
    302            "BUG: at most one of src and dst can wrap. src={src} dst={dst} count={count} cap={}",
    303            self.capacity(),
    304        );
    305
    306        unsafe {
    307            let ptr = self.ptr();
    308            let src_ptr = ptr.add(wrapped_src);
    309            let dst_ptr = ptr.add(wrapped_dst);
    310
    311            if src_wraps {
    312                [
    313                    (src_ptr, dst_ptr, room_after_src),
    314                    (ptr, dst_ptr.add(room_after_src), count - room_after_src),
    315                ]
    316            } else if dst_wraps {
    317                [
    318                    (src_ptr, dst_ptr, room_after_dst),
    319                    (src_ptr.add(room_after_dst), ptr, count - room_after_dst),
    320                ]
    321            } else {
    322                [
    323                    (src_ptr, dst_ptr, count),
    324                    // null pointers are fine as long as the count is 0
    325                    (ptr::null(), ptr::null_mut(), 0),
    326                ]
    327            }
    328        }
    329    }
    330
    331    /// Copies a contiguous block of memory len long from src to dst
    332    #[inline]
    333    unsafe fn copy(&mut self, src: usize, dst: usize, len: usize) {
    334        debug_assert!(
    335            dst + len <= self.capacity(),
    336            "cpy dst={} src={} len={} cap={}",
    337            dst,
    338            src,
    339            len,
    340            self.capacity()
    341        );
    342        debug_assert!(
    343            src + len <= self.capacity(),
    344            "cpy dst={} src={} len={} cap={}",
    345            dst,
    346            src,
    347            len,
    348            self.capacity()
    349        );
    350        unsafe {
    351            ptr::copy(self.ptr().add(src), self.ptr().add(dst), len);
    352        }
    353    }
    354
    355    /// Copies a contiguous block of memory len long from src to dst
    356    #[inline]
    357    unsafe fn copy_nonoverlapping(&mut self, src: usize, dst: usize, len: usize) {
    358        debug_assert!(
    359            dst + len <= self.capacity(),
    360            "cno dst={} src={} len={} cap={}",
    361            dst,
    362            src,
    363            len,
    364            self.capacity()
    365        );
    366        debug_assert!(
    367            src + len <= self.capacity(),
    368            "cno dst={} src={} len={} cap={}",
    369            dst,
    370            src,
    371            len,
    372            self.capacity()
    373        );
    374        unsafe {
    375            ptr::copy_nonoverlapping(self.ptr().add(src), self.ptr().add(dst), len);
    376        }
    377    }
    378
    379    /// Copies a potentially wrapping block of memory len long from src to dest.
    380    /// (abs(dst - src) + len) must be no larger than capacity() (There must be at
    381    /// most one continuous overlapping region between src and dest).
    382    unsafe fn wrap_copy(&mut self, src: usize, dst: usize, len: usize) {
    383        debug_assert!(
    384            cmp::min(src.abs_diff(dst), self.capacity() - src.abs_diff(dst)) + len
    385                <= self.capacity(),
    386            "wrc dst={} src={} len={} cap={}",
    387            dst,
    388            src,
    389            len,
    390            self.capacity()
    391        );
    392
    393        // If T is a ZST, don't do any copying.
    394        if T::IS_ZST || src == dst || len == 0 {
    395            return;
    396        }
    397
    398        let dst_after_src = self.wrap_sub(dst, src) < len;
    399
    400        let src_pre_wrap_len = self.capacity() - src;
    401        let dst_pre_wrap_len = self.capacity() - dst;
    402        let src_wraps = src_pre_wrap_len < len;
    403        let dst_wraps = dst_pre_wrap_len < len;
    404
    405        match (dst_after_src, src_wraps, dst_wraps) {
    406            (_, false, false) => {
    407                // src doesn't wrap, dst doesn't wrap
    408                //
    409                //        S . . .
    410                // 1 [_ _ A A B B C C _]
    411                // 2 [_ _ A A A A B B _]
    412                //            D . . .
    413                //
    414                unsafe {
    415                    self.copy(src, dst, len);
    416                }
    417            }
    418            (false, false, true) => {
    419                // dst before src, src doesn't wrap, dst wraps
    420                //
    421                //    S . . .
    422                // 1 [A A B B _ _ _ C C]
    423                // 2 [A A B B _ _ _ A A]
    424                // 3 [B B B B _ _ _ A A]
    425                //    . .           D .
    426                //
    427                unsafe {
    428                    self.copy(src, dst, dst_pre_wrap_len);
    429                    self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len);
    430                }
    431            }
    432            (true, false, true) => {
    433                // src before dst, src doesn't wrap, dst wraps
    434                //
    435                //              S . . .
    436                // 1 [C C _ _ _ A A B B]
    437                // 2 [B B _ _ _ A A B B]
    438                // 3 [B B _ _ _ A A A A]
    439                //    . .           D .
    440                //
    441                unsafe {
    442                    self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len);
    443                    self.copy(src, dst, dst_pre_wrap_len);
    444                }
    445            }
    446            (false, true, false) => {
    447                // dst before src, src wraps, dst doesn't wrap
    448                //
    449                //    . .           S .
    450                // 1 [C C _ _ _ A A B B]
    451                // 2 [C C _ _ _ B B B B]
    452                // 3 [C C _ _ _ B B C C]
    453                //              D . . .
    454                //
    455                unsafe {
    456                    self.copy(src, dst, src_pre_wrap_len);
    457                    self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len);
    458                }
    459            }
    460            (true, true, false) => {
    461                // src before dst, src wraps, dst doesn't wrap
    462                //
    463                //    . .           S .
    464                // 1 [A A B B _ _ _ C C]
    465                // 2 [A A A A _ _ _ C C]
    466                // 3 [C C A A _ _ _ C C]
    467                //    D . . .
    468                //
    469                unsafe {
    470                    self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len);
    471                    self.copy(src, dst, src_pre_wrap_len);
    472                }
    473            }
    474            (false, true, true) => {
    475                // dst before src, src wraps, dst wraps
    476                //
    477                //    . . .         S .
    478                // 1 [A B C D _ E F G H]
    479                // 2 [A B C D _ E G H H]
    480                // 3 [A B C D _ E G H A]
    481                // 4 [B C C D _ E G H A]
    482                //    . .         D . .
    483                //
    484                debug_assert!(dst_pre_wrap_len > src_pre_wrap_len);
    485                let delta = dst_pre_wrap_len - src_pre_wrap_len;
    486                unsafe {
    487                    self.copy(src, dst, src_pre_wrap_len);
    488                    self.copy(0, dst + src_pre_wrap_len, delta);
    489                    self.copy(delta, 0, len - dst_pre_wrap_len);
    490                }
    491            }
    492            (true, true, true) => {
    493                // src before dst, src wraps, dst wraps
    494                //
    495                //    . .         S . .
    496                // 1 [A B C D _ E F G H]
    497                // 2 [A A B D _ E F G H]
    498                // 3 [H A B D _ E F G H]
    499                // 4 [H A B D _ E F F G]
    500                //    . . .         D .
    501                //
    502                debug_assert!(src_pre_wrap_len > dst_pre_wrap_len);
    503                let delta = src_pre_wrap_len - dst_pre_wrap_len;
    504                unsafe {
    505                    self.copy(0, delta, len - src_pre_wrap_len);
    506                    self.copy(self.capacity() - delta, 0, delta);
    507                    self.copy(src, dst, dst_pre_wrap_len);
    508                }
    509            }
    510        }
    511    }
    512
    513    /// Copies all values from `src` to `dst`, wrapping around if needed.
    514    /// Assumes capacity is sufficient.
    515    #[inline]
    516    unsafe fn copy_slice(&mut self, dst: usize, src: &[T]) {
    517        debug_assert!(src.len() <= self.capacity());
    518        let head_room = self.capacity() - dst;
    519        if src.len() <= head_room {
    520            unsafe {
    521                ptr::copy_nonoverlapping(src.as_ptr(), self.ptr().add(dst), src.len());
    522            }
    523        } else {
    524            let (left, right) = src.split_at(head_room);
    525            unsafe {
    526                ptr::copy_nonoverlapping(left.as_ptr(), self.ptr().add(dst), left.len());
    527                ptr::copy_nonoverlapping(right.as_ptr(), self.ptr(), right.len());
    528            }
    529        }
    530    }
    531
    532    /// Copies all values from `src` to `dst` in reversed order, wrapping around if needed.
    533    /// Assumes capacity is sufficient.
    534    /// Equivalent to calling [`VecDeque::copy_slice`] with a [reversed](https://doc.rust-lang.org/std/primitive.slice.html#method.reverse) slice.
    535    #[inline]
    536    unsafe fn copy_slice_reversed(&mut self, dst: usize, src: &[T]) {
    537        /// # Safety
    538        ///
    539        /// See [`ptr::copy_nonoverlapping`].
    540        unsafe fn copy_nonoverlapping_reversed<T>(src: *const T, dst: *mut T, count: usize) {
    541            for i in 0..count {
    542                unsafe { ptr::copy_nonoverlapping(src.add(count - 1 - i), dst.add(i), 1) };
    543            }
    544        }
    545
    546        debug_assert!(src.len() <= self.capacity());
    547        let head_room = self.capacity() - dst;
    548        if src.len() <= head_room {
    549            unsafe {
    550                copy_nonoverlapping_reversed(src.as_ptr(), self.ptr().add(dst), src.len());
    551            }
    552        } else {
    553            let (left, right) = src.split_at(src.len() - head_room);
    554            unsafe {
    555                copy_nonoverlapping_reversed(right.as_ptr(), self.ptr().add(dst), right.len());
    556                copy_nonoverlapping_reversed(left.as_ptr(), self.ptr(), left.len());
    557            }
    558        }
    559    }
    560
    561    /// Writes all values from `iter` to `dst`.
    562    ///
    563    /// # Safety
    564    ///
    565    /// Assumes no wrapping around happens.
    566    /// Assumes capacity is sufficient.
    567    #[inline]
    568    unsafe fn write_iter(
    569        &mut self,
    570        dst: usize,
    571        iter: impl Iterator<Item = T>,
    572        written: &mut usize,
    573    ) {
    574        iter.enumerate().for_each(|(i, element)| unsafe {
    575            self.buffer_write(dst + i, element);
    576            *written += 1;
    577        });
    578    }
    579
    580    /// Writes all values from `iter` to `dst`, wrapping
    581    /// at the end of the buffer and returns the number
    582    /// of written values.
    583    ///
    584    /// # Safety
    585    ///
    586    /// Assumes that `iter` yields at most `len` items.
    587    /// Assumes capacity is sufficient.
    588    unsafe fn write_iter_wrapping(
    589        &mut self,
    590        dst: usize,
    591        mut iter: impl Iterator<Item = T>,
    592        len: usize,
    593    ) -> usize {
    594        struct Guard<'a, T, A: Allocator> {
    595            deque: &'a mut VecDeque<T, A>,
    596            written: usize,
    597        }
    598
    599        impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> {
    600            fn drop(&mut self) {
    601                self.deque.len += self.written;
    602            }
    603        }
    604
    605        let head_room = self.capacity() - dst;
    606
    607        let mut guard = Guard { deque: self, written: 0 };
    608
    609        if head_room >= len {
    610            unsafe { guard.deque.write_iter(dst, iter, &mut guard.written) };
    611        } else {
    612            unsafe {
    613                guard.deque.write_iter(
    614                    dst,
    615                    ByRefSized(&mut iter).take(head_room),
    616                    &mut guard.written,
    617                );
    618                guard.deque.write_iter(0, iter, &mut guard.written)
    619            };
    620        }
    621
    622        guard.written
    623    }
    624
    625    /// Frobs the head and tail sections around to handle the fact that we
    626    /// just reallocated. Unsafe because it trusts old_capacity.
    627    #[inline]
    628    unsafe fn handle_capacity_increase(&mut self, old_capacity: usize) {
    629        let new_capacity = self.capacity();
    630        debug_assert!(new_capacity >= old_capacity);
    631
    632        // Move the shortest contiguous section of the ring buffer
    633        //
    634        // H := head
    635        // L := last element (`self.to_physical_idx(self.len - 1)`)
    636        //
    637        //    H             L
    638        //   [o o o o o o o o ]
    639        //    H             L
    640        // A [o o o o o o o o . . . . . . . . ]
    641        //        L H
    642        //   [o o o o o o o o ]
    643        //          H             L
    644        // B [. . . o o o o o o o o . . . . . ]
    645        //              L H
    646        //   [o o o o o o o o ]
    647        //              L                 H
    648        // C [o o o o o o . . . . . . . . o o ]
    649
    650        // can't use is_contiguous() because the capacity is already updated.
    651        if self.head <= old_capacity - self.len {
    652            // A
    653            // Nop
    654        } else {
    655            let head_len = old_capacity - self.head;
    656            let tail_len = self.len - head_len;
    657            if head_len > tail_len && new_capacity - old_capacity >= tail_len {
    658                // B
    659                unsafe {
    660                    self.copy_nonoverlapping(0, old_capacity, tail_len);
    661                }
    662            } else {
    663                // C
    664                let new_head = new_capacity - head_len;
    665                unsafe {
    666                    // can't use copy_nonoverlapping here, because if e.g. head_len = 2
    667                    // and new_capacity = old_capacity + 1, then the heads overlap.
    668                    self.copy(self.head, new_head, head_len);
    669                }
    670                self.head = new_head;
    671            }
    672        }
    673        debug_assert!(self.head < self.capacity() || self.capacity() == 0);
    674    }
    675
    676    /// Creates an iterator which uses a closure to determine if an element in the range should be removed.
    677    ///
    678    /// If the closure returns `true`, the element is removed from the deque and yielded. If the closure
    679    /// returns `false`, or panics, the element remains in the deque and will not be yielded.
    680    ///
    681    /// Only elements that fall in the provided range are considered for extraction, but any elements
    682    /// after the range will still have to be moved if any element has been extracted.
    683    ///
    684    /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
    685    /// or the iteration short-circuits, then the remaining elements will be retained.
    686    /// Use `extract_if().for_each(drop)` if you do not need the returned iterator,
    687    /// or [`retain_mut`] with a negated predicate if you also do not need to restrict the range.
    688    ///
    689    /// [`retain_mut`]: VecDeque::retain_mut
    690    ///
    691    /// Using this method is equivalent to the following code:
    692    ///
    693    /// ```
    694    /// #![feature(vec_deque_extract_if)]
    695    /// # use std::collections::VecDeque;
    696    /// # let some_predicate = |x: &mut i32| { *x % 2 == 1 };
    697    /// # let mut deq: VecDeque<_> = (0..10).collect();
    698    /// # let mut deq2 = deq.clone();
    699    /// # let range = 1..5;
    700    /// let mut i = range.start;
    701    /// let end_items = deq.len() - range.end;
    702    /// # let mut extracted = vec![];
    703    ///
    704    /// while i < deq.len() - end_items {
    705    ///     if some_predicate(&mut deq[i]) {
    706    ///         let val = deq.remove(i).unwrap();
    707    ///         // your code here
    708    /// #         extracted.push(val);
    709    ///     } else {
    710    ///         i += 1;
    711    ///     }
    712    /// }
    713    ///
    714    /// # let extracted2: Vec<_> = deq2.extract_if(range, some_predicate).collect();
    715    /// # assert_eq!(deq, deq2);
    716    /// # assert_eq!(extracted, extracted2);
    717    /// ```
    718    ///
    719    /// But `extract_if` is easier to use. `extract_if` is also more efficient,
    720    /// because it can backshift the elements of the array in bulk.
    721    ///
    722    /// The iterator also lets you mutate the value of each element in the
    723    /// closure, regardless of whether you choose to keep or remove it.
    724    ///
    725    /// # Panics
    726    ///
    727    /// If `range` is out of bounds.
    728    ///
    729    /// # Examples
    730    ///
    731    /// Splitting a deque into even and odd values, reusing the original deque:
    732    ///
    733    /// ```
    734    /// #![feature(vec_deque_extract_if)]
    735    /// use std::collections::VecDeque;
    736    ///
    737    /// let mut numbers = VecDeque::from([1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]);
    738    ///
    739    /// let evens = numbers.extract_if(.., |x| *x % 2 == 0).collect::<VecDeque<_>>();
    740    /// let odds = numbers;
    741    ///
    742    /// assert_eq!(evens, VecDeque::from([2, 4, 6, 8, 14]));
    743    /// assert_eq!(odds, VecDeque::from([1, 3, 5, 9, 11, 13, 15]));
    744    /// ```
    745    ///
    746    /// Using the range argument to only process a part of the deque:
    747    ///
    748    /// ```
    749    /// #![feature(vec_deque_extract_if)]
    750    /// use std::collections::VecDeque;
    751    ///
    752    /// let mut items = VecDeque::from([0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2]);
    753    /// let ones = items.extract_if(7.., |x| *x == 1).collect::<VecDeque<_>>();
    754    /// assert_eq!(items, VecDeque::from([0, 0, 0, 0, 0, 0, 0, 2, 2, 2]));
    755    /// assert_eq!(ones.len(), 3);
    756    /// ```
    757    #[unstable(feature = "vec_deque_extract_if", issue = "147750")]
    758    pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, A>
    759    where
    760        F: FnMut(&mut T) -> bool,
    761        R: RangeBounds<usize>,
    762    {
    763        ExtractIf::new(self, filter, range)
    764    }
    765}
    766
    767impl<T> VecDeque<T> {
    768    /// Creates an empty deque.
    769    ///
    770    /// # Examples
    771    ///
    772    /// ```
    773    /// use std::collections::VecDeque;
    774    ///
    775    /// let deque: VecDeque<u32> = VecDeque::new();
    776    /// ```
    777    #[inline]
    778    #[stable(feature = "rust1", since = "1.0.0")]
    779    #[rustc_const_stable(feature = "const_vec_deque_new", since = "1.68.0")]
    780    #[must_use]
    781    pub const fn new() -> VecDeque<T> {
    782        // FIXME(const-hack): This should just be `VecDeque::new_in(Global)` once that hits stable.
    783        VecDeque { head: 0, len: 0, buf: RawVec::new() }
    784    }
    785
    786    /// Creates an empty deque with space for at least `capacity` elements.
    787    ///
    788    /// # Examples
    789    ///
    790    /// ```
    791    /// use std::collections::VecDeque;
    792    ///
    793    /// let deque: VecDeque<u32> = VecDeque::with_capacity(10);
    794    /// ```
    795    #[inline]
    796    #[stable(feature = "rust1", since = "1.0.0")]
    797    #[must_use]
    798    pub fn with_capacity(capacity: usize) -> VecDeque<T> {
    799        Self::with_capacity_in(capacity, Global)
    800    }
    801
    802    /// Creates an empty deque with space for at least `capacity` elements.
    803    ///
    804    /// # Errors
    805    ///
    806    /// Returns an error if the capacity exceeds `isize::MAX` _bytes_,
    807    /// or if the allocator reports allocation failure.
    808    ///
    809    /// # Examples
    810    ///
    811    /// ```
    812    /// # #![feature(try_with_capacity)]
    813    /// # #[allow(unused)]
    814    /// # fn example() -> Result<(), std::collections::TryReserveError> {
    815    /// use std::collections::VecDeque;
    816    ///
    817    /// let deque: VecDeque<u32> = VecDeque::try_with_capacity(10)?;
    818    /// # Ok(()) }
    819    /// ```
    820    #[inline]
    821    #[unstable(feature = "try_with_capacity", issue = "91913")]
    822    pub fn try_with_capacity(capacity: usize) -> Result<VecDeque<T>, TryReserveError> {
    823        Ok(VecDeque { head: 0, len: 0, buf: RawVec::try_with_capacity_in(capacity, Global)? })
    824    }
    825}
    826
    827impl<T, A: Allocator> VecDeque<T, A> {
    828    /// Creates an empty deque.
    829    ///
    830    /// # Examples
    831    ///
    832    /// ```
    833    /// use std::collections::VecDeque;
    834    ///
    835    /// let deque: VecDeque<u32> = VecDeque::new();
    836    /// ```
    837    #[inline]
    838    #[unstable(feature = "allocator_api", issue = "32838")]
    839    pub const fn new_in(alloc: A) -> VecDeque<T, A> {
    840        VecDeque { head: 0, len: 0, buf: RawVec::new_in(alloc) }
    841    }
    842
    843    /// Creates an empty deque with space for at least `capacity` elements.
    844    ///
    845    /// # Examples
    846    ///
    847    /// ```
    848    /// use std::collections::VecDeque;
    849    ///
    850    /// let deque: VecDeque<u32> = VecDeque::with_capacity(10);
    851    /// ```
    852    #[unstable(feature = "allocator_api", issue = "32838")]
    853    pub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A> {
    854        VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) }
    855    }
    856
    857    /// Creates a `VecDeque` from a raw allocation, when the initialized
    858    /// part of that allocation forms a *contiguous* subslice thereof.
    859    ///
    860    /// For use by `vec::IntoIter::into_vecdeque`
    861    ///
    862    /// # Safety
    863    ///
    864    /// All the usual requirements on the allocated memory like in
    865    /// `Vec::from_raw_parts_in`, but takes a *range* of elements that are
    866    /// initialized rather than only supporting `0..len`.  Requires that
    867    /// `initialized.start` ≤ `initialized.end` ≤ `capacity`.
    868    #[inline]
    869    #[cfg(not(test))]
    870    pub(crate) unsafe fn from_contiguous_raw_parts_in(
    871        ptr: *mut T,
    872        initialized: Range<usize>,
    873        capacity: usize,
    874        alloc: A,
    875    ) -> Self {
    876        debug_assert!(initialized.start <= initialized.end);
    877        debug_assert!(initialized.end <= capacity);
    878
    879        // SAFETY: Our safety precondition guarantees the range length won't wrap,
    880        // and that the allocation is valid for use in `RawVec`.
    881        unsafe {
    882            VecDeque {
    883                head: initialized.start,
    884                len: initialized.end.unchecked_sub(initialized.start),
    885                buf: RawVec::from_raw_parts_in(ptr, capacity, alloc),
    886            }
    887        }
    888    }
    889
    890    /// Provides a reference to the element at the given index.
    891    ///
    892    /// Element at index 0 is the front of the queue.
    893    ///
    894    /// # Examples
    895    ///
    896    /// ```
    897    /// use std::collections::VecDeque;
    898    ///
    899    /// let mut buf = VecDeque::new();
    900    /// buf.push_back(3);
    901    /// buf.push_back(4);
    902    /// buf.push_back(5);
    903    /// buf.push_back(6);
    904    /// assert_eq!(buf.get(1), Some(&4));
    905    /// ```
    906    #[stable(feature = "rust1", since = "1.0.0")]
    907    pub fn get(&self, index: usize) -> Option<&T> {
    908        if index < self.len {
    909            let idx = self.to_physical_idx(index);
    910            unsafe { Some(&*self.ptr().add(idx)) }
    911        } else {
    912            None
    913        }
    914    }
    915
    916    /// Provides a mutable reference to the element at the given index.
    917    ///
    918    /// Element at index 0 is the front of the queue.
    919    ///
    920    /// # Examples
    921    ///
    922    /// ```
    923    /// use std::collections::VecDeque;
    924    ///
    925    /// let mut buf = VecDeque::new();
    926    /// buf.push_back(3);
    927    /// buf.push_back(4);
    928    /// buf.push_back(5);
    929    /// buf.push_back(6);
    930    /// assert_eq!(buf[1], 4);
    931    /// if let Some(elem) = buf.get_mut(1) {
    932    ///     *elem = 7;
    933    /// }
    934    /// assert_eq!(buf[1], 7);
    935    /// ```
    936    #[stable(feature = "rust1", since = "1.0.0")]
    937    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
    938        if index < self.len {
    939            let idx = self.to_physical_idx(index);
    940            unsafe { Some(&mut *self.ptr().add(idx)) }
    941        } else {
    942            None
    943        }
    944    }
    945
    946    /// Swaps elements at indices `i` and `j`.
    947    ///
    948    /// `i` and `j` may be equal.
    949    ///
    950    /// Element at index 0 is the front of the queue.
    951    ///
    952    /// # Panics
    953    ///
    954    /// Panics if either index is out of bounds.
    955    ///
    956    /// # Examples
    957    ///
    958    /// ```
    959    /// use std::collections::VecDeque;
    960    ///
    961    /// let mut buf = VecDeque::new();
    962    /// buf.push_back(3);
    963    /// buf.push_back(4);
    964    /// buf.push_back(5);
    965    /// assert_eq!(buf, [3, 4, 5]);
    966    /// buf.swap(0, 2);
    967    /// assert_eq!(buf, [5, 4, 3]);
    968    /// ```
    969    #[stable(feature = "rust1", since = "1.0.0")]
    970    pub fn swap(&mut self, i: usize, j: usize) {
    971        assert!(i < self.len());
    972        assert!(j < self.len());
    973        let ri = self.to_physical_idx(i);
    974        let rj = self.to_physical_idx(j);
    975        unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) }
    976    }
    977
    978    /// Returns the number of elements the deque can hold without
    979    /// reallocating.
    980    ///
    981    /// # Examples
    982    ///
    983    /// ```
    984    /// use std::collections::VecDeque;
    985    ///
    986    /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
    987    /// assert!(buf.capacity() >= 10);
    988    /// ```
    989    #[inline]
    990    #[stable(feature = "rust1", since = "1.0.0")]
    991    pub fn capacity(&self) -> usize {
    992        if T::IS_ZST { usize::MAX } else { self.buf.capacity() }
    993    }
    994
    995    /// Reserves the minimum capacity for at least `additional` more elements to be inserted in the
    996    /// given deque. Does nothing if the capacity is already sufficient.
    997    ///
    998    /// Note that the allocator may give the collection more space than it requests. Therefore
    999    /// capacity can not be relied upon to be precisely minimal. Prefer [`reserve`] if future
    1000    /// insertions are expected.
    1001    ///
    1002    /// # Panics
    1003    ///
    1004    /// Panics if the new capacity overflows `usize`.
    1005    ///
    1006    /// # Examples
    1007    ///
    1008    /// ```
    1009    /// use std::collections::VecDeque;
    1010    ///
    1011    /// let mut buf: VecDeque<i32> = [1].into();
    1012    /// buf.reserve_exact(10);
    1013    /// assert!(buf.capacity() >= 11);
    1014    /// ```
    1015    ///
    1016    /// [`reserve`]: VecDeque::reserve
    1017    #[stable(feature = "rust1", since = "1.0.0")]
    1018    pub fn reserve_exact(&mut self, additional: usize) {
    1019        let new_cap = self.len.checked_add(additional).expect("capacity overflow");
    1020        let old_cap = self.capacity();
    1021
    1022        if new_cap > old_cap {
    1023            self.buf.reserve_exact(self.len, additional);
    1024            unsafe {
    1025                self.handle_capacity_increase(old_cap);
    1026            }
    1027        }
    1028    }
    1029
    1030    /// Reserves capacity for at least `additional` more elements to be inserted in the given
    1031    /// deque. The collection may reserve more space to speculatively avoid frequent reallocations.
    1032    ///
    1033    /// # Panics
    1034    ///
    1035    /// Panics if the new capacity overflows `usize`.
    1036    ///
    1037    /// # Examples
    1038    ///
    1039    /// ```
    1040    /// use std::collections::VecDeque;
    1041    ///
    1042    /// let mut buf: VecDeque<i32> = [1].into();
    1043    /// buf.reserve(10);
    1044    /// assert!(buf.capacity() >= 11);
    1045    /// ```
    1046    #[stable(feature = "rust1", since = "1.0.0")]
    1047    #[cfg_attr(not(test), rustc_diagnostic_item = "vecdeque_reserve")]
    1048    pub fn reserve(&mut self, additional: usize) {
    1049        let new_cap = self.len.checked_add(additional).expect("capacity overflow");
    1050        let old_cap = self.capacity();
    1051
    1052        if new_cap > old_cap {
    1053            // we don't need to reserve_exact(), as the size doesn't have
    1054            // to be a power of 2.
    1055            self.buf.reserve(self.len, additional);
    1056            unsafe {
    1057                self.handle_capacity_increase(old_cap);
    1058            }
    1059        }
    1060    }
    1061
    1062    /// Tries to reserve the minimum capacity for at least `additional` more elements to
    1063    /// be inserted in the given deque. After calling `try_reserve_exact`,
    1064    /// capacity will be greater than or equal to `self.len() + additional` if
    1065    /// it returns `Ok(())`. Does nothing if the capacity is already sufficient.
    1066    ///
    1067    /// Note that the allocator may give the collection more space than it
    1068    /// requests. Therefore, capacity can not be relied upon to be precisely
    1069    /// minimal. Prefer [`try_reserve`] if future insertions are expected.
    1070    ///
    1071    /// [`try_reserve`]: VecDeque::try_reserve
    1072    ///
    1073    /// # Errors
    1074    ///
    1075    /// If the capacity overflows `usize`, or the allocator reports a failure, then an error
    1076    /// is returned.
    1077    ///
    1078    /// # Examples
    1079    ///
    1080    /// ```
    1081    /// use std::collections::TryReserveError;
    1082    /// use std::collections::VecDeque;
    1083    ///
    1084    /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    1085    ///     let mut output = VecDeque::new();
    1086    ///
    1087    ///     // Pre-reserve the memory, exiting if we can't
    1088    ///     output.try_reserve_exact(data.len())?;
    1089    ///
    1090    ///     // Now we know this can't OOM(Out-Of-Memory) in the middle of our complex work
    1091    ///     output.extend(data.iter().map(|&val| {
    1092    ///         val * 2 + 5 // very complicated
    1093    ///     }));
    1094    ///
    1095    ///     Ok(output)
    1096    /// }
    1097    /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
    1098    /// ```
    1099    #[stable(feature = "try_reserve", since = "1.57.0")]
    1100    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
    1101        let new_cap =
    1102            self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?;
    1103        let old_cap = self.capacity();
    1104
    1105        if new_cap > old_cap {
    1106            self.buf.try_reserve_exact(self.len, additional)?;
    1107            unsafe {
    1108                self.handle_capacity_increase(old_cap);
    1109            }
    1110        }
    1111        Ok(())
    1112    }
    1113
    1114    /// Tries to reserve capacity for at least `additional` more elements to be inserted
    1115    /// in the given deque. The collection may reserve more space to speculatively avoid
    1116    /// frequent reallocations. After calling `try_reserve`, capacity will be
    1117    /// greater than or equal to `self.len() + additional` if it returns
    1118    /// `Ok(())`. Does nothing if capacity is already sufficient. This method
    1119    /// preserves the contents even if an error occurs.
    1120    ///
    1121    /// # Errors
    1122    ///
    1123    /// If the capacity overflows `usize`, or the allocator reports a failure, then an error
    1124    /// is returned.
    1125    ///
    1126    /// # Examples
    1127    ///
    1128    /// ```
    1129    /// use std::collections::TryReserveError;
    1130    /// use std::collections::VecDeque;
    1131    ///
    1132    /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    1133    ///     let mut output = VecDeque::new();
    1134    ///
    1135    ///     // Pre-reserve the memory, exiting if we can't
    1136    ///     output.try_reserve(data.len())?;
    1137    ///
    1138    ///     // Now we know this can't OOM in the middle of our complex work
    1139    ///     output.extend(data.iter().map(|&val| {
    1140    ///         val * 2 + 5 // very complicated
    1141    ///     }));
    1142    ///
    1143    ///     Ok(output)
    1144    /// }
    1145    /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
    1146    /// ```
    1147    #[stable(feature = "try_reserve", since = "1.57.0")]
    1148    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
    1149        let new_cap =
    1150            self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?;
    1151        let old_cap = self.capacity();
    1152
    1153        if new_cap > old_cap {
    1154            self.buf.try_reserve(self.len, additional)?;
    1155            unsafe {
    1156                self.handle_capacity_increase(old_cap);
    1157            }
    1158        }
    1159        Ok(())
    1160    }
    1161
    1162    /// Shrinks the capacity of the deque as much as possible.
    1163    ///
    1164    /// It will drop down as close as possible to the length but the allocator may still inform the
    1165    /// deque that there is space for a few more elements.
    1166    ///
    1167    /// # Examples
    1168    ///
    1169    /// ```
    1170    /// use std::collections::VecDeque;
    1171    ///
    1172    /// let mut buf = VecDeque::with_capacity(15);
    1173    /// buf.extend(0..4);
    1174    /// assert_eq!(buf.capacity(), 15);
    1175    /// buf.shrink_to_fit();
    1176    /// assert!(buf.capacity() >= 4);
    1177    /// ```
    1178    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    1179    pub fn shrink_to_fit(&mut self) {
    1180        self.shrink_to(0);
    1181    }
    1182
    1183    /// Shrinks the capacity of the deque with a lower bound.
    1184    ///
    1185    /// The capacity will remain at least as large as both the length
    1186    /// and the supplied value.
    1187    ///
    1188    /// If the current capacity is less than the lower limit, this is a no-op.
    1189    ///
    1190    /// # Examples
    1191    ///
    1192    /// ```
    1193    /// use std::collections::VecDeque;
    1194    ///
    1195    /// let mut buf = VecDeque::with_capacity(15);
    1196    /// buf.extend(0..4);
    1197    /// assert_eq!(buf.capacity(), 15);
    1198    /// buf.shrink_to(6);
    1199    /// assert!(buf.capacity() >= 6);
    1200    /// buf.shrink_to(0);
    1201    /// assert!(buf.capacity() >= 4);
    1202    /// ```
    1203    #[stable(feature = "shrink_to", since = "1.56.0")]
    1204    pub fn shrink_to(&mut self, min_capacity: usize) {
    1205        let target_cap = min_capacity.max(self.len);
    1206
    1207        // never shrink ZSTs
    1208        if T::IS_ZST || self.capacity() <= target_cap {
    1209            return;
    1210        }
    1211
    1212        // There are three cases of interest:
    1213        //   All elements are out of desired bounds
    1214        //   Elements are contiguous, and tail is out of desired bounds
    1215        //   Elements are discontiguous
    1216        //
    1217        // At all other times, element positions are unaffected.
    1218
    1219        // `head` and `len` are at most `isize::MAX` and `target_cap < self.capacity()`, so nothing can
    1220        // overflow.
    1221        let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len));
    1222        // Used in the drop guard below.
    1223        let old_head = self.head;
    1224
    1225        if self.len == 0 {
    1226            self.head = 0;
    1227        } else if self.head >= target_cap && tail_outside {
    1228            // Head and tail are both out of bounds, so copy all of them to the front.
    1229            //
    1230            //  H := head
    1231            //  L := last element
    1232            //                    H           L
    1233            //   [. . . . . . . . o o o o o o o . ]
    1234            //    H           L
    1235            //   [o o o o o o o . ]
    1236            unsafe {
    1237                // nonoverlapping because `self.head >= target_cap >= self.len`.
    1238                self.copy_nonoverlapping(self.head, 0, self.len);
    1239            }
    1240            self.head = 0;
    1241        } else if self.head < target_cap && tail_outside {
    1242            // Head is in bounds, tail is out of bounds.
    1243            // Copy the overflowing part to the beginning of the
    1244            // buffer. This won't overlap because `target_cap >= self.len`.
    1245            //
    1246            //  H := head
    1247            //  L := last element
    1248            //          H           L
    1249            //   [. . . o o o o o o o . . . . . . ]
    1250            //      L   H
    1251            //   [o o . o o o o o ]
    1252            let len = self.head + self.len - target_cap;
    1253            unsafe {
    1254                self.copy_nonoverlapping(target_cap, 0, len);
    1255            }
    1256        } else if !self.is_contiguous() {
    1257            // The head slice is at least partially out of bounds, tail is in bounds.
    1258            // Copy the head backwards so it lines up with the target capacity.
    1259            // This won't overlap because `target_cap >= self.len`.
    1260            //
    1261            //  H := head
    1262            //  L := last element
    1263            //            L                   H
    1264            //   [o o o o o . . . . . . . . . o o ]
    1265            //            L   H
    1266            //   [o o o o o . o o ]
    1267            let head_len = self.capacity() - self.head;
    1268            let new_head = target_cap - head_len;
    1269            unsafe {
    1270                // can't use `copy_nonoverlapping()` here because the new and old
    1271                // regions for the head might overlap.
    1272                self.copy(self.head, new_head, head_len);
    1273            }
    1274            self.head = new_head;
    1275        }
    1276
    1277        struct Guard<'a, T, A: Allocator> {
    1278            deque: &'a mut VecDeque<T, A>,
    1279            old_head: usize,
    1280            target_cap: usize,
    1281        }
    1282
    1283        impl<T, A: Allocator> Drop for Guard<'_, T, A> {
    1284            #[cold]
    1285            fn drop(&mut self) {
    1286                unsafe {
    1287                    // SAFETY: This is only called if `buf.shrink_to_fit` unwinds,
    1288                    // which is the only time it's safe to call `abort_shrink`.
    1289                    self.deque.abort_shrink(self.old_head, self.target_cap)
    1290                }
    1291            }
    1292        }
    1293
    1294        let guard = Guard { deque: self, old_head, target_cap };
    1295
    1296        guard.deque.buf.shrink_to_fit(target_cap);
    1297
    1298        // Don't drop the guard if we didn't unwind.
    1299        mem::forget(guard);
    1300
    1301        debug_assert!(self.head < self.capacity() || self.capacity() == 0);
    1302        debug_assert!(self.len <= self.capacity());
    1303    }
    1304
    1305    /// Reverts the deque back into a consistent state in case `shrink_to` failed.
    1306    /// This is necessary to prevent UB if the backing allocator returns an error
    1307    /// from `shrink` and `handle_alloc_error` subsequently unwinds (see #123369).
    1308    ///
    1309    /// `old_head` refers to the head index before `shrink_to` was called. `target_cap`
    1310    /// is the capacity that it was trying to shrink to.
    1311    unsafe fn abort_shrink(&mut self, old_head: usize, target_cap: usize) {
    1312        // Moral equivalent of self.head + self.len <= target_cap. Won't overflow
    1313        // because `self.len <= target_cap`.
    1314        if self.head <= target_cap - self.len {
    1315            // The deque's buffer is contiguous, so no need to copy anything around.
    1316            return;
    1317        }
    1318
    1319        // `shrink_to` already copied the head to fit into the new capacity, so this won't overflow.
    1320        let head_len = target_cap - self.head;
    1321        // `self.head > target_cap - self.len` => `self.len > target_cap - self.head =: head_len` so this must be positive.
    1322        let tail_len = self.len - head_len;
    1323
    1324        if tail_len <= cmp::min(head_len, self.capacity() - target_cap) {
    1325            // There's enough spare capacity to copy the tail to the back (because `tail_len < self.capacity() - target_cap`),
    1326            // and copying the tail should be cheaper than copying the head (because `tail_len <= head_len`).
    1327
    1328            unsafe {
    1329                // The old tail and the new tail can't overlap because the head slice lies between them. The
    1330                // head slice ends at `target_cap`, so that's where we copy to.
    1331                self.copy_nonoverlapping(0, target_cap, tail_len);
    1332            }
    1333        } else {
    1334            // Either there's not enough spare capacity to make the deque contiguous, or the head is shorter than the tail
    1335            // (and therefore hopefully cheaper to copy).
    1336            unsafe {
    1337                // The old and the new head slice can overlap, so we can't use `copy_nonoverlapping` here.
    1338                self.copy(self.head, old_head, head_len);
    1339                self.head = old_head;
    1340            }
    1341        }
    1342    }
    1343
    1344    /// Shortens the deque, keeping the first `len` elements and dropping
    1345    /// the rest.
    1346    ///
    1347    /// If `len` is greater or equal to the deque's current length, this has
    1348    /// no effect.
    1349    ///
    1350    /// # Examples
    1351    ///
    1352    /// ```
    1353    /// use std::collections::VecDeque;
    1354    ///
    1355    /// let mut buf = VecDeque::new();
    1356    /// buf.push_back(5);
    1357    /// buf.push_back(10);
    1358    /// buf.push_back(15);
    1359    /// assert_eq!(buf, [5, 10, 15]);
    1360    /// buf.truncate(1);
    1361    /// assert_eq!(buf, [5]);
    1362    /// ```
    1363    #[stable(feature = "deque_extras", since = "1.16.0")]
    1364    pub fn truncate(&mut self, len: usize) {
    1365        /// Runs the destructor for all items in the slice when it gets dropped (normally or
    1366        /// during unwinding).
    1367        struct Dropper<'a, T>(&'a mut [T]);
    1368
    1369        impl<'a, T> Drop for Dropper<'a, T> {
    1370            fn drop(&mut self) {
    1371                unsafe {
    1372                    ptr::drop_in_place(self.0);
    1373                }
    1374            }
    1375        }
    1376
    1377        // Safe because:
    1378        //
    1379        // * Any slice passed to `drop_in_place` is valid; the second case has
    1380        //   `len <= front.len()` and returning on `len > self.len()` ensures
    1381        //   `begin <= back.len()` in the first case
    1382        // * The head of the VecDeque is moved before calling `drop_in_place`,
    1383        //   so no value is dropped twice if `drop_in_place` panics
    1384        unsafe {
    1385            if len >= self.len {
    1386                return;
    1387            }
    1388
    1389            let (front, back) = self.as_mut_slices();
    1390            if len > front.len() {
    1391                let begin = len - front.len();
    1392                let drop_back = back.get_unchecked_mut(begin..) as *mut _;
    1393                self.len = len;
    1394                ptr::drop_in_place(drop_back);
    1395            } else {
    1396                let drop_back = back as *mut _;
    1397                let drop_front = front.get_unchecked_mut(len..) as *mut _;
    1398                self.len = len;
    1399
    1400                // Make sure the second half is dropped even when a destructor
    1401                // in the first one panics.
    1402                let _back_dropper = Dropper(&mut *drop_back);
    1403                ptr::drop_in_place(drop_front);
    1404            }
    1405        }
    1406    }
    1407
    1408    /// Shortens the deque, keeping the last `len` elements and dropping
    1409    /// the rest.
    1410    ///
    1411    /// If `len` is greater or equal to the deque's current length, this has
    1412    /// no effect.
    1413    ///
    1414    /// # Examples
    1415    ///
    1416    /// ```
    1417    /// # #![feature(vec_deque_truncate_front)]
    1418    /// use std::collections::VecDeque;
    1419    ///
    1420    /// let mut buf = VecDeque::new();
    1421    /// buf.push_front(5);
    1422    /// buf.push_front(10);
    1423    /// buf.push_front(15);
    1424    /// assert_eq!(buf, [15, 10, 5]);
    1425    /// assert_eq!(buf.as_slices(), (&[15, 10, 5][..], &[][..]));
    1426    /// buf.truncate_front(1);
    1427    /// assert_eq!(buf.as_slices(), (&[5][..], &[][..]));
    1428    /// ```
    1429    #[unstable(feature = "vec_deque_truncate_front", issue = "140667")]
    1430    pub fn truncate_front(&mut self, len: usize) {
    1431        /// Runs the destructor for all items in the slice when it gets dropped (normally or
    1432        /// during unwinding).
    1433        struct Dropper<'a, T>(&'a mut [T]);
    1434
    1435        impl<'a, T> Drop for Dropper<'a, T> {
    1436            fn drop(&mut self) {
    1437                unsafe {
    1438                    ptr::drop_in_place(self.0);
    1439                }
    1440            }
    1441        }
    1442
    1443        unsafe {
    1444            if len >= self.len {
    1445                // No action is taken
    1446                return;
    1447            }
    1448
    1449            let (front, back) = self.as_mut_slices();
    1450            if len > back.len() {
    1451                // The 'back' slice remains unchanged.
    1452                // front.len() + back.len() == self.len, so 'end' is non-negative
    1453                // and end < front.len()
    1454                let end = front.len() - (len - back.len());
    1455                let drop_front = front.get_unchecked_mut(..end) as *mut _;
    1456                self.head += end;
    1457                self.len = len;
    1458                ptr::drop_in_place(drop_front);
    1459            } else {
    1460                let drop_front = front as *mut _;
    1461                // 'end' is non-negative by the condition above
    1462                let end = back.len() - len;
    1463                let drop_back = back.get_unchecked_mut(..end) as *mut _;
    1464                self.head = self.to_physical_idx(self.len - len);
    1465                self.len = len;
    1466
    1467                // Make sure the second half is dropped even when a destructor
    1468                // in the first one panics.
    1469                let _back_dropper = Dropper(&mut *drop_back);
    1470                ptr::drop_in_place(drop_front);
    1471            }
    1472        }
    1473    }
    1474
    1475    /// Returns a reference to the underlying allocator.
    1476    #[unstable(feature = "allocator_api", issue = "32838")]
    1477    #[inline]
    1478    pub fn allocator(&self) -> &A {
    1479        self.buf.allocator()
    1480    }
    1481
    1482    /// Returns a front-to-back iterator.
    1483    ///
    1484    /// # Examples
    1485    ///
    1486    /// ```
    1487    /// use std::collections::VecDeque;
    1488    ///
    1489    /// let mut buf = VecDeque::new();
    1490    /// buf.push_back(5);
    1491    /// buf.push_back(3);
    1492    /// buf.push_back(4);
    1493    /// let b: &[_] = &[&5, &3, &4];
    1494    /// let c: Vec<&i32> = buf.iter().collect();
    1495    /// assert_eq!(&c[..], b);
    1496    /// ```
    1497    #[stable(feature = "rust1", since = "1.0.0")]
    1498    #[cfg_attr(not(test), rustc_diagnostic_item = "vecdeque_iter")]
    1499    pub fn iter(&self) -> Iter<'_, T> {
    1500        let (a, b) = self.as_slices();
    1501        Iter::new(a.iter(), b.iter())
    1502    }
    1503
    1504    /// Returns a front-to-back iterator that returns mutable references.
    1505    ///
    1506    /// # Examples
    1507    ///
    1508    /// ```
    1509    /// use std::collections::VecDeque;
    1510    ///
    1511    /// let mut buf = VecDeque::new();
    1512    /// buf.push_back(5);
    1513    /// buf.push_back(3);
    1514    /// buf.push_back(4);
    1515    /// for num in buf.iter_mut() {
    1516    ///     *num = *num - 2;
    1517    /// }
    1518    /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
    1519    /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
    1520    /// ```
    1521    #[stable(feature = "rust1", since = "1.0.0")]
    1522    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    1523        let (a, b) = self.as_mut_slices();
    1524        IterMut::new(a.iter_mut(), b.iter_mut())
    1525    }
    1526
    1527    /// Returns a pair of slices which contain, in order, the contents of the
    1528    /// deque.
    1529    ///
    1530    /// If [`make_contiguous`] was previously called, all elements of the
    1531    /// deque will be in the first slice and the second slice will be empty.
    1532    /// Otherwise, the exact split point depends on implementation details
    1533    /// and is not guaranteed.
    1534    ///
    1535    /// [`make_contiguous`]: VecDeque::make_contiguous
    1536    ///
    1537    /// # Examples
    1538    ///
    1539    /// ```
    1540    /// use std::collections::VecDeque;
    1541    ///
    1542    /// let mut deque = VecDeque::new();
    1543    ///
    1544    /// deque.push_back(0);
    1545    /// deque.push_back(1);
    1546    /// deque.push_back(2);
    1547    ///
    1548    /// let expected = [0, 1, 2];
    1549    /// let (front, back) = deque.as_slices();
    1550    /// assert_eq!(&expected[..front.len()], front);
    1551    /// assert_eq!(&expected[front.len()..], back);
    1552    ///
    1553    /// deque.push_front(10);
    1554    /// deque.push_front(9);
    1555    ///
    1556    /// let expected = [9, 10, 0, 1, 2];
    1557    /// let (front, back) = deque.as_slices();
    1558    /// assert_eq!(&expected[..front.len()], front);
    1559    /// assert_eq!(&expected[front.len()..], back);
    1560    /// ```
    1561    #[inline]
    1562    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    1563    pub fn as_slices(&self) -> (&[T], &[T]) {
    1564        let (a_range, b_range) = self.slice_ranges(.., self.len);
    1565        // SAFETY: `slice_ranges` always returns valid ranges into
    1566        // the physical buffer.
    1567        unsafe { (&*self.buffer_range(a_range), &*self.buffer_range(b_range)) }
    1568    }
    1569
    1570    /// Returns a pair of slices which contain, in order, the contents of the
    1571    /// deque.
    1572    ///
    1573    /// If [`make_contiguous`] was previously called, all elements of the
    1574    /// deque will be in the first slice and the second slice will be empty.
    1575    /// Otherwise, the exact split point depends on implementation details
    1576    /// and is not guaranteed.
    1577    ///
    1578    /// [`make_contiguous`]: VecDeque::make_contiguous
    1579    ///
    1580    /// # Examples
    1581    ///
    1582    /// ```
    1583    /// use std::collections::VecDeque;
    1584    ///
    1585    /// let mut deque = VecDeque::new();
    1586    ///
    1587    /// deque.push_back(0);
    1588    /// deque.push_back(1);
    1589    ///
    1590    /// deque.push_front(10);
    1591    /// deque.push_front(9);
    1592    ///
    1593    /// // Since the split point is not guaranteed, we may need to update
    1594    /// // either slice.
    1595    /// let mut update_nth = |index: usize, val: u32| {
    1596    ///     let (front, back) = deque.as_mut_slices();
    1597    ///     if index > front.len() - 1 {
    1598    ///         back[index - front.len()] = val;
    1599    ///     } else {
    1600    ///         front[index] = val;
    1601    ///     }
    1602    /// };
    1603    ///
    1604    /// update_nth(0, 42);
    1605    /// update_nth(2, 24);
    1606    ///
    1607    /// let v: Vec<_> = deque.into();
    1608    /// assert_eq!(v, [42, 10, 24, 1]);
    1609    /// ```
    1610    #[inline]
    1611    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    1612    pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
    1613        let (a_range, b_range) = self.slice_ranges(.., self.len);
    1614        // SAFETY: `slice_ranges` always returns valid ranges into
    1615        // the physical buffer.
    1616        unsafe { (&mut *self.buffer_range(a_range), &mut *self.buffer_range(b_range)) }
    1617    }
    1618
    1619    /// Returns the number of elements in the deque.
    1620    ///
    1621    /// # Examples
    1622    ///
    1623    /// ```
    1624    /// use std::collections::VecDeque;
    1625    ///
    1626    /// let mut deque = VecDeque::new();
    1627    /// assert_eq!(deque.len(), 0);
    1628    /// deque.push_back(1);
    1629    /// assert_eq!(deque.len(), 1);
    1630    /// ```
    1631    #[stable(feature = "rust1", since = "1.0.0")]
    1632    #[rustc_confusables("length", "size")]
    1633    pub fn len(&self) -> usize {
    1634        self.len
    1635    }
    1636
    1637    /// Returns `true` if the deque is empty.
    1638    ///
    1639    /// # Examples
    1640    ///
    1641    /// ```
    1642    /// use std::collections::VecDeque;
    1643    ///
    1644    /// let mut deque = VecDeque::new();
    1645    /// assert!(deque.is_empty());
    1646    /// deque.push_front(1);
    1647    /// assert!(!deque.is_empty());
    1648    /// ```
    1649    #[stable(feature = "rust1", since = "1.0.0")]
    1650    pub fn is_empty(&self) -> bool {
    1651        self.len == 0
    1652    }
    1653
    1654    /// Given a range into the logical buffer of the deque, this function
    1655    /// return two ranges into the physical buffer that correspond to
    1656    /// the given range. The `len` parameter should usually just be `self.len`;
    1657    /// the reason it's passed explicitly is that if the deque is wrapped in
    1658    /// a `Drain`, then `self.len` is not actually the length of the deque.
    1659    ///
    1660    /// # Safety
    1661    ///
    1662    /// This function is always safe to call. For the resulting ranges to be valid
    1663    /// ranges into the physical buffer, the caller must ensure that the result of
    1664    /// calling `slice::range(range, ..len)` represents a valid range into the
    1665    /// logical buffer, and that all elements in that range are initialized.
    1666    fn slice_ranges<R>(&self, range: R, len: usize) -> (Range<usize>, Range<usize>)
    1667    where
    1668        R: RangeBounds<usize>,
    1669    {
    1670        let Range { start, end } = slice::range(range, ..len);
    1671        let len = end - start;
    1672
    1673        if len == 0 {
    1674            (0..0, 0..0)
    1675        } else {
    1676            // `slice::range` guarantees that `start <= end <= len`.
    1677            // because `len != 0`, we know that `start < end`, so `start < len`
    1678            // and the indexing is valid.
    1679            let wrapped_start = self.to_physical_idx(start);
    1680
    1681            // this subtraction can never overflow because `wrapped_start` is
    1682            // at most `self.capacity()` (and if `self.capacity != 0`, then `wrapped_start` is strictly less
    1683            // than `self.capacity`).
    1684            let head_len = self.capacity() - wrapped_start;
    1685
    1686            if head_len >= len {
    1687                // we know that `len + wrapped_start <= self.capacity <= usize::MAX`, so this addition can't overflow
    1688                (wrapped_start..wrapped_start + len, 0..0)
    1689            } else {
    1690                // can't overflow because of the if condition
    1691                let tail_len = len - head_len;
    1692                (wrapped_start..self.capacity(), 0..tail_len)
    1693            }
    1694        }
    1695    }
    1696
    1697    /// Creates an iterator that covers the specified range in the deque.
    1698    ///
    1699    /// # Panics
    1700    ///
    1701    /// Panics if the range has `start_bound > end_bound`, or, if the range is
    1702    /// bounded on either end and past the length of the deque.
    1703    ///
    1704    /// # Examples
    1705    ///
    1706    /// ```
    1707    /// use std::collections::VecDeque;
    1708    ///
    1709    /// let deque: VecDeque<_> = [1, 2, 3].into();
    1710    /// let range = deque.range(2..).copied().collect::<VecDeque<_>>();
    1711    /// assert_eq!(range, [3]);
    1712    ///
    1713    /// // A full range covers all contents
    1714    /// let all = deque.range(..);
    1715    /// assert_eq!(all.len(), 3);
    1716    /// ```
    1717    #[inline]
    1718    #[stable(feature = "deque_range", since = "1.51.0")]
    1719    pub fn range<R>(&self, range: R) -> Iter<'_, T>
    1720    where
    1721        R: RangeBounds<usize>,
    1722    {
    1723        let (a_range, b_range) = self.slice_ranges(range, self.len);
    1724        // SAFETY: The ranges returned by `slice_ranges`
    1725        // are valid ranges into the physical buffer, so
    1726        // it's ok to pass them to `buffer_range` and
    1727        // dereference the result.
    1728        let a = unsafe { &*self.buffer_range(a_range) };
    1729        let b = unsafe { &*self.buffer_range(b_range) };
    1730        Iter::new(a.iter(), b.iter())
    1731    }
    1732
    1733    /// Creates an iterator that covers the specified mutable range in the deque.
    1734    ///
    1735    /// # Panics
    1736    ///
    1737    /// Panics if the range has `start_bound > end_bound`, or, if the range is
    1738    /// bounded on either end and past the length of the deque.
    1739    ///
    1740    /// # Examples
    1741    ///
    1742    /// ```
    1743    /// use std::collections::VecDeque;
    1744    ///
    1745    /// let mut deque: VecDeque<_> = [1, 2, 3].into();
    1746    /// for v in deque.range_mut(2..) {
    1747    ///   *v *= 2;
    1748    /// }
    1749    /// assert_eq!(deque, [1, 2, 6]);
    1750    ///
    1751    /// // A full range covers all contents
    1752    /// for v in deque.range_mut(..) {
    1753    ///   *v *= 2;
    1754    /// }
    1755    /// assert_eq!(deque, [2, 4, 12]);
    1756    /// ```
    1757    #[inline]
    1758    #[stable(feature = "deque_range", since = "1.51.0")]
    1759    pub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T>
    1760    where
    1761        R: RangeBounds<usize>,
    1762    {
    1763        let (a_range, b_range) = self.slice_ranges(range, self.len);
    1764        // SAFETY: The ranges returned by `slice_ranges`
    1765        // are valid ranges into the physical buffer, so
    1766        // it's ok to pass them to `buffer_range` and
    1767        // dereference the result.
    1768        let a = unsafe { &mut *self.buffer_range(a_range) };
    1769        let b = unsafe { &mut *self.buffer_range(b_range) };
    1770        IterMut::new(a.iter_mut(), b.iter_mut())
    1771    }
    1772
    1773    /// Removes the specified range from the deque in bulk, returning all
    1774    /// removed elements as an iterator. If the iterator is dropped before
    1775    /// being fully consumed, it drops the remaining removed elements.
    1776    ///
    1777    /// The returned iterator keeps a mutable borrow on the queue to optimize
    1778    /// its implementation.
    1779    ///
    1780    ///
    1781    /// # Panics
    1782    ///
    1783    /// Panics if the range has `start_bound > end_bound`, or, if the range is
    1784    /// bounded on either end and past the length of the deque.
    1785    ///
    1786    /// # Leaking
    1787    ///
    1788    /// If the returned iterator goes out of scope without being dropped (due to
    1789    /// [`mem::forget`], for example), the deque may have lost and leaked
    1790    /// elements arbitrarily, including elements outside the range.
    1791    ///
    1792    /// # Examples
    1793    ///
    1794    /// ```
    1795    /// use std::collections::VecDeque;
    1796    ///
    1797    /// let mut deque: VecDeque<_> = [1, 2, 3].into();
    1798    /// let drained = deque.drain(2..).collect::<VecDeque<_>>();
    1799    /// assert_eq!(drained, [3]);
    1800    /// assert_eq!(deque, [1, 2]);
    1801    ///
    1802    /// // A full range clears all contents, like `clear()` does
    1803    /// deque.drain(..);
    1804    /// assert!(deque.is_empty());
    1805    /// ```
    1806    #[inline]
    1807    #[stable(feature = "drain", since = "1.6.0")]
    1808    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
    1809    where
    1810        R: RangeBounds<usize>,
    1811    {
    1812        // Memory safety
    1813        //
    1814        // When the Drain is first created, the source deque is shortened to
    1815        // make sure no uninitialized or moved-from elements are accessible at
    1816        // all if the Drain's destructor never gets to run.
    1817        //
    1818        // Drain will ptr::read out the values to remove.
    1819        // When finished, the remaining data will be copied back to cover the hole,
    1820        // and the head/tail values will be restored correctly.
    1821        //
    1822        let Range { start, end } = slice::range(range, ..self.len);
    1823        let drain_start = start;
    1824        let drain_len = end - start;
    1825
    1826        // The deque's elements are parted into three segments:
    1827        // * 0  -> drain_start
    1828        // * drain_start -> drain_start+drain_len
    1829        // * drain_start+drain_len -> self.len
    1830        //
    1831        // H = self.head; T = self.head+self.len; t = drain_start+drain_len; h = drain_head
    1832        //
    1833        // We store drain_start as self.len, and drain_len and self.len as
    1834        // drain_len and orig_len respectively on the Drain. This also
    1835        // truncates the effective array such that if the Drain is leaked, we
    1836        // have forgotten about the potentially moved values after the start of
    1837        // the drain.
    1838        //
    1839        //        H   h   t   T
    1840        // [. . . o o x x o o . . .]
    1841        //
    1842        // "forget" about the values after the start of the drain until after
    1843        // the drain is complete and the Drain destructor is run.
    1844
    1845        unsafe { Drain::new(self, drain_start, drain_len) }
    1846    }
    1847
    1848    /// Creates a splicing iterator that replaces the specified range in the deque with the given
    1849    /// `replace_with` iterator and yields the removed items. `replace_with` does not need to be the
    1850    /// same length as `range`.
    1851    ///
    1852    /// `range` is removed even if the `Splice` iterator is not consumed before it is dropped.
    1853    ///
    1854    /// It is unspecified how many elements are removed from the deque if the `Splice` value is
    1855    /// leaked.
    1856    ///
    1857    /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
    1858    ///
    1859    /// This is optimal if:
    1860    ///
    1861    /// * The tail (elements in the deque after `range`) is empty,
    1862    /// * or `replace_with` yields fewer or equal elements than `range`'s length
    1863    /// * or the lower bound of its `size_hint()` is exact.
    1864    ///
    1865    /// Otherwise, a temporary vector is allocated and the tail is moved twice.
    1866    ///
    1867    /// # Panics
    1868    ///
    1869    /// Panics if the range has `start_bound > end_bound`, or, if the range is
    1870    /// bounded on either end and past the length of the deque.
    1871    ///
    1872    /// # Examples
    1873    ///
    1874    /// ```
    1875    /// # #![feature(deque_extend_front)]
    1876    /// # use std::collections::VecDeque;
    1877    ///
    1878    /// let mut v = VecDeque::from(vec![1, 2, 3, 4]);
    1879    /// let new = [7, 8, 9];
    1880    /// let u: Vec<_> = v.splice(1..3, new).collect();
    1881    /// assert_eq!(v, [1, 7, 8, 9, 4]);
    1882    /// assert_eq!(u, [2, 3]);
    1883    /// ```
    1884    ///
    1885    /// Using `splice` to insert new items into a vector efficiently at a specific position
    1886    /// indicated by an empty range:
    1887    ///
    1888    /// ```
    1889    /// # #![feature(deque_extend_front)]
    1890    /// # use std::collections::VecDeque;
    1891    ///
    1892    /// let mut v = VecDeque::from(vec![1, 5]);
    1893    /// let new = [2, 3, 4];
    1894    /// v.splice(1..1, new);
    1895    /// assert_eq!(v, [1, 2, 3, 4, 5]);
    1896    /// ```
    1897    #[unstable(feature = "deque_extend_front", issue = "146975")]
    1898    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
    1899    where
    1900        R: RangeBounds<usize>,
    1901        I: IntoIterator<Item = T>,
    1902    {
    1903        Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
    1904    }
    1905
    1906    /// Clears the deque, removing all values.
    1907    ///
    1908    /// # Examples
    1909    ///
    1910    /// ```
    1911    /// use std::collections::VecDeque;
    1912    ///
    1913    /// let mut deque = VecDeque::new();
    1914    /// deque.push_back(1);
    1915    /// deque.clear();
    1916    /// assert!(deque.is_empty());
    1917    /// ```
    1918    #[stable(feature = "rust1", since = "1.0.0")]
    1919    #[inline]
    1920    pub fn clear(&mut self) {
    1921        self.truncate(0);
    1922        // Not strictly necessary, but leaves things in a more consistent/predictable state.
    1923        self.head = 0;
    1924    }
    1925
    1926    /// Returns `true` if the deque contains an element equal to the
    1927    /// given value.
    1928    ///
    1929    /// This operation is *O*(*n*).
    1930    ///
    1931    /// Note that if you have a sorted `VecDeque`, [`binary_search`] may be faster.
    1932    ///
    1933    /// [`binary_search`]: VecDeque::binary_search
    1934    ///
    1935    /// # Examples
    1936    ///
    1937    /// ```
    1938    /// use std::collections::VecDeque;
    1939    ///
    1940    /// let mut deque: VecDeque<u32> = VecDeque::new();
    1941    ///
    1942    /// deque.push_back(0);
    1943    /// deque.push_back(1);
    1944    ///
    1945    /// assert_eq!(deque.contains(&1), true);
    1946    /// assert_eq!(deque.contains(&10), false);
    1947    /// ```
    1948    #[stable(feature = "vec_deque_contains", since = "1.12.0")]
    1949    pub fn contains(&self, x: &T) -> bool
    1950    where
    1951        T: PartialEq<T>,
    1952    {
    1953        let (a, b) = self.as_slices();
    1954        a.contains(x) || b.contains(x)
    1955    }
    1956
    1957    /// Provides a reference to the front element, or `None` if the deque is
    1958    /// empty.
    1959    ///
    1960    /// # Examples
    1961    ///
    1962    /// ```
    1963    /// use std::collections::VecDeque;
    1964    ///
    1965    /// let mut d = VecDeque::new();
    1966    /// assert_eq!(d.front(), None);
    1967    ///
    1968    /// d.push_back(1);
    1969    /// d.push_back(2);
    1970    /// assert_eq!(d.front(), Some(&1));
    1971    /// ```
    1972    #[stable(feature = "rust1", since = "1.0.0")]
    1973    #[rustc_confusables("first")]
    1974    pub fn front(&self) -> Option<&T> {
    1975        self.get(0)
    1976    }
    1977
    1978    /// Provides a mutable reference to the front element, or `None` if the
    1979    /// deque is empty.
    1980    ///
    1981    /// # Examples
    1982    ///
    1983    /// ```
    1984    /// use std::collections::VecDeque;
    1985    ///
    1986    /// let mut d = VecDeque::new();
    1987    /// assert_eq!(d.front_mut(), None);
    1988    ///
    1989    /// d.push_back(1);
    1990    /// d.push_back(2);
    1991    /// match d.front_mut() {
    1992    ///     Some(x) => *x = 9,
    1993    ///     None => (),
    1994    /// }
    1995    /// assert_eq!(d.front(), Some(&9));
    1996    /// ```
    1997    #[stable(feature = "rust1", since = "1.0.0")]
    1998    pub fn front_mut(&mut self) -> Option<&mut T> {
    1999        self.get_mut(0)
    2000    }
    2001
    2002    /// Provides a reference to the back element, or `None` if the deque is
    2003    /// empty.
    2004    ///
    2005    /// # Examples
    2006    ///
    2007    /// ```
    2008    /// use std::collections::VecDeque;
    2009    ///
    2010    /// let mut d = VecDeque::new();
    2011    /// assert_eq!(d.back(), None);
    2012    ///
    2013    /// d.push_back(1);
    2014    /// d.push_back(2);
    2015    /// assert_eq!(d.back(), Some(&2));
    2016    /// ```
    2017    #[stable(feature = "rust1", since = "1.0.0")]
    2018    #[rustc_confusables("last")]
    2019    pub fn back(&self) -> Option<&T> {
    2020        self.get(self.len.wrapping_sub(1))
    2021    }
    2022
    2023    /// Provides a mutable reference to the back element, or `None` if the
    2024    /// deque is empty.
    2025    ///
    2026    /// # Examples
    2027    ///
    2028    /// ```
    2029    /// use std::collections::VecDeque;
    2030    ///
    2031    /// let mut d = VecDeque::new();
    2032    /// assert_eq!(d.back(), None);
    2033    ///
    2034    /// d.push_back(1);
    2035    /// d.push_back(2);
    2036    /// match d.back_mut() {
    2037    ///     Some(x) => *x = 9,
    2038    ///     None => (),
    2039    /// }
    2040    /// assert_eq!(d.back(), Some(&9));
    2041    /// ```
    2042    #[stable(feature = "rust1", since = "1.0.0")]
    2043    pub fn back_mut(&mut self) -> Option<&mut T> {
    2044        self.get_mut(self.len.wrapping_sub(1))
    2045    }
    2046
    2047    /// Removes the first element and returns it, or `None` if the deque is
    2048    /// empty.
    2049    ///
    2050    /// # Examples
    2051    ///
    2052    /// ```
    2053    /// use std::collections::VecDeque;
    2054    ///
    2055    /// let mut d = VecDeque::new();
    2056    /// d.push_back(1);
    2057    /// d.push_back(2);
    2058    ///
    2059    /// assert_eq!(d.pop_front(), Some(1));
    2060    /// assert_eq!(d.pop_front(), Some(2));
    2061    /// assert_eq!(d.pop_front(), None);
    2062    /// ```
    2063    #[stable(feature = "rust1", since = "1.0.0")]
    2064    pub fn pop_front(&mut self) -> Option<T> {
    2065        if self.is_empty() {
    2066            None
    2067        } else {
    2068            let old_head = self.head;
    2069            self.head = self.to_physical_idx(1);
    2070            self.len -= 1;
    2071            unsafe {
    2072                core::hint::assert_unchecked(self.len < self.capacity());
    2073                Some(self.buffer_read(old_head))
    2074            }
    2075        }
    2076    }
    2077
    2078    /// Removes the last element from the deque and returns it, or `None` if
    2079    /// it is empty.
    2080    ///
    2081    /// # Examples
    2082    ///
    2083    /// ```
    2084    /// use std::collections::VecDeque;
    2085    ///
    2086    /// let mut buf = VecDeque::new();
    2087    /// assert_eq!(buf.pop_back(), None);
    2088    /// buf.push_back(1);
    2089    /// buf.push_back(3);
    2090    /// assert_eq!(buf.pop_back(), Some(3));
    2091    /// ```
    2092    #[stable(feature = "rust1", since = "1.0.0")]
    2093    pub fn pop_back(&mut self) -> Option<T> {
    2094        if self.is_empty() {
    2095            None
    2096        } else {
    2097            self.len -= 1;
    2098            unsafe {
    2099                core::hint::assert_unchecked(self.len < self.capacity());
    2100                Some(self.buffer_read(self.to_physical_idx(self.len)))
    2101            }
    2102        }
    2103    }
    2104
    2105    /// Removes and returns the first element from the deque if the predicate
    2106    /// returns `true`, or [`None`] if the predicate returns false or the deque
    2107    /// is empty (the predicate will not be called in that case).
    2108    ///
    2109    /// # Examples
    2110    ///
    2111    /// ```
    2112    /// use std::collections::VecDeque;
    2113    ///
    2114    /// let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
    2115    /// let pred = |x: &mut i32| *x % 2 == 0;
    2116    ///
    2117    /// assert_eq!(deque.pop_front_if(pred), Some(0));
    2118    /// assert_eq!(deque, [1, 2, 3, 4]);
    2119    /// assert_eq!(deque.pop_front_if(pred), None);
    2120    /// ```
    2121    #[stable(feature = "vec_deque_pop_if", since = "1.93.0")]
    2122    pub fn pop_front_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
    2123        let first = self.front_mut()?;
    2124        if predicate(first) { self.pop_front() } else { None }
    2125    }
    2126
    2127    /// Removes and returns the last element from the deque if the predicate
    2128    /// returns `true`, or [`None`] if the predicate returns false or the deque
    2129    /// is empty (the predicate will not be called in that case).
    2130    ///
    2131    /// # Examples
    2132    ///
    2133    /// ```
    2134    /// use std::collections::VecDeque;
    2135    ///
    2136    /// let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
    2137    /// let pred = |x: &mut i32| *x % 2 == 0;
    2138    ///
    2139    /// assert_eq!(deque.pop_back_if(pred), Some(4));
    2140    /// assert_eq!(deque, [0, 1, 2, 3]);
    2141    /// assert_eq!(deque.pop_back_if(pred), None);
    2142    /// ```
    2143    #[stable(feature = "vec_deque_pop_if", since = "1.93.0")]
    2144    pub fn pop_back_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
    2145        let last = self.back_mut()?;
    2146        if predicate(last) { self.pop_back() } else { None }
    2147    }
    2148
    2149    /// Prepends an element to the deque.
    2150    ///
    2151    /// # Examples
    2152    ///
    2153    /// ```
    2154    /// use std::collections::VecDeque;
    2155    ///
    2156    /// let mut d = VecDeque::new();
    2157    /// d.push_front(1);
    2158    /// d.push_front(2);
    2159    /// assert_eq!(d.front(), Some(&2));
    2160    /// ```
    2161    #[stable(feature = "rust1", since = "1.0.0")]
    2162    pub fn push_front(&mut self, value: T) {
    2163        let _ = self.push_front_mut(value);
    2164    }
    2165
    2166    /// Prepends an element to the deque, returning a reference to it.
    2167    ///
    2168    /// # Examples
    2169    ///
    2170    /// ```
    2171    /// #![feature(push_mut)]
    2172    /// use std::collections::VecDeque;
    2173    ///
    2174    /// let mut d = VecDeque::from([1, 2, 3]);
    2175    /// let x = d.push_front_mut(8);
    2176    /// *x -= 1;
    2177    /// assert_eq!(d.front(), Some(&7));
    2178    /// ```
    2179    #[unstable(feature = "push_mut", issue = "135974")]
    2180    #[must_use = "if you don't need a reference to the value, use `VecDeque::push_front` instead"]
    2181    pub fn push_front_mut(&mut self, value: T) -> &mut T {
    2182        if self.is_full() {
    2183            self.grow();
    2184        }
    2185
    2186        self.head = self.wrap_sub(self.head, 1);
    2187        self.len += 1;
    2188        // SAFETY: We know that self.head is within range of the deque.
    2189        unsafe { self.buffer_write(self.head, value) }
    2190    }
    2191
    2192    /// Appends an element to the back of the deque.
    2193    ///
    2194    /// # Examples
    2195    ///
    2196    /// ```
    2197    /// use std::collections::VecDeque;
    2198    ///
    2199    /// let mut buf = VecDeque::new();
    2200    /// buf.push_back(1);
    2201    /// buf.push_back(3);
    2202    /// assert_eq!(3, *buf.back().unwrap());
    2203    /// ```
    2204    #[stable(feature = "rust1", since = "1.0.0")]
    2205    #[rustc_confusables("push", "put", "append")]
    2206    pub fn push_back(&mut self, value: T) {
    2207        let _ = self.push_back_mut(value);
    2208    }
    2209
    2210    /// Appends an element to the back of the deque, returning a reference to it.
    2211    ///
    2212    /// # Examples
    2213    ///
    2214    /// ```
    2215    /// #![feature(push_mut)]
    2216    /// use std::collections::VecDeque;
    2217    ///
    2218    /// let mut d = VecDeque::from([1, 2, 3]);
    2219    /// let x = d.push_back_mut(9);
    2220    /// *x += 1;
    2221    /// assert_eq!(d.back(), Some(&10));
    2222    /// ```
    2223    #[unstable(feature = "push_mut", issue = "135974")]
    2224    #[must_use = "if you don't need a reference to the value, use `VecDeque::push_back` instead"]
    2225    pub fn push_back_mut(&mut self, value: T) -> &mut T {
    2226        if self.is_full() {
    2227            self.grow();
    2228        }
    2229
    2230        let len = self.len;
    2231        self.len += 1;
    2232        unsafe { self.buffer_write(self.to_physical_idx(len), value) }
    2233    }
    2234
    2235    /// Prepends all contents of the iterator to the front of the deque.
    2236    /// The order of the contents is preserved.
    2237    ///
    2238    /// To get behavior like [`append`][VecDeque::append] where elements are moved
    2239    /// from the other collection to this one, use `self.prepend(other.drain(..))`.
    2240    ///
    2241    /// # Examples
    2242    ///
    2243    /// ```
    2244    /// #![feature(deque_extend_front)]
    2245    /// use std::collections::VecDeque;
    2246    ///
    2247    /// let mut deque = VecDeque::from([4, 5, 6]);
    2248    /// deque.prepend([1, 2, 3]);
    2249    /// assert_eq!(deque, [1, 2, 3, 4, 5, 6]);
    2250    /// ```
    2251    ///
    2252    /// Move values between collections like [`append`][VecDeque::append] does but prepend to the front:
    2253    ///
    2254    /// ```
    2255    /// #![feature(deque_extend_front)]
    2256    /// use std::collections::VecDeque;
    2257    ///
    2258    /// let mut deque1 = VecDeque::from([4, 5, 6]);
    2259    /// let mut deque2 = VecDeque::from([1, 2, 3]);
    2260    /// deque1.prepend(deque2.drain(..));
    2261    /// assert_eq!(deque1, [1, 2, 3, 4, 5, 6]);
    2262    /// assert!(deque2.is_empty());
    2263    /// ```
    2264    #[unstable(feature = "deque_extend_front", issue = "146975")]
    2265    #[track_caller]
    2266    pub fn prepend<I: IntoIterator<Item = T, IntoIter: DoubleEndedIterator>>(&mut self, other: I) {
    2267        self.extend_front(other.into_iter().rev())
    2268    }
    2269
    2270    /// Prepends all contents of the iterator to the front of the deque,
    2271    /// as if [`push_front`][VecDeque::push_front] was called repeatedly with
    2272    /// the values yielded by the iterator.
    2273    ///
    2274    /// # Examples
    2275    ///
    2276    /// ```
    2277    /// #![feature(deque_extend_front)]
    2278    /// use std::collections::VecDeque;
    2279    ///
    2280    /// let mut deque = VecDeque::from([4, 5, 6]);
    2281    /// deque.extend_front([3, 2, 1]);
    2282    /// assert_eq!(deque, [1, 2, 3, 4, 5, 6]);
    2283    /// ```
    2284    ///
    2285    /// This behaves like [`push_front`][VecDeque::push_front] was called repeatedly:
    2286    ///
    2287    /// ```
    2288    /// use std::collections::VecDeque;
    2289    ///
    2290    /// let mut deque = VecDeque::from([4, 5, 6]);
    2291    /// for v in [3, 2, 1] {
    2292    ///     deque.push_front(v);
    2293    /// }
    2294    /// assert_eq!(deque, [1, 2, 3, 4, 5, 6]);
    2295    /// ```
    2296    #[unstable(feature = "deque_extend_front", issue = "146975")]
    2297    #[track_caller]
    2298    pub fn extend_front<I: IntoIterator<Item = T>>(&mut self, iter: I) {
    2299        <Self as SpecExtendFront<T, I::IntoIter>>::spec_extend_front(self, iter.into_iter());
    2300    }
    2301
    2302    #[inline]
    2303    fn is_contiguous(&self) -> bool {
    2304        // Do the calculation like this to avoid overflowing if len + head > usize::MAX
    2305        self.head <= self.capacity() - self.len
    2306    }
    2307
    2308    /// Removes an element from anywhere in the deque and returns it,
    2309    /// replacing it with the first element.
    2310    ///
    2311    /// This does not preserve ordering, but is *O*(1).
    2312    ///
    2313    /// Returns `None` if `index` is out of bounds.
    2314    ///
    2315    /// Element at index 0 is the front of the queue.
    2316    ///
    2317    /// # Examples
    2318    ///
    2319    /// ```
    2320    /// use std::collections::VecDeque;
    2321    ///
    2322    /// let mut buf = VecDeque::new();
    2323    /// assert_eq!(buf.swap_remove_front(0), None);
    2324    /// buf.push_back(1);
    2325    /// buf.push_back(2);
    2326    /// buf.push_back(3);
    2327    /// assert_eq!(buf, [1, 2, 3]);
    2328    ///
    2329    /// assert_eq!(buf.swap_remove_front(2), Some(3));
    2330    /// assert_eq!(buf, [2, 1]);
    2331    /// ```
    2332    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    2333    pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
    2334        let length = self.len;
    2335        if index < length && index != 0 {
    2336            self.swap(index, 0);
    2337        } else if index >= length {
    2338            return None;
    2339        }
    2340        self.pop_front()
    2341    }
    2342
    2343    /// Removes an element from anywhere in the deque and returns it,
    2344    /// replacing it with the last element.
    2345    ///
    2346    /// This does not preserve ordering, but is *O*(1).
    2347    ///
    2348    /// Returns `None` if `index` is out of bounds.
    2349    ///
    2350    /// Element at index 0 is the front of the queue.
    2351    ///
    2352    /// # Examples
    2353    ///
    2354    /// ```
    2355    /// use std::collections::VecDeque;
    2356    ///
    2357    /// let mut buf = VecDeque::new();
    2358    /// assert_eq!(buf.swap_remove_back(0), None);
    2359    /// buf.push_back(1);
    2360    /// buf.push_back(2);
    2361    /// buf.push_back(3);
    2362    /// assert_eq!(buf, [1, 2, 3]);
    2363    ///
    2364    /// assert_eq!(buf.swap_remove_back(0), Some(1));
    2365    /// assert_eq!(buf, [3, 2]);
    2366    /// ```
    2367    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    2368    pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
    2369        let length = self.len;
    2370        if length > 0 && index < length - 1 {
    2371            self.swap(index, length - 1);
    2372        } else if index >= length {
    2373            return None;
    2374        }
    2375        self.pop_back()
    2376    }
    2377
    2378    /// Inserts an element at `index` within the deque, shifting all elements
    2379    /// with indices greater than or equal to `index` towards the back.
    2380    ///
    2381    /// Element at index 0 is the front of the queue.
    2382    ///
    2383    /// # Panics
    2384    ///
    2385    /// Panics if `index` is strictly greater than the deque's length.
    2386    ///
    2387    /// # Examples
    2388    ///
    2389    /// ```
    2390    /// use std::collections::VecDeque;
    2391    ///
    2392    /// let mut vec_deque = VecDeque::new();
    2393    /// vec_deque.push_back('a');
    2394    /// vec_deque.push_back('b');
    2395    /// vec_deque.push_back('c');
    2396    /// assert_eq!(vec_deque, &['a', 'b', 'c']);
    2397    ///
    2398    /// vec_deque.insert(1, 'd');
    2399    /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
    2400    ///
    2401    /// vec_deque.insert(4, 'e');
    2402    /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c', 'e']);
    2403    /// ```
    2404    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    2405    pub fn insert(&mut self, index: usize, value: T) {
    2406        let _ = self.insert_mut(index, value);
    2407    }
    2408
    2409    /// Inserts an element at `index` within the deque, shifting all elements
    2410    /// with indices greater than or equal to `index` towards the back, and
    2411    /// returning a reference to it.
    2412    ///
    2413    /// Element at index 0 is the front of the queue.
    2414    ///
    2415    /// # Panics
    2416    ///
    2417    /// Panics if `index` is strictly greater than the deque's length.
    2418    ///
    2419    /// # Examples
    2420    ///
    2421    /// ```
    2422    /// #![feature(push_mut)]
    2423    /// use std::collections::VecDeque;
    2424    ///
    2425    /// let mut vec_deque = VecDeque::from([1, 2, 3]);
    2426    ///
    2427    /// let x = vec_deque.insert_mut(1, 5);
    2428    /// *x += 7;
    2429    /// assert_eq!(vec_deque, &[1, 12, 2, 3]);
    2430    /// ```
    2431    #[unstable(feature = "push_mut", issue = "135974")]
    2432    #[must_use = "if you don't need a reference to the value, use `VecDeque::insert` instead"]
    2433    pub fn insert_mut(&mut self, index: usize, value: T) -> &mut T {
    2434        assert!(index <= self.len(), "index out of bounds");
    2435
    2436        if self.is_full() {
    2437            self.grow();
    2438        }
    2439
    2440        let k = self.len - index;
    2441        if k < index {
    2442            // `index + 1` can't overflow, because if index was usize::MAX, then either the
    2443            // assert would've failed, or the deque would've tried to grow past usize::MAX
    2444            // and panicked.
    2445            unsafe {
    2446                // see `remove()` for explanation why this wrap_copy() call is safe.
    2447                self.wrap_copy(self.to_physical_idx(index), self.to_physical_idx(index + 1), k);
    2448                self.len += 1;
    2449                self.buffer_write(self.to_physical_idx(index), value)
    2450            }
    2451        } else {
    2452            let old_head = self.head;
    2453            self.head = self.wrap_sub(self.head, 1);
    2454            unsafe {
    2455                self.wrap_copy(old_head, self.head, index);
    2456                self.len += 1;
    2457                self.buffer_write(self.to_physical_idx(index), value)
    2458            }
    2459        }
    2460    }
    2461
    2462    /// Removes and returns the element at `index` from the deque.
    2463    /// Whichever end is closer to the removal point will be moved to make
    2464    /// room, and all the affected elements will be moved to new positions.
    2465    /// Returns `None` if `index` is out of bounds.
    2466    ///
    2467    /// Element at index 0 is the front of the queue.
    2468    ///
    2469    /// # Examples
    2470    ///
    2471    /// ```
    2472    /// use std::collections::VecDeque;
    2473    ///
    2474    /// let mut buf = VecDeque::new();
    2475    /// buf.push_back('a');
    2476    /// buf.push_back('b');
    2477    /// buf.push_back('c');
    2478    /// assert_eq!(buf, ['a', 'b', 'c']);
    2479    ///
    2480    /// assert_eq!(buf.remove(1), Some('b'));
    2481    /// assert_eq!(buf, ['a', 'c']);
    2482    /// ```
    2483    #[stable(feature = "rust1", since = "1.0.0")]
    2484    #[rustc_confusables("delete", "take")]
    2485    pub fn remove(&mut self, index: usize) -> Option<T> {
    2486        if self.len <= index {
    2487            return None;
    2488        }
    2489
    2490        let wrapped_idx = self.to_physical_idx(index);
    2491
    2492        let elem = unsafe { Some(self.buffer_read(wrapped_idx)) };
    2493
    2494        let k = self.len - index - 1;
    2495        // safety: due to the nature of the if-condition, whichever wrap_copy gets called,
    2496        // its length argument will be at most `self.len / 2`, so there can't be more than
    2497        // one overlapping area.
    2498        if k < index {
    2499            unsafe { self.wrap_copy(self.wrap_add(wrapped_idx, 1), wrapped_idx, k) };
    2500            self.len -= 1;
    2501        } else {
    2502            let old_head = self.head;
    2503            self.head = self.to_physical_idx(1);
    2504            unsafe { self.wrap_copy(old_head, self.head, index) };
    2505            self.len -= 1;
    2506        }
    2507
    2508        elem
    2509    }
    2510
    2511    /// Splits the deque into two at the given index.
    2512    ///
    2513    /// Returns a newly allocated `VecDeque`. `self` contains elements `[0, at)`,
    2514    /// and the returned deque contains elements `[at, len)`.
    2515    ///
    2516    /// Note that the capacity of `self` does not change.
    2517    ///
    2518    /// Element at index 0 is the front of the queue.
    2519    ///
    2520    /// # Panics
    2521    ///
    2522    /// Panics if `at > len`.
    2523    ///
    2524    /// # Examples
    2525    ///
    2526    /// ```
    2527    /// use std::collections::VecDeque;
    2528    ///
    2529    /// let mut buf: VecDeque<_> = ['a', 'b', 'c'].into();
    2530    /// let buf2 = buf.split_off(1);
    2531    /// assert_eq!(buf, ['a']);
    2532    /// assert_eq!(buf2, ['b', 'c']);
    2533    /// ```
    2534    #[inline]
    2535    #[must_use = "use `.truncate()` if you don't need the other half"]
    2536    #[stable(feature = "split_off", since = "1.4.0")]
    2537    pub fn split_off(&mut self, at: usize) -> Self
    2538    where
    2539        A: Clone,
    2540    {
    2541        let len = self.len;
    2542        assert!(at <= len, "`at` out of bounds");
    2543
    2544        let other_len = len - at;
    2545        let mut other = VecDeque::with_capacity_in(other_len, self.allocator().clone());
    2546
    2547        let (first_half, second_half) = self.as_slices();
    2548        let first_len = first_half.len();
    2549        let second_len = second_half.len();
    2550
    2551        unsafe {
    2552            if at < first_len {
    2553                // `at` lies in the first half.
    2554                let amount_in_first = first_len - at;
    2555
    2556                ptr::copy_nonoverlapping(first_half.as_ptr().add(at), other.ptr(), amount_in_first);
    2557
    2558                // just take all of the second half.
    2559                ptr::copy_nonoverlapping(
    2560                    second_half.as_ptr(),
    2561                    other.ptr().add(amount_in_first),
    2562                    second_len,
    2563                );
    2564            } else {
    2565                // `at` lies in the second half, need to factor in the elements we skipped
    2566                // in the first half.
    2567                let offset = at - first_len;
    2568                let amount_in_second = second_len - offset;
    2569                ptr::copy_nonoverlapping(
    2570                    second_half.as_ptr().add(offset),
    2571                    other.ptr(),
    2572                    amount_in_second,
    2573                );
    2574            }
    2575        }
    2576
    2577        // Cleanup where the ends of the buffers are
    2578        self.len = at;
    2579        other.len = other_len;
    2580
    2581        other
    2582    }
    2583
    2584    /// Moves all the elements of `other` into `self`, leaving `other` empty.
    2585    ///
    2586    /// # Panics
    2587    ///
    2588    /// Panics if the new number of elements in self overflows a `usize`.
    2589    ///
    2590    /// # Examples
    2591    ///
    2592    /// ```
    2593    /// use std::collections::VecDeque;
    2594    ///
    2595    /// let mut buf: VecDeque<_> = [1, 2].into();
    2596    /// let mut buf2: VecDeque<_> = [3, 4].into();
    2597    /// buf.append(&mut buf2);
    2598    /// assert_eq!(buf, [1, 2, 3, 4]);
    2599    /// assert_eq!(buf2, []);
    2600    /// ```
    2601    #[inline]
    2602    #[stable(feature = "append", since = "1.4.0")]
    2603    pub fn append(&mut self, other: &mut Self) {
    2604        if T::IS_ZST {
    2605            self.len = self.len.checked_add(other.len).expect("capacity overflow");
    2606            other.len = 0;
    2607            other.head = 0;
    2608            return;
    2609        }
    2610
    2611        self.reserve(other.len);
    2612        unsafe {
    2613            let (left, right) = other.as_slices();
    2614            self.copy_slice(self.to_physical_idx(self.len), left);
    2615            // no overflow, because self.capacity() >= old_cap + left.len() >= self.len + left.len()
    2616            self.copy_slice(self.to_physical_idx(self.len + left.len()), right);
    2617        }
    2618        // SAFETY: Update pointers after copying to avoid leaving doppelganger
    2619        // in case of panics.
    2620        self.len += other.len;
    2621        // Now that we own its values, forget everything in `other`.
    2622        other.len = 0;
    2623        other.head = 0;
    2624    }
    2625
    2626    /// Retains only the elements specified by the predicate.
    2627    ///
    2628    /// In other words, remove all elements `e` for which `f(&e)` returns false.
    2629    /// This method operates in place, visiting each element exactly once in the
    2630    /// original order, and preserves the order of the retained elements.
    2631    ///
    2632    /// # Examples
    2633    ///
    2634    /// ```
    2635    /// use std::collections::VecDeque;
    2636    ///
    2637    /// let mut buf = VecDeque::new();
    2638    /// buf.extend(1..5);
    2639    /// buf.retain(|&x| x % 2 == 0);
    2640    /// assert_eq!(buf, [2, 4]);
    2641    /// ```
    2642    ///
    2643    /// Because the elements are visited exactly once in the original order,
    2644    /// external state may be used to decide which elements to keep.
    2645    ///
    2646    /// ```
    2647    /// use std::collections::VecDeque;
    2648    ///
    2649    /// let mut buf = VecDeque::new();
    2650    /// buf.extend(1..6);
    2651    ///
    2652    /// let keep = [false, true, true, false, true];
    2653    /// let mut iter = keep.iter();
    2654    /// buf.retain(|_| *iter.next().unwrap());
    2655    /// assert_eq!(buf, [2, 3, 5]);
    2656    /// ```
    2657    #[stable(feature = "vec_deque_retain", since = "1.4.0")]
    2658    pub fn retain<F>(&mut self, mut f: F)
    2659    where
    2660        F: FnMut(&T) -> bool,
    2661    {
    2662        self.retain_mut(|elem| f(elem));
    2663    }
    2664
    2665    /// Retains only the elements specified by the predicate.
    2666    ///
    2667    /// In other words, remove all elements `e` for which `f(&mut e)` returns false.
    2668    /// This method operates in place, visiting each element exactly once in the
    2669    /// original order, and preserves the order of the retained elements.
    2670    ///
    2671    /// # Examples
    2672    ///
    2673    /// ```
    2674    /// use std::collections::VecDeque;
    2675    ///
    2676    /// let mut buf = VecDeque::new();
    2677    /// buf.extend(1..5);
    2678    /// buf.retain_mut(|x| if *x % 2 == 0 {
    2679    ///     *x += 1;
    2680    ///     true
    2681    /// } else {
    2682    ///     false
    2683    /// });
    2684    /// assert_eq!(buf, [3, 5]);
    2685    /// ```
    2686    #[stable(feature = "vec_retain_mut", since = "1.61.0")]
    2687    pub fn retain_mut<F>(&mut self, mut f: F)
    2688    where
    2689        F: FnMut(&mut T) -> bool,
    2690    {
    2691        let len = self.len;
    2692        let mut idx = 0;
    2693        let mut cur = 0;
    2694
    2695        // Stage 1: All values are retained.
    2696        while cur < len {
    2697            if !f(&mut self[cur]) {
    2698                cur += 1;
    2699                break;
    2700            }
    2701            cur += 1;
    2702            idx += 1;
    2703        }
    2704        // Stage 2: Swap retained value into current idx.
    2705        while cur < len {
    2706            if !f(&mut self[cur]) {
    2707                cur += 1;
    2708                continue;
    2709            }
    2710
    2711            self.swap(idx, cur);
    2712            cur += 1;
    2713            idx += 1;
    2714        }
    2715        // Stage 3: Truncate all values after idx.
    2716        if cur != idx {
    2717            self.truncate(idx);
    2718        }
    2719    }
    2720
    2721    // Double the buffer size. This method is inline(never), so we expect it to only
    2722    // be called in cold paths.
    2723    // This may panic or abort
    2724    #[inline(never)]
    2725    fn grow(&mut self) {
    2726        // Extend or possibly remove this assertion when valid use-cases for growing the
    2727        // buffer without it being full emerge
    2728        debug_assert!(self.is_full());
    2729        let old_cap = self.capacity();
    2730        self.buf.grow_one();
    2731        unsafe {
    2732            self.handle_capacity_increase(old_cap);
    2733        }
    2734        debug_assert!(!self.is_full());
    2735    }
    2736
    2737    /// Modifies the deque in-place so that `len()` is equal to `new_len`,
    2738    /// either by removing excess elements from the back or by appending
    2739    /// elements generated by calling `generator` to the back.
    2740    ///
    2741    /// # Examples
    2742    ///
    2743    /// ```
    2744    /// use std::collections::VecDeque;
    2745    ///
    2746    /// let mut buf = VecDeque::new();
    2747    /// buf.push_back(5);
    2748    /// buf.push_back(10);
    2749    /// buf.push_back(15);
    2750    /// assert_eq!(buf, [5, 10, 15]);
    2751    ///
    2752    /// buf.resize_with(5, Default::default);
    2753    /// assert_eq!(buf, [5, 10, 15, 0, 0]);
    2754    ///
    2755    /// buf.resize_with(2, || unreachable!());
    2756    /// assert_eq!(buf, [5, 10]);
    2757    ///
    2758    /// let mut state = 100;
    2759    /// buf.resize_with(5, || { state += 1; state });
    2760    /// assert_eq!(buf, [5, 10, 101, 102, 103]);
    2761    /// ```
    2762    #[stable(feature = "vec_resize_with", since = "1.33.0")]
    2763    pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) {
    2764        let len = self.len;
    2765
    2766        if new_len > len {
    2767            self.extend(repeat_with(generator).take(new_len - len))
    2768        } else {
    2769            self.truncate(new_len);
    2770        }
    2771    }
    2772
    2773    /// Rearranges the internal storage of this deque so it is one contiguous
    2774    /// slice, which is then returned.
    2775    ///
    2776    /// This method does not allocate and does not change the order of the
    2777    /// inserted elements. As it returns a mutable slice, this can be used to
    2778    /// sort a deque.
    2779    ///
    2780    /// Once the internal storage is contiguous, the [`as_slices`] and
    2781    /// [`as_mut_slices`] methods will return the entire contents of the
    2782    /// deque in a single slice.
    2783    ///
    2784    /// [`as_slices`]: VecDeque::as_slices
    2785    /// [`as_mut_slices`]: VecDeque::as_mut_slices
    2786    ///
    2787    /// # Examples
    2788    ///
    2789    /// Sorting the content of a deque.
    2790    ///
    2791    /// ```
    2792    /// use std::collections::VecDeque;
    2793    ///
    2794    /// let mut buf = VecDeque::with_capacity(15);
    2795    ///
    2796    /// buf.push_back(2);
    2797    /// buf.push_back(1);
    2798    /// buf.push_front(3);
    2799    ///
    2800    /// // sorting the deque
    2801    /// buf.make_contiguous().sort();
    2802    /// assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));
    2803    ///
    2804    /// // sorting it in reverse order
    2805    /// buf.make_contiguous().sort_by(|a, b| b.cmp(a));
    2806    /// assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));
    2807    /// ```
    2808    ///
    2809    /// Getting immutable access to the contiguous slice.
    2810    ///
    2811    /// ```rust
    2812    /// use std::collections::VecDeque;
    2813    ///
    2814    /// let mut buf = VecDeque::new();
    2815    ///
    2816    /// buf.push_back(2);
    2817    /// buf.push_back(1);
    2818    /// buf.push_front(3);
    2819    ///
    2820    /// buf.make_contiguous();
    2821    /// if let (slice, &[]) = buf.as_slices() {
    2822    ///     // we can now be sure that `slice` contains all elements of the deque,
    2823    ///     // while still having immutable access to `buf`.
    2824    ///     assert_eq!(buf.len(), slice.len());
    2825    ///     assert_eq!(slice, &[3, 2, 1] as &[_]);
    2826    /// }
    2827    /// ```
    2828    #[stable(feature = "deque_make_contiguous", since = "1.48.0")]
    2829    pub fn make_contiguous(&mut self) -> &mut [T] {
    2830        if T::IS_ZST {
    2831            self.head = 0;
    2832        }
    2833
    2834        if self.is_contiguous() {
    2835            unsafe { return slice::from_raw_parts_mut(self.ptr().add(self.head), self.len) }
    2836        }
    2837
    2838        let &mut Self { head, len, .. } = self;
    2839        let ptr = self.ptr();
    2840        let cap = self.capacity();
    2841
    2842        let free = cap - len;
    2843        let head_len = cap - head;
    2844        let tail = len - head_len;
    2845        let tail_len = tail;
    2846
    2847        if free >= head_len {
    2848            // there is enough free space to copy the head in one go,
    2849            // this means that we first shift the tail backwards, and then
    2850            // copy the head to the correct position.
    2851            //
    2852            // from: DEFGH....ABC
    2853            // to:   ABCDEFGH....
    2854            unsafe {
    2855                self.copy(0, head_len, tail_len);
    2856                // ...DEFGH.ABC
    2857                self.copy_nonoverlapping(head, 0, head_len);
    2858                // ABCDEFGH....
    2859            }
    2860
    2861            self.head = 0;
    2862        } else if free >= tail_len {
    2863            // there is enough free space to copy the tail in one go,
    2864            // this means that we first shift the head forwards, and then
    2865            // copy the tail to the correct position.
    2866            //
    2867            // from: FGH....ABCDE
    2868            // to:   ...ABCDEFGH.
    2869            unsafe {
    2870                self.copy(head, tail, head_len);
    2871                // FGHABCDE....
    2872                self.copy_nonoverlapping(0, tail + head_len, tail_len);
    2873                // ...ABCDEFGH.
    2874            }
    2875
    2876            self.head = tail;
    2877        } else {
    2878            // `free` is smaller than both `head_len` and `tail_len`.
    2879            // the general algorithm for this first moves the slices
    2880            // right next to each other and then uses `slice::rotate`
    2881            // to rotate them into place:
    2882            //
    2883            // initially:   HIJK..ABCDEFG
    2884            // step 1:      ..HIJKABCDEFG
    2885            // step 2:      ..ABCDEFGHIJK
    2886            //
    2887            // or:
    2888            //
    2889            // initially:   FGHIJK..ABCDE
    2890            // step 1:      FGHIJKABCDE..
    2891            // step 2:      ABCDEFGHIJK..
    2892
    2893            // pick the shorter of the 2 slices to reduce the amount
    2894            // of memory that needs to be moved around.
    2895            if head_len > tail_len {
    2896                // tail is shorter, so:
    2897                //  1. copy tail forwards
    2898                //  2. rotate used part of the buffer
    2899                //  3. update head to point to the new beginning (which is just `free`)
    2900
    2901                unsafe {
    2902                    // if there is no free space in the buffer, then the slices are already
    2903                    // right next to each other and we don't need to move any memory.
    2904                    if free != 0 {
    2905                        // because we only move the tail forward as much as there's free space
    2906                        // behind it, we don't overwrite any elements of the head slice, and
    2907                        // the slices end up right next to each other.
    2908                        self.copy(0, free, tail_len);
    2909                    }
    2910
    2911                    // We just copied the tail right next to the head slice,
    2912                    // so all of the elements in the range are initialized
    2913                    let slice = &mut *self.buffer_range(free..self.capacity());
    2914
    2915                    // because the deque wasn't contiguous, we know that `tail_len < self.len == slice.len()`,
    2916                    // so this will never panic.
    2917                    slice.rotate_left(tail_len);
    2918
    2919                    // the used part of the buffer now is `free..self.capacity()`, so set
    2920                    // `head` to the beginning of that range.
    2921                    self.head = free;
    2922                }
    2923            } else {
    2924                // head is shorter so:
    2925                //  1. copy head backwards
    2926                //  2. rotate used part of the buffer
    2927                //  3. update head to point to the new beginning (which is the beginning of the buffer)
    2928
    2929                unsafe {
    2930                    // if there is no free space in the buffer, then the slices are already
    2931                    // right next to each other and we don't need to move any memory.
    2932                    if free != 0 {
    2933                        // copy the head slice to lie right behind the tail slice.
    2934                        self.copy(self.head, tail_len, head_len);
    2935                    }
    2936
    2937                    // because we copied the head slice so that both slices lie right
    2938                    // next to each other, all the elements in the range are initialized.
    2939                    let slice = &mut *self.buffer_range(0..self.len);
    2940
    2941                    // because the deque wasn't contiguous, we know that `head_len < self.len == slice.len()`
    2942                    // so this will never panic.
    2943                    slice.rotate_right(head_len);
    2944
    2945                    // the used part of the buffer now is `0..self.len`, so set
    2946                    // `head` to the beginning of that range.
    2947                    self.head = 0;
    2948                }
    2949            }
    2950        }
    2951
    2952        unsafe { slice::from_raw_parts_mut(ptr.add(self.head), self.len) }
    2953    }
    2954
    2955    /// Rotates the double-ended queue `n` places to the left.
    2956    ///
    2957    /// Equivalently,
    2958    /// - Rotates item `n` into the first position.
    2959    /// - Pops the first `n` items and pushes them to the end.
    2960    /// - Rotates `len() - n` places to the right.
    2961    ///
    2962    /// # Panics
    2963    ///
    2964    /// If `n` is greater than `len()`. Note that `n == len()`
    2965    /// does _not_ panic and is a no-op rotation.
    2966    ///
    2967    /// # Complexity
    2968    ///
    2969    /// Takes `*O*(min(n, len() - n))` time and no extra space.
    2970    ///
    2971    /// # Examples
    2972    ///
    2973    /// ```
    2974    /// use std::collections::VecDeque;
    2975    ///
    2976    /// let mut buf: VecDeque<_> = (0..10).collect();
    2977    ///
    2978    /// buf.rotate_left(3);
    2979    /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);
    2980    ///
    2981    /// for i in 1..10 {
    2982    ///     assert_eq!(i * 3 % 10, buf[0]);
    2983    ///     buf.rotate_left(3);
    2984    /// }
    2985    /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    2986    /// ```
    2987    #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
    2988    pub fn rotate_left(&mut self, n: usize) {
    2989        assert!(n <= self.len());
    2990        let k = self.len - n;
    2991        if n <= k {
    2992            unsafe { self.rotate_left_inner(n) }
    2993        } else {
    2994            unsafe { self.rotate_right_inner(k) }
    2995        }
    2996    }
    2997
    2998    /// Rotates the double-ended queue `n` places to the right.
    2999    ///
    3000    /// Equivalently,
    3001    /// - Rotates the first item into position `n`.
    3002    /// - Pops the last `n` items and pushes them to the front.
    3003    /// - Rotates `len() - n` places to the left.
    3004    ///
    3005    /// # Panics
    3006    ///
    3007    /// If `n` is greater than `len()`. Note that `n == len()`
    3008    /// does _not_ panic and is a no-op rotation.
    3009    ///
    3010    /// # Complexity
    3011    ///
    3012    /// Takes `*O*(min(n, len() - n))` time and no extra space.
    3013    ///
    3014    /// # Examples
    3015    ///
    3016    /// ```
    3017    /// use std::collections::VecDeque;
    3018    ///
    3019    /// let mut buf: VecDeque<_> = (0..10).collect();
    3020    ///
    3021    /// buf.rotate_right(3);
    3022    /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);
    3023    ///
    3024    /// for i in 1..10 {
    3025    ///     assert_eq!(0, buf[i * 3 % 10]);
    3026    ///     buf.rotate_right(3);
    3027    /// }
    3028    /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    3029    /// ```
    3030    #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
    3031    pub fn rotate_right(&mut self, n: usize) {
    3032        assert!(n <= self.len());
    3033        let k = self.len - n;
    3034        if n <= k {
    3035            unsafe { self.rotate_right_inner(n) }
    3036        } else {
    3037            unsafe { self.rotate_left_inner(k) }
    3038        }
    3039    }
    3040
    3041    // SAFETY: the following two methods require that the rotation amount
    3042    // be less than half the length of the deque.
    3043    //
    3044    // `wrap_copy` requires that `min(x, capacity() - x) + copy_len <= capacity()`,
    3045    // but then `min` is never more than half the capacity, regardless of x,
    3046    // so it's sound to call here because we're calling with something
    3047    // less than half the length, which is never above half the capacity.
    3048
    3049    unsafe fn rotate_left_inner(&mut self, mid: usize) {
    3050        debug_assert!(mid * 2 <= self.len());
    3051        unsafe {
    3052            self.wrap_copy(self.head, self.to_physical_idx(self.len), mid);
    3053        }
    3054        self.head = self.to_physical_idx(mid);
    3055    }
    3056
    3057    unsafe fn rotate_right_inner(&mut self, k: usize) {
    3058        debug_assert!(k * 2 <= self.len());
    3059        self.head = self.wrap_sub(self.head, k);
    3060        unsafe {
    3061            self.wrap_copy(self.to_physical_idx(self.len), self.head, k);
    3062        }
    3063    }
    3064
    3065    /// Binary searches this `VecDeque` for a given element.
    3066    /// If the `VecDeque` is not sorted, the returned result is unspecified and
    3067    /// meaningless.
    3068    ///
    3069    /// If the value is found then [`Result::Ok`] is returned, containing the
    3070    /// index of the matching element. If there are multiple matches, then any
    3071    /// one of the matches could be returned. If the value is not found then
    3072    /// [`Result::Err`] is returned, containing the index where a matching
    3073    /// element could be inserted while maintaining sorted order.
    3074    ///
    3075    /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
    3076    ///
    3077    /// [`binary_search_by`]: VecDeque::binary_search_by
    3078    /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
    3079    /// [`partition_point`]: VecDeque::partition_point
    3080    ///
    3081    /// # Examples
    3082    ///
    3083    /// Looks up a series of four elements. The first is found, with a
    3084    /// uniquely determined position; the second and third are not
    3085    /// found; the fourth could match any position in `[1, 4]`.
    3086    ///
    3087    /// ```
    3088    /// use std::collections::VecDeque;
    3089    ///
    3090    /// let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    3091    ///
    3092    /// assert_eq!(deque.binary_search(&13),  Ok(9));
    3093    /// assert_eq!(deque.binary_search(&4),   Err(7));
    3094    /// assert_eq!(deque.binary_search(&100), Err(13));
    3095    /// let r = deque.binary_search(&1);
    3096    /// assert!(matches!(r, Ok(1..=4)));
    3097    /// ```
    3098    ///
    3099    /// If you want to insert an item to a sorted deque, while maintaining
    3100    /// sort order, consider using [`partition_point`]:
    3101    ///
    3102    /// ```
    3103    /// use std::collections::VecDeque;
    3104    ///
    3105    /// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    3106    /// let num = 42;
    3107    /// let idx = deque.partition_point(|&x| x <= num);
    3108    /// // If `num` is unique, `s.partition_point(|&x| x < num)` (with `<`) is equivalent to
    3109    /// // `s.binary_search(&num).unwrap_or_else(|x| x)`, but using `<=` may allow `insert`
    3110    /// // to shift less elements.
    3111    /// deque.insert(idx, num);
    3112    /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
    3113    /// ```
    3114    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    3115    #[inline]
    3116    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
    3117    where
    3118        T: Ord,
    3119    {
    3120        self.binary_search_by(|e| e.cmp(x))
    3121    }
    3122
    3123    /// Binary searches this `VecDeque` with a comparator function.
    3124    ///
    3125    /// The comparator function should return an order code that indicates
    3126    /// whether its argument is `Less`, `Equal` or `Greater` the desired
    3127    /// target.
    3128    /// If the `VecDeque` is not sorted or if the comparator function does not
    3129    /// implement an order consistent with the sort order of the underlying
    3130    /// `VecDeque`, the returned result is unspecified and meaningless.
    3131    ///
    3132    /// If the value is found then [`Result::Ok`] is returned, containing the
    3133    /// index of the matching element. If there are multiple matches, then any
    3134    /// one of the matches could be returned. If the value is not found then
    3135    /// [`Result::Err`] is returned, containing the index where a matching
    3136    /// element could be inserted while maintaining sorted order.
    3137    ///
    3138    /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
    3139    ///
    3140    /// [`binary_search`]: VecDeque::binary_search
    3141    /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
    3142    /// [`partition_point`]: VecDeque::partition_point
    3143    ///
    3144    /// # Examples
    3145    ///
    3146    /// Looks up a series of four elements. The first is found, with a
    3147    /// uniquely determined position; the second and third are not
    3148    /// found; the fourth could match any position in `[1, 4]`.
    3149    ///
    3150    /// ```
    3151    /// use std::collections::VecDeque;
    3152    ///
    3153    /// let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    3154    ///
    3155    /// assert_eq!(deque.binary_search_by(|x| x.cmp(&13)),  Ok(9));
    3156    /// assert_eq!(deque.binary_search_by(|x| x.cmp(&4)),   Err(7));
    3157    /// assert_eq!(deque.binary_search_by(|x| x.cmp(&100)), Err(13));
    3158    /// let r = deque.binary_search_by(|x| x.cmp(&1));
    3159    /// assert!(matches!(r, Ok(1..=4)));
    3160    /// ```
    3161    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    3162    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
    3163    where
    3164        F: FnMut(&'a T) -> Ordering,
    3165    {
    3166        let (front, back) = self.as_slices();
    3167        let cmp_back = back.first().map(|elem| f(elem));
    3168
    3169        if let Some(Ordering::Equal) = cmp_back {
    3170            Ok(front.len())
    3171        } else if let Some(Ordering::Less) = cmp_back {
    3172            back.binary_search_by(f).map(|idx| idx + front.len()).map_err(|idx| idx + front.len())
    3173        } else {
    3174            front.binary_search_by(f)
    3175        }
    3176    }
    3177
    3178    /// Binary searches this `VecDeque` with a key extraction function.
    3179    ///
    3180    /// Assumes that the deque is sorted by the key, for instance with
    3181    /// [`make_contiguous().sort_by_key()`] using the same key extraction function.
    3182    /// If the deque is not sorted by the key, the returned result is
    3183    /// unspecified and meaningless.
    3184    ///
    3185    /// If the value is found then [`Result::Ok`] is returned, containing the
    3186    /// index of the matching element. If there are multiple matches, then any
    3187    /// one of the matches could be returned. If the value is not found then
    3188    /// [`Result::Err`] is returned, containing the index where a matching
    3189    /// element could be inserted while maintaining sorted order.
    3190    ///
    3191    /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
    3192    ///
    3193    /// [`make_contiguous().sort_by_key()`]: VecDeque::make_contiguous
    3194    /// [`binary_search`]: VecDeque::binary_search
    3195    /// [`binary_search_by`]: VecDeque::binary_search_by
    3196    /// [`partition_point`]: VecDeque::partition_point
    3197    ///
    3198    /// # Examples
    3199    ///
    3200    /// Looks up a series of four elements in a slice of pairs sorted by
    3201    /// their second elements. The first is found, with a uniquely
    3202    /// determined position; the second and third are not found; the
    3203    /// fourth could match any position in `[1, 4]`.
    3204    ///
    3205    /// ```
    3206    /// use std::collections::VecDeque;
    3207    ///
    3208    /// let deque: VecDeque<_> = [(0, 0), (2, 1), (4, 1), (5, 1),
    3209    ///          (3, 1), (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
    3210    ///          (1, 21), (2, 34), (4, 55)].into();
    3211    ///
    3212    /// assert_eq!(deque.binary_search_by_key(&13, |&(a, b)| b),  Ok(9));
    3213    /// assert_eq!(deque.binary_search_by_key(&4, |&(a, b)| b),   Err(7));
    3214    /// assert_eq!(deque.binary_search_by_key(&100, |&(a, b)| b), Err(13));
    3215    /// let r = deque.binary_search_by_key(&1, |&(a, b)| b);
    3216    /// assert!(matches!(r, Ok(1..=4)));
    3217    /// ```
    3218    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    3219    #[inline]
    3220    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
    3221    where
    3222        F: FnMut(&'a T) -> B,
    3223        B: Ord,
    3224    {
    3225        self.binary_search_by(|k| f(k).cmp(b))
    3226    }
    3227
    3228    /// Returns the index of the partition point according to the given predicate
    3229    /// (the index of the first element of the second partition).
    3230    ///
    3231    /// The deque is assumed to be partitioned according to the given predicate.
    3232    /// This means that all elements for which the predicate returns true are at the start of the deque
    3233    /// and all elements for which the predicate returns false are at the end.
    3234    /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0`
    3235    /// (all odd numbers are at the start, all even at the end).
    3236    ///
    3237    /// If the deque is not partitioned, the returned result is unspecified and meaningless,
    3238    /// as this method performs a kind of binary search.
    3239    ///
    3240    /// See also [`binary_search`], [`binary_search_by`], and [`binary_search_by_key`].
    3241    ///
    3242    /// [`binary_search`]: VecDeque::binary_search
    3243    /// [`binary_search_by`]: VecDeque::binary_search_by
    3244    /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
    3245    ///
    3246    /// # Examples
    3247    ///
    3248    /// ```
    3249    /// use std::collections::VecDeque;
    3250    ///
    3251    /// let deque: VecDeque<_> = [1, 2, 3, 3, 5, 6, 7].into();
    3252    /// let i = deque.partition_point(|&x| x < 5);
    3253    ///
    3254    /// assert_eq!(i, 4);
    3255    /// assert!(deque.iter().take(i).all(|&x| x < 5));
    3256    /// assert!(deque.iter().skip(i).all(|&x| !(x < 5)));
    3257    /// ```
    3258    ///
    3259    /// If you want to insert an item to a sorted deque, while maintaining
    3260    /// sort order:
    3261    ///
    3262    /// ```
    3263    /// use std::collections::VecDeque;
    3264    ///
    3265    /// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    3266    /// let num = 42;
    3267    /// let idx = deque.partition_point(|&x| x < num);
    3268    /// deque.insert(idx, num);
    3269    /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
    3270    /// ```
    3271    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    3272    pub fn partition_point<P>(&self, mut pred: P) -> usize
    3273    where
    3274        P: FnMut(&T) -> bool,
    3275    {
    3276        let (front, back) = self.as_slices();
    3277
    3278        if let Some(true) = back.first().map(|v| pred(v)) {
    3279            back.partition_point(pred) + front.len()
    3280        } else {
    3281            front.partition_point(pred)
    3282        }
    3283    }
    3284}
    3285
    3286impl<T: Clone, A: Allocator> VecDeque<T, A> {
    3287    /// Modifies the deque in-place so that `len()` is equal to new_len,
    3288    /// either by removing excess elements from the back or by appending clones of `value`
    3289    /// to the back.
    3290    ///
    3291    /// # Examples
    3292    ///
    3293    /// ```
    3294    /// use std::collections::VecDeque;
    3295    ///
    3296    /// let mut buf = VecDeque::new();
    3297    /// buf.push_back(5);
    3298    /// buf.push_back(10);
    3299    /// buf.push_back(15);
    3300    /// assert_eq!(buf, [5, 10, 15]);
    3301    ///
    3302    /// buf.resize(2, 0);
    3303    /// assert_eq!(buf, [5, 10]);
    3304    ///
    3305    /// buf.resize(5, 20);
    3306    /// assert_eq!(buf, [5, 10, 20, 20, 20]);
    3307    /// ```
    3308    #[stable(feature = "deque_extras", since = "1.16.0")]
    3309    pub fn resize(&mut self, new_len: usize, value: T) {
    3310        if new_len > self.len() {
    3311            let extra = new_len - self.len();
    3312            self.extend(repeat_n(value, extra))
    3313        } else {
    3314            self.truncate(new_len);
    3315        }
    3316    }
    3317
    3318    /// Clones the elements at the range `src` and appends them to the end.
    3319    ///
    3320    /// # Panics
    3321    ///
    3322    /// Panics if the starting index is greater than the end index
    3323    /// or if either index is greater than the length of the vector.
    3324    ///
    3325    /// # Examples
    3326    ///
    3327    /// ```
    3328    /// #![feature(deque_extend_front)]
    3329    /// use std::collections::VecDeque;
    3330    ///
    3331    /// let mut characters = VecDeque::from(['a', 'b', 'c', 'd', 'e']);
    3332    /// characters.extend_from_within(2..);
    3333    /// assert_eq!(characters, ['a', 'b', 'c', 'd', 'e', 'c', 'd', 'e']);
    3334    ///
    3335    /// let mut numbers = VecDeque::from([0, 1, 2, 3, 4]);
    3336    /// numbers.extend_from_within(..2);
    3337    /// assert_eq!(numbers, [0, 1, 2, 3, 4, 0, 1]);
    3338    ///
    3339    /// let mut strings = VecDeque::from([String::from("hello"), String::from("world"), String::from("!")]);
    3340    /// strings.extend_from_within(1..=2);
    3341    /// assert_eq!(strings, ["hello", "world", "!", "world", "!"]);
    3342    /// ```
    3343    #[cfg(not(no_global_oom_handling))]
    3344    #[unstable(feature = "deque_extend_front", issue = "146975")]
    3345    pub fn extend_from_within<R>(&mut self, src: R)
    3346    where
    3347        R: RangeBounds<usize>,
    3348    {
    3349        let range = slice::range(src, ..self.len());
    3350        self.reserve(range.len());
    3351
    3352        // SAFETY:
    3353        // - `slice::range` guarantees that the given range is valid for indexing self
    3354        // - at least `range.len()` additional space is available
    3355        unsafe {
    3356            self.spec_extend_from_within(range);
    3357        }
    3358    }
    3359
    3360    /// Clones the elements at the range `src` and prepends them to the front.
    3361    ///
    3362    /// # Panics
    3363    ///
    3364    /// Panics if the starting index is greater than the end index
    3365    /// or if either index is greater than the length of the vector.
    3366    ///
    3367    /// # Examples
    3368    ///
    3369    /// ```
    3370    /// #![feature(deque_extend_front)]
    3371    /// use std::collections::VecDeque;
    3372    ///
    3373    /// let mut characters = VecDeque::from(['a', 'b', 'c', 'd', 'e']);
    3374    /// characters.prepend_from_within(2..);
    3375    /// assert_eq!(characters, ['c', 'd', 'e', 'a', 'b', 'c', 'd', 'e']);
    3376    ///
    3377    /// let mut numbers = VecDeque::from([0, 1, 2, 3, 4]);
    3378    /// numbers.prepend_from_within(..2);
    3379    /// assert_eq!(numbers, [0, 1, 0, 1, 2, 3, 4]);
    3380    ///
    3381    /// let mut strings = VecDeque::from([String::from("hello"), String::from("world"), String::from("!")]);
    3382    /// strings.prepend_from_within(1..=2);
    3383    /// assert_eq!(strings, ["world", "!", "hello", "world", "!"]);
    3384    /// ```
    3385    #[cfg(not(no_global_oom_handling))]
    3386    #[unstable(feature = "deque_extend_front", issue = "146975")]
    3387    pub fn prepend_from_within<R>(&mut self, src: R)
    3388    where
    3389        R: RangeBounds<usize>,
    3390    {
    3391        let range = slice::range(src, ..self.len());
    3392        self.reserve(range.len());
    3393
    3394        // SAFETY:
    3395        // - `slice::range` guarantees that the given range is valid for indexing self
    3396        // - at least `range.len()` additional space is available
    3397        unsafe {
    3398            self.spec_prepend_from_within(range);
    3399        }
    3400    }
    3401}
    3402
    3403/// Associated functions have the following preconditions:
    3404///
    3405/// - `src` needs to be a valid range: `src.start <= src.end <= self.len()`.
    3406/// - The buffer must have enough spare capacity: `self.capacity() - self.len() >= src.len()`.
    3407#[cfg(not(no_global_oom_handling))]
    3408trait SpecExtendFromWithin {
    3409    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
    3410
    3411    unsafe fn spec_prepend_from_within(&mut self, src: Range<usize>);
    3412}
    3413
    3414#[cfg(not(no_global_oom_handling))]
    3415impl<T: Clone, A: Allocator> SpecExtendFromWithin for VecDeque<T, A> {
    3416    default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
    3417        let dst = self.len();
    3418        let count = src.end - src.start;
    3419        let src = src.start;
    3420
    3421        unsafe {
    3422            // SAFETY:
    3423            // - Ranges do not overlap: src entirely spans initialized values, dst entirely spans uninitialized values.
    3424            // - Ranges are in bounds: guaranteed by the caller.
    3425            let ranges = self.nonoverlapping_ranges(src, dst, count, self.head);
    3426
    3427            // `len` is updated after every clone to prevent leaking and
    3428            // leave the deque in the right state when a clone implementation panics
    3429
    3430            for (src, dst, count) in ranges {
    3431                for offset in 0..count {
    3432                    dst.add(offset).write((*src.add(offset)).clone());
    3433                    self.len += 1;
    3434                }
    3435            }
    3436        }
    3437    }
    3438
    3439    default unsafe fn spec_prepend_from_within(&mut self, src: Range<usize>) {
    3440        let dst = 0;
    3441        let count = src.end - src.start;
    3442        let src = src.start + count;
    3443
    3444        let new_head = self.wrap_sub(self.head, count);
    3445        let cap = self.capacity();
    3446
    3447        unsafe {
    3448            // SAFETY:
    3449            // - Ranges do not overlap: src entirely spans initialized values, dst entirely spans uninitialized values.
    3450            // - Ranges are in bounds: guaranteed by the caller.
    3451            let ranges = self.nonoverlapping_ranges(src, dst, count, new_head);
    3452
    3453            // Cloning is done in reverse because we prepend to the front of the deque,
    3454            // we can't get holes in the *logical* buffer.
    3455            // `head` and `len` are updated after every clone to prevent leaking and
    3456            // leave the deque in the right state when a clone implementation panics
    3457
    3458            // Clone the first range
    3459            let (src, dst, count) = ranges[1];
    3460            for offset in (0..count).rev() {
    3461                dst.add(offset).write((*src.add(offset)).clone());
    3462                self.head -= 1;
    3463                self.len += 1;
    3464            }
    3465
    3466            // Clone the second range
    3467            let (src, dst, count) = ranges[0];
    3468            let mut iter = (0..count).rev();
    3469            if let Some(offset) = iter.next() {
    3470                dst.add(offset).write((*src.add(offset)).clone());
    3471                // After the first clone of the second range, wrap `head` around
    3472                if self.head == 0 {
    3473                    self.head = cap;
    3474                }
    3475                self.head -= 1;
    3476                self.len += 1;
    3477
    3478                // Continue like normal
    3479                for offset in iter {
    3480                    dst.add(offset).write((*src.add(offset)).clone());
    3481                    self.head -= 1;
    3482                    self.len += 1;
    3483                }
    3484            }
    3485        }
    3486    }
    3487}
    3488
    3489#[cfg(not(no_global_oom_handling))]
    3490impl<T: TrivialClone, A: Allocator> SpecExtendFromWithin for VecDeque<T, A> {
    3491    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
    3492        let dst = self.len();
    3493        let count = src.end - src.start;
    3494        let src = src.start;
    3495
    3496        unsafe {
    3497            // SAFETY:
    3498            // - Ranges do not overlap: src entirely spans initialized values, dst entirely spans uninitialized values.
    3499            // - Ranges are in bounds: guaranteed by the caller.
    3500            let ranges = self.nonoverlapping_ranges(src, dst, count, self.head);
    3501            for (src, dst, count) in ranges {
    3502                ptr::copy_nonoverlapping(src, dst, count);
    3503            }
    3504        }
    3505
    3506        // SAFETY:
    3507        // - The elements were just initialized by `copy_nonoverlapping`
    3508        self.len += count;
    3509    }
    3510
    3511    unsafe fn spec_prepend_from_within(&mut self, src: Range<usize>) {
    3512        let dst = 0;
    3513        let count = src.end - src.start;
    3514        let src = src.start + count;
    3515
    3516        let new_head = self.wrap_sub(self.head, count);
    3517
    3518        unsafe {
    3519            // SAFETY:
    3520            // - Ranges do not overlap: src entirely spans initialized values, dst entirely spans uninitialized values.
    3521            // - Ranges are in bounds: guaranteed by the caller.
    3522            let ranges = self.nonoverlapping_ranges(src, dst, count, new_head);
    3523            for (src, dst, count) in ranges {
    3524                ptr::copy_nonoverlapping(src, dst, count);
    3525            }
    3526        }
    3527
    3528        // SAFETY:
    3529        // - The elements were just initialized by `copy_nonoverlapping`
    3530        self.head = new_head;
    3531        self.len += count;
    3532    }
    3533}
    3534
    3535/// Returns the index in the underlying buffer for a given logical element index.
    3536#[inline]
    3537fn wrap_index(logical_index: usize, capacity: usize) -> usize {
    3538    debug_assert!(
    3539        (logical_index == 0 && capacity == 0)
    3540            || logical_index < capacity
    3541            || (logical_index - capacity) < capacity
    3542    );
    3543    if logical_index >= capacity { logical_index - capacity } else { logical_index }
    3544}
    3545
    3546#[stable(feature = "rust1", since = "1.0.0")]
    3547impl<T: PartialEq, A: Allocator> PartialEq for VecDeque<T, A> {
    3548    fn eq(&self, other: &Self) -> bool {
    3549        if self.len != other.len() {
    3550            return false;
    3551        }
    3552        let (sa, sb) = self.as_slices();
    3553        let (oa, ob) = other.as_slices();
    3554        if sa.len() == oa.len() {
    3555            sa == oa && sb == ob
    3556        } else if sa.len() < oa.len() {
    3557            // Always divisible in three sections, for example:
    3558            // self:  [a b c|d e f]
    3559            // other: [0 1 2 3|4 5]
    3560            // front = 3, mid = 1,
    3561            // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
    3562            let front = sa.len();
    3563            let mid = oa.len() - front;
    3564
    3565            let (oa_front, oa_mid) = oa.split_at(front);
    3566            let (sb_mid, sb_back) = sb.split_at(mid);
    3567            debug_assert_eq!(sa.len(), oa_front.len());
    3568            debug_assert_eq!(sb_mid.len(), oa_mid.len());
    3569            debug_assert_eq!(sb_back.len(), ob.len());
    3570            sa == oa_front && sb_mid == oa_mid && sb_back == ob
    3571        } else {
    3572            let front = oa.len();
    3573            let mid = sa.len() - front;
    3574
    3575            let (sa_front, sa_mid) = sa.split_at(front);
    3576            let (ob_mid, ob_back) = ob.split_at(mid);
    3577            debug_assert_eq!(sa_front.len(), oa.len());
    3578            debug_assert_eq!(sa_mid.len(), ob_mid.len());
    3579            debug_assert_eq!(sb.len(), ob_back.len());
    3580            sa_front == oa && sa_mid == ob_mid && sb == ob_back
    3581        }
    3582    }
    3583}
    3584
    3585#[stable(feature = "rust1", since = "1.0.0")]
    3586impl<T: Eq, A: Allocator> Eq for VecDeque<T, A> {}
    3587
    3588__impl_slice_eq1! { [] VecDeque<T, A>, Vec<U, A>, }
    3589__impl_slice_eq1! { [] VecDeque<T, A>, &[U], }
    3590__impl_slice_eq1! { [] VecDeque<T, A>, &mut [U], }
    3591__impl_slice_eq1! { [const N: usize] VecDeque<T, A>, [U; N], }
    3592__impl_slice_eq1! { [const N: usize] VecDeque<T, A>, &[U; N], }
    3593__impl_slice_eq1! { [const N: usize] VecDeque<T, A>, &mut [U; N], }
    3594
    3595#[stable(feature = "rust1", since = "1.0.0")]
    3596impl<T: PartialOrd, A: Allocator> PartialOrd for VecDeque<T, A> {
    3597    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    3598        self.iter().partial_cmp(other.iter())
    3599    }
    3600}
    3601
    3602#[stable(feature = "rust1", since = "1.0.0")]
    3603impl<T: Ord, A: Allocator> Ord for VecDeque<T, A> {
    3604    #[inline]
    3605    fn cmp(&self, other: &Self) -> Ordering {
    3606        self.iter().cmp(other.iter())
    3607    }
    3608}
    3609
    3610#[stable(feature = "rust1", since = "1.0.0")]
    3611impl<T: Hash, A: Allocator> Hash for VecDeque<T, A> {
    3612    fn hash<H: Hasher>(&self, state: &mut H) {
    3613        state.write_length_prefix(self.len);
    3614        // It's not possible to use Hash::hash_slice on slices
    3615        // returned by as_slices method as their length can vary
    3616        // in otherwise identical deques.
    3617        //
    3618        // Hasher only guarantees equivalence for the exact same
    3619        // set of calls to its methods.
    3620        self.iter().for_each(|elem| elem.hash(state));
    3621    }
    3622}
    3623
    3624#[stable(feature = "rust1", since = "1.0.0")]
    3625impl<T, A: Allocator> Index<usize> for VecDeque<T, A> {
    3626    type Output = T;
    3627
    3628    #[inline]
    3629    fn index(&self, index: usize) -> &T {
    3630        self.get(index).expect("Out of bounds access")
    3631    }
    3632}
    3633
    3634#[stable(feature = "rust1", since = "1.0.0")]
    3635impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A> {
    3636    #[inline]
    3637    fn index_mut(&mut self, index: usize) -> &mut T {
    3638        self.get_mut(index).expect("Out of bounds access")
    3639    }
    3640}
    3641
    3642#[stable(feature = "rust1", since = "1.0.0")]
    3643impl<T> FromIterator<T> for VecDeque<T> {
    3644    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T> {
    3645        SpecFromIter::spec_from_iter(iter.into_iter())
    3646    }
    3647}
    3648
    3649#[stable(feature = "rust1", since = "1.0.0")]
    3650impl<T, A: Allocator> IntoIterator for VecDeque<T, A> {
    3651    type Item = T;
    3652    type IntoIter = IntoIter<T, A>;
    3653
    3654    /// Consumes the deque into a front-to-back iterator yielding elements by
    3655    /// value.
    3656    fn into_iter(self) -> IntoIter<T, A> {
    3657        IntoIter::new(self)
    3658    }
    3659}
    3660
    3661#[stable(feature = "rust1", since = "1.0.0")]
    3662impl<'a, T, A: Allocator> IntoIterator for &'a VecDeque<T, A> {
    3663    type Item = &'a T;
    3664    type IntoIter = Iter<'a, T>;
    3665
    3666    fn into_iter(self) -> Iter<'a, T> {
    3667        self.iter()
    3668    }
    3669}
    3670
    3671#[stable(feature = "rust1", since = "1.0.0")]
    3672impl<'a, T, A: Allocator> IntoIterator for &'a mut VecDeque<T, A> {
    3673    type Item = &'a mut T;
    3674    type IntoIter = IterMut<'a, T>;
    3675
    3676    fn into_iter(self) -> IterMut<'a, T> {
    3677        self.iter_mut()
    3678    }
    3679}
    3680
    3681#[stable(feature = "rust1", since = "1.0.0")]
    3682impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
    3683    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
    3684        <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
    3685    }
    3686
    3687    #[inline]
    3688    fn extend_one(&mut self, elem: T) {
    3689        self.push_back(elem);
    3690    }
    3691
    3692    #[inline]
    3693    fn extend_reserve(&mut self, additional: usize) {
    3694        self.reserve(additional);
    3695    }
    3696
    3697    #[inline]
    3698    unsafe fn extend_one_unchecked(&mut self, item: T) {
    3699        // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
    3700        unsafe {
    3701            self.push_unchecked(item);
    3702        }
    3703    }
    3704}
    3705
    3706#[stable(feature = "extend_ref", since = "1.2.0")]
    3707impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> {
    3708    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
    3709        self.spec_extend(iter.into_iter());
    3710    }
    3711
    3712    #[inline]
    3713    fn extend_one(&mut self, &elem: &'a T) {
    3714        self.push_back(elem);
    3715    }
    3716
    3717    #[inline]
    3718    fn extend_reserve(&mut self, additional: usize) {
    3719        self.reserve(additional);
    3720    }
    3721
    3722    #[inline]
    3723    unsafe fn extend_one_unchecked(&mut self, &item: &'a T) {
    3724        // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
    3725        unsafe {
    3726            self.push_unchecked(item);
    3727        }
    3728    }
    3729}
    3730
    3731#[stable(feature = "rust1", since = "1.0.0")]
    3732impl<T: fmt::Debug, A: Allocator> fmt::Debug for VecDeque<T, A> {
    3733    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    3734        f.debug_list().entries(self.iter()).finish()
    3735    }
    3736}
    3737
    3738#[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
    3739impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> {
    3740    /// Turn a [`Vec<T>`] into a [`VecDeque<T>`].
    3741    ///
    3742    /// [`Vec<T>`]: crate::vec::Vec
    3743    /// [`VecDeque<T>`]: crate::collections::VecDeque
    3744    ///
    3745    /// This conversion is guaranteed to run in *O*(1) time
    3746    /// and to not re-allocate the `Vec`'s buffer or allocate
    3747    /// any additional memory.
    3748    #[inline]
    3749    fn from(other: Vec<T, A>) -> Self {
    3750        let (ptr, len, cap, alloc) = other.into_raw_parts_with_alloc();
    3751        Self { head: 0, len, buf: unsafe { RawVec::from_raw_parts_in(ptr, cap, alloc) } }
    3752    }
    3753}
    3754
    3755#[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
    3756impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A> {
    3757    /// Turn a [`VecDeque<T>`] into a [`Vec<T>`].
    3758    ///
    3759    /// [`Vec<T>`]: crate::vec::Vec
    3760    /// [`VecDeque<T>`]: crate::collections::VecDeque
    3761    ///
    3762    /// This never needs to re-allocate, but does need to do *O*(*n*) data movement if
    3763    /// the circular buffer doesn't happen to be at the beginning of the allocation.
    3764    ///
    3765    /// # Examples
    3766    ///
    3767    /// ```
    3768    /// use std::collections::VecDeque;
    3769    ///
    3770    /// // This one is *O*(1).
    3771    /// let deque: VecDeque<_> = (1..5).collect();
    3772    /// let ptr = deque.as_slices().0.as_ptr();
    3773    /// let vec = Vec::from(deque);
    3774    /// assert_eq!(vec, [1, 2, 3, 4]);
    3775    /// assert_eq!(vec.as_ptr(), ptr);
    3776    ///
    3777    /// // This one needs data rearranging.
    3778    /// let mut deque: VecDeque<_> = (1..5).collect();
    3779    /// deque.push_front(9);
    3780    /// deque.push_front(8);
    3781    /// let ptr = deque.as_slices().1.as_ptr();
    3782    /// let vec = Vec::from(deque);
    3783    /// assert_eq!(vec, [8, 9, 1, 2, 3, 4]);
    3784    /// assert_eq!(vec.as_ptr(), ptr);
    3785    /// ```
    3786    fn from(mut other: VecDeque<T, A>) -> Self {
    3787        other.make_contiguous();
    3788
    3789        unsafe {
    3790            let other = ManuallyDrop::new(other);
    3791            let buf = other.buf.ptr();
    3792            let len = other.len();
    3793            let cap = other.capacity();
    3794            let alloc = ptr::read(other.allocator());
    3795
    3796            if other.head != 0 {
    3797                ptr::copy(buf.add(other.head), buf, len);
    3798            }
    3799            Vec::from_raw_parts_in(buf, len, cap, alloc)
    3800        }
    3801    }
    3802}
    3803
    3804#[stable(feature = "std_collections_from_array", since = "1.56.0")]
    3805impl<T, const N: usize> From<[T; N]> for VecDeque<T> {
    3806    /// Converts a `[T; N]` into a `VecDeque<T>`.
    3807    ///
    3808    /// ```
    3809    /// use std::collections::VecDeque;
    3810    ///
    3811    /// let deq1 = VecDeque::from([1, 2, 3, 4]);
    3812    /// let deq2: VecDeque<_> = [1, 2, 3, 4].into();
    3813    /// assert_eq!(deq1, deq2);
    3814    /// ```
    3815    fn from(arr: [T; N]) -> Self {
    3816        let mut deq = VecDeque::with_capacity(N);
    3817        let arr = ManuallyDrop::new(arr);
    3818        if !<T>::IS_ZST {
    3819            // SAFETY: VecDeque::with_capacity ensures that there is enough capacity.
    3820            unsafe {
    3821                ptr::copy_nonoverlapping(arr.as_ptr(), deq.ptr(), N);
    3822            }
    3823        }
    3824        deq.head = 0;
    3825        deq.len = N;
    3826        deq
    3827    }
    3828}