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