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

Provided by KDAB

Privacy Policy