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    /// When `vec.len() == vec.capacity()` the allocation is unchanged. Otherwise, the behavior of
1500    /// this method depends on the allocator, which may either shrink the vector in-place or
1501    /// reallocate. The resulting vector might still have some excess capacity, just as
1502    /// is the case for [`with_capacity`]. See [`Allocator::shrink`] for more details.
1503    ///
1504    /// [`with_capacity`]: Vec::with_capacity
1505    ///
1506    /// # Examples
1507    ///
1508    /// ```
1509    /// let mut vec = Vec::with_capacity(10);
1510    /// vec.extend([1, 2, 3]);
1511    /// assert!(vec.capacity() >= 10);
1512    /// vec.shrink_to_fit();
1513    /// assert!(vec.capacity() >= 3);
1514    /// ```
1515    #[cfg(not(no_global_oom_handling))]
1516    #[stable(feature = "rust1", since = "1.0.0")]
1517    #[inline]
1518    pub fn shrink_to_fit(&mut self) {
1519        // The capacity is never less than the length, and there's nothing to do when
1520        // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit`
1521        // by only calling it with a greater capacity.
1522        if self.capacity() > self.len {
1523            self.buf.shrink_to_fit(self.len);
1524        }
1525    }
1526
1527    /// Shrinks the capacity of the vector with a lower bound.
1528    ///
1529    /// The capacity will remain at least as large as both the length
1530    /// and the supplied value.
1531    ///
1532    /// If the current capacity is less than the lower limit, this is a no-op.
1533    ///
1534    /// # Examples
1535    ///
1536    /// ```
1537    /// let mut vec = Vec::with_capacity(10);
1538    /// vec.extend([1, 2, 3]);
1539    /// assert!(vec.capacity() >= 10);
1540    /// vec.shrink_to(4);
1541    /// assert!(vec.capacity() >= 4);
1542    /// vec.shrink_to(0);
1543    /// assert!(vec.capacity() >= 3);
1544    /// ```
1545    #[cfg(not(no_global_oom_handling))]
1546    #[stable(feature = "shrink_to", since = "1.56.0")]
1547    pub fn shrink_to(&mut self, min_capacity: usize) {
1548        if self.capacity() > min_capacity {
1549            self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
1550        }
1551    }
1552
1553    /// Tries to shrink the capacity of the vector as much as possible
1554    ///
1555    /// The behavior of this method depends on the allocator, which may either shrink the vector
1556    /// in-place or reallocate. The resulting vector might still have some excess capacity, just as
1557    /// is the case for [`with_capacity`]. See [`Allocator::shrink`] for more details.
1558    ///
1559    /// [`with_capacity`]: Vec::with_capacity
1560    ///
1561    /// # Errors
1562    ///
1563    /// This function returns an error if the allocator fails to shrink the allocation,
1564    /// the vector thereafter is still safe to use, the capacity remains unchanged
1565    /// however. See [`Allocator::shrink`].
1566    ///
1567    /// # Examples
1568    ///
1569    /// ```
1570    /// #![feature(vec_fallible_shrink)]
1571    ///
1572    /// let mut vec = Vec::with_capacity(10);
1573    /// vec.extend([1, 2, 3]);
1574    /// assert!(vec.capacity() >= 10);
1575    /// vec.try_shrink_to_fit().expect("for this test, shrink shouldn't fail");
1576    /// assert!(vec.capacity() >= 3);
1577    /// ```
1578    #[unstable(feature = "vec_fallible_shrink", issue = "152350")]
1579    #[inline]
1580    pub fn try_shrink_to_fit(&mut self) -> Result<(), TryReserveError> {
1581        if self.capacity() > self.len { self.buf.try_shrink_to_fit(self.len) } else { Ok(()) }
1582    }
1583
1584    /// Shrinks the capacity of the vector with a lower bound.
1585    ///
1586    /// The capacity will remain at least as large as both the length
1587    /// and the supplied value.
1588    ///
1589    /// If the current capacity is less than the lower limit, this is a no-op.
1590    ///
1591    /// # Errors
1592    ///
1593    /// This function returns an error if the allocator fails to shrink the allocation,
1594    /// the vector thereafter is still safe to use, the capacity remains unchanged
1595    /// however. See [`Allocator::shrink`].
1596    ///
1597    /// # Examples
1598    ///
1599    /// ```
1600    /// #![feature(vec_fallible_shrink)]
1601    ///
1602    /// let mut vec = Vec::with_capacity(10);
1603    /// vec.extend([1, 2, 3]);
1604    /// assert!(vec.capacity() >= 10);
1605    /// vec.try_shrink_to(4).expect("for this test, shrink shouldn't fail");
1606    /// assert!(vec.capacity() >= 4);
1607    /// vec.try_shrink_to(0).expect("this is a no-op and thus the allocator isn't involved.");
1608    /// assert!(vec.capacity() >= 3);
1609    /// ```
1610    #[unstable(feature = "vec_fallible_shrink", issue = "152350")]
1611    #[inline]
1612    pub fn try_shrink_to(&mut self, min_capacity: usize) -> Result<(), TryReserveError> {
1613        if self.capacity() > min_capacity {
1614            self.buf.try_shrink_to_fit(cmp::max(self.len, min_capacity))
1615        } else {
1616            Ok(())
1617        }
1618    }
1619
1620    /// Converts the vector into a boxed slice.
1621    ///
1622    /// This conversion is in-place if `vec.len() == vec.capacity()`.
1623    ///
1624    /// Before doing the conversion, this method adjusts the vector's allocation as
1625    /// needed so that, if a backing allocation is present, the layout of the returned
1626    /// slice [*fits*] that allocation. Thus, the vector's former capacity is not needed
1627    /// to determine a layout suitable for deallocation.
1628    ///
1629    /// [*fits*]: crate::alloc::Allocator#memory-fitting
1630    ///
1631    /// # Examples
1632    ///
1633    /// ```
1634    /// let v = vec![1, 2, 3];
1635    ///
1636    /// let slice = v.into_boxed_slice();
1637    /// ```
1638    ///
1639    /// The vector's spare capacity is not retained:
1640    ///
1641    /// ```
1642    /// let mut vec = Vec::with_capacity(10);
1643    /// vec.extend([1, 2, 3]);
1644    ///
1645    /// assert!(vec.capacity() >= 10);
1646    /// let slice = vec.into_boxed_slice();
1647    /// assert_eq!(slice.into_vec().capacity(), 3);
1648    /// ```
1649    #[cfg(not(no_global_oom_handling))]
1650    #[stable(feature = "rust1", since = "1.0.0")]
1651    pub fn into_boxed_slice(mut self) -> Box<[T], A> {
1652        self.shrink_to_fit();
1653        let me = ManuallyDrop::new(self);
1654        // ignore-tidy-undocumented-unsafe
1655        unsafe {
1656            let buf = ptr::read(&me.buf);
1657            let len = me.len();
1658            buf.into_box(len).assume_init()
1659        }
1660    }
1661
1662    /// Converts the Vec into a boxed array. This conversion will discard any spare capacity,
1663    /// if there is any, see [`Vec::into_boxed_slice`].
1664    /// 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).
1665    ///
1666    /// # Errors
1667    ///
1668    /// Returns the original `Vec<T>` in the `Err` variant if [`Vec::len`] does not equal `N`.
1669    ///
1670    /// # Examples
1671    ///
1672    /// ```
1673    /// #![feature(alloc_slice_into_array)]
1674    /// let vec: Vec<i32> = vec![1, 2, 3];
1675    /// let box_array: Box<[i32; 3]> = vec.clone().into_array().unwrap();
1676    /// let not_enough_elements: Result<Box<[i32; 4]>, Vec<i32>> = vec.into_array::<4>();
1677    /// assert_eq!(not_enough_elements, Err(vec![1, 2, 3]));
1678    /// ```
1679    #[cfg(not(no_global_oom_handling))]
1680    #[unstable(feature = "alloc_slice_into_array", issue = "148082")]
1681    pub fn into_array<const N: usize>(self) -> Result<Box<[T; N], A>, Self> {
1682        if self.len() == N {
1683            // SAFETY: `Box::into_array` is guaranteed to return `Ok` if the
1684            // length of the slice is equal to `N`.
1685            // `self.into_boxed_slice().len()` is equal to `self.len()`,
1686            // which we just checked.
1687            Ok(unsafe { self.into_boxed_slice().into_array().unwrap_unchecked() })
1688        } else {
1689            Err(self)
1690        }
1691    }
1692
1693    /// Shortens the vector, keeping the first `len` elements and dropping
1694    /// the rest.
1695    ///
1696    /// If `len` is greater or equal to the vector's current length, this has
1697    /// no effect.
1698    ///
1699    /// The [`drain`] method can emulate `truncate`, but causes the excess
1700    /// elements to be returned instead of dropped.
1701    ///
1702    /// Note that this method has no effect on the allocated capacity
1703    /// of the vector.
1704    ///
1705    /// # Examples
1706    ///
1707    /// Truncating a five element vector to two elements:
1708    ///
1709    /// ```
1710    /// let mut vec = vec![1, 2, 3, 4, 5];
1711    /// vec.truncate(2);
1712    /// assert_eq!(vec, [1, 2]);
1713    /// ```
1714    ///
1715    /// No truncation occurs when `len` is greater than or equal to the
1716    /// vector's current length:
1717    ///
1718    /// ```
1719    /// let mut vec = vec![1, 2, 3];
1720    /// vec.truncate(8);
1721    /// assert_eq!(vec, [1, 2, 3]);
1722    /// ```
1723    ///
1724    /// Truncating when `len == 0` is equivalent to calling the [`clear`]
1725    /// method.
1726    ///
1727    /// ```
1728    /// let mut vec = vec![1, 2, 3];
1729    /// vec.truncate(0);
1730    /// assert_eq!(vec, []);
1731    /// ```
1732    ///
1733    /// [`clear`]: Vec::clear
1734    /// [`drain`]: Vec::drain
1735    #[stable(feature = "rust1", since = "1.0.0")]
1736    pub fn truncate(&mut self, len: usize) {
1737        // SAFETY: `BufWriter::flush_buf` assumes that this will not
1738        // de-initialize any elements of the spare capacity.
1739
1740        // This is safe because:
1741        //
1742        // * the slice passed to `drop_in_place` is valid; the `len >= self.len`
1743        //   case avoids creating an invalid slice, and
1744        // * the `len` of the vector is shrunk before calling `drop_in_place`,
1745        //   such that no value will be dropped twice in case `drop_in_place`
1746        //   were to panic once (if it panics twice, the program aborts).
1747        unsafe {
1748            if len >= self.len {
1749                return;
1750            }
1751            let remaining_len = self.len - len;
1752            let s = self.as_mut_ptr().add(len).cast_slice(remaining_len);
1753            self.len = len;
1754            ptr::drop_in_place(s);
1755        }
1756    }
1757
1758    /// Extracts a slice containing the entire vector.
1759    ///
1760    /// Equivalent to `&s[..]`.
1761    ///
1762    /// # Examples
1763    ///
1764    /// ```
1765    /// use std::io::{self, Write};
1766    /// let buffer = vec![1, 2, 3, 5, 8];
1767    /// io::sink().write(buffer.as_slice()).unwrap();
1768    /// ```
1769    #[inline]
1770    #[stable(feature = "vec_as_slice", since = "1.7.0")]
1771    #[rustc_diagnostic_item = "vec_as_slice"]
1772    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1773    pub const fn as_slice(&self) -> &[T] {
1774        // SAFETY: `slice::from_raw_parts` requires pointee is a contiguous, aligned buffer of size
1775        // `len` containing properly-initialized `T`s. Data must not be mutated for the returned
1776        // lifetime. Further, `len * size_of::<T>` <= `isize::MAX`, and allocation does not
1777        // "wrap" through overflowing memory addresses.
1778        //
1779        // * Vec API guarantees that self.buf:
1780        //      * contains only properly-initialized items within 0..len
1781        //      * is aligned, contiguous, and valid for `len` reads
1782        //      * obeys size and address-wrapping constraints
1783        //
1784        // * We only construct `&mut` references to `self.buf` through `&mut self` methods; borrow-
1785        //   check ensures that it is not possible to mutably alias `self.buf` within the
1786        //   returned lifetime.
1787        unsafe {
1788            // normally this would use `slice::from_raw_parts`, but it's
1789            // instantiated often enough that avoiding the UB check is worth it
1790            &*core::intrinsics::aggregate_raw_ptr::<*const [T], _, _>(self.as_ptr(), self.len)
1791        }
1792    }
1793
1794    /// Extracts a mutable slice of the entire vector.
1795    ///
1796    /// Equivalent to `&mut s[..]`.
1797    ///
1798    /// # Examples
1799    ///
1800    /// ```
1801    /// use std::io::{self, Read};
1802    /// let mut buffer = vec![0; 3];
1803    /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
1804    /// ```
1805    #[inline]
1806    #[stable(feature = "vec_as_slice", since = "1.7.0")]
1807    #[rustc_diagnostic_item = "vec_as_mut_slice"]
1808    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1809    pub const fn as_mut_slice(&mut self) -> &mut [T] {
1810        // SAFETY: `BufWriter::flush_buf` assumes that this will not
1811        // de-initialize any elements of the spare capacity.
1812
1813        // SAFETY: `slice::from_raw_parts_mut` requires pointee is a contiguous, aligned buffer of
1814        // size `len` containing properly-initialized `T`s. Data must not be accessed through any
1815        // other pointer for the returned lifetime. Further, `len * size_of::<T>` <=
1816        // `isize::MAX` and allocation does not "wrap" through overflowing memory addresses.
1817        //
1818        // * Vec API guarantees that self.buf:
1819        //      * contains only properly-initialized items within 0..len
1820        //      * is aligned, contiguous, and valid for `len` reads
1821        //      * obeys size and address-wrapping constraints
1822        //
1823        // * We only construct references to `self.buf` through `&self` and `&mut self` methods;
1824        //   borrow-check ensures that it is not possible to construct a reference to `self.buf`
1825        //   within the returned lifetime.
1826        unsafe {
1827            // normally this would use `slice::from_raw_parts_mut`, but it's
1828            // instantiated often enough that avoiding the UB check is worth it
1829            &mut *core::intrinsics::aggregate_raw_ptr::<*mut [T], _, _>(self.as_mut_ptr(), self.len)
1830        }
1831    }
1832
1833    /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
1834    /// valid for zero sized reads if the vector [didn't allocate].
1835    ///
1836    /// The caller must ensure that the vector outlives the pointer this
1837    /// function returns, or else it will end up dangling.
1838    /// Modifying the vector may cause its buffer to be reallocated,
1839    /// which would also make any pointers to it invalid.
1840    ///
1841    /// The caller must also ensure that the memory the pointer (non-transitively) points to
1842    /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1843    /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1844    ///
1845    /// This method guarantees that for the purpose of the aliasing model, this method
1846    /// does not materialize a reference to the underlying slice, and thus the returned pointer
1847    /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1848    /// and [`as_non_null`].
1849    /// Note that calling other methods that materialize mutable references to the slice,
1850    /// or mutable references to specific elements you are planning on accessing through this pointer,
1851    /// as well as writing to those elements, may still invalidate this pointer.
1852    /// See the second example below for how this guarantee can be used.
1853    ///
1854    ///
1855    /// # Examples
1856    ///
1857    /// ```
1858    /// let x = vec![1, 2, 4];
1859    /// let x_ptr = x.as_ptr();
1860    ///
1861    /// unsafe {
1862    ///     for i in 0..x.len() {
1863    ///         assert_eq!(*x_ptr.add(i), 1 << i);
1864    ///     }
1865    /// }
1866    /// ```
1867    ///
1868    /// Due to the aliasing guarantee, the following code is legal:
1869    ///
1870    /// ```rust
1871    /// unsafe {
1872    ///     let mut v = vec![0, 1, 2];
1873    ///     let ptr1 = v.as_ptr();
1874    ///     let _ = ptr1.read();
1875    ///     let ptr2 = v.as_mut_ptr().offset(2);
1876    ///     ptr2.write(2);
1877    ///     // Notably, the write to `ptr2` did *not* invalidate `ptr1`
1878    ///     // because it mutated a different element:
1879    ///     let _ = ptr1.read();
1880    /// }
1881    /// ```
1882    ///
1883    /// [`as_mut_ptr`]: Vec::as_mut_ptr
1884    /// [`as_ptr`]: Vec::as_ptr
1885    /// [`as_non_null`]: Vec::as_non_null
1886    /// [didn't allocate]: self#memory-layout
1887    #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1888    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1889    #[inline]
1890    #[lint::as_ptr]
1891    #[lint::never_returns_null_ptr]
1892    pub const fn as_ptr(&self) -> *const T {
1893        // We shadow the slice method of the same name to avoid going through
1894        // `deref`, which creates an intermediate reference.
1895        self.buf.ptr()
1896    }
1897
1898    /// Returns a raw mutable pointer to the vector's buffer, or a dangling
1899    /// raw pointer valid for zero sized reads if the vector [didn't allocate].
1900    ///
1901    /// The caller must ensure that the vector outlives the pointer this
1902    /// function returns, or else it will end up dangling.
1903    /// Modifying the vector may cause its buffer to be reallocated,
1904    /// which would also make any pointers to it invalid.
1905    ///
1906    /// This method guarantees that for the purpose of the aliasing model, this method
1907    /// does not materialize a reference to the underlying slice, and thus the returned pointer
1908    /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1909    /// and [`as_non_null`].
1910    /// Note that calling other methods that materialize references to the slice,
1911    /// or references to specific elements you are planning on accessing through this pointer,
1912    /// may still invalidate this pointer.
1913    /// See the second example below for how this guarantee can be used.
1914    ///
1915    /// The method also guarantees that, as long as `T` is not zero-sized and the capacity is
1916    /// nonzero, the pointer may be passed into [`dealloc`] with a layout of
1917    /// `Layout::array::<T>(capacity)` in order to deallocate the backing memory. If this is done,
1918    /// be careful not to run the destructor of the `Vec`, as dropping it will result in
1919    /// double-frees. Wrapping the `Vec` in a [`ManuallyDrop`] is the typical way to achieve this.
1920    ///
1921    /// # Examples
1922    ///
1923    /// ```
1924    /// // Allocate vector big enough for 4 elements.
1925    /// let size = 4;
1926    /// let mut x: Vec<i32> = Vec::with_capacity(size);
1927    /// let x_ptr = x.as_mut_ptr();
1928    ///
1929    /// // Initialize elements via raw pointer writes, then set length.
1930    /// unsafe {
1931    ///     for i in 0..size {
1932    ///         *x_ptr.add(i) = i as i32;
1933    ///     }
1934    ///     x.set_len(size);
1935    /// }
1936    /// assert_eq!(&*x, &[0, 1, 2, 3]);
1937    /// ```
1938    ///
1939    /// Due to the aliasing guarantee, the following code is legal:
1940    ///
1941    /// ```rust
1942    /// unsafe {
1943    ///     let mut v = vec![0];
1944    ///     let ptr1 = v.as_mut_ptr();
1945    ///     ptr1.write(1);
1946    ///     let ptr2 = v.as_mut_ptr();
1947    ///     ptr2.write(2);
1948    ///     // Notably, the write to `ptr2` did *not* invalidate `ptr1`:
1949    ///     ptr1.write(3);
1950    /// }
1951    /// ```
1952    ///
1953    /// Deallocating a vector using [`Box`] (which uses [`dealloc`] internally):
1954    ///
1955    /// ```
1956    /// use std::mem::{ManuallyDrop, MaybeUninit};
1957    ///
1958    /// let mut v = ManuallyDrop::new(vec![0, 1, 2]);
1959    /// let ptr = v.as_mut_ptr();
1960    /// let capacity = v.capacity();
1961    /// let slice_ptr: *mut [MaybeUninit<i32>] =
1962    ///     std::ptr::slice_from_raw_parts_mut(ptr.cast(), capacity);
1963    /// drop(unsafe { Box::from_raw(slice_ptr) });
1964    /// ```
1965    ///
1966    /// [`as_mut_ptr`]: Vec::as_mut_ptr
1967    /// [`as_ptr`]: Vec::as_ptr
1968    /// [`as_non_null`]: Vec::as_non_null
1969    /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
1970    /// [`ManuallyDrop`]: core::mem::ManuallyDrop
1971    /// [didn't allocate]: self#memory-layout
1972    #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1973    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1974    #[lint::as_ptr]
1975    #[lint::never_returns_null_ptr]
1976    #[inline]
1977    pub const fn as_mut_ptr(&mut self) -> *mut T {
1978        // We shadow the slice method of the same name to avoid going through
1979        // `deref_mut`, which creates an intermediate reference.
1980        self.buf.ptr()
1981    }
1982
1983    /// Returns a `NonNull` pointer to the vector's buffer, or a dangling
1984    /// `NonNull` pointer valid for zero sized reads if the vector [didn't allocate].
1985    ///
1986    /// The caller must ensure that the vector outlives the pointer this
1987    /// function returns, or else it will end up dangling.
1988    /// Modifying the vector may cause its buffer to be reallocated,
1989    /// which would also make any pointers to it invalid.
1990    ///
1991    /// This method guarantees that for the purpose of the aliasing model, this method
1992    /// does not materialize a reference to the underlying slice, and thus the returned pointer
1993    /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1994    /// and [`as_non_null`].
1995    /// Note that calling other methods that materialize references to the slice,
1996    /// or references to specific elements you are planning on accessing through this pointer,
1997    /// may still invalidate this pointer.
1998    /// See the second example below for how this guarantee can be used.
1999    ///
2000    /// # Examples
2001    ///
2002    /// ```
2003    /// #![feature(vec_as_non_null)]
2004    ///
2005    /// // Allocate vector big enough for 4 elements.
2006    /// let size = 4;
2007    /// let mut x: Vec<i32> = Vec::with_capacity(size);
2008    /// let x_ptr = x.as_non_null();
2009    ///
2010    /// // Initialize elements via raw pointer writes, then set length.
2011    /// unsafe {
2012    ///     for i in 0..size {
2013    ///         x_ptr.add(i).write(i as i32);
2014    ///     }
2015    ///     x.set_len(size);
2016    /// }
2017    /// assert_eq!(&*x, &[0, 1, 2, 3]);
2018    /// ```
2019    ///
2020    /// Due to the aliasing guarantee, the following code is legal:
2021    ///
2022    /// ```rust
2023    /// #![feature(vec_as_non_null)]
2024    ///
2025    /// unsafe {
2026    ///     let mut v = vec![0];
2027    ///     let ptr1 = v.as_non_null();
2028    ///     ptr1.write(1);
2029    ///     let ptr2 = v.as_non_null();
2030    ///     ptr2.write(2);
2031    ///     // Notably, the write to `ptr2` did *not* invalidate `ptr1`:
2032    ///     ptr1.write(3);
2033    /// }
2034    /// ```
2035    ///
2036    /// [`as_mut_ptr`]: Vec::as_mut_ptr
2037    /// [`as_ptr`]: Vec::as_ptr
2038    /// [`as_non_null`]: Vec::as_non_null
2039    /// [didn't allocate]: self#memory-layout
2040    #[unstable(feature = "vec_as_non_null", issue = "157843")]
2041    #[rustc_const_unstable(feature = "vec_as_non_null", issue = "157843")]
2042    #[lint::as_ptr]
2043    #[inline]
2044    pub const fn as_non_null(&mut self) -> NonNull<T> {
2045        self.buf.non_null()
2046    }
2047
2048    /// Returns a reference to the underlying allocator.
2049    #[stable(feature = "allocator_api", since = "1.100.0")]
2050    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
2051    #[inline]
2052    pub const fn allocator(&self) -> &A {
2053        self.buf.allocator()
2054    }
2055
2056    /// Forces the length of the vector to `new_len`.
2057    ///
2058    /// This is a low-level operation that maintains none of the normal
2059    /// invariants of the type. Normally changing the length of a vector
2060    /// is done using one of the safe operations instead, such as
2061    /// [`truncate`], [`resize`], [`extend`], or [`clear`].
2062    ///
2063    /// [`truncate`]: Vec::truncate
2064    /// [`resize`]: Vec::resize
2065    /// [`extend`]: Extend::extend
2066    /// [`clear`]: Vec::clear
2067    ///
2068    /// # Safety
2069    ///
2070    /// - `new_len` must be less than or equal to [`capacity()`].
2071    /// - The elements at `old_len..new_len` must be initialized.
2072    ///
2073    /// [`capacity()`]: Vec::capacity
2074    ///
2075    /// # Examples
2076    ///
2077    /// See [`spare_capacity_mut()`] for an example with safe
2078    /// initialization of capacity elements and use of this method.
2079    ///
2080    /// `set_len()` can be useful for situations in which the vector
2081    /// is serving as a buffer for other code, particularly over FFI:
2082    ///
2083    /// ```no_run
2084    /// # #![allow(dead_code)]
2085    /// # // This is just a minimal skeleton for the doc example;
2086    /// # // don't use this as a starting point for a real library.
2087    /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void }
2088    /// # const Z_OK: i32 = 0;
2089    /// # unsafe extern "C" {
2090    /// #     fn deflateGetDictionary(
2091    /// #         strm: *mut std::ffi::c_void,
2092    /// #         dictionary: *mut u8,
2093    /// #         dictLength: *mut usize,
2094    /// #     ) -> i32;
2095    /// # }
2096    /// # impl StreamWrapper {
2097    /// pub fn get_dictionary(&self) -> Option<Vec<u8>> {
2098    ///     // Per the FFI method's docs, "32768 bytes is always enough".
2099    ///     let mut dict = Vec::with_capacity(32_768);
2100    ///     let mut dict_length = 0;
2101    ///     // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
2102    ///     // 1. `dict_length` elements were initialized.
2103    ///     // 2. `dict_length` <= the capacity (32_768)
2104    ///     // which makes `set_len` safe to call.
2105    ///     unsafe {
2106    ///         // Make the FFI call...
2107    ///         let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
2108    ///         if r == Z_OK {
2109    ///             // ...and update the length to what was initialized.
2110    ///             dict.set_len(dict_length);
2111    ///             Some(dict)
2112    ///         } else {
2113    ///             None
2114    ///         }
2115    ///     }
2116    /// }
2117    /// # }
2118    /// ```
2119    ///
2120    /// While the following example is sound, there is a memory leak since
2121    /// the inner vectors were not freed prior to the `set_len` call:
2122    ///
2123    /// ```
2124    /// let mut vec = vec![vec![1, 0, 0],
2125    ///                    vec![0, 1, 0],
2126    ///                    vec![0, 0, 1]];
2127    /// // SAFETY:
2128    /// // 1. `old_len..0` is empty so no elements need to be initialized.
2129    /// // 2. `0 <= capacity` always holds whatever `capacity` is.
2130    /// unsafe {
2131    ///     vec.set_len(0);
2132    /// #   // FIXME(https://github.com/rust-lang/miri/issues/3670):
2133    /// #   // use -Zmiri-disable-leak-check instead of unleaking in tests meant to leak.
2134    /// #   vec.set_len(3);
2135    /// }
2136    /// ```
2137    ///
2138    /// Normally, here, one would use [`clear`] instead to correctly drop
2139    /// the contents and thus not leak memory.
2140    ///
2141    /// [`spare_capacity_mut()`]: Vec::spare_capacity_mut
2142    #[inline]
2143    #[stable(feature = "rust1", since = "1.0.0")]
2144    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
2145    pub const unsafe fn set_len(&mut self, new_len: usize) {
2146        ub_checks::assert_unsafe_precondition!(
2147            check_library_ub,
2148            "Vec::set_len requires that new_len <= capacity()",
2149            (new_len: usize = new_len, capacity: usize = self.capacity()) => new_len <= capacity
2150        );
2151
2152        self.len = new_len;
2153    }
2154
2155    /// Removes an element from the vector and returns it.
2156    ///
2157    /// The removed element is replaced by the last element of the vector.
2158    ///
2159    /// This does not preserve ordering of the remaining elements, but is *O*(1).
2160    /// If you need to preserve the element order, use [`remove`] instead.
2161    ///
2162    /// [`remove`]: Vec::remove
2163    ///
2164    /// # Panics
2165    ///
2166    /// Panics if `index` is out of bounds.
2167    ///
2168    /// # Examples
2169    ///
2170    /// ```
2171    /// let mut v = vec!["foo", "bar", "baz", "qux"];
2172    ///
2173    /// assert_eq!(v.swap_remove(1), "bar");
2174    /// assert_eq!(v, ["foo", "qux", "baz"]);
2175    ///
2176    /// assert_eq!(v.swap_remove(0), "foo");
2177    /// assert_eq!(v, ["baz", "qux"]);
2178    /// ```
2179    #[inline]
2180    #[stable(feature = "rust1", since = "1.0.0")]
2181    pub fn swap_remove(&mut self, index: usize) -> T {
2182        #[cold]
2183        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
2184        #[optimize(size)]
2185        fn assert_failed(index: usize, len: usize) -> ! {
2186            panic!("swap_remove index (is {index}) should be < len (is {len})");
2187        }
2188
2189        let len = self.len();
2190        if index >= len {
2191            assert_failed(index, len);
2192        }
2193        // ignore-tidy-undocumented-unsafe
2194        unsafe {
2195            // We replace self[index] with the last element. Note that if the
2196            // bounds check above succeeds there must be a last element (which
2197            // can be self[index] itself).
2198            let value = ptr::read(self.as_ptr().add(index));
2199            let base_ptr = self.as_mut_ptr();
2200            ptr::copy(base_ptr.add(len - 1), base_ptr.add(index), 1);
2201            self.set_len(len - 1);
2202            value
2203        }
2204    }
2205
2206    /// Inserts an element at position `index` within the vector, shifting all
2207    /// elements after it to the right.
2208    ///
2209    /// # Panics
2210    ///
2211    /// Panics if `index > len`.
2212    ///
2213    /// # Examples
2214    ///
2215    /// ```
2216    /// let mut vec = vec!['a', 'b', 'c'];
2217    /// vec.insert(1, 'd');
2218    /// assert_eq!(vec, ['a', 'd', 'b', 'c']);
2219    /// vec.insert(4, 'e');
2220    /// assert_eq!(vec, ['a', 'd', 'b', 'c', 'e']);
2221    /// ```
2222    ///
2223    /// # Time complexity
2224    ///
2225    /// Takes *O*([`Vec::len`]) time. All items after the insertion index must be
2226    /// shifted to the right. In the worst case, all elements are shifted when
2227    /// the insertion index is 0.
2228    #[cfg(not(no_global_oom_handling))]
2229    #[stable(feature = "rust1", since = "1.0.0")]
2230    #[track_caller]
2231    pub fn insert(&mut self, index: usize, element: T) {
2232        let _ = self.insert_mut(index, element);
2233    }
2234
2235    /// Inserts an element at position `index` within the vector, shifting all
2236    /// elements after it to the right, and returning a reference to the new
2237    /// element.
2238    ///
2239    /// # Panics
2240    ///
2241    /// Panics if `index > len`.
2242    ///
2243    /// # Examples
2244    ///
2245    /// ```
2246    /// let mut vec = vec![1, 3, 5, 9];
2247    /// let x = vec.insert_mut(3, 6);
2248    /// *x += 1;
2249    /// assert_eq!(vec, [1, 3, 5, 7, 9]);
2250    /// ```
2251    ///
2252    /// # Time complexity
2253    ///
2254    /// Takes *O*([`Vec::len`]) time. All items after the insertion index must be
2255    /// shifted to the right. In the worst case, all elements are shifted when
2256    /// the insertion index is 0.
2257    #[cfg(not(no_global_oom_handling))]
2258    #[inline]
2259    #[stable(feature = "push_mut", since = "1.95.0")]
2260    #[track_caller]
2261    #[must_use = "if you don't need a reference to the value, use `Vec::insert` instead"]
2262    pub fn insert_mut(&mut self, index: usize, element: T) -> &mut T {
2263        #[cold]
2264        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
2265        #[track_caller]
2266        #[optimize(size)]
2267        fn assert_failed(index: usize, len: usize) -> ! {
2268            panic!("insertion index (is {index}) should be <= len (is {len})");
2269        }
2270
2271        let len = self.len();
2272        if index > len {
2273            assert_failed(index, len);
2274        }
2275
2276        // space for the new element
2277        if len == self.buf.capacity() {
2278            self.buf.grow_one();
2279        }
2280
2281        // ignore-tidy-undocumented-unsafe
2282        unsafe {
2283            // infallible
2284            // The spot to put the new value
2285            let p = self.as_mut_ptr().add(index);
2286            {
2287                if index < len {
2288                    // Shift everything over to make space. (Duplicating the
2289                    // `index`th element into two consecutive places.)
2290                    ptr::copy(p, p.add(1), len - index);
2291                }
2292                // Write it in, overwriting the first copy of the `index`th
2293                // element.
2294                ptr::write(p, element);
2295            }
2296            self.set_len(len + 1);
2297            &mut *p
2298        }
2299    }
2300
2301    /// Removes and returns the element at position `index` within the vector,
2302    /// shifting all elements after it to the left.
2303    ///
2304    /// Note: Because this shifts over the remaining elements, it has a
2305    /// worst-case performance of *O*(*n*). If you don't need the order of elements
2306    /// to be preserved, use [`swap_remove`] instead. If you'd like to remove
2307    /// elements from the beginning of the `Vec`, consider using
2308    /// [`VecDeque::pop_front`] instead.
2309    ///
2310    /// [`swap_remove`]: Vec::swap_remove
2311    /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2312    ///
2313    /// # Panics
2314    ///
2315    /// Panics if `index` is out of bounds.
2316    ///
2317    /// # Examples
2318    ///
2319    /// ```
2320    /// let mut v = vec!['a', 'b', 'c'];
2321    /// assert_eq!(v.remove(1), 'b');
2322    /// assert_eq!(v, ['a', 'c']);
2323    /// ```
2324    #[stable(feature = "rust1", since = "1.0.0")]
2325    #[track_caller]
2326    #[rustc_confusables("delete", "take")]
2327    pub fn remove(&mut self, index: usize) -> T {
2328        #[cold]
2329        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
2330        #[track_caller]
2331        #[optimize(size)]
2332        fn assert_failed(index: usize, len: usize) -> ! {
2333            panic!("removal index (is {index}) should be < len (is {len})");
2334        }
2335
2336        match self.try_remove(index) {
2337            Some(elem) => elem,
2338            None => assert_failed(index, self.len()),
2339        }
2340    }
2341
2342    /// Remove and return the element at position `index` within the vector,
2343    /// shifting all elements after it to the left, or [`None`] if it does not
2344    /// exist.
2345    ///
2346    /// Note: Because this shifts over the remaining elements, it has a
2347    /// worst-case performance of *O*(*n*). If you'd like to remove
2348    /// elements from the beginning of the `Vec`, consider using
2349    /// [`VecDeque::pop_front`] instead.
2350    ///
2351    /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2352    ///
2353    /// # Examples
2354    ///
2355    /// ```
2356    /// let mut v = vec![1, 2, 3];
2357    /// assert_eq!(v.try_remove(0), Some(1));
2358    /// assert_eq!(v.try_remove(2), None);
2359    /// ```
2360    #[stable(feature = "vec_try_remove", since = "1.101.0")]
2361    #[rustc_confusables("delete", "take", "remove")]
2362    pub fn try_remove(&mut self, index: usize) -> Option<T> {
2363        let len = self.len();
2364        if index >= len {
2365            return None;
2366        }
2367        // infallible
2368        let ret;
2369        // ignore-tidy-undocumented-unsafe
2370        unsafe {
2371            {
2372                // the place we are taking from.
2373                let ptr = self.as_mut_ptr().add(index);
2374                // copy it out, unsafely having a copy of the value on
2375                // the stack and in the vector at the same time.
2376                ret = ptr::read(ptr);
2377
2378                // Shift everything down to fill in that spot.
2379                ptr::copy(ptr.add(1), ptr, len - index - 1);
2380            }
2381            self.set_len(len - 1);
2382        }
2383        Some(ret)
2384    }
2385
2386    /// Retains only the elements specified by the predicate.
2387    ///
2388    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
2389    /// This method operates in place, visiting each element exactly once in the
2390    /// original order, and preserves the order of the retained elements.
2391    ///
2392    /// # Examples
2393    ///
2394    /// ```
2395    /// let mut vec = vec![1, 2, 3, 4];
2396    /// vec.retain(|&x| x % 2 == 0);
2397    /// assert_eq!(vec, [2, 4]);
2398    /// ```
2399    ///
2400    /// Because the elements are visited exactly once in the original order,
2401    /// external state may be used to decide which elements to keep.
2402    ///
2403    /// ```
2404    /// let mut vec = vec![1, 2, 3, 4, 5];
2405    /// let keep = [false, true, true, false, true];
2406    /// let mut iter = keep.iter();
2407    /// vec.retain(|_| *iter.next().unwrap());
2408    /// assert_eq!(vec, [2, 3, 5]);
2409    /// ```
2410    #[stable(feature = "rust1", since = "1.0.0")]
2411    pub fn retain<F>(&mut self, mut f: F)
2412    where
2413        F: FnMut(&T) -> bool,
2414    {
2415        self.retain_mut(|elem| f(elem));
2416    }
2417
2418    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
2419    ///
2420    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
2421    /// This method operates in place, visiting each element exactly once in the
2422    /// original order, and preserves the order of the retained elements.
2423    ///
2424    /// # Examples
2425    ///
2426    /// ```
2427    /// let mut vec = vec![1, 2, 3, 4];
2428    /// vec.retain_mut(|x| if *x <= 3 {
2429    ///     *x += 1;
2430    ///     true
2431    /// } else {
2432    ///     false
2433    /// });
2434    /// assert_eq!(vec, [2, 3, 4]);
2435    /// ```
2436    #[stable(feature = "vec_retain_mut", since = "1.61.0")]
2437    pub fn retain_mut<F>(&mut self, mut f: F)
2438    where
2439        F: FnMut(&mut T) -> bool,
2440    {
2441        let original_len = self.len();
2442
2443        if original_len == 0 {
2444            // Empty case: explicit return allows better optimization, vs letting compiler infer it
2445            return;
2446        }
2447
2448        #[cfg(all(target_arch = "aarch64", target_feature = "sve"))]
2449        {
2450            let long_enough = match mem::size_of::<T>() {
2451                1 => original_len >= sve_retain::MIN_SVE_SIZE_1,
2452                2 => original_len >= sve_retain::MIN_SVE_SIZE_2,
2453                4 => original_len >= sve_retain::MIN_SVE_SIZE_4,
2454                8 => original_len >= sve_retain::MIN_SVE_SIZE_8,
2455                _ => false,
2456            };
2457            if long_enough {
2458                // SAFETY: size_of::<T>() is 1, 2, 4 or 8, matching
2459                // the kernel lane widths.
2460                return unsafe { sve_retain::chunked_retain(self, f) };
2461            }
2462        }
2463
2464        // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
2465        //      |            ^- write                ^- read             |
2466        //      |<-              original_len                          ->|
2467        // Kept: Elements which predicate returns true on.
2468        // Hole: Moved or dropped element slot.
2469        // Unchecked: Unchecked valid elements.
2470        //
2471        // This drop guard will be invoked when predicate or `drop` of element panicked.
2472        // It shifts unchecked elements to cover holes and `set_len` to the correct length.
2473        // In cases when predicate and `drop` never panick, it will be optimized out.
2474        struct PanicGuard<'a, T, A: Allocator> {
2475            v: &'a mut Vec<T, A>,
2476            read: usize,
2477            write: usize,
2478            original_len: usize,
2479        }
2480
2481        impl<T, A: Allocator> Drop for PanicGuard<'_, T, A> {
2482            #[cold]
2483            fn drop(&mut self) {
2484                let remaining = self.original_len - self.read;
2485                // SAFETY: Trailing unchecked items must be valid since we never touch them.
2486                unsafe {
2487                    ptr::copy(
2488                        self.v.as_ptr().add(self.read),
2489                        self.v.as_mut_ptr().add(self.write),
2490                        remaining,
2491                    );
2492                }
2493                // SAFETY: After filling holes, all items are in contiguous memory.
2494                unsafe {
2495                    self.v.set_len(self.write + remaining);
2496                }
2497            }
2498        }
2499
2500        let mut read = 0;
2501        loop {
2502            // SAFETY: read < original_len
2503            let cur = unsafe { self.get_unchecked_mut(read) };
2504            if hint::unlikely(!f(cur)) {
2505                break;
2506            }
2507            read += 1;
2508            if read == original_len {
2509                // All elements are kept, return early.
2510                return;
2511            }
2512        }
2513
2514        // Critical section starts here and at least one element is going to be removed.
2515        // Advance `g.read` early to avoid double drop if `drop_in_place` panicked.
2516        let mut g = PanicGuard { v: self, read: read + 1, write: read, original_len };
2517        // SAFETY: previous `read` is always less than original_len.
2518        unsafe { ptr::drop_in_place(&mut *g.v.as_mut_ptr().add(read)) };
2519
2520        while g.read < g.original_len {
2521            // SAFETY: `read` is always less than original_len.
2522            let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.read) };
2523            if !f(cur) {
2524                // Advance `read` early to avoid double drop if `drop_in_place` panicked.
2525                g.read += 1;
2526                // SAFETY: We never touch this element again after dropped.
2527                unsafe { ptr::drop_in_place(cur) };
2528            } else {
2529                // SAFETY: `read` > `write`, so the slots don't overlap.
2530                // We use copy for move, and never touch the source element again.
2531                unsafe {
2532                    let hole = g.v.as_mut_ptr().add(g.write);
2533                    ptr::copy_nonoverlapping(cur, hole, 1);
2534                }
2535                g.write += 1;
2536                g.read += 1;
2537            }
2538        }
2539
2540        // We are leaving the critical section and no panic happened,
2541        // Commit the length change and forget the guard.
2542        // SAFETY: `write` is always less than or equal to original_len.
2543        unsafe { g.v.set_len(g.write) };
2544        mem::forget(g);
2545    }
2546
2547    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
2548    ///
2549    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
2550    /// This method does not maintain the relative order of the retained elements. If order matters,
2551    /// consider using [`Vec::retain_mut`] instead. However, if no items are removed, then all items
2552    /// are left in their original positions.
2553    ///
2554    /// Generally, this method is faster than [`Vec::retain_mut`] due to its weak ordering guarantees.
2555    ///
2556    /// [`Vec::retain_mut`]: crate::vec::Vec::retain_mut
2557    ///
2558    /// Time complexity: *O*(*n*)
2559    ///
2560    ///
2561    /// # Examples
2562    ///
2563    /// ```
2564    /// #![feature(retain_unstable)]
2565    /// let mut vec = vec![4, 3, 2, 1];
2566    /// vec.retain_unstable(|x| if *x <= 3 {
2567    ///     *x += 1;
2568    ///     true
2569    /// } else {
2570    ///     false
2571    /// });
2572    ///
2573    /// vec.sort(); // it might be in any order, so normalize before asserting
2574    /// assert_eq!(vec, [2, 3, 4]);
2575    /// ```
2576    #[unstable(feature = "retain_unstable", issue = "164152")]
2577    pub fn retain_unstable<F>(&mut self, mut f: F)
2578    where
2579        F: FnMut(&mut T) -> bool,
2580    {
2581        // Currently this does the following:
2582        // 1) Search backward until you find an element you want to remove
2583        // 2) Swap this element with an element that was kept in the back
2584        //    (or if there are no remaining elements, simply truncate the vec)
2585        // 3) Repeat from 1) until there's no element to iterate through
2586
2587        let original_len = self.len();
2588
2589        if original_len == 0 {
2590            // Empty case: explicit return allows better optimization, vs letting compiler infer it
2591            return;
2592        }
2593
2594        let mut read_back = original_len;
2595        let mut hole = loop {
2596            if read_back == 0 {
2597                // All elements are kept
2598                return;
2599            }
2600            // SAFETY: read_back - 1 < original_len
2601            let cur = unsafe { &mut *self.as_mut_ptr().add(read_back - 1) };
2602            if hint::unlikely(!f(cur)) {
2603                break cur;
2604            }
2605            read_back -= 1;
2606        };
2607
2608        if read_back < self.len {
2609            let swap = self.pop().unwrap();
2610            *hole = swap;
2611        } else {
2612            self.truncate(self.len - 1);
2613        }
2614        read_back -= 1;
2615
2616        while read_back > 0 {
2617            // SAFETY: read_back - 1 is always less than current length of
2618            // the vector and the loop condition, read_back > 0, prevents
2619            // read_back from underflowing
2620            hole = unsafe { &mut *self.as_mut_ptr().add(read_back - 1) };
2621            if !f(hole) {
2622                if read_back < self.len {
2623                    let swap = self.pop().unwrap();
2624                    *hole = swap;
2625                } else {
2626                    self.truncate(self.len - 1);
2627                }
2628            }
2629            read_back -= 1;
2630        }
2631    }
2632
2633    /// Removes all but the first of consecutive elements in the vector that resolve to the same
2634    /// key.
2635    ///
2636    /// If the vector is sorted, this removes all duplicates.
2637    ///
2638    /// # Examples
2639    ///
2640    /// ```
2641    /// let mut vec = vec![10, 20, 21, 30, 20];
2642    ///
2643    /// vec.dedup_by_key(|i| *i / 10);
2644    ///
2645    /// assert_eq!(vec, [10, 20, 30, 20]);
2646    /// ```
2647    #[stable(feature = "dedup_by", since = "1.16.0")]
2648    #[inline]
2649    pub fn dedup_by_key<F, K>(&mut self, mut key: F)
2650    where
2651        F: FnMut(&mut T) -> K,
2652        K: PartialEq,
2653    {
2654        self.dedup_by(|a, b| key(a) == key(b))
2655    }
2656
2657    /// Removes all but the first of consecutive elements in the vector that are
2658    /// "equal" according to the given predicate function.
2659    ///
2660    /// The predicate `same_bucket(x, p)` is passed references to two elements.
2661    /// If it returns `true`, the element `x` is removed from the vector.
2662    ///
2663    /// The element `p` occurs *before* `x` in the vector (`[.., p, .., x, ..]`),
2664    /// so `same_bucket(x, p)` is receiving them in reversed order (unlike [`windows`]).
2665    ///
2666    /// If the vector is sorted, this removes all duplicates. For more complicated predicates
2667    /// however, the order (ascending vs. descending) can matter.
2668    ///
2669    /// [`windows`]: slice::windows
2670    ///
2671    /// # Examples
2672    ///
2673    /// ```
2674    /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
2675    /// vec.dedup_by(|x, p| x.eq_ignore_ascii_case(p));
2676    /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
2677    /// ```
2678    ///
2679    /// Both references passed to `same_bucket` are mutable.
2680    /// This allows merging elements by mutating `p` and returning `true`:
2681    ///
2682    /// ```
2683    /// let mut ranges = vec![1..2, 2..4, 2..5, 8..9];
2684    ///
2685    /// // Sort ranges by start, and if equal, by end (lexicographically)
2686    /// // Sorting in reverse instead (`x.start.cmp(&p.start)...`) would later fail
2687    /// ranges.sort_unstable_by(|p, x| p.start.cmp(&x.start).then(p.end.cmp(&x.end)));
2688    ///
2689    /// // Merge touching (`1..2` and `2..4`) and then overlapping (`1..4` and `2..5`) ranges
2690    /// ranges.dedup_by(|x, p| {
2691    ///     if p.end >= x.start {
2692    ///         p.end = p.end.max(x.end);
2693    ///         true
2694    ///     } else {
2695    ///         false
2696    ///     }
2697    /// });
2698    ///
2699    /// assert_eq!(ranges, [1..5, 8..9]);
2700    /// ```
2701    #[stable(feature = "dedup_by", since = "1.16.0")]
2702    pub fn dedup_by<F>(&mut self, mut same_bucket: F)
2703    where
2704        F: FnMut(&mut T, &mut T) -> bool,
2705    {
2706        let len = self.len();
2707        if len <= 1 {
2708            return;
2709        }
2710
2711        // Check if we ever want to remove anything.
2712        // This allows to use copy_non_overlapping in next cycle.
2713        // And avoids any memory writes if we don't need to remove anything.
2714        let mut first_duplicate_idx: usize = 1;
2715        let start = self.as_mut_ptr();
2716        while first_duplicate_idx != len {
2717            let found_duplicate = {
2718                // SAFETY: first_duplicate always in range [1..len).
2719                // Note that we start iteration from 1 so we never overflow.
2720                let prev = unsafe { start.add(first_duplicate_idx.wrapping_sub(1)) };
2721                // ignore-tidy-undocumented-unsafe
2722                let current = unsafe { start.add(first_duplicate_idx) };
2723                // We explicitly say in docs that references are reversed.
2724                // ignore-tidy-undocumented-unsafe
2725                unsafe { same_bucket(&mut *current, &mut *prev) }
2726            };
2727            if found_duplicate {
2728                break;
2729            }
2730            first_duplicate_idx += 1;
2731        }
2732        // Don't need to remove anything.
2733        // We cannot get bigger than len.
2734        if first_duplicate_idx == len {
2735            return;
2736        }
2737        // SAFETY: first_duplicate_idx always in range [1..len)
2738        unsafe {
2739            self.dedup_tail(same_bucket, first_duplicate_idx);
2740        }
2741    }
2742
2743    /// Continues deduplication after the first duplicate is found.
2744    ///
2745    /// The function treats `self[first_duplicate]` as the first duplicated
2746    /// element and drops it.
2747    ///
2748    /// # Safety
2749    ///
2750    /// `1 <= first_duplicate < self.len()`
2751    unsafe fn dedup_tail<F>(&mut self, mut same_bucket: F, first_duplicate: usize)
2752    where
2753        F: FnMut(&mut T, &mut T) -> bool,
2754    {
2755        /* INVARIANT: vec.len() > read > write > write-1 >= 0 */
2756        struct FillGapOnDrop<'a, T, A: core::alloc::Allocator> {
2757            /* Offset of the element we want to check if it is duplicate */
2758            read: usize,
2759
2760            /* Offset of the place where we want to place the non-duplicate
2761             * when we find it. */
2762            write: usize,
2763
2764            /* The Vec that would need correction if `same_bucket` panicked */
2765            vec: &'a mut Vec<T, A>,
2766        }
2767
2768        impl<'a, T, A: core::alloc::Allocator> Drop for FillGapOnDrop<'a, T, A> {
2769            fn drop(&mut self) {
2770                /* This code gets executed when `same_bucket` panics */
2771
2772                // SAFETY: invariant guarantees that `read - write`
2773                // and `len - read` never overflow and that the copy is always
2774                // in-bounds.
2775                unsafe {
2776                    let ptr = self.vec.as_mut_ptr();
2777                    let len = self.vec.len();
2778
2779                    /* How many items were left when `same_bucket` panicked.
2780                     * Basically vec[read..].len() */
2781                    let items_left = len.wrapping_sub(self.read);
2782
2783                    /* Pointer to first item in vec[write..write+items_left] slice */
2784                    let dropped_ptr = ptr.add(self.write);
2785                    /* Pointer to first item in vec[read..] slice */
2786                    let valid_ptr = ptr.add(self.read);
2787
2788                    /* Copy `vec[read..]` to `vec[write..write+items_left]`.
2789                     * The slices can overlap, so `copy_nonoverlapping` cannot be used */
2790                    ptr::copy(valid_ptr, dropped_ptr, items_left);
2791
2792                    /* How many items have been already dropped
2793                     * Basically vec[read..write].len() */
2794                    let dropped = self.read.wrapping_sub(self.write);
2795
2796                    self.vec.set_len(len - dropped);
2797                }
2798            }
2799        }
2800
2801        let start = self.as_mut_ptr();
2802        let len = self.len();
2803
2804        /* Drop items while going through Vec, it should be more efficient than
2805         * doing slice partition_dedup + truncate */
2806
2807        // Construct gap first and then drop item to avoid memory corruption if `T::drop` panics.
2808        let mut gap =
2809            FillGapOnDrop { read: first_duplicate + 1, write: first_duplicate, vec: self };
2810
2811        // SAFETY: By this function's safety contract, `first_duplicate < self.len()`.
2812        // If drop panics, `gap` would remove this item without drop.
2813        unsafe {
2814            ptr::drop_in_place(start.add(first_duplicate));
2815        }
2816
2817        // SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr
2818        // are always in-bounds and read_ptr never aliases prev_ptr
2819        unsafe {
2820            while gap.read < len {
2821                let read_ptr = start.add(gap.read);
2822                let prev_ptr = start.add(gap.write.wrapping_sub(1));
2823
2824                // We explicitly say in docs that references are reversed.
2825                let found_duplicate = same_bucket(&mut *read_ptr, &mut *prev_ptr);
2826                if found_duplicate {
2827                    // Increase `gap.read` now since the drop may panic.
2828                    gap.read += 1;
2829                    /* We have found duplicate, drop it in-place */
2830                    ptr::drop_in_place(read_ptr);
2831                } else {
2832                    let write_ptr = start.add(gap.write);
2833
2834                    /* read_ptr cannot be equal to write_ptr because at this point
2835                     * we guaranteed to skip at least one element (before loop starts).
2836                     */
2837                    ptr::copy_nonoverlapping(read_ptr, write_ptr, 1);
2838
2839                    /* We have filled that place, so go further */
2840                    gap.write += 1;
2841                    gap.read += 1;
2842                }
2843            }
2844
2845            /* Technically we could let `gap` clean up with its Drop, but
2846             * when `same_bucket` is guaranteed to not panic, this bloats a little
2847             * the codegen, so we just do it manually */
2848            gap.vec.set_len(gap.write);
2849            mem::forget(gap);
2850        }
2851    }
2852
2853    /// Appends an element and returns a reference to it if there is sufficient spare capacity,
2854    /// otherwise an error is returned with the element.
2855    ///
2856    /// Unlike [`push`] this method will not reallocate when there's insufficient capacity.
2857    /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity.
2858    ///
2859    /// [`push`]: Vec::push
2860    /// [`reserve`]: Vec::reserve
2861    /// [`try_reserve`]: Vec::try_reserve
2862    ///
2863    /// # Examples
2864    ///
2865    /// A manual, panic-free alternative to [`FromIterator`]:
2866    ///
2867    /// ```
2868    /// #![feature(vec_push_within_capacity)]
2869    ///
2870    /// use std::collections::TryReserveError;
2871    /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> {
2872    ///     let mut vec = Vec::new();
2873    ///     for value in iter {
2874    ///         if let Err(value) = vec.push_within_capacity(value) {
2875    ///             vec.try_reserve(1)?;
2876    ///             // this cannot fail, the previous line either returned or added at least 1 free slot
2877    ///             let _ = vec.push_within_capacity(value);
2878    ///         }
2879    ///     }
2880    ///     Ok(vec)
2881    /// }
2882    /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100)));
2883    /// ```
2884    ///
2885    /// # Time complexity
2886    ///
2887    /// Takes *O*(1) time.
2888    #[inline]
2889    #[unstable(feature = "vec_push_within_capacity", issue = "100486")]
2890    pub fn push_within_capacity(&mut self, value: T) -> Result<&mut T, T> {
2891        if self.len == self.buf.capacity() {
2892            return Err(value);
2893        }
2894
2895        // ignore-tidy-undocumented-unsafe
2896        let end = unsafe { self.as_mut_ptr().add(self.len) };
2897        // ignore-tidy-undocumented-unsafe
2898        unsafe { ptr::write(end, value) };
2899        self.len += 1;
2900
2901        // SAFETY: We just wrote a value to the pointer that will live the lifetime of the reference.
2902        Ok(unsafe { &mut *end })
2903    }
2904
2905    /// Removes the last element from a vector and returns it, or [`None`] if it
2906    /// is empty.
2907    ///
2908    /// If you'd like to pop the first element, consider using
2909    /// [`VecDeque::pop_front`] instead.
2910    ///
2911    /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2912    ///
2913    /// # Examples
2914    ///
2915    /// ```
2916    /// let mut vec = vec![1, 2, 3];
2917    /// assert_eq!(vec.pop(), Some(3));
2918    /// assert_eq!(vec, [1, 2]);
2919    /// ```
2920    ///
2921    /// # Time complexity
2922    ///
2923    /// Takes *O*(1) time.
2924    #[inline]
2925    #[stable(feature = "rust1", since = "1.0.0")]
2926    #[rustc_diagnostic_item = "vec_pop"]
2927    pub fn pop(&mut self) -> Option<T> {
2928        if self.len == 0 {
2929            None
2930        } else {
2931            self.len -= 1;
2932            // ignore-tidy-undocumented-unsafe
2933            unsafe {
2934                core::hint::assert_unchecked(self.len < self.capacity());
2935                Some(ptr::read(self.as_ptr().add(self.len())))
2936            }
2937        }
2938    }
2939
2940    /// Removes and returns the last element from a vector if the predicate
2941    /// returns `true`, or [`None`] if the predicate returns false or the vector
2942    /// is empty (the predicate will not be called in that case).
2943    ///
2944    /// # Examples
2945    ///
2946    /// ```
2947    /// let mut vec = vec![1, 2, 3, 4];
2948    /// let pred = |x: &mut i32| *x % 2 == 0;
2949    ///
2950    /// assert_eq!(vec.pop_if(pred), Some(4));
2951    /// assert_eq!(vec, [1, 2, 3]);
2952    /// assert_eq!(vec.pop_if(pred), None);
2953    /// ```
2954    #[stable(feature = "vec_pop_if", since = "1.86.0")]
2955    pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
2956        let last = self.last_mut()?;
2957        if predicate(last) { self.pop() } else { None }
2958    }
2959
2960    /// Returns a mutable reference to the last item in the vector, or
2961    /// `None` if it is empty.
2962    ///
2963    /// # Examples
2964    ///
2965    /// Basic usage:
2966    ///
2967    /// ```
2968    /// #![feature(vec_peek_mut)]
2969    /// let mut vec = Vec::new();
2970    /// assert!(vec.peek_mut().is_none());
2971    ///
2972    /// vec.push(1);
2973    /// vec.push(5);
2974    /// vec.push(2);
2975    /// assert_eq!(vec.last(), Some(&2));
2976    /// if let Some(mut val) = vec.peek_mut() {
2977    ///     *val = 0;
2978    /// }
2979    /// assert_eq!(vec.last(), Some(&0));
2980    /// ```
2981    #[inline]
2982    #[unstable(feature = "vec_peek_mut", issue = "122742")]
2983    pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, A>>
2984    where
2985        A: AllocatorNightly,
2986    {
2987        PeekMut::new(self)
2988    }
2989
2990    /// Moves all the elements of `other` into `self`, leaving `other` empty.
2991    ///
2992    /// # Panics
2993    ///
2994    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
2995    ///
2996    /// # Examples
2997    ///
2998    /// ```
2999    /// let mut vec = vec![1, 2, 3];
3000    /// let mut vec2 = vec![4, 5, 6];
3001    /// vec.append(&mut vec2);
3002    /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
3003    /// assert_eq!(vec2, []);
3004    /// ```
3005    #[cfg(not(no_global_oom_handling))]
3006    #[inline]
3007    #[stable(feature = "append", since = "1.4.0")]
3008    pub fn append(&mut self, other: &mut Self) {
3009        // ignore-tidy-undocumented-unsafe
3010        unsafe {
3011            self.append_elements(other.as_slice() as _);
3012            other.set_len(0);
3013        }
3014    }
3015
3016    /// Appends elements to `self` from other buffer.
3017    #[cfg(not(no_global_oom_handling))]
3018    #[inline]
3019    unsafe fn append_elements(&mut self, other: *const [T]) {
3020        self.reserve(other.len());
3021        // ignore-tidy-undocumented-unsafe
3022        unsafe {
3023            self.append_elements_unreserved(other);
3024        }
3025    }
3026
3027    /// Appends elements to `self` from other buffer, returning [`TryReserveError`] on OOM.
3028    #[inline]
3029    unsafe fn try_append_elements(&mut self, other: *const [T]) -> Result<(), TryReserveError> {
3030        self.try_reserve(other.len())?;
3031        // ignore-tidy-undocumented-unsafe
3032        unsafe {
3033            self.append_elements_unreserved(other);
3034        }
3035        Ok(())
3036    }
3037
3038    /// Appends elements to `self` from other buffer without reserving additional capacity.
3039    #[inline]
3040    unsafe fn append_elements_unreserved(&mut self, other: *const [T]) {
3041        let count = other.len();
3042        let len = self.len();
3043        if count > 0 {
3044            // ignore-tidy-undocumented-unsafe
3045            unsafe {
3046                ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count)
3047            };
3048        }
3049        self.len += count;
3050    }
3051
3052    /// Removes the subslice indicated by the given range from the vector,
3053    /// returning a double-ended iterator over the removed subslice.
3054    ///
3055    /// If the iterator is dropped before being fully consumed,
3056    /// it drops the remaining removed elements.
3057    ///
3058    /// The returned iterator keeps a mutable borrow on the vector to optimize
3059    /// its implementation.
3060    ///
3061    /// # Panics
3062    ///
3063    /// Panics if the range has `start_bound > end_bound`, or, if the range is
3064    /// bounded on either end and past the length of the vector.
3065    ///
3066    /// # Leaking
3067    ///
3068    /// If the returned iterator goes out of scope without being dropped (due to
3069    /// [`mem::forget`], for example), the vector may have lost and leaked
3070    /// elements arbitrarily, including elements outside the range.
3071    ///
3072    /// # Examples
3073    ///
3074    /// ```
3075    /// let mut v = vec![1, 2, 3];
3076    /// let u: Vec<_> = v.drain(1..).collect();
3077    /// assert_eq!(v, &[1]);
3078    /// assert_eq!(u, &[2, 3]);
3079    ///
3080    /// // A full range clears the vector, like `clear()` does
3081    /// v.drain(..);
3082    /// assert_eq!(v, &[]);
3083    /// ```
3084    #[stable(feature = "drain", since = "1.6.0")]
3085    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
3086    where
3087        A: AllocatorNightly,
3088        R: RangeBounds<usize>,
3089    {
3090        // Memory safety
3091        //
3092        // When the Drain is first created, it shortens the length of
3093        // the source vector to make sure no uninitialized or moved-from elements
3094        // are accessible at all if the Drain's destructor never gets to run.
3095        //
3096        // Drain will ptr::read out the values to remove.
3097        // When finished, remaining tail of the vec is copied back to cover
3098        // the hole, and the vector length is restored to the new length.
3099        //
3100        let len = self.len();
3101        let Range { start, end } = slice::range(range, ..len);
3102
3103        // ignore-tidy-undocumented-unsafe
3104        unsafe {
3105            // set self.vec length's to start, to be safe in case Drain is leaked
3106            self.set_len(start);
3107            let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
3108            Drain {
3109                tail_start: end,
3110                tail_len: len - end,
3111                iter: range_slice.iter(),
3112                vec: NonNull::from(self),
3113            }
3114        }
3115    }
3116
3117    /// Clears the vector, removing all values.
3118    ///
3119    /// Note that this method has no effect on the allocated capacity
3120    /// of the vector.
3121    ///
3122    /// # Examples
3123    ///
3124    /// ```
3125    /// let mut v = vec![1, 2, 3];
3126    ///
3127    /// v.clear();
3128    ///
3129    /// assert!(v.is_empty());
3130    /// ```
3131    #[inline]
3132    #[stable(feature = "rust1", since = "1.0.0")]
3133    pub fn clear(&mut self) {
3134        // Though this is equivalent to `truncate(0)`, the manual version
3135        // optimizes better, justifying the additional complexity
3136        // (see #96002 and #154095 for context).
3137
3138        let elems: *mut [T] = self.as_mut_slice();
3139
3140        // SAFETY:
3141        // - `elems` comes directly from `as_mut_slice` and is therefore valid.
3142        // - Setting `self.len` before calling `drop_in_place` means that,
3143        //   if an element's `Drop` impl panics, the vector's `Drop` impl will
3144        //   do nothing (leaking the rest of the elements) instead of dropping
3145        //   some twice.
3146        unsafe {
3147            self.len = 0;
3148            ptr::drop_in_place(elems);
3149        }
3150    }
3151
3152    /// Returns the number of elements in the vector, also referred to
3153    /// as its 'length'.
3154    ///
3155    /// # Examples
3156    ///
3157    /// ```
3158    /// let a = vec![1, 2, 3];
3159    /// assert_eq!(a.len(), 3);
3160    /// ```
3161    #[inline]
3162    #[stable(feature = "rust1", since = "1.0.0")]
3163    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
3164    #[rustc_confusables("length", "size")]
3165    pub const fn len(&self) -> usize {
3166        let len = self.len;
3167
3168        // SAFETY: The maximum capacity of `Vec<T>` is `isize::MAX` bytes, so the maximum value can
3169        // be returned is `usize::checked_div(size_of::<T>()).unwrap_or(usize::MAX)`, which
3170        // matches the definition of `T::MAX_SLICE_LEN`.
3171        unsafe { intrinsics::assume(len <= T::MAX_SLICE_LEN) };
3172
3173        len
3174    }
3175
3176    /// Returns `true` if the vector contains no elements.
3177    ///
3178    /// # Examples
3179    ///
3180    /// ```
3181    /// let mut v = Vec::new();
3182    /// assert!(v.is_empty());
3183    ///
3184    /// v.push(1);
3185    /// assert!(!v.is_empty());
3186    /// ```
3187    #[stable(feature = "rust1", since = "1.0.0")]
3188    #[rustc_diagnostic_item = "vec_is_empty"]
3189    #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
3190    pub const fn is_empty(&self) -> bool {
3191        self.len() == 0
3192    }
3193
3194    /// Splits the collection into two at the given index.
3195    ///
3196    /// Returns a newly allocated vector containing the elements in the range
3197    /// `[at, len)`. After the call, the original vector will be left containing
3198    /// the elements `[0, at)` with its previous capacity unchanged.
3199    ///
3200    /// - If you want to take ownership of the entire contents and capacity of
3201    ///   the vector, see [`mem::take`] or [`mem::replace`].
3202    /// - If you don't need the returned vector at all, see [`Vec::truncate`].
3203    /// - If you want to take ownership of an arbitrary subslice, or you don't
3204    ///   necessarily want to store the removed items in a vector, see [`Vec::drain`].
3205    ///
3206    /// # Panics
3207    ///
3208    /// Panics if `at > len`.
3209    ///
3210    /// # Examples
3211    ///
3212    /// ```
3213    /// let mut vec = vec!['a', 'b', 'c'];
3214    /// let vec2 = vec.split_off(1);
3215    /// assert_eq!(vec, ['a']);
3216    /// assert_eq!(vec2, ['b', 'c']);
3217    /// ```
3218    #[cfg(not(no_global_oom_handling))]
3219    #[inline]
3220    #[must_use = "use `.truncate()` if you don't need the other half"]
3221    #[stable(feature = "split_off", since = "1.4.0")]
3222    #[track_caller]
3223    pub fn split_off(&mut self, at: usize) -> Self
3224    where
3225        A: Clone,
3226    {
3227        #[cold]
3228        #[cfg_attr(not(panic = "immediate-abort"), inline(never))]
3229        #[track_caller]
3230        #[optimize(size)]
3231        fn assert_failed(at: usize, len: usize) -> ! {
3232            panic!("`at` split index (is {at}) should be <= len (is {len})");
3233        }
3234
3235        if at > self.len() {
3236            assert_failed(at, self.len());
3237        }
3238
3239        let other_len = self.len - at;
3240        let mut other = Vec::with_capacity_in(other_len, self.allocator().clone());
3241
3242        // Unsafely `set_len` and copy items to `other`.
3243        // ignore-tidy-undocumented-unsafe
3244        unsafe {
3245            self.set_len(at);
3246            other.set_len(other_len);
3247
3248            ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
3249        }
3250        other
3251    }
3252
3253    /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
3254    ///
3255    /// If `new_len` is greater than `len`, the `Vec` is extended by the
3256    /// difference, with each additional slot filled with the result of
3257    /// calling the closure `f`. The return values from `f` will end up
3258    /// in the `Vec` in the order they have been generated.
3259    ///
3260    /// If `new_len` is less than or equal to `len`, the `Vec` is simply
3261    /// truncated.
3262    ///
3263    /// This method uses a closure to create new values on every push. If
3264    /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you
3265    /// want to use the [`Default`] trait to generate values, you can
3266    /// pass [`Default::default`] as the second argument.
3267    ///
3268    /// # Panics
3269    ///
3270    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
3271    ///
3272    /// # Examples
3273    ///
3274    /// ```
3275    /// let mut vec = vec![1, 2, 3];
3276    /// vec.resize_with(5, Default::default);
3277    /// assert_eq!(vec, [1, 2, 3, 0, 0]);
3278    ///
3279    /// let mut vec = vec![];
3280    /// let mut p = 1;
3281    /// vec.resize_with(4, || { p *= 2; p });
3282    /// assert_eq!(vec, [2, 4, 8, 16]);
3283    /// ```
3284    #[cfg(not(no_global_oom_handling))]
3285    #[stable(feature = "vec_resize_with", since = "1.33.0")]
3286    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
3287    where
3288        F: FnMut() -> T,
3289    {
3290        let len = self.len();
3291        if new_len > len {
3292            self.extend_trusted(iter::repeat_with(f).take(new_len - len));
3293        } else {
3294            self.truncate(new_len);
3295        }
3296    }
3297
3298    /// Consumes and leaks the `Vec`, returning a mutable reference to the contents,
3299    /// `&'a mut [T]`.
3300    ///
3301    /// Note that the type `T` must outlive the chosen lifetime `'a`. If the type
3302    /// has only static references, or none at all, then this may be chosen to be
3303    /// `'static`.
3304    ///
3305    /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`,
3306    /// so the leaked allocation may include unused capacity that is not part
3307    /// of the returned slice.
3308    ///
3309    /// This function is mainly useful for data that lives for the remainder of
3310    /// the program's life. Dropping the returned reference will cause a memory
3311    /// leak.
3312    ///
3313    /// # Examples
3314    ///
3315    /// Simple usage:
3316    ///
3317    /// ```
3318    /// let x = vec![1, 2, 3];
3319    /// let static_ref: &'static mut [usize] = x.leak();
3320    /// static_ref[0] += 1;
3321    /// assert_eq!(static_ref, &[2, 2, 3]);
3322    /// # // FIXME(https://github.com/rust-lang/miri/issues/3670):
3323    /// # // use -Zmiri-disable-leak-check instead of unleaking in tests meant to leak.
3324    /// # drop(unsafe { Box::from_raw(static_ref) });
3325    /// ```
3326    #[stable(feature = "vec_leak", since = "1.47.0")]
3327    #[inline]
3328    pub fn leak<'a>(self) -> &'a mut [T]
3329    where
3330        A: 'a,
3331    {
3332        let mut me = ManuallyDrop::new(self);
3333        // ignore-tidy-undocumented-unsafe
3334        unsafe { slice::from_raw_parts_mut(me.as_mut_ptr(), me.len) }
3335    }
3336
3337    /// Returns the remaining spare capacity of the vector as a slice of
3338    /// `MaybeUninit<T>`.
3339    ///
3340    /// The returned slice can be used to fill the vector with data (e.g. by
3341    /// reading from a file) before marking the data as initialized using the
3342    /// [`set_len`] method.
3343    ///
3344    /// [`set_len`]: Vec::set_len
3345    ///
3346    /// # Examples
3347    ///
3348    /// ```
3349    /// // Allocate vector big enough for 10 elements.
3350    /// let mut v = Vec::with_capacity(10);
3351    ///
3352    /// // Fill in the first 3 elements.
3353    /// let uninit = v.spare_capacity_mut();
3354    /// uninit[0].write(0);
3355    /// uninit[1].write(1);
3356    /// uninit[2].write(2);
3357    ///
3358    /// // Mark the first 3 elements of the vector as being initialized.
3359    /// unsafe {
3360    ///     v.set_len(3);
3361    /// }
3362    ///
3363    /// assert_eq!(&v, &[0, 1, 2]);
3364    /// ```
3365    #[stable(feature = "vec_spare_capacity", since = "1.60.0")]
3366    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
3367    #[inline]
3368    pub const fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
3369        // Note:
3370        // This method is not implemented in terms of `split_at_spare_mut`,
3371        // to prevent invalidation of pointers to the buffer.
3372        // ignore-tidy-undocumented-unsafe
3373        unsafe {
3374            slice::from_raw_parts_mut(
3375                self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
3376                self.buf.capacity() - self.len,
3377            )
3378        }
3379    }
3380
3381    /// Returns vector content as a slice of `T`, along with the remaining spare
3382    /// capacity of the vector as a slice of `MaybeUninit<T>`.
3383    ///
3384    /// The returned spare capacity slice can be used to fill the vector with data
3385    /// (e.g. by reading from a file) before marking the data as initialized using
3386    /// the [`set_len`] method.
3387    ///
3388    /// [`set_len`]: Vec::set_len
3389    ///
3390    /// Note that this is a low-level API, which should be used with care for
3391    /// optimization purposes. If you need to append data to a `Vec`
3392    /// you can use [`push`], [`extend`], [`extend_from_slice`],
3393    /// [`extend_from_within`], [`insert`], [`append`], [`resize`] or
3394    /// [`resize_with`], depending on your exact needs.
3395    ///
3396    /// [`push`]: Vec::push
3397    /// [`extend`]: Vec::extend
3398    /// [`extend_from_slice`]: Vec::extend_from_slice
3399    /// [`extend_from_within`]: Vec::extend_from_within
3400    /// [`insert`]: Vec::insert
3401    /// [`append`]: Vec::append
3402    /// [`resize`]: Vec::resize
3403    /// [`resize_with`]: Vec::resize_with
3404    ///
3405    /// # Examples
3406    ///
3407    /// ```
3408    /// #![feature(vec_split_at_spare)]
3409    ///
3410    /// let mut v = vec![1, 1, 2];
3411    ///
3412    /// // Reserve additional space big enough for 10 elements.
3413    /// v.reserve(10);
3414    ///
3415    /// let (init, uninit) = v.split_at_spare_mut();
3416    /// let sum = init.iter().copied().sum::<u32>();
3417    ///
3418    /// // Fill in the next 4 elements.
3419    /// uninit[0].write(sum);
3420    /// uninit[1].write(sum * 2);
3421    /// uninit[2].write(sum * 3);
3422    /// uninit[3].write(sum * 4);
3423    ///
3424    /// // Mark the 4 elements of the vector as being initialized.
3425    /// unsafe {
3426    ///     let len = v.len();
3427    ///     v.set_len(len + 4);
3428    /// }
3429    ///
3430    /// assert_eq!(&v, &[1, 1, 2, 4, 8, 12, 16]);
3431    /// ```
3432    #[unstable(feature = "vec_split_at_spare", issue = "81944")]
3433    #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
3434    #[inline]
3435    pub const fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) {
3436        // SAFETY:
3437        // - len is ignored and so never changed
3438        let (init, spare, _) = unsafe { self.split_at_spare_mut_with_len() };
3439        (init, spare)
3440    }
3441
3442    /// Safety: changing returned .2 (&mut usize) is considered the same as calling `.set_len(_)`.
3443    ///
3444    /// This method provides unique access to all vec parts at once in `extend_from_within`.
3445    const unsafe fn split_at_spare_mut_with_len(
3446        &mut self,
3447    ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) {
3448        let ptr = self.as_mut_ptr();
3449        // SAFETY:
3450        // - `ptr` is guaranteed to be valid for `self.len` elements
3451        // - but the allocation extends out to `self.buf.capacity()` elements, possibly
3452        // uninitialized
3453        let spare_ptr = unsafe { ptr.add(self.len) };
3454        let spare_ptr = spare_ptr.cast_uninit();
3455        let spare_len = self.buf.capacity() - self.len;
3456
3457        // SAFETY:
3458        // - `ptr` is guaranteed to be valid for `self.len` elements
3459        // - `spare_ptr` is pointing one element past the buffer, so it doesn't overlap with `initialized`
3460        unsafe {
3461            let initialized = slice::from_raw_parts_mut(ptr, self.len);
3462            let spare = slice::from_raw_parts_mut(spare_ptr, spare_len);
3463
3464            (initialized, spare, &mut self.len)
3465        }
3466    }
3467
3468    /// Groups every `N` elements in the `Vec<T>` into chunks to produce a `Vec<[T; N]>`, dropping
3469    /// elements in the remainder. `N` must be greater than zero.
3470    ///
3471    /// If the capacity is not a multiple of the chunk size, the buffer will shrink down to the
3472    /// nearest multiple with a reallocation or deallocation.
3473    ///
3474    /// This function can be used to reverse [`Vec::into_flattened`].
3475    ///
3476    /// # Examples
3477    ///
3478    /// ```
3479    /// #![feature(vec_into_chunks)]
3480    ///
3481    /// let vec = vec![0, 1, 2, 3, 4, 5, 6, 7];
3482    /// assert_eq!(vec.into_chunks::<3>(), [[0, 1, 2], [3, 4, 5]]);
3483    ///
3484    /// let vec = vec![0, 1, 2, 3];
3485    /// let chunks: Vec<[u8; 10]> = vec.into_chunks();
3486    /// assert!(chunks.is_empty());
3487    ///
3488    /// let flat = vec![0; 8 * 8 * 8];
3489    /// let reshaped: Vec<[[[u8; 8]; 8]; 8]> = flat.into_chunks().into_chunks().into_chunks();
3490    /// assert_eq!(reshaped.len(), 1);
3491    /// ```
3492    #[cfg(not(no_global_oom_handling))]
3493    #[unstable(feature = "vec_into_chunks", issue = "142137")]
3494    pub fn into_chunks<const N: usize>(mut self) -> Vec<[T; N], A> {
3495        const {
3496            assert!(N != 0, "chunk size must be greater than zero");
3497        }
3498
3499        let (len, cap) = (self.len(), self.capacity());
3500
3501        let len_remainder = len % N;
3502        if len_remainder != 0 {
3503            self.truncate(len - len_remainder);
3504        }
3505
3506        let cap_remainder = cap % N;
3507        if !T::IS_ZST && cap_remainder != 0 {
3508            self.buf.shrink_to_fit(cap - cap_remainder);
3509        }
3510
3511        let (ptr, _, _, alloc) = self.into_raw_parts_with_allocator();
3512
3513        // SAFETY:
3514        // - `ptr` and `alloc` were just returned from `self.into_raw_parts_with_allocator()`
3515        // - `[T; N]` has the same alignment as `T`
3516        // - `size_of::<[T; N]>() * cap / N == size_of::<T>() * cap`
3517        // - `len / N <= cap / N` because `len <= cap`
3518        // - the allocated memory consists of `len / N` valid values of type `[T; N]`
3519        // - `cap / N` fits the size of the allocated memory after shrinking
3520        unsafe { Vec::from_raw_parts_in(ptr.cast(), len / N, cap / N, alloc) }
3521    }
3522
3523    /// This clears out this `Vec` and recycles the allocation into a new `Vec`.
3524    /// The item type of the resulting `Vec` needs to have the same size and
3525    /// alignment as the item type of the original `Vec`.
3526    ///
3527    /// # Examples
3528    ///
3529    ///  ```
3530    /// #![feature(vec_recycle, transmutability)]
3531    /// let a: Vec<u8> = vec![0; 100];
3532    /// let capacity = a.capacity();
3533    /// let addr = a.as_ptr().addr();
3534    /// let b: Vec<i8> = a.recycle();
3535    /// assert_eq!(b.len(), 0);
3536    /// assert_eq!(b.capacity(), capacity);
3537    /// assert_eq!(b.as_ptr().addr(), addr);
3538    /// ```
3539    ///
3540    /// The `Recyclable` bound prevents this method from being called when `T` and `U` have different sizes; e.g.:
3541    ///
3542    ///  ```compile_fail,E0277
3543    /// #![feature(vec_recycle, transmutability)]
3544    /// let vec: Vec<[u8; 2]> = Vec::new();
3545    /// let _: Vec<[u8; 1]> = vec.recycle();
3546    /// ```
3547    /// ...or different alignments:
3548    ///
3549    ///  ```compile_fail,E0277
3550    /// #![feature(vec_recycle, transmutability)]
3551    /// let vec: Vec<[u16; 0]> = Vec::new();
3552    /// let _: Vec<[u8; 0]> = vec.recycle();
3553    /// ```
3554    ///
3555    /// However, due to temporary implementation limitations of `Recyclable`,
3556    /// this method is not yet callable when `T` or `U` are slices, trait objects,
3557    /// or other exotic types; e.g.:
3558    ///
3559    /// ```compile_fail,E0277
3560    /// #![feature(vec_recycle, transmutability)]
3561    /// # let inputs = ["a b c", "d e f"];
3562    /// # fn process(_: &[&str]) {}
3563    /// let mut storage: Vec<&[&str]> = Vec::new();
3564    ///
3565    /// for input in inputs {
3566    ///     let mut buffer: Vec<&str> = storage.recycle();
3567    ///     buffer.extend(input.split(" "));
3568    ///     process(&buffer);
3569    ///     storage = buffer.recycle();
3570    /// }
3571    /// ```
3572    #[unstable(feature = "vec_recycle", issue = "148227")]
3573    #[expect(private_bounds)]
3574    pub fn recycle<U>(mut self) -> Vec<U, A>
3575    where
3576        U: Recyclable<T>,
3577    {
3578        self.clear();
3579        const {
3580            // FIXME(const-hack, 146097): compare `Layout`s
3581            assert!(size_of::<T>() == size_of::<U>());
3582            assert!(align_of::<T>() == align_of::<U>());
3583        };
3584        let (ptr, length, capacity, alloc) = self.into_parts_with_allocator();
3585        debug_assert_eq!(length, 0);
3586        // SAFETY:
3587        // - `ptr` and `alloc` were just returned from `self.into_raw_parts_with_allocator()`
3588        // - `T` & `U` have the same layout, so `capacity` does not need to be changed and we can safely use `alloc.dealloc` later
3589        // - the original vector was cleared, so there is no problem with "transmuting" the stored values
3590        unsafe { Vec::from_parts_in(ptr.cast::<U>(), length, capacity, alloc) }
3591    }
3592}
3593
3594/// Denotes that an allocation of `From` can be recycled into an allocation of `Self`.
3595///
3596/// # Safety
3597///
3598/// `Self` is `Recyclable<From>` if `Layout::new::<Self>() == Layout::new::<From>()`.
3599unsafe trait Recyclable<From: Sized>: Sized {}
3600
3601#[unstable_feature_bound(transmutability)]
3602// SAFETY: enforced by `TransmuteFrom`
3603unsafe impl<From, To> Recyclable<From> for To
3604where
3605    for<'a> &'a MaybeUninit<To>: TransmuteFrom<&'a MaybeUninit<From>, { Assume::SAFETY }>,
3606    for<'a> &'a MaybeUninit<From>: TransmuteFrom<&'a MaybeUninit<To>, { Assume::SAFETY }>,
3607{
3608}
3609
3610impl<T: Clone> Vec<T, Global> {
3611    /// Create a new `Vec` that contains `elem` `n` times.
3612    ///
3613    /// This method requires `T` to implement [`Clone`],
3614    /// in order to be able to clone the passed value.
3615    ///
3616    /// If `n` is zero, the vector will not allocate.
3617    ///
3618    /// # Panics
3619    ///
3620    /// Panics if `size_of::<T>() * n` exceeds `isize::MAX` bytes.
3621    ///
3622    /// # Examples
3623    ///
3624    /// ```
3625    /// #![feature(vec_repeat)]
3626    /// let vec = Vec::repeat(0, 3);
3627    /// assert_eq!(vec, [0; 3]);
3628    /// ```
3629    #[cfg(not(no_global_oom_handling))]
3630    #[unstable(feature = "vec_repeat", issue = "164215")]
3631    #[inline]
3632    pub fn repeat(elem: T, n: usize) -> Self {
3633        <T as SpecFromElem>::from_elem(elem, n, Global)
3634    }
3635}
3636
3637impl<T: Clone, A: Allocator> Vec<T, A> {
3638    /// Create a new `Vec` with the provided allocator that contains `elem` `n` times.
3639    ///
3640    /// This method requires `T` to implement [`Clone`],
3641    /// in order to be able to clone the passed value.
3642    ///
3643    /// If `n` is zero, the vector will not allocate.
3644    ///
3645    /// # Panics
3646    ///
3647    /// Panics if `size_of::<T>() * n` exceeds `isize::MAX` bytes.
3648    ///
3649    /// # Examples
3650    ///
3651    /// ```
3652    /// #![feature(vec_repeat)]
3653    /// use std::alloc::System;
3654    ///
3655    /// let vec = Vec::repeat_in(0, 3, System);
3656    /// assert_eq!(vec, [0; 3]);
3657    /// ```
3658    #[cfg(not(no_global_oom_handling))]
3659    #[unstable(feature = "vec_repeat", issue = "164215")]
3660    #[inline]
3661    pub fn repeat_in(elem: T, n: usize, alloc: A) -> Self {
3662        <T as SpecFromElem>::from_elem(elem, n, alloc)
3663    }
3664
3665    /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
3666    ///
3667    /// If `new_len` is greater than `len`, the `Vec` is extended by the
3668    /// difference, with each additional slot filled with `value`.
3669    /// If `new_len` is less than or equal to `len`, the `Vec` is simply
3670    /// truncated.
3671    ///
3672    /// This method requires `T` to implement [`Clone`],
3673    /// in order to be able to clone the passed value.
3674    /// If you need more flexibility (or want to rely on [`Default`] instead of
3675    /// [`Clone`]), use [`Vec::resize_with`].
3676    /// If you only need to resize to a smaller size, use [`Vec::truncate`].
3677    ///
3678    /// # Panics
3679    ///
3680    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
3681    ///
3682    /// # Examples
3683    ///
3684    /// ```
3685    /// let mut vec = vec!["hello"];
3686    /// vec.resize(3, "world");
3687    /// assert_eq!(vec, ["hello", "world", "world"]);
3688    ///
3689    /// let mut vec = vec!['a', 'b', 'c', 'd'];
3690    /// vec.resize(2, '_');
3691    /// assert_eq!(vec, ['a', 'b']);
3692    /// ```
3693    #[cfg(not(no_global_oom_handling))]
3694    #[stable(feature = "vec_resize", since = "1.5.0")]
3695    pub fn resize(&mut self, new_len: usize, value: T) {
3696        let len = self.len();
3697
3698        if new_len > len {
3699            self.extend_with(new_len - len, value)
3700        } else {
3701            self.truncate(new_len);
3702        }
3703    }
3704
3705    /// Clones and appends all elements in a slice to the `Vec`.
3706    ///
3707    /// Iterates over the slice `other`, clones each element, and then appends
3708    /// it to this `Vec`. The `other` slice is traversed in-order.
3709    ///
3710    /// Note that this function is the same as [`extend`],
3711    /// except that it also works with slice elements that are Clone but not Copy.
3712    /// If Rust gets specialization this function may be deprecated.
3713    ///
3714    /// # Panics
3715    ///
3716    /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
3717    ///
3718    /// # Examples
3719    ///
3720    /// ```
3721    /// let mut vec = vec![1];
3722    /// vec.extend_from_slice(&[2, 3, 4]);
3723    /// assert_eq!(vec, [1, 2, 3, 4]);
3724    /// ```
3725    ///
3726    /// [`extend`]: Vec::extend
3727    #[cfg(not(no_global_oom_handling))]
3728    #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
3729    pub fn extend_from_slice(&mut self, other: &[T]) {
3730        self.spec_extend(other.iter())
3731    }
3732
3733    /// Given a range `src`, clones a slice of elements in that range and appends it to the end.
3734    ///
3735    /// `src` must be a range that can form a valid subslice of the `Vec`.
3736    ///
3737    /// # Panics
3738    ///
3739    /// Panics if starting index is greater than the end index, if the index is
3740    /// greater than the length of the vector, or if the new capacity exceeds
3741    /// `isize::MAX` _bytes_.
3742    ///
3743    /// # Examples
3744    ///
3745    /// ```
3746    /// let mut characters = vec!['a', 'b', 'c', 'd', 'e'];
3747    /// characters.extend_from_within(2..);
3748    /// assert_eq!(characters, ['a', 'b', 'c', 'd', 'e', 'c', 'd', 'e']);
3749    ///
3750    /// let mut numbers = vec![0, 1, 2, 3, 4];
3751    /// numbers.extend_from_within(..2);
3752    /// assert_eq!(numbers, [0, 1, 2, 3, 4, 0, 1]);
3753    ///
3754    /// let mut strings = vec![String::from("hello"), String::from("world"), String::from("!")];
3755    /// strings.extend_from_within(1..=2);
3756    /// assert_eq!(strings, ["hello", "world", "!", "world", "!"]);
3757    /// ```
3758    #[cfg(not(no_global_oom_handling))]
3759    #[stable(feature = "vec_extend_from_within", since = "1.53.0")]
3760    pub fn extend_from_within<R>(&mut self, src: R)
3761    where
3762        R: RangeBounds<usize>,
3763    {
3764        let range = slice::range(src, ..self.len());
3765        self.reserve(range.len());
3766
3767        // SAFETY:
3768        // - `slice::range` guarantees that the given range is valid for indexing self
3769        unsafe {
3770            self.spec_extend_from_within(range);
3771        }
3772    }
3773}
3774
3775impl<A: Allocator> Vec<u8, A> {
3776    #[cfg_attr(
3777        not(no_global_oom_handling),
3778        expect(
3779            dead_code,
3780            reason = "currently only used in IO module when global OOM handling is disabled"
3781        )
3782    )]
3783    pub(crate) fn try_extend_from_slice_of_bytes(
3784        &mut self,
3785        other: &[u8],
3786    ) -> Result<(), TryReserveError> {
3787        // ignore-tidy-undocumented-unsafe
3788        unsafe { self.try_append_elements(other) }
3789    }
3790}
3791
3792impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
3793    /// Takes a `Vec<[T; N]>` and flattens it into a `Vec<T>`.
3794    ///
3795    /// # Panics
3796    ///
3797    /// Panics if the length of the resulting vector would overflow a `usize`.
3798    ///
3799    /// This is only possible when flattening a vector of arrays of zero-sized
3800    /// types, and thus tends to be irrelevant in practice. If
3801    /// `size_of::<T>() > 0`, this will never panic.
3802    ///
3803    /// # Examples
3804    ///
3805    /// ```
3806    /// let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
3807    /// assert_eq!(vec.pop(), Some([7, 8, 9]));
3808    ///
3809    /// let mut flattened = vec.into_flattened();
3810    /// assert_eq!(flattened.pop(), Some(6));
3811    /// ```
3812    #[stable(feature = "slice_flatten", since = "1.80.0")]
3813    pub fn into_flattened(self) -> Vec<T, A> {
3814        let (ptr, len, cap, alloc) = self.into_raw_parts_with_allocator();
3815        let (new_len, new_cap) = if T::IS_ZST {
3816            (
3817                len.checked_mul(N).expect("the product of vec len and N shouldn't overflow"),
3818                usize::MAX,
3819            )
3820        } else {
3821            // SAFETY:
3822            // - `cap * N` cannot overflow because the allocation is already in
3823            // the address space.
3824            // - Each `[T; N]` has `N` valid elements, so there are `len * N`
3825            // valid elements in the allocation.
3826            unsafe { (len.unchecked_mul(N), cap.unchecked_mul(N)) }
3827        };
3828        // SAFETY:
3829        // - `ptr` was allocated by `self`
3830        // - `ptr` is well-aligned because `[T; N]` has the same alignment as `T`.
3831        // - `new_cap` refers to the same sized allocation as `cap` because
3832        // `new_cap * size_of::<T>()` == `cap * size_of::<[T; N]>()`
3833        // - `len` <= `cap`, so `len * N` <= `cap * N`.
3834        unsafe { Vec::<T, A>::from_raw_parts_in(ptr.cast(), new_len, new_cap, alloc) }
3835    }
3836}
3837
3838impl<T: Clone, A: Allocator> Vec<T, A> {
3839    #[cfg(not(no_global_oom_handling))]
3840    /// Extend the vector by `n` clones of value.
3841    fn extend_with(&mut self, n: usize, value: T) {
3842        self.spec_extend_with(n, value);
3843    }
3844}
3845
3846impl<T: PartialEq, A: Allocator> Vec<T, A> {
3847    /// Removes consecutive repeated elements in the vector according to the
3848    /// [`PartialEq`] trait implementation.
3849    ///
3850    /// If the vector is sorted, this removes all duplicates.
3851    ///
3852    /// # Examples
3853    ///
3854    /// ```
3855    /// let mut vec = vec![1, 2, 2, 3, 2];
3856    ///
3857    /// vec.dedup();
3858    ///
3859    /// assert_eq!(vec, [1, 2, 3, 2]);
3860    /// ```
3861    #[stable(feature = "rust1", since = "1.0.0")]
3862    #[inline]
3863    pub fn dedup(&mut self) {
3864        // Vectorize the process of finding first duplicate if possible
3865        if let Some(chunk_size) = dedup_simd_chunk_size::<T>() {
3866            // Unlike dedup_by, we don't guarantee the order
3867            // and time in which we call `PartialEq::eq`.
3868            let Some(first_duplicate) = find_first_duplicate(self.as_slice(), chunk_size) else {
3869                return;
3870            };
3871
3872            // SAFETY: `1 <= first_duplicate < self.len()`
3873            unsafe {
3874                self.dedup_tail(|a, b| a == b, first_duplicate);
3875            }
3876        } else {
3877            self.dedup_by(|a, b| a == b);
3878        }
3879    }
3880}
3881
3882const fn dedup_simd_chunk_size<T>() -> Option<usize> {
3883    // The minimal SIMD width on supported platforms
3884    #[allow(unused)]
3885    const SIMD_WIDTH: usize = 16;
3886    let size = size_of::<T>();
3887
3888    // We only have SIMD implementations for these element sizes.
3889    if !matches!(size, 1 | 2 | 4 | 8) {
3890        return None;
3891    }
3892
3893    let simd_width: Option<usize> = cfg_select! {
3894        all(target_arch = "arm", target_feature = "neon") => {
3895            // Packed 64-bit integer lane equality is unavailable on arm neon
3896            if size == 8 { None } else { Some(SIMD_WIDTH) }
3897        }
3898
3899        all(target_arch = "aarch64", target_feature = "neon") => Some(SIMD_WIDTH),
3900
3901        all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "sse4.1") => {
3902            Some(SIMD_WIDTH)
3903        }
3904
3905        all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "sse2") => {
3906            // Packed 64-bit integer lane equality is only available on sse4.1
3907            if size == 8 { None } else { Some(SIMD_WIDTH) }
3908        }
3909
3910        all(any(target_arch = "riscv32", target_arch = "riscv64"), target_feature = "v") => {
3911            Some(SIMD_WIDTH)
3912        }
3913
3914        all(any(target_arch = "loongarch32", target_arch = "loongarch64"), target_feature = "lsx") => {
3915            Some(SIMD_WIDTH)
3916        }
3917
3918        _ => None,
3919    };
3920
3921    if let Some(simd_width) = simd_width { Some(simd_width * 2 / size) } else { None }
3922}
3923
3924fn find_first_duplicate<T: PartialEq>(v: &[T], chunk_size: usize) -> Option<usize> {
3925    let len = v.len();
3926    if len <= 1 {
3927        return None;
3928    }
3929
3930    let mut i = 1;
3931
3932    // The scalar fallback path if the length is not long enough
3933    if len < chunk_size + 1 {
3934        while i < len {
3935            // It keeps the same comparison order as `dedup_tail`
3936            //
3937            // SAFETY: i always in range [1..len)
3938            if unsafe { v.get_unchecked(i) == v.get_unchecked(i - 1) } {
3939                return Some(i);
3940            }
3941            i += 1;
3942        }
3943        return None;
3944    }
3945
3946    /// # Safety
3947    /// - `start > 0` and `start + chunk_size <= v.len()`
3948    /// - `0 < chunk_size <= 32`
3949    #[inline(always)]
3950    unsafe fn find_duplicate<T: PartialEq>(
3951        v: &[T],
3952        start: usize,
3953        chunk_size: usize,
3954    ) -> Option<usize> {
3955        let mut mask: u32 = 0;
3956        debug_assert!(
3957            u32::BITS as usize >= chunk_size,
3958            "the bit width of mask must be greater than or equal to chunk_size"
3959        );
3960        for j in 0..chunk_size {
3961            // SAFETY: start + j always in range [1..v.len())
3962            let eq = unsafe { v.get_unchecked(start + j) == v.get_unchecked(start + j - 1) };
3963            mask |= (eq as u32) << j;
3964        }
3965        if mask != 0 {
3966            return Some(start + mask.trailing_zeros() as usize);
3967        }
3968        None
3969    }
3970
3971    // This loop performs chunk_size comparisons in parallel without early exit,
3972    // which is what allows for SIMD optimization.
3973    while i + chunk_size <= len {
3974        // SAFETY: `i >= 1` and `i + chunk_size <= len`
3975        if let Some(duplicate) = unsafe { find_duplicate(v, i, chunk_size) } {
3976            return Some(duplicate);
3977        }
3978        i += chunk_size;
3979    }
3980
3981    // This may check the same elements multiple times.
3982    // However we don't guarantee `PartialEq::eq` is only called once per pair.
3983    if i < len {
3984        let start = len - chunk_size;
3985        // SAFETY: `len - chunk_size >= 1` and `start + chunk_size <= len`
3986        if let Some(duplicate) = unsafe { find_duplicate(v, start, chunk_size) } {
3987            return Some(duplicate);
3988        }
3989    }
3990
3991    None
3992}
3993
3994////////////////////////////////////////////////////////////////////////////////
3995// Internal methods and functions
3996////////////////////////////////////////////////////////////////////////////////
3997
3998// This function is no longer used internally (`from_elem_global` is used instead).
3999// It is only kept so as not to break a few crates who mistakenly used it at a
4000// time when we didn't have the ability to gate internal methods used by public macros.
4001#[doc(hidden)]
4002#[cfg(not(no_global_oom_handling))]
4003#[stable(feature = "rust1", since = "1.0.0")]
4004// NOTE: the real deprecation version is the same as the stabilization version.
4005// I.e. it should never have been used even in version 1.0.
4006#[deprecated(since = "1.101.0", note = "use the `vec!` macro instead")]
4007pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
4008    vec![elem; n]
4009}
4010
4011// This function is required because it ensures the `vec_from_elem` diagnostic
4012// item is emitted, which is consumed by Clippy to detect calls to
4013// `vec![elem; n]`. We cannot add the item to `Vec::repeat` because then we
4014// would end up confusing Clippy.
4015#[doc(hidden)]
4016#[cfg(not(no_global_oom_handling))]
4017#[unstable(feature = "liballoc_internals", issue = "none")]
4018#[rustc_diagnostic_item = "vec_from_elem"]
4019pub fn from_elem_global<T: Clone>(elem: T, n: usize) -> Vec<T> {
4020    Vec::repeat(elem, n)
4021}
4022
4023#[cfg(not(no_global_oom_handling))]
4024trait ExtendFromWithinSpec {
4025    /// # Safety
4026    ///
4027    /// - `src` needs to be valid index
4028    /// - `self.capacity() - self.len()` must be `>= src.len()`
4029    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
4030}
4031
4032#[cfg(not(no_global_oom_handling))]
4033impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
4034    default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
4035        // SAFETY:
4036        // - len is increased only after initializing elements
4037        let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() };
4038
4039        // SAFETY:
4040        // - caller guarantees that src is a valid index
4041        let to_clone = unsafe { this.get_unchecked(src) };
4042
4043        iter::zip(to_clone, spare)
4044            .map(|(src, dst)| dst.write(src.clone()))
4045            // Note:
4046            // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len
4047            // - len is increased after each element to prevent leaks (see issue #82533)
4048            .for_each(|_| *len += 1);
4049    }
4050}
4051
4052#[cfg(not(no_global_oom_handling))]
4053impl<T: TrivialClone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
4054    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
4055        let count = src.len();
4056        {
4057            let (init, spare) = self.split_at_spare_mut();
4058
4059            // SAFETY:
4060            // - caller guarantees that `src` is a valid index
4061            let source = unsafe { init.get_unchecked(src) };
4062
4063            // SAFETY:
4064            // - Both pointers are created from unique slice references (`&mut [_]`)
4065            //   so they are valid and do not overlap.
4066            // - Elements implement `TrivialClone` so this is equivalent to calling
4067            //   `clone` on every one of them.
4068            // - `count` is equal to the len of `source`, so source is valid for
4069            //   `count` reads
4070            // - `.reserve(count)` guarantees that `spare.len() >= count` so spare
4071            //   is valid for `count` writes
4072            unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) };
4073        }
4074
4075        // SAFETY:
4076        // - The elements were just initialized by `copy_nonoverlapping`
4077        self.len += count;
4078    }
4079}
4080
4081////////////////////////////////////////////////////////////////////////////////
4082// Common trait implementations for Vec
4083////////////////////////////////////////////////////////////////////////////////
4084
4085#[stable(feature = "rust1", since = "1.0.0")]
4086#[rustc_const_unstable(feature = "const_convert", issue = "143773")]
4087const impl<T, A: Allocator> ops::Deref for Vec<T, A> {
4088    type Target = [T];
4089
4090    #[inline]
4091    fn deref(&self) -> &[T] {
4092        self.as_slice()
4093    }
4094}
4095
4096#[stable(feature = "rust1", since = "1.0.0")]
4097#[rustc_const_unstable(feature = "const_convert", issue = "143773")]
4098const impl<T, A: Allocator> ops::DerefMut for Vec<T, A> {
4099    #[inline]
4100    fn deref_mut(&mut self) -> &mut [T] {
4101        self.as_mut_slice()
4102    }
4103}
4104
4105#[unstable(feature = "deref_pure_trait", issue = "87121")]
4106unsafe impl<T, A: Allocator> ops::DerefPure for Vec<T, A> {}
4107
4108#[cfg(not(no_global_oom_handling))]
4109#[stable(feature = "rust1", since = "1.0.0")]
4110impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
4111    /// Creates a new `Vec` by deep-copying the contents of an existing `Vec`.
4112    ///
4113    /// This method will allocate a new `Vec` and `clone` all of `self`'s contents
4114    /// into it. The capacity of the duplicate `Vec` is not forced to match the
4115    /// capacity of the original.
4116    fn clone(&self) -> Self {
4117        let alloc = self.allocator().clone();
4118        <[T]>::to_vec_in(self, alloc)
4119    }
4120
4121    /// Overwrites the contents of `self` with a clone of the contents of `source`.
4122    ///
4123    /// This method is preferred over simply assigning `source.clone()` to `self`,
4124    /// as it avoids reallocation if possible. Additionally, if the element type
4125    /// `T` overrides `clone_from()`, this will reuse the resources of `self`'s
4126    /// elements as well.
4127    ///
4128    /// # Examples
4129    ///
4130    /// ```
4131    /// let x = vec![5, 6, 7];
4132    /// let mut y = vec![8, 9, 10];
4133    /// let yp: *const i32 = y.as_ptr();
4134    ///
4135    /// y.clone_from(&x);
4136    ///
4137    /// // The value is the same
4138    /// assert_eq!(x, y);
4139    ///
4140    /// // And no reallocation occurred
4141    /// assert_eq!(yp, y.as_ptr());
4142    /// ```
4143    fn clone_from(&mut self, source: &Self) {
4144        crate::slice::SpecCloneIntoVec::clone_into(source.as_slice(), self);
4145    }
4146}
4147
4148/// The hash of a vector is the same as that of the corresponding slice,
4149/// as required by the `core::borrow::Borrow` implementation.
4150///
4151/// ```
4152/// use std::hash::BuildHasher;
4153///
4154/// let b = std::hash::RandomState::new();
4155/// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09];
4156/// let s: &[u8] = &[0xa8, 0x3c, 0x09];
4157/// assert_eq!(b.hash_one(v), b.hash_one(s));
4158/// ```
4159#[stable(feature = "rust1", since = "1.0.0")]
4160impl<T: Hash, A: Allocator> Hash for Vec<T, A> {
4161    #[inline]
4162    fn hash<H: Hasher>(&self, state: &mut H) {
4163        Hash::hash(&**self, state)
4164    }
4165}
4166
4167#[stable(feature = "rust1", since = "1.0.0")]
4168#[rustc_const_unstable(feature = "const_index", issue = "143775")]
4169const impl<T, I: [const] SliceIndex<[T]>, A: Allocator> Index<I> for Vec<T, A> {
4170    type Output = I::Output;
4171
4172    #[inline]
4173    fn index(&self, index: I) -> &Self::Output {
4174        Index::index(&**self, index)
4175    }
4176}
4177
4178#[stable(feature = "rust1", since = "1.0.0")]
4179#[rustc_const_unstable(feature = "const_index", issue = "143775")]
4180const impl<T, I: [const] SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> {
4181    #[inline]
4182    fn index_mut(&mut self, index: I) -> &mut Self::Output {
4183        IndexMut::index_mut(&mut **self, index)
4184    }
4185}
4186
4187/// Collects an iterator into a Vec, commonly called via [`Iterator::collect()`]
4188///
4189/// # Allocation behavior
4190///
4191/// In general `Vec` does not guarantee any particular growth or allocation strategy.
4192/// That also applies to this trait impl.
4193///
4194/// **Note:** This section covers implementation details and is therefore exempt from
4195/// stability guarantees.
4196///
4197/// Vec may use any or none of the following strategies,
4198/// depending on the supplied iterator:
4199///
4200/// * preallocate based on [`Iterator::size_hint()`]
4201///   * and panic if the number of items is outside the provided lower/upper bounds
4202/// * use an amortized growth strategy similar to `pushing` one item at a time
4203/// * perform the iteration in-place on the original allocation backing the iterator
4204///
4205/// The last case warrants some attention. It is an optimization that in many cases reduces peak memory
4206/// consumption and improves cache locality. But when big, short-lived allocations are created,
4207/// only a small fraction of their items get collected, no further use is made of the spare capacity
4208/// and the resulting `Vec` is moved into a longer-lived structure, then this can lead to the large
4209/// allocations having their lifetimes unnecessarily extended which can result in increased memory
4210/// footprint.
4211///
4212/// In cases where this is an issue, the excess capacity can be discarded with [`Vec::shrink_to()`],
4213/// [`Vec::shrink_to_fit()`] or by collecting into [`Box<[T]>`][owned slice] instead, which additionally reduces
4214/// the size of the long-lived struct.
4215///
4216/// [owned slice]: Box
4217///
4218/// ```rust
4219/// # use std::sync::Mutex;
4220/// static LONG_LIVED: Mutex<Vec<Vec<u16>>> = Mutex::new(Vec::new());
4221///
4222/// for i in 0..10 {
4223///     let big_temporary: Vec<u16> = (0..1024).collect();
4224///     // discard most items
4225///     let mut result: Vec<_> = big_temporary.into_iter().filter(|i| i % 100 == 0).collect();
4226///     // without this a lot of unused capacity might be moved into the global
4227///     result.shrink_to_fit();
4228///     LONG_LIVED.lock().unwrap().push(result);
4229/// }
4230/// ```
4231#[cfg(not(no_global_oom_handling))]
4232#[stable(feature = "rust1", since = "1.0.0")]
4233impl<T> FromIterator<T> for Vec<T> {
4234    #[inline]
4235    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
4236        <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter())
4237    }
4238}
4239
4240#[stable(feature = "rust1", since = "1.0.0")]
4241impl<T, A: Allocator> IntoIterator for Vec<T, A> {
4242    type Item = T;
4243    type IntoIter = IntoIter<T, A>;
4244
4245    /// Creates a consuming iterator, that is, one that moves each value out of
4246    /// the vector (from start to end). The vector cannot be used after calling
4247    /// this.
4248    ///
4249    /// # Examples
4250    ///
4251    /// ```
4252    /// let v = vec!["a".to_string(), "b".to_string()];
4253    /// let mut v_iter = v.into_iter();
4254    ///
4255    /// let first_element: Option<String> = v_iter.next();
4256    ///
4257    /// assert_eq!(first_element, Some("a".to_string()));
4258    /// assert_eq!(v_iter.next(), Some("b".to_string()));
4259    /// assert_eq!(v_iter.next(), None);
4260    /// ```
4261    #[inline]
4262    fn into_iter(self) -> Self::IntoIter {
4263        let me = ManuallyDrop::new(self);
4264        // ignore-tidy-undocumented-unsafe
4265        unsafe {
4266            let alloc = ManuallyDrop::new(ptr::read(me.allocator()));
4267            let buf = me.buf.non_null();
4268            let begin = buf.as_ptr();
4269            let end = if T::IS_ZST {
4270                begin.wrapping_byte_add(me.len())
4271            } else {
4272                begin.add(me.len()) as *const T
4273            };
4274            let cap = me.buf.capacity();
4275            IntoIter { buf, phantom: PhantomData, cap, alloc, ptr: buf, end }
4276        }
4277    }
4278}
4279
4280#[stable(feature = "rust1", since = "1.0.0")]
4281impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> {
4282    type Item = &'a T;
4283    type IntoIter = slice::Iter<'a, T>;
4284
4285    fn into_iter(self) -> Self::IntoIter {
4286        self.iter()
4287    }
4288}
4289
4290#[stable(feature = "rust1", since = "1.0.0")]
4291impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> {
4292    type Item = &'a mut T;
4293    type IntoIter = slice::IterMut<'a, T>;
4294
4295    fn into_iter(self) -> Self::IntoIter {
4296        self.iter_mut()
4297    }
4298}
4299
4300#[cfg(not(no_global_oom_handling))]
4301#[stable(feature = "rust1", since = "1.0.0")]
4302impl<T, A: Allocator> Extend<T> for Vec<T, A> {
4303    #[inline]
4304    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
4305        <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
4306    }
4307
4308    #[inline]
4309    fn extend_one(&mut self, item: T) {
4310        self.push(item);
4311    }
4312
4313    #[inline]
4314    fn extend_reserve(&mut self, additional: usize) {
4315        self.reserve(additional);
4316    }
4317
4318    #[inline]
4319    unsafe fn extend_one_unchecked(&mut self, item: T) {
4320        // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
4321        unsafe {
4322            let len = self.len();
4323            ptr::write(self.as_mut_ptr().add(len), item);
4324            self.set_len(len + 1);
4325        }
4326    }
4327}
4328
4329impl<T, A: Allocator> Vec<T, A> {
4330    // leaf method to which various SpecFrom/SpecExtend implementations delegate when
4331    // they have no further optimizations to apply
4332    #[cfg(not(no_global_oom_handling))]
4333    fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
4334        // This is the case for a general iterator.
4335        //
4336        // This function should be the moral equivalent of:
4337        //
4338        //      for item in iterator {
4339        //          self.push(item);
4340        //      }
4341        while let Some(element) = iterator.next() {
4342            let len = self.len();
4343            if len == self.capacity() {
4344                let (lower, _) = iterator.size_hint();
4345                self.reserve(lower.saturating_add(1));
4346            }
4347            // ignore-tidy-undocumented-unsafe
4348            unsafe {
4349                ptr::write(self.as_mut_ptr().add(len), element);
4350                // Since next() executes user code which can panic we have to bump the length
4351                // after each step.
4352                // NB can't overflow since we would have had to alloc the address space
4353                self.set_len(len + 1);
4354            }
4355        }
4356    }
4357
4358    // specific extend for `TrustedLen` iterators, called both by the specializations
4359    // and internal places where resolving specialization makes compilation slower
4360    #[cfg(not(no_global_oom_handling))]
4361    fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
4362        let (low, high) = iterator.size_hint();
4363        if let Some(additional) = high {
4364            debug_assert_eq!(
4365                low,
4366                additional,
4367                "TrustedLen iterator's size hint is not exact: {:?}",
4368                (low, high)
4369            );
4370            self.reserve(additional);
4371            let ptr = self.as_mut_ptr();
4372            let mut local_len = SetLenOnDrop::new(&mut self.len);
4373            // ignore-tidy-undocumented-unsafe
4374            unsafe {
4375                iterator.for_each(move |element| {
4376                    ptr::write(ptr.add(local_len.current_len()), element);
4377                    // Since the loop executes user code which can panic we have to update
4378                    // the length every step to correctly drop what we've written.
4379                    // NB can't overflow since we would have had to alloc the address space
4380                    local_len.increment_len(1);
4381                });
4382            }
4383        } else {
4384            // Per TrustedLen contract a `None` upper bound means that the iterator length
4385            // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway.
4386            // Since the other branch already panics eagerly (via `reserve()`) we do the same here.
4387            // This avoids additional codegen for a fallback code path which would eventually
4388            // panic anyway.
4389            panic!("capacity overflow");
4390        }
4391    }
4392
4393    /// Creates a splicing iterator that replaces the specified range in the vector
4394    /// with the given `replace_with` iterator and yields the removed items.
4395    /// `replace_with` does not need to be the same length as `range`.
4396    ///
4397    /// `range` is removed even if the `Splice` iterator is not consumed before it is dropped.
4398    ///
4399    /// It is unspecified how many elements are removed from the vector
4400    /// if the `Splice` value is leaked.
4401    ///
4402    /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
4403    ///
4404    /// This is optimal if:
4405    ///
4406    /// * The tail (elements in the vector after `range`) is empty,
4407    /// * or `replace_with` yields fewer or equal elements than `range`'s length
4408    /// * or the lower bound of its `size_hint()` is exact.
4409    ///
4410    /// Otherwise, a temporary vector is allocated and the tail is moved twice.
4411    ///
4412    /// # Panics
4413    ///
4414    /// Panics if the range has `start_bound > end_bound`, or, if the range is
4415    /// bounded on either end and past the length of the vector.
4416    ///
4417    /// # Examples
4418    ///
4419    /// ```
4420    /// let mut v = vec![1, 2, 3, 4];
4421    /// let new = [7, 8, 9];
4422    /// let u: Vec<_> = v.splice(1..3, new).collect();
4423    /// assert_eq!(v, [1, 7, 8, 9, 4]);
4424    /// assert_eq!(u, [2, 3]);
4425    /// ```
4426    ///
4427    /// Using `splice` to insert new items into a vector efficiently at a specific position
4428    /// indicated by an empty range:
4429    ///
4430    /// ```
4431    /// let mut v = vec![1, 5];
4432    /// let new = [2, 3, 4];
4433    /// v.splice(1..1, new);
4434    /// assert_eq!(v, [1, 2, 3, 4, 5]);
4435    /// ```
4436    #[cfg(not(no_global_oom_handling))]
4437    #[inline]
4438    #[stable(feature = "vec_splice", since = "1.21.0")]
4439    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
4440    where
4441        A: AllocatorNightly,
4442        R: RangeBounds<usize>,
4443        I: IntoIterator<Item = T>,
4444    {
4445        Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
4446    }
4447
4448    /// Creates an iterator which uses a closure to determine if an element in the range should be removed.
4449    ///
4450    /// If the closure returns `true`, the element is removed from the vector
4451    /// and yielded. If the closure returns `false`, or panics, the element
4452    /// remains in the vector and will not be yielded.
4453    ///
4454    /// Only elements that fall in the provided range are considered for extraction, but any elements
4455    /// after the range will still have to be moved if any element has been extracted.
4456    ///
4457    /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
4458    /// or the iteration short-circuits, then the remaining elements will be retained.
4459    /// Use `extract_if().for_each(drop)` if you do not need the returned iterator,
4460    /// or [`retain_mut`] with a negated predicate if you also do not need to restrict the range.
4461    ///
4462    /// [`retain_mut`]: Vec::retain_mut
4463    ///
4464    /// Using this method is equivalent to the following code:
4465    ///
4466    /// ```
4467    /// # let some_predicate = |x: &mut i32| { *x % 2 == 1 };
4468    /// # let mut vec = vec![0, 1, 2, 3, 4, 5, 6];
4469    /// # let mut vec2 = vec.clone();
4470    /// # let range = 1..5;
4471    /// let mut i = range.start;
4472    /// let end_items = vec.len() - range.end;
4473    /// # let mut extracted = vec![];
4474    ///
4475    /// while i < vec.len() - end_items {
4476    ///     if some_predicate(&mut vec[i]) {
4477    ///         let val = vec.remove(i);
4478    ///         // your code here
4479    /// #         extracted.push(val);
4480    ///     } else {
4481    ///         i += 1;
4482    ///     }
4483    /// }
4484    ///
4485    /// # let extracted2: Vec<_> = vec2.extract_if(range, some_predicate).collect();
4486    /// # assert_eq!(vec, vec2);
4487    /// # assert_eq!(extracted, extracted2);
4488    /// ```
4489    ///
4490    /// But `extract_if` is easier to use. `extract_if` is also more efficient,
4491    /// because it can backshift the elements of the array in bulk.
4492    ///
4493    /// The iterator also lets you mutate the value of each element in the
4494    /// closure, regardless of whether you choose to keep or remove it.
4495    ///
4496    /// # Panics
4497    ///
4498    /// If `range` is out of bounds.
4499    ///
4500    /// # Examples
4501    ///
4502    /// Splitting a vector into even and odd values, reusing the original vector:
4503    ///
4504    /// ```
4505    /// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];
4506    ///
4507    /// let evens = numbers.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
4508    /// let odds = numbers;
4509    ///
4510    /// assert_eq!(evens, vec![2, 4, 6, 8, 14]);
4511    /// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]);
4512    /// ```
4513    ///
4514    /// Using the range argument to only process a part of the vector:
4515    ///
4516    /// ```
4517    /// let mut items = vec![0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2];
4518    /// let ones = items.extract_if(7.., |x| *x == 1).collect::<Vec<_>>();
4519    /// assert_eq!(items, vec![0, 0, 0, 0, 0, 0, 0, 2, 2, 2]);
4520    /// assert_eq!(ones.len(), 3);
4521    /// ```
4522    #[stable(feature = "extract_if", since = "1.87.0")]
4523    pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, A>
4524    where
4525        A: AllocatorNightly,
4526        F: FnMut(&mut T) -> bool,
4527        R: RangeBounds<usize>,
4528    {
4529        ExtractIf::new(self, filter, range)
4530    }
4531}
4532
4533/// Extend implementation that copies elements out of references before pushing them onto the Vec.
4534///
4535/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
4536/// append the entire slice at once.
4537///
4538/// [`copy_from_slice`]: slice::copy_from_slice
4539#[cfg(not(no_global_oom_handling))]
4540#[stable(feature = "extend_ref", since = "1.2.0")]
4541impl<'a, T: Copy + 'a, A: Allocator> Extend<&'a T> for Vec<T, A> {
4542    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
4543        self.spec_extend(iter.into_iter())
4544    }
4545
4546    #[inline]
4547    fn extend_one(&mut self, &item: &'a T) {
4548        self.push(item);
4549    }
4550
4551    #[inline]
4552    fn extend_reserve(&mut self, additional: usize) {
4553        self.reserve(additional);
4554    }
4555
4556    #[inline]
4557    unsafe fn extend_one_unchecked(&mut self, &item: &'a T) {
4558        // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
4559        unsafe {
4560            let len = self.len();
4561            ptr::write(self.as_mut_ptr().add(len), item);
4562            self.set_len(len + 1);
4563        }
4564    }
4565}
4566
4567/// Implements comparison of vectors, [lexicographically](Ord#lexicographical-comparison).
4568#[stable(feature = "rust1", since = "1.0.0")]
4569impl<T, A1, A2> PartialOrd<Vec<T, A2>> for Vec<T, A1>
4570where
4571    T: PartialOrd,
4572    A1: Allocator,
4573    A2: Allocator,
4574{
4575    #[inline]
4576    fn partial_cmp(&self, other: &Vec<T, A2>) -> Option<Ordering> {
4577        PartialOrd::partial_cmp(&**self, &**other)
4578    }
4579}
4580
4581#[stable(feature = "rust1", since = "1.0.0")]
4582impl<T: Eq, A: Allocator> Eq for Vec<T, A> {}
4583
4584/// Implements ordering of vectors, [lexicographically](Ord#lexicographical-comparison).
4585#[stable(feature = "rust1", since = "1.0.0")]
4586impl<T: Ord, A: Allocator> Ord for Vec<T, A> {
4587    #[inline]
4588    fn cmp(&self, other: &Self) -> Ordering {
4589        Ord::cmp(&**self, &**other)
4590    }
4591}
4592
4593#[stable(feature = "rust1", since = "1.0.0")]
4594#[rustc_const_unstable(feature = "const_heap", issue = "79597")]
4595const unsafe impl<#[may_dangle] T: [const] Destruct, A: [const] Allocator + [const] Destruct> Drop
4596    for Vec<T, A>
4597{
4598    fn drop(&mut self) {
4599        // ignore-tidy-undocumented-unsafe
4600        unsafe {
4601            // use drop for [T]
4602            // use a raw slice to refer to the elements of the vector as weakest necessary type;
4603            // could avoid questions of validity in certain cases
4604            self.as_mut_ptr().cast_slice(self.len).drop_in_place()
4605        }
4606        // RawVec handles deallocation
4607    }
4608}
4609
4610#[stable(feature = "rust1", since = "1.0.0")]
4611#[rustc_const_unstable(feature = "const_default", issue = "143894")]
4612const impl<T> Default for Vec<T> {
4613    /// Creates an empty `Vec<T>`.
4614    ///
4615    /// The vector will not allocate until elements are pushed onto it.
4616    fn default() -> Vec<T> {
4617        Vec::new()
4618    }
4619}
4620
4621#[stable(feature = "rust1", since = "1.0.0")]
4622impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
4623    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4624        fmt::Debug::fmt(&**self, f)
4625    }
4626}
4627
4628#[stable(feature = "rust1", since = "1.0.0")]
4629impl<T, A: Allocator> AsRef<Vec<T, A>> for Vec<T, A> {
4630    fn as_ref(&self) -> &Vec<T, A> {
4631        self
4632    }
4633}
4634
4635#[stable(feature = "vec_as_mut", since = "1.5.0")]
4636impl<T, A: Allocator> AsMut<Vec<T, A>> for Vec<T, A> {
4637    fn as_mut(&mut self) -> &mut Vec<T, A> {
4638        self
4639    }
4640}
4641
4642#[stable(feature = "rust1", since = "1.0.0")]
4643impl<T, A: Allocator> AsRef<[T]> for Vec<T, A> {
4644    fn as_ref(&self) -> &[T] {
4645        self
4646    }
4647}
4648
4649#[stable(feature = "vec_as_mut", since = "1.5.0")]
4650impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> {
4651    fn as_mut(&mut self) -> &mut [T] {
4652        self
4653    }
4654}
4655
4656#[cfg(not(no_global_oom_handling))]
4657#[stable(feature = "rust1", since = "1.0.0")]
4658impl<T: Clone> From<&[T]> for Vec<T> {
4659    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4660    ///
4661    /// # Examples
4662    ///
4663    /// ```
4664    /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);
4665    /// ```
4666    fn from(s: &[T]) -> Vec<T> {
4667        s.to_vec()
4668    }
4669}
4670
4671#[cfg(not(no_global_oom_handling))]
4672#[stable(feature = "vec_from_mut", since = "1.19.0")]
4673impl<T: Clone> From<&mut [T]> for Vec<T> {
4674    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4675    ///
4676    /// # Examples
4677    ///
4678    /// ```
4679    /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]);
4680    /// ```
4681    fn from(s: &mut [T]) -> Vec<T> {
4682        s.to_vec()
4683    }
4684}
4685
4686#[cfg(not(no_global_oom_handling))]
4687#[stable(feature = "vec_from_array_ref", since = "1.74.0")]
4688impl<T: Clone, const N: usize> From<&[T; N]> for Vec<T> {
4689    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4690    ///
4691    /// # Examples
4692    ///
4693    /// ```
4694    /// assert_eq!(Vec::from(&[1, 2, 3]), vec![1, 2, 3]);
4695    /// ```
4696    fn from(s: &[T; N]) -> Vec<T> {
4697        Self::from(s.as_slice())
4698    }
4699}
4700
4701#[cfg(not(no_global_oom_handling))]
4702#[stable(feature = "vec_from_array_ref", since = "1.74.0")]
4703impl<T: Clone, const N: usize> From<&mut [T; N]> for Vec<T> {
4704    /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
4705    ///
4706    /// # Examples
4707    ///
4708    /// ```
4709    /// assert_eq!(Vec::from(&mut [1, 2, 3]), vec![1, 2, 3]);
4710    /// ```
4711    fn from(s: &mut [T; N]) -> Vec<T> {
4712        Self::from(s.as_mut_slice())
4713    }
4714}
4715
4716#[cfg(not(no_global_oom_handling))]
4717#[stable(feature = "vec_from_array", since = "1.44.0")]
4718impl<T, const N: usize> From<[T; N]> for Vec<T> {
4719    /// Allocates a `Vec<T>` and moves `s`'s items into it.
4720    ///
4721    /// # Examples
4722    ///
4723    /// ```
4724    /// assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]);
4725    /// ```
4726    fn from(s: [T; N]) -> Vec<T> {
4727        <[T]>::into_vec(Box::new(s))
4728    }
4729}
4730
4731#[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
4732impl<'a, T> From<Cow<'a, [T]>> for Vec<T>
4733where
4734    [T]: ToOwned<Owned = Vec<T>>,
4735{
4736    /// Converts a clone-on-write slice into a vector.
4737    ///
4738    /// If `s` already owns a `Vec<T>`, it will be returned directly.
4739    /// If `s` is borrowing a slice, a new `Vec<T>` will be allocated and
4740    /// filled by cloning `s`'s items into it.
4741    ///
4742    /// # Examples
4743    ///
4744    /// ```
4745    /// # use std::borrow::Cow;
4746    /// let o: Cow<'_, [i32]> = Cow::Owned(vec![1, 2, 3]);
4747    /// let b: Cow<'_, [i32]> = Cow::Borrowed(&[1, 2, 3]);
4748    /// assert_eq!(Vec::from(o), Vec::from(b));
4749    /// ```
4750    fn from(s: Cow<'a, [T]>) -> Vec<T> {
4751        s.into_owned()
4752    }
4753}
4754
4755#[stable(feature = "vec_from_box", since = "1.18.0")]
4756impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> {
4757    /// Converts a boxed slice into a vector by transferring ownership of
4758    /// the existing heap allocation.
4759    ///
4760    /// # Examples
4761    ///
4762    /// ```
4763    /// let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice();
4764    /// assert_eq!(Vec::from(b), vec![1, 2, 3]);
4765    /// ```
4766    fn from(s: Box<[T], A>) -> Self {
4767        s.into_vec()
4768    }
4769}
4770
4771#[cfg(not(no_global_oom_handling))]
4772#[stable(feature = "box_from_vec", since = "1.20.0")]
4773impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> {
4774    /// Converts a vector into a boxed slice.
4775    ///
4776    /// This is equivalent to [`Vec::into_boxed_slice`].
4777    ///
4778    /// # Examples
4779    ///
4780    /// ```
4781    /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice());
4782    /// ```
4783    fn from(v: Vec<T, A>) -> Self {
4784        v.into_boxed_slice()
4785    }
4786}
4787
4788#[cfg(not(no_global_oom_handling))]
4789#[stable(feature = "rust1", since = "1.0.0")]
4790impl From<&str> for Vec<u8> {
4791    /// Allocates a `Vec<u8>` and fills it with a UTF-8 string.
4792    ///
4793    /// # Examples
4794    ///
4795    /// ```
4796    /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);
4797    /// ```
4798    fn from(s: &str) -> Vec<u8> {
4799        From::from(s.as_bytes())
4800    }
4801}
4802
4803#[stable(feature = "array_try_from_vec", since = "1.48.0")]
4804#[rustc_const_unstable(feature = "const_convert", issue = "143773")]
4805const impl<T: [const] Destruct, A: [const] Allocator + [const] Destruct, const N: usize>
4806    TryFrom<Vec<T, A>> for [T; N]
4807{
4808    type Error = Vec<T, A>;
4809
4810    /// Gets the entire contents of the `Vec<T>` as an array,
4811    /// if its size exactly matches that of the requested array.
4812    ///
4813    /// # Examples
4814    ///
4815    /// ```
4816    /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3]));
4817    /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([]));
4818    /// ```
4819    ///
4820    /// If the length doesn't match, the input comes back in `Err`:
4821    /// ```
4822    /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into();
4823    /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
4824    /// ```
4825    ///
4826    /// If you're fine with just getting a prefix of the `Vec<T>`,
4827    /// you can call [`.truncate(N)`](Vec::truncate) first.
4828    /// ```
4829    /// let mut v = String::from("hello world").into_bytes();
4830    /// v.sort();
4831    /// v.truncate(2);
4832    /// let [a, b]: [_; 2] = v.try_into().unwrap();
4833    /// assert_eq!(a, b' ');
4834    /// assert_eq!(b, b'd');
4835    /// ```
4836    fn try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>> {
4837        if vec.len() != N {
4838            return Err(vec);
4839        }
4840
4841        // SAFETY: `.set_len(0)` is always sound.
4842        unsafe { vec.set_len(0) };
4843
4844        // SAFETY: A `Vec`'s pointer is always aligned properly, and
4845        // the alignment the array needs is the same as the items.
4846        // We checked earlier that we have sufficient items.
4847        // The items will not double-drop as the `set_len`
4848        // tells the `Vec` not to also drop them.
4849        let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) };
4850        Ok(array)
4851    }
4852}