projects/linux·blob f24767ca · refs

3609 lines · 123.6 KiB

1// SPDX-License-Identifier: Apache-2.0 OR MIT
2
3//! A contiguous growable array type with heap-allocated contents, written
4//! `Vec<T>`.
5//!
6//! Vectors have *O*(1) indexing, amortized *O*(1) push (to the end) and
7//! *O*(1) pop (from the end).
8//!
9//! Vectors ensure they never allocate more than `isize::MAX` bytes.
10//!
11//! # Examples
12//!
13//! You can explicitly create a [`Vec`] with [`Vec::new`]:
14//!
15//! ```
16//! let v: Vec<i32> = Vec::new();
17//! ```
18//!
19//! ...or by using the [`vec!`] macro:
20//!
21//! ```
22//! let v: Vec<i32> = vec![];
23//!
24//! let v = vec![1, 2, 3, 4, 5];
25//!
26//! let v = vec![0; 10]; // ten zeroes
27//! ```
28//!
29//! You can [`push`] values onto the end of a vector (which will grow the vector
30//! as needed):
31//!
32//! ```
33//! let mut v = vec![1, 2];
34//!
35//! v.push(3);
36//! ```
37//!
38//! Popping values works in much the same way:
39//!
40//! ```
41//! let mut v = vec![1, 2];
42//!
43//! let two = v.pop();
44//! ```
45//!
46//! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits):
47//!
48//! ```
49//! let mut v = vec![1, 2, 3];
50//! let three = v[2];
51//! v[1] = v[1] + 5;
52//! ```
53//!
54//! [`push`]: Vec::push
55
56#![stable(feature = "rust1", since = "1.0.0")]
57
58#[cfg(not(no_global_oom_handling))]
59use core::cmp;
60use core::cmp::Ordering;
61use core::convert::TryFrom;
62use core::fmt;
63use core::hash::{Hash, Hasher};
64use core::intrinsics::assume;
65use core::iter;
66#[cfg(not(no_global_oom_handling))]
67use core::iter::FromIterator;
68use core::marker::PhantomData;
69use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties};
70use core::ops::{self, Index, IndexMut, Range, RangeBounds};
71use core::ptr::{self, NonNull};
72use core::slice::{self, SliceIndex};
73
74use crate::alloc::{Allocator, Global};
75#[cfg(not(no_borrow))]
76use crate::borrow::{Cow, ToOwned};
77use crate::boxed::Box;
78use crate::collections::{TryReserveError, TryReserveErrorKind};
79use crate::raw_vec::RawVec;
80
81#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
82pub use self::drain_filter::DrainFilter;
83
84mod drain_filter;
85
86#[cfg(not(no_global_oom_handling))]
87#[stable(feature = "vec_splice", since = "1.21.0")]
88pub use self::splice::Splice;
89
90#[cfg(not(no_global_oom_handling))]
91mod splice;
92
93#[stable(feature = "drain", since = "1.6.0")]
94pub use self::drain::Drain;
95
96mod drain;
97
98#[cfg(not(no_borrow))]
99#[cfg(not(no_global_oom_handling))]
100mod cow;
101
102#[cfg(not(no_global_oom_handling))]
103pub(crate) use self::in_place_collect::AsVecIntoIter;
104#[stable(feature = "rust1", since = "1.0.0")]
105pub use self::into_iter::IntoIter;
106
107mod into_iter;
108
109#[cfg(not(no_global_oom_handling))]
110use self::is_zero::IsZero;
111
112mod is_zero;
113
114#[cfg(not(no_global_oom_handling))]
115mod in_place_collect;
116
117mod partial_eq;
118
119#[cfg(not(no_global_oom_handling))]
120use self::spec_from_elem::SpecFromElem;
121
122#[cfg(not(no_global_oom_handling))]
123mod spec_from_elem;
124
125use self::set_len_on_drop::SetLenOnDrop;
126
127mod set_len_on_drop;
128
129#[cfg(not(no_global_oom_handling))]
130use self::in_place_drop::{InPlaceDrop, InPlaceDstBufDrop};
131
132#[cfg(not(no_global_oom_handling))]
133mod in_place_drop;
134
135#[cfg(not(no_global_oom_handling))]
136use self::spec_from_iter_nested::SpecFromIterNested;
137
138#[cfg(not(no_global_oom_handling))]
139mod spec_from_iter_nested;
140
141#[cfg(not(no_global_oom_handling))]
142use self::spec_from_iter::SpecFromIter;
143
144#[cfg(not(no_global_oom_handling))]
145mod spec_from_iter;
146
147#[cfg(not(no_global_oom_handling))]
148use self::spec_extend::SpecExtend;
149
150use self::spec_extend::TrySpecExtend;
151
152mod spec_extend;
153
154/// A contiguous growable array type, written as `Vec<T>`, short for 'vector'.
155///
156/// # Examples
157///
158/// ```
159/// let mut vec = Vec::new();
160/// vec.push(1);
161/// vec.push(2);
162///
163/// assert_eq!(vec.len(), 2);
164/// assert_eq!(vec[0], 1);
165///
166/// assert_eq!(vec.pop(), Some(2));
167/// assert_eq!(vec.len(), 1);
168///
169/// vec[0] = 7;
170/// assert_eq!(vec[0], 7);
171///
172/// vec.extend([1, 2, 3]);
173///
174/// for x in &vec {
175/// println!("{x}");
176/// }
177/// assert_eq!(vec, [7, 1, 2, 3]);
178/// ```
179///
180/// The [`vec!`] macro is provided for convenient initialization:
181///
182/// ```
183/// let mut vec1 = vec![1, 2, 3];
184/// vec1.push(4);
185/// let vec2 = Vec::from([1, 2, 3, 4]);
186/// assert_eq!(vec1, vec2);
187/// ```
188///
189/// It can also initialize each element of a `Vec<T>` with a given value.
190/// This may be more efficient than performing allocation and initialization
191/// in separate steps, especially when initializing a vector of zeros:
192///
193/// ```
194/// let vec = vec![0; 5];
195/// assert_eq!(vec, [0, 0, 0, 0, 0]);
196///
197/// // The following is equivalent, but potentially slower:
198/// let mut vec = Vec::with_capacity(5);
199/// vec.resize(5, 0);
200/// assert_eq!(vec, [0, 0, 0, 0, 0]);
201/// ```
202///
203/// For more information, see
204/// [Capacity and Reallocation](#capacity-and-reallocation).
205///
206/// Use a `Vec<T>` as an efficient stack:
207///
208/// ```
209/// let mut stack = Vec::new();
210///
211/// stack.push(1);
212/// stack.push(2);
213/// stack.push(3);
214///
215/// while let Some(top) = stack.pop() {
216/// // Prints 3, 2, 1
217/// println!("{top}");
218/// }
219/// ```
220///
221/// # Indexing
222///
223/// The `Vec` type allows to access values by index, because it implements the
224/// [`Index`] trait. An example will be more explicit:
225///
226/// ```
227/// let v = vec![0, 2, 4, 6];
228/// println!("{}", v[1]); // it will display '2'
229/// ```
230///
231/// However be careful: if you try to access an index which isn't in the `Vec`,
232/// your software will panic! You cannot do this:
233///
234/// ```should_panic
235/// let v = vec![0, 2, 4, 6];
236/// println!("{}", v[6]); // it will panic!
237/// ```
238///
239/// Use [`get`] and [`get_mut`] if you want to check whether the index is in
240/// the `Vec`.
241///
242/// # Slicing
243///
244/// A `Vec` can be mutable. On the other hand, slices are read-only objects.
245/// To get a [slice][prim@slice], use [`&`]. Example:
246///
247/// ```
248/// fn read_slice(slice: &[usize]) {
249/// // ...
250/// }
251///
252/// let v = vec![0, 1];
253/// read_slice(&v);
254///
255/// // ... and that's all!
256/// // you can also do it like this:
257/// let u: &[usize] = &v;
258/// // or like this:
259/// let u: &[_] = &v;
260/// ```
261///
262/// In Rust, it's more common to pass slices as arguments rather than vectors
263/// when you just want to provide read access. The same goes for [`String`] and
264/// [`&str`].
265///
266/// # Capacity and reallocation
267///
268/// The capacity of a vector is the amount of space allocated for any future
269/// elements that will be added onto the vector. This is not to be confused with
270/// the *length* of a vector, which specifies the number of actual elements
271/// within the vector. If a vector's length exceeds its capacity, its capacity
272/// will automatically be increased, but its elements will have to be
273/// reallocated.
274///
275/// For example, a vector with capacity 10 and length 0 would be an empty vector
276/// with space for 10 more elements. Pushing 10 or fewer elements onto the
277/// vector will not change its capacity or cause reallocation to occur. However,
278/// if the vector's length is increased to 11, it will have to reallocate, which
279/// can be slow. For this reason, it is recommended to use [`Vec::with_capacity`]
280/// whenever possible to specify how big the vector is expected to get.
281///
282/// # Guarantees
283///
284/// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees
285/// about its design. This ensures that it's as low-overhead as possible in
286/// the general case, and can be correctly manipulated in primitive ways
287/// by unsafe code. Note that these guarantees refer to an unqualified `Vec<T>`.
288/// If additional type parameters are added (e.g., to support custom allocators),
289/// overriding their defaults may change the behavior.
290///
291/// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length)
292/// triplet. No more, no less. The order of these fields is completely
293/// unspecified, and you should use the appropriate methods to modify these.
294/// The pointer will never be null, so this type is null-pointer-optimized.
295///
296/// However, the pointer might not actually point to allocated memory. In particular,
297/// if you construct a `Vec` with capacity 0 via [`Vec::new`], [`vec![]`][`vec!`],
298/// [`Vec::with_capacity(0)`][`Vec::with_capacity`], or by calling [`shrink_to_fit`]
299/// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized
300/// types inside a `Vec`, it will not allocate space for them. *Note that in this case
301/// the `Vec` might not report a [`capacity`] of 0*. `Vec` will allocate if and only
302/// if <code>[mem::size_of::\<T>]\() * [capacity]\() > 0</code>. In general, `Vec`'s allocation
303/// details are very subtle --- if you intend to allocate memory using a `Vec`
304/// and use it for something else (either to pass to unsafe code, or to build your
305/// own memory-backed collection), be sure to deallocate this memory by using
306/// `from_raw_parts` to recover the `Vec` and then dropping it.
307///
308/// If a `Vec` *has* allocated memory, then the memory it points to is on the heap
309/// (as defined by the allocator Rust is configured to use by default), and its
310/// pointer points to [`len`] initialized, contiguous elements in order (what
311/// you would see if you coerced it to a slice), followed by <code>[capacity] - [len]</code>
312/// logically uninitialized, contiguous elements.
313///
314/// A vector containing the elements `'a'` and `'b'` with capacity 4 can be
315/// visualized as below. The top part is the `Vec` struct, it contains a
316/// pointer to the head of the allocation in the heap, length and capacity.
317/// The bottom part is the allocation on the heap, a contiguous memory block.
318///
319/// ```text
320/// ptr len capacity
321/// +--------+--------+--------+
322/// | 0x0123 | 2 | 4 |
323/// +--------+--------+--------+
324/// |
325/// v
326/// Heap +--------+--------+--------+--------+
327/// | 'a' | 'b' | uninit | uninit |
328/// +--------+--------+--------+--------+
329/// ```
330///
331/// - **uninit** represents memory that is not initialized, see [`MaybeUninit`].
332/// - Note: the ABI is not stable and `Vec` makes no guarantees about its memory
333/// layout (including the order of fields).
334///
335/// `Vec` will never perform a "small optimization" where elements are actually
336/// stored on the stack for two reasons:
337///
338/// * It would make it more difficult for unsafe code to correctly manipulate
339/// a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were
340/// only moved, and it would be more difficult to determine if a `Vec` had
341/// actually allocated memory.
342///
343/// * It would penalize the general case, incurring an additional branch
344/// on every access.
345///
346/// `Vec` will never automatically shrink itself, even if completely empty. This
347/// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec`
348/// and then filling it back up to the same [`len`] should incur no calls to
349/// the allocator. If you wish to free up unused memory, use
350/// [`shrink_to_fit`] or [`shrink_to`].
351///
352/// [`push`] and [`insert`] will never (re)allocate if the reported capacity is
353/// sufficient. [`push`] and [`insert`] *will* (re)allocate if
354/// <code>[len] == [capacity]</code>. That is, the reported capacity is completely
355/// accurate, and can be relied on. It can even be used to manually free the memory
356/// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even
357/// when not necessary.
358///
359/// `Vec` does not guarantee any particular growth strategy when reallocating
360/// when full, nor when [`reserve`] is called. The current strategy is basic
361/// and it may prove desirable to use a non-constant growth factor. Whatever
362/// strategy is used will of course guarantee *O*(1) amortized [`push`].
363///
364/// `vec![x; n]`, `vec![a, b, c, d]`, and
365/// [`Vec::with_capacity(n)`][`Vec::with_capacity`], will all produce a `Vec`
366/// with exactly the requested capacity. If <code>[len] == [capacity]</code>,
367/// (as is the case for the [`vec!`] macro), then a `Vec<T>` can be converted to
368/// and from a [`Box<[T]>`][owned slice] without reallocating or moving the elements.
369///
370/// `Vec` will not specifically overwrite any data that is removed from it,
371/// but also won't specifically preserve it. Its uninitialized memory is
372/// scratch space that it may use however it wants. It will generally just do
373/// whatever is most efficient or otherwise easy to implement. Do not rely on
374/// removed data to be erased for security purposes. Even if you drop a `Vec`, its
375/// buffer may simply be reused by another allocation. Even if you zero a `Vec`'s memory
376/// first, that might not actually happen because the optimizer does not consider
377/// this a side-effect that must be preserved. There is one case which we will
378/// not break, however: using `unsafe` code to write to the excess capacity,
379/// and then increasing the length to match, is always valid.
380///
381/// Currently, `Vec` does not guarantee the order in which elements are dropped.
382/// The order has changed in the past and may change again.
383///
384/// [`get`]: ../../std/vec/struct.Vec.html#method.get
385/// [`get_mut`]: ../../std/vec/struct.Vec.html#method.get_mut
386/// [`String`]: crate::string::String
387/// [`&str`]: type@str
388/// [`shrink_to_fit`]: Vec::shrink_to_fit
389/// [`shrink_to`]: Vec::shrink_to
390/// [capacity]: Vec::capacity
391/// [`capacity`]: Vec::capacity
392/// [mem::size_of::\<T>]: core::mem::size_of
393/// [len]: Vec::len
394/// [`len`]: Vec::len
395/// [`push`]: Vec::push
396/// [`insert`]: Vec::insert
397/// [`reserve`]: Vec::reserve
398/// [`MaybeUninit`]: core::mem::MaybeUninit
399/// [owned slice]: Box
400#[stable(feature = "rust1", since = "1.0.0")]
401#[cfg_attr(not(test), rustc_diagnostic_item = "Vec")]
402#[rustc_insignificant_dtor]
403pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {
404 buf: RawVec<T, A>,
405 len: usize,
406}
407
408////////////////////////////////////////////////////////////////////////////////
409// Inherent methods
410////////////////////////////////////////////////////////////////////////////////
411
412impl<T> Vec<T> {
413 /// Constructs a new, empty `Vec<T>`.
414 ///
415 /// The vector will not allocate until elements are pushed onto it.
416 ///
417 /// # Examples
418 ///
419 /// ```
420 /// # #![allow(unused_mut)]
421 /// let mut vec: Vec<i32> = Vec::new();
422 /// ```
423 #[inline]
424 #[rustc_const_stable(feature = "const_vec_new", since = "1.39.0")]
425 #[stable(feature = "rust1", since = "1.0.0")]
426 #[must_use]
427 pub const fn new() -> Self {
428 Vec { buf: RawVec::NEW, len: 0 }
429 }
430
431 /// Constructs a new, empty `Vec<T>` with at least the specified capacity.
432 ///
433 /// The vector will be able to hold at least `capacity` elements without
434 /// reallocating. This method is allowed to allocate for more elements than
435 /// `capacity`. If `capacity` is 0, the vector will not allocate.
436 ///
437 /// It is important to note that although the returned vector has the
438 /// minimum *capacity* specified, the vector will have a zero *length*. For
439 /// an explanation of the difference between length and capacity, see
440 /// *[Capacity and reallocation]*.
441 ///
442 /// If it is important to know the exact allocated capacity of a `Vec`,
443 /// always use the [`capacity`] method after construction.
444 ///
445 /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation
446 /// and the capacity will always be `usize::MAX`.
447 ///
448 /// [Capacity and reallocation]: #capacity-and-reallocation
449 /// [`capacity`]: Vec::capacity
450 ///
451 /// # Panics
452 ///
453 /// Panics if the new capacity exceeds `isize::MAX` bytes.
454 ///
455 /// # Examples
456 ///
457 /// ```
458 /// let mut vec = Vec::with_capacity(10);
459 ///
460 /// // The vector contains no items, even though it has capacity for more
461 /// assert_eq!(vec.len(), 0);
462 /// assert!(vec.capacity() >= 10);
463 ///
464 /// // These are all done without reallocating...
465 /// for i in 0..10 {
466 /// vec.push(i);
467 /// }
468 /// assert_eq!(vec.len(), 10);
469 /// assert!(vec.capacity() >= 10);
470 ///
471 /// // ...but this may make the vector reallocate
472 /// vec.push(11);
473 /// assert_eq!(vec.len(), 11);
474 /// assert!(vec.capacity() >= 11);
475 ///
476 /// // A vector of a zero-sized type will always over-allocate, since no
477 /// // allocation is necessary
478 /// let vec_units = Vec::<()>::with_capacity(10);
479 /// assert_eq!(vec_units.capacity(), usize::MAX);
480 /// ```
481 #[cfg(not(no_global_oom_handling))]
482 #[inline]
483 #[stable(feature = "rust1", since = "1.0.0")]
484 #[must_use]
485 pub fn with_capacity(capacity: usize) -> Self {
486 Self::with_capacity_in(capacity, Global)
487 }
488
489 /// Tries to construct a new, empty `Vec<T>` with at least the specified capacity.
490 ///
491 /// The vector will be able to hold at least `capacity` elements without
492 /// reallocating. This method is allowed to allocate for more elements than
493 /// `capacity`. If `capacity` is 0, the vector will not allocate.
494 ///
495 /// It is important to note that although the returned vector has the
496 /// minimum *capacity* specified, the vector will have a zero *length*. For
497 /// an explanation of the difference between length and capacity, see
498 /// *[Capacity and reallocation]*.
499 ///
500 /// If it is important to know the exact allocated capacity of a `Vec`,
501 /// always use the [`capacity`] method after construction.
502 ///
503 /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation
504 /// and the capacity will always be `usize::MAX`.
505 ///
506 /// [Capacity and reallocation]: #capacity-and-reallocation
507 /// [`capacity`]: Vec::capacity
508 ///
509 /// # Examples
510 ///
511 /// ```
512 /// let mut vec = Vec::try_with_capacity(10).unwrap();
513 ///
514 /// // The vector contains no items, even though it has capacity for more
515 /// assert_eq!(vec.len(), 0);
516 /// assert!(vec.capacity() >= 10);
517 ///
518 /// // These are all done without reallocating...
519 /// for i in 0..10 {
520 /// vec.push(i);
521 /// }
522 /// assert_eq!(vec.len(), 10);
523 /// assert!(vec.capacity() >= 10);
524 ///
525 /// // ...but this may make the vector reallocate
526 /// vec.push(11);
527 /// assert_eq!(vec.len(), 11);
528 /// assert!(vec.capacity() >= 11);
529 ///
530 /// let mut result = Vec::try_with_capacity(usize::MAX);
531 /// assert!(result.is_err());
532 ///
533 /// // A vector of a zero-sized type will always over-allocate, since no
534 /// // allocation is necessary
535 /// let vec_units = Vec::<()>::try_with_capacity(10).unwrap();
536 /// assert_eq!(vec_units.capacity(), usize::MAX);
537 /// ```
538 #[inline]
539 #[stable(feature = "kernel", since = "1.0.0")]
540 pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
541 Self::try_with_capacity_in(capacity, Global)
542 }
543
544 /// Creates a `Vec<T>` directly from a pointer, a capacity, and a length.
545 ///
546 /// # Safety
547 ///
548 /// This is highly unsafe, due to the number of invariants that aren't
549 /// checked:
550 ///
551 /// * `ptr` must have been allocated using the global allocator, such as via
552 /// the [`alloc::alloc`] function.
553 /// * `T` needs to have the same alignment as what `ptr` was allocated with.
554 /// (`T` having a less strict alignment is not sufficient, the alignment really
555 /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be
556 /// allocated and deallocated with the same layout.)
557 /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs
558 /// to be the same size as the pointer was allocated with. (Because similar to
559 /// alignment, [`dealloc`] must be called with the same layout `size`.)
560 /// * `length` needs to be less than or equal to `capacity`.
561 /// * The first `length` values must be properly initialized values of type `T`.
562 /// * `capacity` needs to be the capacity that the pointer was allocated with.
563 /// * The allocated size in bytes must be no larger than `isize::MAX`.
564 /// See the safety documentation of [`pointer::offset`].
565 ///
566 /// These requirements are always upheld by any `ptr` that has been allocated
567 /// via `Vec<T>`. Other allocation sources are allowed if the invariants are
568 /// upheld.
569 ///
570 /// Violating these may cause problems like corrupting the allocator's
571 /// internal data structures. For example it is normally **not** safe
572 /// to build a `Vec<u8>` from a pointer to a C `char` array with length
573 /// `size_t`, doing so is only safe if the array was initially allocated by
574 /// a `Vec` or `String`.
575 /// It's also not safe to build one from a `Vec<u16>` and its length, because
576 /// the allocator cares about the alignment, and these two types have different
577 /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
578 /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1. To avoid
579 /// these issues, it is often preferable to do casting/transmuting using
580 /// [`slice::from_raw_parts`] instead.
581 ///
582 /// The ownership of `ptr` is effectively transferred to the
583 /// `Vec<T>` which may then deallocate, reallocate or change the
584 /// contents of memory pointed to by the pointer at will. Ensure
585 /// that nothing else uses the pointer after calling this
586 /// function.
587 ///
588 /// [`String`]: crate::string::String
589 /// [`alloc::alloc`]: crate::alloc::alloc
590 /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
591 ///
592 /// # Examples
593 ///
594 /// ```
595 /// use std::ptr;
596 /// use std::mem;
597 ///
598 /// let v = vec![1, 2, 3];
599 ///
600 // FIXME Update this when vec_into_raw_parts is stabilized
601 /// // Prevent running `v`'s destructor so we are in complete control
602 /// // of the allocation.
603 /// let mut v = mem::ManuallyDrop::new(v);
604 ///
605 /// // Pull out the various important pieces of information about `v`
606 /// let p = v.as_mut_ptr();
607 /// let len = v.len();
608 /// let cap = v.capacity();
609 ///
610 /// unsafe {
611 /// // Overwrite memory with 4, 5, 6
612 /// for i in 0..len {
613 /// ptr::write(p.add(i), 4 + i);
614 /// }
615 ///
616 /// // Put everything back together into a Vec
617 /// let rebuilt = Vec::from_raw_parts(p, len, cap);
618 /// assert_eq!(rebuilt, [4, 5, 6]);
619 /// }
620 /// ```
621 ///
622 /// Using memory that was allocated elsewhere:
623 ///
624 /// ```rust
625 /// #![feature(allocator_api)]
626 ///
627 /// use std::alloc::{AllocError, Allocator, Global, Layout};
628 ///
629 /// fn main() {
630 /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
631 ///
632 /// let vec = unsafe {
633 /// let mem = match Global.allocate(layout) {
634 /// Ok(mem) => mem.cast::<u32>().as_ptr(),
635 /// Err(AllocError) => return,
636 /// };
637 ///
638 /// mem.write(1_000_000);
639 ///
640 /// Vec::from_raw_parts_in(mem, 1, 16, Global)
641 /// };
642 ///
643 /// assert_eq!(vec, &[1_000_000]);
644 /// assert_eq!(vec.capacity(), 16);
645 /// }
646 /// ```
647 #[inline]
648 #[stable(feature = "rust1", since = "1.0.0")]
649 pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
650 unsafe { Self::from_raw_parts_in(ptr, length, capacity, Global) }
651 }
652}
653
654impl<T, A: Allocator> Vec<T, A> {
655 /// Constructs a new, empty `Vec<T, A>`.
656 ///
657 /// The vector will not allocate until elements are pushed onto it.
658 ///
659 /// # Examples
660 ///
661 /// ```
662 /// #![feature(allocator_api)]
663 ///
664 /// use std::alloc::System;
665 ///
666 /// # #[allow(unused_mut)]
667 /// let mut vec: Vec<i32, _> = Vec::new_in(System);
668 /// ```
669 #[inline]
670 #[unstable(feature = "allocator_api", issue = "32838")]
671 pub const fn new_in(alloc: A) -> Self {
672 Vec { buf: RawVec::new_in(alloc), len: 0 }
673 }
674
675 /// Constructs a new, empty `Vec<T, A>` with at least the specified capacity
676 /// with the provided allocator.
677 ///
678 /// The vector will be able to hold at least `capacity` elements without
679 /// reallocating. This method is allowed to allocate for more elements than
680 /// `capacity`. If `capacity` is 0, the vector will not allocate.
681 ///
682 /// It is important to note that although the returned vector has the
683 /// minimum *capacity* specified, the vector will have a zero *length*. For
684 /// an explanation of the difference between length and capacity, see
685 /// *[Capacity and reallocation]*.
686 ///
687 /// If it is important to know the exact allocated capacity of a `Vec`,
688 /// always use the [`capacity`] method after construction.
689 ///
690 /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation
691 /// and the capacity will always be `usize::MAX`.
692 ///
693 /// [Capacity and reallocation]: #capacity-and-reallocation
694 /// [`capacity`]: Vec::capacity
695 ///
696 /// # Panics
697 ///
698 /// Panics if the new capacity exceeds `isize::MAX` bytes.
699 ///
700 /// # Examples
701 ///
702 /// ```
703 /// #![feature(allocator_api)]
704 ///
705 /// use std::alloc::System;
706 ///
707 /// let mut vec = Vec::with_capacity_in(10, System);
708 ///
709 /// // The vector contains no items, even though it has capacity for more
710 /// assert_eq!(vec.len(), 0);
711 /// assert_eq!(vec.capacity(), 10);
712 ///
713 /// // These are all done without reallocating...
714 /// for i in 0..10 {
715 /// vec.push(i);
716 /// }
717 /// assert_eq!(vec.len(), 10);
718 /// assert_eq!(vec.capacity(), 10);
719 ///
720 /// // ...but this may make the vector reallocate
721 /// vec.push(11);
722 /// assert_eq!(vec.len(), 11);
723 /// assert!(vec.capacity() >= 11);
724 ///
725 /// // A vector of a zero-sized type will always over-allocate, since no
726 /// // allocation is necessary
727 /// let vec_units = Vec::<(), System>::with_capacity_in(10, System);
728 /// assert_eq!(vec_units.capacity(), usize::MAX);
729 /// ```
730 #[cfg(not(no_global_oom_handling))]
731 #[inline]
732 #[unstable(feature = "allocator_api", issue = "32838")]
733 pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
734 Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 }
735 }
736
737 /// Tries to construct a new, empty `Vec<T, A>` with at least the specified capacity
738 /// with the provided allocator.
739 ///
740 /// The vector will be able to hold at least `capacity` elements without
741 /// reallocating. This method is allowed to allocate for more elements than
742 /// `capacity`. If `capacity` is 0, the vector will not allocate.
743 ///
744 /// It is important to note that although the returned vector has the
745 /// minimum *capacity* specified, the vector will have a zero *length*. For
746 /// an explanation of the difference between length and capacity, see
747 /// *[Capacity and reallocation]*.
748 ///
749 /// If it is important to know the exact allocated capacity of a `Vec`,
750 /// always use the [`capacity`] method after construction.
751 ///
752 /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation
753 /// and the capacity will always be `usize::MAX`.
754 ///
755 /// [Capacity and reallocation]: #capacity-and-reallocation
756 /// [`capacity`]: Vec::capacity
757 ///
758 /// # Examples
759 ///
760 /// ```
761 /// #![feature(allocator_api)]
762 ///
763 /// use std::alloc::System;
764 ///
765 /// let mut vec = Vec::try_with_capacity_in(10, System).unwrap();
766 ///
767 /// // The vector contains no items, even though it has capacity for more
768 /// assert_eq!(vec.len(), 0);
769 /// assert_eq!(vec.capacity(), 10);
770 ///
771 /// // These are all done without reallocating...
772 /// for i in 0..10 {
773 /// vec.push(i);
774 /// }
775 /// assert_eq!(vec.len(), 10);
776 /// assert_eq!(vec.capacity(), 10);
777 ///
778 /// // ...but this may make the vector reallocate
779 /// vec.push(11);
780 /// assert_eq!(vec.len(), 11);
781 /// assert!(vec.capacity() >= 11);
782 ///
783 /// let mut result = Vec::try_with_capacity_in(usize::MAX, System);
784 /// assert!(result.is_err());
785 ///
786 /// // A vector of a zero-sized type will always over-allocate, since no
787 /// // allocation is necessary
788 /// let vec_units = Vec::<(), System>::try_with_capacity_in(10, System).unwrap();
789 /// assert_eq!(vec_units.capacity(), usize::MAX);
790 /// ```
791 #[inline]
792 #[stable(feature = "kernel", since = "1.0.0")]
793 pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {
794 Ok(Vec { buf: RawVec::try_with_capacity_in(capacity, alloc)?, len: 0 })
795 }
796
797 /// Creates a `Vec<T, A>` directly from a pointer, a capacity, a length,
798 /// and an allocator.
799 ///
800 /// # Safety
801 ///
802 /// This is highly unsafe, due to the number of invariants that aren't
803 /// checked:
804 ///
805 /// * `ptr` must be [*currently allocated*] via the given allocator `alloc`.
806 /// * `T` needs to have the same alignment as what `ptr` was allocated with.
807 /// (`T` having a less strict alignment is not sufficient, the alignment really
808 /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be
809 /// allocated and deallocated with the same layout.)
810 /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs
811 /// to be the same size as the pointer was allocated with. (Because similar to
812 /// alignment, [`dealloc`] must be called with the same layout `size`.)
813 /// * `length` needs to be less than or equal to `capacity`.
814 /// * The first `length` values must be properly initialized values of type `T`.
815 /// * `capacity` needs to [*fit*] the layout size that the pointer was allocated with.
816 /// * The allocated size in bytes must be no larger than `isize::MAX`.
817 /// See the safety documentation of [`pointer::offset`].
818 ///
819 /// These requirements are always upheld by any `ptr` that has been allocated
820 /// via `Vec<T, A>`. Other allocation sources are allowed if the invariants are
821 /// upheld.
822 ///
823 /// Violating these may cause problems like corrupting the allocator's
824 /// internal data structures. For example it is **not** safe
825 /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.
826 /// It's also not safe to build one from a `Vec<u16>` and its length, because
827 /// the allocator cares about the alignment, and these two types have different
828 /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
829 /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.
830 ///
831 /// The ownership of `ptr` is effectively transferred to the
832 /// `Vec<T>` which may then deallocate, reallocate or change the
833 /// contents of memory pointed to by the pointer at will. Ensure
834 /// that nothing else uses the pointer after calling this
835 /// function.
836 ///
837 /// [`String`]: crate::string::String
838 /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
839 /// [*currently allocated*]: crate::alloc::Allocator#currently-allocated-memory
840 /// [*fit*]: crate::alloc::Allocator#memory-fitting
841 ///
842 /// # Examples
843 ///
844 /// ```
845 /// #![feature(allocator_api)]
846 ///
847 /// use std::alloc::System;
848 ///
849 /// use std::ptr;
850 /// use std::mem;
851 ///
852 /// let mut v = Vec::with_capacity_in(3, System);
853 /// v.push(1);
854 /// v.push(2);
855 /// v.push(3);
856 ///
857 // FIXME Update this when vec_into_raw_parts is stabilized
858 /// // Prevent running `v`'s destructor so we are in complete control
859 /// // of the allocation.
860 /// let mut v = mem::ManuallyDrop::new(v);
861 ///
862 /// // Pull out the various important pieces of information about `v`
863 /// let p = v.as_mut_ptr();
864 /// let len = v.len();
865 /// let cap = v.capacity();
866 /// let alloc = v.allocator();
867 ///
868 /// unsafe {
869 /// // Overwrite memory with 4, 5, 6
870 /// for i in 0..len {
871 /// ptr::write(p.add(i), 4 + i);
872 /// }
873 ///
874 /// // Put everything back together into a Vec
875 /// let rebuilt = Vec::from_raw_parts_in(p, len, cap, alloc.clone());
876 /// assert_eq!(rebuilt, [4, 5, 6]);
877 /// }
878 /// ```
879 ///
880 /// Using memory that was allocated elsewhere:
881 ///
882 /// ```rust
883 /// use std::alloc::{alloc, Layout};
884 ///
885 /// fn main() {
886 /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
887 /// let vec = unsafe {
888 /// let mem = alloc(layout).cast::<u32>();
889 /// if mem.is_null() {
890 /// return;
891 /// }
892 ///
893 /// mem.write(1_000_000);
894 ///
895 /// Vec::from_raw_parts(mem, 1, 16)
896 /// };
897 ///
898 /// assert_eq!(vec, &[1_000_000]);
899 /// assert_eq!(vec.capacity(), 16);
900 /// }
901 /// ```
902 #[inline]
903 #[unstable(feature = "allocator_api", issue = "32838")]
904 pub unsafe fn from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self {
905 unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } }
906 }
907
908 /// Decomposes a `Vec<T>` into its raw components.
909 ///
910 /// Returns the raw pointer to the underlying data, the length of
911 /// the vector (in elements), and the allocated capacity of the
912 /// data (in elements). These are the same arguments in the same
913 /// order as the arguments to [`from_raw_parts`].
914 ///
915 /// After calling this function, the caller is responsible for the
916 /// memory previously managed by the `Vec`. The only way to do
917 /// this is to convert the raw pointer, length, and capacity back
918 /// into a `Vec` with the [`from_raw_parts`] function, allowing
919 /// the destructor to perform the cleanup.
920 ///
921 /// [`from_raw_parts`]: Vec::from_raw_parts
922 ///
923 /// # Examples
924 ///
925 /// ```
926 /// #![feature(vec_into_raw_parts)]
927 /// let v: Vec<i32> = vec![-1, 0, 1];
928 ///
929 /// let (ptr, len, cap) = v.into_raw_parts();
930 ///
931 /// let rebuilt = unsafe {
932 /// // We can now make changes to the components, such as
933 /// // transmuting the raw pointer to a compatible type.
934 /// let ptr = ptr as *mut u32;
935 ///
936 /// Vec::from_raw_parts(ptr, len, cap)
937 /// };
938 /// assert_eq!(rebuilt, [4294967295, 0, 1]);
939 /// ```
940 #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
941 pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
942 let mut me = ManuallyDrop::new(self);
943 (me.as_mut_ptr(), me.len(), me.capacity())
944 }
945
946 /// Decomposes a `Vec<T>` into its raw components.
947 ///
948 /// Returns the raw pointer to the underlying data, the length of the vector (in elements),
949 /// the allocated capacity of the data (in elements), and the allocator. These are the same
950 /// arguments in the same order as the arguments to [`from_raw_parts_in`].
951 ///
952 /// After calling this function, the caller is responsible for the
953 /// memory previously managed by the `Vec`. The only way to do
954 /// this is to convert the raw pointer, length, and capacity back
955 /// into a `Vec` with the [`from_raw_parts_in`] function, allowing
956 /// the destructor to perform the cleanup.
957 ///
958 /// [`from_raw_parts_in`]: Vec::from_raw_parts_in
959 ///
960 /// # Examples
961 ///
962 /// ```
963 /// #![feature(allocator_api, vec_into_raw_parts)]
964 ///
965 /// use std::alloc::System;
966 ///
967 /// let mut v: Vec<i32, System> = Vec::new_in(System);
968 /// v.push(-1);
969 /// v.push(0);
970 /// v.push(1);
971 ///
972 /// let (ptr, len, cap, alloc) = v.into_raw_parts_with_alloc();
973 ///
974 /// let rebuilt = unsafe {
975 /// // We can now make changes to the components, such as
976 /// // transmuting the raw pointer to a compatible type.
977 /// let ptr = ptr as *mut u32;
978 ///
979 /// Vec::from_raw_parts_in(ptr, len, cap, alloc)
980 /// };
981 /// assert_eq!(rebuilt, [4294967295, 0, 1]);
982 /// ```
983 #[unstable(feature = "allocator_api", issue = "32838")]
984 // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
985 pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) {
986 let mut me = ManuallyDrop::new(self);
987 let len = me.len();
988 let capacity = me.capacity();
989 let ptr = me.as_mut_ptr();
990 let alloc = unsafe { ptr::read(me.allocator()) };
991 (ptr, len, capacity, alloc)
992 }
993
994 /// Returns the total number of elements the vector can hold without
995 /// reallocating.
996 ///
997 /// # Examples
998 ///
999 /// ```
1000 /// let mut vec: Vec<i32> = Vec::with_capacity(10);
1001 /// vec.push(42);
1002 /// assert_eq!(vec.capacity(), 10);
1003 /// ```
1004 #[inline]
1005 #[stable(feature = "rust1", since = "1.0.0")]
1006 pub fn capacity(&self) -> usize {
1007 self.buf.capacity()
1008 }
1009
1010 /// Reserves capacity for at least `additional` more elements to be inserted
1011 /// in the given `Vec<T>`. The collection may reserve more space to
1012 /// speculatively avoid frequent reallocations. After calling `reserve`,
1013 /// capacity will be greater than or equal to `self.len() + additional`.
1014 /// Does nothing if capacity is already sufficient.
1015 ///
1016 /// # Panics
1017 ///
1018 /// Panics if the new capacity exceeds `isize::MAX` bytes.
1019 ///
1020 /// # Examples
1021 ///
1022 /// ```
1023 /// let mut vec = vec![1];
1024 /// vec.reserve(10);
1025 /// assert!(vec.capacity() >= 11);
1026 /// ```
1027 #[cfg(not(no_global_oom_handling))]
1028 #[stable(feature = "rust1", since = "1.0.0")]
1029 pub fn reserve(&mut self, additional: usize) {
1030 self.buf.reserve(self.len, additional);
1031 }
1032
1033 /// Reserves the minimum capacity for at least `additional` more elements to
1034 /// be inserted in the given `Vec<T>`. Unlike [`reserve`], this will not
1035 /// deliberately over-allocate to speculatively avoid frequent allocations.
1036 /// After calling `reserve_exact`, capacity will be greater than or equal to
1037 /// `self.len() + additional`. Does nothing if the capacity is already
1038 /// sufficient.
1039 ///
1040 /// Note that the allocator may give the collection more space than it
1041 /// requests. Therefore, capacity can not be relied upon to be precisely
1042 /// minimal. Prefer [`reserve`] if future insertions are expected.
1043 ///
1044 /// [`reserve`]: Vec::reserve
1045 ///
1046 /// # Panics
1047 ///
1048 /// Panics if the new capacity exceeds `isize::MAX` bytes.
1049 ///
1050 /// # Examples
1051 ///
1052 /// ```
1053 /// let mut vec = vec![1];
1054 /// vec.reserve_exact(10);
1055 /// assert!(vec.capacity() >= 11);
1056 /// ```
1057 #[cfg(not(no_global_oom_handling))]
1058 #[stable(feature = "rust1", since = "1.0.0")]
1059 pub fn reserve_exact(&mut self, additional: usize) {
1060 self.buf.reserve_exact(self.len, additional);
1061 }
1062
1063 /// Tries to reserve capacity for at least `additional` more elements to be inserted
1064 /// in the given `Vec<T>`. The collection may reserve more space to speculatively avoid
1065 /// frequent reallocations. After calling `try_reserve`, capacity will be
1066 /// greater than or equal to `self.len() + additional` if it returns
1067 /// `Ok(())`. Does nothing if capacity is already sufficient. This method
1068 /// preserves the contents even if an error occurs.
1069 ///
1070 /// # Errors
1071 ///
1072 /// If the capacity overflows, or the allocator reports a failure, then an error
1073 /// is returned.
1074 ///
1075 /// # Examples
1076 ///
1077 /// ```
1078 /// use std::collections::TryReserveError;
1079 ///
1080 /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1081 /// let mut output = Vec::new();
1082 ///
1083 /// // Pre-reserve the memory, exiting if we can't
1084 /// output.try_reserve(data.len())?;
1085 ///
1086 /// // Now we know this can't OOM in the middle of our complex work
1087 /// output.extend(data.iter().map(|&val| {
1088 /// val * 2 + 5 // very complicated
1089 /// }));
1090 ///
1091 /// Ok(output)
1092 /// }
1093 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
1094 /// ```
1095 #[stable(feature = "try_reserve", since = "1.57.0")]
1096 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
1097 self.buf.try_reserve(self.len, additional)
1098 }
1099
1100 /// Tries to reserve the minimum capacity for at least `additional`
1101 /// elements to be inserted in the given `Vec<T>`. Unlike [`try_reserve`],
1102 /// this will not deliberately over-allocate to speculatively avoid frequent
1103 /// allocations. After calling `try_reserve_exact`, capacity will be greater
1104 /// than or equal to `self.len() + additional` if it returns `Ok(())`.
1105 /// Does nothing if the capacity is already sufficient.
1106 ///
1107 /// Note that the allocator may give the collection more space than it
1108 /// requests. Therefore, capacity can not be relied upon to be precisely
1109 /// minimal. Prefer [`try_reserve`] if future insertions are expected.
1110 ///
1111 /// [`try_reserve`]: Vec::try_reserve
1112 ///
1113 /// # Errors
1114 ///
1115 /// If the capacity overflows, or the allocator reports a failure, then an error
1116 /// is returned.
1117 ///
1118 /// # Examples
1119 ///
1120 /// ```
1121 /// use std::collections::TryReserveError;
1122 ///
1123 /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1124 /// let mut output = Vec::new();
1125 ///
1126 /// // Pre-reserve the memory, exiting if we can't
1127 /// output.try_reserve_exact(data.len())?;
1128 ///
1129 /// // Now we know this can't OOM in the middle of our complex work
1130 /// output.extend(data.iter().map(|&val| {
1131 /// val * 2 + 5 // very complicated
1132 /// }));
1133 ///
1134 /// Ok(output)
1135 /// }
1136 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
1137 /// ```
1138 #[stable(feature = "try_reserve", since = "1.57.0")]
1139 pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
1140 self.buf.try_reserve_exact(self.len, additional)
1141 }
1142
1143 /// Shrinks the capacity of the vector as much as possible.
1144 ///
1145 /// It will drop down as close as possible to the length but the allocator
1146 /// may still inform the vector that there is space for a few more elements.
1147 ///
1148 /// # Examples
1149 ///
1150 /// ```
1151 /// let mut vec = Vec::with_capacity(10);
1152 /// vec.extend([1, 2, 3]);
1153 /// assert_eq!(vec.capacity(), 10);
1154 /// vec.shrink_to_fit();
1155 /// assert!(vec.capacity() >= 3);
1156 /// ```
1157 #[cfg(not(no_global_oom_handling))]
1158 #[stable(feature = "rust1", since = "1.0.0")]
1159 pub fn shrink_to_fit(&mut self) {
1160 // The capacity is never less than the length, and there's nothing to do when
1161 // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit`
1162 // by only calling it with a greater capacity.
1163 if self.capacity() > self.len {
1164 self.buf.shrink_to_fit(self.len);
1165 }
1166 }
1167
1168 /// Shrinks the capacity of the vector with a lower bound.
1169 ///
1170 /// The capacity will remain at least as large as both the length
1171 /// and the supplied value.
1172 ///
1173 /// If the current capacity is less than the lower limit, this is a no-op.
1174 ///
1175 /// # Examples
1176 ///
1177 /// ```
1178 /// let mut vec = Vec::with_capacity(10);
1179 /// vec.extend([1, 2, 3]);
1180 /// assert_eq!(vec.capacity(), 10);
1181 /// vec.shrink_to(4);
1182 /// assert!(vec.capacity() >= 4);
1183 /// vec.shrink_to(0);
1184 /// assert!(vec.capacity() >= 3);
1185 /// ```
1186 #[cfg(not(no_global_oom_handling))]
1187 #[stable(feature = "shrink_to", since = "1.56.0")]
1188 pub fn shrink_to(&mut self, min_capacity: usize) {
1189 if self.capacity() > min_capacity {
1190 self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
1191 }
1192 }
1193
1194 /// Converts the vector into [`Box<[T]>`][owned slice].
1195 ///
1196 /// If the vector has excess capacity, its items will be moved into a
1197 /// newly-allocated buffer with exactly the right capacity.
1198 ///
1199 /// [owned slice]: Box
1200 ///
1201 /// # Examples
1202 ///
1203 /// ```
1204 /// let v = vec![1, 2, 3];
1205 ///
1206 /// let slice = v.into_boxed_slice();
1207 /// ```
1208 ///
1209 /// Any excess capacity is removed:
1210 ///
1211 /// ```
1212 /// let mut vec = Vec::with_capacity(10);
1213 /// vec.extend([1, 2, 3]);
1214 ///
1215 /// assert_eq!(vec.capacity(), 10);
1216 /// let slice = vec.into_boxed_slice();
1217 /// assert_eq!(slice.into_vec().capacity(), 3);
1218 /// ```
1219 #[cfg(not(no_global_oom_handling))]
1220 #[stable(feature = "rust1", since = "1.0.0")]
1221 pub fn into_boxed_slice(mut self) -> Box<[T], A> {
1222 unsafe {
1223 self.shrink_to_fit();
1224 let me = ManuallyDrop::new(self);
1225 let buf = ptr::read(&me.buf);
1226 let len = me.len();
1227 buf.into_box(len).assume_init()
1228 }
1229 }
1230
1231 /// Shortens the vector, keeping the first `len` elements and dropping
1232 /// the rest.
1233 ///
1234 /// If `len` is greater than the vector's current length, this has no
1235 /// effect.
1236 ///
1237 /// The [`drain`] method can emulate `truncate`, but causes the excess
1238 /// elements to be returned instead of dropped.
1239 ///
1240 /// Note that this method has no effect on the allocated capacity
1241 /// of the vector.
1242 ///
1243 /// # Examples
1244 ///
1245 /// Truncating a five element vector to two elements:
1246 ///
1247 /// ```
1248 /// let mut vec = vec![1, 2, 3, 4, 5];
1249 /// vec.truncate(2);
1250 /// assert_eq!(vec, [1, 2]);
1251 /// ```
1252 ///
1253 /// No truncation occurs when `len` is greater than the vector's current
1254 /// length:
1255 ///
1256 /// ```
1257 /// let mut vec = vec![1, 2, 3];
1258 /// vec.truncate(8);
1259 /// assert_eq!(vec, [1, 2, 3]);
1260 /// ```
1261 ///
1262 /// Truncating when `len == 0` is equivalent to calling the [`clear`]
1263 /// method.
1264 ///
1265 /// ```
1266 /// let mut vec = vec![1, 2, 3];
1267 /// vec.truncate(0);
1268 /// assert_eq!(vec, []);
1269 /// ```
1270 ///
1271 /// [`clear`]: Vec::clear
1272 /// [`drain`]: Vec::drain
1273 #[stable(feature = "rust1", since = "1.0.0")]
1274 pub fn truncate(&mut self, len: usize) {
1275 // This is safe because:
1276 //
1277 // * the slice passed to `drop_in_place` is valid; the `len > self.len`
1278 // case avoids creating an invalid slice, and
1279 // * the `len` of the vector is shrunk before calling `drop_in_place`,
1280 // such that no value will be dropped twice in case `drop_in_place`
1281 // were to panic once (if it panics twice, the program aborts).
1282 unsafe {
1283 // Note: It's intentional that this is `>` and not `>=`.
1284 // Changing it to `>=` has negative performance
1285 // implications in some cases. See #78884 for more.
1286 if len > self.len {
1287 return;
1288 }
1289 let remaining_len = self.len - len;
1290 let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
1291 self.len = len;
1292 ptr::drop_in_place(s);
1293 }
1294 }
1295
1296 /// Extracts a slice containing the entire vector.
1297 ///
1298 /// Equivalent to `&s[..]`.
1299 ///
1300 /// # Examples
1301 ///
1302 /// ```
1303 /// use std::io::{self, Write};
1304 /// let buffer = vec![1, 2, 3, 5, 8];
1305 /// io::sink().write(buffer.as_slice()).unwrap();
1306 /// ```
1307 #[inline]
1308 #[stable(feature = "vec_as_slice", since = "1.7.0")]
1309 pub fn as_slice(&self) -> &[T] {
1310 self
1311 }
1312
1313 /// Extracts a mutable slice of the entire vector.
1314 ///
1315 /// Equivalent to `&mut s[..]`.
1316 ///
1317 /// # Examples
1318 ///
1319 /// ```
1320 /// use std::io::{self, Read};
1321 /// let mut buffer = vec![0; 3];
1322 /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
1323 /// ```
1324 #[inline]
1325 #[stable(feature = "vec_as_slice", since = "1.7.0")]
1326 pub fn as_mut_slice(&mut self) -> &mut [T] {
1327 self
1328 }
1329
1330 /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
1331 /// valid for zero sized reads if the vector didn't allocate.
1332 ///
1333 /// The caller must ensure that the vector outlives the pointer this
1334 /// function returns, or else it will end up pointing to garbage.
1335 /// Modifying the vector may cause its buffer to be reallocated,
1336 /// which would also make any pointers to it invalid.
1337 ///
1338 /// The caller must also ensure that the memory the pointer (non-transitively) points to
1339 /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1340 /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1341 ///
1342 /// # Examples
1343 ///
1344 /// ```
1345 /// let x = vec![1, 2, 4];
1346 /// let x_ptr = x.as_ptr();
1347 ///
1348 /// unsafe {
1349 /// for i in 0..x.len() {
1350 /// assert_eq!(*x_ptr.add(i), 1 << i);
1351 /// }
1352 /// }
1353 /// ```
1354 ///
1355 /// [`as_mut_ptr`]: Vec::as_mut_ptr
1356 #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1357 #[inline]
1358 pub fn as_ptr(&self) -> *const T {
1359 // We shadow the slice method of the same name to avoid going through
1360 // `deref`, which creates an intermediate reference.
1361 let ptr = self.buf.ptr();
1362 unsafe {
1363 assume(!ptr.is_null());
1364 }
1365 ptr
1366 }
1367
1368 /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling
1369 /// raw pointer valid for zero sized reads if the vector didn't allocate.
1370 ///
1371 /// The caller must ensure that the vector outlives the pointer this
1372 /// function returns, or else it will end up pointing to garbage.
1373 /// Modifying the vector may cause its buffer to be reallocated,
1374 /// which would also make any pointers to it invalid.
1375 ///
1376 /// # Examples
1377 ///
1378 /// ```
1379 /// // Allocate vector big enough for 4 elements.
1380 /// let size = 4;
1381 /// let mut x: Vec<i32> = Vec::with_capacity(size);
1382 /// let x_ptr = x.as_mut_ptr();
1383 ///
1384 /// // Initialize elements via raw pointer writes, then set length.
1385 /// unsafe {
1386 /// for i in 0..size {
1387 /// *x_ptr.add(i) = i as i32;
1388 /// }
1389 /// x.set_len(size);
1390 /// }
1391 /// assert_eq!(&*x, &[0, 1, 2, 3]);
1392 /// ```
1393 #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1394 #[inline]
1395 pub fn as_mut_ptr(&mut self) -> *mut T {
1396 // We shadow the slice method of the same name to avoid going through
1397 // `deref_mut`, which creates an intermediate reference.
1398 let ptr = self.buf.ptr();
1399 unsafe {
1400 assume(!ptr.is_null());
1401 }
1402 ptr
1403 }
1404
1405 /// Returns a reference to the underlying allocator.
1406 #[unstable(feature = "allocator_api", issue = "32838")]
1407 #[inline]
1408 pub fn allocator(&self) -> &A {
1409 self.buf.allocator()
1410 }
1411
1412 /// Forces the length of the vector to `new_len`.
1413 ///
1414 /// This is a low-level operation that maintains none of the normal
1415 /// invariants of the type. Normally changing the length of a vector
1416 /// is done using one of the safe operations instead, such as
1417 /// [`truncate`], [`resize`], [`extend`], or [`clear`].
1418 ///
1419 /// [`truncate`]: Vec::truncate
1420 /// [`resize`]: Vec::resize
1421 /// [`extend`]: Extend::extend
1422 /// [`clear`]: Vec::clear
1423 ///
1424 /// # Safety
1425 ///
1426 /// - `new_len` must be less than or equal to [`capacity()`].
1427 /// - The elements at `old_len..new_len` must be initialized.
1428 ///
1429 /// [`capacity()`]: Vec::capacity
1430 ///
1431 /// # Examples
1432 ///
1433 /// This method can be useful for situations in which the vector
1434 /// is serving as a buffer for other code, particularly over FFI:
1435 ///
1436 /// ```no_run
1437 /// # #![allow(dead_code)]
1438 /// # // This is just a minimal skeleton for the doc example;
1439 /// # // don't use this as a starting point for a real library.
1440 /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void }
1441 /// # const Z_OK: i32 = 0;
1442 /// # extern "C" {
1443 /// # fn deflateGetDictionary(
1444 /// # strm: *mut std::ffi::c_void,
1445 /// # dictionary: *mut u8,
1446 /// # dictLength: *mut usize,
1447 /// # ) -> i32;
1448 /// # }
1449 /// # impl StreamWrapper {
1450 /// pub fn get_dictionary(&self) -> Option<Vec<u8>> {
1451 /// // Per the FFI method's docs, "32768 bytes is always enough".
1452 /// let mut dict = Vec::with_capacity(32_768);
1453 /// let mut dict_length = 0;
1454 /// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
1455 /// // 1. `dict_length` elements were initialized.
1456 /// // 2. `dict_length` <= the capacity (32_768)
1457 /// // which makes `set_len` safe to call.
1458 /// unsafe {
1459 /// // Make the FFI call...
1460 /// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
1461 /// if r == Z_OK {
1462 /// // ...and update the length to what was initialized.
1463 /// dict.set_len(dict_length);
1464 /// Some(dict)
1465 /// } else {
1466 /// None
1467 /// }
1468 /// }
1469 /// }
1470 /// # }
1471 /// ```
1472 ///
1473 /// While the following example is sound, there is a memory leak since
1474 /// the inner vectors were not freed prior to the `set_len` call:
1475 ///
1476 /// ```
1477 /// let mut vec = vec![vec![1, 0, 0],
1478 /// vec![0, 1, 0],
1479 /// vec![0, 0, 1]];
1480 /// // SAFETY:
1481 /// // 1. `old_len..0` is empty so no elements need to be initialized.
1482 /// // 2. `0 <= capacity` always holds whatever `capacity` is.
1483 /// unsafe {
1484 /// vec.set_len(0);
1485 /// }
1486 /// ```
1487 ///
1488 /// Normally, here, one would use [`clear`] instead to correctly drop
1489 /// the contents and thus not leak memory.
1490 #[inline]
1491 #[stable(feature = "rust1", since = "1.0.0")]
1492 pub unsafe fn set_len(&mut self, new_len: usize) {
1493 debug_assert!(new_len <= self.capacity());
1494
1495 self.len = new_len;
1496 }
1497
1498 /// Removes an element from the vector and returns it.
1499 ///
1500 /// The removed element is replaced by the last element of the vector.
1501 ///
1502 /// This does not preserve ordering, but is *O*(1).
1503 /// If you need to preserve the element order, use [`remove`] instead.
1504 ///
1505 /// [`remove`]: Vec::remove
1506 ///
1507 /// # Panics
1508 ///
1509 /// Panics if `index` is out of bounds.
1510 ///
1511 /// # Examples
1512 ///
1513 /// ```
1514 /// let mut v = vec!["foo", "bar", "baz", "qux"];
1515 ///
1516 /// assert_eq!(v.swap_remove(1), "bar");
1517 /// assert_eq!(v, ["foo", "qux", "baz"]);
1518 ///
1519 /// assert_eq!(v.swap_remove(0), "foo");
1520 /// assert_eq!(v, ["baz", "qux"]);
1521 /// ```
1522 #[inline]
1523 #[stable(feature = "rust1", since = "1.0.0")]
1524 pub fn swap_remove(&mut self, index: usize) -> T {
1525 #[cold]
1526 #[inline(never)]
1527 fn assert_failed(index: usize, len: usize) -> ! {
1528 panic!("swap_remove index (is {index}) should be < len (is {len})");
1529 }
1530
1531 let len = self.len();
1532 if index >= len {
1533 assert_failed(index, len);
1534 }
1535 unsafe {
1536 // We replace self[index] with the last element. Note that if the
1537 // bounds check above succeeds there must be a last element (which
1538 // can be self[index] itself).
1539 let value = ptr::read(self.as_ptr().add(index));
1540 let base_ptr = self.as_mut_ptr();
1541 ptr::copy(base_ptr.add(len - 1), base_ptr.add(index), 1);
1542 self.set_len(len - 1);
1543 value
1544 }
1545 }
1546
1547 /// Inserts an element at position `index` within the vector, shifting all
1548 /// elements after it to the right.
1549 ///
1550 /// # Panics
1551 ///
1552 /// Panics if `index > len`.
1553 ///
1554 /// # Examples
1555 ///
1556 /// ```
1557 /// let mut vec = vec![1, 2, 3];
1558 /// vec.insert(1, 4);
1559 /// assert_eq!(vec, [1, 4, 2, 3]);
1560 /// vec.insert(4, 5);
1561 /// assert_eq!(vec, [1, 4, 2, 3, 5]);
1562 /// ```
1563 #[cfg(not(no_global_oom_handling))]
1564 #[stable(feature = "rust1", since = "1.0.0")]
1565 pub fn insert(&mut self, index: usize, element: T) {
1566 #[cold]
1567 #[inline(never)]
1568 fn assert_failed(index: usize, len: usize) -> ! {
1569 panic!("insertion index (is {index}) should be <= len (is {len})");
1570 }
1571
1572 let len = self.len();
1573
1574 // space for the new element
1575 if len == self.buf.capacity() {
1576 self.reserve(1);
1577 }
1578
1579 unsafe {
1580 // infallible
1581 // The spot to put the new value
1582 {
1583 let p = self.as_mut_ptr().add(index);
1584 if index < len {
1585 // Shift everything over to make space. (Duplicating the
1586 // `index`th element into two consecutive places.)
1587 ptr::copy(p, p.add(1), len - index);
1588 } else if index == len {
1589 // No elements need shifting.
1590 } else {
1591 assert_failed(index, len);
1592 }
1593 // Write it in, overwriting the first copy of the `index`th
1594 // element.
1595 ptr::write(p, element);
1596 }
1597 self.set_len(len + 1);
1598 }
1599 }
1600
1601 /// Removes and returns the element at position `index` within the vector,
1602 /// shifting all elements after it to the left.
1603 ///
1604 /// Note: Because this shifts over the remaining elements, it has a
1605 /// worst-case performance of *O*(*n*). If you don't need the order of elements
1606 /// to be preserved, use [`swap_remove`] instead. If you'd like to remove
1607 /// elements from the beginning of the `Vec`, consider using
1608 /// [`VecDeque::pop_front`] instead.
1609 ///
1610 /// [`swap_remove`]: Vec::swap_remove
1611 /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
1612 ///
1613 /// # Panics
1614 ///
1615 /// Panics if `index` is out of bounds.
1616 ///
1617 /// # Examples
1618 ///
1619 /// ```
1620 /// let mut v = vec![1, 2, 3];
1621 /// assert_eq!(v.remove(1), 2);
1622 /// assert_eq!(v, [1, 3]);
1623 /// ```
1624 #[stable(feature = "rust1", since = "1.0.0")]
1625 #[track_caller]
1626 pub fn remove(&mut self, index: usize) -> T {
1627 #[cold]
1628 #[inline(never)]
1629 #[track_caller]
1630 fn assert_failed(index: usize, len: usize) -> ! {
1631 panic!("removal index (is {index}) should be < len (is {len})");
1632 }
1633
1634 let len = self.len();
1635 if index >= len {
1636 assert_failed(index, len);
1637 }
1638 unsafe {
1639 // infallible
1640 let ret;
1641 {
1642 // the place we are taking from.
1643 let ptr = self.as_mut_ptr().add(index);
1644 // copy it out, unsafely having a copy of the value on
1645 // the stack and in the vector at the same time.
1646 ret = ptr::read(ptr);
1647
1648 // Shift everything down to fill in that spot.
1649 ptr::copy(ptr.add(1), ptr, len - index - 1);
1650 }
1651 self.set_len(len - 1);
1652 ret
1653 }
1654 }
1655
1656 /// Retains only the elements specified by the predicate.
1657 ///
1658 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
1659 /// This method operates in place, visiting each element exactly once in the
1660 /// original order, and preserves the order of the retained elements.
1661 ///
1662 /// # Examples
1663 ///
1664 /// ```
1665 /// let mut vec = vec![1, 2, 3, 4];
1666 /// vec.retain(|&x| x % 2 == 0);
1667 /// assert_eq!(vec, [2, 4]);
1668 /// ```
1669 ///
1670 /// Because the elements are visited exactly once in the original order,
1671 /// external state may be used to decide which elements to keep.
1672 ///
1673 /// ```
1674 /// let mut vec = vec![1, 2, 3, 4, 5];
1675 /// let keep = [false, true, true, false, true];
1676 /// let mut iter = keep.iter();
1677 /// vec.retain(|_| *iter.next().unwrap());
1678 /// assert_eq!(vec, [2, 3, 5]);
1679 /// ```
1680 #[stable(feature = "rust1", since = "1.0.0")]
1681 pub fn retain<F>(&mut self, mut f: F)
1682 where
1683 F: FnMut(&T) -> bool,
1684 {
1685 self.retain_mut(|elem| f(elem));
1686 }
1687
1688 /// Retains only the elements specified by the predicate, passing a mutable reference to it.
1689 ///
1690 /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
1691 /// This method operates in place, visiting each element exactly once in the
1692 /// original order, and preserves the order of the retained elements.
1693 ///
1694 /// # Examples
1695 ///
1696 /// ```
1697 /// let mut vec = vec![1, 2, 3, 4];
1698 /// vec.retain_mut(|x| if *x <= 3 {
1699 /// *x += 1;
1700 /// true
1701 /// } else {
1702 /// false
1703 /// });
1704 /// assert_eq!(vec, [2, 3, 4]);
1705 /// ```
1706 #[stable(feature = "vec_retain_mut", since = "1.61.0")]
1707 pub fn retain_mut<F>(&mut self, mut f: F)
1708 where
1709 F: FnMut(&mut T) -> bool,
1710 {
1711 let original_len = self.len();
1712 // Avoid double drop if the drop guard is not executed,
1713 // since we may make some holes during the process.
1714 unsafe { self.set_len(0) };
1715
1716 // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
1717 // |<- processed len ->| ^- next to check
1718 // |<- deleted cnt ->|
1719 // |<- original_len ->|
1720 // Kept: Elements which predicate returns true on.
1721 // Hole: Moved or dropped element slot.
1722 // Unchecked: Unchecked valid elements.
1723 //
1724 // This drop guard will be invoked when predicate or `drop` of element panicked.
1725 // It shifts unchecked elements to cover holes and `set_len` to the correct length.
1726 // In cases when predicate and `drop` never panick, it will be optimized out.
1727 struct BackshiftOnDrop<'a, T, A: Allocator> {
1728 v: &'a mut Vec<T, A>,
1729 processed_len: usize,
1730 deleted_cnt: usize,
1731 original_len: usize,
1732 }
1733
1734 impl<T, A: Allocator> Drop for BackshiftOnDrop<'_, T, A> {
1735 fn drop(&mut self) {
1736 if self.deleted_cnt > 0 {
1737 // SAFETY: Trailing unchecked items must be valid since we never touch them.
1738 unsafe {
1739 ptr::copy(
1740 self.v.as_ptr().add(self.processed_len),
1741 self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
1742 self.original_len - self.processed_len,
1743 );
1744 }
1745 }
1746 // SAFETY: After filling holes, all items are in contiguous memory.
1747 unsafe {
1748 self.v.set_len(self.original_len - self.deleted_cnt);
1749 }
1750 }
1751 }
1752
1753 let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };
1754
1755 fn process_loop<F, T, A: Allocator, const DELETED: bool>(
1756 original_len: usize,
1757 f: &mut F,
1758 g: &mut BackshiftOnDrop<'_, T, A>,
1759 ) where
1760 F: FnMut(&mut T) -> bool,
1761 {
1762 while g.processed_len != original_len {
1763 // SAFETY: Unchecked element must be valid.
1764 let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) };
1765 if !f(cur) {
1766 // Advance early to avoid double drop if `drop_in_place` panicked.
1767 g.processed_len += 1;
1768 g.deleted_cnt += 1;
1769 // SAFETY: We never touch this element again after dropped.
1770 unsafe { ptr::drop_in_place(cur) };
1771 // We already advanced the counter.
1772 if DELETED {
1773 continue;
1774 } else {
1775 break;
1776 }
1777 }
1778 if DELETED {
1779 // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
1780 // We use copy for move, and never touch this element again.
1781 unsafe {
1782 let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
1783 ptr::copy_nonoverlapping(cur, hole_slot, 1);
1784 }
1785 }
1786 g.processed_len += 1;
1787 }
1788 }
1789
1790 // Stage 1: Nothing was deleted.
1791 process_loop::<F, T, A, false>(original_len, &mut f, &mut g);
1792
1793 // Stage 2: Some elements were deleted.
1794 process_loop::<F, T, A, true>(original_len, &mut f, &mut g);
1795
1796 // All item are processed. This can be optimized to `set_len` by LLVM.
1797 drop(g);
1798 }
1799
1800 /// Removes all but the first of consecutive elements in the vector that resolve to the same
1801 /// key.
1802 ///
1803 /// If the vector is sorted, this removes all duplicates.
1804 ///
1805 /// # Examples
1806 ///
1807 /// ```
1808 /// let mut vec = vec![10, 20, 21, 30, 20];
1809 ///
1810 /// vec.dedup_by_key(|i| *i / 10);
1811 ///
1812 /// assert_eq!(vec, [10, 20, 30, 20]);
1813 /// ```
1814 #[stable(feature = "dedup_by", since = "1.16.0")]
1815 #[inline]
1816 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1817 where
1818 F: FnMut(&mut T) -> K,
1819 K: PartialEq,
1820 {
1821 self.dedup_by(|a, b| key(a) == key(b))
1822 }
1823
1824 /// Removes all but the first of consecutive elements in the vector satisfying a given equality
1825 /// relation.
1826 ///
1827 /// The `same_bucket` function is passed references to two elements from the vector and
1828 /// must determine if the elements compare equal. The elements are passed in opposite order
1829 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
1830 ///
1831 /// If the vector is sorted, this removes all duplicates.
1832 ///
1833 /// # Examples
1834 ///
1835 /// ```
1836 /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
1837 ///
1838 /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
1839 ///
1840 /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
1841 /// ```
1842 #[stable(feature = "dedup_by", since = "1.16.0")]
1843 pub fn dedup_by<F>(&mut self, mut same_bucket: F)
1844 where
1845 F: FnMut(&mut T, &mut T) -> bool,
1846 {
1847 let len = self.len();
1848 if len <= 1 {
1849 return;
1850 }
1851
1852 /* INVARIANT: vec.len() > read >= write > write-1 >= 0 */
1853 struct FillGapOnDrop<'a, T, A: core::alloc::Allocator> {
1854 /* Offset of the element we want to check if it is duplicate */
1855 read: usize,
1856
1857 /* Offset of the place where we want to place the non-duplicate
1858 * when we find it. */
1859 write: usize,
1860
1861 /* The Vec that would need correction if `same_bucket` panicked */
1862 vec: &'a mut Vec<T, A>,
1863 }
1864
1865 impl<'a, T, A: core::alloc::Allocator> Drop for FillGapOnDrop<'a, T, A> {
1866 fn drop(&mut self) {
1867 /* This code gets executed when `same_bucket` panics */
1868
1869 /* SAFETY: invariant guarantees that `read - write`
1870 * and `len - read` never overflow and that the copy is always
1871 * in-bounds. */
1872 unsafe {
1873 let ptr = self.vec.as_mut_ptr();
1874 let len = self.vec.len();
1875
1876 /* How many items were left when `same_bucket` panicked.
1877 * Basically vec[read..].len() */
1878 let items_left = len.wrapping_sub(self.read);
1879
1880 /* Pointer to first item in vec[write..write+items_left] slice */
1881 let dropped_ptr = ptr.add(self.write);
1882 /* Pointer to first item in vec[read..] slice */
1883 let valid_ptr = ptr.add(self.read);
1884
1885 /* Copy `vec[read..]` to `vec[write..write+items_left]`.
1886 * The slices can overlap, so `copy_nonoverlapping` cannot be used */
1887 ptr::copy(valid_ptr, dropped_ptr, items_left);
1888
1889 /* How many items have been already dropped
1890 * Basically vec[read..write].len() */
1891 let dropped = self.read.wrapping_sub(self.write);
1892
1893 self.vec.set_len(len - dropped);
1894 }
1895 }
1896 }
1897
1898 let mut gap = FillGapOnDrop { read: 1, write: 1, vec: self };
1899 let ptr = gap.vec.as_mut_ptr();
1900
1901 /* Drop items while going through Vec, it should be more efficient than
1902 * doing slice partition_dedup + truncate */
1903
1904 /* SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr
1905 * are always in-bounds and read_ptr never aliases prev_ptr */
1906 unsafe {
1907 while gap.read < len {
1908 let read_ptr = ptr.add(gap.read);
1909 let prev_ptr = ptr.add(gap.write.wrapping_sub(1));
1910
1911 if same_bucket(&mut *read_ptr, &mut *prev_ptr) {
1912 // Increase `gap.read` now since the drop may panic.
1913 gap.read += 1;
1914 /* We have found duplicate, drop it in-place */
1915 ptr::drop_in_place(read_ptr);
1916 } else {
1917 let write_ptr = ptr.add(gap.write);
1918
1919 /* Because `read_ptr` can be equal to `write_ptr`, we either
1920 * have to use `copy` or conditional `copy_nonoverlapping`.
1921 * Looks like the first option is faster. */
1922 ptr::copy(read_ptr, write_ptr, 1);
1923
1924 /* We have filled that place, so go further */
1925 gap.write += 1;
1926 gap.read += 1;
1927 }
1928 }
1929
1930 /* Technically we could let `gap` clean up with its Drop, but
1931 * when `same_bucket` is guaranteed to not panic, this bloats a little
1932 * the codegen, so we just do it manually */
1933 gap.vec.set_len(gap.write);
1934 mem::forget(gap);
1935 }
1936 }
1937
1938 /// Appends an element to the back of a collection.
1939 ///
1940 /// # Panics
1941 ///
1942 /// Panics if the new capacity exceeds `isize::MAX` bytes.
1943 ///
1944 /// # Examples
1945 ///
1946 /// ```
1947 /// let mut vec = vec![1, 2];
1948 /// vec.push(3);
1949 /// assert_eq!(vec, [1, 2, 3]);
1950 /// ```
1951 #[cfg(not(no_global_oom_handling))]
1952 #[inline]
1953 #[stable(feature = "rust1", since = "1.0.0")]
1954 pub fn push(&mut self, value: T) {
1955 // This will panic or abort if we would allocate > isize::MAX bytes
1956 // or if the length increment would overflow for zero-sized types.
1957 if self.len == self.buf.capacity() {
1958 self.buf.reserve_for_push(self.len);
1959 }
1960 unsafe {
1961 let end = self.as_mut_ptr().add(self.len);
1962 ptr::write(end, value);
1963 self.len += 1;
1964 }
1965 }
1966
1967 /// Tries to append an element to the back of a collection.
1968 ///
1969 /// # Examples
1970 ///
1971 /// ```
1972 /// let mut vec = vec![1, 2];
1973 /// vec.try_push(3).unwrap();
1974 /// assert_eq!(vec, [1, 2, 3]);
1975 /// ```
1976 #[inline]
1977 #[stable(feature = "kernel", since = "1.0.0")]
1978 pub fn try_push(&mut self, value: T) -> Result<(), TryReserveError> {
1979 if self.len == self.buf.capacity() {
1980 self.buf.try_reserve_for_push(self.len)?;
1981 }
1982 unsafe {
1983 let end = self.as_mut_ptr().add(self.len);
1984 ptr::write(end, value);
1985 self.len += 1;
1986 }
1987 Ok(())
1988 }
1989
1990 /// Appends an element if there is sufficient spare capacity, otherwise an error is returned
1991 /// with the element.
1992 ///
1993 /// Unlike [`push`] this method will not reallocate when there's insufficient capacity.
1994 /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity.
1995 ///
1996 /// [`push`]: Vec::push
1997 /// [`reserve`]: Vec::reserve
1998 /// [`try_reserve`]: Vec::try_reserve
1999 ///
2000 /// # Examples
2001 ///
2002 /// A manual, panic-free alternative to [`FromIterator`]:
2003 ///
2004 /// ```
2005 /// #![feature(vec_push_within_capacity)]
2006 ///
2007 /// use std::collections::TryReserveError;
2008 /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> {
2009 /// let mut vec = Vec::new();
2010 /// for value in iter {
2011 /// if let Err(value) = vec.push_within_capacity(value) {
2012 /// vec.try_reserve(1)?;
2013 /// // this cannot fail, the previous line either returned or added at least 1 free slot
2014 /// let _ = vec.push_within_capacity(value);
2015 /// }
2016 /// }
2017 /// Ok(vec)
2018 /// }
2019 /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100)));
2020 /// ```
2021 #[inline]
2022 #[unstable(feature = "vec_push_within_capacity", issue = "100486")]
2023 pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> {
2024 if self.len == self.buf.capacity() {
2025 return Err(value);
2026 }
2027 unsafe {
2028 let end = self.as_mut_ptr().add(self.len);
2029 ptr::write(end, value);
2030 self.len += 1;
2031 }
2032 Ok(())
2033 }
2034
2035 /// Removes the last element from a vector and returns it, or [`None`] if it
2036 /// is empty.
2037 ///
2038 /// If you'd like to pop the first element, consider using
2039 /// [`VecDeque::pop_front`] instead.
2040 ///
2041 /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2042 ///
2043 /// # Examples
2044 ///
2045 /// ```
2046 /// let mut vec = vec![1, 2, 3];
2047 /// assert_eq!(vec.pop(), Some(3));
2048 /// assert_eq!(vec, [1, 2]);
2049 /// ```
2050 #[inline]
2051 #[stable(feature = "rust1", since = "1.0.0")]
2052 pub fn pop(&mut self) -> Option<T> {
2053 if self.len == 0 {
2054 None
2055 } else {
2056 unsafe {
2057 self.len -= 1;
2058 Some(ptr::read(self.as_ptr().add(self.len())))
2059 }
2060 }
2061 }
2062
2063 /// Moves all the elements of `other` into `self`, leaving `other` empty.
2064 ///
2065 /// # Panics
2066 ///
2067 /// Panics if the new capacity exceeds `isize::MAX` bytes.
2068 ///
2069 /// # Examples
2070 ///
2071 /// ```
2072 /// let mut vec = vec![1, 2, 3];
2073 /// let mut vec2 = vec![4, 5, 6];
2074 /// vec.append(&mut vec2);
2075 /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
2076 /// assert_eq!(vec2, []);
2077 /// ```
2078 #[cfg(not(no_global_oom_handling))]
2079 #[inline]
2080 #[stable(feature = "append", since = "1.4.0")]
2081 pub fn append(&mut self, other: &mut Self) {
2082 unsafe {
2083 self.append_elements(other.as_slice() as _);
2084 other.set_len(0);
2085 }
2086 }
2087
2088 /// Appends elements to `self` from other buffer.
2089 #[cfg(not(no_global_oom_handling))]
2090 #[inline]
2091 unsafe fn append_elements(&mut self, other: *const [T]) {
2092 let count = unsafe { (*other).len() };
2093 self.reserve(count);
2094 let len = self.len();
2095 unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) };
2096 self.len += count;
2097 }
2098
2099 /// Tries to append elements to `self` from other buffer.
2100 #[inline]
2101 unsafe fn try_append_elements(&mut self, other: *const [T]) -> Result<(), TryReserveError> {
2102 let count = unsafe { (*other).len() };
2103 self.try_reserve(count)?;
2104 let len = self.len();
2105 unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) };
2106 self.len += count;
2107 Ok(())
2108 }
2109
2110 /// Removes the specified range from the vector in bulk, returning all
2111 /// removed elements as an iterator. If the iterator is dropped before
2112 /// being fully consumed, it drops the remaining removed elements.
2113 ///
2114 /// The returned iterator keeps a mutable borrow on the vector to optimize
2115 /// its implementation.
2116 ///
2117 /// # Panics
2118 ///
2119 /// Panics if the starting point is greater than the end point or if
2120 /// the end point is greater than the length of the vector.
2121 ///
2122 /// # Leaking
2123 ///
2124 /// If the returned iterator goes out of scope without being dropped (due to
2125 /// [`mem::forget`], for example), the vector may have lost and leaked
2126 /// elements arbitrarily, including elements outside the range.
2127 ///
2128 /// # Examples
2129 ///
2130 /// ```
2131 /// let mut v = vec![1, 2, 3];
2132 /// let u: Vec<_> = v.drain(1..).collect();
2133 /// assert_eq!(v, &[1]);
2134 /// assert_eq!(u, &[2, 3]);
2135 ///
2136 /// // A full range clears the vector, like `clear()` does
2137 /// v.drain(..);
2138 /// assert_eq!(v, &[]);
2139 /// ```
2140 #[stable(feature = "drain", since = "1.6.0")]
2141 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
2142 where
2143 R: RangeBounds<usize>,
2144 {
2145 // Memory safety
2146 //
2147 // When the Drain is first created, it shortens the length of
2148 // the source vector to make sure no uninitialized or moved-from elements
2149 // are accessible at all if the Drain's destructor never gets to run.
2150 //
2151 // Drain will ptr::read out the values to remove.
2152 // When finished, remaining tail of the vec is copied back to cover
2153 // the hole, and the vector length is restored to the new length.
2154 //
2155 let len = self.len();
2156 let Range { start, end } = slice::range(range, ..len);
2157
2158 unsafe {
2159 // set self.vec length's to start, to be safe in case Drain is leaked
2160 self.set_len(start);
2161 let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
2162 Drain {
2163 tail_start: end,
2164 tail_len: len - end,
2165 iter: range_slice.iter(),
2166 vec: NonNull::from(self),
2167 }
2168 }
2169 }
2170
2171 /// Clears the vector, removing all values.
2172 ///
2173 /// Note that this method has no effect on the allocated capacity
2174 /// of the vector.
2175 ///
2176 /// # Examples
2177 ///
2178 /// ```
2179 /// let mut v = vec![1, 2, 3];
2180 ///
2181 /// v.clear();
2182 ///
2183 /// assert!(v.is_empty());
2184 /// ```
2185 #[inline]
2186 #[stable(feature = "rust1", since = "1.0.0")]
2187 pub fn clear(&mut self) {
2188 let elems: *mut [T] = self.as_mut_slice();
2189
2190 // SAFETY:
2191 // - `elems` comes directly from `as_mut_slice` and is therefore valid.
2192 // - Setting `self.len` before calling `drop_in_place` means that,
2193 // if an element's `Drop` impl panics, the vector's `Drop` impl will
2194 // do nothing (leaking the rest of the elements) instead of dropping
2195 // some twice.
2196 unsafe {
2197 self.len = 0;
2198 ptr::drop_in_place(elems);
2199 }
2200 }
2201
2202 /// Returns the number of elements in the vector, also referred to
2203 /// as its 'length'.
2204 ///
2205 /// # Examples
2206 ///
2207 /// ```
2208 /// let a = vec![1, 2, 3];
2209 /// assert_eq!(a.len(), 3);
2210 /// ```
2211 #[inline]
2212 #[stable(feature = "rust1", since = "1.0.0")]
2213 pub fn len(&self) -> usize {
2214 self.len
2215 }
2216
2217 /// Returns `true` if the vector contains no elements.
2218 ///
2219 /// # Examples
2220 ///
2221 /// ```
2222 /// let mut v = Vec::new();
2223 /// assert!(v.is_empty());
2224 ///
2225 /// v.push(1);
2226 /// assert!(!v.is_empty());
2227 /// ```
2228 #[stable(feature = "rust1", since = "1.0.0")]
2229 pub fn is_empty(&self) -> bool {
2230 self.len() == 0
2231 }
2232
2233 /// Splits the collection into two at the given index.
2234 ///
2235 /// Returns a newly allocated vector containing the elements in the range
2236 /// `[at, len)`. After the call, the original vector will be left containing
2237 /// the elements `[0, at)` with its previous capacity unchanged.
2238 ///
2239 /// # Panics
2240 ///
2241 /// Panics if `at > len`.
2242 ///
2243 /// # Examples
2244 ///
2245 /// ```
2246 /// let mut vec = vec![1, 2, 3];
2247 /// let vec2 = vec.split_off(1);
2248 /// assert_eq!(vec, [1]);
2249 /// assert_eq!(vec2, [2, 3]);
2250 /// ```
2251 #[cfg(not(no_global_oom_handling))]
2252 #[inline]
2253 #[must_use = "use `.truncate()` if you don't need the other half"]
2254 #[stable(feature = "split_off", since = "1.4.0")]
2255 pub fn split_off(&mut self, at: usize) -> Self
2256 where
2257 A: Clone,
2258 {
2259 #[cold]
2260 #[inline(never)]
2261 fn assert_failed(at: usize, len: usize) -> ! {
2262 panic!("`at` split index (is {at}) should be <= len (is {len})");
2263 }
2264
2265 if at > self.len() {
2266 assert_failed(at, self.len());
2267 }
2268
2269 if at == 0 {
2270 // the new vector can take over the original buffer and avoid the copy
2271 return mem::replace(
2272 self,
2273 Vec::with_capacity_in(self.capacity(), self.allocator().clone()),
2274 );
2275 }
2276
2277 let other_len = self.len - at;
2278 let mut other = Vec::with_capacity_in(other_len, self.allocator().clone());
2279
2280 // Unsafely `set_len` and copy items to `other`.
2281 unsafe {
2282 self.set_len(at);
2283 other.set_len(other_len);
2284
2285 ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
2286 }
2287 other
2288 }
2289
2290 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
2291 ///
2292 /// If `new_len` is greater than `len`, the `Vec` is extended by the
2293 /// difference, with each additional slot filled with the result of
2294 /// calling the closure `f`. The return values from `f` will end up
2295 /// in the `Vec` in the order they have been generated.
2296 ///
2297 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2298 ///
2299 /// This method uses a closure to create new values on every push. If
2300 /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you
2301 /// want to use the [`Default`] trait to generate values, you can
2302 /// pass [`Default::default`] as the second argument.
2303 ///
2304 /// # Examples
2305 ///
2306 /// ```
2307 /// let mut vec = vec![1, 2, 3];
2308 /// vec.resize_with(5, Default::default);
2309 /// assert_eq!(vec, [1, 2, 3, 0, 0]);
2310 ///
2311 /// let mut vec = vec![];
2312 /// let mut p = 1;
2313 /// vec.resize_with(4, || { p *= 2; p });
2314 /// assert_eq!(vec, [2, 4, 8, 16]);
2315 /// ```
2316 #[cfg(not(no_global_oom_handling))]
2317 #[stable(feature = "vec_resize_with", since = "1.33.0")]
2318 pub fn resize_with<F>(&mut self, new_len: usize, f: F)
2319 where
2320 F: FnMut() -> T,
2321 {
2322 let len = self.len();
2323 if new_len > len {
2324 self.extend_trusted(iter::repeat_with(f).take(new_len - len));
2325 } else {
2326 self.truncate(new_len);
2327 }
2328 }
2329
2330 /// Consumes and leaks the `Vec`, returning a mutable reference to the contents,
2331 /// `&'a mut [T]`. Note that the type `T` must outlive the chosen lifetime
2332 /// `'a`. If the type has only static references, or none at all, then this
2333 /// may be chosen to be `'static`.
2334 ///
2335 /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`,
2336 /// so the leaked allocation may include unused capacity that is not part
2337 /// of the returned slice.
2338 ///
2339 /// This function is mainly useful for data that lives for the remainder of
2340 /// the program's life. Dropping the returned reference will cause a memory
2341 /// leak.
2342 ///
2343 /// # Examples
2344 ///
2345 /// Simple usage:
2346 ///
2347 /// ```
2348 /// let x = vec![1, 2, 3];
2349 /// let static_ref: &'static mut [usize] = x.leak();
2350 /// static_ref[0] += 1;
2351 /// assert_eq!(static_ref, &[2, 2, 3]);
2352 /// ```
2353 #[stable(feature = "vec_leak", since = "1.47.0")]
2354 #[inline]
2355 pub fn leak<'a>(self) -> &'a mut [T]
2356 where
2357 A: 'a,
2358 {
2359 let mut me = ManuallyDrop::new(self);
2360 unsafe { slice::from_raw_parts_mut(me.as_mut_ptr(), me.len) }
2361 }
2362
2363 /// Returns the remaining spare capacity of the vector as a slice of
2364 /// `MaybeUninit<T>`.
2365 ///
2366 /// The returned slice can be used to fill the vector with data (e.g. by
2367 /// reading from a file) before marking the data as initialized using the
2368 /// [`set_len`] method.
2369 ///
2370 /// [`set_len`]: Vec::set_len
2371 ///
2372 /// # Examples
2373 ///
2374 /// ```
2375 /// // Allocate vector big enough for 10 elements.
2376 /// let mut v = Vec::with_capacity(10);
2377 ///
2378 /// // Fill in the first 3 elements.
2379 /// let uninit = v.spare_capacity_mut();
2380 /// uninit[0].write(0);
2381 /// uninit[1].write(1);
2382 /// uninit[2].write(2);
2383 ///
2384 /// // Mark the first 3 elements of the vector as being initialized.
2385 /// unsafe {
2386 /// v.set_len(3);
2387 /// }
2388 ///
2389 /// assert_eq!(&v, &[0, 1, 2]);
2390 /// ```
2391 #[stable(feature = "vec_spare_capacity", since = "1.60.0")]
2392 #[inline]
2393 pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
2394 // Note:
2395 // This method is not implemented in terms of `split_at_spare_mut`,
2396 // to prevent invalidation of pointers to the buffer.
2397 unsafe {
2398 slice::from_raw_parts_mut(
2399 self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
2400 self.buf.capacity() - self.len,
2401 )
2402 }
2403 }
2404
2405 /// Returns vector content as a slice of `T`, along with the remaining spare
2406 /// capacity of the vector as a slice of `MaybeUninit<T>`.
2407 ///
2408 /// The returned spare capacity slice can be used to fill the vector with data
2409 /// (e.g. by reading from a file) before marking the data as initialized using
2410 /// the [`set_len`] method.
2411 ///
2412 /// [`set_len`]: Vec::set_len
2413 ///
2414 /// Note that this is a low-level API, which should be used with care for
2415 /// optimization purposes. If you need to append data to a `Vec`
2416 /// you can use [`push`], [`extend`], [`extend_from_slice`],
2417 /// [`extend_from_within`], [`insert`], [`append`], [`resize`] or
2418 /// [`resize_with`], depending on your exact needs.
2419 ///
2420 /// [`push`]: Vec::push
2421 /// [`extend`]: Vec::extend
2422 /// [`extend_from_slice`]: Vec::extend_from_slice
2423 /// [`extend_from_within`]: Vec::extend_from_within
2424 /// [`insert`]: Vec::insert
2425 /// [`append`]: Vec::append
2426 /// [`resize`]: Vec::resize
2427 /// [`resize_with`]: Vec::resize_with
2428 ///
2429 /// # Examples
2430 ///
2431 /// ```
2432 /// #![feature(vec_split_at_spare)]
2433 ///
2434 /// let mut v = vec![1, 1, 2];
2435 ///
2436 /// // Reserve additional space big enough for 10 elements.
2437 /// v.reserve(10);
2438 ///
2439 /// let (init, uninit) = v.split_at_spare_mut();
2440 /// let sum = init.iter().copied().sum::<u32>();
2441 ///
2442 /// // Fill in the next 4 elements.
2443 /// uninit[0].write(sum);
2444 /// uninit[1].write(sum * 2);
2445 /// uninit[2].write(sum * 3);
2446 /// uninit[3].write(sum * 4);
2447 ///
2448 /// // Mark the 4 elements of the vector as being initialized.
2449 /// unsafe {
2450 /// let len = v.len();
2451 /// v.set_len(len + 4);
2452 /// }
2453 ///
2454 /// assert_eq!(&v, &[1, 1, 2, 4, 8, 12, 16]);
2455 /// ```
2456 #[unstable(feature = "vec_split_at_spare", issue = "81944")]
2457 #[inline]
2458 pub fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) {
2459 // SAFETY:
2460 // - len is ignored and so never changed
2461 let (init, spare, _) = unsafe { self.split_at_spare_mut_with_len() };
2462 (init, spare)
2463 }
2464
2465 /// Safety: changing returned .2 (&mut usize) is considered the same as calling `.set_len(_)`.
2466 ///
2467 /// This method provides unique access to all vec parts at once in `extend_from_within`.
2468 unsafe fn split_at_spare_mut_with_len(
2469 &mut self,
2470 ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) {
2471 let ptr = self.as_mut_ptr();
2472 // SAFETY:
2473 // - `ptr` is guaranteed to be valid for `self.len` elements
2474 // - but the allocation extends out to `self.buf.capacity()` elements, possibly
2475 // uninitialized
2476 let spare_ptr = unsafe { ptr.add(self.len) };
2477 let spare_ptr = spare_ptr.cast::<MaybeUninit<T>>();
2478 let spare_len = self.buf.capacity() - self.len;
2479
2480 // SAFETY:
2481 // - `ptr` is guaranteed to be valid for `self.len` elements
2482 // - `spare_ptr` is pointing one element past the buffer, so it doesn't overlap with `initialized`
2483 unsafe {
2484 let initialized = slice::from_raw_parts_mut(ptr, self.len);
2485 let spare = slice::from_raw_parts_mut(spare_ptr, spare_len);
2486
2487 (initialized, spare, &mut self.len)
2488 }
2489 }
2490}
2491
2492impl<T: Clone, A: Allocator> Vec<T, A> {
2493 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
2494 ///
2495 /// If `new_len` is greater than `len`, the `Vec` is extended by the
2496 /// difference, with each additional slot filled with `value`.
2497 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2498 ///
2499 /// This method requires `T` to implement [`Clone`],
2500 /// in order to be able to clone the passed value.
2501 /// If you need more flexibility (or want to rely on [`Default`] instead of
2502 /// [`Clone`]), use [`Vec::resize_with`].
2503 /// If you only need to resize to a smaller size, use [`Vec::truncate`].
2504 ///
2505 /// # Examples
2506 ///
2507 /// ```
2508 /// let mut vec = vec!["hello"];
2509 /// vec.resize(3, "world");
2510 /// assert_eq!(vec, ["hello", "world", "world"]);
2511 ///
2512 /// let mut vec = vec![1, 2, 3, 4];
2513 /// vec.resize(2, 0);
2514 /// assert_eq!(vec, [1, 2]);
2515 /// ```
2516 #[cfg(not(no_global_oom_handling))]
2517 #[stable(feature = "vec_resize", since = "1.5.0")]
2518 pub fn resize(&mut self, new_len: usize, value: T) {
2519 let len = self.len();
2520
2521 if new_len > len {
2522 self.extend_with(new_len - len, ExtendElement(value))
2523 } else {
2524 self.truncate(new_len);
2525 }
2526 }
2527
2528 /// Tries to resize the `Vec` in-place so that `len` is equal to `new_len`.
2529 ///
2530 /// If `new_len` is greater than `len`, the `Vec` is extended by the
2531 /// difference, with each additional slot filled with `value`.
2532 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2533 ///
2534 /// This method requires `T` to implement [`Clone`],
2535 /// in order to be able to clone the passed value.
2536 /// If you need more flexibility (or want to rely on [`Default`] instead of
2537 /// [`Clone`]), use [`Vec::resize_with`].
2538 /// If you only need to resize to a smaller size, use [`Vec::truncate`].
2539 ///
2540 /// # Examples
2541 ///
2542 /// ```
2543 /// let mut vec = vec!["hello"];
2544 /// vec.try_resize(3, "world").unwrap();
2545 /// assert_eq!(vec, ["hello", "world", "world"]);
2546 ///
2547 /// let mut vec = vec![1, 2, 3, 4];
2548 /// vec.try_resize(2, 0).unwrap();
2549 /// assert_eq!(vec, [1, 2]);
2550 ///
2551 /// let mut vec = vec![42];
2552 /// let result = vec.try_resize(usize::MAX, 0);
2553 /// assert!(result.is_err());
2554 /// ```
2555 #[stable(feature = "kernel", since = "1.0.0")]
2556 pub fn try_resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> {
2557 let len = self.len();
2558
2559 if new_len > len {
2560 self.try_extend_with(new_len - len, ExtendElement(value))
2561 } else {
2562 self.truncate(new_len);
2563 Ok(())
2564 }
2565 }
2566
2567 /// Clones and appends all elements in a slice to the `Vec`.
2568 ///
2569 /// Iterates over the slice `other`, clones each element, and then appends
2570 /// it to this `Vec`. The `other` slice is traversed in-order.
2571 ///
2572 /// Note that this function is same as [`extend`] except that it is
2573 /// specialized to work with slices instead. If and when Rust gets
2574 /// specialization this function will likely be deprecated (but still
2575 /// available).
2576 ///
2577 /// # Examples
2578 ///
2579 /// ```
2580 /// let mut vec = vec![1];
2581 /// vec.extend_from_slice(&[2, 3, 4]);
2582 /// assert_eq!(vec, [1, 2, 3, 4]);
2583 /// ```
2584 ///
2585 /// [`extend`]: Vec::extend
2586 #[cfg(not(no_global_oom_handling))]
2587 #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
2588 pub fn extend_from_slice(&mut self, other: &[T]) {
2589 self.spec_extend(other.iter())
2590 }
2591
2592 /// Tries to clone and append all elements in a slice to the `Vec`.
2593 ///
2594 /// Iterates over the slice `other`, clones each element, and then appends
2595 /// it to this `Vec`. The `other` slice is traversed in-order.
2596 ///
2597 /// Note that this function is same as [`extend`] except that it is
2598 /// specialized to work with slices instead. If and when Rust gets
2599 /// specialization this function will likely be deprecated (but still
2600 /// available).
2601 ///
2602 /// # Examples
2603 ///
2604 /// ```
2605 /// let mut vec = vec![1];
2606 /// vec.try_extend_from_slice(&[2, 3, 4]).unwrap();
2607 /// assert_eq!(vec, [1, 2, 3, 4]);
2608 /// ```
2609 ///
2610 /// [`extend`]: Vec::extend
2611 #[stable(feature = "kernel", since = "1.0.0")]
2612 pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError> {
2613 self.try_spec_extend(other.iter())
2614 }
2615
2616 /// Copies elements from `src` range to the end of the vector.
2617 ///
2618 /// # Panics
2619 ///
2620 /// Panics if the starting point is greater than the end point or if
2621 /// the end point is greater than the length of the vector.
2622 ///
2623 /// # Examples
2624 ///
2625 /// ```
2626 /// let mut vec = vec![0, 1, 2, 3, 4];
2627 ///
2628 /// vec.extend_from_within(2..);
2629 /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4]);
2630 ///
2631 /// vec.extend_from_within(..2);
2632 /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1]);
2633 ///
2634 /// vec.extend_from_within(4..8);
2635 /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1, 4, 2, 3, 4]);
2636 /// ```
2637 #[cfg(not(no_global_oom_handling))]
2638 #[stable(feature = "vec_extend_from_within", since = "1.53.0")]
2639 pub fn extend_from_within<R>(&mut self, src: R)
2640 where
2641 R: RangeBounds<usize>,
2642 {
2643 let range = slice::range(src, ..self.len());
2644 self.reserve(range.len());
2645
2646 // SAFETY:
2647 // - `slice::range` guarantees that the given range is valid for indexing self
2648 unsafe {
2649 self.spec_extend_from_within(range);
2650 }
2651 }
2652}
2653
2654impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
2655 /// Takes a `Vec<[T; N]>` and flattens it into a `Vec<T>`.
2656 ///
2657 /// # Panics
2658 ///
2659 /// Panics if the length of the resulting vector would overflow a `usize`.
2660 ///
2661 /// This is only possible when flattening a vector of arrays of zero-sized
2662 /// types, and thus tends to be irrelevant in practice. If
2663 /// `size_of::<T>() > 0`, this will never panic.
2664 ///
2665 /// # Examples
2666 ///
2667 /// ```
2668 /// #![feature(slice_flatten)]
2669 ///
2670 /// let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
2671 /// assert_eq!(vec.pop(), Some([7, 8, 9]));
2672 ///
2673 /// let mut flattened = vec.into_flattened();
2674 /// assert_eq!(flattened.pop(), Some(6));
2675 /// ```
2676 #[unstable(feature = "slice_flatten", issue = "95629")]
2677 pub fn into_flattened(self) -> Vec<T, A> {
2678 let (ptr, len, cap, alloc) = self.into_raw_parts_with_alloc();
2679 let (new_len, new_cap) = if T::IS_ZST {
2680 (len.checked_mul(N).expect("vec len overflow"), usize::MAX)
2681 } else {
2682 // SAFETY:
2683 // - `cap * N` cannot overflow because the allocation is already in
2684 // the address space.
2685 // - Each `[T; N]` has `N` valid elements, so there are `len * N`
2686 // valid elements in the allocation.
2687 unsafe { (len.unchecked_mul(N), cap.unchecked_mul(N)) }
2688 };
2689 // SAFETY:
2690 // - `ptr` was allocated by `self`
2691 // - `ptr` is well-aligned because `[T; N]` has the same alignment as `T`.
2692 // - `new_cap` refers to the same sized allocation as `cap` because
2693 // `new_cap * size_of::<T>()` == `cap * size_of::<[T; N]>()`
2694 // - `len` <= `cap`, so `len * N` <= `cap * N`.
2695 unsafe { Vec::<T, A>::from_raw_parts_in(ptr.cast(), new_len, new_cap, alloc) }
2696 }
2697}
2698
2699// This code generalizes `extend_with_{element,default}`.
2700trait ExtendWith<T> {
2701 fn next(&mut self) -> T;
2702 fn last(self) -> T;
2703}
2704
2705struct ExtendElement<T>(T);
2706impl<T: Clone> ExtendWith<T> for ExtendElement<T> {
2707 fn next(&mut self) -> T {
2708 self.0.clone()
2709 }
2710 fn last(self) -> T {
2711 self.0
2712 }
2713}
2714
2715impl<T, A: Allocator> Vec<T, A> {
2716 #[cfg(not(no_global_oom_handling))]
2717 /// Extend the vector by `n` values, using the given generator.
2718 fn extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) {
2719 self.reserve(n);
2720
2721 unsafe {
2722 let mut ptr = self.as_mut_ptr().add(self.len());
2723 // Use SetLenOnDrop to work around bug where compiler
2724 // might not realize the store through `ptr` through self.set_len()
2725 // don't alias.
2726 let mut local_len = SetLenOnDrop::new(&mut self.len);
2727
2728 // Write all elements except the last one
2729 for _ in 1..n {
2730 ptr::write(ptr, value.next());
2731 ptr = ptr.add(1);
2732 // Increment the length in every step in case next() panics
2733 local_len.increment_len(1);
2734 }
2735
2736 if n > 0 {
2737 // We can write the last element directly without cloning needlessly
2738 ptr::write(ptr, value.last());
2739 local_len.increment_len(1);
2740 }
2741
2742 // len set by scope guard
2743 }
2744 }
2745
2746 /// Try to extend the vector by `n` values, using the given generator.
2747 fn try_extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) -> Result<(), TryReserveError> {
2748 self.try_reserve(n)?;
2749
2750 unsafe {
2751 let mut ptr = self.as_mut_ptr().add(self.len());
2752 // Use SetLenOnDrop to work around bug where compiler
2753 // might not realize the store through `ptr` through self.set_len()
2754 // don't alias.
2755 let mut local_len = SetLenOnDrop::new(&mut self.len);
2756
2757 // Write all elements except the last one
2758 for _ in 1..n {
2759 ptr::write(ptr, value.next());
2760 ptr = ptr.add(1);
2761 // Increment the length in every step in case next() panics
2762 local_len.increment_len(1);
2763 }
2764
2765 if n > 0 {
2766 // We can write the last element directly without cloning needlessly
2767 ptr::write(ptr, value.last());
2768 local_len.increment_len(1);
2769 }
2770
2771 // len set by scope guard
2772 Ok(())
2773 }
2774 }
2775}
2776
2777impl<T: PartialEq, A: Allocator> Vec<T, A> {
2778 /// Removes consecutive repeated elements in the vector according to the
2779 /// [`PartialEq`] trait implementation.
2780 ///
2781 /// If the vector is sorted, this removes all duplicates.
2782 ///
2783 /// # Examples
2784 ///
2785 /// ```
2786 /// let mut vec = vec![1, 2, 2, 3, 2];
2787 ///
2788 /// vec.dedup();
2789 ///
2790 /// assert_eq!(vec, [1, 2, 3, 2]);
2791 /// ```
2792 #[stable(feature = "rust1", since = "1.0.0")]
2793 #[inline]
2794 pub fn dedup(&mut self) {
2795 self.dedup_by(|a, b| a == b)
2796 }
2797}
2798
2799////////////////////////////////////////////////////////////////////////////////
2800// Internal methods and functions
2801////////////////////////////////////////////////////////////////////////////////
2802
2803#[doc(hidden)]
2804#[cfg(not(no_global_oom_handling))]
2805#[stable(feature = "rust1", since = "1.0.0")]
2806pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
2807 <T as SpecFromElem>::from_elem(elem, n, Global)
2808}
2809
2810#[doc(hidden)]
2811#[cfg(not(no_global_oom_handling))]
2812#[unstable(feature = "allocator_api", issue = "32838")]
2813pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> {
2814 <T as SpecFromElem>::from_elem(elem, n, alloc)
2815}
2816
2817trait ExtendFromWithinSpec {
2818 /// # Safety
2819 ///
2820 /// - `src` needs to be valid index
2821 /// - `self.capacity() - self.len()` must be `>= src.len()`
2822 unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
2823}
2824
2825impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
2826 default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
2827 // SAFETY:
2828 // - len is increased only after initializing elements
2829 let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() };
2830
2831 // SAFETY:
2832 // - caller guarantees that src is a valid index
2833 let to_clone = unsafe { this.get_unchecked(src) };
2834
2835 iter::zip(to_clone, spare)
2836 .map(|(src, dst)| dst.write(src.clone()))
2837 // Note:
2838 // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len
2839 // - len is increased after each element to prevent leaks (see issue #82533)
2840 .for_each(|_| *len += 1);
2841 }
2842}
2843
2844impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
2845 unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
2846 let count = src.len();
2847 {
2848 let (init, spare) = self.split_at_spare_mut();
2849
2850 // SAFETY:
2851 // - caller guarantees that `src` is a valid index
2852 let source = unsafe { init.get_unchecked(src) };
2853
2854 // SAFETY:
2855 // - Both pointers are created from unique slice references (`&mut [_]`)
2856 // so they are valid and do not overlap.
2857 // - Elements are :Copy so it's OK to copy them, without doing
2858 // anything with the original values
2859 // - `count` is equal to the len of `source`, so source is valid for
2860 // `count` reads
2861 // - `.reserve(count)` guarantees that `spare.len() >= count` so spare
2862 // is valid for `count` writes
2863 unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) };
2864 }
2865
2866 // SAFETY:
2867 // - The elements were just initialized by `copy_nonoverlapping`
2868 self.len += count;
2869 }
2870}
2871
2872////////////////////////////////////////////////////////////////////////////////
2873// Common trait implementations for Vec
2874////////////////////////////////////////////////////////////////////////////////
2875
2876#[stable(feature = "rust1", since = "1.0.0")]
2877impl<T, A: Allocator> ops::Deref for Vec<T, A> {
2878 type Target = [T];
2879
2880 #[inline]
2881 fn deref(&self) -> &[T] {
2882 unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
2883 }
2884}
2885
2886#[stable(feature = "rust1", since = "1.0.0")]
2887impl<T, A: Allocator> ops::DerefMut for Vec<T, A> {
2888 #[inline]
2889 fn deref_mut(&mut self) -> &mut [T] {
2890 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
2891 }
2892}
2893
2894#[cfg(not(no_global_oom_handling))]
2895trait SpecCloneFrom {
2896 fn clone_from(this: &mut Self, other: &Self);
2897}
2898
2899#[cfg(not(no_global_oom_handling))]
2900impl<T: Clone, A: Allocator> SpecCloneFrom for Vec<T, A> {
2901 default fn clone_from(this: &mut Self, other: &Self) {
2902 // drop anything that will not be overwritten
2903 this.truncate(other.len());
2904
2905 // self.len <= other.len due to the truncate above, so the
2906 // slices here are always in-bounds.
2907 let (init, tail) = other.split_at(this.len());
2908
2909 // reuse the contained values' allocations/resources.
2910 this.clone_from_slice(init);
2911 this.extend_from_slice(tail);
2912 }
2913}
2914
2915#[cfg(not(no_global_oom_handling))]
2916impl<T: Copy, A: Allocator> SpecCloneFrom for Vec<T, A> {
2917 fn clone_from(this: &mut Self, other: &Self) {
2918 this.clear();
2919 this.extend_from_slice(other);
2920 }
2921}
2922
2923#[cfg(not(no_global_oom_handling))]
2924#[stable(feature = "rust1", since = "1.0.0")]
2925impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
2926 #[cfg(not(test))]
2927 fn clone(&self) -> Self {
2928 let alloc = self.allocator().clone();
2929 <[T]>::to_vec_in(&**self, alloc)
2930 }
2931
2932 // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
2933 // required for this method definition, is not available. Instead use the
2934 // `slice::to_vec` function which is only available with cfg(test)
2935 // NB see the slice::hack module in slice.rs for more information
2936 #[cfg(test)]
2937 fn clone(&self) -> Self {
2938 let alloc = self.allocator().clone();
2939 crate::slice::to_vec(&**self, alloc)
2940 }
2941
2942 fn clone_from(&mut self, other: &Self) {
2943 SpecCloneFrom::clone_from(self, other)
2944 }
2945}
2946
2947/// The hash of a vector is the same as that of the corresponding slice,
2948/// as required by the `core::borrow::Borrow` implementation.
2949///
2950/// ```
2951/// #![feature(build_hasher_simple_hash_one)]
2952/// use std::hash::BuildHasher;
2953///
2954/// let b = std::collections::hash_map::RandomState::new();
2955/// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09];
2956/// let s: &[u8] = &[0xa8, 0x3c, 0x09];
2957/// assert_eq!(b.hash_one(v), b.hash_one(s));
2958/// ```
2959#[stable(feature = "rust1", since = "1.0.0")]
2960impl<T: Hash, A: Allocator> Hash for Vec<T, A> {
2961 #[inline]
2962 fn hash<H: Hasher>(&self, state: &mut H) {
2963 Hash::hash(&**self, state)
2964 }
2965}
2966
2967#[stable(feature = "rust1", since = "1.0.0")]
2968#[rustc_on_unimplemented(
2969 message = "vector indices are of type `usize` or ranges of `usize`",
2970 label = "vector indices are of type `usize` or ranges of `usize`"
2971)]
2972impl<T, I: SliceIndex<[T]>, A: Allocator> Index<I> for Vec<T, A> {
2973 type Output = I::Output;
2974
2975 #[inline]
2976 fn index(&self, index: I) -> &Self::Output {
2977 Index::index(&**self, index)
2978 }
2979}
2980
2981#[stable(feature = "rust1", since = "1.0.0")]
2982#[rustc_on_unimplemented(
2983 message = "vector indices are of type `usize` or ranges of `usize`",
2984 label = "vector indices are of type `usize` or ranges of `usize`"
2985)]
2986impl<T, I: SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> {
2987 #[inline]
2988 fn index_mut(&mut self, index: I) -> &mut Self::Output {
2989 IndexMut::index_mut(&mut **self, index)
2990 }
2991}
2992
2993#[cfg(not(no_global_oom_handling))]
2994#[stable(feature = "rust1", since = "1.0.0")]
2995impl<T> FromIterator<T> for Vec<T> {
2996 #[inline]
2997 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
2998 <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter())
2999 }
3000}
3001
3002#[stable(feature = "rust1", since = "1.0.0")]
3003impl<T, A: Allocator> IntoIterator for Vec<T, A> {
3004 type Item = T;
3005 type IntoIter = IntoIter<T, A>;
3006
3007 /// Creates a consuming iterator, that is, one that moves each value out of
3008 /// the vector (from start to end). The vector cannot be used after calling
3009 /// this.
3010 ///
3011 /// # Examples
3012 ///
3013 /// ```
3014 /// let v = vec!["a".to_string(), "b".to_string()];
3015 /// let mut v_iter = v.into_iter();
3016 ///
3017 /// let first_element: Option<String> = v_iter.next();
3018 ///
3019 /// assert_eq!(first_element, Some("a".to_string()));
3020 /// assert_eq!(v_iter.next(), Some("b".to_string()));
3021 /// assert_eq!(v_iter.next(), None);
3022 /// ```
3023 #[inline]
3024 fn into_iter(self) -> Self::IntoIter {
3025 unsafe {
3026 let mut me = ManuallyDrop::new(self);
3027 let alloc = ManuallyDrop::new(ptr::read(me.allocator()));
3028 let begin = me.as_mut_ptr();
3029 let end = if T::IS_ZST {
3030 begin.wrapping_byte_add(me.len())
3031 } else {
3032 begin.add(me.len()) as *const T
3033 };
3034 let cap = me.buf.capacity();
3035 IntoIter {
3036 buf: NonNull::new_unchecked(begin),
3037 phantom: PhantomData,
3038 cap,
3039 alloc,
3040 ptr: begin,
3041 end,
3042 }
3043 }
3044 }
3045}
3046
3047#[stable(feature = "rust1", since = "1.0.0")]
3048impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> {
3049 type Item = &'a T;
3050 type IntoIter = slice::Iter<'a, T>;
3051
3052 fn into_iter(self) -> Self::IntoIter {
3053 self.iter()
3054 }
3055}
3056
3057#[stable(feature = "rust1", since = "1.0.0")]
3058impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> {
3059 type Item = &'a mut T;
3060 type IntoIter = slice::IterMut<'a, T>;
3061
3062 fn into_iter(self) -> Self::IntoIter {
3063 self.iter_mut()
3064 }
3065}
3066
3067#[cfg(not(no_global_oom_handling))]
3068#[stable(feature = "rust1", since = "1.0.0")]
3069impl<T, A: Allocator> Extend<T> for Vec<T, A> {
3070 #[inline]
3071 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
3072 <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
3073 }
3074
3075 #[inline]
3076 fn extend_one(&mut self, item: T) {
3077 self.push(item);
3078 }
3079
3080 #[inline]
3081 fn extend_reserve(&mut self, additional: usize) {
3082 self.reserve(additional);
3083 }
3084}
3085
3086impl<T, A: Allocator> Vec<T, A> {
3087 // leaf method to which various SpecFrom/SpecExtend implementations delegate when
3088 // they have no further optimizations to apply
3089 #[cfg(not(no_global_oom_handling))]
3090 fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
3091 // This is the case for a general iterator.
3092 //
3093 // This function should be the moral equivalent of:
3094 //
3095 // for item in iterator {
3096 // self.push(item);
3097 // }
3098 while let Some(element) = iterator.next() {
3099 let len = self.len();
3100 if len == self.capacity() {
3101 let (lower, _) = iterator.size_hint();
3102 self.reserve(lower.saturating_add(1));
3103 }
3104 unsafe {
3105 ptr::write(self.as_mut_ptr().add(len), element);
3106 // Since next() executes user code which can panic we have to bump the length
3107 // after each step.
3108 // NB can't overflow since we would have had to alloc the address space
3109 self.set_len(len + 1);
3110 }
3111 }
3112 }
3113
3114 // leaf method to which various SpecFrom/SpecExtend implementations delegate when
3115 // they have no further optimizations to apply
3116 fn try_extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) -> Result<(), TryReserveError> {
3117 // This is the case for a general iterator.
3118 //
3119 // This function should be the moral equivalent of:
3120 //
3121 // for item in iterator {
3122 // self.push(item);
3123 // }
3124 while let Some(element) = iterator.next() {
3125 let len = self.len();
3126 if len == self.capacity() {
3127 let (lower, _) = iterator.size_hint();
3128 self.try_reserve(lower.saturating_add(1))?;
3129 }
3130 unsafe {
3131 ptr::write(self.as_mut_ptr().add(len), element);
3132 // Since next() executes user code which can panic we have to bump the length
3133 // after each step.
3134 // NB can't overflow since we would have had to alloc the address space
3135 self.set_len(len + 1);
3136 }
3137 }
3138
3139 Ok(())
3140 }
3141
3142 // specific extend for `TrustedLen` iterators, called both by the specializations
3143 // and internal places where resolving specialization makes compilation slower
3144 #[cfg(not(no_global_oom_handling))]
3145 fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
3146 let (low, high) = iterator.size_hint();
3147 if let Some(additional) = high {
3148 debug_assert_eq!(
3149 low,
3150 additional,
3151 "TrustedLen iterator's size hint is not exact: {:?}",
3152 (low, high)
3153 );
3154 self.reserve(additional);
3155 unsafe {
3156 let ptr = self.as_mut_ptr();
3157 let mut local_len = SetLenOnDrop::new(&mut self.len);
3158 iterator.for_each(move |element| {
3159 ptr::write(ptr.add(local_len.current_len()), element);
3160 // Since the loop executes user code which can panic we have to update
3161 // the length every step to correctly drop what we've written.
3162 // NB can't overflow since we would have had to alloc the address space
3163 local_len.increment_len(1);
3164 });
3165 }
3166 } else {
3167 // Per TrustedLen contract a `None` upper bound means that the iterator length
3168 // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway.
3169 // Since the other branch already panics eagerly (via `reserve()`) we do the same here.
3170 // This avoids additional codegen for a fallback code path which would eventually
3171 // panic anyway.
3172 panic!("capacity overflow");
3173 }
3174 }
3175
3176 // specific extend for `TrustedLen` iterators, called both by the specializations
3177 // and internal places where resolving specialization makes compilation slower
3178 fn try_extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) -> Result<(), TryReserveError> {
3179 let (low, high) = iterator.size_hint();
3180 if let Some(additional) = high {
3181 debug_assert_eq!(
3182 low,
3183 additional,
3184 "TrustedLen iterator's size hint is not exact: {:?}",
3185 (low, high)
3186 );
3187 self.try_reserve(additional)?;
3188 unsafe {
3189 let ptr = self.as_mut_ptr();
3190 let mut local_len = SetLenOnDrop::new(&mut self.len);
3191 iterator.for_each(move |element| {
3192 ptr::write(ptr.add(local_len.current_len()), element);
3193 // Since the loop executes user code which can panic we have to update
3194 // the length every step to correctly drop what we've written.
3195 // NB can't overflow since we would have had to alloc the address space
3196 local_len.increment_len(1);
3197 });
3198 }
3199 Ok(())
3200 } else {
3201 Err(TryReserveErrorKind::CapacityOverflow.into())
3202 }
3203 }
3204
3205 /// Creates a splicing iterator that replaces the specified range in the vector
3206 /// with the given `replace_with` iterator and yields the removed items.
3207 /// `replace_with` does not need to be the same length as `range`.
3208 ///
3209 /// `range` is removed even if the iterator is not consumed until the end.
3210 ///
3211 /// It is unspecified how many elements are removed from the vector
3212 /// if the `Splice` value is leaked.
3213 ///
3214 /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
3215 ///
3216 /// This is optimal if:
3217 ///
3218 /// * The tail (elements in the vector after `range`) is empty,
3219 /// * or `replace_with` yields fewer or equal elements than `range`’s length
3220 /// * or the lower bound of its `size_hint()` is exact.
3221 ///
3222 /// Otherwise, a temporary vector is allocated and the tail is moved twice.
3223 ///
3224 /// # Panics
3225 ///
3226 /// Panics if the starting point is greater than the end point or if
3227 /// the end point is greater than the length of the vector.
3228 ///
3229 /// # Examples
3230 ///
3231 /// ```
3232 /// let mut v = vec![1, 2, 3, 4];
3233 /// let new = [7, 8, 9];
3234 /// let u: Vec<_> = v.splice(1..3, new).collect();
3235 /// assert_eq!(v, &[1, 7, 8, 9, 4]);
3236 /// assert_eq!(u, &[2, 3]);
3237 /// ```
3238 #[cfg(not(no_global_oom_handling))]
3239 #[inline]
3240 #[stable(feature = "vec_splice", since = "1.21.0")]
3241 pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
3242 where
3243 R: RangeBounds<usize>,
3244 I: IntoIterator<Item = T>,
3245 {
3246 Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
3247 }
3248
3249 /// Creates an iterator which uses a closure to determine if an element should be removed.
3250 ///
3251 /// If the closure returns true, then the element is removed and yielded.
3252 /// If the closure returns false, the element will remain in the vector and will not be yielded
3253 /// by the iterator.
3254 ///
3255 /// Using this method is equivalent to the following code:
3256 ///
3257 /// ```
3258 /// # let some_predicate = |x: &mut i32| { *x == 2 || *x == 3 || *x == 6 };
3259 /// # let mut vec = vec![1, 2, 3, 4, 5, 6];
3260 /// let mut i = 0;
3261 /// while i < vec.len() {
3262 /// if some_predicate(&mut vec[i]) {
3263 /// let val = vec.remove(i);
3264 /// // your code here
3265 /// } else {
3266 /// i += 1;
3267 /// }
3268 /// }
3269 ///
3270 /// # assert_eq!(vec, vec![1, 4, 5]);
3271 /// ```
3272 ///
3273 /// But `drain_filter` is easier to use. `drain_filter` is also more efficient,
3274 /// because it can backshift the elements of the array in bulk.
3275 ///
3276 /// Note that `drain_filter` also lets you mutate every element in the filter closure,
3277 /// regardless of whether you choose to keep or remove it.
3278 ///
3279 /// # Examples
3280 ///
3281 /// Splitting an array into evens and odds, reusing the original allocation:
3282 ///
3283 /// ```
3284 /// #![feature(drain_filter)]
3285 /// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];
3286 ///
3287 /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
3288 /// let odds = numbers;
3289 ///
3290 /// assert_eq!(evens, vec![2, 4, 6, 8, 14]);
3291 /// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]);
3292 /// ```
3293 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
3294 pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F, A>
3295 where
3296 F: FnMut(&mut T) -> bool,
3297 {
3298 let old_len = self.len();
3299
3300 // Guard against us getting leaked (leak amplification)
3301 unsafe {
3302 self.set_len(0);
3303 }
3304
3305 DrainFilter { vec: self, idx: 0, del: 0, old_len, pred: filter, panic_flag: false }
3306 }
3307}
3308
3309/// Extend implementation that copies elements out of references before pushing them onto the Vec.
3310///
3311/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
3312/// append the entire slice at once.
3313///
3314/// [`copy_from_slice`]: slice::copy_from_slice
3315#[cfg(not(no_global_oom_handling))]
3316#[stable(feature = "extend_ref", since = "1.2.0")]
3317impl<'a, T: Copy + 'a, A: Allocator + 'a> Extend<&'a T> for Vec<T, A> {
3318 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
3319 self.spec_extend(iter.into_iter())
3320 }
3321
3322 #[inline]
3323 fn extend_one(&mut self, &item: &'a T) {
3324 self.push(item);
3325 }
3326
3327 #[inline]
3328 fn extend_reserve(&mut self, additional: usize) {
3329 self.reserve(additional);
3330 }
3331}
3332
3333/// Implements comparison of vectors, [lexicographically](core::cmp::Ord#lexicographical-comparison).
3334#[stable(feature = "rust1", since = "1.0.0")]
3335impl<T: PartialOrd, A: Allocator> PartialOrd for Vec<T, A> {
3336 #[inline]
3337 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
3338 PartialOrd::partial_cmp(&**self, &**other)
3339 }
3340}
3341
3342#[stable(feature = "rust1", since = "1.0.0")]
3343impl<T: Eq, A: Allocator> Eq for Vec<T, A> {}
3344
3345/// Implements ordering of vectors, [lexicographically](core::cmp::Ord#lexicographical-comparison).
3346#[stable(feature = "rust1", since = "1.0.0")]
3347impl<T: Ord, A: Allocator> Ord for Vec<T, A> {
3348 #[inline]
3349 fn cmp(&self, other: &Self) -> Ordering {
3350 Ord::cmp(&**self, &**other)
3351 }
3352}
3353
3354#[stable(feature = "rust1", since = "1.0.0")]
3355unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> {
3356 fn drop(&mut self) {
3357 unsafe {
3358 // use drop for [T]
3359 // use a raw slice to refer to the elements of the vector as weakest necessary type;
3360 // could avoid questions of validity in certain cases
3361 ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
3362 }
3363 // RawVec handles deallocation
3364 }
3365}
3366
3367#[stable(feature = "rust1", since = "1.0.0")]
3368#[rustc_const_unstable(feature = "const_default_impls", issue = "87864")]
3369impl<T> const Default for Vec<T> {
3370 /// Creates an empty `Vec<T>`.
3371 ///
3372 /// The vector will not allocate until elements are pushed onto it.
3373 fn default() -> Vec<T> {
3374 Vec::new()
3375 }
3376}
3377
3378#[stable(feature = "rust1", since = "1.0.0")]
3379impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
3380 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3381 fmt::Debug::fmt(&**self, f)
3382 }
3383}
3384
3385#[stable(feature = "rust1", since = "1.0.0")]
3386impl<T, A: Allocator> AsRef<Vec<T, A>> for Vec<T, A> {
3387 fn as_ref(&self) -> &Vec<T, A> {
3388 self
3389 }
3390}
3391
3392#[stable(feature = "vec_as_mut", since = "1.5.0")]
3393impl<T, A: Allocator> AsMut<Vec<T, A>> for Vec<T, A> {
3394 fn as_mut(&mut self) -> &mut Vec<T, A> {
3395 self
3396 }
3397}
3398
3399#[stable(feature = "rust1", since = "1.0.0")]
3400impl<T, A: Allocator> AsRef<[T]> for Vec<T, A> {
3401 fn as_ref(&self) -> &[T] {
3402 self
3403 }
3404}
3405
3406#[stable(feature = "vec_as_mut", since = "1.5.0")]
3407impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> {
3408 fn as_mut(&mut self) -> &mut [T] {
3409 self
3410 }
3411}
3412
3413#[cfg(not(no_global_oom_handling))]
3414#[stable(feature = "rust1", since = "1.0.0")]
3415impl<T: Clone> From<&[T]> for Vec<T> {
3416 /// Allocate a `Vec<T>` and fill it by cloning `s`'s items.
3417 ///
3418 /// # Examples
3419 ///
3420 /// ```
3421 /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);
3422 /// ```
3423 #[cfg(not(test))]
3424 fn from(s: &[T]) -> Vec<T> {
3425 s.to_vec()
3426 }
3427 #[cfg(test)]
3428 fn from(s: &[T]) -> Vec<T> {
3429 crate::slice::to_vec(s, Global)
3430 }
3431}
3432
3433#[cfg(not(no_global_oom_handling))]
3434#[stable(feature = "vec_from_mut", since = "1.19.0")]
3435impl<T: Clone> From<&mut [T]> for Vec<T> {
3436 /// Allocate a `Vec<T>` and fill it by cloning `s`'s items.
3437 ///
3438 /// # Examples
3439 ///
3440 /// ```
3441 /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]);
3442 /// ```
3443 #[cfg(not(test))]
3444 fn from(s: &mut [T]) -> Vec<T> {
3445 s.to_vec()
3446 }
3447 #[cfg(test)]
3448 fn from(s: &mut [T]) -> Vec<T> {
3449 crate::slice::to_vec(s, Global)
3450 }
3451}
3452
3453#[cfg(not(no_global_oom_handling))]
3454#[stable(feature = "vec_from_array", since = "1.44.0")]
3455impl<T, const N: usize> From<[T; N]> for Vec<T> {
3456 /// Allocate a `Vec<T>` and move `s`'s items into it.
3457 ///
3458 /// # Examples
3459 ///
3460 /// ```
3461 /// assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]);
3462 /// ```
3463 #[cfg(not(test))]
3464 fn from(s: [T; N]) -> Vec<T> {
3465 <[T]>::into_vec(
3466 #[rustc_box]
3467 Box::new(s),
3468 )
3469 }
3470
3471 #[cfg(test)]
3472 fn from(s: [T; N]) -> Vec<T> {
3473 crate::slice::into_vec(Box::new(s))
3474 }
3475}
3476
3477#[cfg(not(no_borrow))]
3478#[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
3479impl<'a, T> From<Cow<'a, [T]>> for Vec<T>
3480where
3481 [T]: ToOwned<Owned = Vec<T>>,
3482{
3483 /// Convert a clone-on-write slice into a vector.
3484 ///
3485 /// If `s` already owns a `Vec<T>`, it will be returned directly.
3486 /// If `s` is borrowing a slice, a new `Vec<T>` will be allocated and
3487 /// filled by cloning `s`'s items into it.
3488 ///
3489 /// # Examples
3490 ///
3491 /// ```
3492 /// # use std::borrow::Cow;
3493 /// let o: Cow<[i32]> = Cow::Owned(vec![1, 2, 3]);
3494 /// let b: Cow<[i32]> = Cow::Borrowed(&[1, 2, 3]);
3495 /// assert_eq!(Vec::from(o), Vec::from(b));
3496 /// ```
3497 fn from(s: Cow<'a, [T]>) -> Vec<T> {
3498 s.into_owned()
3499 }
3500}
3501
3502// note: test pulls in std, which causes errors here
3503#[cfg(not(test))]
3504#[stable(feature = "vec_from_box", since = "1.18.0")]
3505impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> {
3506 /// Convert a boxed slice into a vector by transferring ownership of
3507 /// the existing heap allocation.
3508 ///
3509 /// # Examples
3510 ///
3511 /// ```
3512 /// let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice();
3513 /// assert_eq!(Vec::from(b), vec![1, 2, 3]);
3514 /// ```
3515 fn from(s: Box<[T], A>) -> Self {
3516 s.into_vec()
3517 }
3518}
3519
3520// note: test pulls in std, which causes errors here
3521#[cfg(not(no_global_oom_handling))]
3522#[cfg(not(test))]
3523#[stable(feature = "box_from_vec", since = "1.20.0")]
3524impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> {
3525 /// Convert a vector into a boxed slice.
3526 ///
3527 /// If `v` has excess capacity, its items will be moved into a
3528 /// newly-allocated buffer with exactly the right capacity.
3529 ///
3530 /// # Examples
3531 ///
3532 /// ```
3533 /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice());
3534 /// ```
3535 ///
3536 /// Any excess capacity is removed:
3537 /// ```
3538 /// let mut vec = Vec::with_capacity(10);
3539 /// vec.extend([1, 2, 3]);
3540 ///
3541 /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice());
3542 /// ```
3543 fn from(v: Vec<T, A>) -> Self {
3544 v.into_boxed_slice()
3545 }
3546}
3547
3548#[cfg(not(no_global_oom_handling))]
3549#[stable(feature = "rust1", since = "1.0.0")]
3550impl From<&str> for Vec<u8> {
3551 /// Allocate a `Vec<u8>` and fill it with a UTF-8 string.
3552 ///
3553 /// # Examples
3554 ///
3555 /// ```
3556 /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);
3557 /// ```
3558 fn from(s: &str) -> Vec<u8> {
3559 From::from(s.as_bytes())
3560 }
3561}
3562
3563#[stable(feature = "array_try_from_vec", since = "1.48.0")]
3564impl<T, A: Allocator, const N: usize> TryFrom<Vec<T, A>> for [T; N] {
3565 type Error = Vec<T, A>;
3566
3567 /// Gets the entire contents of the `Vec<T>` as an array,
3568 /// if its size exactly matches that of the requested array.
3569 ///
3570 /// # Examples
3571 ///
3572 /// ```
3573 /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3]));
3574 /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([]));
3575 /// ```
3576 ///
3577 /// If the length doesn't match, the input comes back in `Err`:
3578 /// ```
3579 /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into();
3580 /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
3581 /// ```
3582 ///
3583 /// If you're fine with just getting a prefix of the `Vec<T>`,
3584 /// you can call [`.truncate(N)`](Vec::truncate) first.
3585 /// ```
3586 /// let mut v = String::from("hello world").into_bytes();
3587 /// v.sort();
3588 /// v.truncate(2);
3589 /// let [a, b]: [_; 2] = v.try_into().unwrap();
3590 /// assert_eq!(a, b' ');
3591 /// assert_eq!(b, b'd');
3592 /// ```
3593 fn try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>> {
3594 if vec.len() != N {
3595 return Err(vec);
3596 }
3597
3598 // SAFETY: `.set_len(0)` is always sound.
3599 unsafe { vec.set_len(0) };
3600
3601 // SAFETY: A `Vec`'s pointer is always aligned properly, and
3602 // the alignment the array needs is the same as the items.
3603 // We checked earlier that we have sufficient items.
3604 // The items will not double-drop as the `set_len`
3605 // tells the `Vec` not to also drop them.
3606 let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) };
3607 Ok(array)
3608 }
3609}