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