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