Skip to main content

alloc/vec/
mod.rs

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