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