Skip to main content

alloc/vec/
mod.rs

1//! A contiguous growable array type with heap-allocated contents, written
2//! `Vec<T>`.
3//!
4//! Vectors have *O*(1) indexing, amortized *O*(1) push (to the end) and
5//! *O*(1) pop (from the end).
6//!
7//! Vectors ensure they never allocate more than `isize::MAX` bytes.
8//!
9//! # Examples
10//!
11//! You can explicitly create a [`Vec`] with [`Vec::new`]:
12//!
13//! ```
14//! let v: Vec<i32> = Vec::new();
15//! ```
16//!
17//! ...or by using the [`vec!`] macro:
18//!
19//! ```
20//! let v: Vec<i32> = vec![];
21//!
22//! let v = vec![1, 2, 3, 4, 5];
23//!
24//! let v = vec![0; 10]; // ten zeroes
25//! ```
26//!
27//! You can [`push`] values onto the end of a vector (which will grow the vector
28//! as needed):
29//!
30//! ```
31//! let mut v = vec![1, 2];
32//!
33//! v.push(3);
34//! ```
35//!
36//! Popping values works in much the same way:
37//!
38//! ```
39//! let mut v = vec![1, 2];
40//!
41//! let two = v.pop();
42//! ```
43//!
44//! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits):
45//!
46//! ```
47//! let mut v = vec![1, 2, 3];
48//! let three = v[2];
49//! v[1] = v[1] + 5;
50//! ```
51//!
52//! # Memory layout
53//!
54//! A [`Vec`] conceptually consists of a raw pointer `ptr` to the start of the allocation, a
55//! length `len`, a capacity `cap`, and an allocator `alloc`.
56//! While the exact fields and their order are not specified, a [`Vec`] can be converted to and
57//! from these parts using [`Vec::into_raw_parts_with_allocator`], [`Vec::from_raw_parts_in`],
58//! [`Vec::into_raw_parts`], and [`Vec::from_raw_parts`], as well as their [`NonNull`]-based
59//! versions.
60//!
61//! The parts of a [`Vec`] have the following invariants:
62//!
63//! * If [`size_of::<T>()`](size_of) and `cap` are non-zero, then:
64//!   - `ptr` must point to the start of a memory block [*currently allocated*] via `alloc`.
65//!   - [`Layout::array::<T>(cap)`] must [*fit*] the memory block of `ptr`. In particular,
66//!     * `T` must have the same alignment as the [`Layout`] `ptr` was allocated with, and
67//!     * `size_of::<T>() * cap` must be at least the size of the [`Layout`] `ptr` was
68//!       allocated with, and at most the size of the allocation returned the allocator.
69//!   - `size_of::<T>() * cap` must be at most [`isize::MAX`].
70//!     See the safety documentation of [`pointer::offset`].
71//! * If [`size_of::<T>()`](size_of) or `cap` is zero, then `ptr` must be any sufficiently aligned non-null pointer.
72//!
73//!   NOTE: `ptr` will not be passed to the allocator for deallocation by the destructor of [`Vec`]
74//!   in this case. Thus, it is unwise to use a pointer acquired from the allocator for this, as
75//!   overallocated memory may end up being leaked. Use [`ptr::dangling`] instead.
76//! * The following must always be satisfied:
77//!   - `len` needs to be less than or equal to `cap`.
78//!   - At `ptr`, there are at least `len` valid values of type `T`, laid out contiguously
79//!     (like an array). These values are considered owned by the [`Vec`].
80//!
81//! It is sound to create a [`Vec`] from parts that satisfy these invariants.
82//!
83//! Conversely, the memory backing `ptr` obtained from [`Vec::as_mut_ptr`] or
84//! [`Vec::into_raw_parts_with_allocator`]-like methods may be deallocated
85//! using the allocator, with layout [`Layout::array::<T>(cap)`], provided
86//! that [`size_of::<T>()`](size_of) or `cap` is non-zero.
87//! To automatically handle the case where the allocation is zero-sized,
88//! it is recommended to use [`Vec::from_raw_parts_in`], instead of manually
89//! deallocating.
90//!
91//! [*fit*]: crate::alloc::Allocator#memory-fitting
92//! [*currently allocated*]: crate::alloc::Allocator#currently-allocated-memory
93//! [`allocate`]: crate::alloc::Allocator::allocate
94//! [`push`]: Vec::push
95//! [`ptr::NonNull::dangling`]: NonNull::dangling
96//! [`Layout`]: crate::alloc::Layout
97//! [`Layout::array::<T>(cap)`]: crate::alloc::Layout::array
98
99#![stable(feature = "rust1", since = "1.0.0")]
100
101#[cfg(not(no_global_oom_handling))]
102use core::clone::TrivialClone;
103use core::cmp::Ordering;
104use core::hash::{Hash, Hasher};
105#[cfg(not(no_global_oom_handling))]
106use core::iter;
107use core::marker::{Destruct, Freeze, PhantomData};
108use core::mem::{self, Assume, ManuallyDrop, MaybeUninit, SizedTypeProperties, TransmuteFrom};
109use core::ops::{self, Index, IndexMut, Range, RangeBounds};
110use core::ptr::{self, NonNull};
111use core::slice::{self, SliceIndex};
112use core::{cmp, fmt, hint, intrinsics, ub_checks};
113
114#[stable(feature = "extract_if", since = "1.87.0")]
115pub use self::extract_if::ExtractIf;
116use crate::alloc::{Allocator, AllocatorNightly, Global};
117use crate::borrow::{Cow, ToOwned};
118use crate::boxed::Box;
119use crate::collections::TryReserveError;
120use crate::raw_vec::RawVec;
121
122mod extract_if;
123
124#[cfg(not(no_global_oom_handling))]
125#[stable(feature = "vec_splice", since = "1.21.0")]
126pub use self::splice::Splice;
127
128#[cfg(not(no_global_oom_handling))]
129mod splice;
130
131#[stable(feature = "drain", since = "1.6.0")]
132pub use self::drain::Drain;
133
134mod drain;
135
136#[cfg(not(no_global_oom_handling))]
137mod cow;
138
139#[cfg(not(no_global_oom_handling))]
140pub(crate) use self::in_place_collect::AsVecIntoIter;
141#[stable(feature = "rust1", since = "1.0.0")]
142pub use self::into_iter::IntoIter;
143
144mod into_iter;
145
146#[cfg(not(no_global_oom_handling))]
147use self::is_zero::IsZero;
148
149#[cfg(not(no_global_oom_handling))]
150mod is_zero;
151
152#[cfg(not(no_global_oom_handling))]
153mod in_place_collect;
154
155mod partial_eq;
156
157#[unstable(feature = "vec_peek_mut", issue = "122742")]
158pub use self::peek_mut::PeekMut;
159
160mod peek_mut;
161
162#[cfg(not(no_global_oom_handling))]
163use self::spec_from_elem::SpecFromElem;
164
165#[cfg(not(no_global_oom_handling))]
166mod spec_from_elem;
167
168#[cfg(not(no_global_oom_handling))]
169use self::set_len_on_drop::SetLenOnDrop;
170
171#[cfg(not(no_global_oom_handling))]
172mod set_len_on_drop;
173
174#[cfg(not(no_global_oom_handling))]
175use self::in_place_drop::{InPlaceDrop, InPlaceDstDataSrcBufDrop};
176
177#[cfg(not(no_global_oom_handling))]
178mod in_place_drop;
179
180#[cfg(not(no_global_oom_handling))]
181use self::spec_from_iter_nested::SpecFromIterNested;
182
183#[cfg(not(no_global_oom_handling))]
184mod spec_from_iter_nested;
185
186#[cfg(not(no_global_oom_handling))]
187use self::spec_from_iter::SpecFromIter;
188
189#[cfg(not(no_global_oom_handling))]
190mod spec_from_iter;
191
192#[cfg(not(no_global_oom_handling))]
193use self::spec_extend::SpecExtend;
194
195#[cfg(not(no_global_oom_handling))]
196mod spec_extend;
197
198#[cfg(not(no_global_oom_handling))]
199use self::spec_extend_with::SpecExtendWith;
200
201#[cfg(not(no_global_oom_handling))]
202mod spec_extend_with;
203
204#[cfg(all(target_arch = "aarch64", target_feature = "sve"))]
205mod sve_retain;
206
207/// A contiguous growable array type, written as `Vec<T>`, short for 'vector'.
208///
209/// # Examples
210///
211/// ```
212/// let mut vec = Vec::new();
213/// vec.push(1);
214/// vec.push(2);
215///
216/// assert_eq!(vec.len(), 2);
217/// assert_eq!(vec[0], 1);
218///
219/// assert_eq!(vec.pop(), Some(2));
220/// assert_eq!(vec.len(), 1);
221///
222/// vec[0] = 7;
223/// assert_eq!(vec[0], 7);
224///
225/// vec.extend([1, 2, 3]);
226///
227/// for x in &vec {
228///     println!("{x}");
229/// }
230/// assert_eq!(vec, [7, 1, 2, 3]);
231/// ```
232///
233/// The [`vec!`] macro is provided for convenient initialization:
234///
235/// ```
236/// let mut vec1 = vec![1, 2, 3];
237/// vec1.push(4);
238/// let vec2 = Vec::from([1, 2, 3, 4]);
239/// assert_eq!(vec1, vec2);
240/// ```
241///
242/// It can also initialize each element of a `Vec<T>` with a given value.
243/// This may be more efficient than performing allocation and initialization
244/// in separate steps, especially when initializing a vector of zeros:
245///
246/// ```
247/// let vec = vec![0; 5];
248/// assert_eq!(vec, [0, 0, 0, 0, 0]);
249///
250/// // The following is equivalent, but potentially slower:
251/// let mut vec = Vec::with_capacity(5);
252/// vec.resize(5, 0);
253/// assert_eq!(vec, [0, 0, 0, 0, 0]);
254/// ```
255///
256/// For more information, see
257/// [Capacity and Reallocation](#capacity-and-reallocation).
258///
259/// Use a `Vec<T>` as an efficient stack:
260///
261/// ```
262/// let mut stack = Vec::new();
263///
264/// stack.push(1);
265/// stack.push(2);
266/// stack.push(3);
267///
268/// while let Some(top) = stack.pop() {
269///     // Prints 3, 2, 1
270///     println!("{top}");
271/// }
272/// ```
273///
274/// # Indexing
275///
276/// The `Vec` type allows access to values by index, because it implements the
277/// [`Index`] trait. An example will be more explicit:
278///
279/// ```
280/// let v = vec![0, 2, 4, 6];
281/// println!("{}", v[1]); // it will display '2'
282/// ```
283///
284/// However be careful: if you try to access an index which isn't in the `Vec`,
285/// your software will panic! You cannot do this:
286///
287/// ```should_panic
288/// let v = vec![0, 2, 4, 6];
289/// println!("{}", v[6]); // it will panic!
290/// ```
291///
292/// Use [`get`] and [`get_mut`] if you want to check whether the index is in
293/// the `Vec`.
294///
295/// # Slicing
296///
297/// A `Vec` can be mutable. On the other hand, slices are read-only objects.
298/// To get a [slice][prim@slice], use [`&`]. Example:
299///
300/// ```
301/// fn read_slice(slice: &[usize]) {
302///     // ...
303/// }
304///
305/// let v = vec![0, 1];
306/// read_slice(&v);
307///
308/// // ... and that's all!
309/// // you can also do it like this:
310/// let u: &[usize] = &v;
311/// // or like this:
312/// let u: &[_] = &v;
313/// ```
314///
315/// In Rust, it's more common to pass slices as arguments rather than vectors
316/// when you just want to provide read access. The same goes for [`String`] and
317/// [`&str`].
318///
319/// # Capacity and reallocation
320///
321/// The capacity of a vector is the amount of space allocated for any future
322/// elements that will be added onto the vector. This is not to be confused with
323/// the *length* of a vector, which specifies the number of actual elements
324/// within the vector. If a vector's length exceeds its capacity, its capacity
325/// will automatically be increased, but its elements will have to be
326/// reallocated.
327///
328/// For example, a vector with capacity 10 and length 0 would be an empty vector
329/// with space for 10 more elements. Pushing 10 or fewer elements onto the
330/// vector will not change its capacity or cause reallocation to occur. However,
331/// if the vector's length is increased to 11, it will have to reallocate, which
332/// can be slow. For this reason, it is recommended to use [`Vec::with_capacity`]
333/// whenever possible to specify how big the vector is expected to get.
334///
335/// # Guarantees
336///
337/// The following section is to be read as an addendum of the
338/// [memory layout](self#memory-layout) section.
339///
340/// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees
341/// about its design. This ensures that it's as low-overhead as possible in
342/// the general case, and can be correctly manipulated in primitive ways
343/// by unsafe code.
344///
345/// A vector containing the elements `'a'` and `'b'` with capacity 4 can be
346/// visualized as below. The top part is the `Vec` struct, it contains a
347/// pointer to the head of the allocation in the heap, length and capacity.
348/// The bottom part is the allocation on the heap, a contiguous memory block.
349///
350/// ```text
351///             ptr      len  capacity
352///        +--------+--------+--------+
353///        | 0x0123 |      2 |      4 |
354///        +--------+--------+--------+
355///             |
356///             v
357/// Heap   +--------+--------+--------+--------+
358///        |    'a' |    'b' | uninit | uninit |
359///        +--------+--------+--------+--------+
360/// ```
361///
362/// - **uninit** represents memory that is not initialized, see [`MaybeUninit`].
363/// - Note: the ABI is not stable and `Vec` makes no guarantees about its memory
364///   layout (including the order of fields).
365///
366/// `Vec` will never perform a "small optimization" where elements are actually
367/// stored on the stack for two reasons:
368///
369/// * It would make it more difficult for unsafe code to correctly manipulate
370///   a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were
371///   only moved, and it would be more difficult to determine if a `Vec` had
372///   actually allocated memory.
373///
374/// * It would penalize the general case, incurring an additional branch
375///   on every access.
376///
377/// `Vec` will never automatically shrink itself, even if completely empty. This
378/// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec`
379/// and then filling it back up to the same [`len`] should incur no calls to
380/// the allocator. If you wish to free up unused memory, use
381/// [`shrink_to_fit`] or [`shrink_to`].
382///
383/// [`push`] and [`insert`] will never (re)allocate if the reported capacity is
384/// sufficient. [`push`] and [`insert`] *will* (re)allocate if
385/// <code>[len] == [capacity]</code>. That is, the reported capacity is completely
386/// accurate, and can be relied on. It can even be used to manually free the memory
387/// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even
388/// when not necessary.
389///
390/// `Vec` does not guarantee any particular growth strategy when reallocating
391/// when full, nor when [`reserve`] is called. The current strategy is basic
392/// and it may prove desirable to use a non-constant growth factor. Whatever
393/// strategy is used will of course guarantee *O*(1) amortized [`push`].
394///
395/// It is guaranteed, in order to respect the intentions of the programmer, that
396/// all of `vec![e_1, e_2, ..., e_n]`, `vec![x; n]`, and [`Vec::with_capacity(n)`] produce a `Vec`
397/// that requests an allocation of the exact size needed for precisely `n` elements from the allocator,
398/// and no other size (such as, for example: a size rounded up to the nearest power of 2).
399/// The allocator will return an allocation that is at least as large as requested, but it may be larger.
400///
401/// It is guaranteed that the [`Vec::capacity`] method returns a value that is at least the requested capacity
402/// and not more than the allocated capacity.
403///
404/// The method [`Vec::shrink_to_fit`] will attempt to discard excess capacity an allocator has given to a `Vec`.
405/// If <code>[len] == [capacity]</code>, then a `Vec<T>` can be converted
406/// to and from a [`Box<[T]>`][owned slice] without reallocating or moving the elements.
407/// `Vec` exploits this fact as much as reasonable when implementing common conversions
408/// such as [`into_boxed_slice`].
409///
410/// `Vec` will not specifically overwrite any data that is removed from it,
411/// but also won't specifically preserve it. Its uninitialized memory is
412/// scratch space that it may use however it wants. It will generally just do
413/// whatever is most efficient or otherwise easy to implement. Do not rely on
414/// removed data to be erased for security purposes. Even if you drop a `Vec`, its
415/// buffer may simply be reused by another allocation. Even if you zero a `Vec`'s memory
416/// first, that might not actually happen because the optimizer does not consider
417/// this a side-effect that must be preserved. There is one case which we will
418/// not break, however: using `unsafe` code to write to the excess capacity,
419/// and then increasing the length to match, is always valid.
420///
421/// Currently, `Vec` does not guarantee the order in which elements are dropped.
422/// The order has changed in the past and may change again.
423///
424/// [`get`]: slice::get
425/// [`get_mut`]: slice::get_mut
426/// [`String`]: crate::string::String
427/// [`&str`]: type@str
428/// [`shrink_to_fit`]: Vec::shrink_to_fit
429/// [`shrink_to`]: Vec::shrink_to
430/// [capacity]: Vec::capacity
431/// [`capacity`]: Vec::capacity
432/// [`Vec::capacity`]: Vec::capacity
433/// [size_of::\<T>]: size_of
434/// [len]: Vec::len
435/// [`len`]: Vec::len
436/// [`push`]: Vec::push
437/// [`insert`]: Vec::insert
438/// [`reserve`]: Vec::reserve
439/// [`Vec::with_capacity(n)`]: Vec::with_capacity
440/// [`MaybeUninit`]: core::mem::MaybeUninit
441/// [owned slice]: Box
442/// [`into_boxed_slice`]: Vec::into_boxed_slice
443#[stable(feature = "rust1", since = "1.0.0")]
444#[rustc_diagnostic_item = "Vec"]
445#[rustc_insignificant_dtor]
446#[doc(alias = "list")]
447#[doc(alias = "vector")]
448pub struct Vec<T, #[stable(feature = "allocator_api", since = "1.100.0")] A: Allocator = Global> {
449    buf: RawVec<T, A>,
450    len: usize,
451}
452
453////////////////////////////////////////////////////////////////////////////////
454// Inherent methods
455////////////////////////////////////////////////////////////////////////////////
456
457impl<T> Vec<T> {
458    /// Constructs a new, empty `Vec<T>`.
459    ///
460    /// The vector will not allocate until elements are pushed onto it.
461    ///
462    /// # Examples
463    ///
464    /// ```
465    /// # #![allow(unused_mut)]
466    /// let mut vec: Vec<i32> = Vec::new();
467    /// ```
468    #[inline]
469    #[rustc_const_stable(feature = "const_vec_new", since = "1.39.0")]
470    #[rustc_diagnostic_item = "vec_new"]
471    #[stable(feature = "rust1", since = "1.0.0")]
472    #[must_use]
473    pub const fn new() -> Self {
474        Vec { buf: RawVec::new(), len: 0 }
475    }
476
477    /// Constructs a new, empty `Vec<T>` with at least the specified capacity.
478    ///
479    /// The vector will be able to hold at least `capacity` elements without
480    /// reallocating. This method is allowed to allocate for more elements than
481    /// `capacity`. If `capacity` is zero, the vector [will not allocate].
482    ///
483    /// It is important to note that although the returned vector has the
484    /// minimum *capacity* specified, the vector will have a zero *length*. For
485    /// an explanation of the difference between length and capacity, see
486    /// *[Capacity and reallocation]*.
487    ///
488    /// If it is important to know the exact allocated capacity of a `Vec`,
489    /// always use the [`capacity`] method after construction.
490    ///
491    /// For `Vec<T>` where `T` is a zero-sized type, the vector
492    /// [will not allocate], and the capacity will always be `usize::MAX`.
493    ///
494    /// [Capacity and reallocation]: #capacity-and-reallocation
495    /// [`capacity`]: Vec::capacity
496    /// [will not allocate]: self#memory-layout
497    ///
498    /// # Panics
499    ///
500    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
501    ///
502    /// # Examples
503    ///
504    /// ```
505    /// let mut vec = Vec::with_capacity(10);
506    ///
507    /// // The vector contains no items, even though it has capacity for more
508    /// assert_eq!(vec.len(), 0);
509    /// assert!(vec.capacity() >= 10);
510    ///
511    /// // These are all done without reallocating...
512    /// for i in 0..10 {
513    ///     vec.push(i);
514    /// }
515    /// assert_eq!(vec.len(), 10);
516    /// assert!(vec.capacity() >= 10);
517    ///
518    /// // ...but this may make the vector reallocate
519    /// vec.push(11);
520    /// assert_eq!(vec.len(), 11);
521    /// assert!(vec.capacity() >= 11);
522    ///
523    /// // A vector of a zero-sized type will always over-allocate, since no
524    /// // allocation is necessary
525    /// let vec_units = Vec::<()>::with_capacity(10);
526    /// assert_eq!(vec_units.capacity(), usize::MAX);
527    /// ```
528    #[cfg(not(no_global_oom_handling))]
529    #[inline]
530    #[stable(feature = "rust1", since = "1.0.0")]
531    #[must_use]
532    #[rustc_diagnostic_item = "vec_with_capacity"]
533    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
534    pub const fn with_capacity(capacity: usize) -> Self {
535        Self::with_capacity_in(capacity, Global)
536    }
537
538    /// Constructs a new, empty `Vec<T>` with at least the specified capacity.
539    ///
540    /// The vector will be able to hold at least `capacity` elements without
541    /// reallocating. This method is allowed to allocate for more elements than
542    /// `capacity`. If `capacity` is zero, the vector [will not allocate].
543    ///
544    /// # Errors
545    ///
546    /// Returns an error if the capacity exceeds `isize::MAX` _bytes_,
547    /// or if the allocator reports allocation failure.
548    ///
549    /// [will not allocate]: self#memory-layout
550    #[inline]
551    #[unstable(feature = "try_with_capacity", issue = "91913")]
552    pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
553        Self::try_with_capacity_in(capacity, Global)
554    }
555
556    /// Creates a `Vec<T>` directly from a pointer, a length, and a capacity.
557    ///
558    /// # Safety
559    ///
560    /// The parts must satisfy the invariants described in the [memory layout] section,
561    /// with allocator [`Global`].
562    ///
563    /// Violating them may cause problems like corrupting the allocator's
564    /// internal data structures. For example it is normally **not** safe
565    /// to build a `Vec<u8>` from a pointer to a C `char` array with length
566    /// `size_t`, doing so is only safe if the array was initially allocated by
567    /// a `Vec` or `String`.
568    /// It's also not safe to build one from a `Vec<u16>` and its length, because
569    /// the allocator cares about the alignment, and these two types have different
570    /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
571    /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1. To avoid
572    /// these issues, it is often preferable to do casting/transmuting using
573    /// [`slice::from_raw_parts`] instead.
574    ///
575    /// The ownership of `ptr` is effectively transferred to the
576    /// `Vec<T>` which may then deallocate, reallocate or change the
577    /// contents of memory pointed to by the pointer at will. Ensure
578    /// that nothing else uses the pointer after calling this
579    /// function.
580    ///
581    /// [`String`]: crate::string::String
582    /// [memory layout]: self#memory-layout
583    ///
584    /// # Examples
585    ///
586    /// ```
587    /// use std::ptr;
588    ///
589    /// let v = vec![1, 2, 3];
590    ///
591    /// // Deconstruct the vector into parts.
592    /// let (p, len, cap) = v.into_raw_parts();
593    ///
594    /// unsafe {
595    ///     // Overwrite memory with 4, 5, 6
596    ///     for i in 0..len {
597    ///         ptr::write(p.add(i), 4 + i);
598    ///     }
599    ///
600    ///     // Put everything back together into a Vec
601    ///     let rebuilt = Vec::from_raw_parts(p, len, cap);
602    ///     assert_eq!(rebuilt, [4, 5, 6]);
603    /// }
604    /// ```
605    ///
606    /// Using memory that was allocated elsewhere:
607    ///
608    /// ```rust
609    /// use std::alloc::{alloc, Layout};
610    ///
611    /// fn main() {
612    ///     let layout = Layout::array::<u32>(16).expect("16 u32s take 64 bytes, so it shouldn't overflow");
613    ///
614    ///     let vec = unsafe {
615    ///         let mem = alloc(layout).cast::<u32>();
616    ///         if mem.is_null() {
617    ///             return;
618    ///         }
619    ///
620    ///         mem.write(1_000_000);
621    ///
622    ///         Vec::from_raw_parts(mem, 1, 16)
623    ///     };
624    ///
625    ///     assert_eq!(vec, &[1_000_000]);
626    ///     assert_eq!(vec.capacity(), 16);
627    /// }
628    /// ```
629    #[inline]
630    #[stable(feature = "rust1", since = "1.0.0")]
631    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
632    pub const unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
633        // SAFETY: Upheld by caller.
634        unsafe { Self::from_raw_parts_in(ptr, length, capacity, Global) }
635    }
636
637    #[doc(alias = "from_non_null_parts")]
638    /// Creates a `Vec<T>` directly from a `NonNull` pointer, a length, and a capacity.
639    ///
640    /// # Safety
641    ///
642    /// The parts must satisfy the invariants described in the [memory layout] section,
643    /// with allocator [`Global`].
644    ///
645    /// Violating them may cause problems like corrupting the allocator's
646    /// internal data structures. For example it is normally **not** safe
647    /// to build a `Vec<u8>` from a pointer to a C `char` array with length
648    /// `size_t`, doing so is only safe if the array was initially allocated by
649    /// a `Vec` or `String`.
650    /// It's also not safe to build one from a `Vec<u16>` and its length, because
651    /// the allocator cares about the alignment, and these two types have different
652    /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
653    /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1. To avoid
654    /// these issues, it is often preferable to do casting/transmuting using
655    /// [`NonNull::slice_from_raw_parts`] instead.
656    ///
657    /// The ownership of `ptr` is effectively transferred to the
658    /// `Vec<T>` which may then deallocate, reallocate or change the
659    /// contents of memory pointed to by the pointer at will. Ensure
660    /// that nothing else uses the pointer after calling this
661    /// function.
662    ///
663    /// [`String`]: crate::string::String
664    /// [memory layout]: self#memory-layout
665    ///
666    /// # Examples
667    ///
668    /// ```
669    /// let v = vec![1, 2, 3];
670    ///
671    /// // Deconstruct the vector into parts.
672    /// let (p, len, cap) = v.into_parts();
673    ///
674    /// unsafe {
675    ///     // Overwrite memory with 4, 5, 6
676    ///     for i in 0..len {
677    ///         p.add(i).write(4 + i);
678    ///     }
679    ///
680    ///     // Put everything back together into a Vec
681    ///     let rebuilt = Vec::from_parts(p, len, cap);
682    ///     assert_eq!(rebuilt, [4, 5, 6]);
683    /// }
684    /// ```
685    ///
686    /// Using memory that was allocated elsewhere:
687    ///
688    /// ```rust
689    /// use std::alloc::{alloc, Layout};
690    /// use std::ptr::NonNull;
691    ///
692    /// fn main() {
693    ///     let layout = Layout::array::<u32>(16).expect("16 u32s take 64 bytes, so it shouldn't overflow");
694    ///
695    ///     let vec = unsafe {
696    ///         let Some(mem) = NonNull::new(alloc(layout).cast::<u32>()) else {
697    ///             return;
698    ///         };
699    ///
700    ///         mem.write(1_000_000);
701    ///
702    ///         Vec::from_parts(mem, 1, 16)
703    ///     };
704    ///
705    ///     assert_eq!(vec, &[1_000_000]);
706    ///     assert_eq!(vec.capacity(), 16);
707    /// }
708    /// ```
709    #[inline]
710    #[stable(feature = "box_vec_non_null", since = "1.99.0")]
711    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
712    pub const unsafe fn from_parts(ptr: NonNull<T>, length: usize, capacity: usize) -> Self {
713        // SAFETY: Upheld by caller.
714        unsafe { Self::from_parts_in(ptr, length, capacity, Global) }
715    }
716
717    /// Creates a `Vec<T>` where each element is produced by calling `f` with
718    /// that element's index while walking forward through the `Vec<T>`.
719    ///
720    /// This is essentially the same as writing
721    ///
722    /// ```text
723    /// vec![f(0), f(1), f(2), …, f(length - 2), f(length - 1)]
724    /// ```
725    /// and is similar to `(0..i).map(f)`, just for `Vec<T>`s not iterators.
726    ///
727    /// If `length == 0`, this produces an empty `Vec<T>` without ever calling `f`.
728    ///
729    /// # Example
730    ///
731    /// ```rust
732    /// let vec = Vec::from_fn(5, |i| i);
733    ///
734    /// // indexes are:  0  1  2  3  4
735    /// assert_eq!(vec, [0, 1, 2, 3, 4]);
736    ///
737    /// let vec2 = Vec::from_fn(8, |i| i * 2);
738    ///
739    /// // indexes are:   0  1  2  3  4  5   6   7
740    /// assert_eq!(vec2, [0, 2, 4, 6, 8, 10, 12, 14]);
741    ///
742    /// let bool_vec = Vec::from_fn(5, |i| i % 2 == 0);
743    ///
744    /// // indexes are:       0     1      2     3      4
745    /// assert_eq!(bool_vec, [true, false, true, false, true]);
746    /// ```
747    ///
748    /// The `Vec<T>` is generated in ascending index order, starting from the front
749    /// and going towards the back, so you can use closures with mutable state:
750    /// ```
751    /// let mut state = 1;
752    /// let a = Vec::from_fn(6, |_| { let x = state; state *= 2; x });
753    ///
754    /// assert_eq!(a, [1, 2, 4, 8, 16, 32]);
755    /// ```
756    #[cfg(not(no_global_oom_handling))]
757    #[inline]
758    #[stable(feature = "vec_from_fn", since = "1.100.0")]
759    pub fn from_fn<F>(length: usize, f: F) -> Self
760    where
761        F: FnMut(usize) -> T,
762    {
763        (0..length).map(f).collect()
764    }
765
766    /// Decomposes a `Vec<T>` into its raw components: `(pointer, length, capacity)`.
767    ///
768    /// Returns the raw pointer to the underlying data, the length of
769    /// the vector (in elements), and the allocated capacity of the
770    /// data (in elements). These are the same arguments in the same
771    /// order as the arguments to [`from_raw_parts`].
772    ///
773    /// After calling this function, the caller is responsible for the
774    /// memory previously managed by the `Vec`. Most often, one does
775    /// this by converting the raw pointer, length, and capacity back
776    /// into a `Vec` with the [`from_raw_parts`] function; more generally,
777    /// if `T` is non-zero-sized and the capacity is nonzero, one may use
778    /// any method that calls [`dealloc`] with a layout of
779    /// `Layout::array::<T>(capacity)`; if `T` is zero-sized or the
780    /// capacity is zero, nothing needs to be done.
781    ///
782    /// [`from_raw_parts`]: Vec::from_raw_parts
783    /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
784    ///
785    /// # Examples
786    ///
787    /// ```
788    /// let v: Vec<i32> = vec![-1, 0, 1];
789    ///
790    /// let (ptr, len, cap) = v.into_raw_parts();
791    ///
792    /// let rebuilt = unsafe {
793    ///     // We can now make changes to the components, such as
794    ///     // transmuting the raw pointer to a compatible type.
795    ///     let ptr = ptr as *mut u32;
796    ///
797    ///     Vec::from_raw_parts(ptr, len, cap)
798    /// };
799    /// assert_eq!(rebuilt, [4294967295, 0, 1]);
800    /// ```
801    #[must_use = "losing the pointer will leak memory"]
802    #[stable(feature = "vec_into_raw_parts", since = "1.93.0")]
803    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
804    pub const fn into_raw_parts(self) -> (*mut T, usize, usize) {
805        let mut me = ManuallyDrop::new(self);
806        (me.as_mut_ptr(), me.len(), me.capacity())
807    }
808
809    #[doc(alias = "into_non_null_parts")]
810    /// Decomposes a `Vec<T>` into its raw components: `(NonNull pointer, length, capacity)`.
811    ///
812    /// Returns the `NonNull` pointer to the underlying data, the length of
813    /// the vector (in elements), and the allocated capacity of the
814    /// data (in elements). These are the same arguments in the same
815    /// order as the arguments to [`from_parts`].
816    ///
817    /// After calling this function, the caller is responsible for the
818    /// memory previously managed by the `Vec`. The only way to do
819    /// this is to convert the `NonNull` pointer, length, and capacity back
820    /// into a `Vec` with the [`from_parts`] function, allowing
821    /// the destructor to perform the cleanup.
822    ///
823    /// [`from_parts`]: Vec::from_parts
824    ///
825    /// # Examples
826    ///
827    /// ```
828    /// let v: Vec<i32> = vec![-1, 0, 1];
829    ///
830    /// let (ptr, len, cap) = v.into_parts();
831    ///
832    /// let rebuilt = unsafe {
833    ///     // We can now make changes to the components, such as
834    ///     // transmuting the raw pointer to a compatible type.
835    ///     let ptr = ptr.cast::<u32>();
836    ///
837    ///     Vec::from_parts(ptr, len, cap)
838    /// };
839    /// assert_eq!(rebuilt, [4294967295, 0, 1]);
840    /// ```
841    #[must_use = "losing the pointer will leak memory"]
842    #[stable(feature = "box_vec_non_null", since = "1.99.0")]
843    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
844    pub const fn into_parts(self) -> (NonNull<T>, usize, usize) {
845        let (ptr, len, capacity) = self.into_raw_parts();
846        // SAFETY: A `Vec` always has a non-null pointer.
847        (unsafe { NonNull::new_unchecked(ptr) }, len, capacity)
848    }
849
850    /// Interns the `Vec<T>`, making the underlying memory read-only. This method should be
851    /// called during compile time. (This is a no-op if called during runtime)
852    ///
853    /// This method must be called if the memory used by `Vec` needs to appear in the final
854    /// values of constants.
855    #[unstable(feature = "const_heap", issue = "79597")]
856    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
857    pub const fn const_make_global(mut self) -> &'static [T]
858    where
859        T: Freeze,
860    {
861        // `const_make_global` requires the pointer to point to the beginning of a heap allocation,
862        // which is not the case when `self.capacity()` is 0, or if `T::IS_ZST`,
863        // which is why we instead return a new slice in this case.
864        if self.capacity() == 0 || T::IS_ZST {
865            let me = ManuallyDrop::new(self);
866            // ignore-tidy-undocumented-unsafe
867            unsafe { slice::from_raw_parts(NonNull::<T>::dangling().as_ptr(), me.len) }
868        } else {
869            // ignore-tidy-undocumented-unsafe
870            unsafe { core::intrinsics::const_make_global(self.as_mut_ptr().cast()) };
871            let me = ManuallyDrop::new(self);
872            // ignore-tidy-undocumented-unsafe
873            unsafe { slice::from_raw_parts(me.as_ptr(), me.len) }
874        }
875    }
876}
877
878#[cfg(not(no_global_oom_handling))]
879#[rustc_const_unstable(feature = "const_heap", issue = "79597")]
880#[rustfmt::skip] // FIXME(fee1-dead): temporary measure before rustfmt is bumped
881const impl<T, A: [const] Allocator + [const] Destruct> Vec<T, A> {
882    /// Constructs a new, empty `Vec<T, A>` with at least the specified capacity
883    /// with the provided allocator.
884    ///
885    /// The vector will be able to hold at least `capacity` elements without
886    /// reallocating. This method is allowed to allocate for more elements than
887    /// `capacity`. If `capacity` is zero, the vector [will not allocate].
888    ///
889    /// It is important to note that although the returned vector has the
890    /// minimum *capacity* specified, the vector will have a zero *length*. For
891    /// an explanation of the difference between length and capacity, see
892    /// *[Capacity and reallocation]*.
893    ///
894    /// If it is important to know the exact allocated capacity of a `Vec`,
895    /// always use the [`capacity`] method after construction.
896    ///
897    /// For `Vec<T, A>` where `T` is a zero-sized type, the vector
898    /// [will not allocate], and the capacity will always be `usize::MAX`.
899    ///
900    /// [Capacity and reallocation]: #capacity-and-reallocation
901    /// [`capacity`]: Vec::capacity
902    /// [will not allocate]: self#memory-layout
903    ///
904    /// # Panics
905    ///
906    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
907    ///
908    /// # Examples
909    ///
910    /// ```
911    /// use std::alloc::System;
912    ///
913    /// let mut vec = Vec::with_capacity_in(10, System);
914    ///
915    /// // The vector contains no items, even though it has capacity for more
916    /// assert_eq!(vec.len(), 0);
917    /// assert!(vec.capacity() >= 10);
918    ///
919    /// // These are all done without reallocating...
920    /// for i in 0..10 {
921    ///     vec.push(i);
922    /// }
923    /// assert_eq!(vec.len(), 10);
924    /// assert!(vec.capacity() >= 10);
925    ///
926    /// // ...but this may make the vector reallocate
927    /// vec.push(11);
928    /// assert_eq!(vec.len(), 11);
929    /// assert!(vec.capacity() >= 11);
930    ///
931    /// // A vector of a zero-sized type will always over-allocate, since no
932    /// // allocation is necessary
933    /// let vec_units = Vec::<(), System>::with_capacity_in(10, System);
934    /// assert_eq!(vec_units.capacity(), usize::MAX);
935    /// ```
936    #[inline]
937    #[stable(feature = "allocator_api", since = "1.100.0")]
938    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
939        Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 }
940    }
941
942    /// Appends an element to the back of a collection.
943    ///
944    /// # Panics
945    ///
946    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
947    ///
948    /// # Examples
949    ///
950    /// ```
951    /// let mut vec = vec![1, 2];
952    /// vec.push(3);
953    /// assert_eq!(vec, [1, 2, 3]);
954    /// ```
955    ///
956    /// # Time complexity
957    ///
958    /// Takes amortized *O*(1) time. If the vector's length would exceed its
959    /// capacity after the push, *O*(*capacity*) time is taken to copy the
960    /// vector's elements to a larger allocation. This expensive operation is
961    /// offset by the *capacity* *O*(1) insertions it allows.
962    #[inline]
963    #[stable(feature = "rust1", since = "1.0.0")]
964    #[rustc_confusables("push_back", "put", "append")]
965    pub fn push(&mut self, value: T) {
966        let _ = self.push_mut(value);
967    }
968
969    /// Appends an element to the back of a collection, returning a reference to it.
970    ///
971    /// # Panics
972    ///
973    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
974    ///
975    /// # Examples
976    ///
977    /// ```
978    /// let mut vec = vec![1, 2];
979    /// let last = vec.push_mut(3);
980    /// assert_eq!(*last, 3);
981    /// assert_eq!(vec, [1, 2, 3]);
982    ///
983    /// let last = vec.push_mut(3);
984    /// *last += 1;
985    /// assert_eq!(vec, [1, 2, 3, 4]);
986    /// ```
987    ///
988    /// # Time complexity
989    ///
990    /// Takes amortized *O*(1) time. If the vector's length would exceed its
991    /// capacity after the push, *O*(*capacity*) time is taken to copy the
992    /// vector's elements to a larger allocation. This expensive operation is
993    /// offset by the *capacity* *O*(1) insertions it allows.
994    #[inline]
995    #[stable(feature = "push_mut", since = "1.95.0")]
996    #[must_use = "if you don't need a reference to the value, use `Vec::push` instead"]
997    pub fn push_mut(&mut self, value: T) -> &mut T {
998        // Inform codegen that the length does not change across grow_one().
999        let len = self.len;
1000        // This will panic or abort if we would allocate > isize::MAX bytes
1001        // or if the length increment would overflow for zero-sized types.
1002        if len == self.buf.capacity() {
1003            self.buf.grow_one();
1004        }
1005        // ignore-tidy-undocumented-unsafe
1006        unsafe {
1007            let end = self.as_mut_ptr().add(len);
1008            ptr::write(end, value);
1009            self.len = len + 1;
1010            // SAFETY: We just wrote a value to the pointer that will live the lifetime of the reference.
1011            &mut *end
1012        }
1013    }
1014}
1015
1016impl<T, A: Allocator> Vec<T, A> {
1017    /// Constructs a new, empty `Vec<T, A>`.
1018    ///
1019    /// The vector will not allocate until elements are pushed onto it.
1020    ///
1021    /// # Examples
1022    ///
1023    /// ```
1024    /// use std::alloc::System;
1025    ///
1026    /// let vec: Vec<i32, System> = Vec::new_in(System);
1027    /// ```
1028    #[inline]
1029    #[stable(feature = "allocator_api", since = "1.100.0")]
1030    #[rustc_const_unstable(feature = "allocator_ext", issue = "163177")]
1031    pub const fn new_in(alloc: A) -> Self {
1032        Vec { buf: RawVec::new_in(alloc), len: 0 }
1033    }
1034
1035    /// Constructs a new, empty `Vec<T, A>` with at least the specified capacity
1036    /// with the provided allocator.
1037    ///
1038    /// The vector will be able to hold at least `capacity` elements without
1039    /// reallocating. This method is allowed to allocate for more elements than
1040    /// `capacity`. If `capacity` is zero, the vector [will not allocate].
1041    ///
1042    /// # Errors
1043    ///
1044    /// Returns an error if the capacity exceeds `isize::MAX` _bytes_,
1045    /// or if the allocator reports allocation failure.
1046    ///
1047    /// [will not allocate]: self#memory-layout
1048    #[inline]
1049    #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")]
1050    // #[unstable(feature = "try_with_capacity", issue = "91913")]
1051    pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {
1052        Ok(Vec { buf: RawVec::try_with_capacity_in(capacity, alloc)?, len: 0 })
1053    }
1054
1055    /// Creates a `Vec<T, A>` directly from a pointer, a length, a capacity,
1056    /// and an allocator.
1057    ///
1058    /// # Safety
1059    ///
1060    /// The parts must satisfy the invariants described in the [memory layout] section.
1061    ///
1062    /// Violating them may cause problems like corrupting the allocator's
1063    /// internal data structures. For example it is **not** safe
1064    /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.
1065    /// It's also not safe to build one from a `Vec<u16>` and its length, because
1066    /// the allocator cares about the alignment, and these two types have different
1067    /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
1068    /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.
1069    ///
1070    /// The ownership of `ptr` is effectively transferred to the
1071    /// `Vec<T>` which may then deallocate, reallocate or change the
1072    /// contents of memory pointed to by the pointer at will. Ensure
1073    /// that nothing else uses the pointer after calling this
1074    /// function.
1075    ///
1076    /// [`String`]: crate::string::String
1077    /// [`allocate`]: crate::alloc::Allocator::allocate
1078    /// [memory layout]: self#memory-layout
1079    ///
1080    /// # Examples
1081    ///
1082    /// ```
1083    /// use std::alloc::System;
1084    ///
1085    /// use std::ptr;
1086    ///
1087    /// let mut v = Vec::with_capacity_in(3, System);
1088    /// v.push(1);
1089    /// v.push(2);
1090    /// v.push(3);
1091    ///
1092    /// // Deconstruct the vector into parts.
1093    /// let (p, len, cap, alloc) = v.into_raw_parts_with_allocator();
1094    ///
1095    /// unsafe {
1096    ///     // Overwrite memory with 4, 5, 6
1097    ///     for i in 0..len {
1098    ///         ptr::write(p.add(i), 4 + i);
1099    ///     }
1100    ///
1101    ///     // Put everything back together into a Vec
1102    ///     let rebuilt = Vec::from_raw_parts_in(p, len, cap, alloc.clone());
1103    ///     assert_eq!(rebuilt, [4, 5, 6]);
1104    /// }
1105    /// ```
1106    ///
1107    /// Using memory that was allocated elsewhere:
1108    ///
1109    /// ```rust
1110    /// use std::alloc::{AllocError, Allocator, Global, Layout};
1111    ///
1112    /// fn main() {
1113    ///     let layout = Layout::array::<u32>(16).expect("16 u32s take 64 bytes, so it shouldn't overflow");
1114    ///
1115    ///     let vec = unsafe {
1116    ///         let mem = match Global.allocate(layout) {
1117    ///             Ok(mem) => mem.cast::<u32>().as_ptr(),
1118    ///             Err(AllocError) => return,
1119    ///         };
1120    ///
1121    ///         mem.write(1_000_000);
1122    ///
1123    ///         Vec::from_raw_parts_in(mem, 1, 16, Global)
1124    ///     };
1125    ///
1126    ///     assert_eq!(vec, &[1_000_000]);
1127    ///     assert_eq!(vec.capacity(), 16);
1128    /// }
1129    /// ```
1130    #[inline]
1131    #[stable(feature = "allocator_api", since = "1.100.0")]
1132    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
1133    pub const unsafe fn from_raw_parts_in(
1134        ptr: *mut T,
1135        length: usize,
1136        capacity: usize,
1137        alloc: A,
1138    ) -> Self {
1139        ub_checks::assert_unsafe_precondition!(
1140            check_library_ub,
1141            "Vec::from_raw_parts_in requires that length <= capacity",
1142            (length: usize = length, capacity: usize = capacity) => length <= capacity
1143        );
1144        // SAFETY: Upheld by caller.
1145        unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } }
1146    }
1147
1148    #[doc(alias = "from_non_null_parts_in")]
1149    /// Creates a `Vec<T, A>` directly from a `NonNull` pointer, a length, a capacity,
1150    /// and an allocator.
1151    ///
1152    /// # Safety
1153    ///
1154    /// The parts must satisfy the invariants described in the [memory layout] section.
1155    ///
1156    /// Violating them may cause problems like corrupting the allocator's
1157    /// internal data structures. For example it is **not** safe
1158    /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.
1159    /// It's also not safe to build one from a `Vec<u16>` and its length, because
1160    /// the allocator cares about the alignment, and these two types have different
1161    /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
1162    /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.
1163    ///
1164    /// The ownership of `ptr` is effectively transferred to the
1165    /// `Vec<T>` which may then deallocate, reallocate or change the
1166    /// contents of memory pointed to by the pointer at will. Ensure
1167    /// that nothing else uses the pointer after calling this
1168    /// function.
1169    ///
1170    /// [`String`]: crate::string::String
1171    /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
1172    /// [memory layout]: self#memory-layout
1173    ///
1174    /// # Examples
1175    ///
1176    /// ```
1177    /// use std::alloc::System;
1178    ///
1179    /// let mut v = Vec::with_capacity_in(3, System);
1180    /// v.push(1);
1181    /// v.push(2);
1182    /// v.push(3);
1183    ///
1184    /// // Deconstruct the vector into parts.
1185    /// let (p, len, cap, alloc) = v.into_parts_with_allocator();
1186    ///
1187    /// unsafe {
1188    ///     // Overwrite memory with 4, 5, 6
1189    ///     for i in 0..len {
1190    ///         p.add(i).write(4 + i);
1191    ///     }
1192    ///
1193    ///     // Put everything back together into a Vec
1194    ///     let rebuilt = Vec::from_parts_in(p, len, cap, alloc.clone());
1195    ///     assert_eq!(rebuilt, [4, 5, 6]);
1196    /// }
1197    /// ```
1198    ///
1199    /// Using memory that was allocated elsewhere:
1200    ///
1201    /// ```rust
1202    /// use std::alloc::{AllocError, Allocator, Global, Layout};
1203    ///
1204    /// fn main() {
1205    ///     let layout = Layout::array::<u32>(16).expect("16 u32s take 64 bytes, so it shouldn't overflow");
1206    ///
1207    ///     let vec = unsafe {
1208    ///         let mem = match Global.allocate(layout) {
1209    ///             Ok(mem) => mem.cast::<u32>(),
1210    ///             Err(AllocError) => return,
1211    ///         };
1212    ///
1213    ///         mem.write(1_000_000);
1214    ///
1215    ///         Vec::from_parts_in(mem, 1, 16, Global)
1216    ///     };
1217    ///
1218    ///     assert_eq!(vec, &[1_000_000]);
1219    ///     assert_eq!(vec.capacity(), 16);
1220    /// }
1221    /// ```
1222    #[inline]
1223    #[stable(feature = "allocator_api", since = "1.100.0")]
1224    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
1225    pub const unsafe fn from_parts_in(
1226        ptr: NonNull<T>,
1227        length: usize,
1228        capacity: usize,
1229        alloc: A,
1230    ) -> Self {
1231        ub_checks::assert_unsafe_precondition!(
1232            check_library_ub,
1233            "Vec::from_parts_in requires that length <= capacity",
1234            (length: usize = length, capacity: usize = capacity) => length <= capacity
1235        );
1236        // SAFETY: Upheld by caller.
1237        unsafe { Vec { buf: RawVec::from_nonnull_in(ptr, capacity, alloc), len: length } }
1238    }
1239
1240    /// Decomposes a `Vec<T>` into its raw components: `(pointer, length, capacity, allocator)`.
1241    ///
1242    /// Returns the raw pointer to the underlying data, the length of the vector (in elements),
1243    /// the allocated capacity of the data (in elements), and the allocator. These are the same
1244    /// arguments in the same order as the arguments to [`from_raw_parts_in`].
1245    ///
1246    /// After calling this function, the caller is responsible for the
1247    /// memory previously managed by the `Vec`. The only way to do
1248    /// this is to convert the raw pointer, length, and capacity back
1249    /// into a `Vec` with the [`from_raw_parts_in`] function, allowing
1250    /// the destructor to perform the cleanup.
1251    ///
1252    /// [`from_raw_parts_in`]: Vec::from_raw_parts_in
1253    ///
1254    /// # Examples
1255    ///
1256    /// ```
1257    /// use std::alloc::System;
1258    ///
1259    /// let mut v: Vec<i32, System> = Vec::new_in(System);
1260    /// v.push(-1);
1261    /// v.push(0);
1262    /// v.push(1);
1263    ///
1264    /// let (ptr, len, cap, alloc) = v.into_raw_parts_with_allocator();
1265    ///
1266    /// let rebuilt = unsafe {
1267    ///     // We can now make changes to the components, such as
1268    ///     // transmuting the raw pointer to a compatible type.
1269    ///     let ptr = ptr as *mut u32;
1270    ///
1271    ///     Vec::from_raw_parts_in(ptr, len, cap, alloc)
1272    /// };
1273    /// assert_eq!(rebuilt, [4294967295, 0, 1]);
1274    /// ```
1275    #[must_use = "losing the pointer will leak memory"]
1276    #[stable(feature = "allocator_api", since = "1.100.0")]
1277    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
1278    pub const fn into_raw_parts_with_allocator(self) -> (*mut T, usize, usize, A) {
1279        let mut me = ManuallyDrop::new(self);
1280        let len = me.len();
1281        let capacity = me.capacity();
1282        let ptr = me.as_mut_ptr();
1283        // ignore-tidy-undocumented-unsafe
1284        let alloc = unsafe { ptr::read(me.allocator()) };
1285        (ptr, len, capacity, alloc)
1286    }
1287
1288    #[doc(alias = "into_non_null_parts_with_alloc")]
1289    /// Decomposes a `Vec<T>` into its raw components: `(NonNull pointer, length, capacity, allocator)`.
1290    ///
1291    /// Returns the `NonNull` pointer to the underlying data, the length of the vector (in elements),
1292    /// the allocated capacity of the data (in elements), and the allocator. These are the same
1293    /// arguments in the same order as the arguments to [`from_parts_in`].
1294    ///
1295    /// After calling this function, the caller is responsible for the
1296    /// memory previously managed by the `Vec`. The only way to do
1297    /// this is to convert the `NonNull` pointer, length, and capacity back
1298    /// into a `Vec` with the [`from_parts_in`] function, allowing
1299    /// the destructor to perform the cleanup.
1300    ///
1301    /// [`from_parts_in`]: Vec::from_parts_in
1302    ///
1303    /// # Examples
1304    ///
1305    /// ```
1306    /// use std::alloc::System;
1307    ///
1308    /// let mut v: Vec<i32, System> = Vec::new_in(System);
1309    /// v.push(-1);
1310    /// v.push(0);
1311    /// v.push(1);
1312    ///
1313    /// let (ptr, len, cap, alloc) = v.into_parts_with_allocator();
1314    ///
1315    /// let rebuilt = unsafe {
1316    ///     // We can now make changes to the components, such as
1317    ///     // transmuting the raw pointer to a compatible type.
1318    ///     let ptr = ptr.cast::<u32>();
1319    ///
1320    ///     Vec::from_parts_in(ptr, len, cap, alloc)
1321    /// };
1322    /// assert_eq!(rebuilt, [4294967295, 0, 1]);
1323    /// ```
1324    #[must_use = "losing the pointer will leak memory"]
1325    #[stable(feature = "allocator_api", since = "1.100.0")]
1326    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
1327    pub const fn into_parts_with_allocator(self) -> (NonNull<T>, usize, usize, A) {
1328        let (ptr, len, capacity, alloc) = self.into_raw_parts_with_allocator();
1329        // SAFETY: A `Vec` always has a non-null pointer.
1330        (unsafe { NonNull::new_unchecked(ptr) }, len, capacity, alloc)
1331    }
1332
1333    /// Returns the total number of elements the vector can hold without
1334    /// reallocating.
1335    ///
1336    /// # Examples
1337    ///
1338    /// ```
1339    /// let mut vec: Vec<i32> = Vec::with_capacity(10);
1340    /// vec.push(42);
1341    /// assert!(vec.capacity() >= 10);
1342    /// ```
1343    ///
1344    /// A vector with zero-sized elements will always have a capacity of usize::MAX:
1345    ///
1346    /// ```
1347    /// #[derive(Clone)]
1348    /// struct ZeroSized;
1349    ///
1350    /// fn main() {
1351    ///     assert_eq!(std::mem::size_of::<ZeroSized>(), 0);
1352    ///     let v = vec![ZeroSized; 0];
1353    ///     assert_eq!(v.capacity(), usize::MAX);
1354    /// }
1355    /// ```
1356    #[inline]
1357    #[stable(feature = "rust1", since = "1.0.0")]
1358    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1359    pub const fn capacity(&self) -> usize {
1360        self.buf.capacity()
1361    }
1362
1363    /// Reserves capacity for at least `additional` more elements to be inserted
1364    /// in the given `Vec<T>`. The collection may reserve more space to
1365    /// speculatively avoid frequent reallocations. After calling `reserve`,
1366    /// capacity will be greater than or equal to `self.len() + additional`.
1367    /// Does nothing if capacity is already sufficient.
1368    ///
1369    /// # Panics
1370    ///
1371    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
1372    ///
1373    /// # Examples
1374    ///
1375    /// ```
1376    /// let mut vec = vec![1];
1377    /// vec.reserve(10);
1378    /// assert!(vec.capacity() >= 11);
1379    /// ```
1380    #[cfg(not(no_global_oom_handling))]
1381    #[stable(feature = "rust1", since = "1.0.0")]
1382    #[rustc_diagnostic_item = "vec_reserve"]
1383    pub fn reserve(&mut self, additional: usize) {
1384        self.buf.reserve(self.len, additional);
1385    }
1386
1387    /// Reserves the minimum capacity for at least `additional` more elements to
1388    /// be inserted in the given `Vec<T>`. Unlike [`reserve`], this will not
1389    /// deliberately over-allocate to speculatively avoid frequent allocations.
1390    /// After calling `reserve_exact`, capacity will be greater than or equal to
1391    /// `self.len() + additional`. Does nothing if the capacity is already
1392    /// sufficient.
1393    ///
1394    /// Note that the allocator may give the collection more space than it
1395    /// requests. Therefore, capacity can not be relied upon to be precisely
1396    /// minimal. Prefer [`reserve`] if future insertions are expected.
1397    ///
1398    /// [`reserve`]: Vec::reserve
1399    ///
1400    /// # Panics
1401    ///
1402    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
1403    ///
1404    /// # Examples
1405    ///
1406    /// ```
1407    /// let mut vec = vec![1];
1408    /// vec.reserve_exact(10);
1409    /// assert!(vec.capacity() >= 11);
1410    /// ```
1411    #[cfg(not(no_global_oom_handling))]
1412    #[stable(feature = "rust1", since = "1.0.0")]
1413    pub fn reserve_exact(&mut self, additional: usize) {
1414        self.buf.reserve_exact(self.len, additional);
1415    }
1416
1417    /// Tries to reserve capacity for at least `additional` more elements to be inserted
1418    /// in the given `Vec<T>`. The collection may reserve more space to speculatively avoid
1419    /// frequent reallocations. After calling `try_reserve`, capacity will be
1420    /// greater than or equal to `self.len() + additional` if it returns
1421    /// `Ok(())`. Does nothing if capacity is already sufficient. This method
1422    /// preserves the contents even if an error occurs.
1423    ///
1424    /// # Errors
1425    ///
1426    /// If the capacity overflows, or the allocator reports a failure, then an error
1427    /// is returned.
1428    ///
1429    /// # Examples
1430    ///
1431    /// ```
1432    /// use std::collections::TryReserveError;
1433    ///
1434    /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1435    ///     let mut output = Vec::new();
1436    ///
1437    ///     // Pre-reserve the memory, exiting if we can't
1438    ///     output.try_reserve(data.len())?;
1439    ///
1440    ///     // Now we know this can't OOM in the middle of our complex work
1441    ///     output.extend(data.iter().map(|&val| {
1442    ///         val * 2 + 5 // very complicated
1443    ///     }));
1444    ///
1445    ///     Ok(output)
1446    /// }
1447    /// # process_data(&[1, 2, 3]).expect("this test needs 12 bytes, so it shouldn't fail");
1448    /// ```
1449    #[stable(feature = "try_reserve", since = "1.57.0")]
1450    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
1451        self.buf.try_reserve(self.len, additional)
1452    }
1453
1454    /// Tries to reserve the minimum capacity for at least `additional`
1455    /// elements to be inserted in the given `Vec<T>`. Unlike [`try_reserve`],
1456    /// this will not deliberately over-allocate to speculatively avoid frequent
1457    /// allocations. After calling `try_reserve_exact`, capacity will be greater
1458    /// than or equal to `self.len() + additional` if it returns `Ok(())`.
1459    /// Does nothing if the capacity is already sufficient.
1460    ///
1461    /// Note that the allocator may give the collection more space than it
1462    /// requests. Therefore, capacity can not be relied upon to be precisely
1463    /// minimal. Prefer [`try_reserve`] if future insertions are expected.
1464    ///
1465    /// [`try_reserve`]: Vec::try_reserve
1466    ///
1467    /// # Errors
1468    ///
1469    /// If the capacity overflows, or the allocator reports a failure, then an error
1470    /// is returned.
1471    ///
1472    /// # Examples
1473    ///
1474    /// ```
1475    /// use std::collections::TryReserveError;
1476    ///
1477    /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1478    ///     let mut output = Vec::new();
1479    ///
1480    ///     // Pre-reserve the memory, exiting if we can't
1481    ///     output.try_reserve_exact(data.len())?;
1482    ///
1483    ///     // Now we know this can't OOM in the middle of our complex work
1484    ///     output.extend(data.iter().map(|&val| {
1485    ///         val * 2 + 5 // very complicated
1486    ///     }));
1487    ///
1488    ///     Ok(output)
1489    /// }
1490    /// # process_data(&[1, 2, 3]).expect("this test needs 12 bytes, so it shouldn't fail");
1491    /// ```
1492    #[stable(feature = "try_reserve", since = "1.57.0")]
1493    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
1494        self.buf.try_reserve_exact(self.len, additional)
1495    }
1496
1497    /// Shrinks the capacity of the vector as much as possible.
1498    ///
1499    /// The behavior of this method depends on the allocator, which may either shrink the vector
1500    /// in-place or reallocate. The resulting vector might still have some excess capacity, just as
1501    /// is the case for [`with_capacity`]. See [`Allocator::shrink`] for more details.
1502    ///
1503    /// [`with_capacity`]: Vec::with_capacity
1504    ///
1505    /// # Examples
1506    ///
1507    /// ```
1508    /// let mut vec = Vec::with_capacity(10);
1509    /// vec.extend([1, 2, 3]);
1510    /// assert!(vec.capacity() >= 10);
1511    /// vec.shrink_to_fit();
1512    /// assert!(vec.capacity() >= 3);
1513    /// ```
1514    #[cfg(not(no_global_oom_handling))]
1515    #[stable(feature = "rust1", since = "1.0.0")]
1516    #[inline]
1517    pub fn shrink_to_fit(&mut self) {
1518        // The capacity is never less than the length, and there's nothing to do when
1519        // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit`
1520        // by only calling it with a greater capacity.
1521        if self.capacity() > self.len {
1522            self.buf.shrink_to_fit(self.len);
1523        }
1524    }
1525
1526    /// Shrinks the capacity of the vector with a lower bound.
1527    ///
1528    /// The capacity will remain at least as large as both the length
1529    /// and the supplied value.
1530    ///
1531    /// If the current capacity is less than the lower limit, this is a no-op.
1532    ///
1533    /// # Examples
1534    ///
1535    /// ```
1536    /// let mut vec = Vec::with_capacity(10);
1537    /// vec.extend([1, 2, 3]);
1538    /// assert!(vec.capacity() >= 10);
1539    /// vec.shrink_to(4);
1540    /// assert!(vec.capacity() >= 4);
1541    /// vec.shrink_to(0);
1542    /// assert!(vec.capacity() >= 3);
1543    /// ```
1544    #[cfg(not(no_global_oom_handling))]
1545    #[stable(feature = "shrink_to", since = "1.56.0")]
1546    pub fn shrink_to(&mut self, min_capacity: usize) {
1547        if self.capacity() > min_capacity {
1548            self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
1549        }
1550    }
1551
1552    /// Tries to shrink the capacity of the vector as much as possible
1553    ///
1554    /// The behavior of this method depends on the allocator, which may either shrink the vector
1555    /// in-place or reallocate. The resulting vector might still have some excess capacity, just as
1556    /// is the case for [`with_capacity`]. See [`Allocator::shrink`] for more details.
1557    ///
1558    /// [`with_capacity`]: Vec::with_capacity
1559    ///
1560    /// # Errors
1561    ///
1562    /// This function returns an error if the allocator fails to shrink the allocation,
1563    /// the vector thereafter is still safe to use, the capacity remains unchanged
1564    /// however. See [`Allocator::shrink`].
1565    ///
1566    /// # Examples
1567    ///
1568    /// ```
1569    /// #![feature(vec_fallible_shrink)]
1570    ///
1571    /// let mut vec = Vec::with_capacity(10);
1572    /// vec.extend([1, 2, 3]);
1573    /// assert!(vec.capacity() >= 10);
1574    /// vec.try_shrink_to_fit().expect("for this test, shrink shouldn't fail");
1575    /// assert!(vec.capacity() >= 3);
1576    /// ```
1577    #[unstable(feature = "vec_fallible_shrink", issue = "152350")]
1578    #[inline]
1579    pub fn try_shrink_to_fit(&mut self) -> Result<(), TryReserveError> {
1580        if self.capacity() > self.len { self.buf.try_shrink_to_fit(self.len) } else { Ok(()) }
1581    }
1582
1583    /// Shrinks the capacity of the vector with a lower bound.
1584    ///
1585    /// The capacity will remain at least as large as both the length
1586    /// and the supplied value.
1587    ///
1588    /// If the current capacity is less than the lower limit, this is a no-op.
1589    ///
1590    /// # Errors
1591    ///
1592    /// This function returns an error if the allocator fails to shrink the allocation,
1593    /// the vector thereafter is still safe to use, the capacity remains unchanged
1594    /// however. See [`Allocator::shrink`].
1595    ///
1596    /// # Examples
1597    ///
1598    /// ```
1599    /// #![feature(vec_fallible_shrink)]
1600    ///
1601    /// let mut vec = Vec::with_capacity(10);
1602    /// vec.extend([1, 2, 3]);
1603    /// assert!(vec.capacity() >= 10);
1604    /// vec.try_shrink_to(4).expect("for this test, shrink shouldn't fail");
1605    /// assert!(vec.capacity() >= 4);
1606    /// vec.try_shrink_to(0).expect("this is a no-op and thus the allocator isn't involved.");
1607    /// assert!(vec.capacity() >= 3);
1608    /// ```
1609    #[unstable(feature = "vec_fallible_shrink", issue = "152350")]
1610    #[inline]
1611    pub fn try_shrink_to(&mut self, min_capacity: usize) -> Result<(), TryReserveError> {
1612        if self.capacity() > min_capacity {
1613            self.buf.try_shrink_to_fit(cmp::max(self.len, min_capacity))
1614        } else {
1615            Ok(())
1616        }
1617    }
1618
1619    /// Converts the vector into [`Box<[T]>`][owned slice].
1620    ///
1621    /// Before doing the conversion, this method discards excess capacity like [`shrink_to_fit`].
1622    ///
1623    /// [owned slice]: Box
1624    /// [`shrink_to_fit`]: Vec::shrink_to_fit
1625    ///
1626    /// # Examples
1627    ///
1628    /// ```
1629    /// let v = vec![1, 2, 3];
1630    ///
1631    /// let slice = v.into_boxed_slice();
1632    /// ```
1633    ///
1634    /// Any excess capacity is removed:
1635    ///
1636    /// ```
1637    /// let mut vec = Vec::with_capacity(10);
1638    /// vec.extend([1, 2, 3]);
1639    ///
1640    /// assert!(vec.capacity() >= 10);
1641    /// let slice = vec.into_boxed_slice();
1642    /// assert_eq!(slice.into_vec().capacity(), 3);
1643    /// ```
1644    #[cfg(not(no_global_oom_handling))]
1645    #[stable(feature = "rust1", since = "1.0.0")]
1646    pub fn into_boxed_slice(mut self) -> Box<[T], A> {
1647        self.shrink_to_fit();
1648        let me = ManuallyDrop::new(self);
1649        // ignore-tidy-undocumented-unsafe
1650        unsafe {
1651            let buf = ptr::read(&me.buf);
1652            let len = me.len();
1653            buf.into_box(len).assume_init()
1654        }
1655    }
1656
1657    /// Converts the Vec into a boxed array. This conversion will discard any spare capacity,
1658    /// if there is any, see [`Vec::shrink_to_fit`].
1659    /// If you merely wish for a reference to an array, use [`as_array`](https://doc.rust-lang.org/stable/std/primitive.slice.html#method.as_array).
1660    ///
1661    /// # Errors
1662    ///
1663    /// Returns the original `Vec<T>` in the `Err` variant if [`Vec::len`] does not equal `N`.
1664    ///
1665    /// # Examples
1666    ///
1667    /// ```
1668    /// #![feature(alloc_slice_into_array)]
1669    /// let vec: Vec<i32> = vec![1, 2, 3];
1670    /// let box_array: Box<[i32; 3]> = vec.clone().into_array().unwrap();
1671    /// let not_enough_elements: Result<Box<[i32; 4]>, Vec<i32>> = vec.into_array::<4>();
1672    /// assert_eq!(not_enough_elements, Err(vec![1, 2, 3]));
1673    /// ```
1674    #[cfg(not(no_global_oom_handling))]
1675    #[unstable(feature = "alloc_slice_into_array", issue = "148082")]
1676    pub fn into_array<const N: usize>(self) -> Result<Box<[T; N], A>, Self> {
1677        if self.len() == N {
1678            // SAFETY: `Box::into_array` is guaranteed to return `Ok` if the
1679            // length of the slice is equal to `N`.
1680            // `self.into_boxed_slice().len()` is equal to `self.len()`,
1681            // which we just checked.
1682            Ok(unsafe { self.into_boxed_slice().into_array().unwrap_unchecked() })
1683        } else {
1684            Err(self)
1685        }
1686    }
1687
1688    /// Shortens the vector, keeping the first `len` elements and dropping
1689    /// the rest.
1690    ///
1691    /// If `len` is greater or equal to the vector's current length, this has
1692    /// no effect.
1693    ///
1694    /// The [`drain`] method can emulate `truncate`, but causes the excess
1695    /// elements to be returned instead of dropped.
1696    ///
1697    /// Note that this method has no effect on the allocated capacity
1698    /// of the vector.
1699    ///
1700    /// # Examples
1701    ///
1702    /// Truncating a five element vector to two elements:
1703    ///
1704    /// ```
1705    /// let mut vec = vec![1, 2, 3, 4, 5];
1706    /// vec.truncate(2);
1707    /// assert_eq!(vec, [1, 2]);
1708    /// ```
1709    ///
1710    /// No truncation occurs when `len` is greater than or equal to the
1711    /// vector's current length:
1712    ///
1713    /// ```
1714    /// let mut vec = vec![1, 2, 3];
1715    /// vec.truncate(8);
1716    /// assert_eq!(vec, [1, 2, 3]);
1717    /// ```
1718    ///
1719    /// Truncating when `len == 0` is equivalent to calling the [`clear`]
1720    /// method.
1721    ///
1722    /// ```
1723    /// let mut vec = vec![1, 2, 3];
1724    /// vec.truncate(0);
1725    /// assert_eq!(vec, []);
1726    /// ```
1727    ///
1728    /// [`clear`]: Vec::clear
1729    /// [`drain`]: Vec::drain
1730    #[stable(feature = "rust1", since = "1.0.0")]
1731    pub fn truncate(&mut self, len: usize) {
1732        // SAFETY: `BufWriter::flush_buf` assumes that this will not
1733        // de-initialize any elements of the spare capacity.
1734
1735        // This is safe because:
1736        //
1737        // * the slice passed to `drop_in_place` is valid; the `len >= self.len`
1738        //   case avoids creating an invalid slice, and
1739        // * the `len` of the vector is shrunk before calling `drop_in_place`,
1740        //   such that no value will be dropped twice in case `drop_in_place`
1741        //   were to panic once (if it panics twice, the program aborts).
1742        unsafe {
1743            if len >= self.len {
1744                return;
1745            }
1746            let remaining_len = self.len - len;
1747            let s = self.as_mut_ptr().add(len).cast_slice(remaining_len);
1748            self.len = len;
1749            ptr::drop_in_place(s);
1750        }
1751    }
1752
1753    /// Extracts a slice containing the entire vector.
1754    ///
1755    /// Equivalent to `&s[..]`.
1756    ///
1757    /// # Examples
1758    ///
1759    /// ```
1760    /// use std::io::{self, Write};
1761    /// let buffer = vec![1, 2, 3, 5, 8];
1762    /// io::sink().write(buffer.as_slice()).unwrap();
1763    /// ```
1764    #[inline]
1765    #[stable(feature = "vec_as_slice", since = "1.7.0")]
1766    #[rustc_diagnostic_item = "vec_as_slice"]
1767    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1768    pub const fn as_slice(&self) -> &[T] {
1769        // SAFETY: `slice::from_raw_parts` requires pointee is a contiguous, aligned buffer of size
1770        // `len` containing properly-initialized `T`s. Data must not be mutated for the returned
1771        // lifetime. Further, `len * size_of::<T>` <= `isize::MAX`, and allocation does not
1772        // "wrap" through overflowing memory addresses.
1773        //
1774        // * Vec API guarantees that self.buf:
1775        //      * contains only properly-initialized items within 0..len
1776        //      * is aligned, contiguous, and valid for `len` reads
1777        //      * obeys size and address-wrapping constraints
1778        //
1779        // * We only construct `&mut` references to `self.buf` through `&mut self` methods; borrow-
1780        //   check ensures that it is not possible to mutably alias `self.buf` within the
1781        //   returned lifetime.
1782        unsafe {
1783            // normally this would use `slice::from_raw_parts`, but it's
1784            // instantiated often enough that avoiding the UB check is worth it
1785            &*core::intrinsics::aggregate_raw_ptr::<*const [T], _, _>(self.as_ptr(), self.len)
1786        }
1787    }
1788
1789    /// Extracts a mutable slice of the entire vector.
1790    ///
1791    /// Equivalent to `&mut s[..]`.
1792    ///
1793    /// # Examples
1794    ///
1795    /// ```
1796    /// use std::io::{self, Read};
1797    /// let mut buffer = vec![0; 3];
1798    /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
1799    /// ```
1800    #[inline]
1801    #[stable(feature = "vec_as_slice", since = "1.7.0")]
1802    #[rustc_diagnostic_item = "vec_as_mut_slice"]
1803    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1804    pub const fn as_mut_slice(&mut self) -> &mut [T] {
1805        // SAFETY: `BufWriter::flush_buf` assumes that this will not
1806        // de-initialize any elements of the spare capacity.
1807
1808        // SAFETY: `slice::from_raw_parts_mut` requires pointee is a contiguous, aligned buffer of
1809        // size `len` containing properly-initialized `T`s. Data must not be accessed through any
1810        // other pointer for the returned lifetime. Further, `len * size_of::<T>` <=
1811        // `isize::MAX` and allocation does not "wrap" through overflowing memory addresses.
1812        //
1813        // * Vec API guarantees that self.buf:
1814        //      * contains only properly-initialized items within 0..len
1815        //      * is aligned, contiguous, and valid for `len` reads
1816        //      * obeys size and address-wrapping constraints
1817        //
1818        // * We only construct references to `self.buf` through `&self` and `&mut self` methods;
1819        //   borrow-check ensures that it is not possible to construct a reference to `self.buf`
1820        //   within the returned lifetime.
1821        unsafe {
1822            // normally this would use `slice::from_raw_parts_mut`, but it's
1823            // instantiated often enough that avoiding the UB check is worth it
1824            &mut *core::intrinsics::aggregate_raw_ptr::<*mut [T], _, _>(self.as_mut_ptr(), self.len)
1825        }
1826    }
1827
1828    /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
1829    /// valid for zero sized reads if the vector [didn't allocate].
1830    ///
1831    /// The caller must ensure that the vector outlives the pointer this
1832    /// function returns, or else it will end up dangling.
1833    /// Modifying the vector may cause its buffer to be reallocated,
1834    /// which would also make any pointers to it invalid.
1835    ///
1836    /// The caller must also ensure that the memory the pointer (non-transitively) points to
1837    /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1838    /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1839    ///
1840    /// This method guarantees that for the purpose of the aliasing model, this method
1841    /// does not materialize a reference to the underlying slice, and thus the returned pointer
1842    /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1843    /// and [`as_non_null`].
1844    /// Note that calling other methods that materialize mutable references to the slice,
1845    /// or mutable references to specific elements you are planning on accessing through this pointer,
1846    /// as well as writing to those elements, may still invalidate this pointer.
1847    /// See the second example below for how this guarantee can be used.
1848    ///
1849    ///
1850    /// # Examples
1851    ///
1852    /// ```
1853    /// let x = vec![1, 2, 4];
1854    /// let x_ptr = x.as_ptr();
1855    ///
1856    /// unsafe {
1857    ///     for i in 0..x.len() {
1858    ///         assert_eq!(*x_ptr.add(i), 1 << i);
1859    ///     }
1860    /// }
1861    /// ```
1862    ///
1863    /// Due to the aliasing guarantee, the following code is legal:
1864    ///
1865    /// ```rust
1866    /// unsafe {
1867    ///     let mut v = vec![0, 1, 2];
1868    ///     let ptr1 = v.as_ptr();
1869    ///     let _ = ptr1.read();
1870    ///     let ptr2 = v.as_mut_ptr().offset(2);
1871    ///     ptr2.write(2);
1872    ///     // Notably, the write to `ptr2` did *not* invalidate `ptr1`
1873    ///     // because it mutated a different element:
1874    ///     let _ = ptr1.read();
1875    /// }
1876    /// ```
1877    ///
1878    /// [`as_mut_ptr`]: Vec::as_mut_ptr
1879    /// [`as_ptr`]: Vec::as_ptr
1880    /// [`as_non_null`]: Vec::as_non_null
1881    /// [didn't allocate]: self#memory-layout
1882    #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1883    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1884    #[rustc_never_returns_null_ptr]
1885    #[rustc_as_ptr]
1886    #[inline]
1887    pub const fn as_ptr(&self) -> *const T {
1888        // We shadow the slice method of the same name to avoid going through
1889        // `deref`, which creates an intermediate reference.
1890        self.buf.ptr()
1891    }
1892
1893    /// Returns a raw mutable pointer to the vector's buffer, or a dangling
1894    /// raw pointer valid for zero sized reads if the vector [didn't allocate].
1895    ///
1896    /// The caller must ensure that the vector outlives the pointer this
1897    /// function returns, or else it will end up dangling.
1898    /// Modifying the vector may cause its buffer to be reallocated,
1899    /// which would also make any pointers to it invalid.
1900    ///
1901    /// This method guarantees that for the purpose of the aliasing model, this method
1902    /// does not materialize a reference to the underlying slice, and thus the returned pointer
1903    /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1904    /// and [`as_non_null`].
1905    /// Note that calling other methods that materialize references to the slice,
1906    /// or references to specific elements you are planning on accessing through this pointer,
1907    /// may still invalidate this pointer.
1908    /// See the second example below for how this guarantee can be used.
1909    ///
1910    /// The method also guarantees that, as long as `T` is not zero-sized and the capacity is
1911    /// nonzero, the pointer may be passed into [`dealloc`] with a layout of
1912    /// `Layout::array::<T>(capacity)` in order to deallocate the backing memory. If this is done,
1913    /// be careful not to run the destructor of the `Vec`, as dropping it will result in
1914    /// double-frees. Wrapping the `Vec` in a [`ManuallyDrop`] is the typical way to achieve this.
1915    ///
1916    /// # Examples
1917    ///
1918    /// ```
1919    /// // Allocate vector big enough for 4 elements.
1920    /// let size = 4;
1921    /// let mut x: Vec<i32> = Vec::with_capacity(size);
1922    /// let x_ptr = x.as_mut_ptr();
1923    ///
1924    /// // Initialize elements via raw pointer writes, then set length.
1925    /// unsafe {
1926    ///     for i in 0..size {
1927    ///         *x_ptr.add(i) = i as i32;
1928    ///     }
1929    ///     x.set_len(size);
1930    /// }
1931    /// assert_eq!(&*x, &[0, 1, 2, 3]);
1932    /// ```
1933    ///
1934    /// Due to the aliasing guarantee, the following code is legal:
1935    ///
1936    /// ```rust
1937    /// unsafe {
1938    ///     let mut v = vec![0];
1939    ///     let ptr1 = v.as_mut_ptr();
1940    ///     ptr1.write(1);
1941    ///     let ptr2 = v.as_mut_ptr();
1942    ///     ptr2.write(2);
1943    ///     // Notably, the write to `ptr2` did *not* invalidate `ptr1`:
1944    ///     ptr1.write(3);
1945    /// }
1946    /// ```
1947    ///
1948    /// Deallocating a vector using [`Box`] (which uses [`dealloc`] internally):
1949    ///
1950    /// ```
1951    /// use std::mem::{ManuallyDrop, MaybeUninit};
1952    ///
1953    /// let mut v = ManuallyDrop::new(vec![0, 1, 2]);
1954    /// let ptr = v.as_mut_ptr();
1955    /// let capacity = v.capacity();
1956    /// let slice_ptr: *mut [MaybeUninit<i32>] =
1957    ///     std::ptr::slice_from_raw_parts_mut(ptr.cast(), capacity);
1958    /// drop(unsafe { Box::from_raw(slice_ptr) });
1959    /// ```
1960    ///
1961    /// [`as_mut_ptr`]: Vec::as_mut_ptr
1962    /// [`as_ptr`]: Vec::as_ptr
1963    /// [`as_non_null`]: Vec::as_non_null
1964    /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
1965    /// [`ManuallyDrop`]: core::mem::ManuallyDrop
1966    /// [didn't allocate]: self#memory-layout
1967    #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1968    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1969    #[rustc_never_returns_null_ptr]
1970    #[rustc_as_ptr]
1971    #[inline]
1972    pub const fn as_mut_ptr(&mut self) -> *mut T {
1973        // We shadow the slice method of the same name to avoid going through
1974        // `deref_mut`, which creates an intermediate reference.
1975        self.buf.ptr()
1976    }
1977
1978    /// Returns a `NonNull` pointer to the vector's buffer, or a dangling
1979    /// `NonNull` pointer valid for zero sized reads if the vector [didn't allocate].
1980    ///
1981    /// The caller must ensure that the vector outlives the pointer this
1982    /// function returns, or else it will end up dangling.
1983    /// Modifying the vector may cause its buffer to be reallocated,
1984    /// which would also make any pointers to it invalid.
1985    ///
1986    /// This method guarantees that for the purpose of the aliasing model, this method
1987    /// does not materialize a reference to the underlying slice, and thus the returned pointer
1988    /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1989    /// and [`as_non_null`].
1990    /// Note that calling other methods that materialize references to the slice,
1991    /// or references to specific elements you are planning on accessing through this pointer,
1992    /// may still invalidate this pointer.
1993    /// See the second example below for how this guarantee can be used.
1994    ///
1995    /// # Examples
1996    ///
1997    /// ```
1998    /// #![feature(vec_as_non_null)]
1999    ///
2000    /// // Allocate vector big enough for 4 elements.
2001    /// let size = 4;
2002    /// let mut x: Vec<i32> = Vec::with_capacity(size);
2003    /// let x_ptr = x.as_non_null();
2004    ///
2005    /// // Initialize elements via raw pointer writes, then set length.
2006    /// unsafe {
2007    ///     for i in 0..size {
2008    ///         x_ptr.add(i).write(i as i32);
2009    ///     }
2010    ///     x.set_len(size);
2011    /// }
2012    /// assert_eq!(&*x, &[0, 1, 2, 3]);
2013    /// ```
2014    ///
2015    /// Due to the aliasing guarantee, the following code is legal:
2016    ///
2017    /// ```rust
2018    /// #![feature(vec_as_non_null)]
2019    ///
2020    /// unsafe {
2021    ///     let mut v = vec![0];
2022    ///     let ptr1 = v.as_non_null();
2023    ///     ptr1.write(1);
2024    ///     let ptr2 = v.as_non_null();
2025    ///     ptr2.write(2);
2026    ///     // Notably, the write to `ptr2` did *not* invalidate `ptr1`:
2027    ///     ptr1.write(3);
2028    /// }
2029    /// ```
2030    ///
2031    /// [`as_mut_ptr`]: Vec::as_mut_ptr
2032    /// [`as_ptr`]: Vec::as_ptr
2033    /// [`as_non_null`]: Vec::as_non_null
2034    /// [didn't allocate]: self#memory-layout
2035    #[unstable(feature = "vec_as_non_null", issue = "157843")]
2036    #[rustc_const_unstable(feature = "vec_as_non_null", issue = "157843")]
2037    #[rustc_as_ptr]
2038    #[inline]
2039    pub const fn as_non_null(&mut self) -> NonNull<T> {
2040        self.buf.non_null()
2041    }
2042
2043    /// Returns a reference to the underlying allocator.
2044    #[stable(feature = "allocator_api", since = "1.100.0")]
2045    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
2046    #[inline]
2047    pub const fn allocator(&self) -> &A {
2048        self.buf.allocator()
2049    }
2050
2051    /// Forces the length of the vector to `new_len`.
2052    ///
2053    /// This is a low-level operation that maintains none of the normal
2054    /// invariants of the type. Normally changing the length of a vector
2055    /// is done using one of the safe operations instead, such as
2056    /// [`truncate`], [`resize`], [`extend`], or [`clear`].
2057    ///
2058    /// [`truncate`]: Vec::truncate
2059    /// [`resize`]: Vec::resize
2060    /// [`extend`]: Extend::extend
2061    /// [`clear`]: Vec::clear
2062    ///
2063    /// # Safety
2064    ///
2065    /// - `new_len` must be less than or equal to [`capacity()`].
2066    /// - The elements at `old_len..new_len` must be initialized.
2067    ///
2068    /// [`capacity()`]: Vec::capacity
2069    ///
2070    /// # Examples
2071    ///
2072    /// See [`spare_capacity_mut()`] for an example with safe
2073    /// initialization of capacity elements and use of this method.
2074    ///
2075    /// `set_len()` can be useful for situations in which the vector
2076    /// is serving as a buffer for other code, particularly over FFI:
2077    ///
2078    /// ```no_run
2079    /// # #![allow(dead_code)]
2080    /// # // This is just a minimal skeleton for the doc example;
2081    /// # // don't use this as a starting point for a real library.
2082    /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void }
2083    /// # const Z_OK: i32 = 0;
2084    /// # unsafe extern "C" {
2085    /// #     fn deflateGetDictionary(
2086    /// #         strm: *mut std::ffi::c_void,
2087    /// #         dictionary: *mut u8,
2088    /// #         dictLength: *mut usize,
2089    /// #     ) -> i32;
2090    /// # }
2091    /// # impl StreamWrapper {
2092    /// pub fn get_dictionary(&self) -> Option<Vec<u8>> {
2093    ///     // Per the FFI method's docs, "32768 bytes is always enough".
2094    ///     let mut dict = Vec::with_capacity(32_768);
2095    ///     let mut dict_length = 0;
2096    ///     // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
2097    ///     // 1. `dict_length` elements were initialized.
2098    ///     // 2. `dict_length` <= the capacity (32_768)
2099    ///     // which makes `set_len` safe to call.
2100    ///     unsafe {
2101    ///         // Make the FFI call...
2102    ///         let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
2103    ///         if r == Z_OK {
2104    ///             // ...and update the length to what was initialized.
2105    ///             dict.set_len(dict_length);
2106    ///             Some(dict)
2107    ///         } else {
2108    ///             None
2109    ///         }
2110    ///     }
2111    /// }
2112    /// # }
2113    /// ```
2114    ///
2115    /// While the following example is sound, there is a memory leak since
2116    /// the inner vectors were not freed prior to the `set_len` call:
2117    ///
2118    /// ```
2119    /// let mut vec = vec![vec![1, 0, 0],
2120    ///                    vec![0, 1, 0],
2121    ///                    vec![0, 0, 1]];
2122    /// // SAFETY:
2123    /// // 1. `old_len..0` is empty so no elements need to be initialized.
2124    /// // 2. `0 <= capacity` always holds whatever `capacity` is.
2125    /// unsafe {
2126    ///     vec.set_len(0);
2127    /// #   // FIXME(https://github.com/rust-lang/miri/issues/3670):
2128    /// #   // use -Zmiri-disable-leak-check instead of unleaking in tests meant to leak.
2129    /// #   vec.set_len(3);
2130    /// }
2131    /// ```
2132    ///
2133    /// Normally, here, one would use [`clear`] instead to correctly drop
2134    /// the contents and thus not leak memory.
2135    ///
2136    /// [`spare_capacity_mut()`]: Vec::spare_capacity_mut
2137    #[inline]
2138    #[stable(feature = "rust1", since = "1.0.0")]
2139    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
2140    pub const unsafe fn set_len(&mut self, new_len: usize) {
2141        ub_checks::assert_unsafe_precondition!(
2142            check_library_ub,
2143            "Vec::set_len requires that new_len <= capacity()",
2144            (new_len: usize = new_len, capacity: usize = self.capacity()) => new_len <= capacity
2145        );
2146
2147        self.len = new_len;
2148    }
2149
2150    /// Removes an element from the vector and returns it.
2151    ///
2152    /// The removed element is replaced by the last element of the vector.
2153    ///
2154    /// This does not preserve ordering of the remaining elements, but is *O*(1).
2155    /// If you need to preserve the element order, use [`remove`] instead.
2156    ///
2157    /// [`remove`]: Vec::remove
2158    ///
2159    /// # Panics
2160    ///
2161    /// Panics if `index` is out of bounds.
2162    ///
2163    /// # Examples
2164    ///
2165    /// ```
2166    /// let mut v = vec!["foo", "bar", "baz", "qux"];
2167    ///
2168    /// assert_eq!(v.swap_remove(1), "bar");
2169    /// assert_eq!(v, ["foo", "qux", "baz"]);
2170    ///
2171    /// assert_eq!(v.swap_remove(0), "foo");
2172    /// assert_eq!(v, ["baz", "qux"]);
2173    /// ```
2174    #[inline]
2175    #[stable(feature = "rust1", since = "1.0.0")]
2176    pub fn swap_remove(&mut self, index: usize) -> T {
2177        #[cold]
2178        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
2179        #[optimize(size)]
2180        fn assert_failed(index: usize, len: usize) -> ! {
2181            panic!("swap_remove index (is {index}) should be < len (is {len})");
2182        }
2183
2184        let len = self.len();
2185        if index >= len {
2186            assert_failed(index, len);
2187        }
2188        // ignore-tidy-undocumented-unsafe
2189        unsafe {
2190            // We replace self[index] with the last element. Note that if the
2191            // bounds check above succeeds there must be a last element (which
2192            // can be self[index] itself).
2193            let value = ptr::read(self.as_ptr().add(index));
2194            let base_ptr = self.as_mut_ptr();
2195            ptr::copy(base_ptr.add(len - 1), base_ptr.add(index), 1);
2196            self.set_len(len - 1);
2197            value
2198        }
2199    }
2200
2201    /// Inserts an element at position `index` within the vector, shifting all
2202    /// elements after it to the right.
2203    ///
2204    /// # Panics
2205    ///
2206    /// Panics if `index > len`.
2207    ///
2208    /// # Examples
2209    ///
2210    /// ```
2211    /// let mut vec = vec!['a', 'b', 'c'];
2212    /// vec.insert(1, 'd');
2213    /// assert_eq!(vec, ['a', 'd', 'b', 'c']);
2214    /// vec.insert(4, 'e');
2215    /// assert_eq!(vec, ['a', 'd', 'b', 'c', 'e']);
2216    /// ```
2217    ///
2218    /// # Time complexity
2219    ///
2220    /// Takes *O*([`Vec::len`]) time. All items after the insertion index must be
2221    /// shifted to the right. In the worst case, all elements are shifted when
2222    /// the insertion index is 0.
2223    #[cfg(not(no_global_oom_handling))]
2224    #[stable(feature = "rust1", since = "1.0.0")]
2225    #[track_caller]
2226    pub fn insert(&mut self, index: usize, element: T) {
2227        let _ = self.insert_mut(index, element);
2228    }
2229
2230    /// Inserts an element at position `index` within the vector, shifting all
2231    /// elements after it to the right, and returning a reference to the new
2232    /// element.
2233    ///
2234    /// # Panics
2235    ///
2236    /// Panics if `index > len`.
2237    ///
2238    /// # Examples
2239    ///
2240    /// ```
2241    /// let mut vec = vec![1, 3, 5, 9];
2242    /// let x = vec.insert_mut(3, 6);
2243    /// *x += 1;
2244    /// assert_eq!(vec, [1, 3, 5, 7, 9]);
2245    /// ```
2246    ///
2247    /// # Time complexity
2248    ///
2249    /// Takes *O*([`Vec::len`]) time. All items after the insertion index must be
2250    /// shifted to the right. In the worst case, all elements are shifted when
2251    /// the insertion index is 0.
2252    #[cfg(not(no_global_oom_handling))]
2253    #[inline]
2254    #[stable(feature = "push_mut", since = "1.95.0")]
2255    #[track_caller]
2256    #[must_use = "if you don't need a reference to the value, use `Vec::insert` instead"]
2257    pub fn insert_mut(&mut self, index: usize, element: T) -> &mut T {
2258        #[cold]
2259        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
2260        #[track_caller]
2261        #[optimize(size)]
2262        fn assert_failed(index: usize, len: usize) -> ! {
2263            panic!("insertion index (is {index}) should be <= len (is {len})");
2264        }
2265
2266        let len = self.len();
2267        if index > len {
2268            assert_failed(index, len);
2269        }
2270
2271        // space for the new element
2272        if len == self.buf.capacity() {
2273            self.buf.grow_one();
2274        }
2275
2276        // ignore-tidy-undocumented-unsafe
2277        unsafe {
2278            // infallible
2279            // The spot to put the new value
2280            let p = self.as_mut_ptr().add(index);
2281            {
2282                if index < len {
2283                    // Shift everything over to make space. (Duplicating the
2284                    // `index`th element into two consecutive places.)
2285                    ptr::copy(p, p.add(1), len - index);
2286                }
2287                // Write it in, overwriting the first copy of the `index`th
2288                // element.
2289                ptr::write(p, element);
2290            }
2291            self.set_len(len + 1);
2292            &mut *p
2293        }
2294    }
2295
2296    /// Removes and returns the element at position `index` within the vector,
2297    /// shifting all elements after it to the left.
2298    ///
2299    /// Note: Because this shifts over the remaining elements, it has a
2300    /// worst-case performance of *O*(*n*). If you don't need the order of elements
2301    /// to be preserved, use [`swap_remove`] instead. If you'd like to remove
2302    /// elements from the beginning of the `Vec`, consider using
2303    /// [`VecDeque::pop_front`] instead.
2304    ///
2305    /// [`swap_remove`]: Vec::swap_remove
2306    /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2307    ///
2308    /// # Panics
2309    ///
2310    /// Panics if `index` is out of bounds.
2311    ///
2312    /// # Examples
2313    ///
2314    /// ```
2315    /// let mut v = vec!['a', 'b', 'c'];
2316    /// assert_eq!(v.remove(1), 'b');
2317    /// assert_eq!(v, ['a', 'c']);
2318    /// ```
2319    #[stable(feature = "rust1", since = "1.0.0")]
2320    #[track_caller]
2321    #[rustc_confusables("delete", "take")]
2322    pub fn remove(&mut self, index: usize) -> T {
2323        #[cold]
2324        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
2325        #[track_caller]
2326        #[optimize(size)]
2327        fn assert_failed(index: usize, len: usize) -> ! {
2328            panic!("removal index (is {index}) should be < len (is {len})");
2329        }
2330
2331        match self.try_remove(index) {
2332            Some(elem) => elem,
2333            None => assert_failed(index, self.len()),
2334        }
2335    }
2336
2337    /// Remove and return the element at position `index` within the vector,
2338    /// shifting all elements after it to the left, or [`None`] if it does not
2339    /// exist.
2340    ///
2341    /// Note: Because this shifts over the remaining elements, it has a
2342    /// worst-case performance of *O*(*n*). If you'd like to remove
2343    /// elements from the beginning of the `Vec`, consider using
2344    /// [`VecDeque::pop_front`] instead.
2345    ///
2346    /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2347    ///
2348    /// # Examples
2349    ///
2350    /// ```
2351    /// let mut v = vec![1, 2, 3];
2352    /// assert_eq!(v.try_remove(0), Some(1));
2353    /// assert_eq!(v.try_remove(2), None);
2354    /// ```
2355    #[stable(feature = "vec_try_remove", since = "CURRENT_RUSTC_VERSION")]
2356    #[rustc_confusables("delete", "take", "remove")]
2357    pub fn try_remove(&mut self, index: usize) -> Option<T> {
2358        let len = self.len();
2359        if index >= len {
2360            return None;
2361        }
2362        // infallible
2363        let ret;
2364        // ignore-tidy-undocumented-unsafe
2365        unsafe {
2366            {
2367                // the place we are taking from.
2368                let ptr = self.as_mut_ptr().add(index);
2369                // copy it out, unsafely having a copy of the value on
2370                // the stack and in the vector at the same time.
2371                ret = ptr::read(ptr);
2372
2373                // Shift everything down to fill in that spot.
2374                ptr::copy(ptr.add(1), ptr, len - index - 1);
2375            }
2376            self.set_len(len - 1);
2377        }
2378        Some(ret)
2379    }
2380
2381    /// Retains only the elements specified by the predicate.
2382    ///
2383    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
2384    /// This method operates in place, visiting each element exactly once in the
2385    /// original order, and preserves the order of the retained elements.
2386    ///
2387    /// # Examples
2388    ///
2389    /// ```
2390    /// let mut vec = vec![1, 2, 3, 4];
2391    /// vec.retain(|&x| x % 2 == 0);
2392    /// assert_eq!(vec, [2, 4]);
2393    /// ```
2394    ///
2395    /// Because the elements are visited exactly once in the original order,
2396    /// external state may be used to decide which elements to keep.
2397    ///
2398    /// ```
2399    /// let mut vec = vec![1, 2, 3, 4, 5];
2400    /// let keep = [false, true, true, false, true];
2401    /// let mut iter = keep.iter();
2402    /// vec.retain(|_| *iter.next().unwrap());
2403    /// assert_eq!(vec, [2, 3, 5]);
2404    /// ```
2405    #[stable(feature = "rust1", since = "1.0.0")]
2406    pub fn retain<F>(&mut self, mut f: F)
2407    where
2408        F: FnMut(&T) -> bool,
2409    {
2410        self.retain_mut(|elem| f(elem));
2411    }
2412
2413    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
2414    ///
2415    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
2416    /// This method operates in place, visiting each element exactly once in the
2417    /// original order, and preserves the order of the retained elements.
2418    ///
2419    /// # Examples
2420    ///
2421    /// ```
2422    /// let mut vec = vec![1, 2, 3, 4];
2423    /// vec.retain_mut(|x| if *x <= 3 {
2424    ///     *x += 1;
2425    ///     true
2426    /// } else {
2427    ///     false
2428    /// });
2429    /// assert_eq!(vec, [2, 3, 4]);
2430    /// ```
2431    #[stable(feature = "vec_retain_mut", since = "1.61.0")]
2432    pub fn retain_mut<F>(&mut self, mut f: F)
2433    where
2434        F: FnMut(&mut T) -> bool,
2435    {
2436        let original_len = self.len();
2437
2438        if original_len == 0 {
2439            // Empty case: explicit return allows better optimization, vs letting compiler infer it
2440            return;
2441        }
2442
2443        #[cfg(all(target_arch = "aarch64", target_feature = "sve"))]
2444        {
2445            let long_enough = match mem::size_of::<T>() {
2446                1 => original_len >= sve_retain::MIN_SVE_SIZE_1,
2447                2 => original_len >= sve_retain::MIN_SVE_SIZE_2,
2448                4 => original_len >= sve_retain::MIN_SVE_SIZE_4,
2449                8 => original_len >= sve_retain::MIN_SVE_SIZE_8,
2450                _ => false,
2451            };
2452            if long_enough {
2453                // SAFETY: size_of::<T>() is 1, 2, 4 or 8, matching
2454                // the kernel lane widths.
2455                return unsafe { sve_retain::chunked_retain(self, f) };
2456            }
2457        }
2458
2459        // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
2460        //      |            ^- write                ^- read             |
2461        //      |<-              original_len                          ->|
2462        // Kept: Elements which predicate returns true on.
2463        // Hole: Moved or dropped element slot.
2464        // Unchecked: Unchecked valid elements.
2465        //
2466        // This drop guard will be invoked when predicate or `drop` of element panicked.
2467        // It shifts unchecked elements to cover holes and `set_len` to the correct length.
2468        // In cases when predicate and `drop` never panick, it will be optimized out.
2469        struct PanicGuard<'a, T, A: Allocator> {
2470            v: &'a mut Vec<T, A>,
2471            read: usize,
2472            write: usize,
2473            original_len: usize,
2474        }
2475
2476        impl<T, A: Allocator> Drop for PanicGuard<'_, T, A> {
2477            #[cold]
2478            fn drop(&mut self) {
2479                let remaining = self.original_len - self.read;
2480                // SAFETY: Trailing unchecked items must be valid since we never touch them.
2481                unsafe {
2482                    ptr::copy(
2483                        self.v.as_ptr().add(self.read),
2484                        self.v.as_mut_ptr().add(self.write),
2485                        remaining,
2486                    );
2487                }
2488                // SAFETY: After filling holes, all items are in contiguous memory.
2489                unsafe {
2490                    self.v.set_len(self.write + remaining);
2491                }
2492            }
2493        }
2494
2495        let mut read = 0;
2496        loop {
2497            // SAFETY: read < original_len
2498            let cur = unsafe { self.get_unchecked_mut(read) };
2499            if hint::unlikely(!f(cur)) {
2500                break;
2501            }
2502            read += 1;
2503            if read == original_len {
2504                // All elements are kept, return early.
2505                return;
2506            }
2507        }
2508
2509        // Critical section starts here and at least one element is going to be removed.
2510        // Advance `g.read` early to avoid double drop if `drop_in_place` panicked.
2511        let mut g = PanicGuard { v: self, read: read + 1, write: read, original_len };
2512        // SAFETY: previous `read` is always less than original_len.
2513        unsafe { ptr::drop_in_place(&mut *g.v.as_mut_ptr().add(read)) };
2514
2515        while g.read < g.original_len {
2516            // SAFETY: `read` is always less than original_len.
2517            let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.read) };
2518            if !f(cur) {
2519                // Advance `read` early to avoid double drop if `drop_in_place` panicked.
2520                g.read += 1;
2521                // SAFETY: We never touch this element again after dropped.
2522                unsafe { ptr::drop_in_place(cur) };
2523            } else {
2524                // SAFETY: `read` > `write`, so the slots don't overlap.
2525                // We use copy for move, and never touch the source element again.
2526                unsafe {
2527                    let hole = g.v.as_mut_ptr().add(g.write);
2528                    ptr::copy_nonoverlapping(cur, hole, 1);
2529                }
2530                g.write += 1;
2531                g.read += 1;
2532            }
2533        }
2534
2535        // We are leaving the critical section and no panic happened,
2536        // Commit the length change and forget the guard.
2537        // SAFETY: `write` is always less than or equal to original_len.
2538        unsafe { g.v.set_len(g.write) };
2539        mem::forget(g);
2540    }
2541
2542    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
2543    ///
2544    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
2545    /// This method does not maintain the relative order of the retained elements. If order matters,
2546    /// consider using [`Vec::retain_mut`] instead. However, if no items are removed, then all items
2547    /// are left in their original positions.
2548    ///
2549    /// [`Vec::retain_mut`]: crate::vec::Vec::retain_mut
2550    ///
2551    /// Time complexity: *O*(*n*)
2552    ///
2553    ///
2554    /// # Examples
2555    ///
2556    /// ```
2557    /// #![feature(retain_unstable)]
2558    /// let mut vec = vec![4, 3, 2, 1];
2559    /// vec.retain_unstable(|x| if *x <= 3 {
2560    ///     *x += 1;
2561    ///     true
2562    /// } else {
2563    ///     false
2564    /// });
2565    ///
2566    /// vec.sort(); // it might be in any order, so normalize before asserting
2567    /// assert_eq!(vec, [2, 3, 4]);
2568    /// ```
2569    #[unstable(feature = "retain_unstable", issue = "164152")]
2570    pub fn retain_unstable<F>(&mut self, mut f: F)
2571    where
2572        F: FnMut(&mut T) -> bool,
2573    {
2574        // Currently this does the following:
2575        // 1) Search backward until you find an element you want to remove
2576        // 2) Swap this element with an element that was kept in the back
2577        //    (or if there are no remaining elements, simply truncate the vec)
2578        // 3) Repeat from 1) until there's no element to iterate through
2579
2580        let original_len = self.len();
2581
2582        if original_len == 0 {
2583            // Empty case: explicit return allows better optimization, vs letting compiler infer it
2584            return;
2585        }
2586
2587        let mut read_back = original_len;
2588        let mut hole = loop {
2589            if read_back == 0 {
2590                // All elements are kept
2591                return;
2592            }
2593            // SAFETY: read_back - 1 < original_len
2594            let cur = unsafe { &mut *self.as_mut_ptr().add(read_back - 1) };
2595            if hint::unlikely(!f(cur)) {
2596                break cur;
2597            }
2598            read_back -= 1;
2599        };
2600
2601        if read_back < self.len {
2602            let swap = self.pop().unwrap();
2603            *hole = swap;
2604        } else {
2605            self.truncate(self.len - 1);
2606        }
2607        read_back -= 1;
2608
2609        while read_back > 0 {
2610            // SAFETY: read_back - 1 is always less than current length of
2611            // the vector and the loop condition, read_back > 0, prevents
2612            // read_back from underflowing
2613            hole = unsafe { &mut *self.as_mut_ptr().add(read_back - 1) };
2614            if !f(hole) {
2615                if read_back < self.len {
2616                    let swap = self.pop().unwrap();
2617                    *hole = swap;
2618                } else {
2619                    self.truncate(self.len - 1);
2620                }
2621            }
2622            read_back -= 1;
2623        }
2624    }
2625
2626    /// Removes all but the first of consecutive elements in the vector that resolve to the same
2627    /// key.
2628    ///
2629    /// If the vector is sorted, this removes all duplicates.
2630    ///
2631    /// # Examples
2632    ///
2633    /// ```
2634    /// let mut vec = vec![10, 20, 21, 30, 20];
2635    ///
2636    /// vec.dedup_by_key(|i| *i / 10);
2637    ///
2638    /// assert_eq!(vec, [10, 20, 30, 20]);
2639    /// ```
2640    #[stable(feature = "dedup_by", since = "1.16.0")]
2641    #[inline]
2642    pub fn dedup_by_key<F, K>(&mut self, mut key: F)
2643    where
2644        F: FnMut(&mut T) -> K,
2645        K: PartialEq,
2646    {
2647        self.dedup_by(|a, b| key(a) == key(b))
2648    }
2649
2650    /// Removes all but the first of consecutive elements in the vector that are
2651    /// "equal" according to the given predicate function.
2652    ///
2653    /// The predicate `same_bucket(x, p)` is passed references to two elements.
2654    /// If it returns `true`, the element `x` is removed from the vector.
2655    ///
2656    /// The element `p` occurs *before* `x` in the vector (`[.., p, .., x, ..]`),
2657    /// so `same_bucket(x, p)` is receiving them in reversed order (unlike [`windows`]).
2658    ///
2659    /// If the vector is sorted, this removes all duplicates. For more complicated predicates
2660    /// however, the order (ascending vs. descending) can matter.
2661    ///
2662    /// [`windows`]: slice::windows
2663    ///
2664    /// # Examples
2665    ///
2666    /// ```
2667    /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
2668    /// vec.dedup_by(|x, p| x.eq_ignore_ascii_case(p));
2669    /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
2670    /// ```
2671    ///
2672    /// Both references passed to `same_bucket` are mutable.
2673    /// This allows merging elements by mutating `p` and returning `true`:
2674    ///
2675    /// ```
2676    /// let mut ranges = vec![1..2, 2..4, 2..5, 8..9];
2677    ///
2678    /// // Sort ranges by start, and if equal, by end (lexicographically)
2679    /// // Sorting in reverse instead (`x.start.cmp(&p.start)...`) would later fail
2680    /// ranges.sort_unstable_by(|p, x| p.start.cmp(&x.start).then(p.end.cmp(&x.end)));
2681    ///
2682    /// // Merge touching (`1..2` and `2..4`) and then overlapping (`1..4` and `2..5`) ranges
2683    /// ranges.dedup_by(|x, p| {
2684    ///     if p.end >= x.start {
2685    ///         p.end = p.end.max(x.end);
2686    ///         true
2687    ///     } else {
2688    ///         false
2689    ///     }
2690    /// });
2691    ///
2692    /// assert_eq!(ranges, [1..5, 8..9]);
2693    /// ```
2694    #[stable(feature = "dedup_by", since = "1.16.0")]
2695    pub fn dedup_by<F>(&mut self, mut same_bucket: F)
2696    where
2697        F: FnMut(&mut T, &mut T) -> bool,
2698    {
2699        let len = self.len();
2700        if len <= 1 {
2701            return;
2702        }
2703
2704        // Check if we ever want to remove anything.
2705        // This allows to use copy_non_overlapping in next cycle.
2706        // And avoids any memory writes if we don't need to remove anything.
2707        let mut first_duplicate_idx: usize = 1;
2708        let start = self.as_mut_ptr();
2709        while first_duplicate_idx != len {
2710            let found_duplicate = {
2711                // SAFETY: first_duplicate always in range [1..len).
2712                // Note that we start iteration from 1 so we never overflow.
2713                let prev = unsafe { start.add(first_duplicate_idx.wrapping_sub(1)) };
2714                // ignore-tidy-undocumented-unsafe
2715                let current = unsafe { start.add(first_duplicate_idx) };
2716                // We explicitly say in docs that references are reversed.
2717                // ignore-tidy-undocumented-unsafe
2718                unsafe { same_bucket(&mut *current, &mut *prev) }
2719            };
2720            if found_duplicate {
2721                break;
2722            }
2723            first_duplicate_idx += 1;
2724        }
2725        // Don't need to remove anything.
2726        // We cannot get bigger than len.
2727        if first_duplicate_idx == len {
2728            return;
2729        }
2730        // SAFETY: first_duplicate_idx always in range [1..len)
2731        unsafe {
2732            self.dedup_tail(same_bucket, first_duplicate_idx);
2733        }
2734    }
2735
2736    /// Continues deduplication after the first duplicate is found.
2737    ///
2738    /// The function treats `self[first_duplicate]` as the first duplicated
2739    /// element and drops it.
2740    ///
2741    /// # Safety
2742    ///
2743    /// `1 <= first_duplicate < self.len()`
2744    unsafe fn dedup_tail<F>(&mut self, mut same_bucket: F, first_duplicate: usize)
2745    where
2746        F: FnMut(&mut T, &mut T) -> bool,
2747    {
2748        /* INVARIANT: vec.len() > read > write > write-1 >= 0 */
2749        struct FillGapOnDrop<'a, T, A: core::alloc::Allocator> {
2750            /* Offset of the element we want to check if it is duplicate */
2751            read: usize,
2752
2753            /* Offset of the place where we want to place the non-duplicate
2754             * when we find it. */
2755            write: usize,
2756
2757            /* The Vec that would need correction if `same_bucket` panicked */
2758            vec: &'a mut Vec<T, A>,
2759        }
2760
2761        impl<'a, T, A: core::alloc::Allocator> Drop for FillGapOnDrop<'a, T, A> {
2762            fn drop(&mut self) {
2763                /* This code gets executed when `same_bucket` panics */
2764
2765                // SAFETY: invariant guarantees that `read - write`
2766                // and `len - read` never overflow and that the copy is always
2767                // in-bounds.
2768                unsafe {
2769                    let ptr = self.vec.as_mut_ptr();
2770                    let len = self.vec.len();
2771
2772                    /* How many items were left when `same_bucket` panicked.
2773                     * Basically vec[read..].len() */
2774                    let items_left = len.wrapping_sub(self.read);
2775
2776                    /* Pointer to first item in vec[write..write+items_left] slice */
2777                    let dropped_ptr = ptr.add(self.write);
2778                    /* Pointer to first item in vec[read..] slice */
2779                    let valid_ptr = ptr.add(self.read);
2780
2781                    /* Copy `vec[read..]` to `vec[write..write+items_left]`.
2782                     * The slices can overlap, so `copy_nonoverlapping` cannot be used */
2783                    ptr::copy(valid_ptr, dropped_ptr, items_left);
2784
2785                    /* How many items have been already dropped
2786                     * Basically vec[read..write].len() */
2787                    let dropped = self.read.wrapping_sub(self.write);
2788
2789                    self.vec.set_len(len - dropped);
2790                }
2791            }
2792        }
2793
2794        let start = self.as_mut_ptr();
2795        let len = self.len();
2796
2797        /* Drop items while going through Vec, it should be more efficient than
2798         * doing slice partition_dedup + truncate */
2799
2800        // Construct gap first and then drop item to avoid memory corruption if `T::drop` panics.
2801        let mut gap =
2802            FillGapOnDrop { read: first_duplicate + 1, write: first_duplicate, vec: self };
2803
2804        // SAFETY: By this function's safety contract, `first_duplicate < self.len()`.
2805        // If drop panics, `gap` would remove this item without drop.
2806        unsafe {
2807            ptr::drop_in_place(start.add(first_duplicate));
2808        }
2809
2810        // SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr
2811        // are always in-bounds and read_ptr never aliases prev_ptr
2812        unsafe {
2813            while gap.read < len {
2814                let read_ptr = start.add(gap.read);
2815                let prev_ptr = start.add(gap.write.wrapping_sub(1));
2816
2817                // We explicitly say in docs that references are reversed.
2818                let found_duplicate = same_bucket(&mut *read_ptr, &mut *prev_ptr);
2819                if found_duplicate {
2820                    // Increase `gap.read` now since the drop may panic.
2821                    gap.read += 1;
2822                    /* We have found duplicate, drop it in-place */
2823                    ptr::drop_in_place(read_ptr);
2824                } else {
2825                    let write_ptr = start.add(gap.write);
2826
2827                    /* read_ptr cannot be equal to write_ptr because at this point
2828                     * we guaranteed to skip at least one element (before loop starts).
2829                     */
2830                    ptr::copy_nonoverlapping(read_ptr, write_ptr, 1);
2831
2832                    /* We have filled that place, so go further */
2833                    gap.write += 1;
2834                    gap.read += 1;
2835                }
2836            }
2837
2838            /* Technically we could let `gap` clean up with its Drop, but
2839             * when `same_bucket` is guaranteed to not panic, this bloats a little
2840             * the codegen, so we just do it manually */
2841            gap.vec.set_len(gap.write);
2842            mem::forget(gap);
2843        }
2844    }
2845
2846    /// Appends an element and returns a reference to it if there is sufficient spare capacity,
2847    /// otherwise an error is returned with the element.
2848    ///
2849    /// Unlike [`push`] this method will not reallocate when there's insufficient capacity.
2850    /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity.
2851    ///
2852    /// [`push`]: Vec::push
2853    /// [`reserve`]: Vec::reserve
2854    /// [`try_reserve`]: Vec::try_reserve
2855    ///
2856    /// # Examples
2857    ///
2858    /// A manual, panic-free alternative to [`FromIterator`]:
2859    ///
2860    /// ```
2861    /// #![feature(vec_push_within_capacity)]
2862    ///
2863    /// use std::collections::TryReserveError;
2864    /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> {
2865    ///     let mut vec = Vec::new();
2866    ///     for value in iter {
2867    ///         if let Err(value) = vec.push_within_capacity(value) {
2868    ///             vec.try_reserve(1)?;
2869    ///             // this cannot fail, the previous line either returned or added at least 1 free slot
2870    ///             let _ = vec.push_within_capacity(value);
2871    ///         }
2872    ///     }
2873    ///     Ok(vec)
2874    /// }
2875    /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100)));
2876    /// ```
2877    ///
2878    /// # Time complexity
2879    ///
2880    /// Takes *O*(1) time.
2881    #[inline]
2882    #[unstable(feature = "vec_push_within_capacity", issue = "100486")]
2883    pub fn push_within_capacity(&mut self, value: T) -> Result<&mut T, T> {
2884        if self.len == self.buf.capacity() {
2885            return Err(value);
2886        }
2887
2888        // ignore-tidy-undocumented-unsafe
2889        let end = unsafe { self.as_mut_ptr().add(self.len) };
2890        // ignore-tidy-undocumented-unsafe
2891        unsafe { ptr::write(end, value) };
2892        self.len += 1;
2893
2894        // SAFETY: We just wrote a value to the pointer that will live the lifetime of the reference.
2895        Ok(unsafe { &mut *end })
2896    }
2897
2898    /// Removes the last element from a vector and returns it, or [`None`] if it
2899    /// is empty.
2900    ///
2901    /// If you'd like to pop the first element, consider using
2902    /// [`VecDeque::pop_front`] instead.
2903    ///
2904    /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2905    ///
2906    /// # Examples
2907    ///
2908    /// ```
2909    /// let mut vec = vec![1, 2, 3];
2910    /// assert_eq!(vec.pop(), Some(3));
2911    /// assert_eq!(vec, [1, 2]);
2912    /// ```
2913    ///
2914    /// # Time complexity
2915    ///
2916    /// Takes *O*(1) time.
2917    #[inline]
2918    #[stable(feature = "rust1", since = "1.0.0")]
2919    #[rustc_diagnostic_item = "vec_pop"]
2920    pub fn pop(&mut self) -> Option<T> {
2921        if self.len == 0 {
2922            None
2923        } else {
2924            self.len -= 1;
2925            // ignore-tidy-undocumented-unsafe
2926            unsafe {
2927                core::hint::assert_unchecked(self.len < self.capacity());
2928                Some(ptr::read(self.as_ptr().add(self.len())))
2929            }
2930        }
2931    }
2932
2933    /// Removes and returns the last element from a vector if the predicate
2934    /// returns `true`, or [`None`] if the predicate returns false or the vector
2935    /// is empty (the predicate will not be called in that case).
2936    ///
2937    /// # Examples
2938    ///
2939    /// ```
2940    /// let mut vec = vec![1, 2, 3, 4];
2941    /// let pred = |x: &mut i32| *x % 2 == 0;
2942    ///
2943    /// assert_eq!(vec.pop_if(pred), Some(4));
2944    /// assert_eq!(vec, [1, 2, 3]);
2945    /// assert_eq!(vec.pop_if(pred), None);
2946    /// ```
2947    #[stable(feature = "vec_pop_if", since = "1.86.0")]
2948    pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
2949        let last = self.last_mut()?;
2950        if predicate(last) { self.pop() } else { None }
2951    }
2952
2953    /// Returns a mutable reference to the last item in the vector, or
2954    /// `None` if it is empty.
2955    ///
2956    /// # Examples
2957    ///
2958    /// Basic usage:
2959    ///
2960    /// ```
2961    /// #![feature(vec_peek_mut)]
2962    /// let mut vec = Vec::new();
2963    /// assert!(vec.peek_mut().is_none());
2964    ///
2965    /// vec.push(1);
2966    /// vec.push(5);
2967    /// vec.push(2);
2968    /// assert_eq!(vec.last(), Some(&2));
2969    /// if let Some(mut val) = vec.peek_mut() {
2970    ///     *val = 0;
2971    /// }
2972    /// assert_eq!(vec.last(), Some(&0));
2973    /// ```
2974    #[inline]
2975    #[unstable(feature = "vec_peek_mut", issue = "122742")]
2976    pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, A>>
2977    where
2978        A: AllocatorNightly,
2979    {
2980        PeekMut::new(self)
2981    }
2982
2983    /// Moves all the elements of `other` into `self`, leaving `other` empty.
2984    ///
2985    /// # Panics
2986    ///
2987    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
2988    ///
2989    /// # Examples
2990    ///
2991    /// ```
2992    /// let mut vec = vec![1, 2, 3];
2993    /// let mut vec2 = vec![4, 5, 6];
2994    /// vec.append(&mut vec2);
2995    /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
2996    /// assert_eq!(vec2, []);
2997    /// ```
2998    #[cfg(not(no_global_oom_handling))]
2999    #[inline]
3000    #[stable(feature = "append", since = "1.4.0")]
3001    pub fn append(&mut self, other: &mut Self) {
3002        // ignore-tidy-undocumented-unsafe
3003        unsafe {
3004            self.append_elements(other.as_slice() as _);
3005            other.set_len(0);
3006        }
3007    }
3008
3009    /// Appends elements to `self` from other buffer.
3010    #[cfg(not(no_global_oom_handling))]
3011    #[inline]
3012    unsafe fn append_elements(&mut self, other: *const [T]) {
3013        self.reserve(other.len());
3014        // ignore-tidy-undocumented-unsafe
3015        unsafe {
3016            self.append_elements_unreserved(other);
3017        }
3018    }
3019
3020    /// Appends elements to `self` from other buffer, returning [`TryReserveError`] on OOM.
3021    #[inline]
3022    unsafe fn try_append_elements(&mut self, other: *const [T]) -> Result<(), TryReserveError> {
3023        self.try_reserve(other.len())?;
3024        // ignore-tidy-undocumented-unsafe
3025        unsafe {
3026            self.append_elements_unreserved(other);
3027        }
3028        Ok(())
3029    }
3030
3031    /// Appends elements to `self` from other buffer without reserving additional capacity.
3032    #[inline]
3033    unsafe fn append_elements_unreserved(&mut self, other: *const [T]) {
3034        let count = other.len();
3035        let len = self.len();
3036        if count > 0 {
3037            // ignore-tidy-undocumented-unsafe
3038            unsafe {
3039                ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count)
3040            };
3041        }
3042        self.len += count;
3043    }
3044
3045    /// Removes the subslice indicated by the given range from the vector,
3046    /// returning a double-ended iterator over the removed subslice.
3047    ///
3048    /// If the iterator is dropped before being fully consumed,
3049    /// it drops the remaining removed elements.
3050    ///
3051    /// The returned iterator keeps a mutable borrow on the vector to optimize
3052    /// its implementation.
3053    ///
3054    /// # Panics
3055    ///
3056    /// Panics if the range has `start_bound > end_bound`, or, if the range is
3057    /// bounded on either end and past the length of the vector.
3058    ///
3059    /// # Leaking
3060    ///
3061    /// If the returned iterator goes out of scope without being dropped (due to
3062    /// [`mem::forget`], for example), the vector may have lost and leaked
3063    /// elements arbitrarily, including elements outside the range.
3064    ///
3065    /// # Examples
3066    ///
3067    /// ```
3068    /// let mut v = vec![1, 2, 3];
3069    /// let u: Vec<_> = v.drain(1..).collect();
3070    /// assert_eq!(v, &[1]);
3071    /// assert_eq!(u, &[2, 3]);
3072    ///
3073    /// // A full range clears the vector, like `clear()` does
3074    /// v.drain(..);
3075    /// assert_eq!(v, &[]);
3076    /// ```
3077    #[stable(feature = "drain", since = "1.6.0")]
3078    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
3079    where
3080        A: AllocatorNightly,
3081        R: RangeBounds<usize>,
3082    {
3083        // Memory safety
3084        //
3085        // When the Drain is first created, it shortens the length of
3086        // the source vector to make sure no uninitialized or moved-from elements
3087        // are accessible at all if the Drain's destructor never gets to run.
3088        //
3089        // Drain will ptr::read out the values to remove.
3090        // When finished, remaining tail of the vec is copied back to cover
3091        // the hole, and the vector length is restored to the new length.
3092        //
3093        let len = self.len();
3094        let Range { start, end } = slice::range(range, ..len);
3095
3096        // ignore-tidy-undocumented-unsafe
3097        unsafe {
3098            // set self.vec length's to start, to be safe in case Drain is leaked
3099            self.set_len(start);
3100            let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
3101            Drain {
3102                tail_start: end,
3103                tail_len: len - end,
3104                iter: range_slice.iter(),
3105                vec: NonNull::from(self),
3106            }
3107        }
3108    }
3109
3110    /// Clears the vector, removing all values.
3111    ///
3112    /// Note that this method has no effect on the allocated capacity
3113    /// of the vector.
3114    ///
3115    /// # Examples
3116    ///
3117    /// ```
3118    /// let mut v = vec![1, 2, 3];
3119    ///
3120    /// v.clear();
3121    ///
3122    /// assert!(v.is_empty());
3123    /// ```
3124    #[inline]
3125    #[stable(feature = "rust1", since = "1.0.0")]
3126    pub fn clear(&mut self) {
3127        // Though this is equivalent to `truncate(0)`, the manual version
3128        // optimizes better, justifying the additional complexity
3129        // (see #96002 and #154095 for context).
3130
3131        let elems: *mut [T] = self.as_mut_slice();
3132
3133        // SAFETY:
3134        // - `elems` comes directly from `as_mut_slice` and is therefore valid.
3135        // - Setting `self.len` before calling `drop_in_place` means that,
3136        //   if an element's `Drop` impl panics, the vector's `Drop` impl will
3137        //   do nothing (leaking the rest of the elements) instead of dropping
3138        //   some twice.
3139        unsafe {
3140            self.len = 0;
3141            ptr::drop_in_place(elems);
3142        }
3143    }
3144
3145    /// Returns the number of elements in the vector, also referred to
3146    /// as its 'length'.
3147    ///
3148    /// # Examples
3149    ///
3150    /// ```
3151    /// let a = vec![1, 2, 3];
3152    /// assert_eq!(a.len(), 3);
3153    /// ```
3154    #[inline]
3155    #[stable(feature = "rust1", since = "1.0.0")]
3156    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
3157    #[rustc_confusables("length", "size")]
3158    pub const fn len(&self) -> usize {
3159        let len = self.len;
3160
3161        // SAFETY: The maximum capacity of `Vec<T>` is `isize::MAX` bytes, so the maximum value can
3162        // be returned is `usize::checked_div(size_of::<T>()).unwrap_or(usize::MAX)`, which
3163        // matches the definition of `T::MAX_SLICE_LEN`.
3164        unsafe { intrinsics::assume(len <= T::MAX_SLICE_LEN) };
3165
3166        len
3167    }
3168
3169    /// Returns `true` if the vector contains no elements.
3170    ///
3171    /// # Examples
3172    ///
3173    /// ```
3174    /// let mut v = Vec::new();
3175    /// assert!(v.is_empty());
3176    ///
3177    /// v.push(1);
3178    /// assert!(!v.is_empty());
3179    /// ```
3180    #[stable(feature = "rust1", since = "1.0.0")]
3181    #[rustc_diagnostic_item = "vec_is_empty"]
3182    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
3183    pub const fn is_empty(&self) -> bool {
3184        self.len() == 0
3185    }
3186
3187    /// Splits the collection into two at the given index.
3188    ///
3189    /// Returns a newly allocated vector containing the elements in the range
3190    /// `[at, len)`. After the call, the original vector will be left containing
3191    /// the elements `[0, at)` with its previous capacity unchanged.
3192    ///
3193    /// - If you want to take ownership of the entire contents and capacity of
3194    ///   the vector, see [`mem::take`] or [`mem::replace`].
3195    /// - If you don't need the returned vector at all, see [`Vec::truncate`].
3196    /// - If you want to take ownership of an arbitrary subslice, or you don't
3197    ///   necessarily want to store the removed items in a vector, see [`Vec::drain`].
3198    ///
3199    /// # Panics
3200    ///
3201    /// Panics if `at > len`.
3202    ///
3203    /// # Examples
3204    ///
3205    /// ```
3206    /// let mut vec = vec!['a', 'b', 'c'];
3207    /// let vec2 = vec.split_off(1);
3208    /// assert_eq!(vec, ['a']);
3209    /// assert_eq!(vec2, ['b', 'c']);
3210    /// ```
3211    #[cfg(not(no_global_oom_handling))]
3212    #[inline]
3213    #[must_use = "use `.truncate()` if you don't need the other half"]
3214    #[stable(feature = "split_off", since = "1.4.0")]
3215    #[track_caller]
3216    pub fn split_off(&mut self, at: usize) -> Self
3217    where
3218        A: Clone,
3219    {
3220        #[cold]
3221        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
3222        #[track_caller]
3223        #[optimize(size)]
3224        fn assert_failed(at: usize, len: usize) -> ! {
3225            panic!("`at` split index (is {at}) should be <= len (is {len})");
3226        }
3227
3228        if at > self.len() {
3229            assert_failed(at, self.len());
3230        }
3231
3232        let other_len = self.len - at;
3233        let mut other = Vec::with_capacity_in(other_len, self.allocator().clone());
3234
3235        // Unsafely `set_len` and copy items to `other`.
3236        // ignore-tidy-undocumented-unsafe
3237        unsafe {
3238            self.set_len(at);
3239            other.set_len(other_len);
3240
3241            ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
3242        }
3243        other
3244    }
3245
3246    /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
3247    ///
3248    /// If `new_len` is greater than `len`, the `Vec` is extended by the
3249    /// difference, with each additional slot filled with the result of
3250    /// calling the closure `f`. The return values from `f` will end up
3251    /// in the `Vec` in the order they have been generated.
3252    ///
3253    /// If `new_len` is less than or equal to `len`, the `Vec` is simply
3254    /// truncated.
3255    ///
3256    /// This method uses a closure to create new values on every push. If
3257    /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you
3258    /// want to use the [`Default`] trait to generate values, you can
3259    /// pass [`Default::default`] as the second argument.
3260    ///
3261    /// # Panics
3262    ///
3263    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
3264    ///
3265    /// # Examples
3266    ///
3267    /// ```
3268    /// let mut vec = vec![1, 2, 3];
3269    /// vec.resize_with(5, Default::default);
3270    /// assert_eq!(vec, [1, 2, 3, 0, 0]);
3271    ///
3272    /// let mut vec = vec![];
3273    /// let mut p = 1;
3274    /// vec.resize_with(4, || { p *= 2; p });
3275    /// assert_eq!(vec, [2, 4, 8, 16]);
3276    /// ```
3277    #[cfg(not(no_global_oom_handling))]
3278    #[stable(feature = "vec_resize_with", since = "1.33.0")]
3279    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
3280    where
3281        F: FnMut() -> T,
3282    {
3283        let len = self.len();
3284        if new_len > len {
3285            self.extend_trusted(iter::repeat_with(f).take(new_len - len));
3286        } else {
3287            self.truncate(new_len);
3288        }
3289    }
3290
3291    /// Consumes and leaks the `Vec`, returning a mutable reference to the contents,
3292    /// `&'a mut [T]`.
3293    ///
3294    /// Note that the type `T` must outlive the chosen lifetime `'a`. If the type
3295    /// has only static references, or none at all, then this may be chosen to be
3296    /// `'static`.
3297    ///
3298    /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`,
3299    /// so the leaked allocation may include unused capacity that is not part
3300    /// of the returned slice.
3301    ///
3302    /// This function is mainly useful for data that lives for the remainder of
3303    /// the program's life. Dropping the returned reference will cause a memory
3304    /// leak.
3305    ///
3306    /// # Examples
3307    ///
3308    /// Simple usage:
3309    ///
3310    /// ```
3311    /// let x = vec![1, 2, 3];
3312    /// let static_ref: &'static mut [usize] = x.leak();
3313    /// static_ref[0] += 1;
3314    /// assert_eq!(static_ref, &[2, 2, 3]);
3315    /// # // FIXME(https://github.com/rust-lang/miri/issues/3670):
3316    /// # // use -Zmiri-disable-leak-check instead of unleaking in tests meant to leak.
3317    /// # drop(unsafe { Box::from_raw(static_ref) });
3318    /// ```
3319    #[stable(feature = "vec_leak", since = "1.47.0")]
3320    #[inline]
3321    pub fn leak<'a>(self) -> &'a mut [T]
3322    where
3323        A: 'a,
3324    {
3325        let mut me = ManuallyDrop::new(self);
3326        // ignore-tidy-undocumented-unsafe
3327        unsafe { slice::from_raw_parts_mut(me.as_mut_ptr(), me.len) }
3328    }
3329
3330    /// Returns the remaining spare capacity of the vector as a slice of
3331    /// `MaybeUninit<T>`.
3332    ///
3333    /// The returned slice can be used to fill the vector with data (e.g. by
3334    /// reading from a file) before marking the data as initialized using the
3335    /// [`set_len`] method.
3336    ///
3337    /// [`set_len`]: Vec::set_len
3338    ///
3339    /// # Examples
3340    ///
3341    /// ```
3342    /// // Allocate vector big enough for 10 elements.
3343    /// let mut v = Vec::with_capacity(10);
3344    ///
3345    /// // Fill in the first 3 elements.
3346    /// let uninit = v.spare_capacity_mut();
3347    /// uninit[0].write(0);
3348    /// uninit[1].write(1);
3349    /// uninit[2].write(2);
3350    ///
3351    /// // Mark the first 3 elements of the vector as being initialized.
3352    /// unsafe {
3353    ///     v.set_len(3);
3354    /// }
3355    ///
3356    /// assert_eq!(&v, &[0, 1, 2]);
3357    /// ```
3358    #[stable(feature = "vec_spare_capacity", since = "1.60.0")]
3359    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
3360    #[inline]
3361    pub const fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
3362        // Note:
3363        // This method is not implemented in terms of `split_at_spare_mut`,
3364        // to prevent invalidation of pointers to the buffer.
3365        // ignore-tidy-undocumented-unsafe
3366        unsafe {
3367            slice::from_raw_parts_mut(
3368                self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
3369                self.buf.capacity() - self.len,
3370            )
3371        }
3372    }
3373
3374    /// Returns vector content as a slice of `T`, along with the remaining spare
3375    /// capacity of the vector as a slice of `MaybeUninit<T>`.
3376    ///
3377    /// The returned spare capacity slice can be used to fill the vector with data
3378    /// (e.g. by reading from a file) before marking the data as initialized using
3379    /// the [`set_len`] method.
3380    ///
3381    /// [`set_len`]: Vec::set_len
3382    ///
3383    /// Note that this is a low-level API, which should be used with care for
3384    /// optimization purposes. If you need to append data to a `Vec`
3385    /// you can use [`push`], [`extend`], [`extend_from_slice`],
3386    /// [`extend_from_within`], [`insert`], [`append`], [`resize`] or
3387    /// [`resize_with`], depending on your exact needs.
3388    ///
3389    /// [`push`]: Vec::push
3390    /// [`extend`]: Vec::extend
3391    /// [`extend_from_slice`]: Vec::extend_from_slice
3392    /// [`extend_from_within`]: Vec::extend_from_within
3393    /// [`insert`]: Vec::insert
3394    /// [`append`]: Vec::append
3395    /// [`resize`]: Vec::resize
3396    /// [`resize_with`]: Vec::resize_with
3397    ///
3398    /// # Examples
3399    ///
3400    /// ```
3401    /// #![feature(vec_split_at_spare)]
3402    ///
3403    /// let mut v = vec![1, 1, 2];
3404    ///
3405    /// // Reserve additional space big enough for 10 elements.
3406    /// v.reserve(10);
3407    ///
3408    /// let (init, uninit) = v.split_at_spare_mut();
3409    /// let sum = init.iter().copied().sum::<u32>();
3410    ///
3411    /// // Fill in the next 4 elements.
3412    /// uninit[0].write(sum);
3413    /// uninit[1].write(sum * 2);
3414    /// uninit[2].write(sum * 3);
3415    /// uninit[3].write(sum * 4);
3416    ///
3417    /// // Mark the 4 elements of the vector as being initialized.
3418    /// unsafe {
3419    ///     let len = v.len();
3420    ///     v.set_len(len + 4);
3421    /// }
3422    ///
3423    /// assert_eq!(&v, &[1, 1, 2, 4, 8, 12, 16]);
3424    /// ```
3425    #[unstable(feature = "vec_split_at_spare", issue = "81944")]
3426    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
3427    #[inline]
3428    pub const fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) {
3429        // SAFETY:
3430        // - len is ignored and so never changed
3431        let (init, spare, _) = unsafe { self.split_at_spare_mut_with_len() };
3432        (init, spare)
3433    }
3434
3435    /// Safety: changing returned .2 (&mut usize) is considered the same as calling `.set_len(_)`.
3436    ///
3437    /// This method provides unique access to all vec parts at once in `extend_from_within`.
3438    const unsafe fn split_at_spare_mut_with_len(
3439        &mut self,
3440    ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) {
3441        let ptr = self.as_mut_ptr();
3442        // SAFETY:
3443        // - `ptr` is guaranteed to be valid for `self.len` elements
3444        // - but the allocation extends out to `self.buf.capacity()` elements, possibly
3445        // uninitialized
3446        let spare_ptr = unsafe { ptr.add(self.len) };
3447        let spare_ptr = spare_ptr.cast_uninit();
3448        let spare_len = self.buf.capacity() - self.len;
3449
3450        // SAFETY:
3451        // - `ptr` is guaranteed to be valid for `self.len` elements
3452        // - `spare_ptr` is pointing one element past the buffer, so it doesn't overlap with `initialized`
3453        unsafe {
3454            let initialized = slice::from_raw_parts_mut(ptr, self.len);
3455            let spare = slice::from_raw_parts_mut(spare_ptr, spare_len);
3456
3457            (initialized, spare, &mut self.len)
3458        }
3459    }
3460
3461    /// Groups every `N` elements in the `Vec<T>` into chunks to produce a `Vec<[T; N]>`, dropping
3462    /// elements in the remainder. `N` must be greater than zero.
3463    ///
3464    /// If the capacity is not a multiple of the chunk size, the buffer will shrink down to the
3465    /// nearest multiple with a reallocation or deallocation.
3466    ///
3467    /// This function can be used to reverse [`Vec::into_flattened`].
3468    ///
3469    /// # Examples
3470    ///
3471    /// ```
3472    /// #![feature(vec_into_chunks)]
3473    ///
3474    /// let vec = vec![0, 1, 2, 3, 4, 5, 6, 7];
3475    /// assert_eq!(vec.into_chunks::<3>(), [[0, 1, 2], [3, 4, 5]]);
3476    ///
3477    /// let vec = vec![0, 1, 2, 3];
3478    /// let chunks: Vec<[u8; 10]> = vec.into_chunks();
3479    /// assert!(chunks.is_empty());
3480    ///
3481    /// let flat = vec![0; 8 * 8 * 8];
3482    /// let reshaped: Vec<[[[u8; 8]; 8]; 8]> = flat.into_chunks().into_chunks().into_chunks();
3483    /// assert_eq!(reshaped.len(), 1);
3484    /// ```
3485    #[cfg(not(no_global_oom_handling))]
3486    #[unstable(feature = "vec_into_chunks", issue = "142137")]
3487    pub fn into_chunks<const N: usize>(mut self) -> Vec<[T; N], A> {
3488        const {
3489            assert!(N != 0, "chunk size must be greater than zero");
3490        }
3491
3492        let (len, cap) = (self.len(), self.capacity());
3493
3494        let len_remainder = len % N;
3495        if len_remainder != 0 {
3496            self.truncate(len - len_remainder);
3497        }
3498
3499        let cap_remainder = cap % N;
3500        if !T::IS_ZST && cap_remainder != 0 {
3501            self.buf.shrink_to_fit(cap - cap_remainder);
3502        }
3503
3504        let (ptr, _, _, alloc) = self.into_raw_parts_with_allocator();
3505
3506        // SAFETY:
3507        // - `ptr` and `alloc` were just returned from `self.into_raw_parts_with_allocator()`
3508        // - `[T; N]` has the same alignment as `T`
3509        // - `size_of::<[T; N]>() * cap / N == size_of::<T>() * cap`
3510        // - `len / N <= cap / N` because `len <= cap`
3511        // - the allocated memory consists of `len / N` valid values of type `[T; N]`
3512        // - `cap / N` fits the size of the allocated memory after shrinking
3513        unsafe { Vec::from_raw_parts_in(ptr.cast(), len / N, cap / N, alloc) }
3514    }
3515
3516    /// This clears out this `Vec` and recycles the allocation into a new `Vec`.
3517    /// The item type of the resulting `Vec` needs to have the same size and
3518    /// alignment as the item type of the original `Vec`.
3519    ///
3520    /// # Examples
3521    ///
3522    ///  ```
3523    /// #![feature(vec_recycle, transmutability)]
3524    /// let a: Vec<u8> = vec![0; 100];
3525    /// let capacity = a.capacity();
3526    /// let addr = a.as_ptr().addr();
3527    /// let b: Vec<i8> = a.recycle();
3528    /// assert_eq!(b.len(), 0);
3529    /// assert_eq!(b.capacity(), capacity);
3530    /// assert_eq!(b.as_ptr().addr(), addr);
3531    /// ```
3532    ///
3533    /// The `Recyclable` bound prevents this method from being called when `T` and `U` have different sizes; e.g.:
3534    ///
3535    ///  ```compile_fail,E0277
3536    /// #![feature(vec_recycle, transmutability)]
3537    /// let vec: Vec<[u8; 2]> = Vec::new();
3538    /// let _: Vec<[u8; 1]> = vec.recycle();
3539    /// ```
3540    /// ...or different alignments:
3541    ///
3542    ///  ```compile_fail,E0277
3543    /// #![feature(vec_recycle, transmutability)]
3544    /// let vec: Vec<[u16; 0]> = Vec::new();
3545    /// let _: Vec<[u8; 0]> = vec.recycle();
3546    /// ```
3547    ///
3548    /// However, due to temporary implementation limitations of `Recyclable`,
3549    /// this method is not yet callable when `T` or `U` are slices, trait objects,
3550    /// or other exotic types; e.g.:
3551    ///
3552    /// ```compile_fail,E0277
3553    /// #![feature(vec_recycle, transmutability)]
3554    /// # let inputs = ["a b c", "d e f"];
3555    /// # fn process(_: &[&str]) {}
3556    /// let mut storage: Vec<&[&str]> = Vec::new();
3557    ///
3558    /// for input in inputs {
3559    ///     let mut buffer: Vec<&str> = storage.recycle();
3560    ///     buffer.extend(input.split(" "));
3561    ///     process(&buffer);
3562    ///     storage = buffer.recycle();
3563    /// }
3564    /// ```
3565    #[unstable(feature = "vec_recycle", issue = "148227")]
3566    #[expect(private_bounds)]
3567    pub fn recycle<U>(mut self) -> Vec<U, A>
3568    where
3569        U: Recyclable<T>,
3570    {
3571        self.clear();
3572        const {
3573            // FIXME(const-hack, 146097): compare `Layout`s
3574            assert!(size_of::<T>() == size_of::<U>());
3575            assert!(align_of::<T>() == align_of::<U>());
3576        };
3577        let (ptr, length, capacity, alloc) = self.into_parts_with_allocator();
3578        debug_assert_eq!(length, 0);
3579        // SAFETY:
3580        // - `ptr` and `alloc` were just returned from `self.into_raw_parts_with_allocator()`
3581        // - `T` & `U` have the same layout, so `capacity` does not need to be changed and we can safely use `alloc.dealloc` later
3582        // - the original vector was cleared, so there is no problem with "transmuting" the stored values
3583        unsafe { Vec::from_parts_in(ptr.cast::<U>(), length, capacity, alloc) }
3584    }
3585}
3586
3587/// Denotes that an allocation of `From` can be recycled into an allocation of `Self`.
3588///
3589/// # Safety
3590///
3591/// `Self` is `Recyclable<From>` if `Layout::new::<Self>() == Layout::new::<From>()`.
3592unsafe trait Recyclable<From: Sized>: Sized {}
3593
3594#[unstable_feature_bound(transmutability)]
3595// SAFETY: enforced by `TransmuteFrom`
3596unsafe impl<From, To> Recyclable<From> for To
3597where
3598    for<'a> &'a MaybeUninit<To>: TransmuteFrom<&'a MaybeUninit<From>, { Assume::SAFETY }>,
3599    for<'a> &'a MaybeUninit<From>: TransmuteFrom<&'a MaybeUninit<To>, { Assume::SAFETY }>,
3600{
3601}
3602
3603impl<T: Clone, A: Allocator> Vec<T, A> {
3604    /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
3605    ///
3606    /// If `new_len` is greater than `len`, the `Vec` is extended by the
3607    /// difference, with each additional slot filled with `value`.
3608    /// If `new_len` is less than or equal to `len`, the `Vec` is simply
3609    /// truncated.
3610    ///
3611    /// This method requires `T` to implement [`Clone`],
3612    /// in order to be able to clone the passed value.
3613    /// If you need more flexibility (or want to rely on [`Default`] instead of
3614    /// [`Clone`]), use [`Vec::resize_with`].
3615    /// If you only need to resize to a smaller size, use [`Vec::truncate`].
3616    ///
3617    /// # Panics
3618    ///
3619    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
3620    ///
3621    /// # Examples
3622    ///
3623    /// ```
3624    /// let mut vec = vec!["hello"];
3625    /// vec.resize(3, "world");
3626    /// assert_eq!(vec, ["hello", "world", "world"]);
3627    ///
3628    /// let mut vec = vec!['a', 'b', 'c', 'd'];
3629    /// vec.resize(2, '_');
3630    /// assert_eq!(vec, ['a', 'b']);
3631    /// ```
3632    #[cfg(not(no_global_oom_handling))]
3633    #[stable(feature = "vec_resize", since = "1.5.0")]
3634    pub fn resize(&mut self, new_len: usize, value: T) {
3635        let len = self.len();
3636
3637        if new_len > len {
3638            self.extend_with(new_len - len, value)
3639        } else {
3640            self.truncate(new_len);
3641        }
3642    }
3643
3644    /// Clones and appends all elements in a slice to the `Vec`.
3645    ///
3646    /// Iterates over the slice `other`, clones each element, and then appends
3647    /// it to this `Vec`. The `other` slice is traversed in-order.
3648    ///
3649    /// Note that this function is the same as [`extend`],
3650    /// except that it also works with slice elements that are Clone but not Copy.
3651    /// If Rust gets specialization this function may be deprecated.
3652    ///
3653    /// # Panics
3654    ///
3655    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
3656    ///
3657    /// # Examples
3658    ///
3659    /// ```
3660    /// let mut vec = vec![1];
3661    /// vec.extend_from_slice(&[2, 3, 4]);
3662    /// assert_eq!(vec, [1, 2, 3, 4]);
3663    /// ```
3664    ///
3665    /// [`extend`]: Vec::extend
3666    #[cfg(not(no_global_oom_handling))]
3667    #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
3668    pub fn extend_from_slice(&mut self, other: &[T]) {
3669        self.spec_extend(other.iter())
3670    }
3671
3672    /// Given a range `src`, clones a slice of elements in that range and appends it to the end.
3673    ///
3674    /// `src` must be a range that can form a valid subslice of the `Vec`.
3675    ///
3676    /// # Panics
3677    ///
3678    /// Panics if starting index is greater than the end index, if the index is
3679    /// greater than the length of the vector, or if the new capacity exceeds
3680    /// `isize::MAX` _bytes_.
3681    ///
3682    /// # Examples
3683    ///
3684    /// ```
3685    /// let mut characters = vec!['a', 'b', 'c', 'd', 'e'];
3686    /// characters.extend_from_within(2..);
3687    /// assert_eq!(characters, ['a', 'b', 'c', 'd', 'e', 'c', 'd', 'e']);
3688    ///
3689    /// let mut numbers = vec![0, 1, 2, 3, 4];
3690    /// numbers.extend_from_within(..2);
3691    /// assert_eq!(numbers, [0, 1, 2, 3, 4, 0, 1]);
3692    ///
3693    /// let mut strings = vec![String::from("hello"), String::from("world"), String::from("!")];
3694    /// strings.extend_from_within(1..=2);
3695    /// assert_eq!(strings, ["hello", "world", "!", "world", "!"]);
3696    /// ```
3697    #[cfg(not(no_global_oom_handling))]
3698    #[stable(feature = "vec_extend_from_within", since = "1.53.0")]
3699    pub fn extend_from_within<R>(&mut self, src: R)
3700    where
3701        R: RangeBounds<usize>,
3702    {
3703        let range = slice::range(src, ..self.len());
3704        self.reserve(range.len());
3705
3706        // SAFETY:
3707        // - `slice::range` guarantees that the given range is valid for indexing self
3708        unsafe {
3709            self.spec_extend_from_within(range);
3710        }
3711    }
3712}
3713
3714impl<A: Allocator> Vec<u8, A> {
3715    #[cfg_attr(
3716        not(no_global_oom_handling),
3717        expect(
3718            dead_code,
3719            reason = "currently only used in IO module when global OOM handling is disabled"
3720        )
3721    )]
3722    pub(crate) fn try_extend_from_slice_of_bytes(
3723        &mut self,
3724        other: &[u8],
3725    ) -> Result<(), TryReserveError> {
3726        // ignore-tidy-undocumented-unsafe
3727        unsafe { self.try_append_elements(other) }
3728    }
3729}
3730
3731impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
3732    /// Takes a `Vec<[T; N]>` and flattens it into a `Vec<T>`.
3733    ///
3734    /// # Panics
3735    ///
3736    /// Panics if the length of the resulting vector would overflow a `usize`.
3737    ///
3738    /// This is only possible when flattening a vector of arrays of zero-sized
3739    /// types, and thus tends to be irrelevant in practice. If
3740    /// `size_of::<T>() > 0`, this will never panic.
3741    ///
3742    /// # Examples
3743    ///
3744    /// ```
3745    /// let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
3746    /// assert_eq!(vec.pop(), Some([7, 8, 9]));
3747    ///
3748    /// let mut flattened = vec.into_flattened();
3749    /// assert_eq!(flattened.pop(), Some(6));
3750    /// ```
3751    #[stable(feature = "slice_flatten", since = "1.80.0")]
3752    pub fn into_flattened(self) -> Vec<T, A> {
3753        let (ptr, len, cap, alloc) = self.into_raw_parts_with_allocator();
3754        let (new_len, new_cap) = if T::IS_ZST {
3755            (
3756                len.checked_mul(N).expect("the product of vec len and N shouldn't overflow"),
3757                usize::MAX,
3758            )
3759        } else {
3760            // SAFETY:
3761            // - `cap * N` cannot overflow because the allocation is already in
3762            // the address space.
3763            // - Each `[T; N]` has `N` valid elements, so there are `len * N`
3764            // valid elements in the allocation.
3765            unsafe { (len.unchecked_mul(N), cap.unchecked_mul(N)) }
3766        };
3767        // SAFETY:
3768        // - `ptr` was allocated by `self`
3769        // - `ptr` is well-aligned because `[T; N]` has the same alignment as `T`.
3770        // - `new_cap` refers to the same sized allocation as `cap` because
3771        // `new_cap * size_of::<T>()` == `cap * size_of::<[T; N]>()`
3772        // - `len` <= `cap`, so `len * N` <= `cap * N`.
3773        unsafe { Vec::<T, A>::from_raw_parts_in(ptr.cast(), new_len, new_cap, alloc) }
3774    }
3775}
3776
3777impl<T: Clone, A: Allocator> Vec<T, A> {
3778    #[cfg(not(no_global_oom_handling))]
3779    /// Extend the vector by `n` clones of value.
3780    fn extend_with(&mut self, n: usize, value: T) {
3781        self.spec_extend_with(n, value);
3782    }
3783}
3784
3785impl<T: PartialEq, A: Allocator> Vec<T, A> {
3786    /// Removes consecutive repeated elements in the vector according to the
3787    /// [`PartialEq`] trait implementation.
3788    ///
3789    /// If the vector is sorted, this removes all duplicates.
3790    ///
3791    /// # Examples
3792    ///
3793    /// ```
3794    /// let mut vec = vec![1, 2, 2, 3, 2];
3795    ///
3796    /// vec.dedup();
3797    ///
3798    /// assert_eq!(vec, [1, 2, 3, 2]);
3799    /// ```
3800    #[stable(feature = "rust1", since = "1.0.0")]
3801    #[inline]
3802    pub fn dedup(&mut self) {
3803        // Vectorize the process of finding first duplicate if possible
3804        if let Some(chunk_size) = dedup_simd_chunk_size::<T>() {
3805            // Unlike dedup_by, we don't guarantee the order
3806            // and time in which we call `PartialEq::eq`.
3807            let Some(first_duplicate) = find_first_duplicate(self.as_slice(), chunk_size) else {
3808                return;
3809            };
3810
3811            // SAFETY: `1 <= first_duplicate < self.len()`
3812            unsafe {
3813                self.dedup_tail(|a, b| a == b, first_duplicate);
3814            }
3815        } else {
3816            self.dedup_by(|a, b| a == b);
3817        }
3818    }
3819}
3820
3821const fn dedup_simd_chunk_size<T>() -> Option<usize> {
3822    // The minimal SIMD width on supported platforms
3823    #[allow(unused)]
3824    const SIMD_WIDTH: usize = 16;
3825    let size = size_of::<T>();
3826
3827    // We only have SIMD implementations for these element sizes.
3828    if !matches!(size, 1 | 2 | 4 | 8) {
3829        return None;
3830    }
3831
3832    let simd_width: Option<usize> = cfg_select! {
3833        all(target_arch = "arm", target_feature = "neon") => {
3834            // Packed 64-bit integer lane equality is unavailable on arm neon
3835            if size == 8 { None } else { Some(SIMD_WIDTH) }
3836        }
3837
3838        all(target_arch = "aarch64", target_feature = "neon") => {
3839            Some(SIMD_WIDTH)
3840        }
3841
3842        all(
3843            any(target_arch = "x86", target_arch = "x86_64"),
3844            target_feature = "sse4.1"
3845        ) => Some(SIMD_WIDTH),
3846
3847        all(
3848            any(target_arch = "x86", target_arch = "x86_64"),
3849            target_feature = "sse2"
3850        ) => {
3851            // Packed 64-bit integer lane equality is only available on sse4.1
3852            if size == 8 { None } else { Some(SIMD_WIDTH) }
3853        }
3854
3855        all(
3856            any(target_arch = "riscv32", target_arch = "riscv64"),
3857            target_feature = "v"
3858        ) => Some(SIMD_WIDTH),
3859
3860        all(
3861            any(target_arch = "loongarch32", target_arch = "loongarch64"),
3862            target_feature = "lsx"
3863        ) => Some(SIMD_WIDTH),
3864
3865        _ => None,
3866    };
3867
3868    if let Some(simd_width) = simd_width { Some(simd_width * 2 / size) } else { None }
3869}
3870
3871fn find_first_duplicate<T: PartialEq>(v: &[T], chunk_size: usize) -> Option<usize> {
3872    let len = v.len();
3873    if len <= 1 {
3874        return None;
3875    }
3876
3877    let mut i = 1;
3878
3879    // The scalar fallback path if the length is not long enough
3880    if len < chunk_size + 1 {
3881        while i < len {
3882            // It keeps the same comparison order as `dedup_tail`
3883            //
3884            // SAFETY: i always in range [1..len)
3885            if unsafe { v.get_unchecked(i) == v.get_unchecked(i - 1) } {
3886                return Some(i);
3887            }
3888            i += 1;
3889        }
3890        return None;
3891    }
3892
3893    /// # Safety
3894    /// - `start > 0` and `start + chunk_size <= v.len()`
3895    /// - `0 < chunk_size <= 32`
3896    #[inline(always)]
3897    unsafe fn find_duplicate<T: PartialEq>(
3898        v: &[T],
3899        start: usize,
3900        chunk_size: usize,
3901    ) -> Option<usize> {
3902        let mut mask: u32 = 0;
3903        debug_assert!(
3904            u32::BITS as usize >= chunk_size,
3905            "the bit width of mask must be greater than or equal to chunk_size"
3906        );
3907        for j in 0..chunk_size {
3908            // SAFETY: start + j always in range [1..v.len())
3909            let eq = unsafe { v.get_unchecked(start + j) == v.get_unchecked(start + j - 1) };
3910            mask |= (eq as u32) << j;
3911        }
3912        if mask != 0 {
3913            return Some(start + mask.trailing_zeros() as usize);
3914        }
3915        None
3916    }
3917
3918    // This loop performs chunk_size comparisons in parallel without early exit,
3919    // which is what allows for SIMD optimization.
3920    while i + chunk_size <= len {
3921        // SAFETY: `i >= 1` and `i + chunk_size <= len`
3922        if let Some(duplicate) = unsafe { find_duplicate(v, i, chunk_size) } {
3923            return Some(duplicate);
3924        }
3925        i += chunk_size;
3926    }
3927
3928    // This may check the same elements multiple times.
3929    // However we don't guarantee `PartialEq::eq` is only called once per pair.
3930    if i < len {
3931        let start = len - chunk_size;
3932        // SAFETY: `len - chunk_size >= 1` and `start + chunk_size <= len`
3933        if let Some(duplicate) = unsafe { find_duplicate(v, start, chunk_size) } {
3934            return Some(duplicate);
3935        }
3936    }
3937
3938    None
3939}
3940
3941////////////////////////////////////////////////////////////////////////////////
3942// Internal methods and functions
3943////////////////////////////////////////////////////////////////////////////////
3944
3945#[doc(hidden)]
3946#[cfg(not(no_global_oom_handling))]
3947#[stable(feature = "rust1", since = "1.0.0")]
3948#[rustc_diagnostic_item = "vec_from_elem"]
3949pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
3950    <T as SpecFromElem>::from_elem(elem, n, Global)
3951}
3952
3953#[doc(hidden)]
3954#[cfg(not(no_global_oom_handling))]
3955#[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")]
3956pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> {
3957    <T as SpecFromElem>::from_elem(elem, n, alloc)
3958}
3959
3960#[cfg(not(no_global_oom_handling))]
3961trait ExtendFromWithinSpec {
3962    /// # Safety
3963    ///
3964    /// - `src` needs to be valid index
3965    /// - `self.capacity() - self.len()` must be `>= src.len()`
3966    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
3967}
3968
3969#[cfg(not(no_global_oom_handling))]
3970impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
3971    default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
3972        // SAFETY:
3973        // - len is increased only after initializing elements
3974        let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() };
3975
3976        // SAFETY:
3977        // - caller guarantees that src is a valid index
3978        let to_clone = unsafe { this.get_unchecked(src) };
3979
3980        iter::zip(to_clone, spare)
3981            .map(|(src, dst)| dst.write(src.clone()))
3982            // Note:
3983            // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len
3984            // - len is increased after each element to prevent leaks (see issue #82533)
3985            .for_each(|_| *len += 1);
3986    }
3987}
3988
3989#[cfg(not(no_global_oom_handling))]
3990impl<T: TrivialClone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
3991    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
3992        let count = src.len();
3993        {
3994            let (init, spare) = self.split_at_spare_mut();
3995
3996            // SAFETY:
3997            // - caller guarantees that `src` is a valid index
3998            let source = unsafe { init.get_unchecked(src) };
3999
4000            // SAFETY:
4001            // - Both pointers are created from unique slice references (`&mut [_]`)
4002            //   so they are valid and do not overlap.
4003            // - Elements implement `TrivialClone` so this is equivalent to calling
4004            //   `clone` on every one of them.
4005            // - `count` is equal to the len of `source`, so source is valid for
4006            //   `count` reads
4007            // - `.reserve(count)` guarantees that `spare.len() >= count` so spare
4008            //   is valid for `count` writes
4009            unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) };
4010        }
4011
4012        // SAFETY:
4013        // - The elements were just initialized by `copy_nonoverlapping`
4014        self.len += count;
4015    }
4016}
4017
4018////////////////////////////////////////////////////////////////////////////////
4019// Common trait implementations for Vec
4020////////////////////////////////////////////////////////////////////////////////
4021
4022#[stable(feature = "rust1", since = "1.0.0")]
4023#[rustc_const_unstable(feature = "const_convert", issue = "143773")]
4024const impl<T, A: Allocator> ops::Deref for Vec<T, A> {
4025    type Target = [T];
4026
4027    #[inline]
4028    fn deref(&self) -> &[T] {
4029        self.as_slice()
4030    }
4031}
4032
4033#[stable(feature = "rust1", since = "1.0.0")]
4034#[rustc_const_unstable(feature = "const_convert", issue = "143773")]
4035const impl<T, A: Allocator> ops::DerefMut for Vec<T, A> {
4036    #[inline]
4037    fn deref_mut(&mut self) -> &mut [T] {
4038        self.as_mut_slice()
4039    }
4040}
4041
4042#[unstable(feature = "deref_pure_trait", issue = "87121")]
4043unsafe impl<T, A: Allocator> ops::DerefPure for Vec<T, A> {}
4044
4045#[cfg(not(no_global_oom_handling))]
4046#[stable(feature = "rust1", since = "1.0.0")]
4047impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
4048    /// Creates a new `Vec` by deep-copying the contents of an existing `Vec`.
4049    ///
4050    /// This method will allocate a new `Vec` and `clone` all of `self`'s contents
4051    /// into it. The capacity of the duplicate `Vec` is not forced to match the
4052    /// capacity of the original.
4053    fn clone(&self) -> Self {
4054        let alloc = self.allocator().clone();
4055        <[T]>::to_vec_in(self, alloc)
4056    }
4057
4058    /// Overwrites the contents of `self` with a clone of the contents of `source`.
4059    ///
4060    /// This method is preferred over simply assigning `source.clone()` to `self`,
4061    /// as it avoids reallocation if possible. Additionally, if the element type
4062    /// `T` overrides `clone_from()`, this will reuse the resources of `self`'s
4063    /// elements as well.
4064    ///
4065    /// # Examples
4066    ///
4067    /// ```
4068    /// let x = vec![5, 6, 7];
4069    /// let mut y = vec![8, 9, 10];
4070    /// let yp: *const i32 = y.as_ptr();
4071    ///
4072    /// y.clone_from(&x);
4073    ///
4074    /// // The value is the same
4075    /// assert_eq!(x, y);
4076    ///
4077    /// // And no reallocation occurred
4078    /// assert_eq!(yp, y.as_ptr());
4079    /// ```
4080    fn clone_from(&mut self, source: &Self) {
4081        crate::slice::SpecCloneIntoVec::clone_into(source.as_slice(), self);
4082    }
4083}
4084
4085/// The hash of a vector is the same as that of the corresponding slice,
4086/// as required by the `core::borrow::Borrow` implementation.
4087///
4088/// ```
4089/// use std::hash::BuildHasher;
4090///
4091/// let b = std::hash::RandomState::new();
4092/// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09];
4093/// let s: &[u8] = &[0xa8, 0x3c, 0x09];
4094/// assert_eq!(b.hash_one(v), b.hash_one(s));
4095/// ```
4096#[stable(feature = "rust1", since = "1.0.0")]
4097impl<T: Hash, A: Allocator> Hash for Vec<T, A> {
4098    #[inline]
4099    fn hash<H: Hasher>(&self, state: &mut H) {
4100        Hash::hash(&**self, state)
4101    }
4102}
4103
4104#[stable(feature = "rust1", since = "1.0.0")]
4105#[rustc_const_unstable(feature = "const_index", issue = "143775")]
4106const impl<T, I: [const] SliceIndex<[T]>, A: Allocator> Index<I> for Vec<T, A> {
4107    type Output = I::Output;
4108
4109    #[inline]
4110    fn index(&self, index: I) -> &Self::Output {
4111        Index::index(&**self, index)
4112    }
4113}
4114
4115#[stable(feature = "rust1", since = "1.0.0")]
4116#[rustc_const_unstable(feature = "const_index", issue = "143775")]
4117const impl<T, I: [const] SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> {
4118    #[inline]
4119    fn index_mut(&mut self, index: I) -> &mut Self::Output {
4120        IndexMut::index_mut(&mut **self, index)
4121    }
4122}
4123
4124/// Collects an iterator into a Vec, commonly called via [`Iterator::collect()`]
4125///
4126/// # Allocation behavior
4127///
4128/// In general `Vec` does not guarantee any particular growth or allocation strategy.
4129/// That also applies to this trait impl.
4130///
4131/// **Note:** This section covers implementation details and is therefore exempt from
4132/// stability guarantees.
4133///
4134/// Vec may use any or none of the following strategies,
4135/// depending on the supplied iterator:
4136///
4137/// * preallocate based on [`Iterator::size_hint()`]
4138///   * and panic if the number of items is outside the provided lower/upper bounds
4139/// * use an amortized growth strategy similar to `pushing` one item at a time
4140/// * perform the iteration in-place on the original allocation backing the iterator
4141///
4142/// The last case warrants some attention. It is an optimization that in many cases reduces peak memory
4143/// consumption and improves cache locality. But when big, short-lived allocations are created,
4144/// only a small fraction of their items get collected, no further use is made of the spare capacity
4145/// and the resulting `Vec` is moved into a longer-lived structure, then this can lead to the large
4146/// allocations having their lifetimes unnecessarily extended which can result in increased memory
4147/// footprint.
4148///
4149/// In cases where this is an issue, the excess capacity can be discarded with [`Vec::shrink_to()`],
4150/// [`Vec::shrink_to_fit()`] or by collecting into [`Box<[T]>`][owned slice] instead, which additionally reduces
4151/// the size of the long-lived struct.
4152///
4153/// [owned slice]: Box
4154///
4155/// ```rust
4156/// # use std::sync::Mutex;
4157/// static LONG_LIVED: Mutex<Vec<Vec<u16>>> = Mutex::new(Vec::new());
4158///
4159/// for i in 0..10 {
4160///     let big_temporary: Vec<u16> = (0..1024).collect();
4161///     // discard most items
4162///     let mut result: Vec<_> = big_temporary.into_iter().filter(|i| i % 100 == 0).collect();
4163///     // without this a lot of unused capacity might be moved into the global
4164///     result.shrink_to_fit();
4165///     LONG_LIVED.lock().unwrap().push(result);
4166/// }
4167/// ```
4168#[cfg(not(no_global_oom_handling))]
4169#[stable(feature = "rust1", since = "1.0.0")]
4170impl<T> FromIterator<T> for Vec<T> {
4171    #[inline]
4172    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
4173        <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter())
4174    }
4175}
4176
4177#[stable(feature = "rust1", since = "1.0.0")]
4178impl<T, A: Allocator> IntoIterator for Vec<T, A> {
4179    type Item = T;
4180    type IntoIter = IntoIter<T, A>;
4181
4182    /// Creates a consuming iterator, that is, one that moves each value out of
4183    /// the vector (from start to end). The vector cannot be used after calling
4184    /// this.
4185    ///
4186    /// # Examples
4187    ///
4188    /// ```
4189    /// let v = vec!["a".to_string(), "b".to_string()];
4190    /// let mut v_iter = v.into_iter();
4191    ///
4192    /// let first_element: Option<String> = v_iter.next();
4193    ///
4194    /// assert_eq!(first_element, Some("a".to_string()));
4195    /// assert_eq!(v_iter.next(), Some("b".to_string()));
4196    /// assert_eq!(v_iter.next(), None);
4197    /// ```
4198    #[inline]
4199    fn into_iter(self) -> Self::IntoIter {
4200        let me = ManuallyDrop::new(self);
4201        // ignore-tidy-undocumented-unsafe
4202        unsafe {
4203            let alloc = ManuallyDrop::new(ptr::read(me.allocator()));
4204            let buf = me.buf.non_null();
4205            let begin = buf.as_ptr();
4206            let end = if T::IS_ZST {
4207                begin.wrapping_byte_add(me.len())
4208            } else {
4209                begin.add(me.len()) as *const T
4210            };
4211            let cap = me.buf.capacity();
4212            IntoIter { buf, phantom: PhantomData, cap, alloc, ptr: buf, end }
4213        }
4214    }
4215}
4216
4217#[stable(feature = "rust1", since = "1.0.0")]
4218impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> {
4219    type Item = &'a T;
4220    type IntoIter = slice::Iter<'a, T>;
4221
4222    fn into_iter(self) -> Self::IntoIter {
4223        self.iter()
4224    }
4225}
4226
4227#[stable(feature = "rust1", since = "1.0.0")]
4228impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> {
4229    type Item = &'a mut T;
4230    type IntoIter = slice::IterMut<'a, T>;
4231
4232    fn into_iter(self) -> Self::IntoIter {
4233        self.iter_mut()
4234    }
4235}
4236
4237#[cfg(not(no_global_oom_handling))]
4238#[stable(feature = "rust1", since = "1.0.0")]
4239impl<T, A: Allocator> Extend<T> for Vec<T, A> {
4240    #[inline]
4241    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
4242        <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
4243    }
4244
4245    #[inline]
4246    fn extend_one(&mut self, item: T) {
4247        self.push(item);
4248    }
4249
4250    #[inline]
4251    fn extend_reserve(&mut self, additional: usize) {
4252        self.reserve(additional);
4253    }
4254
4255    #[inline]
4256    unsafe fn extend_one_unchecked(&mut self, item: T) {
4257        // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
4258        unsafe {
4259            let len = self.len();
4260            ptr::write(self.as_mut_ptr().add(len), item);
4261            self.set_len(len + 1);
4262        }
4263    }
4264}
4265
4266impl<T, A: Allocator> Vec<T, A> {
4267    // leaf method to which various SpecFrom/SpecExtend implementations delegate when
4268    // they have no further optimizations to apply
4269    #[cfg(not(no_global_oom_handling))]
4270    fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
4271        // This is the case for a general iterator.
4272        //
4273        // This function should be the moral equivalent of:
4274        //
4275        //      for item in iterator {
4276        //          self.push(item);
4277        //      }
4278        while let Some(element) = iterator.next() {
4279            let len = self.len();
4280            if len == self.capacity() {
4281                let (lower, _) = iterator.size_hint();
4282                self.reserve(lower.saturating_add(1));
4283            }
4284            // ignore-tidy-undocumented-unsafe
4285            unsafe {
4286                ptr::write(self.as_mut_ptr().add(len), element);
4287                // Since next() executes user code which can panic we have to bump the length
4288                // after each step.
4289                // NB can't overflow since we would have had to alloc the address space
4290                self.set_len(len + 1);
4291            }
4292        }
4293    }
4294
4295    // specific extend for `TrustedLen` iterators, called both by the specializations
4296    // and internal places where resolving specialization makes compilation slower
4297    #[cfg(not(no_global_oom_handling))]
4298    fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
4299        let (low, high) = iterator.size_hint();
4300        if let Some(additional) = high {
4301            debug_assert_eq!(
4302                low,
4303                additional,
4304                "TrustedLen iterator's size hint is not exact: {:?}",
4305                (low, high)
4306            );
4307            self.reserve(additional);
4308            let ptr = self.as_mut_ptr();
4309            let mut local_len = SetLenOnDrop::new(&mut self.len);
4310            // ignore-tidy-undocumented-unsafe
4311            unsafe {
4312                iterator.for_each(move |element| {
4313                    ptr::write(ptr.add(local_len.current_len()), element);
4314                    // Since the loop executes user code which can panic we have to update
4315                    // the length every step to correctly drop what we've written.
4316                    // NB can't overflow since we would have had to alloc the address space
4317                    local_len.increment_len(1);
4318                });
4319            }
4320        } else {
4321            // Per TrustedLen contract a `None` upper bound means that the iterator length
4322            // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway.
4323            // Since the other branch already panics eagerly (via `reserve()`) we do the same here.
4324            // This avoids additional codegen for a fallback code path which would eventually
4325            // panic anyway.
4326            panic!("capacity overflow");
4327        }
4328    }
4329
4330    /// Creates a splicing iterator that replaces the specified range in the vector
4331    /// with the given `replace_with` iterator and yields the removed items.
4332    /// `replace_with` does not need to be the same length as `range`.
4333    ///
4334    /// `range` is removed even if the `Splice` iterator is not consumed before it is dropped.
4335    ///
4336    /// It is unspecified how many elements are removed from the vector
4337    /// if the `Splice` value is leaked.
4338    ///
4339    /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
4340    ///
4341    /// This is optimal if:
4342    ///
4343    /// * The tail (elements in the vector after `range`) is empty,
4344    /// * or `replace_with` yields fewer or equal elements than `range`'s length
4345    /// * or the lower bound of its `size_hint()` is exact.
4346    ///
4347    /// Otherwise, a temporary vector is allocated and the tail is moved twice.
4348    ///
4349    /// # Panics
4350    ///
4351    /// Panics if the range has `start_bound > end_bound`, or, if the range is
4352    /// bounded on either end and past the length of the vector.
4353    ///
4354    /// # Examples
4355    ///
4356    /// ```
4357    /// let mut v = vec![1, 2, 3, 4];
4358    /// let new = [7, 8, 9];
4359    /// let u: Vec<_> = v.splice(1..3, new).collect();
4360    /// assert_eq!(v, [1, 7, 8, 9, 4]);
4361    /// assert_eq!(u, [2, 3]);
4362    /// ```
4363    ///
4364    /// Using `splice` to insert new items into a vector efficiently at a specific position
4365    /// indicated by an empty range:
4366    ///
4367    /// ```
4368    /// let mut v = vec![1, 5];
4369    /// let new = [2, 3, 4];
4370    /// v.splice(1..1, new);
4371    /// assert_eq!(v, [1, 2, 3, 4, 5]);
4372    /// ```
4373    #[cfg(not(no_global_oom_handling))]
4374    #[inline]
4375    #[stable(feature = "vec_splice", since = "1.21.0")]
4376    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
4377    where
4378        A: AllocatorNightly,
4379        R: RangeBounds<usize>,
4380        I: IntoIterator<Item = T>,
4381    {
4382        Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
4383    }
4384
4385    /// Creates an iterator which uses a closure to determine if an element in the range should be removed.
4386    ///
4387    /// If the closure returns `true`, the element is removed from the vector
4388    /// and yielded. If the closure returns `false`, or panics, the element
4389    /// remains in the vector and will not be yielded.
4390    ///
4391    /// Only elements that fall in the provided range are considered for extraction, but any elements
4392    /// after the range will still have to be moved if any element has been extracted.
4393    ///
4394    /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
4395    /// or the iteration short-circuits, then the remaining elements will be retained.
4396    /// Use `extract_if().for_each(drop)` if you do not need the returned iterator,
4397    /// or [`retain_mut`] with a negated predicate if you also do not need to restrict the range.
4398    ///
4399    /// [`retain_mut`]: Vec::retain_mut
4400    ///
4401    /// Using this method is equivalent to the following code:
4402    ///
4403    /// ```
4404    /// # let some_predicate = |x: &mut i32| { *x % 2 == 1 };
4405    /// # let mut vec = vec![0, 1, 2, 3, 4, 5, 6];
4406    /// # let mut vec2 = vec.clone();
4407    /// # let range = 1..5;
4408    /// let mut i = range.start;
4409    /// let end_items = vec.len() - range.end;
4410    /// # let mut extracted = vec![];
4411    ///
4412    /// while i < vec.len() - end_items {
4413    ///     if some_predicate(&mut vec[i]) {
4414    ///         let val = vec.remove(i);
4415    ///         // your code here
4416    /// #         extracted.push(val);
4417    ///     } else {
4418    ///         i += 1;
4419    ///     }
4420    /// }
4421    ///
4422    /// # let extracted2: Vec<_> = vec2.extract_if(range, some_predicate).collect();
4423    /// # assert_eq!(vec, vec2);
4424    /// # assert_eq!(extracted, extracted2);
4425    /// ```
4426    ///
4427    /// But `extract_if` is easier to use. `extract_if` is also more efficient,
4428    /// because it can backshift the elements of the array in bulk.
4429    ///
4430    /// The iterator also lets you mutate the value of each element in the
4431    /// closure, regardless of whether you choose to keep or remove it.
4432    ///
4433    /// # Panics
4434    ///
4435    /// If `range` is out of bounds.
4436    ///
4437    /// # Examples
4438    ///
4439    /// Splitting a vector into even and odd values, reusing the original vector:
4440    ///
4441    /// ```
4442    /// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];
4443    ///
4444    /// let evens = numbers.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
4445    /// let odds = numbers;
4446    ///
4447    /// assert_eq!(evens, vec![2, 4, 6, 8, 14]);
4448    /// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]);
4449    /// ```
4450    ///
4451    /// Using the range argument to only process a part of the vector:
4452    ///
4453    /// ```
4454    /// let mut items = vec![0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2];
4455    /// let ones = items.extract_if(7.., |x| *x == 1).collect::<Vec<_>>();
4456    /// assert_eq!(items, vec![0, 0, 0, 0, 0, 0, 0, 2, 2, 2]);
4457    /// assert_eq!(ones.len(), 3);
4458    /// ```
4459    #[stable(feature = "extract_if", since = "1.87.0")]
4460    pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, A>
4461    where
4462        A: AllocatorNightly,
4463        F: FnMut(&mut T) -> bool,
4464        R: RangeBounds<usize>,
4465    {
4466        ExtractIf::new(self, filter, range)
4467    }
4468}
4469
4470/// Extend implementation that copies elements out of references before pushing them onto the Vec.
4471///
4472/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
4473/// append the entire slice at once.
4474///
4475/// [`copy_from_slice`]: slice::copy_from_slice
4476#[cfg(not(no_global_oom_handling))]
4477#[stable(feature = "extend_ref", since = "1.2.0")]
4478impl<'a, T: Copy + 'a, A: Allocator> Extend<&'a T> for Vec<T, A> {
4479    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
4480        self.spec_extend(iter.into_iter())
4481    }
4482
4483    #[inline]
4484    fn extend_one(&mut self, &item: &'a T) {
4485        self.push(item);
4486    }
4487
4488    #[inline]
4489    fn extend_reserve(&mut self, additional: usize) {
4490        self.reserve(additional);
4491    }
4492
4493    #[inline]
4494    unsafe fn extend_one_unchecked(&mut self, &item: &'a T) {
4495        // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
4496        unsafe {
4497            let len = self.len();
4498            ptr::write(self.as_mut_ptr().add(len), item);
4499            self.set_len(len + 1);
4500        }
4501    }
4502}
4503
4504/// Implements comparison of vectors, [lexicographically](Ord#lexicographical-comparison).
4505#[stable(feature = "rust1", since = "1.0.0")]
4506impl<T, A1, A2> PartialOrd<Vec<T, A2>> for Vec<T, A1>
4507where
4508    T: PartialOrd,
4509    A1: Allocator,
4510    A2: Allocator,
4511{
4512    #[inline]
4513    fn partial_cmp(&self, other: &Vec<T, A2>) -> Option<Ordering> {
4514        PartialOrd::partial_cmp(&**self, &**other)
4515    }
4516}
4517
4518#[stable(feature = "rust1", since = "1.0.0")]
4519impl<T: Eq, A: Allocator> Eq for Vec<T, A> {}
4520
4521/// Implements ordering of vectors, [lexicographically](Ord#lexicographical-comparison).
4522#[stable(feature = "rust1", since = "1.0.0")]
4523impl<T: Ord, A: Allocator> Ord for Vec<T, A> {
4524    #[inline]
4525    fn cmp(&self, other: &Self) -> Ordering {
4526        Ord::cmp(&**self, &**other)
4527    }
4528}
4529
4530#[stable(feature = "rust1", since = "1.0.0")]
4531#[rustc_const_unstable(feature = "const_heap", issue = "79597")]
4532const unsafe impl<#[may_dangle] T: [const] Destruct, A: [const] Allocator + [const] Destruct> Drop
4533    for Vec<T, A>
4534{
4535    fn drop(&mut self) {
4536        // ignore-tidy-undocumented-unsafe
4537        unsafe {
4538            // use drop for [T]
4539            // use a raw slice to refer to the elements of the vector as weakest necessary type;
4540            // could avoid questions of validity in certain cases
4541            self.as_mut_ptr().cast_slice(self.len).drop_in_place()
4542        }
4543        // RawVec handles deallocation
4544    }
4545}
4546
4547#[stable(feature = "rust1", since = "1.0.0")]
4548#[rustc_const_unstable(feature = "const_default", issue = "143894")]
4549const impl<T> Default for Vec<T> {
4550    /// Creates an empty `Vec<T>`.
4551    ///
4552    /// The vector will not allocate until elements are pushed onto it.
4553    fn default() -> Vec<T> {
4554        Vec::new()
4555    }
4556}
4557
4558#[stable(feature = "rust1", since = "1.0.0")]
4559impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
4560    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4561        fmt::Debug::fmt(&**self, f)
4562    }
4563}
4564
4565#[stable(feature = "rust1", since = "1.0.0")]
4566impl<T, A: Allocator> AsRef<Vec<T, A>> for Vec<T, A> {
4567    fn as_ref(&self) -> &Vec<T, A> {
4568        self
4569    }
4570}
4571
4572#[stable(feature = "vec_as_mut", since = "1.5.0")]
4573impl<T, A: Allocator> AsMut<Vec<T, A>> for Vec<T, A> {
4574    fn as_mut(&mut self) -> &mut Vec<T, A> {
4575        self
4576    }
4577}
4578
4579#[stable(feature = "rust1", since = "1.0.0")]
4580impl<T, A: Allocator> AsRef<[T]> for Vec<T, A> {
4581    fn as_ref(&self) -> &[T] {
4582        self
4583    }
4584}
4585
4586#[stable(feature = "vec_as_mut", since = "1.5.0")]
4587impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> {
4588    fn as_mut(&mut self) -> &mut [T] {
4589        self
4590    }
4591}
4592
4593#[cfg(not(no_global_oom_handling))]
4594#[stable(feature = "rust1", since = "1.0.0")]
4595impl<T: Clone> From<&[T]> for Vec<T> {
4596    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4597    ///
4598    /// # Examples
4599    ///
4600    /// ```
4601    /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);
4602    /// ```
4603    fn from(s: &[T]) -> Vec<T> {
4604        s.to_vec()
4605    }
4606}
4607
4608#[cfg(not(no_global_oom_handling))]
4609#[stable(feature = "vec_from_mut", since = "1.19.0")]
4610impl<T: Clone> From<&mut [T]> for Vec<T> {
4611    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4612    ///
4613    /// # Examples
4614    ///
4615    /// ```
4616    /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]);
4617    /// ```
4618    fn from(s: &mut [T]) -> Vec<T> {
4619        s.to_vec()
4620    }
4621}
4622
4623#[cfg(not(no_global_oom_handling))]
4624#[stable(feature = "vec_from_array_ref", since = "1.74.0")]
4625impl<T: Clone, const N: usize> From<&[T; N]> for Vec<T> {
4626    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4627    ///
4628    /// # Examples
4629    ///
4630    /// ```
4631    /// assert_eq!(Vec::from(&[1, 2, 3]), vec![1, 2, 3]);
4632    /// ```
4633    fn from(s: &[T; N]) -> Vec<T> {
4634        Self::from(s.as_slice())
4635    }
4636}
4637
4638#[cfg(not(no_global_oom_handling))]
4639#[stable(feature = "vec_from_array_ref", since = "1.74.0")]
4640impl<T: Clone, const N: usize> From<&mut [T; N]> for Vec<T> {
4641    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4642    ///
4643    /// # Examples
4644    ///
4645    /// ```
4646    /// assert_eq!(Vec::from(&mut [1, 2, 3]), vec![1, 2, 3]);
4647    /// ```
4648    fn from(s: &mut [T; N]) -> Vec<T> {
4649        Self::from(s.as_mut_slice())
4650    }
4651}
4652
4653#[cfg(not(no_global_oom_handling))]
4654#[stable(feature = "vec_from_array", since = "1.44.0")]
4655impl<T, const N: usize> From<[T; N]> for Vec<T> {
4656    /// Allocates a `Vec<T>` and moves `s`'s items into it.
4657    ///
4658    /// # Examples
4659    ///
4660    /// ```
4661    /// assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]);
4662    /// ```
4663    fn from(s: [T; N]) -> Vec<T> {
4664        <[T]>::into_vec(Box::new(s))
4665    }
4666}
4667
4668#[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
4669impl<'a, T> From<Cow<'a, [T]>> for Vec<T>
4670where
4671    [T]: ToOwned<Owned = Vec<T>>,
4672{
4673    /// Converts a clone-on-write slice into a vector.
4674    ///
4675    /// If `s` already owns a `Vec<T>`, it will be returned directly.
4676    /// If `s` is borrowing a slice, a new `Vec<T>` will be allocated and
4677    /// filled by cloning `s`'s items into it.
4678    ///
4679    /// # Examples
4680    ///
4681    /// ```
4682    /// # use std::borrow::Cow;
4683    /// let o: Cow<'_, [i32]> = Cow::Owned(vec![1, 2, 3]);
4684    /// let b: Cow<'_, [i32]> = Cow::Borrowed(&[1, 2, 3]);
4685    /// assert_eq!(Vec::from(o), Vec::from(b));
4686    /// ```
4687    fn from(s: Cow<'a, [T]>) -> Vec<T> {
4688        s.into_owned()
4689    }
4690}
4691
4692// note: test pulls in std, which causes errors here
4693#[stable(feature = "vec_from_box", since = "1.18.0")]
4694impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> {
4695    /// Converts a boxed slice into a vector by transferring ownership of
4696    /// the existing heap allocation.
4697    ///
4698    /// # Examples
4699    ///
4700    /// ```
4701    /// let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice();
4702    /// assert_eq!(Vec::from(b), vec![1, 2, 3]);
4703    /// ```
4704    fn from(s: Box<[T], A>) -> Self {
4705        s.into_vec()
4706    }
4707}
4708
4709// note: test pulls in std, which causes errors here
4710#[cfg(not(no_global_oom_handling))]
4711#[stable(feature = "box_from_vec", since = "1.20.0")]
4712impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> {
4713    /// Converts a vector into a boxed slice.
4714    ///
4715    /// Before doing the conversion, this method discards excess capacity like [`Vec::shrink_to_fit`].
4716    ///
4717    /// [owned slice]: Box
4718    /// [`Vec::shrink_to_fit`]: Vec::shrink_to_fit
4719    ///
4720    /// # Examples
4721    ///
4722    /// ```
4723    /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice());
4724    /// ```
4725    ///
4726    /// Any excess capacity is removed:
4727    /// ```
4728    /// let mut vec = Vec::with_capacity(10);
4729    /// vec.extend([1, 2, 3]);
4730    ///
4731    /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice());
4732    /// ```
4733    fn from(v: Vec<T, A>) -> Self {
4734        v.into_boxed_slice()
4735    }
4736}
4737
4738#[cfg(not(no_global_oom_handling))]
4739#[stable(feature = "rust1", since = "1.0.0")]
4740impl From<&str> for Vec<u8> {
4741    /// Allocates a `Vec<u8>` and fills it with a UTF-8 string.
4742    ///
4743    /// # Examples
4744    ///
4745    /// ```
4746    /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);
4747    /// ```
4748    fn from(s: &str) -> Vec<u8> {
4749        From::from(s.as_bytes())
4750    }
4751}
4752
4753#[stable(feature = "array_try_from_vec", since = "1.48.0")]
4754#[rustc_const_unstable(feature = "const_convert", issue = "143773")]
4755const impl<T: [const] Destruct, A: [const] Allocator + [const] Destruct, const N: usize>
4756    TryFrom<Vec<T, A>> for [T; N]
4757{
4758    type Error = Vec<T, A>;
4759
4760    /// Gets the entire contents of the `Vec<T>` as an array,
4761    /// if its size exactly matches that of the requested array.
4762    ///
4763    /// # Examples
4764    ///
4765    /// ```
4766    /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3]));
4767    /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([]));
4768    /// ```
4769    ///
4770    /// If the length doesn't match, the input comes back in `Err`:
4771    /// ```
4772    /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into();
4773    /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
4774    /// ```
4775    ///
4776    /// If you're fine with just getting a prefix of the `Vec<T>`,
4777    /// you can call [`.truncate(N)`](Vec::truncate) first.
4778    /// ```
4779    /// let mut v = String::from("hello world").into_bytes();
4780    /// v.sort();
4781    /// v.truncate(2);
4782    /// let [a, b]: [_; 2] = v.try_into().unwrap();
4783    /// assert_eq!(a, b' ');
4784    /// assert_eq!(b, b'd');
4785    /// ```
4786    fn try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>> {
4787        if vec.len() != N {
4788            return Err(vec);
4789        }
4790
4791        // SAFETY: `.set_len(0)` is always sound.
4792        unsafe { vec.set_len(0) };
4793
4794        // SAFETY: A `Vec`'s pointer is always aligned properly, and
4795        // the alignment the array needs is the same as the items.
4796        // We checked earlier that we have sufficient items.
4797        // The items will not double-drop as the `set_len`
4798        // tells the `Vec` not to also drop them.
4799        let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) };
4800        Ok(array)
4801    }
4802}