1 //! A double-ended queue implemented with a growable ring buffer.
3 //! This queue has `O(1)` amortized inserts and removals from both ends of the
4 //! container. It also has `O(1)` indexing like a vector. The contained elements
5 //! are not required to be copyable, and the queue will be sendable if the
6 //! contained type is sendable.
8 #![stable(feature = "rust1", since = "1.0.0")]
10 use core
::array
::LengthAtMost32
;
11 use core
::cmp
::{self, Ordering}
;
13 use core
::hash
::{Hash, Hasher}
;
14 use core
::iter
::{once, repeat_with, FromIterator, FusedIterator}
;
15 use core
::mem
::{self, replace}
;
16 use core
::ops
::Bound
::{Excluded, Included, Unbounded}
;
17 use core
::ops
::{Index, IndexMut, RangeBounds, Try}
;
18 use core
::ptr
::{self, NonNull}
;
21 use crate::collections
::TryReserveError
;
22 use crate::raw_vec
::RawVec
;
25 #[stable(feature = "drain", since = "1.6.0")]
26 pub use self::drain
::Drain
;
33 const INITIAL_CAPACITY
: usize = 7; // 2^3 - 1
34 const MINIMUM_CAPACITY
: usize = 1; // 2 - 1
35 #[cfg(target_pointer_width = "16")]
36 const MAXIMUM_ZST_CAPACITY
: usize = 1 << (16 - 1); // Largest possible power of two
37 #[cfg(target_pointer_width = "32")]
38 const MAXIMUM_ZST_CAPACITY
: usize = 1 << (32 - 1); // Largest possible power of two
39 #[cfg(target_pointer_width = "64")]
40 const MAXIMUM_ZST_CAPACITY
: usize = 1 << (64 - 1); // Largest possible power of two
42 /// A double-ended queue implemented with a growable ring buffer.
44 /// The "default" usage of this type as a queue is to use [`push_back`] to add to
45 /// the queue, and [`pop_front`] to remove from the queue. [`extend`] and [`append`]
46 /// push onto the back in this manner, and iterating over `VecDeque` goes front
49 /// [`push_back`]: #method.push_back
50 /// [`pop_front`]: #method.pop_front
51 /// [`extend`]: #method.extend
52 /// [`append`]: #method.append
53 #[stable(feature = "rust1", since = "1.0.0")]
54 pub struct VecDeque
<T
> {
55 // tail and head are pointers into the buffer. Tail always points
56 // to the first element that could be read, Head always points
57 // to where data should be written.
58 // If tail == head the buffer is empty. The length of the ringbuffer
59 // is defined as the distance between the two.
65 /// PairSlices pairs up equal length slice parts of two deques
67 /// For example, given deques "A" and "B" with the following division into slices:
69 /// A: [0 1 2] [3 4 5]
72 /// It produces the following sequence of matching slices:
78 /// and the uneven remainder of either A or B is skipped.
79 struct PairSlices
<'a
, 'b
, T
> {
86 impl<'a
, 'b
, T
> PairSlices
<'a
, 'b
, T
> {
87 fn from(to
: &'a
mut VecDeque
<T
>, from
: &'b VecDeque
<T
>) -> Self {
88 let (a0
, a1
) = to
.as_mut_slices();
89 let (b0
, b1
) = from
.as_slices();
90 PairSlices { a0, a1, b0, b1 }
93 fn has_remainder(&self) -> bool
{
97 fn remainder(self) -> impl Iterator
<Item
= &'b
[T
]> {
98 once(self.b0
).chain(once(self.b1
))
102 impl<'a
, 'b
, T
> Iterator
for PairSlices
<'a
, 'b
, T
> {
103 type Item
= (&'a
mut [T
], &'b
[T
]);
104 fn next(&mut self) -> Option
<Self::Item
> {
105 // Get next part length
106 let part
= cmp
::min(self.a0
.len(), self.b0
.len());
110 let (p0
, p1
) = replace(&mut self.a0
, &mut []).split_at_mut(part
);
111 let (q0
, q1
) = self.b0
.split_at(part
);
113 // Move a1 into a0, if it's empty (and b1, b0 the same way).
116 if self.a0
.is_empty() {
117 self.a0
= replace(&mut self.a1
, &mut []);
119 if self.b0
.is_empty() {
120 self.b0
= replace(&mut self.b1
, &[]);
126 #[stable(feature = "rust1", since = "1.0.0")]
127 impl<T
: Clone
> Clone
for VecDeque
<T
> {
128 fn clone(&self) -> VecDeque
<T
> {
129 self.iter().cloned().collect()
132 fn clone_from(&mut self, other
: &Self) {
133 self.truncate(other
.len());
135 let mut iter
= PairSlices
::from(self, other
);
136 while let Some((dst
, src
)) = iter
.next() {
137 dst
.clone_from_slice(&src
);
140 if iter
.has_remainder() {
141 for remainder
in iter
.remainder() {
142 self.extend(remainder
.iter().cloned());
148 #[stable(feature = "rust1", since = "1.0.0")]
149 unsafe impl<#[may_dangle] T> Drop for VecDeque<T> {
151 /// Runs the destructor for all items in the slice when it gets dropped (normally or
152 /// during unwinding).
153 struct Dropper
<'a
, T
>(&'a
mut [T
]);
155 impl<'a
, T
> Drop
for Dropper
<'a
, T
> {
158 ptr
::drop_in_place(self.0);
163 let (front
, back
) = self.as_mut_slices();
165 let _back_dropper
= Dropper(back
);
167 ptr
::drop_in_place(front
);
169 // RawVec handles deallocation
173 #[stable(feature = "rust1", since = "1.0.0")]
174 impl<T
> Default
for VecDeque
<T
> {
175 /// Creates an empty `VecDeque<T>`.
177 fn default() -> VecDeque
<T
> {
182 impl<T
> VecDeque
<T
> {
183 /// Marginally more convenient
185 fn ptr(&self) -> *mut T
{
189 /// Marginally more convenient
191 fn cap(&self) -> usize {
192 if mem
::size_of
::<T
>() == 0 {
193 // For zero sized types, we are always at maximum capacity
200 /// Turn ptr into a slice
202 unsafe fn buffer_as_slice(&self) -> &[T
] {
203 slice
::from_raw_parts(self.ptr(), self.cap())
206 /// Turn ptr into a mut slice
208 unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T
] {
209 slice
::from_raw_parts_mut(self.ptr(), self.cap())
212 /// Moves an element out of the buffer
214 unsafe fn buffer_read(&mut self, off
: usize) -> T
{
215 ptr
::read(self.ptr().add(off
))
218 /// Writes an element into the buffer, moving it.
220 unsafe fn buffer_write(&mut self, off
: usize, value
: T
) {
221 ptr
::write(self.ptr().add(off
), value
);
224 /// Returns `true` if the buffer is at full capacity.
226 fn is_full(&self) -> bool
{
227 self.cap() - self.len() == 1
230 /// Returns the index in the underlying buffer for a given logical element
233 fn wrap_index(&self, idx
: usize) -> usize {
234 wrap_index(idx
, self.cap())
237 /// Returns the index in the underlying buffer for a given logical element
240 fn wrap_add(&self, idx
: usize, addend
: usize) -> usize {
241 wrap_index(idx
.wrapping_add(addend
), self.cap())
244 /// Returns the index in the underlying buffer for a given logical element
245 /// index - subtrahend.
247 fn wrap_sub(&self, idx
: usize, subtrahend
: usize) -> usize {
248 wrap_index(idx
.wrapping_sub(subtrahend
), self.cap())
251 /// Copies a contiguous block of memory len long from src to dst
253 unsafe fn copy(&self, dst
: usize, src
: usize, len
: usize) {
255 dst
+ len
<= self.cap(),
256 "cpy dst={} src={} len={} cap={}",
263 src
+ len
<= self.cap(),
264 "cpy dst={} src={} len={} cap={}",
270 ptr
::copy(self.ptr().add(src
), self.ptr().add(dst
), len
);
273 /// Copies a contiguous block of memory len long from src to dst
275 unsafe fn copy_nonoverlapping(&self, dst
: usize, src
: usize, len
: usize) {
277 dst
+ len
<= self.cap(),
278 "cno dst={} src={} len={} cap={}",
285 src
+ len
<= self.cap(),
286 "cno dst={} src={} len={} cap={}",
292 ptr
::copy_nonoverlapping(self.ptr().add(src
), self.ptr().add(dst
), len
);
295 /// Copies a potentially wrapping block of memory len long from src to dest.
296 /// (abs(dst - src) + len) must be no larger than cap() (There must be at
297 /// most one continuous overlapping region between src and dest).
298 unsafe fn wrap_copy(&self, dst
: usize, src
: usize, len
: usize) {
300 fn diff(a
: usize, b
: usize) -> usize {
301 if a
<= b { b - a }
else { a - b }
304 cmp
::min(diff(dst
, src
), self.cap() - diff(dst
, src
)) + len
<= self.cap(),
305 "wrc dst={} src={} len={} cap={}",
312 if src
== dst
|| len
== 0 {
316 let dst_after_src
= self.wrap_sub(dst
, src
) < len
;
318 let src_pre_wrap_len
= self.cap() - src
;
319 let dst_pre_wrap_len
= self.cap() - dst
;
320 let src_wraps
= src_pre_wrap_len
< len
;
321 let dst_wraps
= dst_pre_wrap_len
< len
;
323 match (dst_after_src
, src_wraps
, dst_wraps
) {
324 (_
, false, false) => {
325 // src doesn't wrap, dst doesn't wrap
328 // 1 [_ _ A A B B C C _]
329 // 2 [_ _ A A A A B B _]
332 self.copy(dst
, src
, len
);
334 (false, false, true) => {
335 // dst before src, src doesn't wrap, dst wraps
338 // 1 [A A B B _ _ _ C C]
339 // 2 [A A B B _ _ _ A A]
340 // 3 [B B B B _ _ _ A A]
343 self.copy(dst
, src
, dst_pre_wrap_len
);
344 self.copy(0, src
+ dst_pre_wrap_len
, len
- dst_pre_wrap_len
);
346 (true, false, true) => {
347 // src before dst, src doesn't wrap, dst wraps
350 // 1 [C C _ _ _ A A B B]
351 // 2 [B B _ _ _ A A B B]
352 // 3 [B B _ _ _ A A A A]
355 self.copy(0, src
+ dst_pre_wrap_len
, len
- dst_pre_wrap_len
);
356 self.copy(dst
, src
, dst_pre_wrap_len
);
358 (false, true, false) => {
359 // dst before src, src wraps, dst doesn't wrap
362 // 1 [C C _ _ _ A A B B]
363 // 2 [C C _ _ _ B B B B]
364 // 3 [C C _ _ _ B B C C]
367 self.copy(dst
, src
, src_pre_wrap_len
);
368 self.copy(dst
+ src_pre_wrap_len
, 0, len
- src_pre_wrap_len
);
370 (true, true, false) => {
371 // src before dst, src wraps, dst doesn't wrap
374 // 1 [A A B B _ _ _ C C]
375 // 2 [A A A A _ _ _ C C]
376 // 3 [C C A A _ _ _ C C]
379 self.copy(dst
+ src_pre_wrap_len
, 0, len
- src_pre_wrap_len
);
380 self.copy(dst
, src
, src_pre_wrap_len
);
382 (false, true, true) => {
383 // dst before src, src wraps, dst wraps
386 // 1 [A B C D _ E F G H]
387 // 2 [A B C D _ E G H H]
388 // 3 [A B C D _ E G H A]
389 // 4 [B C C D _ E G H A]
392 debug_assert
!(dst_pre_wrap_len
> src_pre_wrap_len
);
393 let delta
= dst_pre_wrap_len
- src_pre_wrap_len
;
394 self.copy(dst
, src
, src_pre_wrap_len
);
395 self.copy(dst
+ src_pre_wrap_len
, 0, delta
);
396 self.copy(0, delta
, len
- dst_pre_wrap_len
);
398 (true, true, true) => {
399 // src before dst, src wraps, dst wraps
402 // 1 [A B C D _ E F G H]
403 // 2 [A A B D _ E F G H]
404 // 3 [H A B D _ E F G H]
405 // 4 [H A B D _ E F F G]
408 debug_assert
!(src_pre_wrap_len
> dst_pre_wrap_len
);
409 let delta
= src_pre_wrap_len
- dst_pre_wrap_len
;
410 self.copy(delta
, 0, len
- src_pre_wrap_len
);
411 self.copy(0, self.cap() - delta
, delta
);
412 self.copy(dst
, src
, dst_pre_wrap_len
);
417 /// Frobs the head and tail sections around to handle the fact that we
418 /// just reallocated. Unsafe because it trusts old_capacity.
420 unsafe fn handle_capacity_increase(&mut self, old_capacity
: usize) {
421 let new_capacity
= self.cap();
423 // Move the shortest contiguous section of the ring buffer
425 // [o o o o o o o . ]
427 // A [o o o o o o o . . . . . . . . . ]
429 // [o o . o o o o o ]
431 // B [. . . o o o o o o o . . . . . . ]
433 // [o o o o o . o o ]
435 // C [o o o o o . . . . . . . . . o o ]
437 if self.tail
<= self.head
{
440 } else if self.head
< old_capacity
- self.tail
{
442 self.copy_nonoverlapping(old_capacity
, 0, self.head
);
443 self.head
+= old_capacity
;
444 debug_assert
!(self.head
> self.tail
);
447 let new_tail
= new_capacity
- (old_capacity
- self.tail
);
448 self.copy_nonoverlapping(new_tail
, self.tail
, old_capacity
- self.tail
);
449 self.tail
= new_tail
;
450 debug_assert
!(self.head
< self.tail
);
452 debug_assert
!(self.head
< self.cap());
453 debug_assert
!(self.tail
< self.cap());
454 debug_assert
!(self.cap().count_ones() == 1);
458 impl<T
> VecDeque
<T
> {
459 /// Creates an empty `VecDeque`.
464 /// use std::collections::VecDeque;
466 /// let vector: VecDeque<u32> = VecDeque::new();
468 #[stable(feature = "rust1", since = "1.0.0")]
469 pub fn new() -> VecDeque
<T
> {
470 VecDeque
::with_capacity(INITIAL_CAPACITY
)
473 /// Creates an empty `VecDeque` with space for at least `capacity` elements.
478 /// use std::collections::VecDeque;
480 /// let vector: VecDeque<u32> = VecDeque::with_capacity(10);
482 #[stable(feature = "rust1", since = "1.0.0")]
483 pub fn with_capacity(capacity
: usize) -> VecDeque
<T
> {
484 // +1 since the ringbuffer always leaves one space empty
485 let cap
= cmp
::max(capacity
+ 1, MINIMUM_CAPACITY
+ 1).next_power_of_two();
486 assert
!(cap
> capacity
, "capacity overflow");
488 VecDeque { tail: 0, head: 0, buf: RawVec::with_capacity(cap) }
491 /// Retrieves an element in the `VecDeque` by index.
493 /// Element at index 0 is the front of the queue.
498 /// use std::collections::VecDeque;
500 /// let mut buf = VecDeque::new();
501 /// buf.push_back(3);
502 /// buf.push_back(4);
503 /// buf.push_back(5);
504 /// assert_eq!(buf.get(1), Some(&4));
506 #[stable(feature = "rust1", since = "1.0.0")]
507 pub fn get(&self, index
: usize) -> Option
<&T
> {
508 if index
< self.len() {
509 let idx
= self.wrap_add(self.tail
, index
);
510 unsafe { Some(&*self.ptr().add(idx)) }
516 /// Retrieves an element in the `VecDeque` mutably by index.
518 /// Element at index 0 is the front of the queue.
523 /// use std::collections::VecDeque;
525 /// let mut buf = VecDeque::new();
526 /// buf.push_back(3);
527 /// buf.push_back(4);
528 /// buf.push_back(5);
529 /// if let Some(elem) = buf.get_mut(1) {
533 /// assert_eq!(buf[1], 7);
535 #[stable(feature = "rust1", since = "1.0.0")]
536 pub fn get_mut(&mut self, index
: usize) -> Option
<&mut T
> {
537 if index
< self.len() {
538 let idx
= self.wrap_add(self.tail
, index
);
539 unsafe { Some(&mut *self.ptr().add(idx)) }
545 /// Swaps elements at indices `i` and `j`.
547 /// `i` and `j` may be equal.
549 /// Element at index 0 is the front of the queue.
553 /// Panics if either index is out of bounds.
558 /// use std::collections::VecDeque;
560 /// let mut buf = VecDeque::new();
561 /// buf.push_back(3);
562 /// buf.push_back(4);
563 /// buf.push_back(5);
564 /// assert_eq!(buf, [3, 4, 5]);
566 /// assert_eq!(buf, [5, 4, 3]);
568 #[stable(feature = "rust1", since = "1.0.0")]
569 pub fn swap(&mut self, i
: usize, j
: usize) {
570 assert
!(i
< self.len());
571 assert
!(j
< self.len());
572 let ri
= self.wrap_add(self.tail
, i
);
573 let rj
= self.wrap_add(self.tail
, j
);
574 unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) }
577 /// Returns the number of elements the `VecDeque` can hold without
583 /// use std::collections::VecDeque;
585 /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
586 /// assert!(buf.capacity() >= 10);
589 #[stable(feature = "rust1", since = "1.0.0")]
590 pub fn capacity(&self) -> usize {
594 /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
595 /// given `VecDeque`. Does nothing if the capacity is already sufficient.
597 /// Note that the allocator may give the collection more space than it requests. Therefore
598 /// capacity can not be relied upon to be precisely minimal. Prefer [`reserve`] if future
599 /// insertions are expected.
603 /// Panics if the new capacity overflows `usize`.
608 /// use std::collections::VecDeque;
610 /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
611 /// buf.reserve_exact(10);
612 /// assert!(buf.capacity() >= 11);
615 /// [`reserve`]: #method.reserve
616 #[stable(feature = "rust1", since = "1.0.0")]
617 pub fn reserve_exact(&mut self, additional
: usize) {
618 self.reserve(additional
);
621 /// Reserves capacity for at least `additional` more elements to be inserted in the given
622 /// `VecDeque`. The collection may reserve more space to avoid frequent reallocations.
626 /// Panics if the new capacity overflows `usize`.
631 /// use std::collections::VecDeque;
633 /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
635 /// assert!(buf.capacity() >= 11);
637 #[stable(feature = "rust1", since = "1.0.0")]
638 pub fn reserve(&mut self, additional
: usize) {
639 let old_cap
= self.cap();
640 let used_cap
= self.len() + 1;
641 let new_cap
= used_cap
642 .checked_add(additional
)
643 .and_then(|needed_cap
| needed_cap
.checked_next_power_of_two())
644 .expect("capacity overflow");
646 if new_cap
> old_cap
{
647 self.buf
.reserve_exact(used_cap
, new_cap
- used_cap
);
649 self.handle_capacity_increase(old_cap
);
654 /// Tries to reserves the minimum capacity for exactly `additional` more elements to
655 /// be inserted in the given `VecDeque<T>`. After calling `reserve_exact`,
656 /// capacity will be greater than or equal to `self.len() + additional`.
657 /// Does nothing if the capacity is already sufficient.
659 /// Note that the allocator may give the collection more space than it
660 /// requests. Therefore, capacity can not be relied upon to be precisely
661 /// minimal. Prefer `reserve` if future insertions are expected.
665 /// If the capacity overflows, or the allocator reports a failure, then an error
671 /// #![feature(try_reserve)]
672 /// use std::collections::TryReserveError;
673 /// use std::collections::VecDeque;
675 /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
676 /// let mut output = VecDeque::new();
678 /// // Pre-reserve the memory, exiting if we can't
679 /// output.try_reserve_exact(data.len())?;
681 /// // Now we know this can't OOM in the middle of our complex work
682 /// output.extend(data.iter().map(|&val| {
683 /// val * 2 + 5 // very complicated
688 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
690 #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
691 pub fn try_reserve_exact(&mut self, additional
: usize) -> Result
<(), TryReserveError
> {
692 self.try_reserve(additional
)
695 /// Tries to reserve capacity for at least `additional` more elements to be inserted
696 /// in the given `VecDeque<T>`. The collection may reserve more space to avoid
697 /// frequent reallocations. After calling `reserve`, capacity will be
698 /// greater than or equal to `self.len() + additional`. Does nothing if
699 /// capacity is already sufficient.
703 /// If the capacity overflows, or the allocator reports a failure, then an error
709 /// #![feature(try_reserve)]
710 /// use std::collections::TryReserveError;
711 /// use std::collections::VecDeque;
713 /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
714 /// let mut output = VecDeque::new();
716 /// // Pre-reserve the memory, exiting if we can't
717 /// output.try_reserve(data.len())?;
719 /// // Now we know this can't OOM in the middle of our complex work
720 /// output.extend(data.iter().map(|&val| {
721 /// val * 2 + 5 // very complicated
726 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
728 #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
729 pub fn try_reserve(&mut self, additional
: usize) -> Result
<(), TryReserveError
> {
730 let old_cap
= self.cap();
731 let used_cap
= self.len() + 1;
732 let new_cap
= used_cap
733 .checked_add(additional
)
734 .and_then(|needed_cap
| needed_cap
.checked_next_power_of_two())
735 .ok_or(TryReserveError
::CapacityOverflow
)?
;
737 if new_cap
> old_cap
{
738 self.buf
.try_reserve_exact(used_cap
, new_cap
- used_cap
)?
;
740 self.handle_capacity_increase(old_cap
);
746 /// Shrinks the capacity of the `VecDeque` as much as possible.
748 /// It will drop down as close as possible to the length but the allocator may still inform the
749 /// `VecDeque` that there is space for a few more elements.
754 /// use std::collections::VecDeque;
756 /// let mut buf = VecDeque::with_capacity(15);
757 /// buf.extend(0..4);
758 /// assert_eq!(buf.capacity(), 15);
759 /// buf.shrink_to_fit();
760 /// assert!(buf.capacity() >= 4);
762 #[stable(feature = "deque_extras_15", since = "1.5.0")]
763 pub fn shrink_to_fit(&mut self) {
767 /// Shrinks the capacity of the `VecDeque` with a lower bound.
769 /// The capacity will remain at least as large as both the length
770 /// and the supplied value.
772 /// Panics if the current capacity is smaller than the supplied
773 /// minimum capacity.
778 /// #![feature(shrink_to)]
779 /// use std::collections::VecDeque;
781 /// let mut buf = VecDeque::with_capacity(15);
782 /// buf.extend(0..4);
783 /// assert_eq!(buf.capacity(), 15);
784 /// buf.shrink_to(6);
785 /// assert!(buf.capacity() >= 6);
786 /// buf.shrink_to(0);
787 /// assert!(buf.capacity() >= 4);
789 #[unstable(feature = "shrink_to", reason = "new API", issue = "56431")]
790 pub fn shrink_to(&mut self, min_capacity
: usize) {
791 assert
!(self.capacity() >= min_capacity
, "Tried to shrink to a larger capacity");
793 // +1 since the ringbuffer always leaves one space empty
794 // len + 1 can't overflow for an existing, well-formed ringbuffer.
795 let target_cap
= cmp
::max(cmp
::max(min_capacity
, self.len()) + 1, MINIMUM_CAPACITY
+ 1)
796 .next_power_of_two();
798 if target_cap
< self.cap() {
799 // There are three cases of interest:
800 // All elements are out of desired bounds
801 // Elements are contiguous, and head is out of desired bounds
802 // Elements are discontiguous, and tail is out of desired bounds
804 // At all other times, element positions are unaffected.
806 // Indicates that elements at the head should be moved.
807 let head_outside
= self.head
== 0 || self.head
>= target_cap
;
808 // Move elements from out of desired bounds (positions after target_cap)
809 if self.tail
>= target_cap
&& head_outside
{
811 // [. . . . . . . . o o o o o o o . ]
813 // [o o o o o o o . ]
815 self.copy_nonoverlapping(0, self.tail
, self.len());
817 self.head
= self.len();
819 } else if self.tail
!= 0 && self.tail
< target_cap
&& head_outside
{
821 // [. . . o o o o o o o . . . . . . ]
823 // [o o . o o o o o ]
824 let len
= self.wrap_sub(self.head
, target_cap
);
826 self.copy_nonoverlapping(0, target_cap
, len
);
829 debug_assert
!(self.head
< self.tail
);
830 } else if self.tail
>= target_cap
{
832 // [o o o o o . . . . . . . . . o o ]
834 // [o o o o o . o o ]
835 debug_assert
!(self.wrap_sub(self.head
, 1) < target_cap
);
836 let len
= self.cap() - self.tail
;
837 let new_tail
= target_cap
- len
;
839 self.copy_nonoverlapping(new_tail
, self.tail
, len
);
841 self.tail
= new_tail
;
842 debug_assert
!(self.head
< self.tail
);
845 self.buf
.shrink_to_fit(target_cap
);
847 debug_assert
!(self.head
< self.cap());
848 debug_assert
!(self.tail
< self.cap());
849 debug_assert
!(self.cap().count_ones() == 1);
853 /// Shortens the `VecDeque`, keeping the first `len` elements and dropping
856 /// If `len` is greater than the `VecDeque`'s current length, this has no
862 /// use std::collections::VecDeque;
864 /// let mut buf = VecDeque::new();
865 /// buf.push_back(5);
866 /// buf.push_back(10);
867 /// buf.push_back(15);
868 /// assert_eq!(buf, [5, 10, 15]);
870 /// assert_eq!(buf, [5]);
872 #[stable(feature = "deque_extras", since = "1.16.0")]
873 pub fn truncate(&mut self, len
: usize) {
874 /// Runs the destructor for all items in the slice when it gets dropped (normally or
875 /// during unwinding).
876 struct Dropper
<'a
, T
>(&'a
mut [T
]);
878 impl<'a
, T
> Drop
for Dropper
<'a
, T
> {
881 ptr
::drop_in_place(self.0);
888 // * Any slice passed to `drop_in_place` is valid; the second case has
889 // `len <= front.len()` and returning on `len > self.len()` ensures
890 // `begin <= back.len()` in the first case
891 // * The head of the VecDeque is moved before calling `drop_in_place`,
892 // so no value is dropped twice if `drop_in_place` panics
894 if len
> self.len() {
897 let num_dropped
= self.len() - len
;
898 let (front
, back
) = self.as_mut_slices();
899 if len
> front
.len() {
900 let begin
= len
- front
.len();
901 let drop_back
= back
.get_unchecked_mut(begin
..) as *mut _
;
902 self.head
= self.wrap_sub(self.head
, num_dropped
);
903 ptr
::drop_in_place(drop_back
);
905 let drop_back
= back
as *mut _
;
906 let drop_front
= front
.get_unchecked_mut(len
..) as *mut _
;
907 self.head
= self.wrap_sub(self.head
, num_dropped
);
909 // Make sure the second half is dropped even when a destructor
910 // in the first one panics.
911 let _back_dropper
= Dropper(&mut *drop_back
);
912 ptr
::drop_in_place(drop_front
);
917 /// Returns a front-to-back iterator.
922 /// use std::collections::VecDeque;
924 /// let mut buf = VecDeque::new();
925 /// buf.push_back(5);
926 /// buf.push_back(3);
927 /// buf.push_back(4);
928 /// let b: &[_] = &[&5, &3, &4];
929 /// let c: Vec<&i32> = buf.iter().collect();
930 /// assert_eq!(&c[..], b);
932 #[stable(feature = "rust1", since = "1.0.0")]
933 pub fn iter(&self) -> Iter
<'_
, T
> {
934 Iter { tail: self.tail, head: self.head, ring: unsafe { self.buffer_as_slice() }
}
937 /// Returns a front-to-back iterator that returns mutable references.
942 /// use std::collections::VecDeque;
944 /// let mut buf = VecDeque::new();
945 /// buf.push_back(5);
946 /// buf.push_back(3);
947 /// buf.push_back(4);
948 /// for num in buf.iter_mut() {
951 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
952 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
954 #[stable(feature = "rust1", since = "1.0.0")]
955 pub fn iter_mut(&mut self) -> IterMut
<'_
, T
> {
956 IterMut { tail: self.tail, head: self.head, ring: unsafe { self.buffer_as_mut_slice() }
}
959 /// Returns a pair of slices which contain, in order, the contents of the
965 /// use std::collections::VecDeque;
967 /// let mut vector = VecDeque::new();
969 /// vector.push_back(0);
970 /// vector.push_back(1);
971 /// vector.push_back(2);
973 /// assert_eq!(vector.as_slices(), (&[0, 1, 2][..], &[][..]));
975 /// vector.push_front(10);
976 /// vector.push_front(9);
978 /// assert_eq!(vector.as_slices(), (&[9, 10][..], &[0, 1, 2][..]));
981 #[stable(feature = "deque_extras_15", since = "1.5.0")]
982 pub fn as_slices(&self) -> (&[T
], &[T
]) {
984 let buf
= self.buffer_as_slice();
985 RingSlices
::ring_slices(buf
, self.head
, self.tail
)
989 /// Returns a pair of slices which contain, in order, the contents of the
995 /// use std::collections::VecDeque;
997 /// let mut vector = VecDeque::new();
999 /// vector.push_back(0);
1000 /// vector.push_back(1);
1002 /// vector.push_front(10);
1003 /// vector.push_front(9);
1005 /// vector.as_mut_slices().0[0] = 42;
1006 /// vector.as_mut_slices().1[0] = 24;
1007 /// assert_eq!(vector.as_slices(), (&[42, 10][..], &[24, 1][..]));
1010 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1011 pub fn as_mut_slices(&mut self) -> (&mut [T
], &mut [T
]) {
1013 let head
= self.head
;
1014 let tail
= self.tail
;
1015 let buf
= self.buffer_as_mut_slice();
1016 RingSlices
::ring_slices(buf
, head
, tail
)
1020 /// Returns the number of elements in the `VecDeque`.
1025 /// use std::collections::VecDeque;
1027 /// let mut v = VecDeque::new();
1028 /// assert_eq!(v.len(), 0);
1030 /// assert_eq!(v.len(), 1);
1032 #[stable(feature = "rust1", since = "1.0.0")]
1033 pub fn len(&self) -> usize {
1034 count(self.tail
, self.head
, self.cap())
1037 /// Returns `true` if the `VecDeque` is empty.
1042 /// use std::collections::VecDeque;
1044 /// let mut v = VecDeque::new();
1045 /// assert!(v.is_empty());
1046 /// v.push_front(1);
1047 /// assert!(!v.is_empty());
1049 #[stable(feature = "rust1", since = "1.0.0")]
1050 pub fn is_empty(&self) -> bool
{
1051 self.tail
== self.head
1054 /// Creates a draining iterator that removes the specified range in the
1055 /// `VecDeque` and yields the removed items.
1057 /// Note 1: The element range is removed even if the iterator is not
1058 /// consumed until the end.
1060 /// Note 2: It is unspecified how many elements are removed from the deque,
1061 /// if the `Drain` value is not dropped, but the borrow it holds expires
1062 /// (e.g., due to `mem::forget`).
1066 /// Panics if the starting point is greater than the end point or if
1067 /// the end point is greater than the length of the vector.
1072 /// use std::collections::VecDeque;
1074 /// let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
1075 /// let drained = v.drain(2..).collect::<VecDeque<_>>();
1076 /// assert_eq!(drained, [3]);
1077 /// assert_eq!(v, [1, 2]);
1079 /// // A full range clears all contents
1081 /// assert!(v.is_empty());
1084 #[stable(feature = "drain", since = "1.6.0")]
1085 pub fn drain
<R
>(&mut self, range
: R
) -> Drain
<'_
, T
>
1087 R
: RangeBounds
<usize>,
1091 // When the Drain is first created, the source deque is shortened to
1092 // make sure no uninitialized or moved-from elements are accessible at
1093 // all if the Drain's destructor never gets to run.
1095 // Drain will ptr::read out the values to remove.
1096 // When finished, the remaining data will be copied back to cover the hole,
1097 // and the head/tail values will be restored correctly.
1099 let len
= self.len();
1100 let start
= match range
.start_bound() {
1102 Excluded(&n
) => n
+ 1,
1105 let end
= match range
.end_bound() {
1106 Included(&n
) => n
+ 1,
1110 assert
!(start
<= end
, "drain lower bound was too large");
1111 assert
!(end
<= len
, "drain upper bound was too large");
1113 // The deque's elements are parted into three segments:
1114 // * self.tail -> drain_tail
1115 // * drain_tail -> drain_head
1116 // * drain_head -> self.head
1118 // T = self.tail; H = self.head; t = drain_tail; h = drain_head
1120 // We store drain_tail as self.head, and drain_head and self.head as
1121 // after_tail and after_head respectively on the Drain. This also
1122 // truncates the effective array such that if the Drain is leaked, we
1123 // have forgotten about the potentially moved values after the start of
1127 // [. . . o o x x o o . . .]
1129 let drain_tail
= self.wrap_add(self.tail
, start
);
1130 let drain_head
= self.wrap_add(self.tail
, end
);
1131 let head
= self.head
;
1133 // "forget" about the values after the start of the drain until after
1134 // the drain is complete and the Drain destructor is run.
1135 self.head
= drain_tail
;
1138 deque
: NonNull
::from(&mut *self),
1139 after_tail
: drain_head
,
1144 // Crucially, we only create shared references from `self` here and read from
1145 // it. We do not write to `self` nor reborrow to a mutable reference.
1146 // Hence the raw pointer we created above, for `deque`, remains valid.
1147 ring
: unsafe { self.buffer_as_slice() }
,
1152 /// Clears the `VecDeque`, removing all values.
1157 /// use std::collections::VecDeque;
1159 /// let mut v = VecDeque::new();
1162 /// assert!(v.is_empty());
1164 #[stable(feature = "rust1", since = "1.0.0")]
1166 pub fn clear(&mut self) {
1170 /// Returns `true` if the `VecDeque` contains an element equal to the
1176 /// use std::collections::VecDeque;
1178 /// let mut vector: VecDeque<u32> = VecDeque::new();
1180 /// vector.push_back(0);
1181 /// vector.push_back(1);
1183 /// assert_eq!(vector.contains(&1), true);
1184 /// assert_eq!(vector.contains(&10), false);
1186 #[stable(feature = "vec_deque_contains", since = "1.12.0")]
1187 pub fn contains(&self, x
: &T
) -> bool
1191 let (a
, b
) = self.as_slices();
1192 a
.contains(x
) || b
.contains(x
)
1195 /// Provides a reference to the front element, or `None` if the `VecDeque` is
1201 /// use std::collections::VecDeque;
1203 /// let mut d = VecDeque::new();
1204 /// assert_eq!(d.front(), None);
1208 /// assert_eq!(d.front(), Some(&1));
1210 #[stable(feature = "rust1", since = "1.0.0")]
1211 pub fn front(&self) -> Option
<&T
> {
1212 if !self.is_empty() { Some(&self[0]) }
else { None }
1215 /// Provides a mutable reference to the front element, or `None` if the
1216 /// `VecDeque` is empty.
1221 /// use std::collections::VecDeque;
1223 /// let mut d = VecDeque::new();
1224 /// assert_eq!(d.front_mut(), None);
1228 /// match d.front_mut() {
1229 /// Some(x) => *x = 9,
1232 /// assert_eq!(d.front(), Some(&9));
1234 #[stable(feature = "rust1", since = "1.0.0")]
1235 pub fn front_mut(&mut self) -> Option
<&mut T
> {
1236 if !self.is_empty() { Some(&mut self[0]) }
else { None }
1239 /// Provides a reference to the back element, or `None` if the `VecDeque` is
1245 /// use std::collections::VecDeque;
1247 /// let mut d = VecDeque::new();
1248 /// assert_eq!(d.back(), None);
1252 /// assert_eq!(d.back(), Some(&2));
1254 #[stable(feature = "rust1", since = "1.0.0")]
1255 pub fn back(&self) -> Option
<&T
> {
1256 if !self.is_empty() { Some(&self[self.len() - 1]) }
else { None }
1259 /// Provides a mutable reference to the back element, or `None` if the
1260 /// `VecDeque` is empty.
1265 /// use std::collections::VecDeque;
1267 /// let mut d = VecDeque::new();
1268 /// assert_eq!(d.back(), None);
1272 /// match d.back_mut() {
1273 /// Some(x) => *x = 9,
1276 /// assert_eq!(d.back(), Some(&9));
1278 #[stable(feature = "rust1", since = "1.0.0")]
1279 pub fn back_mut(&mut self) -> Option
<&mut T
> {
1280 let len
= self.len();
1281 if !self.is_empty() { Some(&mut self[len - 1]) }
else { None }
1284 /// Removes the first element and returns it, or `None` if the `VecDeque` is
1290 /// use std::collections::VecDeque;
1292 /// let mut d = VecDeque::new();
1296 /// assert_eq!(d.pop_front(), Some(1));
1297 /// assert_eq!(d.pop_front(), Some(2));
1298 /// assert_eq!(d.pop_front(), None);
1300 #[stable(feature = "rust1", since = "1.0.0")]
1301 pub fn pop_front(&mut self) -> Option
<T
> {
1302 if self.is_empty() {
1305 let tail
= self.tail
;
1306 self.tail
= self.wrap_add(self.tail
, 1);
1307 unsafe { Some(self.buffer_read(tail)) }
1311 /// Removes the last element from the `VecDeque` and returns it, or `None` if
1317 /// use std::collections::VecDeque;
1319 /// let mut buf = VecDeque::new();
1320 /// assert_eq!(buf.pop_back(), None);
1321 /// buf.push_back(1);
1322 /// buf.push_back(3);
1323 /// assert_eq!(buf.pop_back(), Some(3));
1325 #[stable(feature = "rust1", since = "1.0.0")]
1326 pub fn pop_back(&mut self) -> Option
<T
> {
1327 if self.is_empty() {
1330 self.head
= self.wrap_sub(self.head
, 1);
1331 let head
= self.head
;
1332 unsafe { Some(self.buffer_read(head)) }
1336 /// Prepends an element to the `VecDeque`.
1341 /// use std::collections::VecDeque;
1343 /// let mut d = VecDeque::new();
1344 /// d.push_front(1);
1345 /// d.push_front(2);
1346 /// assert_eq!(d.front(), Some(&2));
1348 #[stable(feature = "rust1", since = "1.0.0")]
1349 pub fn push_front(&mut self, value
: T
) {
1350 self.grow_if_necessary();
1352 self.tail
= self.wrap_sub(self.tail
, 1);
1353 let tail
= self.tail
;
1355 self.buffer_write(tail
, value
);
1359 /// Appends an element to the back of the `VecDeque`.
1364 /// use std::collections::VecDeque;
1366 /// let mut buf = VecDeque::new();
1367 /// buf.push_back(1);
1368 /// buf.push_back(3);
1369 /// assert_eq!(3, *buf.back().unwrap());
1371 #[stable(feature = "rust1", since = "1.0.0")]
1372 pub fn push_back(&mut self, value
: T
) {
1373 self.grow_if_necessary();
1375 let head
= self.head
;
1376 self.head
= self.wrap_add(self.head
, 1);
1377 unsafe { self.buffer_write(head, value) }
1381 fn is_contiguous(&self) -> bool
{
1382 self.tail
<= self.head
1385 /// Removes an element from anywhere in the `VecDeque` and returns it,
1386 /// replacing it with the first element.
1388 /// This does not preserve ordering, but is O(1).
1390 /// Returns `None` if `index` is out of bounds.
1392 /// Element at index 0 is the front of the queue.
1397 /// use std::collections::VecDeque;
1399 /// let mut buf = VecDeque::new();
1400 /// assert_eq!(buf.swap_remove_front(0), None);
1401 /// buf.push_back(1);
1402 /// buf.push_back(2);
1403 /// buf.push_back(3);
1404 /// assert_eq!(buf, [1, 2, 3]);
1406 /// assert_eq!(buf.swap_remove_front(2), Some(3));
1407 /// assert_eq!(buf, [2, 1]);
1409 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1410 pub fn swap_remove_front(&mut self, index
: usize) -> Option
<T
> {
1411 let length
= self.len();
1412 if length
> 0 && index
< length
&& index
!= 0 {
1413 self.swap(index
, 0);
1414 } else if index
>= length
{
1420 /// Removes an element from anywhere in the `VecDeque` and returns it, replacing it with the
1423 /// This does not preserve ordering, but is O(1).
1425 /// Returns `None` if `index` is out of bounds.
1427 /// Element at index 0 is the front of the queue.
1432 /// use std::collections::VecDeque;
1434 /// let mut buf = VecDeque::new();
1435 /// assert_eq!(buf.swap_remove_back(0), None);
1436 /// buf.push_back(1);
1437 /// buf.push_back(2);
1438 /// buf.push_back(3);
1439 /// assert_eq!(buf, [1, 2, 3]);
1441 /// assert_eq!(buf.swap_remove_back(0), Some(1));
1442 /// assert_eq!(buf, [3, 2]);
1444 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1445 pub fn swap_remove_back(&mut self, index
: usize) -> Option
<T
> {
1446 let length
= self.len();
1447 if length
> 0 && index
< length
- 1 {
1448 self.swap(index
, length
- 1);
1449 } else if index
>= length
{
1455 /// Inserts an element at `index` within the `VecDeque`, shifting all elements with indices
1456 /// greater than or equal to `index` towards the back.
1458 /// Element at index 0 is the front of the queue.
1462 /// Panics if `index` is greater than `VecDeque`'s length
1467 /// use std::collections::VecDeque;
1469 /// let mut vec_deque = VecDeque::new();
1470 /// vec_deque.push_back('a');
1471 /// vec_deque.push_back('b');
1472 /// vec_deque.push_back('c');
1473 /// assert_eq!(vec_deque, &['a', 'b', 'c']);
1475 /// vec_deque.insert(1, 'd');
1476 /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
1478 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1479 pub fn insert(&mut self, index
: usize, value
: T
) {
1480 assert
!(index
<= self.len(), "index out of bounds");
1481 self.grow_if_necessary();
1483 // Move the least number of elements in the ring buffer and insert
1486 // At most len/2 - 1 elements will be moved. O(min(n, n-i))
1488 // There are three main cases:
1489 // Elements are contiguous
1490 // - special case when tail is 0
1491 // Elements are discontiguous and the insert is in the tail section
1492 // Elements are discontiguous and the insert is in the head section
1494 // For each of those there are two more cases:
1495 // Insert is closer to tail
1496 // Insert is closer to head
1498 // Key: H - self.head
1500 // o - Valid element
1501 // I - Insertion element
1502 // A - The element that should be after the insertion point
1503 // M - Indicates element was moved
1505 let idx
= self.wrap_add(self.tail
, index
);
1507 let distance_to_tail
= index
;
1508 let distance_to_head
= self.len() - index
;
1510 let contiguous
= self.is_contiguous();
1512 match (contiguous
, distance_to_tail
<= distance_to_head
, idx
>= self.tail
) {
1513 (true, true, _
) if index
== 0 => {
1518 // [A o o o o o o . . . . . . . . .]
1521 // [A o o o o o o o . . . . . I]
1524 self.tail
= self.wrap_sub(self.tail
, 1);
1526 (true, true, _
) => {
1528 // contiguous, insert closer to tail:
1531 // [. . . o o A o o o o . . . . . .]
1534 // [. . o o I A o o o o . . . . . .]
1537 // contiguous, insert closer to tail and tail is 0:
1541 // [o o A o o o o . . . . . . . . .]
1544 // [o I A o o o o o . . . . . . . o]
1547 let new_tail
= self.wrap_sub(self.tail
, 1);
1549 self.copy(new_tail
, self.tail
, 1);
1550 // Already moved the tail, so we only copy `index - 1` elements.
1551 self.copy(self.tail
, self.tail
+ 1, index
- 1);
1553 self.tail
= new_tail
;
1556 (true, false, _
) => {
1558 // contiguous, insert closer to head:
1561 // [. . . o o o o A o o . . . . . .]
1564 // [. . . o o o o I A o o . . . . .]
1567 self.copy(idx
+ 1, idx
, self.head
- idx
);
1568 self.head
= self.wrap_add(self.head
, 1);
1571 (false, true, true) => {
1573 // discontiguous, insert closer to tail, tail section:
1576 // [o o o o o o . . . . . o o A o o]
1579 // [o o o o o o . . . . o o I A o o]
1582 self.copy(self.tail
- 1, self.tail
, index
);
1586 (false, false, true) => {
1588 // discontiguous, insert closer to head, tail section:
1591 // [o o . . . . . . . o o o o o A o]
1594 // [o o o . . . . . . o o o o o I A]
1597 // copy elements up to new head
1598 self.copy(1, 0, self.head
);
1600 // copy last element into empty spot at bottom of buffer
1601 self.copy(0, self.cap() - 1, 1);
1603 // move elements from idx to end forward not including ^ element
1604 self.copy(idx
+ 1, idx
, self.cap() - 1 - idx
);
1609 (false, true, false) if idx
== 0 => {
1611 // discontiguous, insert is closer to tail, head section,
1612 // and is at index zero in the internal buffer:
1615 // [A o o o o o o o o o . . . o o o]
1618 // [A o o o o o o o o o . . o o o I]
1621 // copy elements up to new tail
1622 self.copy(self.tail
- 1, self.tail
, self.cap() - self.tail
);
1624 // copy last element into empty spot at bottom of buffer
1625 self.copy(self.cap() - 1, 0, 1);
1630 (false, true, false) => {
1632 // discontiguous, insert closer to tail, head section:
1635 // [o o o A o o o o o o . . . o o o]
1638 // [o o I A o o o o o o . . o o o o]
1641 // copy elements up to new tail
1642 self.copy(self.tail
- 1, self.tail
, self.cap() - self.tail
);
1644 // copy last element into empty spot at bottom of buffer
1645 self.copy(self.cap() - 1, 0, 1);
1647 // move elements from idx-1 to end forward not including ^ element
1648 self.copy(0, 1, idx
- 1);
1653 (false, false, false) => {
1655 // discontiguous, insert closer to head, head section:
1658 // [o o o o A o o . . . . . . o o o]
1661 // [o o o o I A o o . . . . . o o o]
1664 self.copy(idx
+ 1, idx
, self.head
- idx
);
1670 // tail might've been changed so we need to recalculate
1671 let new_idx
= self.wrap_add(self.tail
, index
);
1673 self.buffer_write(new_idx
, value
);
1677 /// Removes and returns the element at `index` from the `VecDeque`.
1678 /// Whichever end is closer to the removal point will be moved to make
1679 /// room, and all the affected elements will be moved to new positions.
1680 /// Returns `None` if `index` is out of bounds.
1682 /// Element at index 0 is the front of the queue.
1687 /// use std::collections::VecDeque;
1689 /// let mut buf = VecDeque::new();
1690 /// buf.push_back(1);
1691 /// buf.push_back(2);
1692 /// buf.push_back(3);
1693 /// assert_eq!(buf, [1, 2, 3]);
1695 /// assert_eq!(buf.remove(1), Some(2));
1696 /// assert_eq!(buf, [1, 3]);
1698 #[stable(feature = "rust1", since = "1.0.0")]
1699 pub fn remove(&mut self, index
: usize) -> Option
<T
> {
1700 if self.is_empty() || self.len() <= index
{
1704 // There are three main cases:
1705 // Elements are contiguous
1706 // Elements are discontiguous and the removal is in the tail section
1707 // Elements are discontiguous and the removal is in the head section
1708 // - special case when elements are technically contiguous,
1709 // but self.head = 0
1711 // For each of those there are two more cases:
1712 // Insert is closer to tail
1713 // Insert is closer to head
1715 // Key: H - self.head
1717 // o - Valid element
1718 // x - Element marked for removal
1719 // R - Indicates element that is being removed
1720 // M - Indicates element was moved
1722 let idx
= self.wrap_add(self.tail
, index
);
1724 let elem
= unsafe { Some(self.buffer_read(idx)) }
;
1726 let distance_to_tail
= index
;
1727 let distance_to_head
= self.len() - index
;
1729 let contiguous
= self.is_contiguous();
1731 match (contiguous
, distance_to_tail
<= distance_to_head
, idx
>= self.tail
) {
1732 (true, true, _
) => {
1734 // contiguous, remove closer to tail:
1737 // [. . . o o x o o o o . . . . . .]
1740 // [. . . . o o o o o o . . . . . .]
1743 self.copy(self.tail
+ 1, self.tail
, index
);
1747 (true, false, _
) => {
1749 // contiguous, remove closer to head:
1752 // [. . . o o o o x o o . . . . . .]
1755 // [. . . o o o o o o . . . . . . .]
1758 self.copy(idx
, idx
+ 1, self.head
- idx
- 1);
1762 (false, true, true) => {
1764 // discontiguous, remove closer to tail, tail section:
1767 // [o o o o o o . . . . . o o x o o]
1770 // [o o o o o o . . . . . . o o o o]
1773 self.copy(self.tail
+ 1, self.tail
, index
);
1774 self.tail
= self.wrap_add(self.tail
, 1);
1777 (false, false, false) => {
1779 // discontiguous, remove closer to head, head section:
1782 // [o o o o x o o . . . . . . o o o]
1785 // [o o o o o o . . . . . . . o o o]
1788 self.copy(idx
, idx
+ 1, self.head
- idx
- 1);
1792 (false, false, true) => {
1794 // discontiguous, remove closer to head, tail section:
1797 // [o o o . . . . . . o o o o o x o]
1800 // [o o . . . . . . . o o o o o o o]
1803 // or quasi-discontiguous, remove next to head, tail section:
1806 // [. . . . . . . . . o o o o o x o]
1809 // [. . . . . . . . . o o o o o o .]
1812 // draw in elements in the tail section
1813 self.copy(idx
, idx
+ 1, self.cap() - idx
- 1);
1815 // Prevents underflow.
1817 // copy first element into empty spot
1818 self.copy(self.cap() - 1, 0, 1);
1820 // move elements in the head section backwards
1821 self.copy(0, 1, self.head
- 1);
1824 self.head
= self.wrap_sub(self.head
, 1);
1827 (false, true, false) => {
1829 // discontiguous, remove closer to tail, head section:
1832 // [o o x o o o o o o o . . . o o o]
1835 // [o o o o o o o o o o . . . . o o]
1838 // draw in elements up to idx
1839 self.copy(1, 0, idx
);
1841 // copy last element into empty spot
1842 self.copy(0, self.cap() - 1, 1);
1844 // move elements from tail to end forward, excluding the last one
1845 self.copy(self.tail
+ 1, self.tail
, self.cap() - self.tail
- 1);
1847 self.tail
= self.wrap_add(self.tail
, 1);
1855 /// Splits the `VecDeque` into two at the given index.
1857 /// Returns a newly allocated `VecDeque`. `self` contains elements `[0, at)`,
1858 /// and the returned `VecDeque` contains elements `[at, len)`.
1860 /// Note that the capacity of `self` does not change.
1862 /// Element at index 0 is the front of the queue.
1866 /// Panics if `at > len`.
1871 /// use std::collections::VecDeque;
1873 /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect();
1874 /// let buf2 = buf.split_off(1);
1875 /// assert_eq!(buf, [1]);
1876 /// assert_eq!(buf2, [2, 3]);
1879 #[stable(feature = "split_off", since = "1.4.0")]
1880 pub fn split_off(&mut self, at
: usize) -> Self {
1881 let len
= self.len();
1882 assert
!(at
<= len
, "`at` out of bounds");
1884 let other_len
= len
- at
;
1885 let mut other
= VecDeque
::with_capacity(other_len
);
1888 let (first_half
, second_half
) = self.as_slices();
1890 let first_len
= first_half
.len();
1891 let second_len
= second_half
.len();
1893 // `at` lies in the first half.
1894 let amount_in_first
= first_len
- at
;
1896 ptr
::copy_nonoverlapping(first_half
.as_ptr().add(at
), other
.ptr(), amount_in_first
);
1898 // just take all of the second half.
1899 ptr
::copy_nonoverlapping(
1900 second_half
.as_ptr(),
1901 other
.ptr().add(amount_in_first
),
1905 // `at` lies in the second half, need to factor in the elements we skipped
1906 // in the first half.
1907 let offset
= at
- first_len
;
1908 let amount_in_second
= second_len
- offset
;
1909 ptr
::copy_nonoverlapping(
1910 second_half
.as_ptr().add(offset
),
1917 // Cleanup where the ends of the buffers are
1918 self.head
= self.wrap_sub(self.head
, other_len
);
1919 other
.head
= other
.wrap_index(other_len
);
1924 /// Moves all the elements of `other` into `self`, leaving `other` empty.
1928 /// Panics if the new number of elements in self overflows a `usize`.
1933 /// use std::collections::VecDeque;
1935 /// let mut buf: VecDeque<_> = vec![1, 2].into_iter().collect();
1936 /// let mut buf2: VecDeque<_> = vec![3, 4].into_iter().collect();
1937 /// buf.append(&mut buf2);
1938 /// assert_eq!(buf, [1, 2, 3, 4]);
1939 /// assert_eq!(buf2, []);
1942 #[stable(feature = "append", since = "1.4.0")]
1943 pub fn append(&mut self, other
: &mut Self) {
1945 self.extend(other
.drain(..));
1948 /// Retains only the elements specified by the predicate.
1950 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1951 /// This method operates in place, visiting each element exactly once in the
1952 /// original order, and preserves the order of the retained elements.
1957 /// use std::collections::VecDeque;
1959 /// let mut buf = VecDeque::new();
1960 /// buf.extend(1..5);
1961 /// buf.retain(|&x| x % 2 == 0);
1962 /// assert_eq!(buf, [2, 4]);
1965 /// The exact order may be useful for tracking external state, like an index.
1968 /// use std::collections::VecDeque;
1970 /// let mut buf = VecDeque::new();
1971 /// buf.extend(1..6);
1973 /// let keep = [false, true, true, false, true];
1975 /// buf.retain(|_| (keep[i], i += 1).0);
1976 /// assert_eq!(buf, [2, 3, 5]);
1978 #[stable(feature = "vec_deque_retain", since = "1.4.0")]
1979 pub fn retain
<F
>(&mut self, mut f
: F
)
1981 F
: FnMut(&T
) -> bool
,
1983 let len
= self.len();
1989 self.swap(i
- del
, i
);
1993 self.truncate(len
- del
);
1997 // This may panic or abort
1999 fn grow_if_necessary(&mut self) {
2001 let old_cap
= self.cap();
2004 self.handle_capacity_increase(old_cap
);
2006 debug_assert
!(!self.is_full());
2010 /// Modifies the `VecDeque` in-place so that `len()` is equal to `new_len`,
2011 /// either by removing excess elements from the back or by appending
2012 /// elements generated by calling `generator` to the back.
2017 /// use std::collections::VecDeque;
2019 /// let mut buf = VecDeque::new();
2020 /// buf.push_back(5);
2021 /// buf.push_back(10);
2022 /// buf.push_back(15);
2023 /// assert_eq!(buf, [5, 10, 15]);
2025 /// buf.resize_with(5, Default::default);
2026 /// assert_eq!(buf, [5, 10, 15, 0, 0]);
2028 /// buf.resize_with(2, || unreachable!());
2029 /// assert_eq!(buf, [5, 10]);
2031 /// let mut state = 100;
2032 /// buf.resize_with(5, || { state += 1; state });
2033 /// assert_eq!(buf, [5, 10, 101, 102, 103]);
2035 #[stable(feature = "vec_resize_with", since = "1.33.0")]
2036 pub fn resize_with(&mut self, new_len
: usize, generator
: impl FnMut() -> T
) {
2037 let len
= self.len();
2040 self.extend(repeat_with(generator
).take(new_len
- len
))
2042 self.truncate(new_len
);
2046 /// Rotates the double-ended queue `mid` places to the left.
2049 /// - Rotates item `mid` into the first position.
2050 /// - Pops the first `mid` items and pushes them to the end.
2051 /// - Rotates `len() - mid` places to the right.
2055 /// If `mid` is greater than `len()`. Note that `mid == len()`
2056 /// does _not_ panic and is a no-op rotation.
2060 /// Takes `O(min(mid, len() - mid))` time and no extra space.
2065 /// use std::collections::VecDeque;
2067 /// let mut buf: VecDeque<_> = (0..10).collect();
2069 /// buf.rotate_left(3);
2070 /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);
2072 /// for i in 1..10 {
2073 /// assert_eq!(i * 3 % 10, buf[0]);
2074 /// buf.rotate_left(3);
2076 /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
2078 #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
2079 pub fn rotate_left(&mut self, mid
: usize) {
2080 assert
!(mid
<= self.len());
2081 let k
= self.len() - mid
;
2083 unsafe { self.rotate_left_inner(mid) }
2085 unsafe { self.rotate_right_inner(k) }
2089 /// Rotates the double-ended queue `k` places to the right.
2092 /// - Rotates the first item into position `k`.
2093 /// - Pops the last `k` items and pushes them to the front.
2094 /// - Rotates `len() - k` places to the left.
2098 /// If `k` is greater than `len()`. Note that `k == len()`
2099 /// does _not_ panic and is a no-op rotation.
2103 /// Takes `O(min(k, len() - k))` time and no extra space.
2108 /// use std::collections::VecDeque;
2110 /// let mut buf: VecDeque<_> = (0..10).collect();
2112 /// buf.rotate_right(3);
2113 /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);
2115 /// for i in 1..10 {
2116 /// assert_eq!(0, buf[i * 3 % 10]);
2117 /// buf.rotate_right(3);
2119 /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
2121 #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
2122 pub fn rotate_right(&mut self, k
: usize) {
2123 assert
!(k
<= self.len());
2124 let mid
= self.len() - k
;
2126 unsafe { self.rotate_right_inner(k) }
2128 unsafe { self.rotate_left_inner(mid) }
2132 // Safety: the following two methods require that the rotation amount
2133 // be less than half the length of the deque.
2135 // `wrap_copy` requires that `min(x, cap() - x) + copy_len <= cap()`,
2136 // but than `min` is never more than half the capacity, regardless of x,
2137 // so it's sound to call here because we're calling with something
2138 // less than half the length, which is never above half the capacity.
2140 unsafe fn rotate_left_inner(&mut self, mid
: usize) {
2141 debug_assert
!(mid
* 2 <= self.len());
2142 self.wrap_copy(self.head
, self.tail
, mid
);
2143 self.head
= self.wrap_add(self.head
, mid
);
2144 self.tail
= self.wrap_add(self.tail
, mid
);
2147 unsafe fn rotate_right_inner(&mut self, k
: usize) {
2148 debug_assert
!(k
* 2 <= self.len());
2149 self.head
= self.wrap_sub(self.head
, k
);
2150 self.tail
= self.wrap_sub(self.tail
, k
);
2151 self.wrap_copy(self.tail
, self.head
, k
);
2155 impl<T
: Clone
> VecDeque
<T
> {
2156 /// Modifies the `VecDeque` in-place so that `len()` is equal to new_len,
2157 /// either by removing excess elements from the back or by appending clones of `value`
2163 /// use std::collections::VecDeque;
2165 /// let mut buf = VecDeque::new();
2166 /// buf.push_back(5);
2167 /// buf.push_back(10);
2168 /// buf.push_back(15);
2169 /// assert_eq!(buf, [5, 10, 15]);
2171 /// buf.resize(2, 0);
2172 /// assert_eq!(buf, [5, 10]);
2174 /// buf.resize(5, 20);
2175 /// assert_eq!(buf, [5, 10, 20, 20, 20]);
2177 #[stable(feature = "deque_extras", since = "1.16.0")]
2178 pub fn resize(&mut self, new_len
: usize, value
: T
) {
2179 self.resize_with(new_len
, || value
.clone());
2183 /// Returns the index in the underlying buffer for a given logical element index.
2185 fn wrap_index(index
: usize, size
: usize) -> usize {
2186 // size is always a power of 2
2187 debug_assert
!(size
.is_power_of_two());
2191 /// Returns the two slices that cover the `VecDeque`'s valid range
2192 trait RingSlices
: Sized
{
2193 fn slice(self, from
: usize, to
: usize) -> Self;
2194 fn split_at(self, i
: usize) -> (Self, Self);
2196 fn ring_slices(buf
: Self, head
: usize, tail
: usize) -> (Self, Self) {
2197 let contiguous
= tail
<= head
;
2199 let (empty
, buf
) = buf
.split_at(0);
2200 (buf
.slice(tail
, head
), empty
)
2202 let (mid
, right
) = buf
.split_at(tail
);
2203 let (left
, _
) = mid
.split_at(head
);
2209 impl<T
> RingSlices
for &[T
] {
2210 fn slice(self, from
: usize, to
: usize) -> Self {
2213 fn split_at(self, i
: usize) -> (Self, Self) {
2218 impl<T
> RingSlices
for &mut [T
] {
2219 fn slice(self, from
: usize, to
: usize) -> Self {
2222 fn split_at(self, i
: usize) -> (Self, Self) {
2223 (*self).split_at_mut(i
)
2227 /// Calculate the number of elements left to be read in the buffer
2229 fn count(tail
: usize, head
: usize, size
: usize) -> usize {
2230 // size is always a power of 2
2231 (head
.wrapping_sub(tail
)) & (size
- 1)
2234 /// An iterator over the elements of a `VecDeque`.
2236 /// This `struct` is created by the [`iter`] method on [`VecDeque`]. See its
2237 /// documentation for more.
2239 /// [`iter`]: struct.VecDeque.html#method.iter
2240 /// [`VecDeque`]: struct.VecDeque.html
2241 #[stable(feature = "rust1", since = "1.0.0")]
2242 pub struct Iter
<'a
, T
: 'a
> {
2248 #[stable(feature = "collection_debug", since = "1.17.0")]
2249 impl<T
: fmt
::Debug
> fmt
::Debug
for Iter
<'_
, T
> {
2250 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2251 let (front
, back
) = RingSlices
::ring_slices(self.ring
, self.head
, self.tail
);
2252 f
.debug_tuple("Iter").field(&front
).field(&back
).finish()
2256 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2257 #[stable(feature = "rust1", since = "1.0.0")]
2258 impl<T
> Clone
for Iter
<'_
, T
> {
2259 fn clone(&self) -> Self {
2260 Iter { ring: self.ring, tail: self.tail, head: self.head }
2264 #[stable(feature = "rust1", since = "1.0.0")]
2265 impl<'a
, T
> Iterator
for Iter
<'a
, T
> {
2269 fn next(&mut self) -> Option
<&'a T
> {
2270 if self.tail
== self.head
{
2273 let tail
= self.tail
;
2274 self.tail
= wrap_index(self.tail
.wrapping_add(1), self.ring
.len());
2275 unsafe { Some(self.ring.get_unchecked(tail)) }
2279 fn size_hint(&self) -> (usize, Option
<usize>) {
2280 let len
= count(self.tail
, self.head
, self.ring
.len());
2284 fn fold
<Acc
, F
>(self, mut accum
: Acc
, mut f
: F
) -> Acc
2286 F
: FnMut(Acc
, Self::Item
) -> Acc
,
2288 let (front
, back
) = RingSlices
::ring_slices(self.ring
, self.head
, self.tail
);
2289 accum
= front
.iter().fold(accum
, &mut f
);
2290 back
.iter().fold(accum
, &mut f
)
2293 fn try_fold
<B
, F
, R
>(&mut self, init
: B
, mut f
: F
) -> R
2296 F
: FnMut(B
, Self::Item
) -> R
,
2299 let (mut iter
, final_res
);
2300 if self.tail
<= self.head
{
2301 // single slice self.ring[self.tail..self.head]
2302 iter
= self.ring
[self.tail
..self.head
].iter();
2303 final_res
= iter
.try_fold(init
, &mut f
);
2305 // two slices: self.ring[self.tail..], self.ring[..self.head]
2306 let (front
, back
) = self.ring
.split_at(self.tail
);
2307 let mut back_iter
= back
.iter();
2308 let res
= back_iter
.try_fold(init
, &mut f
);
2309 let len
= self.ring
.len();
2310 self.tail
= (self.ring
.len() - back_iter
.len()) & (len
- 1);
2311 iter
= front
[..self.head
].iter();
2312 final_res
= iter
.try_fold(res?
, &mut f
);
2314 self.tail
= self.head
- iter
.len();
2318 fn nth(&mut self, n
: usize) -> Option
<Self::Item
> {
2319 if n
>= count(self.tail
, self.head
, self.ring
.len()) {
2320 self.tail
= self.head
;
2323 self.tail
= wrap_index(self.tail
.wrapping_add(n
), self.ring
.len());
2329 fn last(mut self) -> Option
<&'a T
> {
2334 #[stable(feature = "rust1", since = "1.0.0")]
2335 impl<'a
, T
> DoubleEndedIterator
for Iter
<'a
, T
> {
2337 fn next_back(&mut self) -> Option
<&'a T
> {
2338 if self.tail
== self.head
{
2341 self.head
= wrap_index(self.head
.wrapping_sub(1), self.ring
.len());
2342 unsafe { Some(self.ring.get_unchecked(self.head)) }
2345 fn rfold
<Acc
, F
>(self, mut accum
: Acc
, mut f
: F
) -> Acc
2347 F
: FnMut(Acc
, Self::Item
) -> Acc
,
2349 let (front
, back
) = RingSlices
::ring_slices(self.ring
, self.head
, self.tail
);
2350 accum
= back
.iter().rfold(accum
, &mut f
);
2351 front
.iter().rfold(accum
, &mut f
)
2354 fn try_rfold
<B
, F
, R
>(&mut self, init
: B
, mut f
: F
) -> R
2357 F
: FnMut(B
, Self::Item
) -> R
,
2360 let (mut iter
, final_res
);
2361 if self.tail
<= self.head
{
2362 // single slice self.ring[self.tail..self.head]
2363 iter
= self.ring
[self.tail
..self.head
].iter();
2364 final_res
= iter
.try_rfold(init
, &mut f
);
2366 // two slices: self.ring[self.tail..], self.ring[..self.head]
2367 let (front
, back
) = self.ring
.split_at(self.tail
);
2368 let mut front_iter
= front
[..self.head
].iter();
2369 let res
= front_iter
.try_rfold(init
, &mut f
);
2370 self.head
= front_iter
.len();
2372 final_res
= iter
.try_rfold(res?
, &mut f
);
2374 self.head
= self.tail
+ iter
.len();
2379 #[stable(feature = "rust1", since = "1.0.0")]
2380 impl<T
> ExactSizeIterator
for Iter
<'_
, T
> {
2381 fn is_empty(&self) -> bool
{
2382 self.head
== self.tail
2386 #[stable(feature = "fused", since = "1.26.0")]
2387 impl<T
> FusedIterator
for Iter
<'_
, T
> {}
2389 /// A mutable iterator over the elements of a `VecDeque`.
2391 /// This `struct` is created by the [`iter_mut`] method on [`VecDeque`]. See its
2392 /// documentation for more.
2394 /// [`iter_mut`]: struct.VecDeque.html#method.iter_mut
2395 /// [`VecDeque`]: struct.VecDeque.html
2396 #[stable(feature = "rust1", since = "1.0.0")]
2397 pub struct IterMut
<'a
, T
: 'a
> {
2403 #[stable(feature = "collection_debug", since = "1.17.0")]
2404 impl<T
: fmt
::Debug
> fmt
::Debug
for IterMut
<'_
, T
> {
2405 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2406 let (front
, back
) = RingSlices
::ring_slices(&*self.ring
, self.head
, self.tail
);
2407 f
.debug_tuple("IterMut").field(&front
).field(&back
).finish()
2411 #[stable(feature = "rust1", since = "1.0.0")]
2412 impl<'a
, T
> Iterator
for IterMut
<'a
, T
> {
2413 type Item
= &'a
mut T
;
2416 fn next(&mut self) -> Option
<&'a
mut T
> {
2417 if self.tail
== self.head
{
2420 let tail
= self.tail
;
2421 self.tail
= wrap_index(self.tail
.wrapping_add(1), self.ring
.len());
2424 let elem
= self.ring
.get_unchecked_mut(tail
);
2425 Some(&mut *(elem
as *mut _
))
2430 fn size_hint(&self) -> (usize, Option
<usize>) {
2431 let len
= count(self.tail
, self.head
, self.ring
.len());
2435 fn fold
<Acc
, F
>(self, mut accum
: Acc
, mut f
: F
) -> Acc
2437 F
: FnMut(Acc
, Self::Item
) -> Acc
,
2439 let (front
, back
) = RingSlices
::ring_slices(self.ring
, self.head
, self.tail
);
2440 accum
= front
.iter_mut().fold(accum
, &mut f
);
2441 back
.iter_mut().fold(accum
, &mut f
)
2444 fn nth(&mut self, n
: usize) -> Option
<Self::Item
> {
2445 if n
>= count(self.tail
, self.head
, self.ring
.len()) {
2446 self.tail
= self.head
;
2449 self.tail
= wrap_index(self.tail
.wrapping_add(n
), self.ring
.len());
2455 fn last(mut self) -> Option
<&'a
mut T
> {
2460 #[stable(feature = "rust1", since = "1.0.0")]
2461 impl<'a
, T
> DoubleEndedIterator
for IterMut
<'a
, T
> {
2463 fn next_back(&mut self) -> Option
<&'a
mut T
> {
2464 if self.tail
== self.head
{
2467 self.head
= wrap_index(self.head
.wrapping_sub(1), self.ring
.len());
2470 let elem
= self.ring
.get_unchecked_mut(self.head
);
2471 Some(&mut *(elem
as *mut _
))
2475 fn rfold
<Acc
, F
>(self, mut accum
: Acc
, mut f
: F
) -> Acc
2477 F
: FnMut(Acc
, Self::Item
) -> Acc
,
2479 let (front
, back
) = RingSlices
::ring_slices(self.ring
, self.head
, self.tail
);
2480 accum
= back
.iter_mut().rfold(accum
, &mut f
);
2481 front
.iter_mut().rfold(accum
, &mut f
)
2485 #[stable(feature = "rust1", since = "1.0.0")]
2486 impl<T
> ExactSizeIterator
for IterMut
<'_
, T
> {
2487 fn is_empty(&self) -> bool
{
2488 self.head
== self.tail
2492 #[stable(feature = "fused", since = "1.26.0")]
2493 impl<T
> FusedIterator
for IterMut
<'_
, T
> {}
2495 /// An owning iterator over the elements of a `VecDeque`.
2497 /// This `struct` is created by the [`into_iter`] method on [`VecDeque`]
2498 /// (provided by the `IntoIterator` trait). See its documentation for more.
2500 /// [`into_iter`]: struct.VecDeque.html#method.into_iter
2501 /// [`VecDeque`]: struct.VecDeque.html
2503 #[stable(feature = "rust1", since = "1.0.0")]
2504 pub struct IntoIter
<T
> {
2508 #[stable(feature = "collection_debug", since = "1.17.0")]
2509 impl<T
: fmt
::Debug
> fmt
::Debug
for IntoIter
<T
> {
2510 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2511 f
.debug_tuple("IntoIter").field(&self.inner
).finish()
2515 #[stable(feature = "rust1", since = "1.0.0")]
2516 impl<T
> Iterator
for IntoIter
<T
> {
2520 fn next(&mut self) -> Option
<T
> {
2521 self.inner
.pop_front()
2525 fn size_hint(&self) -> (usize, Option
<usize>) {
2526 let len
= self.inner
.len();
2531 #[stable(feature = "rust1", since = "1.0.0")]
2532 impl<T
> DoubleEndedIterator
for IntoIter
<T
> {
2534 fn next_back(&mut self) -> Option
<T
> {
2535 self.inner
.pop_back()
2539 #[stable(feature = "rust1", since = "1.0.0")]
2540 impl<T
> ExactSizeIterator
for IntoIter
<T
> {
2541 fn is_empty(&self) -> bool
{
2542 self.inner
.is_empty()
2546 #[stable(feature = "fused", since = "1.26.0")]
2547 impl<T
> FusedIterator
for IntoIter
<T
> {}
2549 #[stable(feature = "rust1", since = "1.0.0")]
2550 impl<A
: PartialEq
> PartialEq
for VecDeque
<A
> {
2551 fn eq(&self, other
: &VecDeque
<A
>) -> bool
{
2552 if self.len() != other
.len() {
2555 let (sa
, sb
) = self.as_slices();
2556 let (oa
, ob
) = other
.as_slices();
2557 if sa
.len() == oa
.len() {
2558 sa
== oa
&& sb
== ob
2559 } else if sa
.len() < oa
.len() {
2560 // Always divisible in three sections, for example:
2561 // self: [a b c|d e f]
2562 // other: [0 1 2 3|4 5]
2563 // front = 3, mid = 1,
2564 // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
2565 let front
= sa
.len();
2566 let mid
= oa
.len() - front
;
2568 let (oa_front
, oa_mid
) = oa
.split_at(front
);
2569 let (sb_mid
, sb_back
) = sb
.split_at(mid
);
2570 debug_assert_eq
!(sa
.len(), oa_front
.len());
2571 debug_assert_eq
!(sb_mid
.len(), oa_mid
.len());
2572 debug_assert_eq
!(sb_back
.len(), ob
.len());
2573 sa
== oa_front
&& sb_mid
== oa_mid
&& sb_back
== ob
2575 let front
= oa
.len();
2576 let mid
= sa
.len() - front
;
2578 let (sa_front
, sa_mid
) = sa
.split_at(front
);
2579 let (ob_mid
, ob_back
) = ob
.split_at(mid
);
2580 debug_assert_eq
!(sa_front
.len(), oa
.len());
2581 debug_assert_eq
!(sa_mid
.len(), ob_mid
.len());
2582 debug_assert_eq
!(sb
.len(), ob_back
.len());
2583 sa_front
== oa
&& sa_mid
== ob_mid
&& sb
== ob_back
2588 #[stable(feature = "rust1", since = "1.0.0")]
2589 impl<A
: Eq
> Eq
for VecDeque
<A
> {}
2591 macro_rules
! __impl_slice_eq1
{
2592 ([$
($vars
:tt
)*] $lhs
:ty
, $rhs
:ty
, $
($constraints
:tt
)*) => {
2593 #[stable(feature = "vec_deque_partial_eq_slice", since = "1.17.0")]
2594 impl<A
, B
, $
($vars
)*> PartialEq
<$rhs
> for $lhs
2599 fn eq(&self, other
: &$rhs
) -> bool
{
2600 if self.len() != other
.len() {
2603 let (sa
, sb
) = self.as_slices();
2604 let (oa
, ob
) = other
[..].split_at(sa
.len());
2605 sa
== oa
&& sb
== ob
2611 __impl_slice_eq1
! { [] VecDeque<A>, Vec<B>, }
2612 __impl_slice_eq1
! { [] VecDeque<A>, &[B], }
2613 __impl_slice_eq1
! { [] VecDeque<A>, &mut [B], }
2614 __impl_slice_eq1
! { [const N: usize] VecDeque<A>, [B; N], [B; N]: LengthAtMost32 }
2615 __impl_slice_eq1
! { [const N: usize] VecDeque<A>, &[B; N], [B; N]: LengthAtMost32 }
2616 __impl_slice_eq1
! { [const N: usize] VecDeque<A>, &mut [B; N], [B; N]: LengthAtMost32 }
2618 #[stable(feature = "rust1", since = "1.0.0")]
2619 impl<A
: PartialOrd
> PartialOrd
for VecDeque
<A
> {
2620 fn partial_cmp(&self, other
: &VecDeque
<A
>) -> Option
<Ordering
> {
2621 self.iter().partial_cmp(other
.iter())
2625 #[stable(feature = "rust1", since = "1.0.0")]
2626 impl<A
: Ord
> Ord
for VecDeque
<A
> {
2628 fn cmp(&self, other
: &VecDeque
<A
>) -> Ordering
{
2629 self.iter().cmp(other
.iter())
2633 #[stable(feature = "rust1", since = "1.0.0")]
2634 impl<A
: Hash
> Hash
for VecDeque
<A
> {
2635 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
2636 self.len().hash(state
);
2637 let (a
, b
) = self.as_slices();
2638 Hash
::hash_slice(a
, state
);
2639 Hash
::hash_slice(b
, state
);
2643 #[stable(feature = "rust1", since = "1.0.0")]
2644 impl<A
> Index
<usize> for VecDeque
<A
> {
2648 fn index(&self, index
: usize) -> &A
{
2649 self.get(index
).expect("Out of bounds access")
2653 #[stable(feature = "rust1", since = "1.0.0")]
2654 impl<A
> IndexMut
<usize> for VecDeque
<A
> {
2656 fn index_mut(&mut self, index
: usize) -> &mut A
{
2657 self.get_mut(index
).expect("Out of bounds access")
2661 #[stable(feature = "rust1", since = "1.0.0")]
2662 impl<A
> FromIterator
<A
> for VecDeque
<A
> {
2663 fn from_iter
<T
: IntoIterator
<Item
= A
>>(iter
: T
) -> VecDeque
<A
> {
2664 let iterator
= iter
.into_iter();
2665 let (lower
, _
) = iterator
.size_hint();
2666 let mut deq
= VecDeque
::with_capacity(lower
);
2667 deq
.extend(iterator
);
2672 #[stable(feature = "rust1", since = "1.0.0")]
2673 impl<T
> IntoIterator
for VecDeque
<T
> {
2675 type IntoIter
= IntoIter
<T
>;
2677 /// Consumes the `VecDeque` into a front-to-back iterator yielding elements by
2679 fn into_iter(self) -> IntoIter
<T
> {
2680 IntoIter { inner: self }
2684 #[stable(feature = "rust1", since = "1.0.0")]
2685 impl<'a
, T
> IntoIterator
for &'a VecDeque
<T
> {
2687 type IntoIter
= Iter
<'a
, T
>;
2689 fn into_iter(self) -> Iter
<'a
, T
> {
2694 #[stable(feature = "rust1", since = "1.0.0")]
2695 impl<'a
, T
> IntoIterator
for &'a
mut VecDeque
<T
> {
2696 type Item
= &'a
mut T
;
2697 type IntoIter
= IterMut
<'a
, T
>;
2699 fn into_iter(self) -> IterMut
<'a
, T
> {
2704 #[stable(feature = "rust1", since = "1.0.0")]
2705 impl<A
> Extend
<A
> for VecDeque
<A
> {
2706 fn extend
<T
: IntoIterator
<Item
= A
>>(&mut self, iter
: T
) {
2707 // This function should be the moral equivalent of:
2709 // for item in iter.into_iter() {
2710 // self.push_back(item);
2712 let mut iter
= iter
.into_iter();
2713 while let Some(element
) = iter
.next() {
2714 if self.len() == self.capacity() {
2715 let (lower
, _
) = iter
.size_hint();
2716 self.reserve(lower
.saturating_add(1));
2719 let head
= self.head
;
2720 self.head
= self.wrap_add(self.head
, 1);
2722 self.buffer_write(head
, element
);
2728 #[stable(feature = "extend_ref", since = "1.2.0")]
2729 impl<'a
, T
: 'a
+ Copy
> Extend
<&'a T
> for VecDeque
<T
> {
2730 fn extend
<I
: IntoIterator
<Item
= &'a T
>>(&mut self, iter
: I
) {
2731 self.extend(iter
.into_iter().cloned());
2735 #[stable(feature = "rust1", since = "1.0.0")]
2736 impl<T
: fmt
::Debug
> fmt
::Debug
for VecDeque
<T
> {
2737 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2738 f
.debug_list().entries(self).finish()
2742 #[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
2743 impl<T
> From
<Vec
<T
>> for VecDeque
<T
> {
2744 /// Turn a [`Vec<T>`] into a [`VecDeque<T>`].
2746 /// [`Vec<T>`]: crate::vec::Vec
2747 /// [`VecDeque<T>`]: crate::collections::VecDeque
2749 /// This avoids reallocating where possible, but the conditions for that are
2750 /// strict, and subject to change, and so shouldn't be relied upon unless the
2751 /// `Vec<T>` came from `From<VecDeque<T>>` and hasn't been reallocated.
2752 fn from(mut other
: Vec
<T
>) -> Self {
2754 let other_buf
= other
.as_mut_ptr();
2755 let mut buf
= RawVec
::from_raw_parts(other_buf
, other
.capacity());
2756 let len
= other
.len();
2759 // We need to extend the buf if it's not a power of two, too small
2760 // or doesn't have at least one free space
2761 if !buf
.capacity().is_power_of_two()
2762 || (buf
.capacity() < (MINIMUM_CAPACITY
+ 1))
2763 || (buf
.capacity() == len
)
2765 let cap
= cmp
::max(buf
.capacity() + 1, MINIMUM_CAPACITY
+ 1).next_power_of_two();
2766 buf
.reserve_exact(len
, cap
- len
);
2769 VecDeque { tail: 0, head: len, buf }
2774 #[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
2775 impl<T
> From
<VecDeque
<T
>> for Vec
<T
> {
2776 /// Turn a [`VecDeque<T>`] into a [`Vec<T>`].
2778 /// [`Vec<T>`]: crate::vec::Vec
2779 /// [`VecDeque<T>`]: crate::collections::VecDeque
2781 /// This never needs to re-allocate, but does need to do O(n) data movement if
2782 /// the circular buffer doesn't happen to be at the beginning of the allocation.
2787 /// use std::collections::VecDeque;
2789 /// // This one is O(1).
2790 /// let deque: VecDeque<_> = (1..5).collect();
2791 /// let ptr = deque.as_slices().0.as_ptr();
2792 /// let vec = Vec::from(deque);
2793 /// assert_eq!(vec, [1, 2, 3, 4]);
2794 /// assert_eq!(vec.as_ptr(), ptr);
2796 /// // This one needs data rearranging.
2797 /// let mut deque: VecDeque<_> = (1..5).collect();
2798 /// deque.push_front(9);
2799 /// deque.push_front(8);
2800 /// let ptr = deque.as_slices().1.as_ptr();
2801 /// let vec = Vec::from(deque);
2802 /// assert_eq!(vec, [8, 9, 1, 2, 3, 4]);
2803 /// assert_eq!(vec.as_ptr(), ptr);
2805 fn from(other
: VecDeque
<T
>) -> Self {
2807 let buf
= other
.buf
.ptr();
2808 let len
= other
.len();
2809 let tail
= other
.tail
;
2810 let head
= other
.head
;
2811 let cap
= other
.cap();
2813 // Need to move the ring to the front of the buffer, as vec will expect this.
2814 if other
.is_contiguous() {
2815 ptr
::copy(buf
.add(tail
), buf
, len
);
2817 if (tail
- head
) >= cmp
::min(cap
- tail
, head
) {
2818 // There is enough free space in the centre for the shortest block so we can
2819 // do this in at most three copy moves.
2820 if (cap
- tail
) > head
{
2821 // right hand block is the long one; move that enough for the left
2822 ptr
::copy(buf
.add(tail
), buf
.add(tail
- head
), cap
- tail
);
2823 // copy left in the end
2824 ptr
::copy(buf
, buf
.add(cap
- head
), head
);
2825 // shift the new thing to the start
2826 ptr
::copy(buf
.add(tail
- head
), buf
, len
);
2828 // left hand block is the long one, we can do it in two!
2829 ptr
::copy(buf
, buf
.add(cap
- tail
), head
);
2830 ptr
::copy(buf
.add(tail
), buf
, cap
- tail
);
2833 // Need to use N swaps to move the ring
2834 // We can use the space at the end of the ring as a temp store
2836 let mut left_edge
: usize = 0;
2837 let mut right_edge
: usize = tail
;
2839 // The general problem looks like this
2840 // GHIJKLM...ABCDEF - before any swaps
2841 // ABCDEFM...GHIJKL - after 1 pass of swaps
2842 // ABCDEFGHIJM...KL - swap until the left edge reaches the temp store
2843 // - then restart the algorithm with a new (smaller) store
2844 // Sometimes the temp store is reached when the right edge is at the end
2845 // of the buffer - this means we've hit the right order with fewer swaps!
2848 // ABCDEF.. - after four only swaps we've finished
2850 while left_edge
< len
&& right_edge
!= cap
{
2851 let mut right_offset
= 0;
2852 for i
in left_edge
..right_edge
{
2853 right_offset
= (i
- left_edge
) % (cap
- right_edge
);
2854 let src
: isize = (right_edge
+ right_offset
) as isize;
2855 ptr
::swap(buf
.add(i
), buf
.offset(src
));
2857 let n_ops
= right_edge
- left_edge
;
2859 right_edge
+= right_offset
+ 1;
2863 let out
= Vec
::from_raw_parts(buf
, len
, cap
);