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