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};
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 unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } }
1062 }
1063
1064 #[doc(alias = "from_non_null_parts_in")]
1065 /// Creates a `Vec<T, A>` directly from a `NonNull` pointer, a length, a capacity,
1066 /// and an allocator.
1067 ///
1068 /// # Safety
1069 ///
1070 /// This is highly unsafe, due to the number of invariants that aren't
1071 /// checked:
1072 ///
1073 /// * `ptr` must be [*currently allocated*] via the given allocator `alloc`.
1074 /// * `T` needs to have the same alignment as what `ptr` was allocated with.
1075 /// (`T` having a less strict alignment is not sufficient, the alignment really
1076 /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be
1077 /// allocated and deallocated with the same layout.)
1078 /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs
1079 /// to be the same size as the pointer was allocated with. (Because similar to
1080 /// alignment, [`dealloc`] must be called with the same layout `size`.)
1081 /// * `length` needs to be less than or equal to `capacity`.
1082 /// * The first `length` values must be properly initialized values of type `T`.
1083 /// * `capacity` needs to [*fit*] the layout size that the pointer was allocated with.
1084 /// * The allocated size in bytes must be no larger than `isize::MAX`.
1085 /// See the safety documentation of [`pointer::offset`].
1086 ///
1087 /// These requirements are always upheld by any `ptr` that has been allocated
1088 /// via `Vec<T, A>`. Other allocation sources are allowed if the invariants are
1089 /// upheld.
1090 ///
1091 /// Violating these may cause problems like corrupting the allocator's
1092 /// internal data structures. For example it is **not** safe
1093 /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.
1094 /// It's also not safe to build one from a `Vec<u16>` and its length, because
1095 /// the allocator cares about the alignment, and these two types have different
1096 /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
1097 /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.
1098 ///
1099 /// The ownership of `ptr` is effectively transferred to the
1100 /// `Vec<T>` which may then deallocate, reallocate or change the
1101 /// contents of memory pointed to by the pointer at will. Ensure
1102 /// that nothing else uses the pointer after calling this
1103 /// function.
1104 ///
1105 /// [`String`]: crate::string::String
1106 /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
1107 /// [*currently allocated*]: crate::alloc::Allocator#currently-allocated-memory
1108 /// [*fit*]: crate::alloc::Allocator#memory-fitting
1109 ///
1110 /// # Examples
1111 ///
1112 /// ```
1113 /// #![feature(allocator_api, box_vec_non_null)]
1114 ///
1115 /// use std::alloc::System;
1116 ///
1117 /// use std::ptr::NonNull;
1118 /// use std::mem;
1119 ///
1120 /// let mut v = Vec::with_capacity_in(3, System);
1121 /// v.push(1);
1122 /// v.push(2);
1123 /// v.push(3);
1124 ///
1125 // FIXME Update this when vec_into_raw_parts is stabilized
1126 /// // Prevent running `v`'s destructor so we are in complete control
1127 /// // of the allocation.
1128 /// let mut v = mem::ManuallyDrop::new(v);
1129 ///
1130 /// // Pull out the various important pieces of information about `v`
1131 /// let p = unsafe { NonNull::new_unchecked(v.as_mut_ptr()) };
1132 /// let len = v.len();
1133 /// let cap = v.capacity();
1134 /// let alloc = v.allocator();
1135 ///
1136 /// unsafe {
1137 /// // Overwrite memory with 4, 5, 6
1138 /// for i in 0..len {
1139 /// p.add(i).write(4 + i);
1140 /// }
1141 ///
1142 /// // Put everything back together into a Vec
1143 /// let rebuilt = Vec::from_parts_in(p, len, cap, alloc.clone());
1144 /// assert_eq!(rebuilt, [4, 5, 6]);
1145 /// }
1146 /// ```
1147 ///
1148 /// Using memory that was allocated elsewhere:
1149 ///
1150 /// ```rust
1151 /// #![feature(allocator_api, box_vec_non_null)]
1152 ///
1153 /// use std::alloc::{AllocError, Allocator, Global, Layout};
1154 ///
1155 /// fn main() {
1156 /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
1157 ///
1158 /// let vec = unsafe {
1159 /// let mem = match Global.allocate(layout) {
1160 /// Ok(mem) => mem.cast::<u32>(),
1161 /// Err(AllocError) => return,
1162 /// };
1163 ///
1164 /// mem.write(1_000_000);
1165 ///
1166 /// Vec::from_parts_in(mem, 1, 16, Global)
1167 /// };
1168 ///
1169 /// assert_eq!(vec, &[1_000_000]);
1170 /// assert_eq!(vec.capacity(), 16);
1171 /// }
1172 /// ```
1173 #[inline]
1174 #[unstable(feature = "allocator_api", reason = "new API", issue = "32838")]
1175 // #[unstable(feature = "box_vec_non_null", issue = "130364")]
1176 pub unsafe fn from_parts_in(ptr: NonNull<T>, length: usize, capacity: usize, alloc: A) -> Self {
1177 unsafe { Vec { buf: RawVec::from_nonnull_in(ptr, capacity, alloc), len: length } }
1178 }
1179
1180 /// Decomposes a `Vec<T>` into its raw components: `(pointer, length, capacity, allocator)`.
1181 ///
1182 /// Returns the raw pointer to the underlying data, the length of the vector (in elements),
1183 /// the allocated capacity of the data (in elements), and the allocator. These are the same
1184 /// arguments in the same order as the arguments to [`from_raw_parts_in`].
1185 ///
1186 /// After calling this function, the caller is responsible for the
1187 /// memory previously managed by the `Vec`. The only way to do
1188 /// this is to convert the raw pointer, length, and capacity back
1189 /// into a `Vec` with the [`from_raw_parts_in`] function, allowing
1190 /// the destructor to perform the cleanup.
1191 ///
1192 /// [`from_raw_parts_in`]: Vec::from_raw_parts_in
1193 ///
1194 /// # Examples
1195 ///
1196 /// ```
1197 /// #![feature(allocator_api, vec_into_raw_parts)]
1198 ///
1199 /// use std::alloc::System;
1200 ///
1201 /// let mut v: Vec<i32, System> = Vec::new_in(System);
1202 /// v.push(-1);
1203 /// v.push(0);
1204 /// v.push(1);
1205 ///
1206 /// let (ptr, len, cap, alloc) = v.into_raw_parts_with_alloc();
1207 ///
1208 /// let rebuilt = unsafe {
1209 /// // We can now make changes to the components, such as
1210 /// // transmuting the raw pointer to a compatible type.
1211 /// let ptr = ptr as *mut u32;
1212 ///
1213 /// Vec::from_raw_parts_in(ptr, len, cap, alloc)
1214 /// };
1215 /// assert_eq!(rebuilt, [4294967295, 0, 1]);
1216 /// ```
1217 #[must_use = "losing the pointer will leak memory"]
1218 #[unstable(feature = "allocator_api", issue = "32838")]
1219 // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
1220 pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) {
1221 let mut me = ManuallyDrop::new(self);
1222 let len = me.len();
1223 let capacity = me.capacity();
1224 let ptr = me.as_mut_ptr();
1225 let alloc = unsafe { ptr::read(me.allocator()) };
1226 (ptr, len, capacity, alloc)
1227 }
1228
1229 #[doc(alias = "into_non_null_parts_with_alloc")]
1230 /// Decomposes a `Vec<T>` into its raw components: `(NonNull pointer, length, capacity, allocator)`.
1231 ///
1232 /// Returns the `NonNull` pointer to the underlying data, the length of the vector (in elements),
1233 /// the allocated capacity of the data (in elements), and the allocator. These are the same
1234 /// arguments in the same order as the arguments to [`from_parts_in`].
1235 ///
1236 /// After calling this function, the caller is responsible for the
1237 /// memory previously managed by the `Vec`. The only way to do
1238 /// this is to convert the `NonNull` pointer, length, and capacity back
1239 /// into a `Vec` with the [`from_parts_in`] function, allowing
1240 /// the destructor to perform the cleanup.
1241 ///
1242 /// [`from_parts_in`]: Vec::from_parts_in
1243 ///
1244 /// # Examples
1245 ///
1246 /// ```
1247 /// #![feature(allocator_api, vec_into_raw_parts, box_vec_non_null)]
1248 ///
1249 /// use std::alloc::System;
1250 ///
1251 /// let mut v: Vec<i32, System> = Vec::new_in(System);
1252 /// v.push(-1);
1253 /// v.push(0);
1254 /// v.push(1);
1255 ///
1256 /// let (ptr, len, cap, alloc) = v.into_parts_with_alloc();
1257 ///
1258 /// let rebuilt = unsafe {
1259 /// // We can now make changes to the components, such as
1260 /// // transmuting the raw pointer to a compatible type.
1261 /// let ptr = ptr.cast::<u32>();
1262 ///
1263 /// Vec::from_parts_in(ptr, len, cap, alloc)
1264 /// };
1265 /// assert_eq!(rebuilt, [4294967295, 0, 1]);
1266 /// ```
1267 #[must_use = "losing the pointer will leak memory"]
1268 #[unstable(feature = "allocator_api", issue = "32838")]
1269 // #[unstable(feature = "box_vec_non_null", reason = "new API", issue = "130364")]
1270 // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
1271 pub fn into_parts_with_alloc(self) -> (NonNull<T>, usize, usize, A) {
1272 let (ptr, len, capacity, alloc) = self.into_raw_parts_with_alloc();
1273 // SAFETY: A `Vec` always has a non-null pointer.
1274 (unsafe { NonNull::new_unchecked(ptr) }, len, capacity, alloc)
1275 }
1276
1277 /// Returns the total number of elements the vector can hold without
1278 /// reallocating.
1279 ///
1280 /// # Examples
1281 ///
1282 /// ```
1283 /// let mut vec: Vec<i32> = Vec::with_capacity(10);
1284 /// vec.push(42);
1285 /// assert!(vec.capacity() >= 10);
1286 /// ```
1287 ///
1288 /// A vector with zero-sized elements will always have a capacity of usize::MAX:
1289 ///
1290 /// ```
1291 /// #[derive(Clone)]
1292 /// struct ZeroSized;
1293 ///
1294 /// fn main() {
1295 /// assert_eq!(std::mem::size_of::<ZeroSized>(), 0);
1296 /// let v = vec![ZeroSized; 0];
1297 /// assert_eq!(v.capacity(), usize::MAX);
1298 /// }
1299 /// ```
1300 #[inline]
1301 #[stable(feature = "rust1", since = "1.0.0")]
1302 #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1303 pub const fn capacity(&self) -> usize {
1304 self.buf.capacity()
1305 }
1306
1307 /// Reserves capacity for at least `additional` more elements to be inserted
1308 /// in the given `Vec<T>`. The collection may reserve more space to
1309 /// speculatively avoid frequent reallocations. After calling `reserve`,
1310 /// capacity will be greater than or equal to `self.len() + additional`.
1311 /// Does nothing if capacity is already sufficient.
1312 ///
1313 /// # Panics
1314 ///
1315 /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
1316 ///
1317 /// # Examples
1318 ///
1319 /// ```
1320 /// let mut vec = vec![1];
1321 /// vec.reserve(10);
1322 /// assert!(vec.capacity() >= 11);
1323 /// ```
1324 #[cfg(not(no_global_oom_handling))]
1325 #[stable(feature = "rust1", since = "1.0.0")]
1326 #[track_caller]
1327 #[rustc_diagnostic_item = "vec_reserve"]
1328 pub fn reserve(&mut self, additional: usize) {
1329 self.buf.reserve(self.len, additional);
1330 }
1331
1332 /// Reserves the minimum capacity for at least `additional` more elements to
1333 /// be inserted in the given `Vec<T>`. Unlike [`reserve`], this will not
1334 /// deliberately over-allocate to speculatively avoid frequent allocations.
1335 /// After calling `reserve_exact`, capacity will be greater than or equal to
1336 /// `self.len() + additional`. Does nothing if the capacity is already
1337 /// sufficient.
1338 ///
1339 /// Note that the allocator may give the collection more space than it
1340 /// requests. Therefore, capacity can not be relied upon to be precisely
1341 /// minimal. Prefer [`reserve`] if future insertions are expected.
1342 ///
1343 /// [`reserve`]: Vec::reserve
1344 ///
1345 /// # Panics
1346 ///
1347 /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
1348 ///
1349 /// # Examples
1350 ///
1351 /// ```
1352 /// let mut vec = vec![1];
1353 /// vec.reserve_exact(10);
1354 /// assert!(vec.capacity() >= 11);
1355 /// ```
1356 #[cfg(not(no_global_oom_handling))]
1357 #[stable(feature = "rust1", since = "1.0.0")]
1358 #[track_caller]
1359 pub fn reserve_exact(&mut self, additional: usize) {
1360 self.buf.reserve_exact(self.len, additional);
1361 }
1362
1363 /// Tries to reserve capacity for at least `additional` more elements to be inserted
1364 /// in the given `Vec<T>`. The collection may reserve more space to speculatively avoid
1365 /// frequent reallocations. After calling `try_reserve`, capacity will be
1366 /// greater than or equal to `self.len() + additional` if it returns
1367 /// `Ok(())`. Does nothing if capacity is already sufficient. This method
1368 /// preserves the contents even if an error occurs.
1369 ///
1370 /// # Errors
1371 ///
1372 /// If the capacity overflows, or the allocator reports a failure, then an error
1373 /// is returned.
1374 ///
1375 /// # Examples
1376 ///
1377 /// ```
1378 /// use std::collections::TryReserveError;
1379 ///
1380 /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1381 /// let mut output = Vec::new();
1382 ///
1383 /// // Pre-reserve the memory, exiting if we can't
1384 /// output.try_reserve(data.len())?;
1385 ///
1386 /// // Now we know this can't OOM in the middle of our complex work
1387 /// output.extend(data.iter().map(|&val| {
1388 /// val * 2 + 5 // very complicated
1389 /// }));
1390 ///
1391 /// Ok(output)
1392 /// }
1393 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
1394 /// ```
1395 #[stable(feature = "try_reserve", since = "1.57.0")]
1396 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
1397 self.buf.try_reserve(self.len, additional)
1398 }
1399
1400 /// Tries to reserve the minimum capacity for at least `additional`
1401 /// elements to be inserted in the given `Vec<T>`. Unlike [`try_reserve`],
1402 /// this will not deliberately over-allocate to speculatively avoid frequent
1403 /// allocations. After calling `try_reserve_exact`, capacity will be greater
1404 /// than or equal to `self.len() + additional` if it returns `Ok(())`.
1405 /// Does nothing if the capacity is already sufficient.
1406 ///
1407 /// Note that the allocator may give the collection more space than it
1408 /// requests. Therefore, capacity can not be relied upon to be precisely
1409 /// minimal. Prefer [`try_reserve`] if future insertions are expected.
1410 ///
1411 /// [`try_reserve`]: Vec::try_reserve
1412 ///
1413 /// # Errors
1414 ///
1415 /// If the capacity overflows, or the allocator reports a failure, then an error
1416 /// is returned.
1417 ///
1418 /// # Examples
1419 ///
1420 /// ```
1421 /// use std::collections::TryReserveError;
1422 ///
1423 /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1424 /// let mut output = Vec::new();
1425 ///
1426 /// // Pre-reserve the memory, exiting if we can't
1427 /// output.try_reserve_exact(data.len())?;
1428 ///
1429 /// // Now we know this can't OOM in the middle of our complex work
1430 /// output.extend(data.iter().map(|&val| {
1431 /// val * 2 + 5 // very complicated
1432 /// }));
1433 ///
1434 /// Ok(output)
1435 /// }
1436 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
1437 /// ```
1438 #[stable(feature = "try_reserve", since = "1.57.0")]
1439 pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
1440 self.buf.try_reserve_exact(self.len, additional)
1441 }
1442
1443 /// Shrinks the capacity of the vector as much as possible.
1444 ///
1445 /// The behavior of this method depends on the allocator, which may either shrink the vector
1446 /// in-place or reallocate. The resulting vector might still have some excess capacity, just as
1447 /// is the case for [`with_capacity`]. See [`Allocator::shrink`] for more details.
1448 ///
1449 /// [`with_capacity`]: Vec::with_capacity
1450 ///
1451 /// # Examples
1452 ///
1453 /// ```
1454 /// let mut vec = Vec::with_capacity(10);
1455 /// vec.extend([1, 2, 3]);
1456 /// assert!(vec.capacity() >= 10);
1457 /// vec.shrink_to_fit();
1458 /// assert!(vec.capacity() >= 3);
1459 /// ```
1460 #[cfg(not(no_global_oom_handling))]
1461 #[stable(feature = "rust1", since = "1.0.0")]
1462 #[track_caller]
1463 #[inline]
1464 pub fn shrink_to_fit(&mut self) {
1465 // The capacity is never less than the length, and there's nothing to do when
1466 // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit`
1467 // by only calling it with a greater capacity.
1468 if self.capacity() > self.len {
1469 self.buf.shrink_to_fit(self.len);
1470 }
1471 }
1472
1473 /// Shrinks the capacity of the vector with a lower bound.
1474 ///
1475 /// The capacity will remain at least as large as both the length
1476 /// and the supplied value.
1477 ///
1478 /// If the current capacity is less than the lower limit, this is a no-op.
1479 ///
1480 /// # Examples
1481 ///
1482 /// ```
1483 /// let mut vec = Vec::with_capacity(10);
1484 /// vec.extend([1, 2, 3]);
1485 /// assert!(vec.capacity() >= 10);
1486 /// vec.shrink_to(4);
1487 /// assert!(vec.capacity() >= 4);
1488 /// vec.shrink_to(0);
1489 /// assert!(vec.capacity() >= 3);
1490 /// ```
1491 #[cfg(not(no_global_oom_handling))]
1492 #[stable(feature = "shrink_to", since = "1.56.0")]
1493 #[track_caller]
1494 pub fn shrink_to(&mut self, min_capacity: usize) {
1495 if self.capacity() > min_capacity {
1496 self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
1497 }
1498 }
1499
1500 /// Converts the vector into [`Box<[T]>`][owned slice].
1501 ///
1502 /// Before doing the conversion, this method discards excess capacity like [`shrink_to_fit`].
1503 ///
1504 /// [owned slice]: Box
1505 /// [`shrink_to_fit`]: Vec::shrink_to_fit
1506 ///
1507 /// # Examples
1508 ///
1509 /// ```
1510 /// let v = vec![1, 2, 3];
1511 ///
1512 /// let slice = v.into_boxed_slice();
1513 /// ```
1514 ///
1515 /// Any excess capacity is removed:
1516 ///
1517 /// ```
1518 /// let mut vec = Vec::with_capacity(10);
1519 /// vec.extend([1, 2, 3]);
1520 ///
1521 /// assert!(vec.capacity() >= 10);
1522 /// let slice = vec.into_boxed_slice();
1523 /// assert_eq!(slice.into_vec().capacity(), 3);
1524 /// ```
1525 #[cfg(not(no_global_oom_handling))]
1526 #[stable(feature = "rust1", since = "1.0.0")]
1527 #[track_caller]
1528 pub fn into_boxed_slice(mut self) -> Box<[T], A> {
1529 unsafe {
1530 self.shrink_to_fit();
1531 let me = ManuallyDrop::new(self);
1532 let buf = ptr::read(&me.buf);
1533 let len = me.len();
1534 buf.into_box(len).assume_init()
1535 }
1536 }
1537
1538 /// Shortens the vector, keeping the first `len` elements and dropping
1539 /// the rest.
1540 ///
1541 /// If `len` is greater or equal to the vector's current length, this has
1542 /// no effect.
1543 ///
1544 /// The [`drain`] method can emulate `truncate`, but causes the excess
1545 /// elements to be returned instead of dropped.
1546 ///
1547 /// Note that this method has no effect on the allocated capacity
1548 /// of the vector.
1549 ///
1550 /// # Examples
1551 ///
1552 /// Truncating a five element vector to two elements:
1553 ///
1554 /// ```
1555 /// let mut vec = vec![1, 2, 3, 4, 5];
1556 /// vec.truncate(2);
1557 /// assert_eq!(vec, [1, 2]);
1558 /// ```
1559 ///
1560 /// No truncation occurs when `len` is greater than the vector's current
1561 /// length:
1562 ///
1563 /// ```
1564 /// let mut vec = vec![1, 2, 3];
1565 /// vec.truncate(8);
1566 /// assert_eq!(vec, [1, 2, 3]);
1567 /// ```
1568 ///
1569 /// Truncating when `len == 0` is equivalent to calling the [`clear`]
1570 /// method.
1571 ///
1572 /// ```
1573 /// let mut vec = vec![1, 2, 3];
1574 /// vec.truncate(0);
1575 /// assert_eq!(vec, []);
1576 /// ```
1577 ///
1578 /// [`clear`]: Vec::clear
1579 /// [`drain`]: Vec::drain
1580 #[stable(feature = "rust1", since = "1.0.0")]
1581 pub fn truncate(&mut self, len: usize) {
1582 // This is safe because:
1583 //
1584 // * the slice passed to `drop_in_place` is valid; the `len > self.len`
1585 // case avoids creating an invalid slice, and
1586 // * the `len` of the vector is shrunk before calling `drop_in_place`,
1587 // such that no value will be dropped twice in case `drop_in_place`
1588 // were to panic once (if it panics twice, the program aborts).
1589 unsafe {
1590 // Note: It's intentional that this is `>` and not `>=`.
1591 // Changing it to `>=` has negative performance
1592 // implications in some cases. See #78884 for more.
1593 if len > self.len {
1594 return;
1595 }
1596 let remaining_len = self.len - len;
1597 let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
1598 self.len = len;
1599 ptr::drop_in_place(s);
1600 }
1601 }
1602
1603 /// Extracts a slice containing the entire vector.
1604 ///
1605 /// Equivalent to `&s[..]`.
1606 ///
1607 /// # Examples
1608 ///
1609 /// ```
1610 /// use std::io::{self, Write};
1611 /// let buffer = vec![1, 2, 3, 5, 8];
1612 /// io::sink().write(buffer.as_slice()).unwrap();
1613 /// ```
1614 #[inline]
1615 #[stable(feature = "vec_as_slice", since = "1.7.0")]
1616 #[rustc_diagnostic_item = "vec_as_slice"]
1617 #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1618 pub const fn as_slice(&self) -> &[T] {
1619 // SAFETY: `slice::from_raw_parts` requires pointee is a contiguous, aligned buffer of size
1620 // `len` containing properly-initialized `T`s. Data must not be mutated for the returned
1621 // lifetime. Further, `len * size_of::<T>` <= `isize::MAX`, and allocation does not
1622 // "wrap" through overflowing memory addresses.
1623 //
1624 // * Vec API guarantees that self.buf:
1625 // * contains only properly-initialized items within 0..len
1626 // * is aligned, contiguous, and valid for `len` reads
1627 // * obeys size and address-wrapping constraints
1628 //
1629 // * We only construct `&mut` references to `self.buf` through `&mut self` methods; borrow-
1630 // check ensures that it is not possible to mutably alias `self.buf` within the
1631 // returned lifetime.
1632 unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
1633 }
1634
1635 /// Extracts a mutable slice of the entire vector.
1636 ///
1637 /// Equivalent to `&mut s[..]`.
1638 ///
1639 /// # Examples
1640 ///
1641 /// ```
1642 /// use std::io::{self, Read};
1643 /// let mut buffer = vec![0; 3];
1644 /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
1645 /// ```
1646 #[inline]
1647 #[stable(feature = "vec_as_slice", since = "1.7.0")]
1648 #[rustc_diagnostic_item = "vec_as_mut_slice"]
1649 #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1650 pub const fn as_mut_slice(&mut self) -> &mut [T] {
1651 // SAFETY: `slice::from_raw_parts_mut` requires pointee is a contiguous, aligned buffer of
1652 // size `len` containing properly-initialized `T`s. Data must not be accessed through any
1653 // other pointer for the returned lifetime. Further, `len * size_of::<T>` <=
1654 // `ISIZE::MAX` and allocation does not "wrap" through overflowing memory addresses.
1655 //
1656 // * Vec API guarantees that self.buf:
1657 // * contains only properly-initialized items within 0..len
1658 // * is aligned, contiguous, and valid for `len` reads
1659 // * obeys size and address-wrapping constraints
1660 //
1661 // * We only construct references to `self.buf` through `&self` and `&mut self` methods;
1662 // borrow-check ensures that it is not possible to construct a reference to `self.buf`
1663 // within the returned lifetime.
1664 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
1665 }
1666
1667 /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
1668 /// valid for zero sized reads if the vector didn't allocate.
1669 ///
1670 /// The caller must ensure that the vector outlives the pointer this
1671 /// function returns, or else it will end up dangling.
1672 /// Modifying the vector may cause its buffer to be reallocated,
1673 /// which would also make any pointers to it invalid.
1674 ///
1675 /// The caller must also ensure that the memory the pointer (non-transitively) points to
1676 /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1677 /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1678 ///
1679 /// This method guarantees that for the purpose of the aliasing model, this method
1680 /// does not materialize a reference to the underlying slice, and thus the returned pointer
1681 /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1682 /// and [`as_non_null`].
1683 /// Note that calling other methods that materialize mutable references to the slice,
1684 /// or mutable references to specific elements you are planning on accessing through this pointer,
1685 /// as well as writing to those elements, may still invalidate this pointer.
1686 /// See the second example below for how this guarantee can be used.
1687 ///
1688 ///
1689 /// # Examples
1690 ///
1691 /// ```
1692 /// let x = vec![1, 2, 4];
1693 /// let x_ptr = x.as_ptr();
1694 ///
1695 /// unsafe {
1696 /// for i in 0..x.len() {
1697 /// assert_eq!(*x_ptr.add(i), 1 << i);
1698 /// }
1699 /// }
1700 /// ```
1701 ///
1702 /// Due to the aliasing guarantee, the following code is legal:
1703 ///
1704 /// ```rust
1705 /// unsafe {
1706 /// let mut v = vec![0, 1, 2];
1707 /// let ptr1 = v.as_ptr();
1708 /// let _ = ptr1.read();
1709 /// let ptr2 = v.as_mut_ptr().offset(2);
1710 /// ptr2.write(2);
1711 /// // Notably, the write to `ptr2` did *not* invalidate `ptr1`
1712 /// // because it mutated a different element:
1713 /// let _ = ptr1.read();
1714 /// }
1715 /// ```
1716 ///
1717 /// [`as_mut_ptr`]: Vec::as_mut_ptr
1718 /// [`as_ptr`]: Vec::as_ptr
1719 /// [`as_non_null`]: Vec::as_non_null
1720 #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1721 #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1722 #[rustc_never_returns_null_ptr]
1723 #[rustc_as_ptr]
1724 #[inline]
1725 pub const fn as_ptr(&self) -> *const T {
1726 // We shadow the slice method of the same name to avoid going through
1727 // `deref`, which creates an intermediate reference.
1728 self.buf.ptr()
1729 }
1730
1731 /// Returns a raw mutable pointer to the vector's buffer, or a dangling
1732 /// raw pointer valid for zero sized reads if the vector didn't allocate.
1733 ///
1734 /// The caller must ensure that the vector outlives the pointer this
1735 /// function returns, or else it will end up dangling.
1736 /// Modifying the vector may cause its buffer to be reallocated,
1737 /// which would also make any pointers to it invalid.
1738 ///
1739 /// This method guarantees that for the purpose of the aliasing model, this method
1740 /// does not materialize a reference to the underlying slice, and thus the returned pointer
1741 /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1742 /// and [`as_non_null`].
1743 /// Note that calling other methods that materialize references to the slice,
1744 /// or references to specific elements you are planning on accessing through this pointer,
1745 /// may still invalidate this pointer.
1746 /// See the second example below for how this guarantee can be used.
1747 ///
1748 /// # Examples
1749 ///
1750 /// ```
1751 /// // Allocate vector big enough for 4 elements.
1752 /// let size = 4;
1753 /// let mut x: Vec<i32> = Vec::with_capacity(size);
1754 /// let x_ptr = x.as_mut_ptr();
1755 ///
1756 /// // Initialize elements via raw pointer writes, then set length.
1757 /// unsafe {
1758 /// for i in 0..size {
1759 /// *x_ptr.add(i) = i as i32;
1760 /// }
1761 /// x.set_len(size);
1762 /// }
1763 /// assert_eq!(&*x, &[0, 1, 2, 3]);
1764 /// ```
1765 ///
1766 /// Due to the aliasing guarantee, the following code is legal:
1767 ///
1768 /// ```rust
1769 /// unsafe {
1770 /// let mut v = vec![0];
1771 /// let ptr1 = v.as_mut_ptr();
1772 /// ptr1.write(1);
1773 /// let ptr2 = v.as_mut_ptr();
1774 /// ptr2.write(2);
1775 /// // Notably, the write to `ptr2` did *not* invalidate `ptr1`:
1776 /// ptr1.write(3);
1777 /// }
1778 /// ```
1779 ///
1780 /// [`as_mut_ptr`]: Vec::as_mut_ptr
1781 /// [`as_ptr`]: Vec::as_ptr
1782 /// [`as_non_null`]: Vec::as_non_null
1783 #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1784 #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
1785 #[rustc_never_returns_null_ptr]
1786 #[rustc_as_ptr]
1787 #[inline]
1788 pub const fn as_mut_ptr(&mut self) -> *mut T {
1789 // We shadow the slice method of the same name to avoid going through
1790 // `deref_mut`, which creates an intermediate reference.
1791 self.buf.ptr()
1792 }
1793
1794 /// Returns a `NonNull` pointer to the vector's buffer, or a dangling
1795 /// `NonNull` pointer valid for zero sized reads if the vector didn't allocate.
1796 ///
1797 /// The caller must ensure that the vector outlives the pointer this
1798 /// function returns, or else it will end up dangling.
1799 /// Modifying the vector may cause its buffer to be reallocated,
1800 /// which would also make any pointers to it invalid.
1801 ///
1802 /// This method guarantees that for the purpose of the aliasing model, this method
1803 /// does not materialize a reference to the underlying slice, and thus the returned pointer
1804 /// will remain valid when mixed with other calls to [`as_ptr`], [`as_mut_ptr`],
1805 /// and [`as_non_null`].
1806 /// Note that calling other methods that materialize references to the slice,
1807 /// or references to specific elements you are planning on accessing through this pointer,
1808 /// may still invalidate this pointer.
1809 /// See the second example below for how this guarantee can be used.
1810 ///
1811 /// # Examples
1812 ///
1813 /// ```
1814 /// #![feature(box_vec_non_null)]
1815 ///
1816 /// // Allocate vector big enough for 4 elements.
1817 /// let size = 4;
1818 /// let mut x: Vec<i32> = Vec::with_capacity(size);
1819 /// let x_ptr = x.as_non_null();
1820 ///
1821 /// // Initialize elements via raw pointer writes, then set length.
1822 /// unsafe {
1823 /// for i in 0..size {
1824 /// x_ptr.add(i).write(i as i32);
1825 /// }
1826 /// x.set_len(size);
1827 /// }
1828 /// assert_eq!(&*x, &[0, 1, 2, 3]);
1829 /// ```
1830 ///
1831 /// Due to the aliasing guarantee, the following code is legal:
1832 ///
1833 /// ```rust
1834 /// #![feature(box_vec_non_null)]
1835 ///
1836 /// unsafe {
1837 /// let mut v = vec![0];
1838 /// let ptr1 = v.as_non_null();
1839 /// ptr1.write(1);
1840 /// let ptr2 = v.as_non_null();
1841 /// ptr2.write(2);
1842 /// // Notably, the write to `ptr2` did *not* invalidate `ptr1`:
1843 /// ptr1.write(3);
1844 /// }
1845 /// ```
1846 ///
1847 /// [`as_mut_ptr`]: Vec::as_mut_ptr
1848 /// [`as_ptr`]: Vec::as_ptr
1849 /// [`as_non_null`]: Vec::as_non_null
1850 #[unstable(feature = "box_vec_non_null", reason = "new API", issue = "130364")]
1851 #[rustc_const_unstable(feature = "box_vec_non_null", reason = "new API", issue = "130364")]
1852 #[inline]
1853 pub const fn as_non_null(&mut self) -> NonNull<T> {
1854 self.buf.non_null()
1855 }
1856
1857 /// Returns a reference to the underlying allocator.
1858 #[unstable(feature = "allocator_api", issue = "32838")]
1859 #[inline]
1860 pub fn allocator(&self) -> &A {
1861 self.buf.allocator()
1862 }
1863
1864 /// Forces the length of the vector to `new_len`.
1865 ///
1866 /// This is a low-level operation that maintains none of the normal
1867 /// invariants of the type. Normally changing the length of a vector
1868 /// is done using one of the safe operations instead, such as
1869 /// [`truncate`], [`resize`], [`extend`], or [`clear`].
1870 ///
1871 /// [`truncate`]: Vec::truncate
1872 /// [`resize`]: Vec::resize
1873 /// [`extend`]: Extend::extend
1874 /// [`clear`]: Vec::clear
1875 ///
1876 /// # Safety
1877 ///
1878 /// - `new_len` must be less than or equal to [`capacity()`].
1879 /// - The elements at `old_len..new_len` must be initialized.
1880 ///
1881 /// [`capacity()`]: Vec::capacity
1882 ///
1883 /// # Examples
1884 ///
1885 /// See [`spare_capacity_mut()`] for an example with safe
1886 /// initialization of capacity elements and use of this method.
1887 ///
1888 /// `set_len()` can be useful for situations in which the vector
1889 /// is serving as a buffer for other code, particularly over FFI:
1890 ///
1891 /// ```no_run
1892 /// # #![allow(dead_code)]
1893 /// # // This is just a minimal skeleton for the doc example;
1894 /// # // don't use this as a starting point for a real library.
1895 /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void }
1896 /// # const Z_OK: i32 = 0;
1897 /// # unsafe extern "C" {
1898 /// # fn deflateGetDictionary(
1899 /// # strm: *mut std::ffi::c_void,
1900 /// # dictionary: *mut u8,
1901 /// # dictLength: *mut usize,
1902 /// # ) -> i32;
1903 /// # }
1904 /// # impl StreamWrapper {
1905 /// pub fn get_dictionary(&self) -> Option<Vec<u8>> {
1906 /// // Per the FFI method's docs, "32768 bytes is always enough".
1907 /// let mut dict = Vec::with_capacity(32_768);
1908 /// let mut dict_length = 0;
1909 /// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
1910 /// // 1. `dict_length` elements were initialized.
1911 /// // 2. `dict_length` <= the capacity (32_768)
1912 /// // which makes `set_len` safe to call.
1913 /// unsafe {
1914 /// // Make the FFI call...
1915 /// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
1916 /// if r == Z_OK {
1917 /// // ...and update the length to what was initialized.
1918 /// dict.set_len(dict_length);
1919 /// Some(dict)
1920 /// } else {
1921 /// None
1922 /// }
1923 /// }
1924 /// }
1925 /// # }
1926 /// ```
1927 ///
1928 /// While the following example is sound, there is a memory leak since
1929 /// the inner vectors were not freed prior to the `set_len` call:
1930 ///
1931 /// ```
1932 /// let mut vec = vec![vec![1, 0, 0],
1933 /// vec![0, 1, 0],
1934 /// vec![0, 0, 1]];
1935 /// // SAFETY:
1936 /// // 1. `old_len..0` is empty so no elements need to be initialized.
1937 /// // 2. `0 <= capacity` always holds whatever `capacity` is.
1938 /// unsafe {
1939 /// vec.set_len(0);
1940 /// # // FIXME(https://github.com/rust-lang/miri/issues/3670):
1941 /// # // use -Zmiri-disable-leak-check instead of unleaking in tests meant to leak.
1942 /// # vec.set_len(3);
1943 /// }
1944 /// ```
1945 ///
1946 /// Normally, here, one would use [`clear`] instead to correctly drop
1947 /// the contents and thus not leak memory.
1948 ///
1949 /// [`spare_capacity_mut()`]: Vec::spare_capacity_mut
1950 #[inline]
1951 #[stable(feature = "rust1", since = "1.0.0")]
1952 pub unsafe fn set_len(&mut self, new_len: usize) {
1953 debug_assert!(new_len <= self.capacity());
1954
1955 self.len = new_len;
1956 }
1957
1958 /// Removes an element from the vector and returns it.
1959 ///
1960 /// The removed element is replaced by the last element of the vector.
1961 ///
1962 /// This does not preserve ordering of the remaining elements, but is *O*(1).
1963 /// If you need to preserve the element order, use [`remove`] instead.
1964 ///
1965 /// [`remove`]: Vec::remove
1966 ///
1967 /// # Panics
1968 ///
1969 /// Panics if `index` is out of bounds.
1970 ///
1971 /// # Examples
1972 ///
1973 /// ```
1974 /// let mut v = vec!["foo", "bar", "baz", "qux"];
1975 ///
1976 /// assert_eq!(v.swap_remove(1), "bar");
1977 /// assert_eq!(v, ["foo", "qux", "baz"]);
1978 ///
1979 /// assert_eq!(v.swap_remove(0), "foo");
1980 /// assert_eq!(v, ["baz", "qux"]);
1981 /// ```
1982 #[inline]
1983 #[stable(feature = "rust1", since = "1.0.0")]
1984 pub fn swap_remove(&mut self, index: usize) -> T {
1985 #[cold]
1986 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
1987 #[track_caller]
1988 #[optimize(size)]
1989 fn assert_failed(index: usize, len: usize) -> ! {
1990 panic!("swap_remove index (is {index}) should be < len (is {len})");
1991 }
1992
1993 let len = self.len();
1994 if index >= len {
1995 assert_failed(index, len);
1996 }
1997 unsafe {
1998 // We replace self[index] with the last element. Note that if the
1999 // bounds check above succeeds there must be a last element (which
2000 // can be self[index] itself).
2001 let value = ptr::read(self.as_ptr().add(index));
2002 let base_ptr = self.as_mut_ptr();
2003 ptr::copy(base_ptr.add(len - 1), base_ptr.add(index), 1);
2004 self.set_len(len - 1);
2005 value
2006 }
2007 }
2008
2009 /// Inserts an element at position `index` within the vector, shifting all
2010 /// elements after it to the right.
2011 ///
2012 /// # Panics
2013 ///
2014 /// Panics if `index > len`.
2015 ///
2016 /// # Examples
2017 ///
2018 /// ```
2019 /// let mut vec = vec!['a', 'b', 'c'];
2020 /// vec.insert(1, 'd');
2021 /// assert_eq!(vec, ['a', 'd', 'b', 'c']);
2022 /// vec.insert(4, 'e');
2023 /// assert_eq!(vec, ['a', 'd', 'b', 'c', 'e']);
2024 /// ```
2025 ///
2026 /// # Time complexity
2027 ///
2028 /// Takes *O*([`Vec::len`]) time. All items after the insertion index must be
2029 /// shifted to the right. In the worst case, all elements are shifted when
2030 /// the insertion index is 0.
2031 #[cfg(not(no_global_oom_handling))]
2032 #[stable(feature = "rust1", since = "1.0.0")]
2033 #[track_caller]
2034 pub fn insert(&mut self, index: usize, element: T) {
2035 #[cold]
2036 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
2037 #[track_caller]
2038 #[optimize(size)]
2039 fn assert_failed(index: usize, len: usize) -> ! {
2040 panic!("insertion index (is {index}) should be <= len (is {len})");
2041 }
2042
2043 let len = self.len();
2044 if index > len {
2045 assert_failed(index, len);
2046 }
2047
2048 // space for the new element
2049 if len == self.buf.capacity() {
2050 self.buf.grow_one();
2051 }
2052
2053 unsafe {
2054 // infallible
2055 // The spot to put the new value
2056 {
2057 let p = self.as_mut_ptr().add(index);
2058 if index < len {
2059 // Shift everything over to make space. (Duplicating the
2060 // `index`th element into two consecutive places.)
2061 ptr::copy(p, p.add(1), len - index);
2062 }
2063 // Write it in, overwriting the first copy of the `index`th
2064 // element.
2065 ptr::write(p, element);
2066 }
2067 self.set_len(len + 1);
2068 }
2069 }
2070
2071 /// Removes and returns the element at position `index` within the vector,
2072 /// shifting all elements after it to the left.
2073 ///
2074 /// Note: Because this shifts over the remaining elements, it has a
2075 /// worst-case performance of *O*(*n*). If you don't need the order of elements
2076 /// to be preserved, use [`swap_remove`] instead. If you'd like to remove
2077 /// elements from the beginning of the `Vec`, consider using
2078 /// [`VecDeque::pop_front`] instead.
2079 ///
2080 /// [`swap_remove`]: Vec::swap_remove
2081 /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2082 ///
2083 /// # Panics
2084 ///
2085 /// Panics if `index` is out of bounds.
2086 ///
2087 /// # Examples
2088 ///
2089 /// ```
2090 /// let mut v = vec!['a', 'b', 'c'];
2091 /// assert_eq!(v.remove(1), 'b');
2092 /// assert_eq!(v, ['a', 'c']);
2093 /// ```
2094 #[stable(feature = "rust1", since = "1.0.0")]
2095 #[track_caller]
2096 #[rustc_confusables("delete", "take")]
2097 pub fn remove(&mut self, index: usize) -> T {
2098 #[cold]
2099 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
2100 #[track_caller]
2101 #[optimize(size)]
2102 fn assert_failed(index: usize, len: usize) -> ! {
2103 panic!("removal index (is {index}) should be < len (is {len})");
2104 }
2105
2106 let len = self.len();
2107 if index >= len {
2108 assert_failed(index, len);
2109 }
2110 unsafe {
2111 // infallible
2112 let ret;
2113 {
2114 // the place we are taking from.
2115 let ptr = self.as_mut_ptr().add(index);
2116 // copy it out, unsafely having a copy of the value on
2117 // the stack and in the vector at the same time.
2118 ret = ptr::read(ptr);
2119
2120 // Shift everything down to fill in that spot.
2121 ptr::copy(ptr.add(1), ptr, len - index - 1);
2122 }
2123 self.set_len(len - 1);
2124 ret
2125 }
2126 }
2127
2128 /// Retains only the elements specified by the predicate.
2129 ///
2130 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
2131 /// This method operates in place, visiting each element exactly once in the
2132 /// original order, and preserves the order of the retained elements.
2133 ///
2134 /// # Examples
2135 ///
2136 /// ```
2137 /// let mut vec = vec![1, 2, 3, 4];
2138 /// vec.retain(|&x| x % 2 == 0);
2139 /// assert_eq!(vec, [2, 4]);
2140 /// ```
2141 ///
2142 /// Because the elements are visited exactly once in the original order,
2143 /// external state may be used to decide which elements to keep.
2144 ///
2145 /// ```
2146 /// let mut vec = vec![1, 2, 3, 4, 5];
2147 /// let keep = [false, true, true, false, true];
2148 /// let mut iter = keep.iter();
2149 /// vec.retain(|_| *iter.next().unwrap());
2150 /// assert_eq!(vec, [2, 3, 5]);
2151 /// ```
2152 #[stable(feature = "rust1", since = "1.0.0")]
2153 pub fn retain<F>(&mut self, mut f: F)
2154 where
2155 F: FnMut(&T) -> bool,
2156 {
2157 self.retain_mut(|elem| f(elem));
2158 }
2159
2160 /// Retains only the elements specified by the predicate, passing a mutable reference to it.
2161 ///
2162 /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
2163 /// This method operates in place, visiting each element exactly once in the
2164 /// original order, and preserves the order of the retained elements.
2165 ///
2166 /// # Examples
2167 ///
2168 /// ```
2169 /// let mut vec = vec![1, 2, 3, 4];
2170 /// vec.retain_mut(|x| if *x <= 3 {
2171 /// *x += 1;
2172 /// true
2173 /// } else {
2174 /// false
2175 /// });
2176 /// assert_eq!(vec, [2, 3, 4]);
2177 /// ```
2178 #[stable(feature = "vec_retain_mut", since = "1.61.0")]
2179 pub fn retain_mut<F>(&mut self, mut f: F)
2180 where
2181 F: FnMut(&mut T) -> bool,
2182 {
2183 let original_len = self.len();
2184
2185 if original_len == 0 {
2186 // Empty case: explicit return allows better optimization, vs letting compiler infer it
2187 return;
2188 }
2189
2190 // Avoid double drop if the drop guard is not executed,
2191 // since we may make some holes during the process.
2192 unsafe { self.set_len(0) };
2193
2194 // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
2195 // |<- processed len ->| ^- next to check
2196 // |<- deleted cnt ->|
2197 // |<- original_len ->|
2198 // Kept: Elements which predicate returns true on.
2199 // Hole: Moved or dropped element slot.
2200 // Unchecked: Unchecked valid elements.
2201 //
2202 // This drop guard will be invoked when predicate or `drop` of element panicked.
2203 // It shifts unchecked elements to cover holes and `set_len` to the correct length.
2204 // In cases when predicate and `drop` never panick, it will be optimized out.
2205 struct BackshiftOnDrop<'a, T, A: Allocator> {
2206 v: &'a mut Vec<T, A>,
2207 processed_len: usize,
2208 deleted_cnt: usize,
2209 original_len: usize,
2210 }
2211
2212 impl<T, A: Allocator> Drop for BackshiftOnDrop<'_, T, A> {
2213 fn drop(&mut self) {
2214 if self.deleted_cnt > 0 {
2215 // SAFETY: Trailing unchecked items must be valid since we never touch them.
2216 unsafe {
2217 ptr::copy(
2218 self.v.as_ptr().add(self.processed_len),
2219 self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
2220 self.original_len - self.processed_len,
2221 );
2222 }
2223 }
2224 // SAFETY: After filling holes, all items are in contiguous memory.
2225 unsafe {
2226 self.v.set_len(self.original_len - self.deleted_cnt);
2227 }
2228 }
2229 }
2230
2231 let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };
2232
2233 fn process_loop<F, T, A: Allocator, const DELETED: bool>(
2234 original_len: usize,
2235 f: &mut F,
2236 g: &mut BackshiftOnDrop<'_, T, A>,
2237 ) where
2238 F: FnMut(&mut T) -> bool,
2239 {
2240 while g.processed_len != original_len {
2241 // SAFETY: Unchecked element must be valid.
2242 let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) };
2243 if !f(cur) {
2244 // Advance early to avoid double drop if `drop_in_place` panicked.
2245 g.processed_len += 1;
2246 g.deleted_cnt += 1;
2247 // SAFETY: We never touch this element again after dropped.
2248 unsafe { ptr::drop_in_place(cur) };
2249 // We already advanced the counter.
2250 if DELETED {
2251 continue;
2252 } else {
2253 break;
2254 }
2255 }
2256 if DELETED {
2257 // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
2258 // We use copy for move, and never touch this element again.
2259 unsafe {
2260 let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
2261 ptr::copy_nonoverlapping(cur, hole_slot, 1);
2262 }
2263 }
2264 g.processed_len += 1;
2265 }
2266 }
2267
2268 // Stage 1: Nothing was deleted.
2269 process_loop::<F, T, A, false>(original_len, &mut f, &mut g);
2270
2271 // Stage 2: Some elements were deleted.
2272 process_loop::<F, T, A, true>(original_len, &mut f, &mut g);
2273
2274 // All item are processed. This can be optimized to `set_len` by LLVM.
2275 drop(g);
2276 }
2277
2278 /// Removes all but the first of consecutive elements in the vector that resolve to the same
2279 /// key.
2280 ///
2281 /// If the vector is sorted, this removes all duplicates.
2282 ///
2283 /// # Examples
2284 ///
2285 /// ```
2286 /// let mut vec = vec![10, 20, 21, 30, 20];
2287 ///
2288 /// vec.dedup_by_key(|i| *i / 10);
2289 ///
2290 /// assert_eq!(vec, [10, 20, 30, 20]);
2291 /// ```
2292 #[stable(feature = "dedup_by", since = "1.16.0")]
2293 #[inline]
2294 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
2295 where
2296 F: FnMut(&mut T) -> K,
2297 K: PartialEq,
2298 {
2299 self.dedup_by(|a, b| key(a) == key(b))
2300 }
2301
2302 /// Removes all but the first of consecutive elements in the vector satisfying a given equality
2303 /// relation.
2304 ///
2305 /// The `same_bucket` function is passed references to two elements from the vector and
2306 /// must determine if the elements compare equal. The elements are passed in opposite order
2307 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
2308 ///
2309 /// If the vector is sorted, this removes all duplicates.
2310 ///
2311 /// # Examples
2312 ///
2313 /// ```
2314 /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
2315 ///
2316 /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
2317 ///
2318 /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
2319 /// ```
2320 #[stable(feature = "dedup_by", since = "1.16.0")]
2321 pub fn dedup_by<F>(&mut self, mut same_bucket: F)
2322 where
2323 F: FnMut(&mut T, &mut T) -> bool,
2324 {
2325 let len = self.len();
2326 if len <= 1 {
2327 return;
2328 }
2329
2330 // Check if we ever want to remove anything.
2331 // This allows to use copy_non_overlapping in next cycle.
2332 // And avoids any memory writes if we don't need to remove anything.
2333 let mut first_duplicate_idx: usize = 1;
2334 let start = self.as_mut_ptr();
2335 while first_duplicate_idx != len {
2336 let found_duplicate = unsafe {
2337 // SAFETY: first_duplicate always in range [1..len)
2338 // Note that we start iteration from 1 so we never overflow.
2339 let prev = start.add(first_duplicate_idx.wrapping_sub(1));
2340 let current = start.add(first_duplicate_idx);
2341 // We explicitly say in docs that references are reversed.
2342 same_bucket(&mut *current, &mut *prev)
2343 };
2344 if found_duplicate {
2345 break;
2346 }
2347 first_duplicate_idx += 1;
2348 }
2349 // Don't need to remove anything.
2350 // We cannot get bigger than len.
2351 if first_duplicate_idx == len {
2352 return;
2353 }
2354
2355 /* INVARIANT: vec.len() > read > write > write-1 >= 0 */
2356 struct FillGapOnDrop<'a, T, A: core::alloc::Allocator> {
2357 /* Offset of the element we want to check if it is duplicate */
2358 read: usize,
2359
2360 /* Offset of the place where we want to place the non-duplicate
2361 * when we find it. */
2362 write: usize,
2363
2364 /* The Vec that would need correction if `same_bucket` panicked */
2365 vec: &'a mut Vec<T, A>,
2366 }
2367
2368 impl<'a, T, A: core::alloc::Allocator> Drop for FillGapOnDrop<'a, T, A> {
2369 fn drop(&mut self) {
2370 /* This code gets executed when `same_bucket` panics */
2371
2372 /* SAFETY: invariant guarantees that `read - write`
2373 * and `len - read` never overflow and that the copy is always
2374 * in-bounds. */
2375 unsafe {
2376 let ptr = self.vec.as_mut_ptr();
2377 let len = self.vec.len();
2378
2379 /* How many items were left when `same_bucket` panicked.
2380 * Basically vec[read..].len() */
2381 let items_left = len.wrapping_sub(self.read);
2382
2383 /* Pointer to first item in vec[write..write+items_left] slice */
2384 let dropped_ptr = ptr.add(self.write);
2385 /* Pointer to first item in vec[read..] slice */
2386 let valid_ptr = ptr.add(self.read);
2387
2388 /* Copy `vec[read..]` to `vec[write..write+items_left]`.
2389 * The slices can overlap, so `copy_nonoverlapping` cannot be used */
2390 ptr::copy(valid_ptr, dropped_ptr, items_left);
2391
2392 /* How many items have been already dropped
2393 * Basically vec[read..write].len() */
2394 let dropped = self.read.wrapping_sub(self.write);
2395
2396 self.vec.set_len(len - dropped);
2397 }
2398 }
2399 }
2400
2401 /* Drop items while going through Vec, it should be more efficient than
2402 * doing slice partition_dedup + truncate */
2403
2404 // Construct gap first and then drop item to avoid memory corruption if `T::drop` panics.
2405 let mut gap =
2406 FillGapOnDrop { read: first_duplicate_idx + 1, write: first_duplicate_idx, vec: self };
2407 unsafe {
2408 // SAFETY: we checked that first_duplicate_idx in bounds before.
2409 // If drop panics, `gap` would remove this item without drop.
2410 ptr::drop_in_place(start.add(first_duplicate_idx));
2411 }
2412
2413 /* SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr
2414 * are always in-bounds and read_ptr never aliases prev_ptr */
2415 unsafe {
2416 while gap.read < len {
2417 let read_ptr = start.add(gap.read);
2418 let prev_ptr = start.add(gap.write.wrapping_sub(1));
2419
2420 // We explicitly say in docs that references are reversed.
2421 let found_duplicate = same_bucket(&mut *read_ptr, &mut *prev_ptr);
2422 if found_duplicate {
2423 // Increase `gap.read` now since the drop may panic.
2424 gap.read += 1;
2425 /* We have found duplicate, drop it in-place */
2426 ptr::drop_in_place(read_ptr);
2427 } else {
2428 let write_ptr = start.add(gap.write);
2429
2430 /* read_ptr cannot be equal to write_ptr because at this point
2431 * we guaranteed to skip at least one element (before loop starts).
2432 */
2433 ptr::copy_nonoverlapping(read_ptr, write_ptr, 1);
2434
2435 /* We have filled that place, so go further */
2436 gap.write += 1;
2437 gap.read += 1;
2438 }
2439 }
2440
2441 /* Technically we could let `gap` clean up with its Drop, but
2442 * when `same_bucket` is guaranteed to not panic, this bloats a little
2443 * the codegen, so we just do it manually */
2444 gap.vec.set_len(gap.write);
2445 mem::forget(gap);
2446 }
2447 }
2448
2449 /// Appends an element to the back of a collection.
2450 ///
2451 /// # Panics
2452 ///
2453 /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
2454 ///
2455 /// # Examples
2456 ///
2457 /// ```
2458 /// let mut vec = vec![1, 2];
2459 /// vec.push(3);
2460 /// assert_eq!(vec, [1, 2, 3]);
2461 /// ```
2462 ///
2463 /// # Time complexity
2464 ///
2465 /// Takes amortized *O*(1) time. If the vector's length would exceed its
2466 /// capacity after the push, *O*(*capacity*) time is taken to copy the
2467 /// vector's elements to a larger allocation. This expensive operation is
2468 /// offset by the *capacity* *O*(1) insertions it allows.
2469 #[cfg(not(no_global_oom_handling))]
2470 #[inline]
2471 #[stable(feature = "rust1", since = "1.0.0")]
2472 #[rustc_confusables("push_back", "put", "append")]
2473 #[track_caller]
2474 pub fn push(&mut self, value: T) {
2475 // Inform codegen that the length does not change across grow_one().
2476 let len = self.len;
2477 // This will panic or abort if we would allocate > isize::MAX bytes
2478 // or if the length increment would overflow for zero-sized types.
2479 if len == self.buf.capacity() {
2480 self.buf.grow_one();
2481 }
2482 unsafe {
2483 let end = self.as_mut_ptr().add(len);
2484 ptr::write(end, value);
2485 self.len = len + 1;
2486 }
2487 }
2488
2489 /// Appends an element if there is sufficient spare capacity, otherwise an error is returned
2490 /// with the element.
2491 ///
2492 /// Unlike [`push`] this method will not reallocate when there's insufficient capacity.
2493 /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity.
2494 ///
2495 /// [`push`]: Vec::push
2496 /// [`reserve`]: Vec::reserve
2497 /// [`try_reserve`]: Vec::try_reserve
2498 ///
2499 /// # Examples
2500 ///
2501 /// A manual, panic-free alternative to [`FromIterator`]:
2502 ///
2503 /// ```
2504 /// #![feature(vec_push_within_capacity)]
2505 ///
2506 /// use std::collections::TryReserveError;
2507 /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> {
2508 /// let mut vec = Vec::new();
2509 /// for value in iter {
2510 /// if let Err(value) = vec.push_within_capacity(value) {
2511 /// vec.try_reserve(1)?;
2512 /// // this cannot fail, the previous line either returned or added at least 1 free slot
2513 /// let _ = vec.push_within_capacity(value);
2514 /// }
2515 /// }
2516 /// Ok(vec)
2517 /// }
2518 /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100)));
2519 /// ```
2520 ///
2521 /// # Time complexity
2522 ///
2523 /// Takes *O*(1) time.
2524 #[inline]
2525 #[unstable(feature = "vec_push_within_capacity", issue = "100486")]
2526 pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> {
2527 if self.len == self.buf.capacity() {
2528 return Err(value);
2529 }
2530 unsafe {
2531 let end = self.as_mut_ptr().add(self.len);
2532 ptr::write(end, value);
2533 self.len += 1;
2534 }
2535 Ok(())
2536 }
2537
2538 /// Removes the last element from a vector and returns it, or [`None`] if it
2539 /// is empty.
2540 ///
2541 /// If you'd like to pop the first element, consider using
2542 /// [`VecDeque::pop_front`] instead.
2543 ///
2544 /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2545 ///
2546 /// # Examples
2547 ///
2548 /// ```
2549 /// let mut vec = vec![1, 2, 3];
2550 /// assert_eq!(vec.pop(), Some(3));
2551 /// assert_eq!(vec, [1, 2]);
2552 /// ```
2553 ///
2554 /// # Time complexity
2555 ///
2556 /// Takes *O*(1) time.
2557 #[inline]
2558 #[stable(feature = "rust1", since = "1.0.0")]
2559 #[rustc_diagnostic_item = "vec_pop"]
2560 pub fn pop(&mut self) -> Option<T> {
2561 if self.len == 0 {
2562 None
2563 } else {
2564 unsafe {
2565 self.len -= 1;
2566 core::hint::assert_unchecked(self.len < self.capacity());
2567 Some(ptr::read(self.as_ptr().add(self.len())))
2568 }
2569 }
2570 }
2571
2572 /// Removes and returns the last element from a vector if the predicate
2573 /// returns `true`, or [`None`] if the predicate returns false or the vector
2574 /// is empty (the predicate will not be called in that case).
2575 ///
2576 /// # Examples
2577 ///
2578 /// ```
2579 /// let mut vec = vec![1, 2, 3, 4];
2580 /// let pred = |x: &mut i32| *x % 2 == 0;
2581 ///
2582 /// assert_eq!(vec.pop_if(pred), Some(4));
2583 /// assert_eq!(vec, [1, 2, 3]);
2584 /// assert_eq!(vec.pop_if(pred), None);
2585 /// ```
2586 #[stable(feature = "vec_pop_if", since = "1.86.0")]
2587 pub fn pop_if(&mut self, predicate: impl FnOnce(&mut T) -> bool) -> Option<T> {
2588 let last = self.last_mut()?;
2589 if predicate(last) { self.pop() } else { None }
2590 }
2591
2592 /// Moves all the elements of `other` into `self`, leaving `other` empty.
2593 ///
2594 /// # Panics
2595 ///
2596 /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
2597 ///
2598 /// # Examples
2599 ///
2600 /// ```
2601 /// let mut vec = vec![1, 2, 3];
2602 /// let mut vec2 = vec![4, 5, 6];
2603 /// vec.append(&mut vec2);
2604 /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
2605 /// assert_eq!(vec2, []);
2606 /// ```
2607 #[cfg(not(no_global_oom_handling))]
2608 #[inline]
2609 #[stable(feature = "append", since = "1.4.0")]
2610 #[track_caller]
2611 pub fn append(&mut self, other: &mut Self) {
2612 unsafe {
2613 self.append_elements(other.as_slice() as _);
2614 other.set_len(0);
2615 }
2616 }
2617
2618 /// Appends elements to `self` from other buffer.
2619 #[cfg(not(no_global_oom_handling))]
2620 #[inline]
2621 #[track_caller]
2622 unsafe fn append_elements(&mut self, other: *const [T]) {
2623 let count = other.len();
2624 self.reserve(count);
2625 let len = self.len();
2626 unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) };
2627 self.len += count;
2628 }
2629
2630 /// Removes the subslice indicated by the given range from the vector,
2631 /// returning a double-ended iterator over the removed subslice.
2632 ///
2633 /// If the iterator is dropped before being fully consumed,
2634 /// it drops the remaining removed elements.
2635 ///
2636 /// The returned iterator keeps a mutable borrow on the vector to optimize
2637 /// its implementation.
2638 ///
2639 /// # Panics
2640 ///
2641 /// Panics if the starting point is greater than the end point or if
2642 /// the end point is greater than the length of the vector.
2643 ///
2644 /// # Leaking
2645 ///
2646 /// If the returned iterator goes out of scope without being dropped (due to
2647 /// [`mem::forget`], for example), the vector may have lost and leaked
2648 /// elements arbitrarily, including elements outside the range.
2649 ///
2650 /// # Examples
2651 ///
2652 /// ```
2653 /// let mut v = vec![1, 2, 3];
2654 /// let u: Vec<_> = v.drain(1..).collect();
2655 /// assert_eq!(v, &[1]);
2656 /// assert_eq!(u, &[2, 3]);
2657 ///
2658 /// // A full range clears the vector, like `clear()` does
2659 /// v.drain(..);
2660 /// assert_eq!(v, &[]);
2661 /// ```
2662 #[stable(feature = "drain", since = "1.6.0")]
2663 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
2664 where
2665 R: RangeBounds<usize>,
2666 {
2667 // Memory safety
2668 //
2669 // When the Drain is first created, it shortens the length of
2670 // the source vector to make sure no uninitialized or moved-from elements
2671 // are accessible at all if the Drain's destructor never gets to run.
2672 //
2673 // Drain will ptr::read out the values to remove.
2674 // When finished, remaining tail of the vec is copied back to cover
2675 // the hole, and the vector length is restored to the new length.
2676 //
2677 let len = self.len();
2678 let Range { start, end } = slice::range(range, ..len);
2679
2680 unsafe {
2681 // set self.vec length's to start, to be safe in case Drain is leaked
2682 self.set_len(start);
2683 let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
2684 Drain {
2685 tail_start: end,
2686 tail_len: len - end,
2687 iter: range_slice.iter(),
2688 vec: NonNull::from(self),
2689 }
2690 }
2691 }
2692
2693 /// Clears the vector, removing all values.
2694 ///
2695 /// Note that this method has no effect on the allocated capacity
2696 /// of the vector.
2697 ///
2698 /// # Examples
2699 ///
2700 /// ```
2701 /// let mut v = vec![1, 2, 3];
2702 ///
2703 /// v.clear();
2704 ///
2705 /// assert!(v.is_empty());
2706 /// ```
2707 #[inline]
2708 #[stable(feature = "rust1", since = "1.0.0")]
2709 pub fn clear(&mut self) {
2710 let elems: *mut [T] = self.as_mut_slice();
2711
2712 // SAFETY:
2713 // - `elems` comes directly from `as_mut_slice` and is therefore valid.
2714 // - Setting `self.len` before calling `drop_in_place` means that,
2715 // if an element's `Drop` impl panics, the vector's `Drop` impl will
2716 // do nothing (leaking the rest of the elements) instead of dropping
2717 // some twice.
2718 unsafe {
2719 self.len = 0;
2720 ptr::drop_in_place(elems);
2721 }
2722 }
2723
2724 /// Returns the number of elements in the vector, also referred to
2725 /// as its 'length'.
2726 ///
2727 /// # Examples
2728 ///
2729 /// ```
2730 /// let a = vec![1, 2, 3];
2731 /// assert_eq!(a.len(), 3);
2732 /// ```
2733 #[inline]
2734 #[stable(feature = "rust1", since = "1.0.0")]
2735 #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
2736 #[rustc_confusables("length", "size")]
2737 pub const fn len(&self) -> usize {
2738 let len = self.len;
2739
2740 // SAFETY: The maximum capacity of `Vec<T>` is `isize::MAX` bytes, so the maximum value can
2741 // be returned is `usize::checked_div(size_of::<T>()).unwrap_or(usize::MAX)`, which
2742 // matches the definition of `T::MAX_SLICE_LEN`.
2743 unsafe { intrinsics::assume(len <= T::MAX_SLICE_LEN) };
2744
2745 len
2746 }
2747
2748 /// Returns `true` if the vector contains no elements.
2749 ///
2750 /// # Examples
2751 ///
2752 /// ```
2753 /// let mut v = Vec::new();
2754 /// assert!(v.is_empty());
2755 ///
2756 /// v.push(1);
2757 /// assert!(!v.is_empty());
2758 /// ```
2759 #[stable(feature = "rust1", since = "1.0.0")]
2760 #[rustc_diagnostic_item = "vec_is_empty"]
2761 #[rustc_const_stable(feature = "const_vec_string_slice", since = "1.87.0")]
2762 pub const fn is_empty(&self) -> bool {
2763 self.len() == 0
2764 }
2765
2766 /// Splits the collection into two at the given index.
2767 ///
2768 /// Returns a newly allocated vector containing the elements in the range
2769 /// `[at, len)`. After the call, the original vector will be left containing
2770 /// the elements `[0, at)` with its previous capacity unchanged.
2771 ///
2772 /// - If you want to take ownership of the entire contents and capacity of
2773 /// the vector, see [`mem::take`] or [`mem::replace`].
2774 /// - If you don't need the returned vector at all, see [`Vec::truncate`].
2775 /// - If you want to take ownership of an arbitrary subslice, or you don't
2776 /// necessarily want to store the removed items in a vector, see [`Vec::drain`].
2777 ///
2778 /// # Panics
2779 ///
2780 /// Panics if `at > len`.
2781 ///
2782 /// # Examples
2783 ///
2784 /// ```
2785 /// let mut vec = vec!['a', 'b', 'c'];
2786 /// let vec2 = vec.split_off(1);
2787 /// assert_eq!(vec, ['a']);
2788 /// assert_eq!(vec2, ['b', 'c']);
2789 /// ```
2790 #[cfg(not(no_global_oom_handling))]
2791 #[inline]
2792 #[must_use = "use `.truncate()` if you don't need the other half"]
2793 #[stable(feature = "split_off", since = "1.4.0")]
2794 #[track_caller]
2795 pub fn split_off(&mut self, at: usize) -> Self
2796 where
2797 A: Clone,
2798 {
2799 #[cold]
2800 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
2801 #[track_caller]
2802 #[optimize(size)]
2803 fn assert_failed(at: usize, len: usize) -> ! {
2804 panic!("`at` split index (is {at}) should be <= len (is {len})");
2805 }
2806
2807 if at > self.len() {
2808 assert_failed(at, self.len());
2809 }
2810
2811 let other_len = self.len - at;
2812 let mut other = Vec::with_capacity_in(other_len, self.allocator().clone());
2813
2814 // Unsafely `set_len` and copy items to `other`.
2815 unsafe {
2816 self.set_len(at);
2817 other.set_len(other_len);
2818
2819 ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
2820 }
2821 other
2822 }
2823
2824 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
2825 ///
2826 /// If `new_len` is greater than `len`, the `Vec` is extended by the
2827 /// difference, with each additional slot filled with the result of
2828 /// calling the closure `f`. The return values from `f` will end up
2829 /// in the `Vec` in the order they have been generated.
2830 ///
2831 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2832 ///
2833 /// This method uses a closure to create new values on every push. If
2834 /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you
2835 /// want to use the [`Default`] trait to generate values, you can
2836 /// pass [`Default::default`] as the second argument.
2837 ///
2838 /// # Panics
2839 ///
2840 /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
2841 ///
2842 /// # Examples
2843 ///
2844 /// ```
2845 /// let mut vec = vec![1, 2, 3];
2846 /// vec.resize_with(5, Default::default);
2847 /// assert_eq!(vec, [1, 2, 3, 0, 0]);
2848 ///
2849 /// let mut vec = vec![];
2850 /// let mut p = 1;
2851 /// vec.resize_with(4, || { p *= 2; p });
2852 /// assert_eq!(vec, [2, 4, 8, 16]);
2853 /// ```
2854 #[cfg(not(no_global_oom_handling))]
2855 #[stable(feature = "vec_resize_with", since = "1.33.0")]
2856 #[track_caller]
2857 pub fn resize_with<F>(&mut self, new_len: usize, f: F)
2858 where
2859 F: FnMut() -> T,
2860 {
2861 let len = self.len();
2862 if new_len > len {
2863 self.extend_trusted(iter::repeat_with(f).take(new_len - len));
2864 } else {
2865 self.truncate(new_len);
2866 }
2867 }
2868
2869 /// Consumes and leaks the `Vec`, returning a mutable reference to the contents,
2870 /// `&'a mut [T]`.
2871 ///
2872 /// Note that the type `T` must outlive the chosen lifetime `'a`. If the type
2873 /// has only static references, or none at all, then this may be chosen to be
2874 /// `'static`.
2875 ///
2876 /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`,
2877 /// so the leaked allocation may include unused capacity that is not part
2878 /// of the returned slice.
2879 ///
2880 /// This function is mainly useful for data that lives for the remainder of
2881 /// the program's life. Dropping the returned reference will cause a memory
2882 /// leak.
2883 ///
2884 /// # Examples
2885 ///
2886 /// Simple usage:
2887 ///
2888 /// ```
2889 /// let x = vec![1, 2, 3];
2890 /// let static_ref: &'static mut [usize] = x.leak();
2891 /// static_ref[0] += 1;
2892 /// assert_eq!(static_ref, &[2, 2, 3]);
2893 /// # // FIXME(https://github.com/rust-lang/miri/issues/3670):
2894 /// # // use -Zmiri-disable-leak-check instead of unleaking in tests meant to leak.
2895 /// # drop(unsafe { Box::from_raw(static_ref) });
2896 /// ```
2897 #[stable(feature = "vec_leak", since = "1.47.0")]
2898 #[inline]
2899 pub fn leak<'a>(self) -> &'a mut [T]
2900 where
2901 A: 'a,
2902 {
2903 let mut me = ManuallyDrop::new(self);
2904 unsafe { slice::from_raw_parts_mut(me.as_mut_ptr(), me.len) }
2905 }
2906
2907 /// Returns the remaining spare capacity of the vector as a slice of
2908 /// `MaybeUninit<T>`.
2909 ///
2910 /// The returned slice can be used to fill the vector with data (e.g. by
2911 /// reading from a file) before marking the data as initialized using the
2912 /// [`set_len`] method.
2913 ///
2914 /// [`set_len`]: Vec::set_len
2915 ///
2916 /// # Examples
2917 ///
2918 /// ```
2919 /// // Allocate vector big enough for 10 elements.
2920 /// let mut v = Vec::with_capacity(10);
2921 ///
2922 /// // Fill in the first 3 elements.
2923 /// let uninit = v.spare_capacity_mut();
2924 /// uninit[0].write(0);
2925 /// uninit[1].write(1);
2926 /// uninit[2].write(2);
2927 ///
2928 /// // Mark the first 3 elements of the vector as being initialized.
2929 /// unsafe {
2930 /// v.set_len(3);
2931 /// }
2932 ///
2933 /// assert_eq!(&v, &[0, 1, 2]);
2934 /// ```
2935 #[stable(feature = "vec_spare_capacity", since = "1.60.0")]
2936 #[inline]
2937 pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
2938 // Note:
2939 // This method is not implemented in terms of `split_at_spare_mut`,
2940 // to prevent invalidation of pointers to the buffer.
2941 unsafe {
2942 slice::from_raw_parts_mut(
2943 self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
2944 self.buf.capacity() - self.len,
2945 )
2946 }
2947 }
2948
2949 /// Returns vector content as a slice of `T`, along with the remaining spare
2950 /// capacity of the vector as a slice of `MaybeUninit<T>`.
2951 ///
2952 /// The returned spare capacity slice can be used to fill the vector with data
2953 /// (e.g. by reading from a file) before marking the data as initialized using
2954 /// the [`set_len`] method.
2955 ///
2956 /// [`set_len`]: Vec::set_len
2957 ///
2958 /// Note that this is a low-level API, which should be used with care for
2959 /// optimization purposes. If you need to append data to a `Vec`
2960 /// you can use [`push`], [`extend`], [`extend_from_slice`],
2961 /// [`extend_from_within`], [`insert`], [`append`], [`resize`] or
2962 /// [`resize_with`], depending on your exact needs.
2963 ///
2964 /// [`push`]: Vec::push
2965 /// [`extend`]: Vec::extend
2966 /// [`extend_from_slice`]: Vec::extend_from_slice
2967 /// [`extend_from_within`]: Vec::extend_from_within
2968 /// [`insert`]: Vec::insert
2969 /// [`append`]: Vec::append
2970 /// [`resize`]: Vec::resize
2971 /// [`resize_with`]: Vec::resize_with
2972 ///
2973 /// # Examples
2974 ///
2975 /// ```
2976 /// #![feature(vec_split_at_spare)]
2977 ///
2978 /// let mut v = vec![1, 1, 2];
2979 ///
2980 /// // Reserve additional space big enough for 10 elements.
2981 /// v.reserve(10);
2982 ///
2983 /// let (init, uninit) = v.split_at_spare_mut();
2984 /// let sum = init.iter().copied().sum::<u32>();
2985 ///
2986 /// // Fill in the next 4 elements.
2987 /// uninit[0].write(sum);
2988 /// uninit[1].write(sum * 2);
2989 /// uninit[2].write(sum * 3);
2990 /// uninit[3].write(sum * 4);
2991 ///
2992 /// // Mark the 4 elements of the vector as being initialized.
2993 /// unsafe {
2994 /// let len = v.len();
2995 /// v.set_len(len + 4);
2996 /// }
2997 ///
2998 /// assert_eq!(&v, &[1, 1, 2, 4, 8, 12, 16]);
2999 /// ```
3000 #[unstable(feature = "vec_split_at_spare", issue = "81944")]
3001 #[inline]
3002 pub fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) {
3003 // SAFETY:
3004 // - len is ignored and so never changed
3005 let (init, spare, _) = unsafe { self.split_at_spare_mut_with_len() };
3006 (init, spare)
3007 }
3008
3009 /// Safety: changing returned .2 (&mut usize) is considered the same as calling `.set_len(_)`.
3010 ///
3011 /// This method provides unique access to all vec parts at once in `extend_from_within`.
3012 unsafe fn split_at_spare_mut_with_len(
3013 &mut self,
3014 ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) {
3015 let ptr = self.as_mut_ptr();
3016 // SAFETY:
3017 // - `ptr` is guaranteed to be valid for `self.len` elements
3018 // - but the allocation extends out to `self.buf.capacity()` elements, possibly
3019 // uninitialized
3020 let spare_ptr = unsafe { ptr.add(self.len) };
3021 let spare_ptr = spare_ptr.cast::<MaybeUninit<T>>();
3022 let spare_len = self.buf.capacity() - self.len;
3023
3024 // SAFETY:
3025 // - `ptr` is guaranteed to be valid for `self.len` elements
3026 // - `spare_ptr` is pointing one element past the buffer, so it doesn't overlap with `initialized`
3027 unsafe {
3028 let initialized = slice::from_raw_parts_mut(ptr, self.len);
3029 let spare = slice::from_raw_parts_mut(spare_ptr, spare_len);
3030
3031 (initialized, spare, &mut self.len)
3032 }
3033 }
3034
3035 /// Groups every `N` elements in the `Vec<T>` into chunks to produce a `Vec<[T; N]>`, dropping
3036 /// elements in the remainder. `N` must be greater than zero.
3037 ///
3038 /// If the capacity is not a multiple of the chunk size, the buffer will shrink down to the
3039 /// nearest multiple with a reallocation or deallocation.
3040 ///
3041 /// This function can be used to reverse [`Vec::into_flattened`].
3042 ///
3043 /// # Examples
3044 ///
3045 /// ```
3046 /// #![feature(vec_into_chunks)]
3047 ///
3048 /// let vec = vec![0, 1, 2, 3, 4, 5, 6, 7];
3049 /// assert_eq!(vec.into_chunks::<3>(), [[0, 1, 2], [3, 4, 5]]);
3050 ///
3051 /// let vec = vec![0, 1, 2, 3];
3052 /// let chunks: Vec<[u8; 10]> = vec.into_chunks();
3053 /// assert!(chunks.is_empty());
3054 ///
3055 /// let flat = vec![0; 8 * 8 * 8];
3056 /// let reshaped: Vec<[[[u8; 8]; 8]; 8]> = flat.into_chunks().into_chunks().into_chunks();
3057 /// assert_eq!(reshaped.len(), 1);
3058 /// ```
3059 #[cfg(not(no_global_oom_handling))]
3060 #[unstable(feature = "vec_into_chunks", issue = "142137")]
3061 pub fn into_chunks<const N: usize>(mut self) -> Vec<[T; N], A> {
3062 const {
3063 assert!(N != 0, "chunk size must be greater than zero");
3064 }
3065
3066 let (len, cap) = (self.len(), self.capacity());
3067
3068 let len_remainder = len % N;
3069 if len_remainder != 0 {
3070 self.truncate(len - len_remainder);
3071 }
3072
3073 let cap_remainder = cap % N;
3074 if !T::IS_ZST && cap_remainder != 0 {
3075 self.buf.shrink_to_fit(cap - cap_remainder);
3076 }
3077
3078 let (ptr, _, _, alloc) = self.into_raw_parts_with_alloc();
3079
3080 // SAFETY:
3081 // - `ptr` and `alloc` were just returned from `self.into_raw_parts_with_alloc()`
3082 // - `[T; N]` has the same alignment as `T`
3083 // - `size_of::<[T; N]>() * cap / N == size_of::<T>() * cap`
3084 // - `len / N <= cap / N` because `len <= cap`
3085 // - the allocated memory consists of `len / N` valid values of type `[T; N]`
3086 // - `cap / N` fits the size of the allocated memory after shrinking
3087 unsafe { Vec::from_raw_parts_in(ptr.cast(), len / N, cap / N, alloc) }
3088 }
3089}
3090
3091impl<T: Clone, A: Allocator> Vec<T, A> {
3092 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
3093 ///
3094 /// If `new_len` is greater than `len`, the `Vec` is extended by the
3095 /// difference, with each additional slot filled with `value`.
3096 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
3097 ///
3098 /// This method requires `T` to implement [`Clone`],
3099 /// in order to be able to clone the passed value.
3100 /// If you need more flexibility (or want to rely on [`Default`] instead of
3101 /// [`Clone`]), use [`Vec::resize_with`].
3102 /// If you only need to resize to a smaller size, use [`Vec::truncate`].
3103 ///
3104 /// # Panics
3105 ///
3106 /// Panics if the new capacity exceeds `isize::MAX` _bytes_.
3107 ///
3108 /// # Examples
3109 ///
3110 /// ```
3111 /// let mut vec = vec!["hello"];
3112 /// vec.resize(3, "world");
3113 /// assert_eq!(vec, ["hello", "world", "world"]);
3114 ///
3115 /// let mut vec = vec!['a', 'b', 'c', 'd'];
3116 /// vec.resize(2, '_');
3117 /// assert_eq!(vec, ['a', 'b']);
3118 /// ```
3119 #[cfg(not(no_global_oom_handling))]
3120 #[stable(feature = "vec_resize", since = "1.5.0")]
3121 #[track_caller]
3122 pub fn resize(&mut self, new_len: usize, value: T) {
3123 let len = self.len();
3124
3125 if new_len > len {
3126 self.extend_with(new_len - len, value)
3127 } else {
3128 self.truncate(new_len);
3129 }
3130 }
3131
3132 /// Clones and appends all elements in a slice to the `Vec`.
3133 ///
3134 /// Iterates over the slice `other`, clones each element, and then appends
3135 /// it to this `Vec`. The `other` slice is traversed in-order.
3136 ///
3137 /// Note that this function is the same as [`extend`],
3138 /// except that it also works with slice elements that are Clone but not Copy.
3139 /// If Rust gets specialization this function may be deprecated.
3140 ///
3141 /// # Examples
3142 ///
3143 /// ```
3144 /// let mut vec = vec![1];
3145 /// vec.extend_from_slice(&[2, 3, 4]);
3146 /// assert_eq!(vec, [1, 2, 3, 4]);
3147 /// ```
3148 ///
3149 /// [`extend`]: Vec::extend
3150 #[cfg(not(no_global_oom_handling))]
3151 #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
3152 #[track_caller]
3153 pub fn extend_from_slice(&mut self, other: &[T]) {
3154 self.spec_extend(other.iter())
3155 }
3156
3157 /// Given a range `src`, clones a slice of elements in that range and appends it to the end.
3158 ///
3159 /// `src` must be a range that can form a valid subslice of the `Vec`.
3160 ///
3161 /// # Panics
3162 ///
3163 /// Panics if starting index is greater than the end index
3164 /// or if the index is greater than the length of the vector.
3165 ///
3166 /// # Examples
3167 ///
3168 /// ```
3169 /// let mut characters = vec!['a', 'b', 'c', 'd', 'e'];
3170 /// characters.extend_from_within(2..);
3171 /// assert_eq!(characters, ['a', 'b', 'c', 'd', 'e', 'c', 'd', 'e']);
3172 ///
3173 /// let mut numbers = vec![0, 1, 2, 3, 4];
3174 /// numbers.extend_from_within(..2);
3175 /// assert_eq!(numbers, [0, 1, 2, 3, 4, 0, 1]);
3176 ///
3177 /// let mut strings = vec![String::from("hello"), String::from("world"), String::from("!")];
3178 /// strings.extend_from_within(1..=2);
3179 /// assert_eq!(strings, ["hello", "world", "!", "world", "!"]);
3180 /// ```
3181 #[cfg(not(no_global_oom_handling))]
3182 #[stable(feature = "vec_extend_from_within", since = "1.53.0")]
3183 #[track_caller]
3184 pub fn extend_from_within<R>(&mut self, src: R)
3185 where
3186 R: RangeBounds<usize>,
3187 {
3188 let range = slice::range(src, ..self.len());
3189 self.reserve(range.len());
3190
3191 // SAFETY:
3192 // - `slice::range` guarantees that the given range is valid for indexing self
3193 unsafe {
3194 self.spec_extend_from_within(range);
3195 }
3196 }
3197}
3198
3199impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
3200 /// Takes a `Vec<[T; N]>` and flattens it into a `Vec<T>`.
3201 ///
3202 /// # Panics
3203 ///
3204 /// Panics if the length of the resulting vector would overflow a `usize`.
3205 ///
3206 /// This is only possible when flattening a vector of arrays of zero-sized
3207 /// types, and thus tends to be irrelevant in practice. If
3208 /// `size_of::<T>() > 0`, this will never panic.
3209 ///
3210 /// # Examples
3211 ///
3212 /// ```
3213 /// let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
3214 /// assert_eq!(vec.pop(), Some([7, 8, 9]));
3215 ///
3216 /// let mut flattened = vec.into_flattened();
3217 /// assert_eq!(flattened.pop(), Some(6));
3218 /// ```
3219 #[stable(feature = "slice_flatten", since = "1.80.0")]
3220 pub fn into_flattened(self) -> Vec<T, A> {
3221 let (ptr, len, cap, alloc) = self.into_raw_parts_with_alloc();
3222 let (new_len, new_cap) = if T::IS_ZST {
3223 (len.checked_mul(N).expect("vec len overflow"), usize::MAX)
3224 } else {
3225 // SAFETY:
3226 // - `cap * N` cannot overflow because the allocation is already in
3227 // the address space.
3228 // - Each `[T; N]` has `N` valid elements, so there are `len * N`
3229 // valid elements in the allocation.
3230 unsafe { (len.unchecked_mul(N), cap.unchecked_mul(N)) }
3231 };
3232 // SAFETY:
3233 // - `ptr` was allocated by `self`
3234 // - `ptr` is well-aligned because `[T; N]` has the same alignment as `T`.
3235 // - `new_cap` refers to the same sized allocation as `cap` because
3236 // `new_cap * size_of::<T>()` == `cap * size_of::<[T; N]>()`
3237 // - `len` <= `cap`, so `len * N` <= `cap * N`.
3238 unsafe { Vec::<T, A>::from_raw_parts_in(ptr.cast(), new_len, new_cap, alloc) }
3239 }
3240}
3241
3242impl<T: Clone, A: Allocator> Vec<T, A> {
3243 #[cfg(not(no_global_oom_handling))]
3244 #[track_caller]
3245 /// Extend the vector by `n` clones of value.
3246 fn extend_with(&mut self, n: usize, value: T) {
3247 self.reserve(n);
3248
3249 unsafe {
3250 let mut ptr = self.as_mut_ptr().add(self.len());
3251 // Use SetLenOnDrop to work around bug where compiler
3252 // might not realize the store through `ptr` through self.set_len()
3253 // don't alias.
3254 let mut local_len = SetLenOnDrop::new(&mut self.len);
3255
3256 // Write all elements except the last one
3257 for _ in 1..n {
3258 ptr::write(ptr, value.clone());
3259 ptr = ptr.add(1);
3260 // Increment the length in every step in case clone() panics
3261 local_len.increment_len(1);
3262 }
3263
3264 if n > 0 {
3265 // We can write the last element directly without cloning needlessly
3266 ptr::write(ptr, value);
3267 local_len.increment_len(1);
3268 }
3269
3270 // len set by scope guard
3271 }
3272 }
3273}
3274
3275impl<T: PartialEq, A: Allocator> Vec<T, A> {
3276 /// Removes consecutive repeated elements in the vector according to the
3277 /// [`PartialEq`] trait implementation.
3278 ///
3279 /// If the vector is sorted, this removes all duplicates.
3280 ///
3281 /// # Examples
3282 ///
3283 /// ```
3284 /// let mut vec = vec![1, 2, 2, 3, 2];
3285 ///
3286 /// vec.dedup();
3287 ///
3288 /// assert_eq!(vec, [1, 2, 3, 2]);
3289 /// ```
3290 #[stable(feature = "rust1", since = "1.0.0")]
3291 #[inline]
3292 pub fn dedup(&mut self) {
3293 self.dedup_by(|a, b| a == b)
3294 }
3295}
3296
3297////////////////////////////////////////////////////////////////////////////////
3298// Internal methods and functions
3299////////////////////////////////////////////////////////////////////////////////
3300
3301#[doc(hidden)]
3302#[cfg(not(no_global_oom_handling))]
3303#[stable(feature = "rust1", since = "1.0.0")]
3304#[rustc_diagnostic_item = "vec_from_elem"]
3305#[track_caller]
3306pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
3307 <T as SpecFromElem>::from_elem(elem, n, Global)
3308}
3309
3310#[doc(hidden)]
3311#[cfg(not(no_global_oom_handling))]
3312#[unstable(feature = "allocator_api", issue = "32838")]
3313#[track_caller]
3314pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> {
3315 <T as SpecFromElem>::from_elem(elem, n, alloc)
3316}
3317
3318#[cfg(not(no_global_oom_handling))]
3319trait ExtendFromWithinSpec {
3320 /// # Safety
3321 ///
3322 /// - `src` needs to be valid index
3323 /// - `self.capacity() - self.len()` must be `>= src.len()`
3324 unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
3325}
3326
3327#[cfg(not(no_global_oom_handling))]
3328impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
3329 default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
3330 // SAFETY:
3331 // - len is increased only after initializing elements
3332 let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() };
3333
3334 // SAFETY:
3335 // - caller guarantees that src is a valid index
3336 let to_clone = unsafe { this.get_unchecked(src) };
3337
3338 iter::zip(to_clone, spare)
3339 .map(|(src, dst)| dst.write(src.clone()))
3340 // Note:
3341 // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len
3342 // - len is increased after each element to prevent leaks (see issue #82533)
3343 .for_each(|_| *len += 1);
3344 }
3345}
3346
3347#[cfg(not(no_global_oom_handling))]
3348impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
3349 unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
3350 let count = src.len();
3351 {
3352 let (init, spare) = self.split_at_spare_mut();
3353
3354 // SAFETY:
3355 // - caller guarantees that `src` is a valid index
3356 let source = unsafe { init.get_unchecked(src) };
3357
3358 // SAFETY:
3359 // - Both pointers are created from unique slice references (`&mut [_]`)
3360 // so they are valid and do not overlap.
3361 // - Elements are :Copy so it's OK to copy them, without doing
3362 // anything with the original values
3363 // - `count` is equal to the len of `source`, so source is valid for
3364 // `count` reads
3365 // - `.reserve(count)` guarantees that `spare.len() >= count` so spare
3366 // is valid for `count` writes
3367 unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) };
3368 }
3369
3370 // SAFETY:
3371 // - The elements were just initialized by `copy_nonoverlapping`
3372 self.len += count;
3373 }
3374}
3375
3376////////////////////////////////////////////////////////////////////////////////
3377// Common trait implementations for Vec
3378////////////////////////////////////////////////////////////////////////////////
3379
3380#[stable(feature = "rust1", since = "1.0.0")]
3381impl<T, A: Allocator> ops::Deref for Vec<T, A> {
3382 type Target = [T];
3383
3384 #[inline]
3385 fn deref(&self) -> &[T] {
3386 self.as_slice()
3387 }
3388}
3389
3390#[stable(feature = "rust1", since = "1.0.0")]
3391impl<T, A: Allocator> ops::DerefMut for Vec<T, A> {
3392 #[inline]
3393 fn deref_mut(&mut self) -> &mut [T] {
3394 self.as_mut_slice()
3395 }
3396}
3397
3398#[unstable(feature = "deref_pure_trait", issue = "87121")]
3399unsafe impl<T, A: Allocator> ops::DerefPure for Vec<T, A> {}
3400
3401#[cfg(not(no_global_oom_handling))]
3402#[stable(feature = "rust1", since = "1.0.0")]
3403impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
3404 #[track_caller]
3405 fn clone(&self) -> Self {
3406 let alloc = self.allocator().clone();
3407 <[T]>::to_vec_in(&**self, alloc)
3408 }
3409
3410 /// Overwrites the contents of `self` with a clone of the contents of `source`.
3411 ///
3412 /// This method is preferred over simply assigning `source.clone()` to `self`,
3413 /// as it avoids reallocation if possible. Additionally, if the element type
3414 /// `T` overrides `clone_from()`, this will reuse the resources of `self`'s
3415 /// elements as well.
3416 ///
3417 /// # Examples
3418 ///
3419 /// ```
3420 /// let x = vec![5, 6, 7];
3421 /// let mut y = vec![8, 9, 10];
3422 /// let yp: *const i32 = y.as_ptr();
3423 ///
3424 /// y.clone_from(&x);
3425 ///
3426 /// // The value is the same
3427 /// assert_eq!(x, y);
3428 ///
3429 /// // And no reallocation occurred
3430 /// assert_eq!(yp, y.as_ptr());
3431 /// ```
3432 #[track_caller]
3433 fn clone_from(&mut self, source: &Self) {
3434 crate::slice::SpecCloneIntoVec::clone_into(source.as_slice(), self);
3435 }
3436}
3437
3438/// The hash of a vector is the same as that of the corresponding slice,
3439/// as required by the `core::borrow::Borrow` implementation.
3440///
3441/// ```
3442/// use std::hash::BuildHasher;
3443///
3444/// let b = std::hash::RandomState::new();
3445/// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09];
3446/// let s: &[u8] = &[0xa8, 0x3c, 0x09];
3447/// assert_eq!(b.hash_one(v), b.hash_one(s));
3448/// ```
3449#[stable(feature = "rust1", since = "1.0.0")]
3450impl<T: Hash, A: Allocator> Hash for Vec<T, A> {
3451 #[inline]
3452 fn hash<H: Hasher>(&self, state: &mut H) {
3453 Hash::hash(&**self, state)
3454 }
3455}
3456
3457#[stable(feature = "rust1", since = "1.0.0")]
3458impl<T, I: SliceIndex<[T]>, A: Allocator> Index<I> for Vec<T, A> {
3459 type Output = I::Output;
3460
3461 #[inline]
3462 fn index(&self, index: I) -> &Self::Output {
3463 Index::index(&**self, index)
3464 }
3465}
3466
3467#[stable(feature = "rust1", since = "1.0.0")]
3468impl<T, I: SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> {
3469 #[inline]
3470 fn index_mut(&mut self, index: I) -> &mut Self::Output {
3471 IndexMut::index_mut(&mut **self, index)
3472 }
3473}
3474
3475/// Collects an iterator into a Vec, commonly called via [`Iterator::collect()`]
3476///
3477/// # Allocation behavior
3478///
3479/// In general `Vec` does not guarantee any particular growth or allocation strategy.
3480/// That also applies to this trait impl.
3481///
3482/// **Note:** This section covers implementation details and is therefore exempt from
3483/// stability guarantees.
3484///
3485/// Vec may use any or none of the following strategies,
3486/// depending on the supplied iterator:
3487///
3488/// * preallocate based on [`Iterator::size_hint()`]
3489/// * and panic if the number of items is outside the provided lower/upper bounds
3490/// * use an amortized growth strategy similar to `pushing` one item at a time
3491/// * perform the iteration in-place on the original allocation backing the iterator
3492///
3493/// The last case warrants some attention. It is an optimization that in many cases reduces peak memory
3494/// consumption and improves cache locality. But when big, short-lived allocations are created,
3495/// only a small fraction of their items get collected, no further use is made of the spare capacity
3496/// and the resulting `Vec` is moved into a longer-lived structure, then this can lead to the large
3497/// allocations having their lifetimes unnecessarily extended which can result in increased memory
3498/// footprint.
3499///
3500/// In cases where this is an issue, the excess capacity can be discarded with [`Vec::shrink_to()`],
3501/// [`Vec::shrink_to_fit()`] or by collecting into [`Box<[T]>`][owned slice] instead, which additionally reduces
3502/// the size of the long-lived struct.
3503///
3504/// [owned slice]: Box
3505///
3506/// ```rust
3507/// # use std::sync::Mutex;
3508/// static LONG_LIVED: Mutex<Vec<Vec<u16>>> = Mutex::new(Vec::new());
3509///
3510/// for i in 0..10 {
3511/// let big_temporary: Vec<u16> = (0..1024).collect();
3512/// // discard most items
3513/// let mut result: Vec<_> = big_temporary.into_iter().filter(|i| i % 100 == 0).collect();
3514/// // without this a lot of unused capacity might be moved into the global
3515/// result.shrink_to_fit();
3516/// LONG_LIVED.lock().unwrap().push(result);
3517/// }
3518/// ```
3519#[cfg(not(no_global_oom_handling))]
3520#[stable(feature = "rust1", since = "1.0.0")]
3521impl<T> FromIterator<T> for Vec<T> {
3522 #[inline]
3523 #[track_caller]
3524 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
3525 <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter())
3526 }
3527}
3528
3529#[stable(feature = "rust1", since = "1.0.0")]
3530impl<T, A: Allocator> IntoIterator for Vec<T, A> {
3531 type Item = T;
3532 type IntoIter = IntoIter<T, A>;
3533
3534 /// Creates a consuming iterator, that is, one that moves each value out of
3535 /// the vector (from start to end). The vector cannot be used after calling
3536 /// this.
3537 ///
3538 /// # Examples
3539 ///
3540 /// ```
3541 /// let v = vec!["a".to_string(), "b".to_string()];
3542 /// let mut v_iter = v.into_iter();
3543 ///
3544 /// let first_element: Option<String> = v_iter.next();
3545 ///
3546 /// assert_eq!(first_element, Some("a".to_string()));
3547 /// assert_eq!(v_iter.next(), Some("b".to_string()));
3548 /// assert_eq!(v_iter.next(), None);
3549 /// ```
3550 #[inline]
3551 fn into_iter(self) -> Self::IntoIter {
3552 unsafe {
3553 let me = ManuallyDrop::new(self);
3554 let alloc = ManuallyDrop::new(ptr::read(me.allocator()));
3555 let buf = me.buf.non_null();
3556 let begin = buf.as_ptr();
3557 let end = if T::IS_ZST {
3558 begin.wrapping_byte_add(me.len())
3559 } else {
3560 begin.add(me.len()) as *const T
3561 };
3562 let cap = me.buf.capacity();
3563 IntoIter { buf, phantom: PhantomData, cap, alloc, ptr: buf, end }
3564 }
3565 }
3566}
3567
3568#[stable(feature = "rust1", since = "1.0.0")]
3569impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> {
3570 type Item = &'a T;
3571 type IntoIter = slice::Iter<'a, T>;
3572
3573 fn into_iter(self) -> Self::IntoIter {
3574 self.iter()
3575 }
3576}
3577
3578#[stable(feature = "rust1", since = "1.0.0")]
3579impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> {
3580 type Item = &'a mut T;
3581 type IntoIter = slice::IterMut<'a, T>;
3582
3583 fn into_iter(self) -> Self::IntoIter {
3584 self.iter_mut()
3585 }
3586}
3587
3588#[cfg(not(no_global_oom_handling))]
3589#[stable(feature = "rust1", since = "1.0.0")]
3590impl<T, A: Allocator> Extend<T> for Vec<T, A> {
3591 #[inline]
3592 #[track_caller]
3593 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
3594 <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
3595 }
3596
3597 #[inline]
3598 #[track_caller]
3599 fn extend_one(&mut self, item: T) {
3600 self.push(item);
3601 }
3602
3603 #[inline]
3604 #[track_caller]
3605 fn extend_reserve(&mut self, additional: usize) {
3606 self.reserve(additional);
3607 }
3608
3609 #[inline]
3610 unsafe fn extend_one_unchecked(&mut self, item: T) {
3611 // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
3612 unsafe {
3613 let len = self.len();
3614 ptr::write(self.as_mut_ptr().add(len), item);
3615 self.set_len(len + 1);
3616 }
3617 }
3618}
3619
3620impl<T, A: Allocator> Vec<T, A> {
3621 // leaf method to which various SpecFrom/SpecExtend implementations delegate when
3622 // they have no further optimizations to apply
3623 #[cfg(not(no_global_oom_handling))]
3624 #[track_caller]
3625 fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
3626 // This is the case for a general iterator.
3627 //
3628 // This function should be the moral equivalent of:
3629 //
3630 // for item in iterator {
3631 // self.push(item);
3632 // }
3633 while let Some(element) = iterator.next() {
3634 let len = self.len();
3635 if len == self.capacity() {
3636 let (lower, _) = iterator.size_hint();
3637 self.reserve(lower.saturating_add(1));
3638 }
3639 unsafe {
3640 ptr::write(self.as_mut_ptr().add(len), element);
3641 // Since next() executes user code which can panic we have to bump the length
3642 // after each step.
3643 // NB can't overflow since we would have had to alloc the address space
3644 self.set_len(len + 1);
3645 }
3646 }
3647 }
3648
3649 // specific extend for `TrustedLen` iterators, called both by the specializations
3650 // and internal places where resolving specialization makes compilation slower
3651 #[cfg(not(no_global_oom_handling))]
3652 #[track_caller]
3653 fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
3654 let (low, high) = iterator.size_hint();
3655 if let Some(additional) = high {
3656 debug_assert_eq!(
3657 low,
3658 additional,
3659 "TrustedLen iterator's size hint is not exact: {:?}",
3660 (low, high)
3661 );
3662 self.reserve(additional);
3663 unsafe {
3664 let ptr = self.as_mut_ptr();
3665 let mut local_len = SetLenOnDrop::new(&mut self.len);
3666 iterator.for_each(move |element| {
3667 ptr::write(ptr.add(local_len.current_len()), element);
3668 // Since the loop executes user code which can panic we have to update
3669 // the length every step to correctly drop what we've written.
3670 // NB can't overflow since we would have had to alloc the address space
3671 local_len.increment_len(1);
3672 });
3673 }
3674 } else {
3675 // Per TrustedLen contract a `None` upper bound means that the iterator length
3676 // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway.
3677 // Since the other branch already panics eagerly (via `reserve()`) we do the same here.
3678 // This avoids additional codegen for a fallback code path which would eventually
3679 // panic anyway.
3680 panic!("capacity overflow");
3681 }
3682 }
3683
3684 /// Creates a splicing iterator that replaces the specified range in the vector
3685 /// with the given `replace_with` iterator and yields the removed items.
3686 /// `replace_with` does not need to be the same length as `range`.
3687 ///
3688 /// `range` is removed even if the `Splice` iterator is not consumed before it is dropped.
3689 ///
3690 /// It is unspecified how many elements are removed from the vector
3691 /// if the `Splice` value is leaked.
3692 ///
3693 /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
3694 ///
3695 /// This is optimal if:
3696 ///
3697 /// * The tail (elements in the vector after `range`) is empty,
3698 /// * or `replace_with` yields fewer or equal elements than `range`’s length
3699 /// * or the lower bound of its `size_hint()` is exact.
3700 ///
3701 /// Otherwise, a temporary vector is allocated and the tail is moved twice.
3702 ///
3703 /// # Panics
3704 ///
3705 /// Panics if the starting point is greater than the end point or if
3706 /// the end point is greater than the length of the vector.
3707 ///
3708 /// # Examples
3709 ///
3710 /// ```
3711 /// let mut v = vec![1, 2, 3, 4];
3712 /// let new = [7, 8, 9];
3713 /// let u: Vec<_> = v.splice(1..3, new).collect();
3714 /// assert_eq!(v, [1, 7, 8, 9, 4]);
3715 /// assert_eq!(u, [2, 3]);
3716 /// ```
3717 ///
3718 /// Using `splice` to insert new items into a vector efficiently at a specific position
3719 /// indicated by an empty range:
3720 ///
3721 /// ```
3722 /// let mut v = vec![1, 5];
3723 /// let new = [2, 3, 4];
3724 /// v.splice(1..1, new);
3725 /// assert_eq!(v, [1, 2, 3, 4, 5]);
3726 /// ```
3727 #[cfg(not(no_global_oom_handling))]
3728 #[inline]
3729 #[stable(feature = "vec_splice", since = "1.21.0")]
3730 pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
3731 where
3732 R: RangeBounds<usize>,
3733 I: IntoIterator<Item = T>,
3734 {
3735 Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
3736 }
3737
3738 /// Creates an iterator which uses a closure to determine if an element in the range should be removed.
3739 ///
3740 /// If the closure returns `true`, the element is removed from the vector
3741 /// and yielded. If the closure returns `false`, or panics, the element
3742 /// remains in the vector and will not be yielded.
3743 ///
3744 /// Only elements that fall in the provided range are considered for extraction, but any elements
3745 /// after the range will still have to be moved if any element has been extracted.
3746 ///
3747 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
3748 /// or the iteration short-circuits, then the remaining elements will be retained.
3749 /// Use [`retain_mut`] with a negated predicate if you do not need the returned iterator.
3750 ///
3751 /// [`retain_mut`]: Vec::retain_mut
3752 ///
3753 /// Using this method is equivalent to the following code:
3754 ///
3755 /// ```
3756 /// # let some_predicate = |x: &mut i32| { *x % 2 == 1 };
3757 /// # let mut vec = vec![0, 1, 2, 3, 4, 5, 6];
3758 /// # let mut vec2 = vec.clone();
3759 /// # let range = 1..5;
3760 /// let mut i = range.start;
3761 /// let end_items = vec.len() - range.end;
3762 /// # let mut extracted = vec![];
3763 ///
3764 /// while i < vec.len() - end_items {
3765 /// if some_predicate(&mut vec[i]) {
3766 /// let val = vec.remove(i);
3767 /// # extracted.push(val);
3768 /// // your code here
3769 /// } else {
3770 /// i += 1;
3771 /// }
3772 /// }
3773 ///
3774 /// # let extracted2: Vec<_> = vec2.extract_if(range, some_predicate).collect();
3775 /// # assert_eq!(vec, vec2);
3776 /// # assert_eq!(extracted, extracted2);
3777 /// ```
3778 ///
3779 /// But `extract_if` is easier to use. `extract_if` is also more efficient,
3780 /// because it can backshift the elements of the array in bulk.
3781 ///
3782 /// The iterator also lets you mutate the value of each element in the
3783 /// closure, regardless of whether you choose to keep or remove it.
3784 ///
3785 /// # Panics
3786 ///
3787 /// If `range` is out of bounds.
3788 ///
3789 /// # Examples
3790 ///
3791 /// Splitting a vector into even and odd values, reusing the original vector:
3792 ///
3793 /// ```
3794 /// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];
3795 ///
3796 /// let evens = numbers.extract_if(.., |x| *x % 2 == 0).collect::<Vec<_>>();
3797 /// let odds = numbers;
3798 ///
3799 /// assert_eq!(evens, vec![2, 4, 6, 8, 14]);
3800 /// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]);
3801 /// ```
3802 ///
3803 /// Using the range argument to only process a part of the vector:
3804 ///
3805 /// ```
3806 /// let mut items = vec![0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2];
3807 /// let ones = items.extract_if(7.., |x| *x == 1).collect::<Vec<_>>();
3808 /// assert_eq!(items, vec![0, 0, 0, 0, 0, 0, 0, 2, 2, 2]);
3809 /// assert_eq!(ones.len(), 3);
3810 /// ```
3811 #[stable(feature = "extract_if", since = "1.87.0")]
3812 pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, A>
3813 where
3814 F: FnMut(&mut T) -> bool,
3815 R: RangeBounds<usize>,
3816 {
3817 ExtractIf::new(self, filter, range)
3818 }
3819}
3820
3821/// Extend implementation that copies elements out of references before pushing them onto the Vec.
3822///
3823/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
3824/// append the entire slice at once.
3825///
3826/// [`copy_from_slice`]: slice::copy_from_slice
3827#[cfg(not(no_global_oom_handling))]
3828#[stable(feature = "extend_ref", since = "1.2.0")]
3829impl<'a, T: Copy + 'a, A: Allocator> Extend<&'a T> for Vec<T, A> {
3830 #[track_caller]
3831 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
3832 self.spec_extend(iter.into_iter())
3833 }
3834
3835 #[inline]
3836 #[track_caller]
3837 fn extend_one(&mut self, &item: &'a T) {
3838 self.push(item);
3839 }
3840
3841 #[inline]
3842 #[track_caller]
3843 fn extend_reserve(&mut self, additional: usize) {
3844 self.reserve(additional);
3845 }
3846
3847 #[inline]
3848 unsafe fn extend_one_unchecked(&mut self, &item: &'a T) {
3849 // SAFETY: Our preconditions ensure the space has been reserved, and `extend_reserve` is implemented correctly.
3850 unsafe {
3851 let len = self.len();
3852 ptr::write(self.as_mut_ptr().add(len), item);
3853 self.set_len(len + 1);
3854 }
3855 }
3856}
3857
3858/// Implements comparison of vectors, [lexicographically](Ord#lexicographical-comparison).
3859#[stable(feature = "rust1", since = "1.0.0")]
3860impl<T, A1, A2> PartialOrd<Vec<T, A2>> for Vec<T, A1>
3861where
3862 T: PartialOrd,
3863 A1: Allocator,
3864 A2: Allocator,
3865{
3866 #[inline]
3867 fn partial_cmp(&self, other: &Vec<T, A2>) -> Option<Ordering> {
3868 PartialOrd::partial_cmp(&**self, &**other)
3869 }
3870}
3871
3872#[stable(feature = "rust1", since = "1.0.0")]
3873impl<T: Eq, A: Allocator> Eq for Vec<T, A> {}
3874
3875/// Implements ordering of vectors, [lexicographically](Ord#lexicographical-comparison).
3876#[stable(feature = "rust1", since = "1.0.0")]
3877impl<T: Ord, A: Allocator> Ord for Vec<T, A> {
3878 #[inline]
3879 fn cmp(&self, other: &Self) -> Ordering {
3880 Ord::cmp(&**self, &**other)
3881 }
3882}
3883
3884#[stable(feature = "rust1", since = "1.0.0")]
3885unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> {
3886 fn drop(&mut self) {
3887 unsafe {
3888 // use drop for [T]
3889 // use a raw slice to refer to the elements of the vector as weakest necessary type;
3890 // could avoid questions of validity in certain cases
3891 ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
3892 }
3893 // RawVec handles deallocation
3894 }
3895}
3896
3897#[stable(feature = "rust1", since = "1.0.0")]
3898#[rustc_const_unstable(feature = "const_default", issue = "67792")]
3899impl<T> const Default for Vec<T> {
3900 /// Creates an empty `Vec<T>`.
3901 ///
3902 /// The vector will not allocate until elements are pushed onto it.
3903 fn default() -> Vec<T> {
3904 Vec::new()
3905 }
3906}
3907
3908#[stable(feature = "rust1", since = "1.0.0")]
3909impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
3910 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3911 fmt::Debug::fmt(&**self, f)
3912 }
3913}
3914
3915#[stable(feature = "rust1", since = "1.0.0")]
3916impl<T, A: Allocator> AsRef<Vec<T, A>> for Vec<T, A> {
3917 fn as_ref(&self) -> &Vec<T, A> {
3918 self
3919 }
3920}
3921
3922#[stable(feature = "vec_as_mut", since = "1.5.0")]
3923impl<T, A: Allocator> AsMut<Vec<T, A>> for Vec<T, A> {
3924 fn as_mut(&mut self) -> &mut Vec<T, A> {
3925 self
3926 }
3927}
3928
3929#[stable(feature = "rust1", since = "1.0.0")]
3930impl<T, A: Allocator> AsRef<[T]> for Vec<T, A> {
3931 fn as_ref(&self) -> &[T] {
3932 self
3933 }
3934}
3935
3936#[stable(feature = "vec_as_mut", since = "1.5.0")]
3937impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> {
3938 fn as_mut(&mut self) -> &mut [T] {
3939 self
3940 }
3941}
3942
3943#[cfg(not(no_global_oom_handling))]
3944#[stable(feature = "rust1", since = "1.0.0")]
3945impl<T: Clone> From<&[T]> for Vec<T> {
3946 /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
3947 ///
3948 /// # Examples
3949 ///
3950 /// ```
3951 /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);
3952 /// ```
3953 #[track_caller]
3954 fn from(s: &[T]) -> Vec<T> {
3955 s.to_vec()
3956 }
3957}
3958
3959#[cfg(not(no_global_oom_handling))]
3960#[stable(feature = "vec_from_mut", since = "1.19.0")]
3961impl<T: Clone> From<&mut [T]> for Vec<T> {
3962 /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
3963 ///
3964 /// # Examples
3965 ///
3966 /// ```
3967 /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]);
3968 /// ```
3969 #[track_caller]
3970 fn from(s: &mut [T]) -> Vec<T> {
3971 s.to_vec()
3972 }
3973}
3974
3975#[cfg(not(no_global_oom_handling))]
3976#[stable(feature = "vec_from_array_ref", since = "1.74.0")]
3977impl<T: Clone, const N: usize> From<&[T; N]> for Vec<T> {
3978 /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
3979 ///
3980 /// # Examples
3981 ///
3982 /// ```
3983 /// assert_eq!(Vec::from(&[1, 2, 3]), vec![1, 2, 3]);
3984 /// ```
3985 #[track_caller]
3986 fn from(s: &[T; N]) -> Vec<T> {
3987 Self::from(s.as_slice())
3988 }
3989}
3990
3991#[cfg(not(no_global_oom_handling))]
3992#[stable(feature = "vec_from_array_ref", since = "1.74.0")]
3993impl<T: Clone, const N: usize> From<&mut [T; N]> for Vec<T> {
3994 /// Allocates a `Vec<T>` and fills it by cloning `s`'s items.
3995 ///
3996 /// # Examples
3997 ///
3998 /// ```
3999 /// assert_eq!(Vec::from(&mut [1, 2, 3]), vec![1, 2, 3]);
4000 /// ```
4001 #[track_caller]
4002 fn from(s: &mut [T; N]) -> Vec<T> {
4003 Self::from(s.as_mut_slice())
4004 }
4005}
4006
4007#[cfg(not(no_global_oom_handling))]
4008#[stable(feature = "vec_from_array", since = "1.44.0")]
4009impl<T, const N: usize> From<[T; N]> for Vec<T> {
4010 /// Allocates a `Vec<T>` and moves `s`'s items into it.
4011 ///
4012 /// # Examples
4013 ///
4014 /// ```
4015 /// assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]);
4016 /// ```
4017 #[track_caller]
4018 fn from(s: [T; N]) -> Vec<T> {
4019 <[T]>::into_vec(Box::new(s))
4020 }
4021}
4022
4023#[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
4024impl<'a, T> From<Cow<'a, [T]>> for Vec<T>
4025where
4026 [T]: ToOwned<Owned = Vec<T>>,
4027{
4028 /// Converts a clone-on-write slice into a vector.
4029 ///
4030 /// If `s` already owns a `Vec<T>`, it will be returned directly.
4031 /// If `s` is borrowing a slice, a new `Vec<T>` will be allocated and
4032 /// filled by cloning `s`'s items into it.
4033 ///
4034 /// # Examples
4035 ///
4036 /// ```
4037 /// # use std::borrow::Cow;
4038 /// let o: Cow<'_, [i32]> = Cow::Owned(vec![1, 2, 3]);
4039 /// let b: Cow<'_, [i32]> = Cow::Borrowed(&[1, 2, 3]);
4040 /// assert_eq!(Vec::from(o), Vec::from(b));
4041 /// ```
4042 #[track_caller]
4043 fn from(s: Cow<'a, [T]>) -> Vec<T> {
4044 s.into_owned()
4045 }
4046}
4047
4048// note: test pulls in std, which causes errors here
4049#[stable(feature = "vec_from_box", since = "1.18.0")]
4050impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> {
4051 /// Converts a boxed slice into a vector by transferring ownership of
4052 /// the existing heap allocation.
4053 ///
4054 /// # Examples
4055 ///
4056 /// ```
4057 /// let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice();
4058 /// assert_eq!(Vec::from(b), vec![1, 2, 3]);
4059 /// ```
4060 fn from(s: Box<[T], A>) -> Self {
4061 s.into_vec()
4062 }
4063}
4064
4065// note: test pulls in std, which causes errors here
4066#[cfg(not(no_global_oom_handling))]
4067#[stable(feature = "box_from_vec", since = "1.20.0")]
4068impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> {
4069 /// Converts a vector into a boxed slice.
4070 ///
4071 /// Before doing the conversion, this method discards excess capacity like [`Vec::shrink_to_fit`].
4072 ///
4073 /// [owned slice]: Box
4074 /// [`Vec::shrink_to_fit`]: Vec::shrink_to_fit
4075 ///
4076 /// # Examples
4077 ///
4078 /// ```
4079 /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice());
4080 /// ```
4081 ///
4082 /// Any excess capacity is removed:
4083 /// ```
4084 /// let mut vec = Vec::with_capacity(10);
4085 /// vec.extend([1, 2, 3]);
4086 ///
4087 /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice());
4088 /// ```
4089 #[track_caller]
4090 fn from(v: Vec<T, A>) -> Self {
4091 v.into_boxed_slice()
4092 }
4093}
4094
4095#[cfg(not(no_global_oom_handling))]
4096#[stable(feature = "rust1", since = "1.0.0")]
4097impl From<&str> for Vec<u8> {
4098 /// Allocates a `Vec<u8>` and fills it with a UTF-8 string.
4099 ///
4100 /// # Examples
4101 ///
4102 /// ```
4103 /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);
4104 /// ```
4105 #[track_caller]
4106 fn from(s: &str) -> Vec<u8> {
4107 From::from(s.as_bytes())
4108 }
4109}
4110
4111#[stable(feature = "array_try_from_vec", since = "1.48.0")]
4112impl<T, A: Allocator, const N: usize> TryFrom<Vec<T, A>> for [T; N] {
4113 type Error = Vec<T, A>;
4114
4115 /// Gets the entire contents of the `Vec<T>` as an array,
4116 /// if its size exactly matches that of the requested array.
4117 ///
4118 /// # Examples
4119 ///
4120 /// ```
4121 /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3]));
4122 /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([]));
4123 /// ```
4124 ///
4125 /// If the length doesn't match, the input comes back in `Err`:
4126 /// ```
4127 /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into();
4128 /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
4129 /// ```
4130 ///
4131 /// If you're fine with just getting a prefix of the `Vec<T>`,
4132 /// you can call [`.truncate(N)`](Vec::truncate) first.
4133 /// ```
4134 /// let mut v = String::from("hello world").into_bytes();
4135 /// v.sort();
4136 /// v.truncate(2);
4137 /// let [a, b]: [_; 2] = v.try_into().unwrap();
4138 /// assert_eq!(a, b' ');
4139 /// assert_eq!(b, b'd');
4140 /// ```
4141 fn try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>> {
4142 if vec.len() != N {
4143 return Err(vec);
4144 }
4145
4146 // SAFETY: `.set_len(0)` is always sound.
4147 unsafe { vec.set_len(0) };
4148
4149 // SAFETY: A `Vec`'s pointer is always aligned properly, and
4150 // the alignment the array needs is the same as the items.
4151 // We checked earlier that we have sufficient items.
4152 // The items will not double-drop as the `set_len`
4153 // tells the `Vec` not to also drop them.
4154 let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) };
4155 Ok(array)
4156 }
4157}