// SPDX-License-Identifier: Apache-2.0 OR MIT

//! A contiguous growable array type with heap-allocated contents, written

//! `Vec<T>`.

//!

//! Vectors have *O*(1) indexing, amortized *O*(1) push (to the end) and

//! *O*(1) pop (from the end).

//!

//! Vectors ensure they never allocate more than `isize::MAX` bytes.

//!

//! # Examples

//!

//! You can explicitly create a [`Vec`] with [`Vec::new`]:

//!

//! ```

//! let v: Vec<i32> = Vec::new();

//! ```

//!

//! ...or by using the [`vec!`] macro:

//!

//! ```

//! let v: Vec<i32> = vec![];

//!

//! let v = vec![1, 2, 3, 4, 5];

//!

//! let v = vec![0; 10]; // ten zeroes

//! ```

//!

//! You can [`push`] values onto the end of a vector (which will grow the vector

//! as needed):

//!

//! ```

//! let mut v = vec![1, 2];

//!

//! v.push(3);

//! ```

//!

//! Popping values works in much the same way:

//!

//! ```

//! let mut v = vec![1, 2];

//!

//! let two = v.pop();

//! ```

//!

//! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits):

//!

//! ```

//! let mut v = vec![1, 2, 3];

//! let three = v[2];

//! v[1] = v[1] + 5;

//! ```

//!

//! [`push`]: Vec::push

#![stable(feature = "rust1", since = "1.0.0")]

#[cfg(not(no_global_oom_handling))]

use core::cmp;

use core::cmp::Ordering;

use core::convert::TryFrom;

use core::fmt;

use core::hash::{Hash, Hasher};

use core::intrinsics::{arith_offset, assume};

use core::iter;

#[cfg(not(no_global_oom_handling))]

use core::iter::FromIterator;

use core::marker::PhantomData;

use core::mem::{self, ManuallyDrop, MaybeUninit};

use core::ops::{self, Index, IndexMut, Range, RangeBounds};

use core::ptr::{self, NonNull};

use core::slice::{self, SliceIndex};

use crate::alloc::{Allocator, Global};

use crate::borrow::{Cow, ToOwned};

use crate::boxed::Box;

use crate::collections::TryReserveError;

use crate::raw_vec::RawVec;

#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]

pub use self::drain_filter::DrainFilter;

mod drain_filter;

#[cfg(not(no_global_oom_handling))]

#[stable(feature = "vec_splice", since = "1.21.0")]

pub use self::splice::Splice;

#[cfg(not(no_global_oom_handling))]

mod splice;

#[stable(feature = "drain", since = "1.6.0")]

pub use self::drain::Drain;

mod drain;

#[cfg(not(no_global_oom_handling))]

mod cow;

#[cfg(not(no_global_oom_handling))]

pub(crate) use self::in_place_collect::AsVecIntoIter;

#[stable(feature = "rust1", since = "1.0.0")]

pub use self::into_iter::IntoIter;

mod into_iter;

#[cfg(not(no_global_oom_handling))]

use self::is_zero::IsZero;

mod is_zero;

#[cfg(not(no_global_oom_handling))]

mod in_place_collect;

mod partial_eq;

#[cfg(not(no_global_oom_handling))]

use self::spec_from_elem::SpecFromElem;

#[cfg(not(no_global_oom_handling))]

mod spec_from_elem;

#[cfg(not(no_global_oom_handling))]

use self::set_len_on_drop::SetLenOnDrop;

#[cfg(not(no_global_oom_handling))]

mod set_len_on_drop;

#[cfg(not(no_global_oom_handling))]

use self::in_place_drop::InPlaceDrop;

#[cfg(not(no_global_oom_handling))]

mod in_place_drop;

#[cfg(not(no_global_oom_handling))]

use self::spec_from_iter_nested::SpecFromIterNested;

#[cfg(not(no_global_oom_handling))]

mod spec_from_iter_nested;

#[cfg(not(no_global_oom_handling))]

use self::spec_from_iter::SpecFromIter;

#[cfg(not(no_global_oom_handling))]

mod spec_from_iter;

#[cfg(not(no_global_oom_handling))]

use self::spec_extend::SpecExtend;

#[cfg(not(no_global_oom_handling))]

mod spec_extend;

/// A contiguous growable array type, written as `Vec<T>`, short for 'vector'.

///

/// # Examples

///

/// ```

/// let mut vec = Vec::new();

/// vec.push(1);

/// vec.push(2);

///

/// assert_eq!(vec.len(), 2);

/// assert_eq!(vec[0], 1);

///

/// assert_eq!(vec.pop(), Some(2));

/// assert_eq!(vec.len(), 1);

///

/// vec[0] = 7;

/// assert_eq!(vec[0], 7);

///

/// vec.extend([1, 2, 3].iter().copied());

///

/// for x in &vec {

/// println!("{x}");

/// }

/// assert_eq!(vec, [7, 1, 2, 3]);

/// ```

///

/// The [`vec!`] macro is provided for convenient initialization:

///

/// ```

/// let mut vec1 = vec![1, 2, 3];

/// vec1.push(4);

/// let vec2 = Vec::from([1, 2, 3, 4]);

/// assert_eq!(vec1, vec2);

/// ```

///

/// It can also initialize each element of a `Vec<T>` with a given value.

/// This may be more efficient than performing allocation and initialization

/// in separate steps, especially when initializing a vector of zeros:

///

/// ```

/// let vec = vec![0; 5];

/// assert_eq!(vec, [0, 0, 0, 0, 0]);

///

/// // The following is equivalent, but potentially slower:

/// let mut vec = Vec::with_capacity(5);

/// vec.resize(5, 0);

/// assert_eq!(vec, [0, 0, 0, 0, 0]);

/// ```

///

/// For more information, see

/// [Capacity and Reallocation](#capacity-and-reallocation).

///

/// Use a `Vec<T>` as an efficient stack:

///

/// ```

/// let mut stack = Vec::new();

///

/// stack.push(1);

/// stack.push(2);

/// stack.push(3);

///

/// while let Some(top) = stack.pop() {

/// // Prints 3, 2, 1

/// println!("{top}");

/// }

/// ```

///

/// # Indexing

///

/// The `Vec` type allows to access values by index, because it implements the

/// [`Index`] trait. An example will be more explicit:

///

/// ```

/// let v = vec![0, 2, 4, 6];

/// println!("{}", v[1]); // it will display '2'

/// ```

///

/// However be careful: if you try to access an index which isn't in the `Vec`,

/// your software will panic! You cannot do this:

///

/// ```should_panic

/// let v = vec![0, 2, 4, 6];

/// println!("{}", v[6]); // it will panic!

/// ```

///

/// Use [`get`] and [`get_mut`] if you want to check whether the index is in

/// the `Vec`.

///

/// # Slicing

///

/// A `Vec` can be mutable. On the other hand, slices are read-only objects.

/// To get a [slice][prim@slice], use [`&`]. Example:

///

/// ```

/// fn read_slice(slice: &[usize]) {

/// // ...

/// }

///

/// let v = vec![0, 1];

/// read_slice(&v);

///

/// // ... and that's all!

/// // you can also do it like this:

/// let u: &[usize] = &v;

/// // or like this:

/// let u: &[_] = &v;

/// ```

///

/// In Rust, it's more common to pass slices as arguments rather than vectors

/// when you just want to provide read access. The same goes for [`String`] and

/// [`&str`].

///

/// # Capacity and reallocation

///

/// The capacity of a vector is the amount of space allocated for any future

/// elements that will be added onto the vector. This is not to be confused with

/// the *length* of a vector, which specifies the number of actual elements

/// within the vector. If a vector's length exceeds its capacity, its capacity

/// will automatically be increased, but its elements will have to be

/// reallocated.

///

/// For example, a vector with capacity 10 and length 0 would be an empty vector

/// with space for 10 more elements. Pushing 10 or fewer elements onto the

/// vector will not change its capacity or cause reallocation to occur. However,

/// if the vector's length is increased to 11, it will have to reallocate, which

/// can be slow. For this reason, it is recommended to use [`Vec::with_capacity`]

/// whenever possible to specify how big the vector is expected to get.

///

/// # Guarantees

///

/// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees

/// about its design. This ensures that it's as low-overhead as possible in

/// the general case, and can be correctly manipulated in primitive ways

/// by unsafe code. Note that these guarantees refer to an unqualified `Vec<T>`.

/// If additional type parameters are added (e.g., to support custom allocators),

/// overriding their defaults may change the behavior.

///

/// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length)

/// triplet. No more, no less. The order of these fields is completely

/// unspecified, and you should use the appropriate methods to modify these.

/// The pointer will never be null, so this type is null-pointer-optimized.

///

/// However, the pointer might not actually point to allocated memory. In particular,

/// if you construct a `Vec` with capacity 0 via [`Vec::new`], [`vec![]`][`vec!`],

/// [`Vec::with_capacity(0)`][`Vec::with_capacity`], or by calling [`shrink_to_fit`]

/// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized

/// types inside a `Vec`, it will not allocate space for them. *Note that in this case

/// the `Vec` might not report a [`capacity`] of 0*. `Vec` will allocate if and only

/// if <code>[mem::size_of::\<T>]\() * [capacity]\() > 0</code>. In general, `Vec`'s allocation

/// details are very subtle --- if you intend to allocate memory using a `Vec`

/// and use it for something else (either to pass to unsafe code, or to build your

/// own memory-backed collection), be sure to deallocate this memory by using

/// `from_raw_parts` to recover the `Vec` and then dropping it.

///

/// If a `Vec` *has* allocated memory, then the memory it points to is on the heap

/// (as defined by the allocator Rust is configured to use by default), and its

/// pointer points to [`len`] initialized, contiguous elements in order (what

/// you would see if you coerced it to a slice), followed by <code>[capacity] - [len]</code>

/// logically uninitialized, contiguous elements.

///

/// A vector containing the elements `'a'` and `'b'` with capacity 4 can be

/// visualized as below. The top part is the `Vec` struct, it contains a

/// pointer to the head of the allocation in the heap, length and capacity.

/// The bottom part is the allocation on the heap, a contiguous memory block.

///

/// ```text

/// ptr len capacity

/// +--------+--------+--------+

/// | 0x0123 | 2 | 4 |

/// +--------+--------+--------+

/// |

/// v

/// Heap +--------+--------+--------+--------+

/// | 'a' | 'b' | uninit | uninit |

/// +--------+--------+--------+--------+

/// ```

///

/// - **uninit** represents memory that is not initialized, see [`MaybeUninit`].

/// - Note: the ABI is not stable and `Vec` makes no guarantees about its memory

/// layout (including the order of fields).

///

/// `Vec` will never perform a "small optimization" where elements are actually

/// stored on the stack for two reasons:

///

/// * It would make it more difficult for unsafe code to correctly manipulate

/// a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were

/// only moved, and it would be more difficult to determine if a `Vec` had

/// actually allocated memory.

///

/// * It would penalize the general case, incurring an additional branch

/// on every access.

///

/// `Vec` will never automatically shrink itself, even if completely empty. This

/// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec`

/// and then filling it back up to the same [`len`] should incur no calls to

/// the allocator. If you wish to free up unused memory, use

/// [`shrink_to_fit`] or [`shrink_to`].

///

/// [`push`] and [`insert`] will never (re)allocate if the reported capacity is

/// sufficient. [`push`] and [`insert`] *will* (re)allocate if

/// <code>[len] == [capacity]</code>. That is, the reported capacity is completely

/// accurate, and can be relied on. It can even be used to manually free the memory

/// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even

/// when not necessary.

///

/// `Vec` does not guarantee any particular growth strategy when reallocating

/// when full, nor when [`reserve`] is called. The current strategy is basic

/// and it may prove desirable to use a non-constant growth factor. Whatever

/// strategy is used will of course guarantee *O*(1) amortized [`push`].

///

/// `vec![x; n]`, `vec![a, b, c, d]`, and

/// [`Vec::with_capacity(n)`][`Vec::with_capacity`], will all produce a `Vec`

/// with exactly the requested capacity. If <code>[len] == [capacity]</code>,

/// (as is the case for the [`vec!`] macro), then a `Vec<T>` can be converted to

/// and from a [`Box<[T]>`][owned slice] without reallocating or moving the elements.

///

/// `Vec` will not specifically overwrite any data that is removed from it,

/// but also won't specifically preserve it. Its uninitialized memory is

/// scratch space that it may use however it wants. It will generally just do

/// whatever is most efficient or otherwise easy to implement. Do not rely on

/// removed data to be erased for security purposes. Even if you drop a `Vec`, its

/// buffer may simply be reused by another allocation. Even if you zero a `Vec`'s memory

/// first, that might not actually happen because the optimizer does not consider

/// this a side-effect that must be preserved. There is one case which we will

/// not break, however: using `unsafe` code to write to the excess capacity,

/// and then increasing the length to match, is always valid.

///

/// Currently, `Vec` does not guarantee the order in which elements are dropped.

/// The order has changed in the past and may change again.

///

/// [`get`]: ../../std/vec/struct.Vec.html#method.get

/// [`get_mut`]: ../../std/vec/struct.Vec.html#method.get_mut

/// [`String`]: crate::string::String

/// [`&str`]: type@str

/// [`shrink_to_fit`]: Vec::shrink_to_fit

/// [`shrink_to`]: Vec::shrink_to

/// [capacity]: Vec::capacity

/// [`capacity`]: Vec::capacity

/// [mem::size_of::\<T>]: core::mem::size_of

/// [len]: Vec::len

/// [`len`]: Vec::len

/// [`push`]: Vec::push

/// [`insert`]: Vec::insert

/// [`reserve`]: Vec::reserve

/// [`MaybeUninit`]: core::mem::MaybeUninit

/// [owned slice]: Box

#[stable(feature = "rust1", since = "1.0.0")]

#[cfg_attr(not(test), rustc_diagnostic_item = "Vec")]

#[rustc_insignificant_dtor]

pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {

buf: RawVec<T, A>,

len: usize,

}

////////////////////////////////////////////////////////////////////////////////

// Inherent methods

////////////////////////////////////////////////////////////////////////////////

impl<T> Vec<T> {

/// Constructs a new, empty `Vec<T>`.

///

/// The vector will not allocate until elements are pushed onto it.

///

/// # Examples

///

/// ```

/// # #![allow(unused_mut)]

/// let mut vec: Vec<i32> = Vec::new();

/// ```

#[inline]

#[rustc_const_stable(feature = "const_vec_new", since = "1.39.0")]

#[stable(feature = "rust1", since = "1.0.0")]

#[must_use]

pub const fn new() -> Self {

Vec { buf: RawVec::NEW, len: 0 }

}

/// Constructs a new, empty `Vec<T>` with the specified capacity.

///

/// The vector will be able to hold exactly `capacity` elements without

/// reallocating. If `capacity` is 0, the vector will not allocate.

///

/// It is important to note that although the returned vector has the

/// *capacity* specified, the vector will have a zero *length*. For an

/// explanation of the difference between length and capacity, see

/// *[Capacity and reallocation]*.

///

/// [Capacity and reallocation]: #capacity-and-reallocation

///

/// # Panics

///

/// Panics if the new capacity exceeds `isize::MAX` bytes.

///

/// # Examples

///

/// ```

/// let mut vec = Vec::with_capacity(10);

///

/// // The vector contains no items, even though it has capacity for more

/// assert_eq!(vec.len(), 0);

/// assert_eq!(vec.capacity(), 10);

///

/// // These are all done without reallocating...

/// for i in 0..10 {

/// vec.push(i);

/// }

/// assert_eq!(vec.len(), 10);

/// assert_eq!(vec.capacity(), 10);

///

/// // ...but this may make the vector reallocate

/// vec.push(11);

/// assert_eq!(vec.len(), 11);

/// assert!(vec.capacity() >= 11);

/// ```

#[cfg(not(no_global_oom_handling))]

#[inline]

#[stable(feature = "rust1", since = "1.0.0")]

#[must_use]

pub fn with_capacity(capacity: usize) -> Self {

Self::with_capacity_in(capacity, Global)

}

/// Tries to construct a new, empty `Vec<T>` with the specified capacity.

///

/// The vector will be able to hold exactly `capacity` elements without

/// reallocating. If `capacity` is 0, the vector will not allocate.

///

/// It is important to note that although the returned vector has the

/// *capacity* specified, the vector will have a zero *length*. For an

/// explanation of the difference between length and capacity, see

/// *[Capacity and reallocation]*.

///

/// [Capacity and reallocation]: #capacity-and-reallocation

///

/// # Examples

///

/// ```

/// let mut vec = Vec::try_with_capacity(10).unwrap();

///

/// // The vector contains no items, even though it has capacity for more

/// assert_eq!(vec.len(), 0);

/// assert_eq!(vec.capacity(), 10);

///

/// // These are all done without reallocating...

/// for i in 0..10 {

/// vec.push(i);

/// }

/// assert_eq!(vec.len(), 10);

/// assert_eq!(vec.capacity(), 10);

///

/// // ...but this may make the vector reallocate

/// vec.push(11);

/// assert_eq!(vec.len(), 11);

/// assert!(vec.capacity() >= 11);

///

/// let mut result = Vec::try_with_capacity(usize::MAX);

/// assert!(result.is_err());

/// ```

#[inline]

#[stable(feature = "kernel", since = "1.0.0")]

pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {

Self::try_with_capacity_in(capacity, Global)

}

/// Creates a `Vec<T>` directly from the raw components of another vector.

///

/// # Safety

///

/// This is highly unsafe, due to the number of invariants that aren't

/// checked:

///

/// * `ptr` needs to have been previously allocated via [`String`]/`Vec<T>`

/// (at least, it's highly likely to be incorrect if it wasn't).

/// * `T` needs to have the same alignment as what `ptr` was allocated with.

/// (`T` having a less strict alignment is not sufficient, the alignment really

/// needs to be equal to satisfy the [`dealloc`] requirement that memory must be

/// allocated and deallocated with the same layout.)

/// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs

/// to be the same size as the pointer was allocated with. (Because similar to

/// alignment, [`dealloc`] must be called with the same layout `size`.)

/// * `length` needs to be less than or equal to `capacity`.

///

/// Violating these may cause problems like corrupting the allocator's

/// internal data structures. For example it is normally **not** safe

/// to build a `Vec<u8>` from a pointer to a C `char` array with length

/// `size_t`, doing so is only safe if the array was initially allocated by

/// a `Vec` or `String`.

/// It's also not safe to build one from a `Vec<u16>` and its length, because

/// the allocator cares about the alignment, and these two types have different

/// alignments. The buffer was allocated with alignment 2 (for `u16`), but after

/// turning it into a `Vec<u8>` it'll be deallocated with alignment 1. To avoid

/// these issues, it is often preferable to do casting/transmuting using

/// [`slice::from_raw_parts`] instead.

///

/// The ownership of `ptr` is effectively transferred to the

/// `Vec<T>` which may then deallocate, reallocate or change the

/// contents of memory pointed to by the pointer at will. Ensure

/// that nothing else uses the pointer after calling this

/// function.

///

/// [`String`]: crate::string::String

/// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc

///

/// # Examples

///

/// ```

/// use std::ptr;

/// use std::mem;

///

/// let v = vec![1, 2, 3];

///

// FIXME Update this when vec_into_raw_parts is stabilized

/// // Prevent running `v`'s destructor so we are in complete control

/// // of the allocation.

/// let mut v = mem::ManuallyDrop::new(v);

///

/// // Pull out the various important pieces of information about `v`

/// let p = v.as_mut_ptr();

/// let len = v.len();

/// let cap = v.capacity();

///

/// unsafe {

/// // Overwrite memory with 4, 5, 6

/// for i in 0..len as isize {

/// ptr::write(p.offset(i), 4 + i);

/// }

///

/// // Put everything back together into a Vec

/// let rebuilt = Vec::from_raw_parts(p, len, cap);

/// assert_eq!(rebuilt, [4, 5, 6]);

/// }

/// ```

#[inline]

#[stable(feature = "rust1", since = "1.0.0")]

pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {

unsafe { Self::from_raw_parts_in(ptr, length, capacity, Global) }

}

}

impl<T, A: Allocator> Vec<T, A> {

/// Constructs a new, empty `Vec<T, A>`.

///

/// The vector will not allocate until elements are pushed onto it.

///

/// # Examples

///

/// ```

/// #![feature(allocator_api)]

///

/// use std::alloc::System;

///

/// # #[allow(unused_mut)]

/// let mut vec: Vec<i32, _> = Vec::new_in(System);

/// ```

#[inline]

#[unstable(feature = "allocator_api", issue = "32838")]

pub const fn new_in(alloc: A) -> Self {

Vec { buf: RawVec::new_in(alloc), len: 0 }

}

/// Constructs a new, empty `Vec<T, A>` with the specified capacity with the provided

/// allocator.

///

/// The vector will be able to hold exactly `capacity` elements without

/// reallocating. If `capacity` is 0, the vector will not allocate.

///

/// It is important to note that although the returned vector has the

/// *capacity* specified, the vector will have a zero *length*. For an

/// explanation of the difference between length and capacity, see

/// *[Capacity and reallocation]*.

///

/// [Capacity and reallocation]: #capacity-and-reallocation

///

/// # Panics

///

/// Panics if the new capacity exceeds `isize::MAX` bytes.

///

/// # Examples

///

/// ```

/// #![feature(allocator_api)]

///

/// use std::alloc::System;

///

/// let mut vec = Vec::with_capacity_in(10, System);

///

/// // The vector contains no items, even though it has capacity for more

/// assert_eq!(vec.len(), 0);

/// assert_eq!(vec.capacity(), 10);

///

/// // These are all done without reallocating...

/// for i in 0..10 {

/// vec.push(i);

/// }

/// assert_eq!(vec.len(), 10);

/// assert_eq!(vec.capacity(), 10);

///

/// // ...but this may make the vector reallocate

/// vec.push(11);

/// assert_eq!(vec.len(), 11);

/// assert!(vec.capacity() >= 11);

/// ```

#[cfg(not(no_global_oom_handling))]

#[inline]

#[unstable(feature = "allocator_api", issue = "32838")]

pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {

Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 }

}

/// Tries to construct a new, empty `Vec<T, A>` with the specified capacity

/// with the provided allocator.

///

/// The vector will be able to hold exactly `capacity` elements without

/// reallocating. If `capacity` is 0, the vector will not allocate.

///

/// It is important to note that although the returned vector has the

/// *capacity* specified, the vector will have a zero *length*. For an

/// explanation of the difference between length and capacity, see

/// *[Capacity and reallocation]*.

///

/// [Capacity and reallocation]: #capacity-and-reallocation

///

/// # Examples

///

/// ```

/// #![feature(allocator_api)]

///

/// use std::alloc::System;

///

/// let mut vec = Vec::try_with_capacity_in(10, System).unwrap();

///

/// // The vector contains no items, even though it has capacity for more

/// assert_eq!(vec.len(), 0);

/// assert_eq!(vec.capacity(), 10);

///

/// // These are all done without reallocating...

/// for i in 0..10 {

/// vec.push(i);

/// }

/// assert_eq!(vec.len(), 10);

/// assert_eq!(vec.capacity(), 10);

///

/// // ...but this may make the vector reallocate

/// vec.push(11);

/// assert_eq!(vec.len(), 11);

/// assert!(vec.capacity() >= 11);

///

/// let mut result = Vec::try_with_capacity_in(usize::MAX, System);

/// assert!(result.is_err());

/// ```

#[inline]

#[stable(feature = "kernel", since = "1.0.0")]

pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {

Ok(Vec { buf: RawVec::try_with_capacity_in(capacity, alloc)?, len: 0 })

}

/// Creates a `Vec<T, A>` directly from the raw components of another vector.

///

/// # Safety

///

/// This is highly unsafe, due to the number of invariants that aren't

/// checked:

///

/// * `ptr` needs to have been previously allocated via [`String`]/`Vec<T>`

/// (at least, it's highly likely to be incorrect if it wasn't).

/// * `T` needs to have the same size and alignment as what `ptr` was allocated with.

/// (`T` having a less strict alignment is not sufficient, the alignment really

/// needs to be equal to satisfy the [`dealloc`] requirement that memory must be

/// allocated and deallocated with the same layout.)

/// * `length` needs to be less than or equal to `capacity`.

/// * `capacity` needs to be the capacity that the pointer was allocated with.

///

/// Violating these may cause problems like corrupting the allocator's

/// internal data structures. For example it is **not** safe

/// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.

/// It's also not safe to build one from a `Vec<u16>` and its length, because

/// the allocator cares about the alignment, and these two types have different

/// alignments. The buffer was allocated with alignment 2 (for `u16`), but after

/// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.

///

/// The ownership of `ptr` is effectively transferred to the

/// `Vec<T>` which may then deallocate, reallocate or change the

/// contents of memory pointed to by the pointer at will. Ensure

/// that nothing else uses the pointer after calling this

/// function.

///

/// [`String`]: crate::string::String

/// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc

///

/// # Examples

///

/// ```

/// #![feature(allocator_api)]

///

/// use std::alloc::System;

///

/// use std::ptr;

/// use std::mem;

///

/// let mut v = Vec::with_capacity_in(3, System);

/// v.push(1);

/// v.push(2);

/// v.push(3);

///

// FIXME Update this when vec_into_raw_parts is stabilized

/// // Prevent running `v`'s destructor so we are in complete control

/// // of the allocation.

/// let mut v = mem::ManuallyDrop::new(v);

///

/// // Pull out the various important pieces of information about `v`

/// let p = v.as_mut_ptr();

/// let len = v.len();

/// let cap = v.capacity();

/// let alloc = v.allocator();

///

/// unsafe {

/// // Overwrite memory with 4, 5, 6

/// for i in 0..len as isize {

/// ptr::write(p.offset(i), 4 + i);

/// }

///

/// // Put everything back together into a Vec

/// let rebuilt = Vec::from_raw_parts_in(p, len, cap, alloc.clone());

/// assert_eq!(rebuilt, [4, 5, 6]);

/// }

/// ```

#[inline]

#[unstable(feature = "allocator_api", issue = "32838")]

pub unsafe fn from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self {

unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } }

}

/// Decomposes a `Vec<T>` into its raw components.

///

/// Returns the raw pointer to the underlying data, the length of

/// the vector (in elements), and the allocated capacity of the

/// data (in elements). These are the same arguments in the same

/// order as the arguments to [`from_raw_parts`].

///

/// After calling this function, the caller is responsible for the

/// memory previously managed by the `Vec`. The only way to do

/// this is to convert the raw pointer, length, and capacity back

/// into a `Vec` with the [`from_raw_parts`] function, allowing

/// the destructor to perform the cleanup.

///

/// [`from_raw_parts`]: Vec::from_raw_parts

///

/// # Examples

///

/// ```

/// #![feature(vec_into_raw_parts)]

/// let v: Vec<i32> = vec![-1, 0, 1];

///

/// let (ptr, len, cap) = v.into_raw_parts();

///

/// let rebuilt = unsafe {

/// // We can now make changes to the components, such as

/// // transmuting the raw pointer to a compatible type.

/// let ptr = ptr as *mut u32;

///

/// Vec::from_raw_parts(ptr, len, cap)

/// };

/// assert_eq!(rebuilt, [4294967295, 0, 1]);

/// ```

#[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]

pub fn into_raw_parts(self) -> (*mut T, usize, usize) {

let mut me = ManuallyDrop::new(self);

(me.as_mut_ptr(), me.len(), me.capacity())

}

/// Decomposes a `Vec<T>` into its raw components.

///

/// Returns the raw pointer to the underlying data, the length of the vector (in elements),

/// the allocated capacity of the data (in elements), and the allocator. These are the same

/// arguments in the same order as the arguments to [`from_raw_parts_in`].

///

/// After calling this function, the caller is responsible for the

/// memory previously managed by the `Vec`. The only way to do

/// this is to convert the raw pointer, length, and capacity back

/// into a `Vec` with the [`from_raw_parts_in`] function, allowing

/// the destructor to perform the cleanup.

///

/// [`from_raw_parts_in`]: Vec::from_raw_parts_in

///

/// # Examples

///

/// ```

/// #![feature(allocator_api, vec_into_raw_parts)]

///

/// use std::alloc::System;

///

/// let mut v: Vec<i32, System> = Vec::new_in(System);

/// v.push(-1);

/// v.push(0);

/// v.push(1);

///

/// let (ptr, len, cap, alloc) = v.into_raw_parts_with_alloc();

///

/// let rebuilt = unsafe {

/// // We can now make changes to the components, such as

/// // transmuting the raw pointer to a compatible type.

/// let ptr = ptr as *mut u32;

///

/// Vec::from_raw_parts_in(ptr, len, cap, alloc)

/// };

/// assert_eq!(rebuilt, [4294967295, 0, 1]);

/// ```

#[unstable(feature = "allocator_api", issue = "32838")]

// #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]

pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) {

let mut me = ManuallyDrop::new(self);

let len = me.len();

let capacity = me.capacity();

let ptr = me.as_mut_ptr();

let alloc = unsafe { ptr::read(me.allocator()) };

(ptr, len, capacity, alloc)

}

/// Returns the number of elements the vector can hold without

/// reallocating.

///

/// # Examples

///

/// ```

/// let vec: Vec<i32> = Vec::with_capacity(10);

/// assert_eq!(vec.capacity(), 10);

/// ```

#[inline]

#[stable(feature = "rust1", since = "1.0.0")]

pub fn capacity(&self) -> usize {

self.buf.capacity()

}

/// Reserves capacity for at least `additional` more elements to be inserted

/// in the given `Vec<T>`. The collection may reserve more space to avoid

/// frequent reallocations. After calling `reserve`, capacity will be

/// greater than or equal to `self.len() + additional`. Does nothing if

/// capacity is already sufficient.

///

/// # Panics

///

/// Panics if the new capacity exceeds `isize::MAX` bytes.

///

/// # Examples

///

/// ```

/// let mut vec = vec![1];

/// vec.reserve(10);

/// assert!(vec.capacity() >= 11);

/// ```

#[cfg(not(no_global_oom_handling))]

#[stable(feature = "rust1", since = "1.0.0")]

pub fn reserve(&mut self, additional: usize) {

self.buf.reserve(self.len, additional);

}

/// Reserves the minimum capacity for exactly `additional` more elements to

/// be inserted in the given `Vec<T>`. After calling `reserve_exact`,

/// capacity will be greater than or equal to `self.len() + additional`.

/// Does nothing if the capacity is already sufficient.

///

/// Note that the allocator may give the collection more space than it

/// requests. Therefore, capacity can not be relied upon to be precisely

/// minimal. Prefer [`reserve`] if future insertions are expected.

///

/// [`reserve`]: Vec::reserve

///

/// # Panics

///

/// Panics if the new capacity exceeds `isize::MAX` bytes.

///

/// # Examples

///

/// ```

/// let mut vec = vec![1];

/// vec.reserve_exact(10);

/// assert!(vec.capacity() >= 11);

/// ```

#[cfg(not(no_global_oom_handling))]

#[stable(feature = "rust1", since = "1.0.0")]

pub fn reserve_exact(&mut self, additional: usize) {

self.buf.reserve_exact(self.len, additional);

}

/// Tries to reserve capacity for at least `additional` more elements to be inserted

/// in the given `Vec<T>`. The collection may reserve more space to avoid

/// frequent reallocations. After calling `try_reserve`, capacity will be

/// greater than or equal to `self.len() + additional`. Does nothing if

/// capacity is already sufficient.

///

/// # Errors

///

/// If the capacity overflows, or the allocator reports a failure, then an error

/// is returned.

///

/// # Examples

///

/// ```

/// use std::collections::TryReserveError;

///

/// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {

/// let mut output = Vec::new();

///

/// // Pre-reserve the memory, exiting if we can't

/// output.try_reserve(data.len())?;

///

/// // Now we know this can't OOM in the middle of our complex work

/// output.extend(data.iter().map(|&val| {

/// val * 2 + 5 // very complicated

/// }));

///

/// Ok(output)

/// }

/// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");

/// ```

#[stable(feature = "try_reserve", since = "1.57.0")]

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {

self.buf.try_reserve(self.len, additional)

}

/// Tries to reserve the minimum capacity for exactly `additional`

/// elements to be inserted in the given `Vec<T>`. After calling

/// `try_reserve_exact`, capacity will be greater than or equal to

/// `self.len() + additional` if it returns `Ok(())`.

/// Does nothing if the capacity is already sufficient.

///

/// Note that the allocator may give the collection more space than it

/// requests. Therefore, capacity can not be relied upon to be precisely

/// minimal. Prefer [`try_reserve`] if future insertions are expected.

///

/// [`try_reserve`]: Vec::try_reserve

///

/// # Errors

///

/// If the capacity overflows, or the allocator reports a failure, then an error

/// is returned.

///

/// # Examples

///

/// ```

/// use std::collections::TryReserveError;

///

/// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {

/// let mut output = Vec::new();

///

/// // Pre-reserve the memory, exiting if we can't

/// output.try_reserve_exact(data.len())?;

///