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