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: VecDeque = 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(iter: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: &mut [T], back: &mut [T]) = self.as_mut_slices();
140 unsafe {
141 let _back_dropper: Dropper<'_, T> = Dropper(back);
142 // use drop for [T]
143 ptr::drop_in_place(to_drop: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 /// Shortens the deque, keeping the last `len` elements and dropping
1192 /// the rest.
1193 ///
1194 /// If `len` is greater or equal to the deque's current length, this has
1195 /// no effect.
1196 ///
1197 /// # Examples
1198 ///
1199 /// ```
1200 /// # #![feature(vec_deque_truncate_front)]
1201 /// use std::collections::VecDeque;
1202 ///
1203 /// let mut buf = VecDeque::new();
1204 /// buf.push_front(5);
1205 /// buf.push_front(10);
1206 /// buf.push_front(15);
1207 /// assert_eq!(buf, [15, 10, 5]);
1208 /// assert_eq!(buf.as_slices(), (&[15, 10, 5][..], &[][..]));
1209 /// buf.truncate_front(1);
1210 /// assert_eq!(buf.as_slices(), (&[5][..], &[][..]));
1211 /// ```
1212 #[unstable(feature = "vec_deque_truncate_front", issue = "140667")]
1213 pub fn truncate_front(&mut self, len: usize) {
1214 /// Runs the destructor for all items in the slice when it gets dropped (normally or
1215 /// during unwinding).
1216 struct Dropper<'a, T>(&'a mut [T]);
1217
1218 impl<'a, T> Drop for Dropper<'a, T> {
1219 fn drop(&mut self) {
1220 unsafe {
1221 ptr::drop_in_place(self.0);
1222 }
1223 }
1224 }
1225
1226 unsafe {
1227 if len >= self.len {
1228 // No action is taken
1229 return;
1230 }
1231
1232 let (front, back) = self.as_mut_slices();
1233 if len > back.len() {
1234 // The 'back' slice remains unchanged.
1235 // front.len() + back.len() == self.len, so 'end' is non-negative
1236 // and end < front.len()
1237 let end = front.len() - (len - back.len());
1238 let drop_front = front.get_unchecked_mut(..end) as *mut _;
1239 self.head += end;
1240 self.len = len;
1241 ptr::drop_in_place(drop_front);
1242 } else {
1243 let drop_front = front as *mut _;
1244 // 'end' is non-negative by the condition above
1245 let end = back.len() - len;
1246 let drop_back = back.get_unchecked_mut(..end) as *mut _;
1247 self.head = self.to_physical_idx(self.len - len);
1248 self.len = len;
1249
1250 // Make sure the second half is dropped even when a destructor
1251 // in the first one panics.
1252 let _back_dropper = Dropper(&mut *drop_back);
1253 ptr::drop_in_place(drop_front);
1254 }
1255 }
1256 }
1257
1258 /// Returns a reference to the underlying allocator.
1259 #[unstable(feature = "allocator_api", issue = "32838")]
1260 #[inline]
1261 pub fn allocator(&self) -> &A {
1262 self.buf.allocator()
1263 }
1264
1265 /// Returns a front-to-back iterator.
1266 ///
1267 /// # Examples
1268 ///
1269 /// ```
1270 /// use std::collections::VecDeque;
1271 ///
1272 /// let mut buf = VecDeque::new();
1273 /// buf.push_back(5);
1274 /// buf.push_back(3);
1275 /// buf.push_back(4);
1276 /// let b: &[_] = &[&5, &3, &4];
1277 /// let c: Vec<&i32> = buf.iter().collect();
1278 /// assert_eq!(&c[..], b);
1279 /// ```
1280 #[stable(feature = "rust1", since = "1.0.0")]
1281 #[cfg_attr(not(test), rustc_diagnostic_item = "vecdeque_iter")]
1282 pub fn iter(&self) -> Iter<'_, T> {
1283 let (a, b) = self.as_slices();
1284 Iter::new(a.iter(), b.iter())
1285 }
1286
1287 /// Returns a front-to-back iterator that returns mutable references.
1288 ///
1289 /// # Examples
1290 ///
1291 /// ```
1292 /// use std::collections::VecDeque;
1293 ///
1294 /// let mut buf = VecDeque::new();
1295 /// buf.push_back(5);
1296 /// buf.push_back(3);
1297 /// buf.push_back(4);
1298 /// for num in buf.iter_mut() {
1299 /// *num = *num - 2;
1300 /// }
1301 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
1302 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
1303 /// ```
1304 #[stable(feature = "rust1", since = "1.0.0")]
1305 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
1306 let (a, b) = self.as_mut_slices();
1307 IterMut::new(a.iter_mut(), b.iter_mut())
1308 }
1309
1310 /// Returns a pair of slices which contain, in order, the contents of the
1311 /// deque.
1312 ///
1313 /// If [`make_contiguous`] was previously called, all elements of the
1314 /// deque will be in the first slice and the second slice will be empty.
1315 /// Otherwise, the exact split point depends on implementation details
1316 /// and is not guaranteed.
1317 ///
1318 /// [`make_contiguous`]: VecDeque::make_contiguous
1319 ///
1320 /// # Examples
1321 ///
1322 /// ```
1323 /// use std::collections::VecDeque;
1324 ///
1325 /// let mut deque = VecDeque::new();
1326 ///
1327 /// deque.push_back(0);
1328 /// deque.push_back(1);
1329 /// deque.push_back(2);
1330 ///
1331 /// let expected = [0, 1, 2];
1332 /// let (front, back) = deque.as_slices();
1333 /// assert_eq!(&expected[..front.len()], front);
1334 /// assert_eq!(&expected[front.len()..], back);
1335 ///
1336 /// deque.push_front(10);
1337 /// deque.push_front(9);
1338 ///
1339 /// let expected = [9, 10, 0, 1, 2];
1340 /// let (front, back) = deque.as_slices();
1341 /// assert_eq!(&expected[..front.len()], front);
1342 /// assert_eq!(&expected[front.len()..], back);
1343 /// ```
1344 #[inline]
1345 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1346 pub fn as_slices(&self) -> (&[T], &[T]) {
1347 let (a_range, b_range) = self.slice_ranges(.., self.len);
1348 // SAFETY: `slice_ranges` always returns valid ranges into
1349 // the physical buffer.
1350 unsafe { (&*self.buffer_range(a_range), &*self.buffer_range(b_range)) }
1351 }
1352
1353 /// Returns a pair of slices which contain, in order, the contents of the
1354 /// deque.
1355 ///
1356 /// If [`make_contiguous`] was previously called, all elements of the
1357 /// deque will be in the first slice and the second slice will be empty.
1358 /// Otherwise, the exact split point depends on implementation details
1359 /// and is not guaranteed.
1360 ///
1361 /// [`make_contiguous`]: VecDeque::make_contiguous
1362 ///
1363 /// # Examples
1364 ///
1365 /// ```
1366 /// use std::collections::VecDeque;
1367 ///
1368 /// let mut deque = VecDeque::new();
1369 ///
1370 /// deque.push_back(0);
1371 /// deque.push_back(1);
1372 ///
1373 /// deque.push_front(10);
1374 /// deque.push_front(9);
1375 ///
1376 /// // Since the split point is not guaranteed, we may need to update
1377 /// // either slice.
1378 /// let mut update_nth = |index: usize, val: u32| {
1379 /// let (front, back) = deque.as_mut_slices();
1380 /// if index > front.len() - 1 {
1381 /// back[index - front.len()] = val;
1382 /// } else {
1383 /// front[index] = val;
1384 /// }
1385 /// };
1386 ///
1387 /// update_nth(0, 42);
1388 /// update_nth(2, 24);
1389 ///
1390 /// let v: Vec<_> = deque.into();
1391 /// assert_eq!(v, [42, 10, 24, 1]);
1392 /// ```
1393 #[inline]
1394 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1395 pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
1396 let (a_range, b_range) = self.slice_ranges(.., self.len);
1397 // SAFETY: `slice_ranges` always returns valid ranges into
1398 // the physical buffer.
1399 unsafe { (&mut *self.buffer_range(a_range), &mut *self.buffer_range(b_range)) }
1400 }
1401
1402 /// Returns the number of elements in the deque.
1403 ///
1404 /// # Examples
1405 ///
1406 /// ```
1407 /// use std::collections::VecDeque;
1408 ///
1409 /// let mut deque = VecDeque::new();
1410 /// assert_eq!(deque.len(), 0);
1411 /// deque.push_back(1);
1412 /// assert_eq!(deque.len(), 1);
1413 /// ```
1414 #[stable(feature = "rust1", since = "1.0.0")]
1415 #[rustc_confusables("length", "size")]
1416 pub fn len(&self) -> usize {
1417 self.len
1418 }
1419
1420 /// Returns `true` if the deque is empty.
1421 ///
1422 /// # Examples
1423 ///
1424 /// ```
1425 /// use std::collections::VecDeque;
1426 ///
1427 /// let mut deque = VecDeque::new();
1428 /// assert!(deque.is_empty());
1429 /// deque.push_front(1);
1430 /// assert!(!deque.is_empty());
1431 /// ```
1432 #[stable(feature = "rust1", since = "1.0.0")]
1433 pub fn is_empty(&self) -> bool {
1434 self.len == 0
1435 }
1436
1437 /// Given a range into the logical buffer of the deque, this function
1438 /// return two ranges into the physical buffer that correspond to
1439 /// the given range. The `len` parameter should usually just be `self.len`;
1440 /// the reason it's passed explicitly is that if the deque is wrapped in
1441 /// a `Drain`, then `self.len` is not actually the length of the deque.
1442 ///
1443 /// # Safety
1444 ///
1445 /// This function is always safe to call. For the resulting ranges to be valid
1446 /// ranges into the physical buffer, the caller must ensure that the result of
1447 /// calling `slice::range(range, ..len)` represents a valid range into the
1448 /// logical buffer, and that all elements in that range are initialized.
1449 fn slice_ranges<R>(&self, range: R, len: usize) -> (Range<usize>, Range<usize>)
1450 where
1451 R: RangeBounds<usize>,
1452 {
1453 let Range { start, end } = slice::range(range, ..len);
1454 let len = end - start;
1455
1456 if len == 0 {
1457 (0..0, 0..0)
1458 } else {
1459 // `slice::range` guarantees that `start <= end <= len`.
1460 // because `len != 0`, we know that `start < end`, so `start < len`
1461 // and the indexing is valid.
1462 let wrapped_start = self.to_physical_idx(start);
1463
1464 // this subtraction can never overflow because `wrapped_start` is
1465 // at most `self.capacity()` (and if `self.capacity != 0`, then `wrapped_start` is strictly less
1466 // than `self.capacity`).
1467 let head_len = self.capacity() - wrapped_start;
1468
1469 if head_len >= len {
1470 // we know that `len + wrapped_start <= self.capacity <= usize::MAX`, so this addition can't overflow
1471 (wrapped_start..wrapped_start + len, 0..0)
1472 } else {
1473 // can't overflow because of the if condition
1474 let tail_len = len - head_len;
1475 (wrapped_start..self.capacity(), 0..tail_len)
1476 }
1477 }
1478 }
1479
1480 /// Creates an iterator that covers the specified range in the deque.
1481 ///
1482 /// # Panics
1483 ///
1484 /// Panics if the starting point is greater than the end point or if
1485 /// the end point is greater than the length of the deque.
1486 ///
1487 /// # Examples
1488 ///
1489 /// ```
1490 /// use std::collections::VecDeque;
1491 ///
1492 /// let deque: VecDeque<_> = [1, 2, 3].into();
1493 /// let range = deque.range(2..).copied().collect::<VecDeque<_>>();
1494 /// assert_eq!(range, [3]);
1495 ///
1496 /// // A full range covers all contents
1497 /// let all = deque.range(..);
1498 /// assert_eq!(all.len(), 3);
1499 /// ```
1500 #[inline]
1501 #[stable(feature = "deque_range", since = "1.51.0")]
1502 pub fn range<R>(&self, range: R) -> Iter<'_, T>
1503 where
1504 R: RangeBounds<usize>,
1505 {
1506 let (a_range, b_range) = self.slice_ranges(range, self.len);
1507 // SAFETY: The ranges returned by `slice_ranges`
1508 // are valid ranges into the physical buffer, so
1509 // it's ok to pass them to `buffer_range` and
1510 // dereference the result.
1511 let a = unsafe { &*self.buffer_range(a_range) };
1512 let b = unsafe { &*self.buffer_range(b_range) };
1513 Iter::new(a.iter(), b.iter())
1514 }
1515
1516 /// Creates an iterator that covers the specified mutable range in the deque.
1517 ///
1518 /// # Panics
1519 ///
1520 /// Panics if the starting point is greater than the end point or if
1521 /// the end point is greater than the length of the deque.
1522 ///
1523 /// # Examples
1524 ///
1525 /// ```
1526 /// use std::collections::VecDeque;
1527 ///
1528 /// let mut deque: VecDeque<_> = [1, 2, 3].into();
1529 /// for v in deque.range_mut(2..) {
1530 /// *v *= 2;
1531 /// }
1532 /// assert_eq!(deque, [1, 2, 6]);
1533 ///
1534 /// // A full range covers all contents
1535 /// for v in deque.range_mut(..) {
1536 /// *v *= 2;
1537 /// }
1538 /// assert_eq!(deque, [2, 4, 12]);
1539 /// ```
1540 #[inline]
1541 #[stable(feature = "deque_range", since = "1.51.0")]
1542 pub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T>
1543 where
1544 R: RangeBounds<usize>,
1545 {
1546 let (a_range, b_range) = self.slice_ranges(range, self.len);
1547 // SAFETY: The ranges returned by `slice_ranges`
1548 // are valid ranges into the physical buffer, so
1549 // it's ok to pass them to `buffer_range` and
1550 // dereference the result.
1551 let a = unsafe { &mut *self.buffer_range(a_range) };
1552 let b = unsafe { &mut *self.buffer_range(b_range) };
1553 IterMut::new(a.iter_mut(), b.iter_mut())
1554 }
1555
1556 /// Removes the specified range from the deque in bulk, returning all
1557 /// removed elements as an iterator. If the iterator is dropped before
1558 /// being fully consumed, it drops the remaining removed elements.
1559 ///
1560 /// The returned iterator keeps a mutable borrow on the queue to optimize
1561 /// its implementation.
1562 ///
1563 ///
1564 /// # Panics
1565 ///
1566 /// Panics if the starting point is greater than the end point or if
1567 /// the end point is greater than the length of the deque.
1568 ///
1569 /// # Leaking
1570 ///
1571 /// If the returned iterator goes out of scope without being dropped (due to
1572 /// [`mem::forget`], for example), the deque may have lost and leaked
1573 /// elements arbitrarily, including elements outside the range.
1574 ///
1575 /// # Examples
1576 ///
1577 /// ```
1578 /// use std::collections::VecDeque;
1579 ///
1580 /// let mut deque: VecDeque<_> = [1, 2, 3].into();
1581 /// let drained = deque.drain(2..).collect::<VecDeque<_>>();
1582 /// assert_eq!(drained, [3]);
1583 /// assert_eq!(deque, [1, 2]);
1584 ///
1585 /// // A full range clears all contents, like `clear()` does
1586 /// deque.drain(..);
1587 /// assert!(deque.is_empty());
1588 /// ```
1589 #[inline]
1590 #[stable(feature = "drain", since = "1.6.0")]
1591 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
1592 where
1593 R: RangeBounds<usize>,
1594 {
1595 // Memory safety
1596 //
1597 // When the Drain is first created, the source deque is shortened to
1598 // make sure no uninitialized or moved-from elements are accessible at
1599 // all if the Drain's destructor never gets to run.
1600 //
1601 // Drain will ptr::read out the values to remove.
1602 // When finished, the remaining data will be copied back to cover the hole,
1603 // and the head/tail values will be restored correctly.
1604 //
1605 let Range { start, end } = slice::range(range, ..self.len);
1606 let drain_start = start;
1607 let drain_len = end - start;
1608
1609 // The deque's elements are parted into three segments:
1610 // * 0 -> drain_start
1611 // * drain_start -> drain_start+drain_len
1612 // * drain_start+drain_len -> self.len
1613 //
1614 // H = self.head; T = self.head+self.len; t = drain_start+drain_len; h = drain_head
1615 //
1616 // We store drain_start as self.len, and drain_len and self.len as
1617 // drain_len and orig_len respectively on the Drain. This also
1618 // truncates the effective array such that if the Drain is leaked, we
1619 // have forgotten about the potentially moved values after the start of
1620 // the drain.
1621 //
1622 // H h t T
1623 // [. . . o o x x o o . . .]
1624 //
1625 // "forget" about the values after the start of the drain until after
1626 // the drain is complete and the Drain destructor is run.
1627
1628 unsafe { Drain::new(self, drain_start, drain_len) }
1629 }
1630
1631 /// Clears the deque, removing all values.
1632 ///
1633 /// # Examples
1634 ///
1635 /// ```
1636 /// use std::collections::VecDeque;
1637 ///
1638 /// let mut deque = VecDeque::new();
1639 /// deque.push_back(1);
1640 /// deque.clear();
1641 /// assert!(deque.is_empty());
1642 /// ```
1643 #[stable(feature = "rust1", since = "1.0.0")]
1644 #[inline]
1645 pub fn clear(&mut self) {
1646 self.truncate(0);
1647 // Not strictly necessary, but leaves things in a more consistent/predictable state.
1648 self.head = 0;
1649 }
1650
1651 /// Returns `true` if the deque contains an element equal to the
1652 /// given value.
1653 ///
1654 /// This operation is *O*(*n*).
1655 ///
1656 /// Note that if you have a sorted `VecDeque`, [`binary_search`] may be faster.
1657 ///
1658 /// [`binary_search`]: VecDeque::binary_search
1659 ///
1660 /// # Examples
1661 ///
1662 /// ```
1663 /// use std::collections::VecDeque;
1664 ///
1665 /// let mut deque: VecDeque<u32> = VecDeque::new();
1666 ///
1667 /// deque.push_back(0);
1668 /// deque.push_back(1);
1669 ///
1670 /// assert_eq!(deque.contains(&1), true);
1671 /// assert_eq!(deque.contains(&10), false);
1672 /// ```
1673 #[stable(feature = "vec_deque_contains", since = "1.12.0")]
1674 pub fn contains(&self, x: &T) -> bool
1675 where
1676 T: PartialEq<T>,
1677 {
1678 let (a, b) = self.as_slices();
1679 a.contains(x) || b.contains(x)
1680 }
1681
1682 /// Provides a reference to the front element, 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 /// assert_eq!(d.front(), None);
1692 ///
1693 /// d.push_back(1);
1694 /// d.push_back(2);
1695 /// assert_eq!(d.front(), Some(&1));
1696 /// ```
1697 #[stable(feature = "rust1", since = "1.0.0")]
1698 #[rustc_confusables("first")]
1699 pub fn front(&self) -> Option<&T> {
1700 self.get(0)
1701 }
1702
1703 /// Provides a mutable reference to the front element, or `None` if the
1704 /// deque is empty.
1705 ///
1706 /// # Examples
1707 ///
1708 /// ```
1709 /// use std::collections::VecDeque;
1710 ///
1711 /// let mut d = VecDeque::new();
1712 /// assert_eq!(d.front_mut(), None);
1713 ///
1714 /// d.push_back(1);
1715 /// d.push_back(2);
1716 /// match d.front_mut() {
1717 /// Some(x) => *x = 9,
1718 /// None => (),
1719 /// }
1720 /// assert_eq!(d.front(), Some(&9));
1721 /// ```
1722 #[stable(feature = "rust1", since = "1.0.0")]
1723 pub fn front_mut(&mut self) -> Option<&mut T> {
1724 self.get_mut(0)
1725 }
1726
1727 /// Provides a reference to the back element, or `None` if the deque is
1728 /// empty.
1729 ///
1730 /// # Examples
1731 ///
1732 /// ```
1733 /// use std::collections::VecDeque;
1734 ///
1735 /// let mut d = VecDeque::new();
1736 /// assert_eq!(d.back(), None);
1737 ///
1738 /// d.push_back(1);
1739 /// d.push_back(2);
1740 /// assert_eq!(d.back(), Some(&2));
1741 /// ```
1742 #[stable(feature = "rust1", since = "1.0.0")]
1743 #[rustc_confusables("last")]
1744 pub fn back(&self) -> Option<&T> {
1745 self.get(self.len.wrapping_sub(1))
1746 }
1747
1748 /// Provides a mutable reference to the back element, or `None` if the
1749 /// deque is empty.
1750 ///
1751 /// # Examples
1752 ///
1753 /// ```
1754 /// use std::collections::VecDeque;
1755 ///
1756 /// let mut d = VecDeque::new();
1757 /// assert_eq!(d.back(), None);
1758 ///
1759 /// d.push_back(1);
1760 /// d.push_back(2);
1761 /// match d.back_mut() {
1762 /// Some(x) => *x = 9,
1763 /// None => (),
1764 /// }
1765 /// assert_eq!(d.back(), Some(&9));
1766 /// ```
1767 #[stable(feature = "rust1", since = "1.0.0")]
1768 pub fn back_mut(&mut self) -> Option<&mut T> {
1769 self.get_mut(self.len.wrapping_sub(1))
1770 }
1771
1772 /// Removes the first element and returns it, or `None` if the deque is
1773 /// empty.
1774 ///
1775 /// # Examples
1776 ///
1777 /// ```
1778 /// use std::collections::VecDeque;
1779 ///
1780 /// let mut d = VecDeque::new();
1781 /// d.push_back(1);
1782 /// d.push_back(2);
1783 ///
1784 /// assert_eq!(d.pop_front(), Some(1));
1785 /// assert_eq!(d.pop_front(), Some(2));
1786 /// assert_eq!(d.pop_front(), None);
1787 /// ```
1788 #[stable(feature = "rust1", since = "1.0.0")]
1789 pub fn pop_front(&mut self) -> Option<T> {
1790 if self.is_empty() {
1791 None
1792 } else {
1793 let old_head = self.head;
1794 self.head = self.to_physical_idx(1);
1795 self.len -= 1;
1796 unsafe {
1797 core::hint::assert_unchecked(self.len < self.capacity());
1798 Some(self.buffer_read(old_head))
1799 }
1800 }
1801 }
1802
1803 /// Removes the last element from the deque and returns it, or `None` if
1804 /// it is empty.
1805 ///
1806 /// # Examples
1807 ///
1808 /// ```
1809 /// use std::collections::VecDeque;
1810 ///
1811 /// let mut buf = VecDeque::new();
1812 /// assert_eq!(buf.pop_back(), None);
1813 /// buf.push_back(1);
1814 /// buf.push_back(3);
1815 /// assert_eq!(buf.pop_back(), Some(3));
1816 /// ```
1817 #[stable(feature = "rust1", since = "1.0.0")]
1818 pub fn pop_back(&mut self) -> Option<T> {
1819 if self.is_empty() {
1820 None
1821 } else {
1822 self.len -= 1;
1823 unsafe {
1824 core::hint::assert_unchecked(self.len < self.capacity());
1825 Some(self.buffer_read(self.to_physical_idx(self.len)))
1826 }
1827 }
1828 }
1829
1830 /// Removes and returns the first element from the deque if the predicate
1831 /// returns `true`, or [`None`] if the predicate returns false or the deque
1832 /// is empty (the predicate will not be called in that case).
1833 ///
1834 /// # Examples
1835 ///
1836 /// ```
1837 /// #![feature(vec_deque_pop_if)]
1838 /// use std::collections::VecDeque;
1839 ///
1840 /// let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
1841 /// let pred = |x: &mut i32| *x % 2 == 0;
1842 ///
1843 /// assert_eq!(deque.pop_front_if(pred), Some(0));
1844 /// assert_eq!(deque, [1, 2, 3, 4]);
1845 /// assert_eq!(deque.pop_front_if(pred), None);
1846 /// ```
1847 #[unstable(feature = "vec_deque_pop_if", issue = "135889")]
1848 pub fn pop_front_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
1849 let first = self.front_mut()?;
1850 if predicate(first) { self.pop_front() } else { None }
1851 }
1852
1853 /// Removes and returns the last element from the deque if the predicate
1854 /// returns `true`, or [`None`] if the predicate returns false or the deque
1855 /// is empty (the predicate will not be called in that case).
1856 ///
1857 /// # Examples
1858 ///
1859 /// ```
1860 /// #![feature(vec_deque_pop_if)]
1861 /// use std::collections::VecDeque;
1862 ///
1863 /// let mut deque: VecDeque<i32> = vec![0, 1, 2, 3, 4].into();
1864 /// let pred = |x: &mut i32| *x % 2 == 0;
1865 ///
1866 /// assert_eq!(deque.pop_back_if(pred), Some(4));
1867 /// assert_eq!(deque, [0, 1, 2, 3]);
1868 /// assert_eq!(deque.pop_back_if(pred), None);
1869 /// ```
1870 #[unstable(feature = "vec_deque_pop_if", issue = "135889")]
1871 pub fn pop_back_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
1872 let first = self.back_mut()?;
1873 if predicate(first) { self.pop_back() } else { None }
1874 }
1875
1876 /// Prepends an element to the deque.
1877 ///
1878 /// # Examples
1879 ///
1880 /// ```
1881 /// use std::collections::VecDeque;
1882 ///
1883 /// let mut d = VecDeque::new();
1884 /// d.push_front(1);
1885 /// d.push_front(2);
1886 /// assert_eq!(d.front(), Some(&2));
1887 /// ```
1888 #[stable(feature = "rust1", since = "1.0.0")]
1889 #[track_caller]
1890 pub fn push_front(&mut self, value: T) {
1891 if self.is_full() {
1892 self.grow();
1893 }
1894
1895 self.head = self.wrap_sub(self.head, 1);
1896 self.len += 1;
1897
1898 unsafe {
1899 self.buffer_write(self.head, value);
1900 }
1901 }
1902
1903 /// Appends an element to the back of the deque.
1904 ///
1905 /// # Examples
1906 ///
1907 /// ```
1908 /// use std::collections::VecDeque;
1909 ///
1910 /// let mut buf = VecDeque::new();
1911 /// buf.push_back(1);
1912 /// buf.push_back(3);
1913 /// assert_eq!(3, *buf.back().unwrap());
1914 /// ```
1915 #[stable(feature = "rust1", since = "1.0.0")]
1916 #[rustc_confusables("push", "put", "append")]
1917 #[track_caller]
1918 pub fn push_back(&mut self, value: T) {
1919 if self.is_full() {
1920 self.grow();
1921 }
1922
1923 unsafe { self.buffer_write(self.to_physical_idx(self.len), value) }
1924 self.len += 1;
1925 }
1926
1927 #[inline]
1928 fn is_contiguous(&self) -> bool {
1929 // Do the calculation like this to avoid overflowing if len + head > usize::MAX
1930 self.head <= self.capacity() - self.len
1931 }
1932
1933 /// Removes an element from anywhere in the deque and returns it,
1934 /// replacing it with the first element.
1935 ///
1936 /// This does not preserve ordering, but is *O*(1).
1937 ///
1938 /// Returns `None` if `index` is out of bounds.
1939 ///
1940 /// Element at index 0 is the front of the queue.
1941 ///
1942 /// # Examples
1943 ///
1944 /// ```
1945 /// use std::collections::VecDeque;
1946 ///
1947 /// let mut buf = VecDeque::new();
1948 /// assert_eq!(buf.swap_remove_front(0), None);
1949 /// buf.push_back(1);
1950 /// buf.push_back(2);
1951 /// buf.push_back(3);
1952 /// assert_eq!(buf, [1, 2, 3]);
1953 ///
1954 /// assert_eq!(buf.swap_remove_front(2), Some(3));
1955 /// assert_eq!(buf, [2, 1]);
1956 /// ```
1957 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1958 pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
1959 let length = self.len;
1960 if index < length && index != 0 {
1961 self.swap(index, 0);
1962 } else if index >= length {
1963 return None;
1964 }
1965 self.pop_front()
1966 }
1967
1968 /// Removes an element from anywhere in the deque and returns it,
1969 /// replacing it with the last element.
1970 ///
1971 /// This does not preserve ordering, but is *O*(1).
1972 ///
1973 /// Returns `None` if `index` is out of bounds.
1974 ///
1975 /// Element at index 0 is the front of the queue.
1976 ///
1977 /// # Examples
1978 ///
1979 /// ```
1980 /// use std::collections::VecDeque;
1981 ///
1982 /// let mut buf = VecDeque::new();
1983 /// assert_eq!(buf.swap_remove_back(0), None);
1984 /// buf.push_back(1);
1985 /// buf.push_back(2);
1986 /// buf.push_back(3);
1987 /// assert_eq!(buf, [1, 2, 3]);
1988 ///
1989 /// assert_eq!(buf.swap_remove_back(0), Some(1));
1990 /// assert_eq!(buf, [3, 2]);
1991 /// ```
1992 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1993 pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
1994 let length = self.len;
1995 if length > 0 && index < length - 1 {
1996 self.swap(index, length - 1);
1997 } else if index >= length {
1998 return None;
1999 }
2000 self.pop_back()
2001 }
2002
2003 /// Inserts an element at `index` within the deque, shifting all elements
2004 /// with indices greater than or equal to `index` towards the back.
2005 ///
2006 /// Element at index 0 is the front of the queue.
2007 ///
2008 /// # Panics
2009 ///
2010 /// Panics if `index` is strictly greater than deque's length
2011 ///
2012 /// # Examples
2013 ///
2014 /// ```
2015 /// use std::collections::VecDeque;
2016 ///
2017 /// let mut vec_deque = VecDeque::new();
2018 /// vec_deque.push_back('a');
2019 /// vec_deque.push_back('b');
2020 /// vec_deque.push_back('c');
2021 /// assert_eq!(vec_deque, &['a', 'b', 'c']);
2022 ///
2023 /// vec_deque.insert(1, 'd');
2024 /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
2025 ///
2026 /// vec_deque.insert(4, 'e');
2027 /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c', 'e']);
2028 /// ```
2029 #[stable(feature = "deque_extras_15", since = "1.5.0")]
2030 #[track_caller]
2031 pub fn insert(&mut self, index: usize, value: T) {
2032 assert!(index <= self.len(), "index out of bounds");
2033 if self.is_full() {
2034 self.grow();
2035 }
2036
2037 let k = self.len - index;
2038 if k < index {
2039 // `index + 1` can't overflow, because if index was usize::MAX, then either the
2040 // assert would've failed, or the deque would've tried to grow past usize::MAX
2041 // and panicked.
2042 unsafe {
2043 // see `remove()` for explanation why this wrap_copy() call is safe.
2044 self.wrap_copy(self.to_physical_idx(index), self.to_physical_idx(index + 1), k);
2045 self.buffer_write(self.to_physical_idx(index), value);
2046 self.len += 1;
2047 }
2048 } else {
2049 let old_head = self.head;
2050 self.head = self.wrap_sub(self.head, 1);
2051 unsafe {
2052 self.wrap_copy(old_head, self.head, index);
2053 self.buffer_write(self.to_physical_idx(index), value);
2054 self.len += 1;
2055 }
2056 }
2057 }
2058
2059 /// Removes and returns the element at `index` from the deque.
2060 /// Whichever end is closer to the removal point will be moved to make
2061 /// room, and all the affected elements will be moved to new positions.
2062 /// Returns `None` if `index` is out of bounds.
2063 ///
2064 /// Element at index 0 is the front of the queue.
2065 ///
2066 /// # Examples
2067 ///
2068 /// ```
2069 /// use std::collections::VecDeque;
2070 ///
2071 /// let mut buf = VecDeque::new();
2072 /// buf.push_back('a');
2073 /// buf.push_back('b');
2074 /// buf.push_back('c');
2075 /// assert_eq!(buf, ['a', 'b', 'c']);
2076 ///
2077 /// assert_eq!(buf.remove(1), Some('b'));
2078 /// assert_eq!(buf, ['a', 'c']);
2079 /// ```
2080 #[stable(feature = "rust1", since = "1.0.0")]
2081 #[rustc_confusables("delete", "take")]
2082 pub fn remove(&mut self, index: usize) -> Option<T> {
2083 if self.len <= index {
2084 return None;
2085 }
2086
2087 let wrapped_idx = self.to_physical_idx(index);
2088
2089 let elem = unsafe { Some(self.buffer_read(wrapped_idx)) };
2090
2091 let k = self.len - index - 1;
2092 // safety: due to the nature of the if-condition, whichever wrap_copy gets called,
2093 // its length argument will be at most `self.len / 2`, so there can't be more than
2094 // one overlapping area.
2095 if k < index {
2096 unsafe { self.wrap_copy(self.wrap_add(wrapped_idx, 1), wrapped_idx, k) };
2097 self.len -= 1;
2098 } else {
2099 let old_head = self.head;
2100 self.head = self.to_physical_idx(1);
2101 unsafe { self.wrap_copy(old_head, self.head, index) };
2102 self.len -= 1;
2103 }
2104
2105 elem
2106 }
2107
2108 /// Splits the deque into two at the given index.
2109 ///
2110 /// Returns a newly allocated `VecDeque`. `self` contains elements `[0, at)`,
2111 /// and the returned deque contains elements `[at, len)`.
2112 ///
2113 /// Note that the capacity of `self` does not change.
2114 ///
2115 /// Element at index 0 is the front of the queue.
2116 ///
2117 /// # Panics
2118 ///
2119 /// Panics if `at > len`.
2120 ///
2121 /// # Examples
2122 ///
2123 /// ```
2124 /// use std::collections::VecDeque;
2125 ///
2126 /// let mut buf: VecDeque<_> = ['a', 'b', 'c'].into();
2127 /// let buf2 = buf.split_off(1);
2128 /// assert_eq!(buf, ['a']);
2129 /// assert_eq!(buf2, ['b', 'c']);
2130 /// ```
2131 #[inline]
2132 #[must_use = "use `.truncate()` if you don't need the other half"]
2133 #[stable(feature = "split_off", since = "1.4.0")]
2134 #[track_caller]
2135 pub fn split_off(&mut self, at: usize) -> Self
2136 where
2137 A: Clone,
2138 {
2139 let len = self.len;
2140 assert!(at <= len, "`at` out of bounds");
2141
2142 let other_len = len - at;
2143 let mut other = VecDeque::with_capacity_in(other_len, self.allocator().clone());
2144
2145 unsafe {
2146 let (first_half, second_half) = self.as_slices();
2147
2148 let first_len = first_half.len();
2149 let second_len = second_half.len();
2150 if at < first_len {
2151 // `at` lies in the first half.
2152 let amount_in_first = first_len - at;
2153
2154 ptr::copy_nonoverlapping(first_half.as_ptr().add(at), other.ptr(), amount_in_first);
2155
2156 // just take all of the second half.
2157 ptr::copy_nonoverlapping(
2158 second_half.as_ptr(),
2159 other.ptr().add(amount_in_first),
2160 second_len,
2161 );
2162 } else {
2163 // `at` lies in the second half, need to factor in the elements we skipped
2164 // in the first half.
2165 let offset = at - first_len;
2166 let amount_in_second = second_len - offset;
2167 ptr::copy_nonoverlapping(
2168 second_half.as_ptr().add(offset),
2169 other.ptr(),
2170 amount_in_second,
2171 );
2172 }
2173 }
2174
2175 // Cleanup where the ends of the buffers are
2176 self.len = at;
2177 other.len = other_len;
2178
2179 other
2180 }
2181
2182 /// Moves all the elements of `other` into `self`, leaving `other` empty.
2183 ///
2184 /// # Panics
2185 ///
2186 /// Panics if the new number of elements in self overflows a `usize`.
2187 ///
2188 /// # Examples
2189 ///
2190 /// ```
2191 /// use std::collections::VecDeque;
2192 ///
2193 /// let mut buf: VecDeque<_> = [1, 2].into();
2194 /// let mut buf2: VecDeque<_> = [3, 4].into();
2195 /// buf.append(&mut buf2);
2196 /// assert_eq!(buf, [1, 2, 3, 4]);
2197 /// assert_eq!(buf2, []);
2198 /// ```
2199 #[inline]
2200 #[stable(feature = "append", since = "1.4.0")]
2201 #[track_caller]
2202 pub fn append(&mut self, other: &mut Self) {
2203 if T::IS_ZST {
2204 self.len = self.len.checked_add(other.len).expect("capacity overflow");
2205 other.len = 0;
2206 other.head = 0;
2207 return;
2208 }
2209
2210 self.reserve(other.len);
2211 unsafe {
2212 let (left, right) = other.as_slices();
2213 self.copy_slice(self.to_physical_idx(self.len), left);
2214 // no overflow, because self.capacity() >= old_cap + left.len() >= self.len + left.len()
2215 self.copy_slice(self.to_physical_idx(self.len + left.len()), right);
2216 }
2217 // SAFETY: Update pointers after copying to avoid leaving doppelganger
2218 // in case of panics.
2219 self.len += other.len;
2220 // Now that we own its values, forget everything in `other`.
2221 other.len = 0;
2222 other.head = 0;
2223 }
2224
2225 /// Retains only the elements specified by the predicate.
2226 ///
2227 /// In other words, remove all elements `e` for which `f(&e)` returns false.
2228 /// This method operates in place, visiting each element exactly once in the
2229 /// original order, and preserves the order of the retained elements.
2230 ///
2231 /// # Examples
2232 ///
2233 /// ```
2234 /// use std::collections::VecDeque;
2235 ///
2236 /// let mut buf = VecDeque::new();
2237 /// buf.extend(1..5);
2238 /// buf.retain(|&x| x % 2 == 0);
2239 /// assert_eq!(buf, [2, 4]);
2240 /// ```
2241 ///
2242 /// Because the elements are visited exactly once in the original order,
2243 /// external state may be used to decide which elements to keep.
2244 ///
2245 /// ```
2246 /// use std::collections::VecDeque;
2247 ///
2248 /// let mut buf = VecDeque::new();
2249 /// buf.extend(1..6);
2250 ///
2251 /// let keep = [false, true, true, false, true];
2252 /// let mut iter = keep.iter();
2253 /// buf.retain(|_| *iter.next().unwrap());
2254 /// assert_eq!(buf, [2, 3, 5]);
2255 /// ```
2256 #[stable(feature = "vec_deque_retain", since = "1.4.0")]
2257 pub fn retain<F>(&mut self, mut f: F)
2258 where
2259 F: FnMut(&T) -> bool,
2260 {
2261 self.retain_mut(|elem| f(elem));
2262 }
2263
2264 /// Retains only the elements specified by the predicate.
2265 ///
2266 /// In other words, remove all elements `e` for which `f(&mut e)` returns false.
2267 /// This method operates in place, visiting each element exactly once in the
2268 /// original order, and preserves the order of the retained elements.
2269 ///
2270 /// # Examples
2271 ///
2272 /// ```
2273 /// use std::collections::VecDeque;
2274 ///
2275 /// let mut buf = VecDeque::new();
2276 /// buf.extend(1..5);
2277 /// buf.retain_mut(|x| if *x % 2 == 0 {
2278 /// *x += 1;
2279 /// true
2280 /// } else {
2281 /// false
2282 /// });
2283 /// assert_eq!(buf, [3, 5]);
2284 /// ```
2285 #[stable(feature = "vec_retain_mut", since = "1.61.0")]
2286 pub fn retain_mut<F>(&mut self, mut f: F)
2287 where
2288 F: FnMut(&mut T) -> bool,
2289 {
2290 let len = self.len;
2291 let mut idx = 0;
2292 let mut cur = 0;
2293
2294 // Stage 1: All values are retained.
2295 while cur < len {
2296 if !f(&mut self[cur]) {
2297 cur += 1;
2298 break;
2299 }
2300 cur += 1;
2301 idx += 1;
2302 }
2303 // Stage 2: Swap retained value into current idx.
2304 while cur < len {
2305 if !f(&mut self[cur]) {
2306 cur += 1;
2307 continue;
2308 }
2309
2310 self.swap(idx, cur);
2311 cur += 1;
2312 idx += 1;
2313 }
2314 // Stage 3: Truncate all values after idx.
2315 if cur != idx {
2316 self.truncate(idx);
2317 }
2318 }
2319
2320 // Double the buffer size. This method is inline(never), so we expect it to only
2321 // be called in cold paths.
2322 // This may panic or abort
2323 #[inline(never)]
2324 #[track_caller]
2325 fn grow(&mut self) {
2326 // Extend or possibly remove this assertion when valid use-cases for growing the
2327 // buffer without it being full emerge
2328 debug_assert!(self.is_full());
2329 let old_cap = self.capacity();
2330 self.buf.grow_one();
2331 unsafe {
2332 self.handle_capacity_increase(old_cap);
2333 }
2334 debug_assert!(!self.is_full());
2335 }
2336
2337 /// Modifies the deque in-place so that `len()` is equal to `new_len`,
2338 /// either by removing excess elements from the back or by appending
2339 /// elements generated by calling `generator` to the back.
2340 ///
2341 /// # Examples
2342 ///
2343 /// ```
2344 /// use std::collections::VecDeque;
2345 ///
2346 /// let mut buf = VecDeque::new();
2347 /// buf.push_back(5);
2348 /// buf.push_back(10);
2349 /// buf.push_back(15);
2350 /// assert_eq!(buf, [5, 10, 15]);
2351 ///
2352 /// buf.resize_with(5, Default::default);
2353 /// assert_eq!(buf, [5, 10, 15, 0, 0]);
2354 ///
2355 /// buf.resize_with(2, || unreachable!());
2356 /// assert_eq!(buf, [5, 10]);
2357 ///
2358 /// let mut state = 100;
2359 /// buf.resize_with(5, || { state += 1; state });
2360 /// assert_eq!(buf, [5, 10, 101, 102, 103]);
2361 /// ```
2362 #[stable(feature = "vec_resize_with", since = "1.33.0")]
2363 #[track_caller]
2364 pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) {
2365 let len = self.len;
2366
2367 if new_len > len {
2368 self.extend(repeat_with(generator).take(new_len - len))
2369 } else {
2370 self.truncate(new_len);
2371 }
2372 }
2373
2374 /// Rearranges the internal storage of this deque so it is one contiguous
2375 /// slice, which is then returned.
2376 ///
2377 /// This method does not allocate and does not change the order of the
2378 /// inserted elements. As it returns a mutable slice, this can be used to
2379 /// sort a deque.
2380 ///
2381 /// Once the internal storage is contiguous, the [`as_slices`] and
2382 /// [`as_mut_slices`] methods will return the entire contents of the
2383 /// deque in a single slice.
2384 ///
2385 /// [`as_slices`]: VecDeque::as_slices
2386 /// [`as_mut_slices`]: VecDeque::as_mut_slices
2387 ///
2388 /// # Examples
2389 ///
2390 /// Sorting the content of a deque.
2391 ///
2392 /// ```
2393 /// use std::collections::VecDeque;
2394 ///
2395 /// let mut buf = VecDeque::with_capacity(15);
2396 ///
2397 /// buf.push_back(2);
2398 /// buf.push_back(1);
2399 /// buf.push_front(3);
2400 ///
2401 /// // sorting the deque
2402 /// buf.make_contiguous().sort();
2403 /// assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));
2404 ///
2405 /// // sorting it in reverse order
2406 /// buf.make_contiguous().sort_by(|a, b| b.cmp(a));
2407 /// assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));
2408 /// ```
2409 ///
2410 /// Getting immutable access to the contiguous slice.
2411 ///
2412 /// ```rust
2413 /// use std::collections::VecDeque;
2414 ///
2415 /// let mut buf = VecDeque::new();
2416 ///
2417 /// buf.push_back(2);
2418 /// buf.push_back(1);
2419 /// buf.push_front(3);
2420 ///
2421 /// buf.make_contiguous();
2422 /// if let (slice, &[]) = buf.as_slices() {
2423 /// // we can now be sure that `slice` contains all elements of the deque,
2424 /// // while still having immutable access to `buf`.
2425 /// assert_eq!(buf.len(), slice.len());
2426 /// assert_eq!(slice, &[3, 2, 1] as &[_]);
2427 /// }
2428 /// ```
2429 #[stable(feature = "deque_make_contiguous", since = "1.48.0")]
2430 pub fn make_contiguous(&mut self) -> &mut [T] {
2431 if T::IS_ZST {
2432 self.head = 0;
2433 }
2434
2435 if self.is_contiguous() {
2436 unsafe { return slice::from_raw_parts_mut(self.ptr().add(self.head), self.len) }
2437 }
2438
2439 let &mut Self { head, len, .. } = self;
2440 let ptr = self.ptr();
2441 let cap = self.capacity();
2442
2443 let free = cap - len;
2444 let head_len = cap - head;
2445 let tail = len - head_len;
2446 let tail_len = tail;
2447
2448 if free >= head_len {
2449 // there is enough free space to copy the head in one go,
2450 // this means that we first shift the tail backwards, and then
2451 // copy the head to the correct position.
2452 //
2453 // from: DEFGH....ABC
2454 // to: ABCDEFGH....
2455 unsafe {
2456 self.copy(0, head_len, tail_len);
2457 // ...DEFGH.ABC
2458 self.copy_nonoverlapping(head, 0, head_len);
2459 // ABCDEFGH....
2460 }
2461
2462 self.head = 0;
2463 } else if free >= tail_len {
2464 // there is enough free space to copy the tail in one go,
2465 // this means that we first shift the head forwards, and then
2466 // copy the tail to the correct position.
2467 //
2468 // from: FGH....ABCDE
2469 // to: ...ABCDEFGH.
2470 unsafe {
2471 self.copy(head, tail, head_len);
2472 // FGHABCDE....
2473 self.copy_nonoverlapping(0, tail + head_len, tail_len);
2474 // ...ABCDEFGH.
2475 }
2476
2477 self.head = tail;
2478 } else {
2479 // `free` is smaller than both `head_len` and `tail_len`.
2480 // the general algorithm for this first moves the slices
2481 // right next to each other and then uses `slice::rotate`
2482 // to rotate them into place:
2483 //
2484 // initially: HIJK..ABCDEFG
2485 // step 1: ..HIJKABCDEFG
2486 // step 2: ..ABCDEFGHIJK
2487 //
2488 // or:
2489 //
2490 // initially: FGHIJK..ABCDE
2491 // step 1: FGHIJKABCDE..
2492 // step 2: ABCDEFGHIJK..
2493
2494 // pick the shorter of the 2 slices to reduce the amount
2495 // of memory that needs to be moved around.
2496 if head_len > tail_len {
2497 // tail is shorter, so:
2498 // 1. copy tail forwards
2499 // 2. rotate used part of the buffer
2500 // 3. update head to point to the new beginning (which is just `free`)
2501
2502 unsafe {
2503 // if there is no free space in the buffer, then the slices are already
2504 // right next to each other and we don't need to move any memory.
2505 if free != 0 {
2506 // because we only move the tail forward as much as there's free space
2507 // behind it, we don't overwrite any elements of the head slice, and
2508 // the slices end up right next to each other.
2509 self.copy(0, free, tail_len);
2510 }
2511
2512 // We just copied the tail right next to the head slice,
2513 // so all of the elements in the range are initialized
2514 let slice = &mut *self.buffer_range(free..self.capacity());
2515
2516 // because the deque wasn't contiguous, we know that `tail_len < self.len == slice.len()`,
2517 // so this will never panic.
2518 slice.rotate_left(tail_len);
2519
2520 // the used part of the buffer now is `free..self.capacity()`, so set
2521 // `head` to the beginning of that range.
2522 self.head = free;
2523 }
2524 } else {
2525 // head is shorter so:
2526 // 1. copy head backwards
2527 // 2. rotate used part of the buffer
2528 // 3. update head to point to the new beginning (which is the beginning of the buffer)
2529
2530 unsafe {
2531 // if there is no free space in the buffer, then the slices are already
2532 // right next to each other and we don't need to move any memory.
2533 if free != 0 {
2534 // copy the head slice to lie right behind the tail slice.
2535 self.copy(self.head, tail_len, head_len);
2536 }
2537
2538 // because we copied the head slice so that both slices lie right
2539 // next to each other, all the elements in the range are initialized.
2540 let slice = &mut *self.buffer_range(0..self.len);
2541
2542 // because the deque wasn't contiguous, we know that `head_len < self.len == slice.len()`
2543 // so this will never panic.
2544 slice.rotate_right(head_len);
2545
2546 // the used part of the buffer now is `0..self.len`, so set
2547 // `head` to the beginning of that range.
2548 self.head = 0;
2549 }
2550 }
2551 }
2552
2553 unsafe { slice::from_raw_parts_mut(ptr.add(self.head), self.len) }
2554 }
2555
2556 /// Rotates the double-ended queue `n` places to the left.
2557 ///
2558 /// Equivalently,
2559 /// - Rotates item `n` into the first position.
2560 /// - Pops the first `n` items and pushes them to the end.
2561 /// - Rotates `len() - n` places to the right.
2562 ///
2563 /// # Panics
2564 ///
2565 /// If `n` is greater than `len()`. Note that `n == len()`
2566 /// does _not_ panic and is a no-op rotation.
2567 ///
2568 /// # Complexity
2569 ///
2570 /// Takes `*O*(min(n, len() - n))` time and no extra space.
2571 ///
2572 /// # Examples
2573 ///
2574 /// ```
2575 /// use std::collections::VecDeque;
2576 ///
2577 /// let mut buf: VecDeque<_> = (0..10).collect();
2578 ///
2579 /// buf.rotate_left(3);
2580 /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);
2581 ///
2582 /// for i in 1..10 {
2583 /// assert_eq!(i * 3 % 10, buf[0]);
2584 /// buf.rotate_left(3);
2585 /// }
2586 /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
2587 /// ```
2588 #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
2589 pub fn rotate_left(&mut self, n: usize) {
2590 assert!(n <= self.len());
2591 let k = self.len - n;
2592 if n <= k {
2593 unsafe { self.rotate_left_inner(n) }
2594 } else {
2595 unsafe { self.rotate_right_inner(k) }
2596 }
2597 }
2598
2599 /// Rotates the double-ended queue `n` places to the right.
2600 ///
2601 /// Equivalently,
2602 /// - Rotates the first item into position `n`.
2603 /// - Pops the last `n` items and pushes them to the front.
2604 /// - Rotates `len() - n` places to the left.
2605 ///
2606 /// # Panics
2607 ///
2608 /// If `n` is greater than `len()`. Note that `n == len()`
2609 /// does _not_ panic and is a no-op rotation.
2610 ///
2611 /// # Complexity
2612 ///
2613 /// Takes `*O*(min(n, len() - n))` time and no extra space.
2614 ///
2615 /// # Examples
2616 ///
2617 /// ```
2618 /// use std::collections::VecDeque;
2619 ///
2620 /// let mut buf: VecDeque<_> = (0..10).collect();
2621 ///
2622 /// buf.rotate_right(3);
2623 /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);
2624 ///
2625 /// for i in 1..10 {
2626 /// assert_eq!(0, buf[i * 3 % 10]);
2627 /// buf.rotate_right(3);
2628 /// }
2629 /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
2630 /// ```
2631 #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
2632 pub fn rotate_right(&mut self, n: usize) {
2633 assert!(n <= self.len());
2634 let k = self.len - n;
2635 if n <= k {
2636 unsafe { self.rotate_right_inner(n) }
2637 } else {
2638 unsafe { self.rotate_left_inner(k) }
2639 }
2640 }
2641
2642 // SAFETY: the following two methods require that the rotation amount
2643 // be less than half the length of the deque.
2644 //
2645 // `wrap_copy` requires that `min(x, capacity() - x) + copy_len <= capacity()`,
2646 // but then `min` is never more than half the capacity, regardless of x,
2647 // so it's sound to call here because we're calling with something
2648 // less than half the length, which is never above half the capacity.
2649
2650 unsafe fn rotate_left_inner(&mut self, mid: usize) {
2651 debug_assert!(mid * 2 <= self.len());
2652 unsafe {
2653 self.wrap_copy(self.head, self.to_physical_idx(self.len), mid);
2654 }
2655 self.head = self.to_physical_idx(mid);
2656 }
2657
2658 unsafe fn rotate_right_inner(&mut self, k: usize) {
2659 debug_assert!(k * 2 <= self.len());
2660 self.head = self.wrap_sub(self.head, k);
2661 unsafe {
2662 self.wrap_copy(self.to_physical_idx(self.len), self.head, k);
2663 }
2664 }
2665
2666 /// Binary searches this `VecDeque` for a given element.
2667 /// If the `VecDeque` is not sorted, the returned result is unspecified and
2668 /// meaningless.
2669 ///
2670 /// If the value is found then [`Result::Ok`] is returned, containing the
2671 /// index of the matching element. If there are multiple matches, then any
2672 /// one of the matches could be returned. If the value is not found then
2673 /// [`Result::Err`] is returned, containing the index where a matching
2674 /// element could be inserted while maintaining sorted order.
2675 ///
2676 /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
2677 ///
2678 /// [`binary_search_by`]: VecDeque::binary_search_by
2679 /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
2680 /// [`partition_point`]: VecDeque::partition_point
2681 ///
2682 /// # Examples
2683 ///
2684 /// Looks up a series of four elements. The first is found, with a
2685 /// uniquely determined position; the second and third are not
2686 /// found; the fourth could match any position in `[1, 4]`.
2687 ///
2688 /// ```
2689 /// use std::collections::VecDeque;
2690 ///
2691 /// let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2692 ///
2693 /// assert_eq!(deque.binary_search(&13), Ok(9));
2694 /// assert_eq!(deque.binary_search(&4), Err(7));
2695 /// assert_eq!(deque.binary_search(&100), Err(13));
2696 /// let r = deque.binary_search(&1);
2697 /// assert!(matches!(r, Ok(1..=4)));
2698 /// ```
2699 ///
2700 /// If you want to insert an item to a sorted deque, while maintaining
2701 /// sort order, consider using [`partition_point`]:
2702 ///
2703 /// ```
2704 /// use std::collections::VecDeque;
2705 ///
2706 /// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2707 /// let num = 42;
2708 /// let idx = deque.partition_point(|&x| x <= num);
2709 /// // If `num` is unique, `s.partition_point(|&x| x < num)` (with `<`) is equivalent to
2710 /// // `s.binary_search(&num).unwrap_or_else(|x| x)`, but using `<=` may allow `insert`
2711 /// // to shift less elements.
2712 /// deque.insert(idx, num);
2713 /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
2714 /// ```
2715 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2716 #[inline]
2717 pub fn binary_search(&self, x: &T) -> Result<usize, usize>
2718 where
2719 T: Ord,
2720 {
2721 self.binary_search_by(|e| e.cmp(x))
2722 }
2723
2724 /// Binary searches this `VecDeque` with a comparator function.
2725 ///
2726 /// The comparator function should return an order code that indicates
2727 /// whether its argument is `Less`, `Equal` or `Greater` the desired
2728 /// target.
2729 /// If the `VecDeque` is not sorted or if the comparator function does not
2730 /// implement an order consistent with the sort order of the underlying
2731 /// `VecDeque`, the returned result is unspecified and meaningless.
2732 ///
2733 /// If the value is found then [`Result::Ok`] is returned, containing the
2734 /// index of the matching element. If there are multiple matches, then any
2735 /// one of the matches could be returned. If the value is not found then
2736 /// [`Result::Err`] is returned, containing the index where a matching
2737 /// element could be inserted while maintaining sorted order.
2738 ///
2739 /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
2740 ///
2741 /// [`binary_search`]: VecDeque::binary_search
2742 /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
2743 /// [`partition_point`]: VecDeque::partition_point
2744 ///
2745 /// # Examples
2746 ///
2747 /// Looks up a series of four elements. The first is found, with a
2748 /// uniquely determined position; the second and third are not
2749 /// found; the fourth could match any position in `[1, 4]`.
2750 ///
2751 /// ```
2752 /// use std::collections::VecDeque;
2753 ///
2754 /// let deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2755 ///
2756 /// assert_eq!(deque.binary_search_by(|x| x.cmp(&13)), Ok(9));
2757 /// assert_eq!(deque.binary_search_by(|x| x.cmp(&4)), Err(7));
2758 /// assert_eq!(deque.binary_search_by(|x| x.cmp(&100)), Err(13));
2759 /// let r = deque.binary_search_by(|x| x.cmp(&1));
2760 /// assert!(matches!(r, Ok(1..=4)));
2761 /// ```
2762 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2763 pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
2764 where
2765 F: FnMut(&'a T) -> Ordering,
2766 {
2767 let (front, back) = self.as_slices();
2768 let cmp_back = back.first().map(|elem| f(elem));
2769
2770 if let Some(Ordering::Equal) = cmp_back {
2771 Ok(front.len())
2772 } else if let Some(Ordering::Less) = cmp_back {
2773 back.binary_search_by(f).map(|idx| idx + front.len()).map_err(|idx| idx + front.len())
2774 } else {
2775 front.binary_search_by(f)
2776 }
2777 }
2778
2779 /// Binary searches this `VecDeque` with a key extraction function.
2780 ///
2781 /// Assumes that the deque is sorted by the key, for instance with
2782 /// [`make_contiguous().sort_by_key()`] using the same key extraction function.
2783 /// If the deque is not sorted by the key, the returned result is
2784 /// unspecified and meaningless.
2785 ///
2786 /// If the value is found then [`Result::Ok`] is returned, containing the
2787 /// index of the matching element. If there are multiple matches, then any
2788 /// one of the matches could be returned. If the value is not found then
2789 /// [`Result::Err`] is returned, containing the index where a matching
2790 /// element could be inserted while maintaining sorted order.
2791 ///
2792 /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
2793 ///
2794 /// [`make_contiguous().sort_by_key()`]: VecDeque::make_contiguous
2795 /// [`binary_search`]: VecDeque::binary_search
2796 /// [`binary_search_by`]: VecDeque::binary_search_by
2797 /// [`partition_point`]: VecDeque::partition_point
2798 ///
2799 /// # Examples
2800 ///
2801 /// Looks up a series of four elements in a slice of pairs sorted by
2802 /// their second elements. The first is found, with a uniquely
2803 /// determined position; the second and third are not found; the
2804 /// fourth could match any position in `[1, 4]`.
2805 ///
2806 /// ```
2807 /// use std::collections::VecDeque;
2808 ///
2809 /// let deque: VecDeque<_> = [(0, 0), (2, 1), (4, 1), (5, 1),
2810 /// (3, 1), (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
2811 /// (1, 21), (2, 34), (4, 55)].into();
2812 ///
2813 /// assert_eq!(deque.binary_search_by_key(&13, |&(a, b)| b), Ok(9));
2814 /// assert_eq!(deque.binary_search_by_key(&4, |&(a, b)| b), Err(7));
2815 /// assert_eq!(deque.binary_search_by_key(&100, |&(a, b)| b), Err(13));
2816 /// let r = deque.binary_search_by_key(&1, |&(a, b)| b);
2817 /// assert!(matches!(r, Ok(1..=4)));
2818 /// ```
2819 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2820 #[inline]
2821 pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
2822 where
2823 F: FnMut(&'a T) -> B,
2824 B: Ord,
2825 {
2826 self.binary_search_by(|k| f(k).cmp(b))
2827 }
2828
2829 /// Returns the index of the partition point according to the given predicate
2830 /// (the index of the first element of the second partition).
2831 ///
2832 /// The deque is assumed to be partitioned according to the given predicate.
2833 /// This means that all elements for which the predicate returns true are at the start of the deque
2834 /// and all elements for which the predicate returns false are at the end.
2835 /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0`
2836 /// (all odd numbers are at the start, all even at the end).
2837 ///
2838 /// If the deque is not partitioned, the returned result is unspecified and meaningless,
2839 /// as this method performs a kind of binary search.
2840 ///
2841 /// See also [`binary_search`], [`binary_search_by`], and [`binary_search_by_key`].
2842 ///
2843 /// [`binary_search`]: VecDeque::binary_search
2844 /// [`binary_search_by`]: VecDeque::binary_search_by
2845 /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
2846 ///
2847 /// # Examples
2848 ///
2849 /// ```
2850 /// use std::collections::VecDeque;
2851 ///
2852 /// let deque: VecDeque<_> = [1, 2, 3, 3, 5, 6, 7].into();
2853 /// let i = deque.partition_point(|&x| x < 5);
2854 ///
2855 /// assert_eq!(i, 4);
2856 /// assert!(deque.iter().take(i).all(|&x| x < 5));
2857 /// assert!(deque.iter().skip(i).all(|&x| !(x < 5)));
2858 /// ```
2859 ///
2860 /// If you want to insert an item to a sorted deque, while maintaining
2861 /// sort order:
2862 ///
2863 /// ```
2864 /// use std::collections::VecDeque;
2865 ///
2866 /// let mut deque: VecDeque<_> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
2867 /// let num = 42;
2868 /// let idx = deque.partition_point(|&x| x < num);
2869 /// deque.insert(idx, num);
2870 /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
2871 /// ```
2872 #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
2873 pub fn partition_point<P>(&self, mut pred: P) -> usize
2874 where
2875 P: FnMut(&T) -> bool,
2876 {
2877 let (front, back) = self.as_slices();
2878
2879 if let Some(true) = back.first().map(|v| pred(v)) {
2880 back.partition_point(pred) + front.len()
2881 } else {
2882 front.partition_point(pred)
2883 }
2884 }
2885}
2886
2887impl<T: Clone, A: Allocator> VecDeque<T, A> {
2888 /// Modifies the deque in-place so that `len()` is equal to new_len,
2889 /// either by removing excess elements from the back or by appending clones of `value`
2890 /// to the back.
2891 ///
2892 /// # Examples
2893 ///
2894 /// ```
2895 /// use std::collections::VecDeque;
2896 ///
2897 /// let mut buf = VecDeque::new();
2898 /// buf.push_back(5);
2899 /// buf.push_back(10);
2900 /// buf.push_back(15);
2901 /// assert_eq!(buf, [5, 10, 15]);
2902 ///
2903 /// buf.resize(2, 0);
2904 /// assert_eq!(buf, [5, 10]);
2905 ///
2906 /// buf.resize(5, 20);
2907 /// assert_eq!(buf, [5, 10, 20, 20, 20]);
2908 /// ```
2909 #[stable(feature = "deque_extras", since = "1.16.0")]
2910 #[track_caller]
2911 pub fn resize(&mut self, new_len: usize, value: T) {
2912 if new_len > self.len() {
2913 let extra = new_len - self.len();
2914 self.extend(repeat_n(value, extra))
2915 } else {
2916 self.truncate(new_len);
2917 }
2918 }
2919}
2920
2921/// Returns the index in the underlying buffer for a given logical element index.
2922#[inline]
2923fn wrap_index(logical_index: usize, capacity: usize) -> usize {
2924 debug_assert!(
2925 (logical_index == 0 && capacity == 0)
2926 || logical_index < capacity
2927 || (logical_index - capacity) < capacity
2928 );
2929 if logical_index >= capacity { logical_index - capacity } else { logical_index }
2930}
2931
2932#[stable(feature = "rust1", since = "1.0.0")]
2933impl<T: PartialEq, A: Allocator> PartialEq for VecDeque<T, A> {
2934 fn eq(&self, other: &Self) -> bool {
2935 if self.len != other.len() {
2936 return false;
2937 }
2938 let (sa, sb) = self.as_slices();
2939 let (oa, ob) = other.as_slices();
2940 if sa.len() == oa.len() {
2941 sa == oa && sb == ob
2942 } else if sa.len() < oa.len() {
2943 // Always divisible in three sections, for example:
2944 // self: [a b c|d e f]
2945 // other: [0 1 2 3|4 5]
2946 // front = 3, mid = 1,
2947 // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
2948 let front = sa.len();
2949 let mid = oa.len() - front;
2950
2951 let (oa_front, oa_mid) = oa.split_at(front);
2952 let (sb_mid, sb_back) = sb.split_at(mid);
2953 debug_assert_eq!(sa.len(), oa_front.len());
2954 debug_assert_eq!(sb_mid.len(), oa_mid.len());
2955 debug_assert_eq!(sb_back.len(), ob.len());
2956 sa == oa_front && sb_mid == oa_mid && sb_back == ob
2957 } else {
2958 let front = oa.len();
2959 let mid = sa.len() - front;
2960
2961 let (sa_front, sa_mid) = sa.split_at(front);
2962 let (ob_mid, ob_back) = ob.split_at(mid);
2963 debug_assert_eq!(sa_front.len(), oa.len());
2964 debug_assert_eq!(sa_mid.len(), ob_mid.len());
2965 debug_assert_eq!(sb.len(), ob_back.len());
2966 sa_front == oa && sa_mid == ob_mid && sb == ob_back
2967 }
2968 }
2969}
2970
2971#[stable(feature = "rust1", since = "1.0.0")]
2972impl<T: Eq, A: Allocator> Eq for VecDeque<T, A> {}
2973
2974__impl_slice_eq1! { [] VecDeque<T, A>, Vec<U, A>, }
2975__impl_slice_eq1! { [] VecDeque<T, A>, &[U], }
2976__impl_slice_eq1! { [] VecDeque<T, A>, &mut [U], }
2977__impl_slice_eq1! { [const N: usize] VecDeque<T, A>, [U; N], }
2978__impl_slice_eq1! { [const N: usize] VecDeque<T, A>, &[U; N], }
2979__impl_slice_eq1! { [const N: usize] VecDeque<T, A>, &mut [U; N], }
2980
2981#[stable(feature = "rust1", since = "1.0.0")]
2982impl<T: PartialOrd, A: Allocator> PartialOrd for VecDeque<T, A> {
2983 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2984 self.iter().partial_cmp(other.iter())
2985 }
2986}
2987
2988#[stable(feature = "rust1", since = "1.0.0")]
2989impl<T: Ord, A: Allocator> Ord for VecDeque<T, A> {
2990 #[inline]
2991 fn cmp(&self, other: &Self) -> Ordering {
2992 self.iter().cmp(other.iter())
2993 }
2994}
2995
2996#[stable(feature = "rust1", since = "1.0.0")]
2997impl<T: Hash, A: Allocator> Hash for VecDeque<T, A> {
2998 fn hash<H: Hasher>(&self, state: &mut H) {
2999 state.write_length_prefix(self.len);
3000 // It's not possible to use Hash::hash_slice on slices
3001 // returned by as_slices method as their length can vary
3002 // in otherwise identical deques.
3003 //
3004 // Hasher only guarantees equivalence for the exact same
3005 // set of calls to its methods.
3006 self.iter().for_each(|elem: &T| elem.hash(state));
3007 }
3008}
3009
3010#[stable(feature = "rust1", since = "1.0.0")]
3011impl<T, A: Allocator> Index<usize> for VecDeque<T, A> {
3012 type Output = T;
3013
3014 #[inline]
3015 fn index(&self, index: usize) -> &T {
3016 self.get(index).expect(msg:"Out of bounds access")
3017 }
3018}
3019
3020#[stable(feature = "rust1", since = "1.0.0")]
3021impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A> {
3022 #[inline]
3023 fn index_mut(&mut self, index: usize) -> &mut T {
3024 self.get_mut(index).expect(msg:"Out of bounds access")
3025 }
3026}
3027
3028#[stable(feature = "rust1", since = "1.0.0")]
3029impl<T> FromIterator<T> for VecDeque<T> {
3030 #[track_caller]
3031 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T> {
3032 SpecFromIter::spec_from_iter(iter.into_iter())
3033 }
3034}
3035
3036#[stable(feature = "rust1", since = "1.0.0")]
3037impl<T, A: Allocator> IntoIterator for VecDeque<T, A> {
3038 type Item = T;
3039 type IntoIter = IntoIter<T, A>;
3040
3041 /// Consumes the deque into a front-to-back iterator yielding elements by
3042 /// value.
3043 fn into_iter(self) -> IntoIter<T, A> {
3044 IntoIter::new(self)
3045 }
3046}
3047
3048#[stable(feature = "rust1", since = "1.0.0")]
3049impl<'a, T, A: Allocator> IntoIterator for &'a VecDeque<T, A> {
3050 type Item = &'a T;
3051 type IntoIter = Iter<'a, T>;
3052
3053 fn into_iter(self) -> Iter<'a, T> {
3054 self.iter()
3055 }
3056}
3057
3058#[stable(feature = "rust1", since = "1.0.0")]
3059impl<'a, T, A: Allocator> IntoIterator for &'a mut VecDeque<T, A> {
3060 type Item = &'a mut T;
3061 type IntoIter = IterMut<'a, T>;
3062
3063 fn into_iter(self) -> IterMut<'a, T> {
3064 self.iter_mut()
3065 }
3066}
3067
3068#[stable(feature = "rust1", since = "1.0.0")]
3069impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
3070 #[track_caller]
3071 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
3072 <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
3073 }
3074
3075 #[inline]
3076 #[track_caller]
3077 fn extend_one(&mut self, elem: T) {
3078 self.push_back(elem);
3079 }
3080
3081 #[inline]
3082 #[track_caller]
3083 fn extend_reserve(&mut self, additional: usize) {
3084 self.reserve(additional);
3085 }
3086
3087 #[inline]
3088 unsafe fn extend_one_unchecked(&mut self, item: T) {
3089 // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
3090 unsafe {
3091 self.push_unchecked(item);
3092 }
3093 }
3094}
3095
3096#[stable(feature = "extend_ref", since = "1.2.0")]
3097impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> {
3098 #[track_caller]
3099 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
3100 self.spec_extend(iter.into_iter());
3101 }
3102
3103 #[inline]
3104 #[track_caller]
3105 fn extend_one(&mut self, &elem: &'a T) {
3106 self.push_back(elem);
3107 }
3108
3109 #[inline]
3110 #[track_caller]
3111 fn extend_reserve(&mut self, additional: usize) {
3112 self.reserve(additional);
3113 }
3114
3115 #[inline]
3116 unsafe fn extend_one_unchecked(&mut self, &item: &'a T) {
3117 // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
3118 unsafe {
3119 self.push_unchecked(item);
3120 }
3121 }
3122}
3123
3124#[stable(feature = "rust1", since = "1.0.0")]
3125impl<T: fmt::Debug, A: Allocator> fmt::Debug for VecDeque<T, A> {
3126 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3127 f.debug_list().entries(self.iter()).finish()
3128 }
3129}
3130
3131#[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
3132impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> {
3133 /// Turn a [`Vec<T>`] into a [`VecDeque<T>`].
3134 ///
3135 /// [`Vec<T>`]: crate::vec::Vec
3136 /// [`VecDeque<T>`]: crate::collections::VecDeque
3137 ///
3138 /// This conversion is guaranteed to run in *O*(1) time
3139 /// and to not re-allocate the `Vec`'s buffer or allocate
3140 /// any additional memory.
3141 #[inline]
3142 fn from(other: Vec<T, A>) -> Self {
3143 let (ptr: *mut T, len: usize, cap: usize, alloc: A) = other.into_raw_parts_with_alloc();
3144 Self { head: 0, len, buf: unsafe { RawVec::from_raw_parts_in(ptr, capacity:cap, alloc) } }
3145 }
3146}
3147
3148#[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
3149impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A> {
3150 /// Turn a [`VecDeque<T>`] into a [`Vec<T>`].
3151 ///
3152 /// [`Vec<T>`]: crate::vec::Vec
3153 /// [`VecDeque<T>`]: crate::collections::VecDeque
3154 ///
3155 /// This never needs to re-allocate, but does need to do *O*(*n*) data movement if
3156 /// the circular buffer doesn't happen to be at the beginning of the allocation.
3157 ///
3158 /// # Examples
3159 ///
3160 /// ```
3161 /// use std::collections::VecDeque;
3162 ///
3163 /// // This one is *O*(1).
3164 /// let deque: VecDeque<_> = (1..5).collect();
3165 /// let ptr = deque.as_slices().0.as_ptr();
3166 /// let vec = Vec::from(deque);
3167 /// assert_eq!(vec, [1, 2, 3, 4]);
3168 /// assert_eq!(vec.as_ptr(), ptr);
3169 ///
3170 /// // This one needs data rearranging.
3171 /// let mut deque: VecDeque<_> = (1..5).collect();
3172 /// deque.push_front(9);
3173 /// deque.push_front(8);
3174 /// let ptr = deque.as_slices().1.as_ptr();
3175 /// let vec = Vec::from(deque);
3176 /// assert_eq!(vec, [8, 9, 1, 2, 3, 4]);
3177 /// assert_eq!(vec.as_ptr(), ptr);
3178 /// ```
3179 fn from(mut other: VecDeque<T, A>) -> Self {
3180 other.make_contiguous();
3181
3182 unsafe {
3183 let other = ManuallyDrop::new(other);
3184 let buf = other.buf.ptr();
3185 let len = other.len();
3186 let cap = other.capacity();
3187 let alloc = ptr::read(other.allocator());
3188
3189 if other.head != 0 {
3190 ptr::copy(buf.add(other.head), buf, len);
3191 }
3192 Vec::from_raw_parts_in(buf, len, cap, alloc)
3193 }
3194 }
3195}
3196
3197#[stable(feature = "std_collections_from_array", since = "1.56.0")]
3198impl<T, const N: usize> From<[T; N]> for VecDeque<T> {
3199 /// Converts a `[T; N]` into a `VecDeque<T>`.
3200 ///
3201 /// ```
3202 /// use std::collections::VecDeque;
3203 ///
3204 /// let deq1 = VecDeque::from([1, 2, 3, 4]);
3205 /// let deq2: VecDeque<_> = [1, 2, 3, 4].into();
3206 /// assert_eq!(deq1, deq2);
3207 /// ```
3208 #[track_caller]
3209 fn from(arr: [T; N]) -> Self {
3210 let mut deq = VecDeque::with_capacity(N);
3211 let arr = ManuallyDrop::new(arr);
3212 if !<T>::IS_ZST {
3213 // SAFETY: VecDeque::with_capacity ensures that there is enough capacity.
3214 unsafe {
3215 ptr::copy_nonoverlapping(arr.as_ptr(), deq.ptr(), N);
3216 }
3217 }
3218 deq.head = 0;
3219 deq.len = N;
3220 deq
3221 }
3222}
3223