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