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