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