1057b8d25SMiguel Ojeda // SPDX-License-Identifier: Apache-2.0 OR MIT 2057b8d25SMiguel Ojeda 3753dece8SMiguel Ojeda //! A contiguous growable array type with heap-allocated contents, written 4753dece8SMiguel Ojeda //! `Vec<T>`. 5753dece8SMiguel Ojeda //! 6753dece8SMiguel Ojeda //! Vectors have *O*(1) indexing, amortized *O*(1) push (to the end) and 7753dece8SMiguel Ojeda //! *O*(1) pop (from the end). 8753dece8SMiguel Ojeda //! 9753dece8SMiguel Ojeda //! Vectors ensure they never allocate more than `isize::MAX` bytes. 10753dece8SMiguel Ojeda //! 11753dece8SMiguel Ojeda //! # Examples 12753dece8SMiguel Ojeda //! 13753dece8SMiguel Ojeda //! You can explicitly create a [`Vec`] with [`Vec::new`]: 14753dece8SMiguel Ojeda //! 15753dece8SMiguel Ojeda //! ``` 16753dece8SMiguel Ojeda //! let v: Vec<i32> = Vec::new(); 17753dece8SMiguel Ojeda //! ``` 18753dece8SMiguel Ojeda //! 19753dece8SMiguel Ojeda //! ...or by using the [`vec!`] macro: 20753dece8SMiguel Ojeda //! 21753dece8SMiguel Ojeda //! ``` 22753dece8SMiguel Ojeda //! let v: Vec<i32> = vec![]; 23753dece8SMiguel Ojeda //! 24753dece8SMiguel Ojeda //! let v = vec![1, 2, 3, 4, 5]; 25753dece8SMiguel Ojeda //! 26753dece8SMiguel Ojeda //! let v = vec![0; 10]; // ten zeroes 27753dece8SMiguel Ojeda //! ``` 28753dece8SMiguel Ojeda //! 29753dece8SMiguel Ojeda //! You can [`push`] values onto the end of a vector (which will grow the vector 30753dece8SMiguel Ojeda //! as needed): 31753dece8SMiguel Ojeda //! 32753dece8SMiguel Ojeda //! ``` 33753dece8SMiguel Ojeda //! let mut v = vec![1, 2]; 34753dece8SMiguel Ojeda //! 35753dece8SMiguel Ojeda //! v.push(3); 36753dece8SMiguel Ojeda //! ``` 37753dece8SMiguel Ojeda //! 38753dece8SMiguel Ojeda //! Popping values works in much the same way: 39753dece8SMiguel Ojeda //! 40753dece8SMiguel Ojeda //! ``` 41753dece8SMiguel Ojeda //! let mut v = vec![1, 2]; 42753dece8SMiguel Ojeda //! 43753dece8SMiguel Ojeda //! let two = v.pop(); 44753dece8SMiguel Ojeda //! ``` 45753dece8SMiguel Ojeda //! 46753dece8SMiguel Ojeda //! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits): 47753dece8SMiguel Ojeda //! 48753dece8SMiguel Ojeda //! ``` 49753dece8SMiguel Ojeda //! let mut v = vec![1, 2, 3]; 50753dece8SMiguel Ojeda //! let three = v[2]; 51753dece8SMiguel Ojeda //! v[1] = v[1] + 5; 52753dece8SMiguel Ojeda //! ``` 53753dece8SMiguel Ojeda //! 54753dece8SMiguel Ojeda //! [`push`]: Vec::push 55753dece8SMiguel Ojeda 56753dece8SMiguel Ojeda #![stable(feature = "rust1", since = "1.0.0")] 57753dece8SMiguel Ojeda 58753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 59753dece8SMiguel Ojeda use core::cmp; 60753dece8SMiguel Ojeda use core::cmp::Ordering; 61753dece8SMiguel Ojeda use core::fmt; 62753dece8SMiguel Ojeda use core::hash::{Hash, Hasher}; 63753dece8SMiguel Ojeda use core::iter; 64753dece8SMiguel Ojeda use core::marker::PhantomData; 653ed03f4dSMiguel Ojeda use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; 66753dece8SMiguel Ojeda use core::ops::{self, Index, IndexMut, Range, RangeBounds}; 67753dece8SMiguel Ojeda use core::ptr::{self, NonNull}; 68753dece8SMiguel Ojeda use core::slice::{self, SliceIndex}; 69753dece8SMiguel Ojeda 70753dece8SMiguel Ojeda use crate::alloc::{Allocator, Global}; 718909a80eSMiguel Ojeda #[cfg(not(no_borrow))] 72753dece8SMiguel Ojeda use crate::borrow::{Cow, ToOwned}; 73753dece8SMiguel Ojeda use crate::boxed::Box; 743ed03f4dSMiguel Ojeda use crate::collections::{TryReserveError, TryReserveErrorKind}; 75753dece8SMiguel Ojeda use crate::raw_vec::RawVec; 76753dece8SMiguel Ojeda 77753dece8SMiguel Ojeda #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] 78753dece8SMiguel Ojeda pub use self::drain_filter::DrainFilter; 79753dece8SMiguel Ojeda 80753dece8SMiguel Ojeda mod drain_filter; 81753dece8SMiguel Ojeda 82753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 83753dece8SMiguel Ojeda #[stable(feature = "vec_splice", since = "1.21.0")] 84753dece8SMiguel Ojeda pub use self::splice::Splice; 85753dece8SMiguel Ojeda 86753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 87753dece8SMiguel Ojeda mod splice; 88753dece8SMiguel Ojeda 89753dece8SMiguel Ojeda #[stable(feature = "drain", since = "1.6.0")] 90753dece8SMiguel Ojeda pub use self::drain::Drain; 91753dece8SMiguel Ojeda 92753dece8SMiguel Ojeda mod drain; 93753dece8SMiguel Ojeda 948909a80eSMiguel Ojeda #[cfg(not(no_borrow))] 95753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 96753dece8SMiguel Ojeda mod cow; 97753dece8SMiguel Ojeda 98753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 99753dece8SMiguel Ojeda pub(crate) use self::in_place_collect::AsVecIntoIter; 100753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 101753dece8SMiguel Ojeda pub use self::into_iter::IntoIter; 102753dece8SMiguel Ojeda 103753dece8SMiguel Ojeda mod into_iter; 104753dece8SMiguel Ojeda 105753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 106753dece8SMiguel Ojeda use self::is_zero::IsZero; 107753dece8SMiguel Ojeda 108753dece8SMiguel Ojeda mod is_zero; 109753dece8SMiguel Ojeda 110753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 111753dece8SMiguel Ojeda mod in_place_collect; 112753dece8SMiguel Ojeda 113753dece8SMiguel Ojeda mod partial_eq; 114753dece8SMiguel Ojeda 115753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 116753dece8SMiguel Ojeda use self::spec_from_elem::SpecFromElem; 117753dece8SMiguel Ojeda 118753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 119753dece8SMiguel Ojeda mod spec_from_elem; 120753dece8SMiguel Ojeda 121753dece8SMiguel Ojeda use self::set_len_on_drop::SetLenOnDrop; 122753dece8SMiguel Ojeda 123753dece8SMiguel Ojeda mod set_len_on_drop; 124753dece8SMiguel Ojeda 125753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1263ed03f4dSMiguel Ojeda use self::in_place_drop::{InPlaceDrop, InPlaceDstBufDrop}; 127753dece8SMiguel Ojeda 128753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 129753dece8SMiguel Ojeda mod in_place_drop; 130753dece8SMiguel Ojeda 131753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 132753dece8SMiguel Ojeda use self::spec_from_iter_nested::SpecFromIterNested; 133753dece8SMiguel Ojeda 134753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 135753dece8SMiguel Ojeda mod spec_from_iter_nested; 136753dece8SMiguel Ojeda 137753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 138753dece8SMiguel Ojeda use self::spec_from_iter::SpecFromIter; 139753dece8SMiguel Ojeda 140753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 141753dece8SMiguel Ojeda mod spec_from_iter; 142753dece8SMiguel Ojeda 143753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 144753dece8SMiguel Ojeda use self::spec_extend::SpecExtend; 145753dece8SMiguel Ojeda 146318c3cc8SMiguel Ojeda use self::spec_extend::TrySpecExtend; 147318c3cc8SMiguel Ojeda 148753dece8SMiguel Ojeda mod spec_extend; 149753dece8SMiguel Ojeda 150753dece8SMiguel Ojeda /// A contiguous growable array type, written as `Vec<T>`, short for 'vector'. 151753dece8SMiguel Ojeda /// 152753dece8SMiguel Ojeda /// # Examples 153753dece8SMiguel Ojeda /// 154753dece8SMiguel Ojeda /// ``` 155753dece8SMiguel Ojeda /// let mut vec = Vec::new(); 156753dece8SMiguel Ojeda /// vec.push(1); 157753dece8SMiguel Ojeda /// vec.push(2); 158753dece8SMiguel Ojeda /// 159753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 2); 160753dece8SMiguel Ojeda /// assert_eq!(vec[0], 1); 161753dece8SMiguel Ojeda /// 162753dece8SMiguel Ojeda /// assert_eq!(vec.pop(), Some(2)); 163753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 1); 164753dece8SMiguel Ojeda /// 165753dece8SMiguel Ojeda /// vec[0] = 7; 166753dece8SMiguel Ojeda /// assert_eq!(vec[0], 7); 167753dece8SMiguel Ojeda /// 1683ed03f4dSMiguel Ojeda /// vec.extend([1, 2, 3]); 169753dece8SMiguel Ojeda /// 170753dece8SMiguel Ojeda /// for x in &vec { 171753dece8SMiguel Ojeda /// println!("{x}"); 172753dece8SMiguel Ojeda /// } 173753dece8SMiguel Ojeda /// assert_eq!(vec, [7, 1, 2, 3]); 174753dece8SMiguel Ojeda /// ``` 175753dece8SMiguel Ojeda /// 176753dece8SMiguel Ojeda /// The [`vec!`] macro is provided for convenient initialization: 177753dece8SMiguel Ojeda /// 178753dece8SMiguel Ojeda /// ``` 179753dece8SMiguel Ojeda /// let mut vec1 = vec![1, 2, 3]; 180753dece8SMiguel Ojeda /// vec1.push(4); 181753dece8SMiguel Ojeda /// let vec2 = Vec::from([1, 2, 3, 4]); 182753dece8SMiguel Ojeda /// assert_eq!(vec1, vec2); 183753dece8SMiguel Ojeda /// ``` 184753dece8SMiguel Ojeda /// 185753dece8SMiguel Ojeda /// It can also initialize each element of a `Vec<T>` with a given value. 186753dece8SMiguel Ojeda /// This may be more efficient than performing allocation and initialization 187753dece8SMiguel Ojeda /// in separate steps, especially when initializing a vector of zeros: 188753dece8SMiguel Ojeda /// 189753dece8SMiguel Ojeda /// ``` 190753dece8SMiguel Ojeda /// let vec = vec![0; 5]; 191753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 0, 0, 0, 0]); 192753dece8SMiguel Ojeda /// 193753dece8SMiguel Ojeda /// // The following is equivalent, but potentially slower: 194753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(5); 195753dece8SMiguel Ojeda /// vec.resize(5, 0); 196753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 0, 0, 0, 0]); 197753dece8SMiguel Ojeda /// ``` 198753dece8SMiguel Ojeda /// 199753dece8SMiguel Ojeda /// For more information, see 200753dece8SMiguel Ojeda /// [Capacity and Reallocation](#capacity-and-reallocation). 201753dece8SMiguel Ojeda /// 202753dece8SMiguel Ojeda /// Use a `Vec<T>` as an efficient stack: 203753dece8SMiguel Ojeda /// 204753dece8SMiguel Ojeda /// ``` 205753dece8SMiguel Ojeda /// let mut stack = Vec::new(); 206753dece8SMiguel Ojeda /// 207753dece8SMiguel Ojeda /// stack.push(1); 208753dece8SMiguel Ojeda /// stack.push(2); 209753dece8SMiguel Ojeda /// stack.push(3); 210753dece8SMiguel Ojeda /// 211753dece8SMiguel Ojeda /// while let Some(top) = stack.pop() { 212753dece8SMiguel Ojeda /// // Prints 3, 2, 1 213753dece8SMiguel Ojeda /// println!("{top}"); 214753dece8SMiguel Ojeda /// } 215753dece8SMiguel Ojeda /// ``` 216753dece8SMiguel Ojeda /// 217753dece8SMiguel Ojeda /// # Indexing 218753dece8SMiguel Ojeda /// 219753dece8SMiguel Ojeda /// The `Vec` type allows to access values by index, because it implements the 220753dece8SMiguel Ojeda /// [`Index`] trait. An example will be more explicit: 221753dece8SMiguel Ojeda /// 222753dece8SMiguel Ojeda /// ``` 223753dece8SMiguel Ojeda /// let v = vec![0, 2, 4, 6]; 224753dece8SMiguel Ojeda /// println!("{}", v[1]); // it will display '2' 225753dece8SMiguel Ojeda /// ``` 226753dece8SMiguel Ojeda /// 227753dece8SMiguel Ojeda /// However be careful: if you try to access an index which isn't in the `Vec`, 228753dece8SMiguel Ojeda /// your software will panic! You cannot do this: 229753dece8SMiguel Ojeda /// 230753dece8SMiguel Ojeda /// ```should_panic 231753dece8SMiguel Ojeda /// let v = vec![0, 2, 4, 6]; 232753dece8SMiguel Ojeda /// println!("{}", v[6]); // it will panic! 233753dece8SMiguel Ojeda /// ``` 234753dece8SMiguel Ojeda /// 235753dece8SMiguel Ojeda /// Use [`get`] and [`get_mut`] if you want to check whether the index is in 236753dece8SMiguel Ojeda /// the `Vec`. 237753dece8SMiguel Ojeda /// 238753dece8SMiguel Ojeda /// # Slicing 239753dece8SMiguel Ojeda /// 240753dece8SMiguel Ojeda /// A `Vec` can be mutable. On the other hand, slices are read-only objects. 241753dece8SMiguel Ojeda /// To get a [slice][prim@slice], use [`&`]. Example: 242753dece8SMiguel Ojeda /// 243753dece8SMiguel Ojeda /// ``` 244753dece8SMiguel Ojeda /// fn read_slice(slice: &[usize]) { 245753dece8SMiguel Ojeda /// // ... 246753dece8SMiguel Ojeda /// } 247753dece8SMiguel Ojeda /// 248753dece8SMiguel Ojeda /// let v = vec![0, 1]; 249753dece8SMiguel Ojeda /// read_slice(&v); 250753dece8SMiguel Ojeda /// 251753dece8SMiguel Ojeda /// // ... and that's all! 252753dece8SMiguel Ojeda /// // you can also do it like this: 253753dece8SMiguel Ojeda /// let u: &[usize] = &v; 254753dece8SMiguel Ojeda /// // or like this: 255753dece8SMiguel Ojeda /// let u: &[_] = &v; 256753dece8SMiguel Ojeda /// ``` 257753dece8SMiguel Ojeda /// 258753dece8SMiguel Ojeda /// In Rust, it's more common to pass slices as arguments rather than vectors 259753dece8SMiguel Ojeda /// when you just want to provide read access. The same goes for [`String`] and 260753dece8SMiguel Ojeda /// [`&str`]. 261753dece8SMiguel Ojeda /// 262753dece8SMiguel Ojeda /// # Capacity and reallocation 263753dece8SMiguel Ojeda /// 264753dece8SMiguel Ojeda /// The capacity of a vector is the amount of space allocated for any future 265753dece8SMiguel Ojeda /// elements that will be added onto the vector. This is not to be confused with 266753dece8SMiguel Ojeda /// the *length* of a vector, which specifies the number of actual elements 267753dece8SMiguel Ojeda /// within the vector. If a vector's length exceeds its capacity, its capacity 268753dece8SMiguel Ojeda /// will automatically be increased, but its elements will have to be 269753dece8SMiguel Ojeda /// reallocated. 270753dece8SMiguel Ojeda /// 271753dece8SMiguel Ojeda /// For example, a vector with capacity 10 and length 0 would be an empty vector 272753dece8SMiguel Ojeda /// with space for 10 more elements. Pushing 10 or fewer elements onto the 273753dece8SMiguel Ojeda /// vector will not change its capacity or cause reallocation to occur. However, 274753dece8SMiguel Ojeda /// if the vector's length is increased to 11, it will have to reallocate, which 275753dece8SMiguel Ojeda /// can be slow. For this reason, it is recommended to use [`Vec::with_capacity`] 276753dece8SMiguel Ojeda /// whenever possible to specify how big the vector is expected to get. 277753dece8SMiguel Ojeda /// 278753dece8SMiguel Ojeda /// # Guarantees 279753dece8SMiguel Ojeda /// 280753dece8SMiguel Ojeda /// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees 281753dece8SMiguel Ojeda /// about its design. This ensures that it's as low-overhead as possible in 282753dece8SMiguel Ojeda /// the general case, and can be correctly manipulated in primitive ways 283753dece8SMiguel Ojeda /// by unsafe code. Note that these guarantees refer to an unqualified `Vec<T>`. 284753dece8SMiguel Ojeda /// If additional type parameters are added (e.g., to support custom allocators), 285753dece8SMiguel Ojeda /// overriding their defaults may change the behavior. 286753dece8SMiguel Ojeda /// 287753dece8SMiguel Ojeda /// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length) 288753dece8SMiguel Ojeda /// triplet. No more, no less. The order of these fields is completely 289753dece8SMiguel Ojeda /// unspecified, and you should use the appropriate methods to modify these. 290753dece8SMiguel Ojeda /// The pointer will never be null, so this type is null-pointer-optimized. 291753dece8SMiguel Ojeda /// 292753dece8SMiguel Ojeda /// However, the pointer might not actually point to allocated memory. In particular, 293753dece8SMiguel Ojeda /// if you construct a `Vec` with capacity 0 via [`Vec::new`], [`vec![]`][`vec!`], 294753dece8SMiguel Ojeda /// [`Vec::with_capacity(0)`][`Vec::with_capacity`], or by calling [`shrink_to_fit`] 295753dece8SMiguel Ojeda /// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized 296753dece8SMiguel Ojeda /// types inside a `Vec`, it will not allocate space for them. *Note that in this case 297753dece8SMiguel Ojeda /// the `Vec` might not report a [`capacity`] of 0*. `Vec` will allocate if and only 298753dece8SMiguel Ojeda /// if <code>[mem::size_of::\<T>]\() * [capacity]\() > 0</code>. In general, `Vec`'s allocation 299753dece8SMiguel Ojeda /// details are very subtle --- if you intend to allocate memory using a `Vec` 300753dece8SMiguel Ojeda /// and use it for something else (either to pass to unsafe code, or to build your 301753dece8SMiguel Ojeda /// own memory-backed collection), be sure to deallocate this memory by using 302753dece8SMiguel Ojeda /// `from_raw_parts` to recover the `Vec` and then dropping it. 303753dece8SMiguel Ojeda /// 304753dece8SMiguel Ojeda /// If a `Vec` *has* allocated memory, then the memory it points to is on the heap 305753dece8SMiguel Ojeda /// (as defined by the allocator Rust is configured to use by default), and its 306753dece8SMiguel Ojeda /// pointer points to [`len`] initialized, contiguous elements in order (what 307753dece8SMiguel Ojeda /// you would see if you coerced it to a slice), followed by <code>[capacity] - [len]</code> 308753dece8SMiguel Ojeda /// logically uninitialized, contiguous elements. 309753dece8SMiguel Ojeda /// 310753dece8SMiguel Ojeda /// A vector containing the elements `'a'` and `'b'` with capacity 4 can be 311753dece8SMiguel Ojeda /// visualized as below. The top part is the `Vec` struct, it contains a 312753dece8SMiguel Ojeda /// pointer to the head of the allocation in the heap, length and capacity. 313753dece8SMiguel Ojeda /// The bottom part is the allocation on the heap, a contiguous memory block. 314753dece8SMiguel Ojeda /// 315753dece8SMiguel Ojeda /// ```text 316753dece8SMiguel Ojeda /// ptr len capacity 317753dece8SMiguel Ojeda /// +--------+--------+--------+ 318753dece8SMiguel Ojeda /// | 0x0123 | 2 | 4 | 319753dece8SMiguel Ojeda /// +--------+--------+--------+ 320753dece8SMiguel Ojeda /// | 321753dece8SMiguel Ojeda /// v 322753dece8SMiguel Ojeda /// Heap +--------+--------+--------+--------+ 323753dece8SMiguel Ojeda /// | 'a' | 'b' | uninit | uninit | 324753dece8SMiguel Ojeda /// +--------+--------+--------+--------+ 325753dece8SMiguel Ojeda /// ``` 326753dece8SMiguel Ojeda /// 327753dece8SMiguel Ojeda /// - **uninit** represents memory that is not initialized, see [`MaybeUninit`]. 328753dece8SMiguel Ojeda /// - Note: the ABI is not stable and `Vec` makes no guarantees about its memory 329753dece8SMiguel Ojeda /// layout (including the order of fields). 330753dece8SMiguel Ojeda /// 331753dece8SMiguel Ojeda /// `Vec` will never perform a "small optimization" where elements are actually 332753dece8SMiguel Ojeda /// stored on the stack for two reasons: 333753dece8SMiguel Ojeda /// 334753dece8SMiguel Ojeda /// * It would make it more difficult for unsafe code to correctly manipulate 335753dece8SMiguel Ojeda /// a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were 336753dece8SMiguel Ojeda /// only moved, and it would be more difficult to determine if a `Vec` had 337753dece8SMiguel Ojeda /// actually allocated memory. 338753dece8SMiguel Ojeda /// 339753dece8SMiguel Ojeda /// * It would penalize the general case, incurring an additional branch 340753dece8SMiguel Ojeda /// on every access. 341753dece8SMiguel Ojeda /// 342753dece8SMiguel Ojeda /// `Vec` will never automatically shrink itself, even if completely empty. This 343753dece8SMiguel Ojeda /// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec` 344753dece8SMiguel Ojeda /// and then filling it back up to the same [`len`] should incur no calls to 345753dece8SMiguel Ojeda /// the allocator. If you wish to free up unused memory, use 346753dece8SMiguel Ojeda /// [`shrink_to_fit`] or [`shrink_to`]. 347753dece8SMiguel Ojeda /// 348753dece8SMiguel Ojeda /// [`push`] and [`insert`] will never (re)allocate if the reported capacity is 349753dece8SMiguel Ojeda /// sufficient. [`push`] and [`insert`] *will* (re)allocate if 350753dece8SMiguel Ojeda /// <code>[len] == [capacity]</code>. That is, the reported capacity is completely 351753dece8SMiguel Ojeda /// accurate, and can be relied on. It can even be used to manually free the memory 352753dece8SMiguel Ojeda /// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even 353753dece8SMiguel Ojeda /// when not necessary. 354753dece8SMiguel Ojeda /// 355753dece8SMiguel Ojeda /// `Vec` does not guarantee any particular growth strategy when reallocating 356753dece8SMiguel Ojeda /// when full, nor when [`reserve`] is called. The current strategy is basic 357753dece8SMiguel Ojeda /// and it may prove desirable to use a non-constant growth factor. Whatever 358753dece8SMiguel Ojeda /// strategy is used will of course guarantee *O*(1) amortized [`push`]. 359753dece8SMiguel Ojeda /// 360753dece8SMiguel Ojeda /// `vec![x; n]`, `vec![a, b, c, d]`, and 361753dece8SMiguel Ojeda /// [`Vec::with_capacity(n)`][`Vec::with_capacity`], will all produce a `Vec` 362753dece8SMiguel Ojeda /// with exactly the requested capacity. If <code>[len] == [capacity]</code>, 363753dece8SMiguel Ojeda /// (as is the case for the [`vec!`] macro), then a `Vec<T>` can be converted to 364753dece8SMiguel Ojeda /// and from a [`Box<[T]>`][owned slice] without reallocating or moving the elements. 365753dece8SMiguel Ojeda /// 366753dece8SMiguel Ojeda /// `Vec` will not specifically overwrite any data that is removed from it, 367753dece8SMiguel Ojeda /// but also won't specifically preserve it. Its uninitialized memory is 368753dece8SMiguel Ojeda /// scratch space that it may use however it wants. It will generally just do 369753dece8SMiguel Ojeda /// whatever is most efficient or otherwise easy to implement. Do not rely on 370753dece8SMiguel Ojeda /// removed data to be erased for security purposes. Even if you drop a `Vec`, its 371753dece8SMiguel Ojeda /// buffer may simply be reused by another allocation. Even if you zero a `Vec`'s memory 372753dece8SMiguel Ojeda /// first, that might not actually happen because the optimizer does not consider 373753dece8SMiguel Ojeda /// this a side-effect that must be preserved. There is one case which we will 374753dece8SMiguel Ojeda /// not break, however: using `unsafe` code to write to the excess capacity, 375753dece8SMiguel Ojeda /// and then increasing the length to match, is always valid. 376753dece8SMiguel Ojeda /// 377753dece8SMiguel Ojeda /// Currently, `Vec` does not guarantee the order in which elements are dropped. 378753dece8SMiguel Ojeda /// The order has changed in the past and may change again. 379753dece8SMiguel Ojeda /// 380*89eed1abSMiguel Ojeda /// [`get`]: slice::get 381*89eed1abSMiguel Ojeda /// [`get_mut`]: slice::get_mut 382753dece8SMiguel Ojeda /// [`String`]: crate::string::String 383753dece8SMiguel Ojeda /// [`&str`]: type@str 384753dece8SMiguel Ojeda /// [`shrink_to_fit`]: Vec::shrink_to_fit 385753dece8SMiguel Ojeda /// [`shrink_to`]: Vec::shrink_to 386753dece8SMiguel Ojeda /// [capacity]: Vec::capacity 387753dece8SMiguel Ojeda /// [`capacity`]: Vec::capacity 388753dece8SMiguel Ojeda /// [mem::size_of::\<T>]: core::mem::size_of 389753dece8SMiguel Ojeda /// [len]: Vec::len 390753dece8SMiguel Ojeda /// [`len`]: Vec::len 391753dece8SMiguel Ojeda /// [`push`]: Vec::push 392753dece8SMiguel Ojeda /// [`insert`]: Vec::insert 393753dece8SMiguel Ojeda /// [`reserve`]: Vec::reserve 394753dece8SMiguel Ojeda /// [`MaybeUninit`]: core::mem::MaybeUninit 395753dece8SMiguel Ojeda /// [owned slice]: Box 396753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 397753dece8SMiguel Ojeda #[cfg_attr(not(test), rustc_diagnostic_item = "Vec")] 398753dece8SMiguel Ojeda #[rustc_insignificant_dtor] 399753dece8SMiguel Ojeda pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> { 400753dece8SMiguel Ojeda buf: RawVec<T, A>, 401753dece8SMiguel Ojeda len: usize, 402753dece8SMiguel Ojeda } 403753dece8SMiguel Ojeda 404753dece8SMiguel Ojeda //////////////////////////////////////////////////////////////////////////////// 405753dece8SMiguel Ojeda // Inherent methods 406753dece8SMiguel Ojeda //////////////////////////////////////////////////////////////////////////////// 407753dece8SMiguel Ojeda 408753dece8SMiguel Ojeda impl<T> Vec<T> { 409753dece8SMiguel Ojeda /// Constructs a new, empty `Vec<T>`. 410753dece8SMiguel Ojeda /// 411753dece8SMiguel Ojeda /// The vector will not allocate until elements are pushed onto it. 412753dece8SMiguel Ojeda /// 413753dece8SMiguel Ojeda /// # Examples 414753dece8SMiguel Ojeda /// 415753dece8SMiguel Ojeda /// ``` 416753dece8SMiguel Ojeda /// # #![allow(unused_mut)] 417753dece8SMiguel Ojeda /// let mut vec: Vec<i32> = Vec::new(); 418753dece8SMiguel Ojeda /// ``` 419753dece8SMiguel Ojeda #[inline] 420753dece8SMiguel Ojeda #[rustc_const_stable(feature = "const_vec_new", since = "1.39.0")] 421753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 422753dece8SMiguel Ojeda #[must_use] 423753dece8SMiguel Ojeda pub const fn new() -> Self { 424753dece8SMiguel Ojeda Vec { buf: RawVec::NEW, len: 0 } 425753dece8SMiguel Ojeda } 426753dece8SMiguel Ojeda 4273ed03f4dSMiguel Ojeda /// Constructs a new, empty `Vec<T>` with at least the specified capacity. 428753dece8SMiguel Ojeda /// 4293ed03f4dSMiguel Ojeda /// The vector will be able to hold at least `capacity` elements without 4303ed03f4dSMiguel Ojeda /// reallocating. This method is allowed to allocate for more elements than 4313ed03f4dSMiguel Ojeda /// `capacity`. If `capacity` is 0, the vector will not allocate. 432753dece8SMiguel Ojeda /// 433753dece8SMiguel Ojeda /// It is important to note that although the returned vector has the 4343ed03f4dSMiguel Ojeda /// minimum *capacity* specified, the vector will have a zero *length*. For 4353ed03f4dSMiguel Ojeda /// an explanation of the difference between length and capacity, see 436753dece8SMiguel Ojeda /// *[Capacity and reallocation]*. 437753dece8SMiguel Ojeda /// 4383ed03f4dSMiguel Ojeda /// If it is important to know the exact allocated capacity of a `Vec`, 4393ed03f4dSMiguel Ojeda /// always use the [`capacity`] method after construction. 4403ed03f4dSMiguel Ojeda /// 4413ed03f4dSMiguel Ojeda /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation 4423ed03f4dSMiguel Ojeda /// and the capacity will always be `usize::MAX`. 4433ed03f4dSMiguel Ojeda /// 444753dece8SMiguel Ojeda /// [Capacity and reallocation]: #capacity-and-reallocation 4453ed03f4dSMiguel Ojeda /// [`capacity`]: Vec::capacity 446753dece8SMiguel Ojeda /// 447753dece8SMiguel Ojeda /// # Panics 448753dece8SMiguel Ojeda /// 449753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes. 450753dece8SMiguel Ojeda /// 451753dece8SMiguel Ojeda /// # Examples 452753dece8SMiguel Ojeda /// 453753dece8SMiguel Ojeda /// ``` 454753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(10); 455753dece8SMiguel Ojeda /// 456753dece8SMiguel Ojeda /// // The vector contains no items, even though it has capacity for more 457753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 0); 4583ed03f4dSMiguel Ojeda /// assert!(vec.capacity() >= 10); 459753dece8SMiguel Ojeda /// 460753dece8SMiguel Ojeda /// // These are all done without reallocating... 461753dece8SMiguel Ojeda /// for i in 0..10 { 462753dece8SMiguel Ojeda /// vec.push(i); 463753dece8SMiguel Ojeda /// } 464753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 10); 4653ed03f4dSMiguel Ojeda /// assert!(vec.capacity() >= 10); 466753dece8SMiguel Ojeda /// 467753dece8SMiguel Ojeda /// // ...but this may make the vector reallocate 468753dece8SMiguel Ojeda /// vec.push(11); 469753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 11); 470753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 11); 4713ed03f4dSMiguel Ojeda /// 4723ed03f4dSMiguel Ojeda /// // A vector of a zero-sized type will always over-allocate, since no 4733ed03f4dSMiguel Ojeda /// // allocation is necessary 4743ed03f4dSMiguel Ojeda /// let vec_units = Vec::<()>::with_capacity(10); 4753ed03f4dSMiguel Ojeda /// assert_eq!(vec_units.capacity(), usize::MAX); 476753dece8SMiguel Ojeda /// ``` 477753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 478753dece8SMiguel Ojeda #[inline] 479753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 480753dece8SMiguel Ojeda #[must_use] 481753dece8SMiguel Ojeda pub fn with_capacity(capacity: usize) -> Self { 482753dece8SMiguel Ojeda Self::with_capacity_in(capacity, Global) 483753dece8SMiguel Ojeda } 484753dece8SMiguel Ojeda 4853ed03f4dSMiguel Ojeda /// Tries to construct a new, empty `Vec<T>` with at least the specified capacity. 486feadd062SMiguel Ojeda /// 4873ed03f4dSMiguel Ojeda /// The vector will be able to hold at least `capacity` elements without 4883ed03f4dSMiguel Ojeda /// reallocating. This method is allowed to allocate for more elements than 4893ed03f4dSMiguel Ojeda /// `capacity`. If `capacity` is 0, the vector will not allocate. 490feadd062SMiguel Ojeda /// 491feadd062SMiguel Ojeda /// It is important to note that although the returned vector has the 4923ed03f4dSMiguel Ojeda /// minimum *capacity* specified, the vector will have a zero *length*. For 4933ed03f4dSMiguel Ojeda /// an explanation of the difference between length and capacity, see 494feadd062SMiguel Ojeda /// *[Capacity and reallocation]*. 495feadd062SMiguel Ojeda /// 4963ed03f4dSMiguel Ojeda /// If it is important to know the exact allocated capacity of a `Vec`, 4973ed03f4dSMiguel Ojeda /// always use the [`capacity`] method after construction. 4983ed03f4dSMiguel Ojeda /// 4993ed03f4dSMiguel Ojeda /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation 5003ed03f4dSMiguel Ojeda /// and the capacity will always be `usize::MAX`. 5013ed03f4dSMiguel Ojeda /// 502feadd062SMiguel Ojeda /// [Capacity and reallocation]: #capacity-and-reallocation 5033ed03f4dSMiguel Ojeda /// [`capacity`]: Vec::capacity 504feadd062SMiguel Ojeda /// 505feadd062SMiguel Ojeda /// # Examples 506feadd062SMiguel Ojeda /// 507feadd062SMiguel Ojeda /// ``` 508feadd062SMiguel Ojeda /// let mut vec = Vec::try_with_capacity(10).unwrap(); 509feadd062SMiguel Ojeda /// 510feadd062SMiguel Ojeda /// // The vector contains no items, even though it has capacity for more 511feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 0); 5123ed03f4dSMiguel Ojeda /// assert!(vec.capacity() >= 10); 513feadd062SMiguel Ojeda /// 514feadd062SMiguel Ojeda /// // These are all done without reallocating... 515feadd062SMiguel Ojeda /// for i in 0..10 { 516feadd062SMiguel Ojeda /// vec.push(i); 517feadd062SMiguel Ojeda /// } 518feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 10); 5193ed03f4dSMiguel Ojeda /// assert!(vec.capacity() >= 10); 520feadd062SMiguel Ojeda /// 521feadd062SMiguel Ojeda /// // ...but this may make the vector reallocate 522feadd062SMiguel Ojeda /// vec.push(11); 523feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 11); 524feadd062SMiguel Ojeda /// assert!(vec.capacity() >= 11); 525feadd062SMiguel Ojeda /// 526feadd062SMiguel Ojeda /// let mut result = Vec::try_with_capacity(usize::MAX); 527feadd062SMiguel Ojeda /// assert!(result.is_err()); 5283ed03f4dSMiguel Ojeda /// 5293ed03f4dSMiguel Ojeda /// // A vector of a zero-sized type will always over-allocate, since no 5303ed03f4dSMiguel Ojeda /// // allocation is necessary 5313ed03f4dSMiguel Ojeda /// let vec_units = Vec::<()>::try_with_capacity(10).unwrap(); 5323ed03f4dSMiguel Ojeda /// assert_eq!(vec_units.capacity(), usize::MAX); 533feadd062SMiguel Ojeda /// ``` 534feadd062SMiguel Ojeda #[inline] 535feadd062SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")] 536feadd062SMiguel Ojeda pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> { 537feadd062SMiguel Ojeda Self::try_with_capacity_in(capacity, Global) 538feadd062SMiguel Ojeda } 539feadd062SMiguel Ojeda 5403ed03f4dSMiguel Ojeda /// Creates a `Vec<T>` directly from a pointer, a capacity, and a length. 541753dece8SMiguel Ojeda /// 542753dece8SMiguel Ojeda /// # Safety 543753dece8SMiguel Ojeda /// 544753dece8SMiguel Ojeda /// This is highly unsafe, due to the number of invariants that aren't 545753dece8SMiguel Ojeda /// checked: 546753dece8SMiguel Ojeda /// 5473ed03f4dSMiguel Ojeda /// * `ptr` must have been allocated using the global allocator, such as via 5483ed03f4dSMiguel Ojeda /// the [`alloc::alloc`] function. 549753dece8SMiguel Ojeda /// * `T` needs to have the same alignment as what `ptr` was allocated with. 550753dece8SMiguel Ojeda /// (`T` having a less strict alignment is not sufficient, the alignment really 551753dece8SMiguel Ojeda /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be 552753dece8SMiguel Ojeda /// allocated and deallocated with the same layout.) 553753dece8SMiguel Ojeda /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs 554753dece8SMiguel Ojeda /// to be the same size as the pointer was allocated with. (Because similar to 555753dece8SMiguel Ojeda /// alignment, [`dealloc`] must be called with the same layout `size`.) 556753dece8SMiguel Ojeda /// * `length` needs to be less than or equal to `capacity`. 5573ed03f4dSMiguel Ojeda /// * The first `length` values must be properly initialized values of type `T`. 5583ed03f4dSMiguel Ojeda /// * `capacity` needs to be the capacity that the pointer was allocated with. 5593ed03f4dSMiguel Ojeda /// * The allocated size in bytes must be no larger than `isize::MAX`. 5603ed03f4dSMiguel Ojeda /// See the safety documentation of [`pointer::offset`]. 5613ed03f4dSMiguel Ojeda /// 5623ed03f4dSMiguel Ojeda /// These requirements are always upheld by any `ptr` that has been allocated 5633ed03f4dSMiguel Ojeda /// via `Vec<T>`. Other allocation sources are allowed if the invariants are 5643ed03f4dSMiguel Ojeda /// upheld. 565753dece8SMiguel Ojeda /// 566753dece8SMiguel Ojeda /// Violating these may cause problems like corrupting the allocator's 567753dece8SMiguel Ojeda /// internal data structures. For example it is normally **not** safe 568753dece8SMiguel Ojeda /// to build a `Vec<u8>` from a pointer to a C `char` array with length 569753dece8SMiguel Ojeda /// `size_t`, doing so is only safe if the array was initially allocated by 570753dece8SMiguel Ojeda /// a `Vec` or `String`. 571753dece8SMiguel Ojeda /// It's also not safe to build one from a `Vec<u16>` and its length, because 572753dece8SMiguel Ojeda /// the allocator cares about the alignment, and these two types have different 573753dece8SMiguel Ojeda /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after 574753dece8SMiguel Ojeda /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1. To avoid 575753dece8SMiguel Ojeda /// these issues, it is often preferable to do casting/transmuting using 576753dece8SMiguel Ojeda /// [`slice::from_raw_parts`] instead. 577753dece8SMiguel Ojeda /// 578753dece8SMiguel Ojeda /// The ownership of `ptr` is effectively transferred to the 579753dece8SMiguel Ojeda /// `Vec<T>` which may then deallocate, reallocate or change the 580753dece8SMiguel Ojeda /// contents of memory pointed to by the pointer at will. Ensure 581753dece8SMiguel Ojeda /// that nothing else uses the pointer after calling this 582753dece8SMiguel Ojeda /// function. 583753dece8SMiguel Ojeda /// 584753dece8SMiguel Ojeda /// [`String`]: crate::string::String 5853ed03f4dSMiguel Ojeda /// [`alloc::alloc`]: crate::alloc::alloc 586753dece8SMiguel Ojeda /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc 587753dece8SMiguel Ojeda /// 588753dece8SMiguel Ojeda /// # Examples 589753dece8SMiguel Ojeda /// 590753dece8SMiguel Ojeda /// ``` 591753dece8SMiguel Ojeda /// use std::ptr; 592753dece8SMiguel Ojeda /// use std::mem; 593753dece8SMiguel Ojeda /// 594753dece8SMiguel Ojeda /// let v = vec![1, 2, 3]; 595753dece8SMiguel Ojeda /// 596753dece8SMiguel Ojeda // FIXME Update this when vec_into_raw_parts is stabilized 597753dece8SMiguel Ojeda /// // Prevent running `v`'s destructor so we are in complete control 598753dece8SMiguel Ojeda /// // of the allocation. 599753dece8SMiguel Ojeda /// let mut v = mem::ManuallyDrop::new(v); 600753dece8SMiguel Ojeda /// 601753dece8SMiguel Ojeda /// // Pull out the various important pieces of information about `v` 602753dece8SMiguel Ojeda /// let p = v.as_mut_ptr(); 603753dece8SMiguel Ojeda /// let len = v.len(); 604753dece8SMiguel Ojeda /// let cap = v.capacity(); 605753dece8SMiguel Ojeda /// 606753dece8SMiguel Ojeda /// unsafe { 607753dece8SMiguel Ojeda /// // Overwrite memory with 4, 5, 6 6083ed03f4dSMiguel Ojeda /// for i in 0..len { 6093ed03f4dSMiguel Ojeda /// ptr::write(p.add(i), 4 + i); 610753dece8SMiguel Ojeda /// } 611753dece8SMiguel Ojeda /// 612753dece8SMiguel Ojeda /// // Put everything back together into a Vec 613753dece8SMiguel Ojeda /// let rebuilt = Vec::from_raw_parts(p, len, cap); 614753dece8SMiguel Ojeda /// assert_eq!(rebuilt, [4, 5, 6]); 615753dece8SMiguel Ojeda /// } 616753dece8SMiguel Ojeda /// ``` 6173ed03f4dSMiguel Ojeda /// 6183ed03f4dSMiguel Ojeda /// Using memory that was allocated elsewhere: 6193ed03f4dSMiguel Ojeda /// 6203ed03f4dSMiguel Ojeda /// ```rust 6213ed03f4dSMiguel Ojeda /// #![feature(allocator_api)] 6223ed03f4dSMiguel Ojeda /// 6233ed03f4dSMiguel Ojeda /// use std::alloc::{AllocError, Allocator, Global, Layout}; 6243ed03f4dSMiguel Ojeda /// 6253ed03f4dSMiguel Ojeda /// fn main() { 6263ed03f4dSMiguel Ojeda /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen"); 6273ed03f4dSMiguel Ojeda /// 6283ed03f4dSMiguel Ojeda /// let vec = unsafe { 6293ed03f4dSMiguel Ojeda /// let mem = match Global.allocate(layout) { 6303ed03f4dSMiguel Ojeda /// Ok(mem) => mem.cast::<u32>().as_ptr(), 6313ed03f4dSMiguel Ojeda /// Err(AllocError) => return, 6323ed03f4dSMiguel Ojeda /// }; 6333ed03f4dSMiguel Ojeda /// 6343ed03f4dSMiguel Ojeda /// mem.write(1_000_000); 6353ed03f4dSMiguel Ojeda /// 6363ed03f4dSMiguel Ojeda /// Vec::from_raw_parts_in(mem, 1, 16, Global) 6373ed03f4dSMiguel Ojeda /// }; 6383ed03f4dSMiguel Ojeda /// 6393ed03f4dSMiguel Ojeda /// assert_eq!(vec, &[1_000_000]); 6403ed03f4dSMiguel Ojeda /// assert_eq!(vec.capacity(), 16); 6413ed03f4dSMiguel Ojeda /// } 6423ed03f4dSMiguel Ojeda /// ``` 643753dece8SMiguel Ojeda #[inline] 644753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 645753dece8SMiguel Ojeda pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { 646753dece8SMiguel Ojeda unsafe { Self::from_raw_parts_in(ptr, length, capacity, Global) } 647753dece8SMiguel Ojeda } 648753dece8SMiguel Ojeda } 649753dece8SMiguel Ojeda 650753dece8SMiguel Ojeda impl<T, A: Allocator> Vec<T, A> { 651753dece8SMiguel Ojeda /// Constructs a new, empty `Vec<T, A>`. 652753dece8SMiguel Ojeda /// 653753dece8SMiguel Ojeda /// The vector will not allocate until elements are pushed onto it. 654753dece8SMiguel Ojeda /// 655753dece8SMiguel Ojeda /// # Examples 656753dece8SMiguel Ojeda /// 657753dece8SMiguel Ojeda /// ``` 658753dece8SMiguel Ojeda /// #![feature(allocator_api)] 659753dece8SMiguel Ojeda /// 660753dece8SMiguel Ojeda /// use std::alloc::System; 661753dece8SMiguel Ojeda /// 662753dece8SMiguel Ojeda /// # #[allow(unused_mut)] 663753dece8SMiguel Ojeda /// let mut vec: Vec<i32, _> = Vec::new_in(System); 664753dece8SMiguel Ojeda /// ``` 665753dece8SMiguel Ojeda #[inline] 666753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")] 667753dece8SMiguel Ojeda pub const fn new_in(alloc: A) -> Self { 668753dece8SMiguel Ojeda Vec { buf: RawVec::new_in(alloc), len: 0 } 669753dece8SMiguel Ojeda } 670753dece8SMiguel Ojeda 6713ed03f4dSMiguel Ojeda /// Constructs a new, empty `Vec<T, A>` with at least the specified capacity 6723ed03f4dSMiguel Ojeda /// with the provided allocator. 673753dece8SMiguel Ojeda /// 6743ed03f4dSMiguel Ojeda /// The vector will be able to hold at least `capacity` elements without 6753ed03f4dSMiguel Ojeda /// reallocating. This method is allowed to allocate for more elements than 6763ed03f4dSMiguel Ojeda /// `capacity`. If `capacity` is 0, the vector will not allocate. 677753dece8SMiguel Ojeda /// 678753dece8SMiguel Ojeda /// It is important to note that although the returned vector has the 6793ed03f4dSMiguel Ojeda /// minimum *capacity* specified, the vector will have a zero *length*. For 6803ed03f4dSMiguel Ojeda /// an explanation of the difference between length and capacity, see 681753dece8SMiguel Ojeda /// *[Capacity and reallocation]*. 682753dece8SMiguel Ojeda /// 6833ed03f4dSMiguel Ojeda /// If it is important to know the exact allocated capacity of a `Vec`, 6843ed03f4dSMiguel Ojeda /// always use the [`capacity`] method after construction. 6853ed03f4dSMiguel Ojeda /// 6863ed03f4dSMiguel Ojeda /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation 6873ed03f4dSMiguel Ojeda /// and the capacity will always be `usize::MAX`. 6883ed03f4dSMiguel Ojeda /// 689753dece8SMiguel Ojeda /// [Capacity and reallocation]: #capacity-and-reallocation 6903ed03f4dSMiguel Ojeda /// [`capacity`]: Vec::capacity 691753dece8SMiguel Ojeda /// 692753dece8SMiguel Ojeda /// # Panics 693753dece8SMiguel Ojeda /// 694753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes. 695753dece8SMiguel Ojeda /// 696753dece8SMiguel Ojeda /// # Examples 697753dece8SMiguel Ojeda /// 698753dece8SMiguel Ojeda /// ``` 699753dece8SMiguel Ojeda /// #![feature(allocator_api)] 700753dece8SMiguel Ojeda /// 701753dece8SMiguel Ojeda /// use std::alloc::System; 702753dece8SMiguel Ojeda /// 703753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity_in(10, System); 704753dece8SMiguel Ojeda /// 705753dece8SMiguel Ojeda /// // The vector contains no items, even though it has capacity for more 706753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 0); 707*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 708753dece8SMiguel Ojeda /// 709753dece8SMiguel Ojeda /// // These are all done without reallocating... 710753dece8SMiguel Ojeda /// for i in 0..10 { 711753dece8SMiguel Ojeda /// vec.push(i); 712753dece8SMiguel Ojeda /// } 713753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 10); 714*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 715753dece8SMiguel Ojeda /// 716753dece8SMiguel Ojeda /// // ...but this may make the vector reallocate 717753dece8SMiguel Ojeda /// vec.push(11); 718753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 11); 719753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 11); 7203ed03f4dSMiguel Ojeda /// 7213ed03f4dSMiguel Ojeda /// // A vector of a zero-sized type will always over-allocate, since no 7223ed03f4dSMiguel Ojeda /// // allocation is necessary 7233ed03f4dSMiguel Ojeda /// let vec_units = Vec::<(), System>::with_capacity_in(10, System); 7243ed03f4dSMiguel Ojeda /// assert_eq!(vec_units.capacity(), usize::MAX); 725753dece8SMiguel Ojeda /// ``` 726753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 727753dece8SMiguel Ojeda #[inline] 728753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")] 729753dece8SMiguel Ojeda pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { 730753dece8SMiguel Ojeda Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 } 731753dece8SMiguel Ojeda } 732753dece8SMiguel Ojeda 7333ed03f4dSMiguel Ojeda /// Tries to construct a new, empty `Vec<T, A>` with at least the specified capacity 734feadd062SMiguel Ojeda /// with the provided allocator. 735feadd062SMiguel Ojeda /// 7363ed03f4dSMiguel Ojeda /// The vector will be able to hold at least `capacity` elements without 7373ed03f4dSMiguel Ojeda /// reallocating. This method is allowed to allocate for more elements than 7383ed03f4dSMiguel Ojeda /// `capacity`. If `capacity` is 0, the vector will not allocate. 739feadd062SMiguel Ojeda /// 740feadd062SMiguel Ojeda /// It is important to note that although the returned vector has the 7413ed03f4dSMiguel Ojeda /// minimum *capacity* specified, the vector will have a zero *length*. For 7423ed03f4dSMiguel Ojeda /// an explanation of the difference between length and capacity, see 743feadd062SMiguel Ojeda /// *[Capacity and reallocation]*. 744feadd062SMiguel Ojeda /// 7453ed03f4dSMiguel Ojeda /// If it is important to know the exact allocated capacity of a `Vec`, 7463ed03f4dSMiguel Ojeda /// always use the [`capacity`] method after construction. 7473ed03f4dSMiguel Ojeda /// 7483ed03f4dSMiguel Ojeda /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation 7493ed03f4dSMiguel Ojeda /// and the capacity will always be `usize::MAX`. 7503ed03f4dSMiguel Ojeda /// 751feadd062SMiguel Ojeda /// [Capacity and reallocation]: #capacity-and-reallocation 7523ed03f4dSMiguel Ojeda /// [`capacity`]: Vec::capacity 753feadd062SMiguel Ojeda /// 754feadd062SMiguel Ojeda /// # Examples 755feadd062SMiguel Ojeda /// 756feadd062SMiguel Ojeda /// ``` 757feadd062SMiguel Ojeda /// #![feature(allocator_api)] 758feadd062SMiguel Ojeda /// 759feadd062SMiguel Ojeda /// use std::alloc::System; 760feadd062SMiguel Ojeda /// 761feadd062SMiguel Ojeda /// let mut vec = Vec::try_with_capacity_in(10, System).unwrap(); 762feadd062SMiguel Ojeda /// 763feadd062SMiguel Ojeda /// // The vector contains no items, even though it has capacity for more 764feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 0); 765*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 766feadd062SMiguel Ojeda /// 767feadd062SMiguel Ojeda /// // These are all done without reallocating... 768feadd062SMiguel Ojeda /// for i in 0..10 { 769feadd062SMiguel Ojeda /// vec.push(i); 770feadd062SMiguel Ojeda /// } 771feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 10); 772*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 773feadd062SMiguel Ojeda /// 774feadd062SMiguel Ojeda /// // ...but this may make the vector reallocate 775feadd062SMiguel Ojeda /// vec.push(11); 776feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 11); 777feadd062SMiguel Ojeda /// assert!(vec.capacity() >= 11); 778feadd062SMiguel Ojeda /// 779feadd062SMiguel Ojeda /// let mut result = Vec::try_with_capacity_in(usize::MAX, System); 780feadd062SMiguel Ojeda /// assert!(result.is_err()); 7813ed03f4dSMiguel Ojeda /// 7823ed03f4dSMiguel Ojeda /// // A vector of a zero-sized type will always over-allocate, since no 7833ed03f4dSMiguel Ojeda /// // allocation is necessary 7843ed03f4dSMiguel Ojeda /// let vec_units = Vec::<(), System>::try_with_capacity_in(10, System).unwrap(); 7853ed03f4dSMiguel Ojeda /// assert_eq!(vec_units.capacity(), usize::MAX); 786feadd062SMiguel Ojeda /// ``` 787feadd062SMiguel Ojeda #[inline] 788feadd062SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")] 789feadd062SMiguel Ojeda pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> { 790feadd062SMiguel Ojeda Ok(Vec { buf: RawVec::try_with_capacity_in(capacity, alloc)?, len: 0 }) 791feadd062SMiguel Ojeda } 792feadd062SMiguel Ojeda 7933ed03f4dSMiguel Ojeda /// Creates a `Vec<T, A>` directly from a pointer, a capacity, a length, 7943ed03f4dSMiguel Ojeda /// and an allocator. 795753dece8SMiguel Ojeda /// 796753dece8SMiguel Ojeda /// # Safety 797753dece8SMiguel Ojeda /// 798753dece8SMiguel Ojeda /// This is highly unsafe, due to the number of invariants that aren't 799753dece8SMiguel Ojeda /// checked: 800753dece8SMiguel Ojeda /// 8013ed03f4dSMiguel Ojeda /// * `ptr` must be [*currently allocated*] via the given allocator `alloc`. 8023ed03f4dSMiguel Ojeda /// * `T` needs to have the same alignment as what `ptr` was allocated with. 803753dece8SMiguel Ojeda /// (`T` having a less strict alignment is not sufficient, the alignment really 804753dece8SMiguel Ojeda /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be 805753dece8SMiguel Ojeda /// allocated and deallocated with the same layout.) 8063ed03f4dSMiguel Ojeda /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs 8073ed03f4dSMiguel Ojeda /// to be the same size as the pointer was allocated with. (Because similar to 8083ed03f4dSMiguel Ojeda /// alignment, [`dealloc`] must be called with the same layout `size`.) 809753dece8SMiguel Ojeda /// * `length` needs to be less than or equal to `capacity`. 8103ed03f4dSMiguel Ojeda /// * The first `length` values must be properly initialized values of type `T`. 8113ed03f4dSMiguel Ojeda /// * `capacity` needs to [*fit*] the layout size that the pointer was allocated with. 8123ed03f4dSMiguel Ojeda /// * The allocated size in bytes must be no larger than `isize::MAX`. 8133ed03f4dSMiguel Ojeda /// See the safety documentation of [`pointer::offset`]. 8143ed03f4dSMiguel Ojeda /// 8153ed03f4dSMiguel Ojeda /// These requirements are always upheld by any `ptr` that has been allocated 8163ed03f4dSMiguel Ojeda /// via `Vec<T, A>`. Other allocation sources are allowed if the invariants are 8173ed03f4dSMiguel Ojeda /// upheld. 818753dece8SMiguel Ojeda /// 819753dece8SMiguel Ojeda /// Violating these may cause problems like corrupting the allocator's 820753dece8SMiguel Ojeda /// internal data structures. For example it is **not** safe 821753dece8SMiguel Ojeda /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`. 822753dece8SMiguel Ojeda /// It's also not safe to build one from a `Vec<u16>` and its length, because 823753dece8SMiguel Ojeda /// the allocator cares about the alignment, and these two types have different 824753dece8SMiguel Ojeda /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after 825753dece8SMiguel Ojeda /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1. 826753dece8SMiguel Ojeda /// 827753dece8SMiguel Ojeda /// The ownership of `ptr` is effectively transferred to the 828753dece8SMiguel Ojeda /// `Vec<T>` which may then deallocate, reallocate or change the 829753dece8SMiguel Ojeda /// contents of memory pointed to by the pointer at will. Ensure 830753dece8SMiguel Ojeda /// that nothing else uses the pointer after calling this 831753dece8SMiguel Ojeda /// function. 832753dece8SMiguel Ojeda /// 833753dece8SMiguel Ojeda /// [`String`]: crate::string::String 834753dece8SMiguel Ojeda /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc 8353ed03f4dSMiguel Ojeda /// [*currently allocated*]: crate::alloc::Allocator#currently-allocated-memory 8363ed03f4dSMiguel Ojeda /// [*fit*]: crate::alloc::Allocator#memory-fitting 837753dece8SMiguel Ojeda /// 838753dece8SMiguel Ojeda /// # Examples 839753dece8SMiguel Ojeda /// 840753dece8SMiguel Ojeda /// ``` 841753dece8SMiguel Ojeda /// #![feature(allocator_api)] 842753dece8SMiguel Ojeda /// 843753dece8SMiguel Ojeda /// use std::alloc::System; 844753dece8SMiguel Ojeda /// 845753dece8SMiguel Ojeda /// use std::ptr; 846753dece8SMiguel Ojeda /// use std::mem; 847753dece8SMiguel Ojeda /// 848753dece8SMiguel Ojeda /// let mut v = Vec::with_capacity_in(3, System); 849753dece8SMiguel Ojeda /// v.push(1); 850753dece8SMiguel Ojeda /// v.push(2); 851753dece8SMiguel Ojeda /// v.push(3); 852753dece8SMiguel Ojeda /// 853753dece8SMiguel Ojeda // FIXME Update this when vec_into_raw_parts is stabilized 854753dece8SMiguel Ojeda /// // Prevent running `v`'s destructor so we are in complete control 855753dece8SMiguel Ojeda /// // of the allocation. 856753dece8SMiguel Ojeda /// let mut v = mem::ManuallyDrop::new(v); 857753dece8SMiguel Ojeda /// 858753dece8SMiguel Ojeda /// // Pull out the various important pieces of information about `v` 859753dece8SMiguel Ojeda /// let p = v.as_mut_ptr(); 860753dece8SMiguel Ojeda /// let len = v.len(); 861753dece8SMiguel Ojeda /// let cap = v.capacity(); 862753dece8SMiguel Ojeda /// let alloc = v.allocator(); 863753dece8SMiguel Ojeda /// 864753dece8SMiguel Ojeda /// unsafe { 865753dece8SMiguel Ojeda /// // Overwrite memory with 4, 5, 6 8663ed03f4dSMiguel Ojeda /// for i in 0..len { 8673ed03f4dSMiguel Ojeda /// ptr::write(p.add(i), 4 + i); 868753dece8SMiguel Ojeda /// } 869753dece8SMiguel Ojeda /// 870753dece8SMiguel Ojeda /// // Put everything back together into a Vec 871753dece8SMiguel Ojeda /// let rebuilt = Vec::from_raw_parts_in(p, len, cap, alloc.clone()); 872753dece8SMiguel Ojeda /// assert_eq!(rebuilt, [4, 5, 6]); 873753dece8SMiguel Ojeda /// } 874753dece8SMiguel Ojeda /// ``` 8753ed03f4dSMiguel Ojeda /// 8763ed03f4dSMiguel Ojeda /// Using memory that was allocated elsewhere: 8773ed03f4dSMiguel Ojeda /// 8783ed03f4dSMiguel Ojeda /// ```rust 8793ed03f4dSMiguel Ojeda /// use std::alloc::{alloc, Layout}; 8803ed03f4dSMiguel Ojeda /// 8813ed03f4dSMiguel Ojeda /// fn main() { 8823ed03f4dSMiguel Ojeda /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen"); 8833ed03f4dSMiguel Ojeda /// let vec = unsafe { 8843ed03f4dSMiguel Ojeda /// let mem = alloc(layout).cast::<u32>(); 8853ed03f4dSMiguel Ojeda /// if mem.is_null() { 8863ed03f4dSMiguel Ojeda /// return; 8873ed03f4dSMiguel Ojeda /// } 8883ed03f4dSMiguel Ojeda /// 8893ed03f4dSMiguel Ojeda /// mem.write(1_000_000); 8903ed03f4dSMiguel Ojeda /// 8913ed03f4dSMiguel Ojeda /// Vec::from_raw_parts(mem, 1, 16) 8923ed03f4dSMiguel Ojeda /// }; 8933ed03f4dSMiguel Ojeda /// 8943ed03f4dSMiguel Ojeda /// assert_eq!(vec, &[1_000_000]); 8953ed03f4dSMiguel Ojeda /// assert_eq!(vec.capacity(), 16); 8963ed03f4dSMiguel Ojeda /// } 8973ed03f4dSMiguel Ojeda /// ``` 898753dece8SMiguel Ojeda #[inline] 899753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")] 900753dece8SMiguel Ojeda pub unsafe fn from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self { 901753dece8SMiguel Ojeda unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } } 902753dece8SMiguel Ojeda } 903753dece8SMiguel Ojeda 904753dece8SMiguel Ojeda /// Decomposes a `Vec<T>` into its raw components. 905753dece8SMiguel Ojeda /// 906753dece8SMiguel Ojeda /// Returns the raw pointer to the underlying data, the length of 907753dece8SMiguel Ojeda /// the vector (in elements), and the allocated capacity of the 908753dece8SMiguel Ojeda /// data (in elements). These are the same arguments in the same 909753dece8SMiguel Ojeda /// order as the arguments to [`from_raw_parts`]. 910753dece8SMiguel Ojeda /// 911753dece8SMiguel Ojeda /// After calling this function, the caller is responsible for the 912753dece8SMiguel Ojeda /// memory previously managed by the `Vec`. The only way to do 913753dece8SMiguel Ojeda /// this is to convert the raw pointer, length, and capacity back 914753dece8SMiguel Ojeda /// into a `Vec` with the [`from_raw_parts`] function, allowing 915753dece8SMiguel Ojeda /// the destructor to perform the cleanup. 916753dece8SMiguel Ojeda /// 917753dece8SMiguel Ojeda /// [`from_raw_parts`]: Vec::from_raw_parts 918753dece8SMiguel Ojeda /// 919753dece8SMiguel Ojeda /// # Examples 920753dece8SMiguel Ojeda /// 921753dece8SMiguel Ojeda /// ``` 922753dece8SMiguel Ojeda /// #![feature(vec_into_raw_parts)] 923753dece8SMiguel Ojeda /// let v: Vec<i32> = vec![-1, 0, 1]; 924753dece8SMiguel Ojeda /// 925753dece8SMiguel Ojeda /// let (ptr, len, cap) = v.into_raw_parts(); 926753dece8SMiguel Ojeda /// 927753dece8SMiguel Ojeda /// let rebuilt = unsafe { 928753dece8SMiguel Ojeda /// // We can now make changes to the components, such as 929753dece8SMiguel Ojeda /// // transmuting the raw pointer to a compatible type. 930753dece8SMiguel Ojeda /// let ptr = ptr as *mut u32; 931753dece8SMiguel Ojeda /// 932753dece8SMiguel Ojeda /// Vec::from_raw_parts(ptr, len, cap) 933753dece8SMiguel Ojeda /// }; 934753dece8SMiguel Ojeda /// assert_eq!(rebuilt, [4294967295, 0, 1]); 935753dece8SMiguel Ojeda /// ``` 936753dece8SMiguel Ojeda #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")] 937753dece8SMiguel Ojeda pub fn into_raw_parts(self) -> (*mut T, usize, usize) { 938753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self); 939753dece8SMiguel Ojeda (me.as_mut_ptr(), me.len(), me.capacity()) 940753dece8SMiguel Ojeda } 941753dece8SMiguel Ojeda 942753dece8SMiguel Ojeda /// Decomposes a `Vec<T>` into its raw components. 943753dece8SMiguel Ojeda /// 944753dece8SMiguel Ojeda /// Returns the raw pointer to the underlying data, the length of the vector (in elements), 945753dece8SMiguel Ojeda /// the allocated capacity of the data (in elements), and the allocator. These are the same 946753dece8SMiguel Ojeda /// arguments in the same order as the arguments to [`from_raw_parts_in`]. 947753dece8SMiguel Ojeda /// 948753dece8SMiguel Ojeda /// After calling this function, the caller is responsible for the 949753dece8SMiguel Ojeda /// memory previously managed by the `Vec`. The only way to do 950753dece8SMiguel Ojeda /// this is to convert the raw pointer, length, and capacity back 951753dece8SMiguel Ojeda /// into a `Vec` with the [`from_raw_parts_in`] function, allowing 952753dece8SMiguel Ojeda /// the destructor to perform the cleanup. 953753dece8SMiguel Ojeda /// 954753dece8SMiguel Ojeda /// [`from_raw_parts_in`]: Vec::from_raw_parts_in 955753dece8SMiguel Ojeda /// 956753dece8SMiguel Ojeda /// # Examples 957753dece8SMiguel Ojeda /// 958753dece8SMiguel Ojeda /// ``` 959753dece8SMiguel Ojeda /// #![feature(allocator_api, vec_into_raw_parts)] 960753dece8SMiguel Ojeda /// 961753dece8SMiguel Ojeda /// use std::alloc::System; 962753dece8SMiguel Ojeda /// 963753dece8SMiguel Ojeda /// let mut v: Vec<i32, System> = Vec::new_in(System); 964753dece8SMiguel Ojeda /// v.push(-1); 965753dece8SMiguel Ojeda /// v.push(0); 966753dece8SMiguel Ojeda /// v.push(1); 967753dece8SMiguel Ojeda /// 968753dece8SMiguel Ojeda /// let (ptr, len, cap, alloc) = v.into_raw_parts_with_alloc(); 969753dece8SMiguel Ojeda /// 970753dece8SMiguel Ojeda /// let rebuilt = unsafe { 971753dece8SMiguel Ojeda /// // We can now make changes to the components, such as 972753dece8SMiguel Ojeda /// // transmuting the raw pointer to a compatible type. 973753dece8SMiguel Ojeda /// let ptr = ptr as *mut u32; 974753dece8SMiguel Ojeda /// 975753dece8SMiguel Ojeda /// Vec::from_raw_parts_in(ptr, len, cap, alloc) 976753dece8SMiguel Ojeda /// }; 977753dece8SMiguel Ojeda /// assert_eq!(rebuilt, [4294967295, 0, 1]); 978753dece8SMiguel Ojeda /// ``` 979753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")] 980753dece8SMiguel Ojeda // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")] 981753dece8SMiguel Ojeda pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) { 982753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self); 983753dece8SMiguel Ojeda let len = me.len(); 984753dece8SMiguel Ojeda let capacity = me.capacity(); 985753dece8SMiguel Ojeda let ptr = me.as_mut_ptr(); 986753dece8SMiguel Ojeda let alloc = unsafe { ptr::read(me.allocator()) }; 987753dece8SMiguel Ojeda (ptr, len, capacity, alloc) 988753dece8SMiguel Ojeda } 989753dece8SMiguel Ojeda 9903ed03f4dSMiguel Ojeda /// Returns the total number of elements the vector can hold without 991753dece8SMiguel Ojeda /// reallocating. 992753dece8SMiguel Ojeda /// 993753dece8SMiguel Ojeda /// # Examples 994753dece8SMiguel Ojeda /// 995753dece8SMiguel Ojeda /// ``` 9963ed03f4dSMiguel Ojeda /// let mut vec: Vec<i32> = Vec::with_capacity(10); 9973ed03f4dSMiguel Ojeda /// vec.push(42); 998*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 999753dece8SMiguel Ojeda /// ``` 1000753dece8SMiguel Ojeda #[inline] 1001753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1002753dece8SMiguel Ojeda pub fn capacity(&self) -> usize { 1003753dece8SMiguel Ojeda self.buf.capacity() 1004753dece8SMiguel Ojeda } 1005753dece8SMiguel Ojeda 1006753dece8SMiguel Ojeda /// Reserves capacity for at least `additional` more elements to be inserted 10073ed03f4dSMiguel Ojeda /// in the given `Vec<T>`. The collection may reserve more space to 10083ed03f4dSMiguel Ojeda /// speculatively avoid frequent reallocations. After calling `reserve`, 10093ed03f4dSMiguel Ojeda /// capacity will be greater than or equal to `self.len() + additional`. 10103ed03f4dSMiguel Ojeda /// Does nothing if capacity is already sufficient. 1011753dece8SMiguel Ojeda /// 1012753dece8SMiguel Ojeda /// # Panics 1013753dece8SMiguel Ojeda /// 1014753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes. 1015753dece8SMiguel Ojeda /// 1016753dece8SMiguel Ojeda /// # Examples 1017753dece8SMiguel Ojeda /// 1018753dece8SMiguel Ojeda /// ``` 1019753dece8SMiguel Ojeda /// let mut vec = vec![1]; 1020753dece8SMiguel Ojeda /// vec.reserve(10); 1021753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 11); 1022753dece8SMiguel Ojeda /// ``` 1023753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1024753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1025753dece8SMiguel Ojeda pub fn reserve(&mut self, additional: usize) { 1026753dece8SMiguel Ojeda self.buf.reserve(self.len, additional); 1027753dece8SMiguel Ojeda } 1028753dece8SMiguel Ojeda 10293ed03f4dSMiguel Ojeda /// Reserves the minimum capacity for at least `additional` more elements to 10303ed03f4dSMiguel Ojeda /// be inserted in the given `Vec<T>`. Unlike [`reserve`], this will not 10313ed03f4dSMiguel Ojeda /// deliberately over-allocate to speculatively avoid frequent allocations. 10323ed03f4dSMiguel Ojeda /// After calling `reserve_exact`, capacity will be greater than or equal to 10333ed03f4dSMiguel Ojeda /// `self.len() + additional`. Does nothing if the capacity is already 10343ed03f4dSMiguel Ojeda /// sufficient. 1035753dece8SMiguel Ojeda /// 1036753dece8SMiguel Ojeda /// Note that the allocator may give the collection more space than it 1037753dece8SMiguel Ojeda /// requests. Therefore, capacity can not be relied upon to be precisely 1038753dece8SMiguel Ojeda /// minimal. Prefer [`reserve`] if future insertions are expected. 1039753dece8SMiguel Ojeda /// 1040753dece8SMiguel Ojeda /// [`reserve`]: Vec::reserve 1041753dece8SMiguel Ojeda /// 1042753dece8SMiguel Ojeda /// # Panics 1043753dece8SMiguel Ojeda /// 1044753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes. 1045753dece8SMiguel Ojeda /// 1046753dece8SMiguel Ojeda /// # Examples 1047753dece8SMiguel Ojeda /// 1048753dece8SMiguel Ojeda /// ``` 1049753dece8SMiguel Ojeda /// let mut vec = vec![1]; 1050753dece8SMiguel Ojeda /// vec.reserve_exact(10); 1051753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 11); 1052753dece8SMiguel Ojeda /// ``` 1053753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1054753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1055753dece8SMiguel Ojeda pub fn reserve_exact(&mut self, additional: usize) { 1056753dece8SMiguel Ojeda self.buf.reserve_exact(self.len, additional); 1057753dece8SMiguel Ojeda } 1058753dece8SMiguel Ojeda 1059753dece8SMiguel Ojeda /// Tries to reserve capacity for at least `additional` more elements to be inserted 10603ed03f4dSMiguel Ojeda /// in the given `Vec<T>`. The collection may reserve more space to speculatively avoid 1061753dece8SMiguel Ojeda /// frequent reallocations. After calling `try_reserve`, capacity will be 10623ed03f4dSMiguel Ojeda /// greater than or equal to `self.len() + additional` if it returns 10633ed03f4dSMiguel Ojeda /// `Ok(())`. Does nothing if capacity is already sufficient. This method 10643ed03f4dSMiguel Ojeda /// preserves the contents even if an error occurs. 1065753dece8SMiguel Ojeda /// 1066753dece8SMiguel Ojeda /// # Errors 1067753dece8SMiguel Ojeda /// 1068753dece8SMiguel Ojeda /// If the capacity overflows, or the allocator reports a failure, then an error 1069753dece8SMiguel Ojeda /// is returned. 1070753dece8SMiguel Ojeda /// 1071753dece8SMiguel Ojeda /// # Examples 1072753dece8SMiguel Ojeda /// 1073753dece8SMiguel Ojeda /// ``` 1074753dece8SMiguel Ojeda /// use std::collections::TryReserveError; 1075753dece8SMiguel Ojeda /// 1076753dece8SMiguel Ojeda /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> { 1077753dece8SMiguel Ojeda /// let mut output = Vec::new(); 1078753dece8SMiguel Ojeda /// 1079753dece8SMiguel Ojeda /// // Pre-reserve the memory, exiting if we can't 1080753dece8SMiguel Ojeda /// output.try_reserve(data.len())?; 1081753dece8SMiguel Ojeda /// 1082753dece8SMiguel Ojeda /// // Now we know this can't OOM in the middle of our complex work 1083753dece8SMiguel Ojeda /// output.extend(data.iter().map(|&val| { 1084753dece8SMiguel Ojeda /// val * 2 + 5 // very complicated 1085753dece8SMiguel Ojeda /// })); 1086753dece8SMiguel Ojeda /// 1087753dece8SMiguel Ojeda /// Ok(output) 1088753dece8SMiguel Ojeda /// } 1089753dece8SMiguel Ojeda /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); 1090753dece8SMiguel Ojeda /// ``` 1091753dece8SMiguel Ojeda #[stable(feature = "try_reserve", since = "1.57.0")] 1092753dece8SMiguel Ojeda pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { 1093753dece8SMiguel Ojeda self.buf.try_reserve(self.len, additional) 1094753dece8SMiguel Ojeda } 1095753dece8SMiguel Ojeda 10963ed03f4dSMiguel Ojeda /// Tries to reserve the minimum capacity for at least `additional` 10973ed03f4dSMiguel Ojeda /// elements to be inserted in the given `Vec<T>`. Unlike [`try_reserve`], 10983ed03f4dSMiguel Ojeda /// this will not deliberately over-allocate to speculatively avoid frequent 10993ed03f4dSMiguel Ojeda /// allocations. After calling `try_reserve_exact`, capacity will be greater 11003ed03f4dSMiguel Ojeda /// than or equal to `self.len() + additional` if it returns `Ok(())`. 1101753dece8SMiguel Ojeda /// Does nothing if the capacity is already sufficient. 1102753dece8SMiguel Ojeda /// 1103753dece8SMiguel Ojeda /// Note that the allocator may give the collection more space than it 1104753dece8SMiguel Ojeda /// requests. Therefore, capacity can not be relied upon to be precisely 1105753dece8SMiguel Ojeda /// minimal. Prefer [`try_reserve`] if future insertions are expected. 1106753dece8SMiguel Ojeda /// 1107753dece8SMiguel Ojeda /// [`try_reserve`]: Vec::try_reserve 1108753dece8SMiguel Ojeda /// 1109753dece8SMiguel Ojeda /// # Errors 1110753dece8SMiguel Ojeda /// 1111753dece8SMiguel Ojeda /// If the capacity overflows, or the allocator reports a failure, then an error 1112753dece8SMiguel Ojeda /// is returned. 1113753dece8SMiguel Ojeda /// 1114753dece8SMiguel Ojeda /// # Examples 1115753dece8SMiguel Ojeda /// 1116753dece8SMiguel Ojeda /// ``` 1117753dece8SMiguel Ojeda /// use std::collections::TryReserveError; 1118753dece8SMiguel Ojeda /// 1119753dece8SMiguel Ojeda /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> { 1120753dece8SMiguel Ojeda /// let mut output = Vec::new(); 1121753dece8SMiguel Ojeda /// 1122753dece8SMiguel Ojeda /// // Pre-reserve the memory, exiting if we can't 1123753dece8SMiguel Ojeda /// output.try_reserve_exact(data.len())?; 1124753dece8SMiguel Ojeda /// 1125753dece8SMiguel Ojeda /// // Now we know this can't OOM in the middle of our complex work 1126753dece8SMiguel Ojeda /// output.extend(data.iter().map(|&val| { 1127753dece8SMiguel Ojeda /// val * 2 + 5 // very complicated 1128753dece8SMiguel Ojeda /// })); 1129753dece8SMiguel Ojeda /// 1130753dece8SMiguel Ojeda /// Ok(output) 1131753dece8SMiguel Ojeda /// } 1132753dece8SMiguel Ojeda /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); 1133753dece8SMiguel Ojeda /// ``` 1134753dece8SMiguel Ojeda #[stable(feature = "try_reserve", since = "1.57.0")] 1135753dece8SMiguel Ojeda pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { 1136753dece8SMiguel Ojeda self.buf.try_reserve_exact(self.len, additional) 1137753dece8SMiguel Ojeda } 1138753dece8SMiguel Ojeda 1139753dece8SMiguel Ojeda /// Shrinks the capacity of the vector as much as possible. 1140753dece8SMiguel Ojeda /// 1141753dece8SMiguel Ojeda /// It will drop down as close as possible to the length but the allocator 1142753dece8SMiguel Ojeda /// may still inform the vector that there is space for a few more elements. 1143753dece8SMiguel Ojeda /// 1144753dece8SMiguel Ojeda /// # Examples 1145753dece8SMiguel Ojeda /// 1146753dece8SMiguel Ojeda /// ``` 1147753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(10); 1148753dece8SMiguel Ojeda /// vec.extend([1, 2, 3]); 1149*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 1150753dece8SMiguel Ojeda /// vec.shrink_to_fit(); 1151753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 3); 1152753dece8SMiguel Ojeda /// ``` 1153753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1154753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1155753dece8SMiguel Ojeda pub fn shrink_to_fit(&mut self) { 1156753dece8SMiguel Ojeda // The capacity is never less than the length, and there's nothing to do when 1157753dece8SMiguel Ojeda // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit` 1158753dece8SMiguel Ojeda // by only calling it with a greater capacity. 1159753dece8SMiguel Ojeda if self.capacity() > self.len { 1160753dece8SMiguel Ojeda self.buf.shrink_to_fit(self.len); 1161753dece8SMiguel Ojeda } 1162753dece8SMiguel Ojeda } 1163753dece8SMiguel Ojeda 1164753dece8SMiguel Ojeda /// Shrinks the capacity of the vector with a lower bound. 1165753dece8SMiguel Ojeda /// 1166753dece8SMiguel Ojeda /// The capacity will remain at least as large as both the length 1167753dece8SMiguel Ojeda /// and the supplied value. 1168753dece8SMiguel Ojeda /// 1169753dece8SMiguel Ojeda /// If the current capacity is less than the lower limit, this is a no-op. 1170753dece8SMiguel Ojeda /// 1171753dece8SMiguel Ojeda /// # Examples 1172753dece8SMiguel Ojeda /// 1173753dece8SMiguel Ojeda /// ``` 1174753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(10); 1175753dece8SMiguel Ojeda /// vec.extend([1, 2, 3]); 1176*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 1177753dece8SMiguel Ojeda /// vec.shrink_to(4); 1178753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 4); 1179753dece8SMiguel Ojeda /// vec.shrink_to(0); 1180753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 3); 1181753dece8SMiguel Ojeda /// ``` 1182753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1183753dece8SMiguel Ojeda #[stable(feature = "shrink_to", since = "1.56.0")] 1184753dece8SMiguel Ojeda pub fn shrink_to(&mut self, min_capacity: usize) { 1185753dece8SMiguel Ojeda if self.capacity() > min_capacity { 1186753dece8SMiguel Ojeda self.buf.shrink_to_fit(cmp::max(self.len, min_capacity)); 1187753dece8SMiguel Ojeda } 1188753dece8SMiguel Ojeda } 1189753dece8SMiguel Ojeda 1190753dece8SMiguel Ojeda /// Converts the vector into [`Box<[T]>`][owned slice]. 1191753dece8SMiguel Ojeda /// 11923ed03f4dSMiguel Ojeda /// If the vector has excess capacity, its items will be moved into a 11933ed03f4dSMiguel Ojeda /// newly-allocated buffer with exactly the right capacity. 1194753dece8SMiguel Ojeda /// 1195753dece8SMiguel Ojeda /// [owned slice]: Box 1196753dece8SMiguel Ojeda /// 1197753dece8SMiguel Ojeda /// # Examples 1198753dece8SMiguel Ojeda /// 1199753dece8SMiguel Ojeda /// ``` 1200753dece8SMiguel Ojeda /// let v = vec![1, 2, 3]; 1201753dece8SMiguel Ojeda /// 1202753dece8SMiguel Ojeda /// let slice = v.into_boxed_slice(); 1203753dece8SMiguel Ojeda /// ``` 1204753dece8SMiguel Ojeda /// 1205753dece8SMiguel Ojeda /// Any excess capacity is removed: 1206753dece8SMiguel Ojeda /// 1207753dece8SMiguel Ojeda /// ``` 1208753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(10); 1209753dece8SMiguel Ojeda /// vec.extend([1, 2, 3]); 1210753dece8SMiguel Ojeda /// 1211*89eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10); 1212753dece8SMiguel Ojeda /// let slice = vec.into_boxed_slice(); 1213753dece8SMiguel Ojeda /// assert_eq!(slice.into_vec().capacity(), 3); 1214753dece8SMiguel Ojeda /// ``` 1215753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1216753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1217753dece8SMiguel Ojeda pub fn into_boxed_slice(mut self) -> Box<[T], A> { 1218753dece8SMiguel Ojeda unsafe { 1219753dece8SMiguel Ojeda self.shrink_to_fit(); 1220753dece8SMiguel Ojeda let me = ManuallyDrop::new(self); 1221753dece8SMiguel Ojeda let buf = ptr::read(&me.buf); 1222753dece8SMiguel Ojeda let len = me.len(); 1223753dece8SMiguel Ojeda buf.into_box(len).assume_init() 1224753dece8SMiguel Ojeda } 1225753dece8SMiguel Ojeda } 1226753dece8SMiguel Ojeda 1227753dece8SMiguel Ojeda /// Shortens the vector, keeping the first `len` elements and dropping 1228753dece8SMiguel Ojeda /// the rest. 1229753dece8SMiguel Ojeda /// 1230753dece8SMiguel Ojeda /// If `len` is greater than the vector's current length, this has no 1231753dece8SMiguel Ojeda /// effect. 1232753dece8SMiguel Ojeda /// 1233753dece8SMiguel Ojeda /// The [`drain`] method can emulate `truncate`, but causes the excess 1234753dece8SMiguel Ojeda /// elements to be returned instead of dropped. 1235753dece8SMiguel Ojeda /// 1236753dece8SMiguel Ojeda /// Note that this method has no effect on the allocated capacity 1237753dece8SMiguel Ojeda /// of the vector. 1238753dece8SMiguel Ojeda /// 1239753dece8SMiguel Ojeda /// # Examples 1240753dece8SMiguel Ojeda /// 1241753dece8SMiguel Ojeda /// Truncating a five element vector to two elements: 1242753dece8SMiguel Ojeda /// 1243753dece8SMiguel Ojeda /// ``` 1244753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4, 5]; 1245753dece8SMiguel Ojeda /// vec.truncate(2); 1246753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2]); 1247753dece8SMiguel Ojeda /// ``` 1248753dece8SMiguel Ojeda /// 1249753dece8SMiguel Ojeda /// No truncation occurs when `len` is greater than the vector's current 1250753dece8SMiguel Ojeda /// length: 1251753dece8SMiguel Ojeda /// 1252753dece8SMiguel Ojeda /// ``` 1253753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3]; 1254753dece8SMiguel Ojeda /// vec.truncate(8); 1255753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3]); 1256753dece8SMiguel Ojeda /// ``` 1257753dece8SMiguel Ojeda /// 1258753dece8SMiguel Ojeda /// Truncating when `len == 0` is equivalent to calling the [`clear`] 1259753dece8SMiguel Ojeda /// method. 1260753dece8SMiguel Ojeda /// 1261753dece8SMiguel Ojeda /// ``` 1262753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3]; 1263753dece8SMiguel Ojeda /// vec.truncate(0); 1264753dece8SMiguel Ojeda /// assert_eq!(vec, []); 1265753dece8SMiguel Ojeda /// ``` 1266753dece8SMiguel Ojeda /// 1267753dece8SMiguel Ojeda /// [`clear`]: Vec::clear 1268753dece8SMiguel Ojeda /// [`drain`]: Vec::drain 1269753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1270753dece8SMiguel Ojeda pub fn truncate(&mut self, len: usize) { 1271753dece8SMiguel Ojeda // This is safe because: 1272753dece8SMiguel Ojeda // 1273753dece8SMiguel Ojeda // * the slice passed to `drop_in_place` is valid; the `len > self.len` 1274753dece8SMiguel Ojeda // case avoids creating an invalid slice, and 1275753dece8SMiguel Ojeda // * the `len` of the vector is shrunk before calling `drop_in_place`, 1276753dece8SMiguel Ojeda // such that no value will be dropped twice in case `drop_in_place` 1277753dece8SMiguel Ojeda // were to panic once (if it panics twice, the program aborts). 1278753dece8SMiguel Ojeda unsafe { 1279753dece8SMiguel Ojeda // Note: It's intentional that this is `>` and not `>=`. 1280753dece8SMiguel Ojeda // Changing it to `>=` has negative performance 1281753dece8SMiguel Ojeda // implications in some cases. See #78884 for more. 1282753dece8SMiguel Ojeda if len > self.len { 1283753dece8SMiguel Ojeda return; 1284753dece8SMiguel Ojeda } 1285753dece8SMiguel Ojeda let remaining_len = self.len - len; 1286753dece8SMiguel Ojeda let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len); 1287753dece8SMiguel Ojeda self.len = len; 1288753dece8SMiguel Ojeda ptr::drop_in_place(s); 1289753dece8SMiguel Ojeda } 1290753dece8SMiguel Ojeda } 1291753dece8SMiguel Ojeda 1292753dece8SMiguel Ojeda /// Extracts a slice containing the entire vector. 1293753dece8SMiguel Ojeda /// 1294753dece8SMiguel Ojeda /// Equivalent to `&s[..]`. 1295753dece8SMiguel Ojeda /// 1296753dece8SMiguel Ojeda /// # Examples 1297753dece8SMiguel Ojeda /// 1298753dece8SMiguel Ojeda /// ``` 1299753dece8SMiguel Ojeda /// use std::io::{self, Write}; 1300753dece8SMiguel Ojeda /// let buffer = vec![1, 2, 3, 5, 8]; 1301753dece8SMiguel Ojeda /// io::sink().write(buffer.as_slice()).unwrap(); 1302753dece8SMiguel Ojeda /// ``` 1303753dece8SMiguel Ojeda #[inline] 1304753dece8SMiguel Ojeda #[stable(feature = "vec_as_slice", since = "1.7.0")] 1305753dece8SMiguel Ojeda pub fn as_slice(&self) -> &[T] { 1306753dece8SMiguel Ojeda self 1307753dece8SMiguel Ojeda } 1308753dece8SMiguel Ojeda 1309753dece8SMiguel Ojeda /// Extracts a mutable slice of the entire vector. 1310753dece8SMiguel Ojeda /// 1311753dece8SMiguel Ojeda /// Equivalent to `&mut s[..]`. 1312753dece8SMiguel Ojeda /// 1313753dece8SMiguel Ojeda /// # Examples 1314753dece8SMiguel Ojeda /// 1315753dece8SMiguel Ojeda /// ``` 1316753dece8SMiguel Ojeda /// use std::io::{self, Read}; 1317753dece8SMiguel Ojeda /// let mut buffer = vec![0; 3]; 1318753dece8SMiguel Ojeda /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap(); 1319753dece8SMiguel Ojeda /// ``` 1320753dece8SMiguel Ojeda #[inline] 1321753dece8SMiguel Ojeda #[stable(feature = "vec_as_slice", since = "1.7.0")] 1322753dece8SMiguel Ojeda pub fn as_mut_slice(&mut self) -> &mut [T] { 1323753dece8SMiguel Ojeda self 1324753dece8SMiguel Ojeda } 1325753dece8SMiguel Ojeda 13263ed03f4dSMiguel Ojeda /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer 13273ed03f4dSMiguel Ojeda /// valid for zero sized reads if the vector didn't allocate. 1328753dece8SMiguel Ojeda /// 1329753dece8SMiguel Ojeda /// The caller must ensure that the vector outlives the pointer this 1330753dece8SMiguel Ojeda /// function returns, or else it will end up pointing to garbage. 1331753dece8SMiguel Ojeda /// Modifying the vector may cause its buffer to be reallocated, 1332753dece8SMiguel Ojeda /// which would also make any pointers to it invalid. 1333753dece8SMiguel Ojeda /// 1334753dece8SMiguel Ojeda /// The caller must also ensure that the memory the pointer (non-transitively) points to 1335753dece8SMiguel Ojeda /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer 1336753dece8SMiguel Ojeda /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`]. 1337753dece8SMiguel Ojeda /// 1338753dece8SMiguel Ojeda /// # Examples 1339753dece8SMiguel Ojeda /// 1340753dece8SMiguel Ojeda /// ``` 1341753dece8SMiguel Ojeda /// let x = vec![1, 2, 4]; 1342753dece8SMiguel Ojeda /// let x_ptr = x.as_ptr(); 1343753dece8SMiguel Ojeda /// 1344753dece8SMiguel Ojeda /// unsafe { 1345753dece8SMiguel Ojeda /// for i in 0..x.len() { 1346753dece8SMiguel Ojeda /// assert_eq!(*x_ptr.add(i), 1 << i); 1347753dece8SMiguel Ojeda /// } 1348753dece8SMiguel Ojeda /// } 1349753dece8SMiguel Ojeda /// ``` 1350753dece8SMiguel Ojeda /// 1351753dece8SMiguel Ojeda /// [`as_mut_ptr`]: Vec::as_mut_ptr 1352753dece8SMiguel Ojeda #[stable(feature = "vec_as_ptr", since = "1.37.0")] 1353753dece8SMiguel Ojeda #[inline] 1354753dece8SMiguel Ojeda pub fn as_ptr(&self) -> *const T { 1355753dece8SMiguel Ojeda // We shadow the slice method of the same name to avoid going through 1356753dece8SMiguel Ojeda // `deref`, which creates an intermediate reference. 1357*89eed1abSMiguel Ojeda self.buf.ptr() 1358753dece8SMiguel Ojeda } 1359753dece8SMiguel Ojeda 13603ed03f4dSMiguel Ojeda /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling 13613ed03f4dSMiguel Ojeda /// raw pointer valid for zero sized reads if the vector didn't allocate. 1362753dece8SMiguel Ojeda /// 1363753dece8SMiguel Ojeda /// The caller must ensure that the vector outlives the pointer this 1364753dece8SMiguel Ojeda /// function returns, or else it will end up pointing to garbage. 1365753dece8SMiguel Ojeda /// Modifying the vector may cause its buffer to be reallocated, 1366753dece8SMiguel Ojeda /// which would also make any pointers to it invalid. 1367753dece8SMiguel Ojeda /// 1368753dece8SMiguel Ojeda /// # Examples 1369753dece8SMiguel Ojeda /// 1370753dece8SMiguel Ojeda /// ``` 1371753dece8SMiguel Ojeda /// // Allocate vector big enough for 4 elements. 1372753dece8SMiguel Ojeda /// let size = 4; 1373753dece8SMiguel Ojeda /// let mut x: Vec<i32> = Vec::with_capacity(size); 1374753dece8SMiguel Ojeda /// let x_ptr = x.as_mut_ptr(); 1375753dece8SMiguel Ojeda /// 1376753dece8SMiguel Ojeda /// // Initialize elements via raw pointer writes, then set length. 1377753dece8SMiguel Ojeda /// unsafe { 1378753dece8SMiguel Ojeda /// for i in 0..size { 1379753dece8SMiguel Ojeda /// *x_ptr.add(i) = i as i32; 1380753dece8SMiguel Ojeda /// } 1381753dece8SMiguel Ojeda /// x.set_len(size); 1382753dece8SMiguel Ojeda /// } 1383753dece8SMiguel Ojeda /// assert_eq!(&*x, &[0, 1, 2, 3]); 1384753dece8SMiguel Ojeda /// ``` 1385753dece8SMiguel Ojeda #[stable(feature = "vec_as_ptr", since = "1.37.0")] 1386753dece8SMiguel Ojeda #[inline] 1387753dece8SMiguel Ojeda pub fn as_mut_ptr(&mut self) -> *mut T { 1388753dece8SMiguel Ojeda // We shadow the slice method of the same name to avoid going through 1389753dece8SMiguel Ojeda // `deref_mut`, which creates an intermediate reference. 1390*89eed1abSMiguel Ojeda self.buf.ptr() 1391753dece8SMiguel Ojeda } 1392753dece8SMiguel Ojeda 1393753dece8SMiguel Ojeda /// Returns a reference to the underlying allocator. 1394753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")] 1395753dece8SMiguel Ojeda #[inline] 1396753dece8SMiguel Ojeda pub fn allocator(&self) -> &A { 1397753dece8SMiguel Ojeda self.buf.allocator() 1398753dece8SMiguel Ojeda } 1399753dece8SMiguel Ojeda 1400753dece8SMiguel Ojeda /// Forces the length of the vector to `new_len`. 1401753dece8SMiguel Ojeda /// 1402753dece8SMiguel Ojeda /// This is a low-level operation that maintains none of the normal 1403753dece8SMiguel Ojeda /// invariants of the type. Normally changing the length of a vector 1404753dece8SMiguel Ojeda /// is done using one of the safe operations instead, such as 1405753dece8SMiguel Ojeda /// [`truncate`], [`resize`], [`extend`], or [`clear`]. 1406753dece8SMiguel Ojeda /// 1407753dece8SMiguel Ojeda /// [`truncate`]: Vec::truncate 1408753dece8SMiguel Ojeda /// [`resize`]: Vec::resize 1409753dece8SMiguel Ojeda /// [`extend`]: Extend::extend 1410753dece8SMiguel Ojeda /// [`clear`]: Vec::clear 1411753dece8SMiguel Ojeda /// 1412753dece8SMiguel Ojeda /// # Safety 1413753dece8SMiguel Ojeda /// 1414753dece8SMiguel Ojeda /// - `new_len` must be less than or equal to [`capacity()`]. 1415753dece8SMiguel Ojeda /// - The elements at `old_len..new_len` must be initialized. 1416753dece8SMiguel Ojeda /// 1417753dece8SMiguel Ojeda /// [`capacity()`]: Vec::capacity 1418753dece8SMiguel Ojeda /// 1419753dece8SMiguel Ojeda /// # Examples 1420753dece8SMiguel Ojeda /// 1421753dece8SMiguel Ojeda /// This method can be useful for situations in which the vector 1422753dece8SMiguel Ojeda /// is serving as a buffer for other code, particularly over FFI: 1423753dece8SMiguel Ojeda /// 1424753dece8SMiguel Ojeda /// ```no_run 1425753dece8SMiguel Ojeda /// # #![allow(dead_code)] 1426753dece8SMiguel Ojeda /// # // This is just a minimal skeleton for the doc example; 1427753dece8SMiguel Ojeda /// # // don't use this as a starting point for a real library. 1428753dece8SMiguel Ojeda /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void } 1429753dece8SMiguel Ojeda /// # const Z_OK: i32 = 0; 1430753dece8SMiguel Ojeda /// # extern "C" { 1431753dece8SMiguel Ojeda /// # fn deflateGetDictionary( 1432753dece8SMiguel Ojeda /// # strm: *mut std::ffi::c_void, 1433753dece8SMiguel Ojeda /// # dictionary: *mut u8, 1434753dece8SMiguel Ojeda /// # dictLength: *mut usize, 1435753dece8SMiguel Ojeda /// # ) -> i32; 1436753dece8SMiguel Ojeda /// # } 1437753dece8SMiguel Ojeda /// # impl StreamWrapper { 1438753dece8SMiguel Ojeda /// pub fn get_dictionary(&self) -> Option<Vec<u8>> { 1439753dece8SMiguel Ojeda /// // Per the FFI method's docs, "32768 bytes is always enough". 1440753dece8SMiguel Ojeda /// let mut dict = Vec::with_capacity(32_768); 1441753dece8SMiguel Ojeda /// let mut dict_length = 0; 1442753dece8SMiguel Ojeda /// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that: 1443753dece8SMiguel Ojeda /// // 1. `dict_length` elements were initialized. 1444753dece8SMiguel Ojeda /// // 2. `dict_length` <= the capacity (32_768) 1445753dece8SMiguel Ojeda /// // which makes `set_len` safe to call. 1446753dece8SMiguel Ojeda /// unsafe { 1447753dece8SMiguel Ojeda /// // Make the FFI call... 1448753dece8SMiguel Ojeda /// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length); 1449753dece8SMiguel Ojeda /// if r == Z_OK { 1450753dece8SMiguel Ojeda /// // ...and update the length to what was initialized. 1451753dece8SMiguel Ojeda /// dict.set_len(dict_length); 1452753dece8SMiguel Ojeda /// Some(dict) 1453753dece8SMiguel Ojeda /// } else { 1454753dece8SMiguel Ojeda /// None 1455753dece8SMiguel Ojeda /// } 1456753dece8SMiguel Ojeda /// } 1457753dece8SMiguel Ojeda /// } 1458753dece8SMiguel Ojeda /// # } 1459753dece8SMiguel Ojeda /// ``` 1460753dece8SMiguel Ojeda /// 1461753dece8SMiguel Ojeda /// While the following example is sound, there is a memory leak since 1462753dece8SMiguel Ojeda /// the inner vectors were not freed prior to the `set_len` call: 1463753dece8SMiguel Ojeda /// 1464753dece8SMiguel Ojeda /// ``` 1465753dece8SMiguel Ojeda /// let mut vec = vec![vec![1, 0, 0], 1466753dece8SMiguel Ojeda /// vec![0, 1, 0], 1467753dece8SMiguel Ojeda /// vec![0, 0, 1]]; 1468753dece8SMiguel Ojeda /// // SAFETY: 1469753dece8SMiguel Ojeda /// // 1. `old_len..0` is empty so no elements need to be initialized. 1470753dece8SMiguel Ojeda /// // 2. `0 <= capacity` always holds whatever `capacity` is. 1471753dece8SMiguel Ojeda /// unsafe { 1472753dece8SMiguel Ojeda /// vec.set_len(0); 1473753dece8SMiguel Ojeda /// } 1474753dece8SMiguel Ojeda /// ``` 1475753dece8SMiguel Ojeda /// 1476753dece8SMiguel Ojeda /// Normally, here, one would use [`clear`] instead to correctly drop 1477753dece8SMiguel Ojeda /// the contents and thus not leak memory. 1478753dece8SMiguel Ojeda #[inline] 1479753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1480753dece8SMiguel Ojeda pub unsafe fn set_len(&mut self, new_len: usize) { 1481753dece8SMiguel Ojeda debug_assert!(new_len <= self.capacity()); 1482753dece8SMiguel Ojeda 1483753dece8SMiguel Ojeda self.len = new_len; 1484753dece8SMiguel Ojeda } 1485753dece8SMiguel Ojeda 1486753dece8SMiguel Ojeda /// Removes an element from the vector and returns it. 1487753dece8SMiguel Ojeda /// 1488753dece8SMiguel Ojeda /// The removed element is replaced by the last element of the vector. 1489753dece8SMiguel Ojeda /// 1490753dece8SMiguel Ojeda /// This does not preserve ordering, but is *O*(1). 1491753dece8SMiguel Ojeda /// If you need to preserve the element order, use [`remove`] instead. 1492753dece8SMiguel Ojeda /// 1493753dece8SMiguel Ojeda /// [`remove`]: Vec::remove 1494753dece8SMiguel Ojeda /// 1495753dece8SMiguel Ojeda /// # Panics 1496753dece8SMiguel Ojeda /// 1497753dece8SMiguel Ojeda /// Panics if `index` is out of bounds. 1498753dece8SMiguel Ojeda /// 1499753dece8SMiguel Ojeda /// # Examples 1500753dece8SMiguel Ojeda /// 1501753dece8SMiguel Ojeda /// ``` 1502753dece8SMiguel Ojeda /// let mut v = vec!["foo", "bar", "baz", "qux"]; 1503753dece8SMiguel Ojeda /// 1504753dece8SMiguel Ojeda /// assert_eq!(v.swap_remove(1), "bar"); 1505753dece8SMiguel Ojeda /// assert_eq!(v, ["foo", "qux", "baz"]); 1506753dece8SMiguel Ojeda /// 1507753dece8SMiguel Ojeda /// assert_eq!(v.swap_remove(0), "foo"); 1508753dece8SMiguel Ojeda /// assert_eq!(v, ["baz", "qux"]); 1509753dece8SMiguel Ojeda /// ``` 1510753dece8SMiguel Ojeda #[inline] 1511753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1512753dece8SMiguel Ojeda pub fn swap_remove(&mut self, index: usize) -> T { 1513753dece8SMiguel Ojeda #[cold] 1514753dece8SMiguel Ojeda #[inline(never)] 1515753dece8SMiguel Ojeda fn assert_failed(index: usize, len: usize) -> ! { 1516753dece8SMiguel Ojeda panic!("swap_remove index (is {index}) should be < len (is {len})"); 1517753dece8SMiguel Ojeda } 1518753dece8SMiguel Ojeda 1519753dece8SMiguel Ojeda let len = self.len(); 1520753dece8SMiguel Ojeda if index >= len { 1521753dece8SMiguel Ojeda assert_failed(index, len); 1522753dece8SMiguel Ojeda } 1523753dece8SMiguel Ojeda unsafe { 1524753dece8SMiguel Ojeda // We replace self[index] with the last element. Note that if the 1525753dece8SMiguel Ojeda // bounds check above succeeds there must be a last element (which 1526753dece8SMiguel Ojeda // can be self[index] itself). 1527753dece8SMiguel Ojeda let value = ptr::read(self.as_ptr().add(index)); 1528753dece8SMiguel Ojeda let base_ptr = self.as_mut_ptr(); 1529753dece8SMiguel Ojeda ptr::copy(base_ptr.add(len - 1), base_ptr.add(index), 1); 1530753dece8SMiguel Ojeda self.set_len(len - 1); 1531753dece8SMiguel Ojeda value 1532753dece8SMiguel Ojeda } 1533753dece8SMiguel Ojeda } 1534753dece8SMiguel Ojeda 1535753dece8SMiguel Ojeda /// Inserts an element at position `index` within the vector, shifting all 1536753dece8SMiguel Ojeda /// elements after it to the right. 1537753dece8SMiguel Ojeda /// 1538753dece8SMiguel Ojeda /// # Panics 1539753dece8SMiguel Ojeda /// 1540753dece8SMiguel Ojeda /// Panics if `index > len`. 1541753dece8SMiguel Ojeda /// 1542753dece8SMiguel Ojeda /// # Examples 1543753dece8SMiguel Ojeda /// 1544753dece8SMiguel Ojeda /// ``` 1545753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3]; 1546753dece8SMiguel Ojeda /// vec.insert(1, 4); 1547753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 4, 2, 3]); 1548753dece8SMiguel Ojeda /// vec.insert(4, 5); 1549753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 4, 2, 3, 5]); 1550753dece8SMiguel Ojeda /// ``` 1551753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1552753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1553753dece8SMiguel Ojeda pub fn insert(&mut self, index: usize, element: T) { 1554753dece8SMiguel Ojeda #[cold] 1555753dece8SMiguel Ojeda #[inline(never)] 1556753dece8SMiguel Ojeda fn assert_failed(index: usize, len: usize) -> ! { 1557753dece8SMiguel Ojeda panic!("insertion index (is {index}) should be <= len (is {len})"); 1558753dece8SMiguel Ojeda } 1559753dece8SMiguel Ojeda 1560753dece8SMiguel Ojeda let len = self.len(); 1561753dece8SMiguel Ojeda 1562753dece8SMiguel Ojeda // space for the new element 1563753dece8SMiguel Ojeda if len == self.buf.capacity() { 1564753dece8SMiguel Ojeda self.reserve(1); 1565753dece8SMiguel Ojeda } 1566753dece8SMiguel Ojeda 1567753dece8SMiguel Ojeda unsafe { 1568753dece8SMiguel Ojeda // infallible 1569753dece8SMiguel Ojeda // The spot to put the new value 1570753dece8SMiguel Ojeda { 1571753dece8SMiguel Ojeda let p = self.as_mut_ptr().add(index); 15723ed03f4dSMiguel Ojeda if index < len { 1573753dece8SMiguel Ojeda // Shift everything over to make space. (Duplicating the 1574753dece8SMiguel Ojeda // `index`th element into two consecutive places.) 15753ed03f4dSMiguel Ojeda ptr::copy(p, p.add(1), len - index); 15763ed03f4dSMiguel Ojeda } else if index == len { 15773ed03f4dSMiguel Ojeda // No elements need shifting. 15783ed03f4dSMiguel Ojeda } else { 15793ed03f4dSMiguel Ojeda assert_failed(index, len); 15803ed03f4dSMiguel Ojeda } 1581753dece8SMiguel Ojeda // Write it in, overwriting the first copy of the `index`th 1582753dece8SMiguel Ojeda // element. 1583753dece8SMiguel Ojeda ptr::write(p, element); 1584753dece8SMiguel Ojeda } 1585753dece8SMiguel Ojeda self.set_len(len + 1); 1586753dece8SMiguel Ojeda } 1587753dece8SMiguel Ojeda } 1588753dece8SMiguel Ojeda 1589753dece8SMiguel Ojeda /// Removes and returns the element at position `index` within the vector, 1590753dece8SMiguel Ojeda /// shifting all elements after it to the left. 1591753dece8SMiguel Ojeda /// 1592753dece8SMiguel Ojeda /// Note: Because this shifts over the remaining elements, it has a 1593753dece8SMiguel Ojeda /// worst-case performance of *O*(*n*). If you don't need the order of elements 1594753dece8SMiguel Ojeda /// to be preserved, use [`swap_remove`] instead. If you'd like to remove 1595753dece8SMiguel Ojeda /// elements from the beginning of the `Vec`, consider using 1596753dece8SMiguel Ojeda /// [`VecDeque::pop_front`] instead. 1597753dece8SMiguel Ojeda /// 1598753dece8SMiguel Ojeda /// [`swap_remove`]: Vec::swap_remove 1599753dece8SMiguel Ojeda /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front 1600753dece8SMiguel Ojeda /// 1601753dece8SMiguel Ojeda /// # Panics 1602753dece8SMiguel Ojeda /// 1603753dece8SMiguel Ojeda /// Panics if `index` is out of bounds. 1604753dece8SMiguel Ojeda /// 1605753dece8SMiguel Ojeda /// # Examples 1606753dece8SMiguel Ojeda /// 1607753dece8SMiguel Ojeda /// ``` 1608753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3]; 1609753dece8SMiguel Ojeda /// assert_eq!(v.remove(1), 2); 1610753dece8SMiguel Ojeda /// assert_eq!(v, [1, 3]); 1611753dece8SMiguel Ojeda /// ``` 1612753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1613753dece8SMiguel Ojeda #[track_caller] 1614753dece8SMiguel Ojeda pub fn remove(&mut self, index: usize) -> T { 1615753dece8SMiguel Ojeda #[cold] 1616753dece8SMiguel Ojeda #[inline(never)] 1617753dece8SMiguel Ojeda #[track_caller] 1618753dece8SMiguel Ojeda fn assert_failed(index: usize, len: usize) -> ! { 1619753dece8SMiguel Ojeda panic!("removal index (is {index}) should be < len (is {len})"); 1620753dece8SMiguel Ojeda } 1621753dece8SMiguel Ojeda 1622753dece8SMiguel Ojeda let len = self.len(); 1623753dece8SMiguel Ojeda if index >= len { 1624753dece8SMiguel Ojeda assert_failed(index, len); 1625753dece8SMiguel Ojeda } 1626753dece8SMiguel Ojeda unsafe { 1627753dece8SMiguel Ojeda // infallible 1628753dece8SMiguel Ojeda let ret; 1629753dece8SMiguel Ojeda { 1630753dece8SMiguel Ojeda // the place we are taking from. 1631753dece8SMiguel Ojeda let ptr = self.as_mut_ptr().add(index); 1632753dece8SMiguel Ojeda // copy it out, unsafely having a copy of the value on 1633753dece8SMiguel Ojeda // the stack and in the vector at the same time. 1634753dece8SMiguel Ojeda ret = ptr::read(ptr); 1635753dece8SMiguel Ojeda 1636753dece8SMiguel Ojeda // Shift everything down to fill in that spot. 16373ed03f4dSMiguel Ojeda ptr::copy(ptr.add(1), ptr, len - index - 1); 1638753dece8SMiguel Ojeda } 1639753dece8SMiguel Ojeda self.set_len(len - 1); 1640753dece8SMiguel Ojeda ret 1641753dece8SMiguel Ojeda } 1642753dece8SMiguel Ojeda } 1643753dece8SMiguel Ojeda 1644753dece8SMiguel Ojeda /// Retains only the elements specified by the predicate. 1645753dece8SMiguel Ojeda /// 1646753dece8SMiguel Ojeda /// In other words, remove all elements `e` for which `f(&e)` returns `false`. 1647753dece8SMiguel Ojeda /// This method operates in place, visiting each element exactly once in the 1648753dece8SMiguel Ojeda /// original order, and preserves the order of the retained elements. 1649753dece8SMiguel Ojeda /// 1650753dece8SMiguel Ojeda /// # Examples 1651753dece8SMiguel Ojeda /// 1652753dece8SMiguel Ojeda /// ``` 1653753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4]; 1654753dece8SMiguel Ojeda /// vec.retain(|&x| x % 2 == 0); 1655753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 4]); 1656753dece8SMiguel Ojeda /// ``` 1657753dece8SMiguel Ojeda /// 1658753dece8SMiguel Ojeda /// Because the elements are visited exactly once in the original order, 1659753dece8SMiguel Ojeda /// external state may be used to decide which elements to keep. 1660753dece8SMiguel Ojeda /// 1661753dece8SMiguel Ojeda /// ``` 1662753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4, 5]; 1663753dece8SMiguel Ojeda /// let keep = [false, true, true, false, true]; 1664753dece8SMiguel Ojeda /// let mut iter = keep.iter(); 1665753dece8SMiguel Ojeda /// vec.retain(|_| *iter.next().unwrap()); 1666753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 3, 5]); 1667753dece8SMiguel Ojeda /// ``` 1668753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1669753dece8SMiguel Ojeda pub fn retain<F>(&mut self, mut f: F) 1670753dece8SMiguel Ojeda where 1671753dece8SMiguel Ojeda F: FnMut(&T) -> bool, 1672753dece8SMiguel Ojeda { 1673753dece8SMiguel Ojeda self.retain_mut(|elem| f(elem)); 1674753dece8SMiguel Ojeda } 1675753dece8SMiguel Ojeda 1676753dece8SMiguel Ojeda /// Retains only the elements specified by the predicate, passing a mutable reference to it. 1677753dece8SMiguel Ojeda /// 1678753dece8SMiguel Ojeda /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`. 1679753dece8SMiguel Ojeda /// This method operates in place, visiting each element exactly once in the 1680753dece8SMiguel Ojeda /// original order, and preserves the order of the retained elements. 1681753dece8SMiguel Ojeda /// 1682753dece8SMiguel Ojeda /// # Examples 1683753dece8SMiguel Ojeda /// 1684753dece8SMiguel Ojeda /// ``` 1685753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4]; 16863ed03f4dSMiguel Ojeda /// vec.retain_mut(|x| if *x <= 3 { 1687753dece8SMiguel Ojeda /// *x += 1; 1688753dece8SMiguel Ojeda /// true 16893ed03f4dSMiguel Ojeda /// } else { 16903ed03f4dSMiguel Ojeda /// false 1691753dece8SMiguel Ojeda /// }); 1692753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 3, 4]); 1693753dece8SMiguel Ojeda /// ``` 1694753dece8SMiguel Ojeda #[stable(feature = "vec_retain_mut", since = "1.61.0")] 1695753dece8SMiguel Ojeda pub fn retain_mut<F>(&mut self, mut f: F) 1696753dece8SMiguel Ojeda where 1697753dece8SMiguel Ojeda F: FnMut(&mut T) -> bool, 1698753dece8SMiguel Ojeda { 1699753dece8SMiguel Ojeda let original_len = self.len(); 1700753dece8SMiguel Ojeda // Avoid double drop if the drop guard is not executed, 1701753dece8SMiguel Ojeda // since we may make some holes during the process. 1702753dece8SMiguel Ojeda unsafe { self.set_len(0) }; 1703753dece8SMiguel Ojeda 1704753dece8SMiguel Ojeda // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked] 1705753dece8SMiguel Ojeda // |<- processed len ->| ^- next to check 1706753dece8SMiguel Ojeda // |<- deleted cnt ->| 1707753dece8SMiguel Ojeda // |<- original_len ->| 1708753dece8SMiguel Ojeda // Kept: Elements which predicate returns true on. 1709753dece8SMiguel Ojeda // Hole: Moved or dropped element slot. 1710753dece8SMiguel Ojeda // Unchecked: Unchecked valid elements. 1711753dece8SMiguel Ojeda // 1712753dece8SMiguel Ojeda // This drop guard will be invoked when predicate or `drop` of element panicked. 1713753dece8SMiguel Ojeda // It shifts unchecked elements to cover holes and `set_len` to the correct length. 1714753dece8SMiguel Ojeda // In cases when predicate and `drop` never panick, it will be optimized out. 1715753dece8SMiguel Ojeda struct BackshiftOnDrop<'a, T, A: Allocator> { 1716753dece8SMiguel Ojeda v: &'a mut Vec<T, A>, 1717753dece8SMiguel Ojeda processed_len: usize, 1718753dece8SMiguel Ojeda deleted_cnt: usize, 1719753dece8SMiguel Ojeda original_len: usize, 1720753dece8SMiguel Ojeda } 1721753dece8SMiguel Ojeda 1722753dece8SMiguel Ojeda impl<T, A: Allocator> Drop for BackshiftOnDrop<'_, T, A> { 1723753dece8SMiguel Ojeda fn drop(&mut self) { 1724753dece8SMiguel Ojeda if self.deleted_cnt > 0 { 1725753dece8SMiguel Ojeda // SAFETY: Trailing unchecked items must be valid since we never touch them. 1726753dece8SMiguel Ojeda unsafe { 1727753dece8SMiguel Ojeda ptr::copy( 1728753dece8SMiguel Ojeda self.v.as_ptr().add(self.processed_len), 1729753dece8SMiguel Ojeda self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt), 1730753dece8SMiguel Ojeda self.original_len - self.processed_len, 1731753dece8SMiguel Ojeda ); 1732753dece8SMiguel Ojeda } 1733753dece8SMiguel Ojeda } 1734753dece8SMiguel Ojeda // SAFETY: After filling holes, all items are in contiguous memory. 1735753dece8SMiguel Ojeda unsafe { 1736753dece8SMiguel Ojeda self.v.set_len(self.original_len - self.deleted_cnt); 1737753dece8SMiguel Ojeda } 1738753dece8SMiguel Ojeda } 1739753dece8SMiguel Ojeda } 1740753dece8SMiguel Ojeda 1741753dece8SMiguel Ojeda let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len }; 1742753dece8SMiguel Ojeda 1743753dece8SMiguel Ojeda fn process_loop<F, T, A: Allocator, const DELETED: bool>( 1744753dece8SMiguel Ojeda original_len: usize, 1745753dece8SMiguel Ojeda f: &mut F, 1746753dece8SMiguel Ojeda g: &mut BackshiftOnDrop<'_, T, A>, 1747753dece8SMiguel Ojeda ) where 1748753dece8SMiguel Ojeda F: FnMut(&mut T) -> bool, 1749753dece8SMiguel Ojeda { 1750753dece8SMiguel Ojeda while g.processed_len != original_len { 1751753dece8SMiguel Ojeda // SAFETY: Unchecked element must be valid. 1752753dece8SMiguel Ojeda let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) }; 1753753dece8SMiguel Ojeda if !f(cur) { 1754753dece8SMiguel Ojeda // Advance early to avoid double drop if `drop_in_place` panicked. 1755753dece8SMiguel Ojeda g.processed_len += 1; 1756753dece8SMiguel Ojeda g.deleted_cnt += 1; 1757753dece8SMiguel Ojeda // SAFETY: We never touch this element again after dropped. 1758753dece8SMiguel Ojeda unsafe { ptr::drop_in_place(cur) }; 1759753dece8SMiguel Ojeda // We already advanced the counter. 1760753dece8SMiguel Ojeda if DELETED { 1761753dece8SMiguel Ojeda continue; 1762753dece8SMiguel Ojeda } else { 1763753dece8SMiguel Ojeda break; 1764753dece8SMiguel Ojeda } 1765753dece8SMiguel Ojeda } 1766753dece8SMiguel Ojeda if DELETED { 1767753dece8SMiguel Ojeda // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element. 1768753dece8SMiguel Ojeda // We use copy for move, and never touch this element again. 1769753dece8SMiguel Ojeda unsafe { 1770753dece8SMiguel Ojeda let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt); 1771753dece8SMiguel Ojeda ptr::copy_nonoverlapping(cur, hole_slot, 1); 1772753dece8SMiguel Ojeda } 1773753dece8SMiguel Ojeda } 1774753dece8SMiguel Ojeda g.processed_len += 1; 1775753dece8SMiguel Ojeda } 1776753dece8SMiguel Ojeda } 1777753dece8SMiguel Ojeda 1778753dece8SMiguel Ojeda // Stage 1: Nothing was deleted. 1779753dece8SMiguel Ojeda process_loop::<F, T, A, false>(original_len, &mut f, &mut g); 1780753dece8SMiguel Ojeda 1781753dece8SMiguel Ojeda // Stage 2: Some elements were deleted. 1782753dece8SMiguel Ojeda process_loop::<F, T, A, true>(original_len, &mut f, &mut g); 1783753dece8SMiguel Ojeda 1784753dece8SMiguel Ojeda // All item are processed. This can be optimized to `set_len` by LLVM. 1785753dece8SMiguel Ojeda drop(g); 1786753dece8SMiguel Ojeda } 1787753dece8SMiguel Ojeda 1788753dece8SMiguel Ojeda /// Removes all but the first of consecutive elements in the vector that resolve to the same 1789753dece8SMiguel Ojeda /// key. 1790753dece8SMiguel Ojeda /// 1791753dece8SMiguel Ojeda /// If the vector is sorted, this removes all duplicates. 1792753dece8SMiguel Ojeda /// 1793753dece8SMiguel Ojeda /// # Examples 1794753dece8SMiguel Ojeda /// 1795753dece8SMiguel Ojeda /// ``` 1796753dece8SMiguel Ojeda /// let mut vec = vec![10, 20, 21, 30, 20]; 1797753dece8SMiguel Ojeda /// 1798753dece8SMiguel Ojeda /// vec.dedup_by_key(|i| *i / 10); 1799753dece8SMiguel Ojeda /// 1800753dece8SMiguel Ojeda /// assert_eq!(vec, [10, 20, 30, 20]); 1801753dece8SMiguel Ojeda /// ``` 1802753dece8SMiguel Ojeda #[stable(feature = "dedup_by", since = "1.16.0")] 1803753dece8SMiguel Ojeda #[inline] 1804753dece8SMiguel Ojeda pub fn dedup_by_key<F, K>(&mut self, mut key: F) 1805753dece8SMiguel Ojeda where 1806753dece8SMiguel Ojeda F: FnMut(&mut T) -> K, 1807753dece8SMiguel Ojeda K: PartialEq, 1808753dece8SMiguel Ojeda { 1809753dece8SMiguel Ojeda self.dedup_by(|a, b| key(a) == key(b)) 1810753dece8SMiguel Ojeda } 1811753dece8SMiguel Ojeda 1812753dece8SMiguel Ojeda /// Removes all but the first of consecutive elements in the vector satisfying a given equality 1813753dece8SMiguel Ojeda /// relation. 1814753dece8SMiguel Ojeda /// 1815753dece8SMiguel Ojeda /// The `same_bucket` function is passed references to two elements from the vector and 1816753dece8SMiguel Ojeda /// must determine if the elements compare equal. The elements are passed in opposite order 1817753dece8SMiguel Ojeda /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed. 1818753dece8SMiguel Ojeda /// 1819753dece8SMiguel Ojeda /// If the vector is sorted, this removes all duplicates. 1820753dece8SMiguel Ojeda /// 1821753dece8SMiguel Ojeda /// # Examples 1822753dece8SMiguel Ojeda /// 1823753dece8SMiguel Ojeda /// ``` 1824753dece8SMiguel Ojeda /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"]; 1825753dece8SMiguel Ojeda /// 1826753dece8SMiguel Ojeda /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b)); 1827753dece8SMiguel Ojeda /// 1828753dece8SMiguel Ojeda /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]); 1829753dece8SMiguel Ojeda /// ``` 1830753dece8SMiguel Ojeda #[stable(feature = "dedup_by", since = "1.16.0")] 1831753dece8SMiguel Ojeda pub fn dedup_by<F>(&mut self, mut same_bucket: F) 1832753dece8SMiguel Ojeda where 1833753dece8SMiguel Ojeda F: FnMut(&mut T, &mut T) -> bool, 1834753dece8SMiguel Ojeda { 1835753dece8SMiguel Ojeda let len = self.len(); 1836753dece8SMiguel Ojeda if len <= 1 { 1837753dece8SMiguel Ojeda return; 1838753dece8SMiguel Ojeda } 1839753dece8SMiguel Ojeda 1840753dece8SMiguel Ojeda /* INVARIANT: vec.len() > read >= write > write-1 >= 0 */ 1841753dece8SMiguel Ojeda struct FillGapOnDrop<'a, T, A: core::alloc::Allocator> { 1842753dece8SMiguel Ojeda /* Offset of the element we want to check if it is duplicate */ 1843753dece8SMiguel Ojeda read: usize, 1844753dece8SMiguel Ojeda 1845753dece8SMiguel Ojeda /* Offset of the place where we want to place the non-duplicate 1846753dece8SMiguel Ojeda * when we find it. */ 1847753dece8SMiguel Ojeda write: usize, 1848753dece8SMiguel Ojeda 1849753dece8SMiguel Ojeda /* The Vec that would need correction if `same_bucket` panicked */ 1850753dece8SMiguel Ojeda vec: &'a mut Vec<T, A>, 1851753dece8SMiguel Ojeda } 1852753dece8SMiguel Ojeda 1853753dece8SMiguel Ojeda impl<'a, T, A: core::alloc::Allocator> Drop for FillGapOnDrop<'a, T, A> { 1854753dece8SMiguel Ojeda fn drop(&mut self) { 1855753dece8SMiguel Ojeda /* This code gets executed when `same_bucket` panics */ 1856753dece8SMiguel Ojeda 1857753dece8SMiguel Ojeda /* SAFETY: invariant guarantees that `read - write` 1858753dece8SMiguel Ojeda * and `len - read` never overflow and that the copy is always 1859753dece8SMiguel Ojeda * in-bounds. */ 1860753dece8SMiguel Ojeda unsafe { 1861753dece8SMiguel Ojeda let ptr = self.vec.as_mut_ptr(); 1862753dece8SMiguel Ojeda let len = self.vec.len(); 1863753dece8SMiguel Ojeda 1864753dece8SMiguel Ojeda /* How many items were left when `same_bucket` panicked. 1865753dece8SMiguel Ojeda * Basically vec[read..].len() */ 1866753dece8SMiguel Ojeda let items_left = len.wrapping_sub(self.read); 1867753dece8SMiguel Ojeda 1868753dece8SMiguel Ojeda /* Pointer to first item in vec[write..write+items_left] slice */ 1869753dece8SMiguel Ojeda let dropped_ptr = ptr.add(self.write); 1870753dece8SMiguel Ojeda /* Pointer to first item in vec[read..] slice */ 1871753dece8SMiguel Ojeda let valid_ptr = ptr.add(self.read); 1872753dece8SMiguel Ojeda 1873753dece8SMiguel Ojeda /* Copy `vec[read..]` to `vec[write..write+items_left]`. 1874753dece8SMiguel Ojeda * The slices can overlap, so `copy_nonoverlapping` cannot be used */ 1875753dece8SMiguel Ojeda ptr::copy(valid_ptr, dropped_ptr, items_left); 1876753dece8SMiguel Ojeda 1877753dece8SMiguel Ojeda /* How many items have been already dropped 1878753dece8SMiguel Ojeda * Basically vec[read..write].len() */ 1879753dece8SMiguel Ojeda let dropped = self.read.wrapping_sub(self.write); 1880753dece8SMiguel Ojeda 1881753dece8SMiguel Ojeda self.vec.set_len(len - dropped); 1882753dece8SMiguel Ojeda } 1883753dece8SMiguel Ojeda } 1884753dece8SMiguel Ojeda } 1885753dece8SMiguel Ojeda 1886753dece8SMiguel Ojeda let mut gap = FillGapOnDrop { read: 1, write: 1, vec: self }; 1887753dece8SMiguel Ojeda let ptr = gap.vec.as_mut_ptr(); 1888753dece8SMiguel Ojeda 1889753dece8SMiguel Ojeda /* Drop items while going through Vec, it should be more efficient than 1890753dece8SMiguel Ojeda * doing slice partition_dedup + truncate */ 1891753dece8SMiguel Ojeda 1892753dece8SMiguel Ojeda /* SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr 1893753dece8SMiguel Ojeda * are always in-bounds and read_ptr never aliases prev_ptr */ 1894753dece8SMiguel Ojeda unsafe { 1895753dece8SMiguel Ojeda while gap.read < len { 1896753dece8SMiguel Ojeda let read_ptr = ptr.add(gap.read); 1897753dece8SMiguel Ojeda let prev_ptr = ptr.add(gap.write.wrapping_sub(1)); 1898753dece8SMiguel Ojeda 1899753dece8SMiguel Ojeda if same_bucket(&mut *read_ptr, &mut *prev_ptr) { 1900753dece8SMiguel Ojeda // Increase `gap.read` now since the drop may panic. 1901753dece8SMiguel Ojeda gap.read += 1; 1902753dece8SMiguel Ojeda /* We have found duplicate, drop it in-place */ 1903753dece8SMiguel Ojeda ptr::drop_in_place(read_ptr); 1904753dece8SMiguel Ojeda } else { 1905753dece8SMiguel Ojeda let write_ptr = ptr.add(gap.write); 1906753dece8SMiguel Ojeda 1907753dece8SMiguel Ojeda /* Because `read_ptr` can be equal to `write_ptr`, we either 1908753dece8SMiguel Ojeda * have to use `copy` or conditional `copy_nonoverlapping`. 1909753dece8SMiguel Ojeda * Looks like the first option is faster. */ 1910753dece8SMiguel Ojeda ptr::copy(read_ptr, write_ptr, 1); 1911753dece8SMiguel Ojeda 1912753dece8SMiguel Ojeda /* We have filled that place, so go further */ 1913753dece8SMiguel Ojeda gap.write += 1; 1914753dece8SMiguel Ojeda gap.read += 1; 1915753dece8SMiguel Ojeda } 1916753dece8SMiguel Ojeda } 1917753dece8SMiguel Ojeda 1918753dece8SMiguel Ojeda /* Technically we could let `gap` clean up with its Drop, but 1919753dece8SMiguel Ojeda * when `same_bucket` is guaranteed to not panic, this bloats a little 1920753dece8SMiguel Ojeda * the codegen, so we just do it manually */ 1921753dece8SMiguel Ojeda gap.vec.set_len(gap.write); 1922753dece8SMiguel Ojeda mem::forget(gap); 1923753dece8SMiguel Ojeda } 1924753dece8SMiguel Ojeda } 1925753dece8SMiguel Ojeda 1926753dece8SMiguel Ojeda /// Appends an element to the back of a collection. 1927753dece8SMiguel Ojeda /// 1928753dece8SMiguel Ojeda /// # Panics 1929753dece8SMiguel Ojeda /// 1930753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes. 1931753dece8SMiguel Ojeda /// 1932753dece8SMiguel Ojeda /// # Examples 1933753dece8SMiguel Ojeda /// 1934753dece8SMiguel Ojeda /// ``` 1935753dece8SMiguel Ojeda /// let mut vec = vec![1, 2]; 1936753dece8SMiguel Ojeda /// vec.push(3); 1937753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3]); 1938753dece8SMiguel Ojeda /// ``` 1939753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 1940753dece8SMiguel Ojeda #[inline] 1941753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 1942753dece8SMiguel Ojeda pub fn push(&mut self, value: T) { 1943753dece8SMiguel Ojeda // This will panic or abort if we would allocate > isize::MAX bytes 1944753dece8SMiguel Ojeda // or if the length increment would overflow for zero-sized types. 1945753dece8SMiguel Ojeda if self.len == self.buf.capacity() { 1946753dece8SMiguel Ojeda self.buf.reserve_for_push(self.len); 1947753dece8SMiguel Ojeda } 1948753dece8SMiguel Ojeda unsafe { 1949753dece8SMiguel Ojeda let end = self.as_mut_ptr().add(self.len); 1950753dece8SMiguel Ojeda ptr::write(end, value); 1951753dece8SMiguel Ojeda self.len += 1; 1952753dece8SMiguel Ojeda } 1953753dece8SMiguel Ojeda } 1954753dece8SMiguel Ojeda 1955057b8d25SMiguel Ojeda /// Tries to append an element to the back of a collection. 1956057b8d25SMiguel Ojeda /// 1957057b8d25SMiguel Ojeda /// # Examples 1958057b8d25SMiguel Ojeda /// 1959057b8d25SMiguel Ojeda /// ``` 1960057b8d25SMiguel Ojeda /// let mut vec = vec![1, 2]; 1961057b8d25SMiguel Ojeda /// vec.try_push(3).unwrap(); 1962057b8d25SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3]); 1963057b8d25SMiguel Ojeda /// ``` 1964057b8d25SMiguel Ojeda #[inline] 1965057b8d25SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")] 1966057b8d25SMiguel Ojeda pub fn try_push(&mut self, value: T) -> Result<(), TryReserveError> { 1967057b8d25SMiguel Ojeda if self.len == self.buf.capacity() { 1968057b8d25SMiguel Ojeda self.buf.try_reserve_for_push(self.len)?; 1969057b8d25SMiguel Ojeda } 1970057b8d25SMiguel Ojeda unsafe { 1971057b8d25SMiguel Ojeda let end = self.as_mut_ptr().add(self.len); 1972057b8d25SMiguel Ojeda ptr::write(end, value); 1973057b8d25SMiguel Ojeda self.len += 1; 1974057b8d25SMiguel Ojeda } 1975057b8d25SMiguel Ojeda Ok(()) 1976057b8d25SMiguel Ojeda } 1977057b8d25SMiguel Ojeda 19783ed03f4dSMiguel Ojeda /// Appends an element if there is sufficient spare capacity, otherwise an error is returned 19793ed03f4dSMiguel Ojeda /// with the element. 19803ed03f4dSMiguel Ojeda /// 19813ed03f4dSMiguel Ojeda /// Unlike [`push`] this method will not reallocate when there's insufficient capacity. 19823ed03f4dSMiguel Ojeda /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity. 19833ed03f4dSMiguel Ojeda /// 19843ed03f4dSMiguel Ojeda /// [`push`]: Vec::push 19853ed03f4dSMiguel Ojeda /// [`reserve`]: Vec::reserve 19863ed03f4dSMiguel Ojeda /// [`try_reserve`]: Vec::try_reserve 19873ed03f4dSMiguel Ojeda /// 19883ed03f4dSMiguel Ojeda /// # Examples 19893ed03f4dSMiguel Ojeda /// 19903ed03f4dSMiguel Ojeda /// A manual, panic-free alternative to [`FromIterator`]: 19913ed03f4dSMiguel Ojeda /// 19923ed03f4dSMiguel Ojeda /// ``` 19933ed03f4dSMiguel Ojeda /// #![feature(vec_push_within_capacity)] 19943ed03f4dSMiguel Ojeda /// 19953ed03f4dSMiguel Ojeda /// use std::collections::TryReserveError; 19963ed03f4dSMiguel Ojeda /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> { 19973ed03f4dSMiguel Ojeda /// let mut vec = Vec::new(); 19983ed03f4dSMiguel Ojeda /// for value in iter { 19993ed03f4dSMiguel Ojeda /// if let Err(value) = vec.push_within_capacity(value) { 20003ed03f4dSMiguel Ojeda /// vec.try_reserve(1)?; 20013ed03f4dSMiguel Ojeda /// // this cannot fail, the previous line either returned or added at least 1 free slot 20023ed03f4dSMiguel Ojeda /// let _ = vec.push_within_capacity(value); 20033ed03f4dSMiguel Ojeda /// } 20043ed03f4dSMiguel Ojeda /// } 20053ed03f4dSMiguel Ojeda /// Ok(vec) 20063ed03f4dSMiguel Ojeda /// } 20073ed03f4dSMiguel Ojeda /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100))); 20083ed03f4dSMiguel Ojeda /// ``` 20093ed03f4dSMiguel Ojeda #[inline] 20103ed03f4dSMiguel Ojeda #[unstable(feature = "vec_push_within_capacity", issue = "100486")] 20113ed03f4dSMiguel Ojeda pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> { 20123ed03f4dSMiguel Ojeda if self.len == self.buf.capacity() { 20133ed03f4dSMiguel Ojeda return Err(value); 20143ed03f4dSMiguel Ojeda } 20153ed03f4dSMiguel Ojeda unsafe { 20163ed03f4dSMiguel Ojeda let end = self.as_mut_ptr().add(self.len); 20173ed03f4dSMiguel Ojeda ptr::write(end, value); 20183ed03f4dSMiguel Ojeda self.len += 1; 20193ed03f4dSMiguel Ojeda } 20203ed03f4dSMiguel Ojeda Ok(()) 20213ed03f4dSMiguel Ojeda } 20223ed03f4dSMiguel Ojeda 2023753dece8SMiguel Ojeda /// Removes the last element from a vector and returns it, or [`None`] if it 2024753dece8SMiguel Ojeda /// is empty. 2025753dece8SMiguel Ojeda /// 2026753dece8SMiguel Ojeda /// If you'd like to pop the first element, consider using 2027753dece8SMiguel Ojeda /// [`VecDeque::pop_front`] instead. 2028753dece8SMiguel Ojeda /// 2029753dece8SMiguel Ojeda /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front 2030753dece8SMiguel Ojeda /// 2031753dece8SMiguel Ojeda /// # Examples 2032753dece8SMiguel Ojeda /// 2033753dece8SMiguel Ojeda /// ``` 2034753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3]; 2035753dece8SMiguel Ojeda /// assert_eq!(vec.pop(), Some(3)); 2036753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2]); 2037753dece8SMiguel Ojeda /// ``` 2038753dece8SMiguel Ojeda #[inline] 2039753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2040753dece8SMiguel Ojeda pub fn pop(&mut self) -> Option<T> { 2041753dece8SMiguel Ojeda if self.len == 0 { 2042753dece8SMiguel Ojeda None 2043753dece8SMiguel Ojeda } else { 2044753dece8SMiguel Ojeda unsafe { 2045753dece8SMiguel Ojeda self.len -= 1; 2046753dece8SMiguel Ojeda Some(ptr::read(self.as_ptr().add(self.len()))) 2047753dece8SMiguel Ojeda } 2048753dece8SMiguel Ojeda } 2049753dece8SMiguel Ojeda } 2050753dece8SMiguel Ojeda 2051753dece8SMiguel Ojeda /// Moves all the elements of `other` into `self`, leaving `other` empty. 2052753dece8SMiguel Ojeda /// 2053753dece8SMiguel Ojeda /// # Panics 2054753dece8SMiguel Ojeda /// 20553ed03f4dSMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes. 2056753dece8SMiguel Ojeda /// 2057753dece8SMiguel Ojeda /// # Examples 2058753dece8SMiguel Ojeda /// 2059753dece8SMiguel Ojeda /// ``` 2060753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3]; 2061753dece8SMiguel Ojeda /// let mut vec2 = vec![4, 5, 6]; 2062753dece8SMiguel Ojeda /// vec.append(&mut vec2); 2063753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]); 2064753dece8SMiguel Ojeda /// assert_eq!(vec2, []); 2065753dece8SMiguel Ojeda /// ``` 2066753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2067753dece8SMiguel Ojeda #[inline] 2068753dece8SMiguel Ojeda #[stable(feature = "append", since = "1.4.0")] 2069753dece8SMiguel Ojeda pub fn append(&mut self, other: &mut Self) { 2070753dece8SMiguel Ojeda unsafe { 2071753dece8SMiguel Ojeda self.append_elements(other.as_slice() as _); 2072753dece8SMiguel Ojeda other.set_len(0); 2073753dece8SMiguel Ojeda } 2074753dece8SMiguel Ojeda } 2075753dece8SMiguel Ojeda 2076753dece8SMiguel Ojeda /// Appends elements to `self` from other buffer. 2077753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2078753dece8SMiguel Ojeda #[inline] 2079753dece8SMiguel Ojeda unsafe fn append_elements(&mut self, other: *const [T]) { 2080753dece8SMiguel Ojeda let count = unsafe { (*other).len() }; 2081753dece8SMiguel Ojeda self.reserve(count); 2082753dece8SMiguel Ojeda let len = self.len(); 2083753dece8SMiguel Ojeda unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) }; 2084753dece8SMiguel Ojeda self.len += count; 2085753dece8SMiguel Ojeda } 2086753dece8SMiguel Ojeda 2087318c3cc8SMiguel Ojeda /// Tries to append elements to `self` from other buffer. 2088318c3cc8SMiguel Ojeda #[inline] 2089318c3cc8SMiguel Ojeda unsafe fn try_append_elements(&mut self, other: *const [T]) -> Result<(), TryReserveError> { 2090318c3cc8SMiguel Ojeda let count = unsafe { (*other).len() }; 2091318c3cc8SMiguel Ojeda self.try_reserve(count)?; 2092318c3cc8SMiguel Ojeda let len = self.len(); 2093318c3cc8SMiguel Ojeda unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) }; 2094318c3cc8SMiguel Ojeda self.len += count; 2095318c3cc8SMiguel Ojeda Ok(()) 2096318c3cc8SMiguel Ojeda } 2097318c3cc8SMiguel Ojeda 2098753dece8SMiguel Ojeda /// Removes the specified range from the vector in bulk, returning all 2099753dece8SMiguel Ojeda /// removed elements as an iterator. If the iterator is dropped before 2100753dece8SMiguel Ojeda /// being fully consumed, it drops the remaining removed elements. 2101753dece8SMiguel Ojeda /// 2102753dece8SMiguel Ojeda /// The returned iterator keeps a mutable borrow on the vector to optimize 2103753dece8SMiguel Ojeda /// its implementation. 2104753dece8SMiguel Ojeda /// 2105753dece8SMiguel Ojeda /// # Panics 2106753dece8SMiguel Ojeda /// 2107753dece8SMiguel Ojeda /// Panics if the starting point is greater than the end point or if 2108753dece8SMiguel Ojeda /// the end point is greater than the length of the vector. 2109753dece8SMiguel Ojeda /// 2110753dece8SMiguel Ojeda /// # Leaking 2111753dece8SMiguel Ojeda /// 2112753dece8SMiguel Ojeda /// If the returned iterator goes out of scope without being dropped (due to 2113753dece8SMiguel Ojeda /// [`mem::forget`], for example), the vector may have lost and leaked 2114753dece8SMiguel Ojeda /// elements arbitrarily, including elements outside the range. 2115753dece8SMiguel Ojeda /// 2116753dece8SMiguel Ojeda /// # Examples 2117753dece8SMiguel Ojeda /// 2118753dece8SMiguel Ojeda /// ``` 2119753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3]; 2120753dece8SMiguel Ojeda /// let u: Vec<_> = v.drain(1..).collect(); 2121753dece8SMiguel Ojeda /// assert_eq!(v, &[1]); 2122753dece8SMiguel Ojeda /// assert_eq!(u, &[2, 3]); 2123753dece8SMiguel Ojeda /// 2124753dece8SMiguel Ojeda /// // A full range clears the vector, like `clear()` does 2125753dece8SMiguel Ojeda /// v.drain(..); 2126753dece8SMiguel Ojeda /// assert_eq!(v, &[]); 2127753dece8SMiguel Ojeda /// ``` 2128753dece8SMiguel Ojeda #[stable(feature = "drain", since = "1.6.0")] 2129753dece8SMiguel Ojeda pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A> 2130753dece8SMiguel Ojeda where 2131753dece8SMiguel Ojeda R: RangeBounds<usize>, 2132753dece8SMiguel Ojeda { 2133753dece8SMiguel Ojeda // Memory safety 2134753dece8SMiguel Ojeda // 2135753dece8SMiguel Ojeda // When the Drain is first created, it shortens the length of 2136753dece8SMiguel Ojeda // the source vector to make sure no uninitialized or moved-from elements 2137753dece8SMiguel Ojeda // are accessible at all if the Drain's destructor never gets to run. 2138753dece8SMiguel Ojeda // 2139753dece8SMiguel Ojeda // Drain will ptr::read out the values to remove. 2140753dece8SMiguel Ojeda // When finished, remaining tail of the vec is copied back to cover 2141753dece8SMiguel Ojeda // the hole, and the vector length is restored to the new length. 2142753dece8SMiguel Ojeda // 2143753dece8SMiguel Ojeda let len = self.len(); 2144753dece8SMiguel Ojeda let Range { start, end } = slice::range(range, ..len); 2145753dece8SMiguel Ojeda 2146753dece8SMiguel Ojeda unsafe { 2147753dece8SMiguel Ojeda // set self.vec length's to start, to be safe in case Drain is leaked 2148753dece8SMiguel Ojeda self.set_len(start); 21493ed03f4dSMiguel Ojeda let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start); 2150753dece8SMiguel Ojeda Drain { 2151753dece8SMiguel Ojeda tail_start: end, 2152753dece8SMiguel Ojeda tail_len: len - end, 2153753dece8SMiguel Ojeda iter: range_slice.iter(), 2154753dece8SMiguel Ojeda vec: NonNull::from(self), 2155753dece8SMiguel Ojeda } 2156753dece8SMiguel Ojeda } 2157753dece8SMiguel Ojeda } 2158753dece8SMiguel Ojeda 2159753dece8SMiguel Ojeda /// Clears the vector, removing all values. 2160753dece8SMiguel Ojeda /// 2161753dece8SMiguel Ojeda /// Note that this method has no effect on the allocated capacity 2162753dece8SMiguel Ojeda /// of the vector. 2163753dece8SMiguel Ojeda /// 2164753dece8SMiguel Ojeda /// # Examples 2165753dece8SMiguel Ojeda /// 2166753dece8SMiguel Ojeda /// ``` 2167753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3]; 2168753dece8SMiguel Ojeda /// 2169753dece8SMiguel Ojeda /// v.clear(); 2170753dece8SMiguel Ojeda /// 2171753dece8SMiguel Ojeda /// assert!(v.is_empty()); 2172753dece8SMiguel Ojeda /// ``` 2173753dece8SMiguel Ojeda #[inline] 2174753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2175753dece8SMiguel Ojeda pub fn clear(&mut self) { 2176753dece8SMiguel Ojeda let elems: *mut [T] = self.as_mut_slice(); 2177753dece8SMiguel Ojeda 2178753dece8SMiguel Ojeda // SAFETY: 2179753dece8SMiguel Ojeda // - `elems` comes directly from `as_mut_slice` and is therefore valid. 2180753dece8SMiguel Ojeda // - Setting `self.len` before calling `drop_in_place` means that, 2181753dece8SMiguel Ojeda // if an element's `Drop` impl panics, the vector's `Drop` impl will 2182753dece8SMiguel Ojeda // do nothing (leaking the rest of the elements) instead of dropping 2183753dece8SMiguel Ojeda // some twice. 2184753dece8SMiguel Ojeda unsafe { 2185753dece8SMiguel Ojeda self.len = 0; 2186753dece8SMiguel Ojeda ptr::drop_in_place(elems); 2187753dece8SMiguel Ojeda } 2188753dece8SMiguel Ojeda } 2189753dece8SMiguel Ojeda 2190753dece8SMiguel Ojeda /// Returns the number of elements in the vector, also referred to 2191753dece8SMiguel Ojeda /// as its 'length'. 2192753dece8SMiguel Ojeda /// 2193753dece8SMiguel Ojeda /// # Examples 2194753dece8SMiguel Ojeda /// 2195753dece8SMiguel Ojeda /// ``` 2196753dece8SMiguel Ojeda /// let a = vec![1, 2, 3]; 2197753dece8SMiguel Ojeda /// assert_eq!(a.len(), 3); 2198753dece8SMiguel Ojeda /// ``` 2199753dece8SMiguel Ojeda #[inline] 2200753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2201753dece8SMiguel Ojeda pub fn len(&self) -> usize { 2202753dece8SMiguel Ojeda self.len 2203753dece8SMiguel Ojeda } 2204753dece8SMiguel Ojeda 2205753dece8SMiguel Ojeda /// Returns `true` if the vector contains no elements. 2206753dece8SMiguel Ojeda /// 2207753dece8SMiguel Ojeda /// # Examples 2208753dece8SMiguel Ojeda /// 2209753dece8SMiguel Ojeda /// ``` 2210753dece8SMiguel Ojeda /// let mut v = Vec::new(); 2211753dece8SMiguel Ojeda /// assert!(v.is_empty()); 2212753dece8SMiguel Ojeda /// 2213753dece8SMiguel Ojeda /// v.push(1); 2214753dece8SMiguel Ojeda /// assert!(!v.is_empty()); 2215753dece8SMiguel Ojeda /// ``` 2216753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2217753dece8SMiguel Ojeda pub fn is_empty(&self) -> bool { 2218753dece8SMiguel Ojeda self.len() == 0 2219753dece8SMiguel Ojeda } 2220753dece8SMiguel Ojeda 2221753dece8SMiguel Ojeda /// Splits the collection into two at the given index. 2222753dece8SMiguel Ojeda /// 2223753dece8SMiguel Ojeda /// Returns a newly allocated vector containing the elements in the range 2224753dece8SMiguel Ojeda /// `[at, len)`. After the call, the original vector will be left containing 2225753dece8SMiguel Ojeda /// the elements `[0, at)` with its previous capacity unchanged. 2226753dece8SMiguel Ojeda /// 2227753dece8SMiguel Ojeda /// # Panics 2228753dece8SMiguel Ojeda /// 2229753dece8SMiguel Ojeda /// Panics if `at > len`. 2230753dece8SMiguel Ojeda /// 2231753dece8SMiguel Ojeda /// # Examples 2232753dece8SMiguel Ojeda /// 2233753dece8SMiguel Ojeda /// ``` 2234753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3]; 2235753dece8SMiguel Ojeda /// let vec2 = vec.split_off(1); 2236753dece8SMiguel Ojeda /// assert_eq!(vec, [1]); 2237753dece8SMiguel Ojeda /// assert_eq!(vec2, [2, 3]); 2238753dece8SMiguel Ojeda /// ``` 2239753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2240753dece8SMiguel Ojeda #[inline] 2241753dece8SMiguel Ojeda #[must_use = "use `.truncate()` if you don't need the other half"] 2242753dece8SMiguel Ojeda #[stable(feature = "split_off", since = "1.4.0")] 2243753dece8SMiguel Ojeda pub fn split_off(&mut self, at: usize) -> Self 2244753dece8SMiguel Ojeda where 2245753dece8SMiguel Ojeda A: Clone, 2246753dece8SMiguel Ojeda { 2247753dece8SMiguel Ojeda #[cold] 2248753dece8SMiguel Ojeda #[inline(never)] 2249753dece8SMiguel Ojeda fn assert_failed(at: usize, len: usize) -> ! { 2250753dece8SMiguel Ojeda panic!("`at` split index (is {at}) should be <= len (is {len})"); 2251753dece8SMiguel Ojeda } 2252753dece8SMiguel Ojeda 2253753dece8SMiguel Ojeda if at > self.len() { 2254753dece8SMiguel Ojeda assert_failed(at, self.len()); 2255753dece8SMiguel Ojeda } 2256753dece8SMiguel Ojeda 2257753dece8SMiguel Ojeda if at == 0 { 2258753dece8SMiguel Ojeda // the new vector can take over the original buffer and avoid the copy 2259753dece8SMiguel Ojeda return mem::replace( 2260753dece8SMiguel Ojeda self, 2261753dece8SMiguel Ojeda Vec::with_capacity_in(self.capacity(), self.allocator().clone()), 2262753dece8SMiguel Ojeda ); 2263753dece8SMiguel Ojeda } 2264753dece8SMiguel Ojeda 2265753dece8SMiguel Ojeda let other_len = self.len - at; 2266753dece8SMiguel Ojeda let mut other = Vec::with_capacity_in(other_len, self.allocator().clone()); 2267753dece8SMiguel Ojeda 2268753dece8SMiguel Ojeda // Unsafely `set_len` and copy items to `other`. 2269753dece8SMiguel Ojeda unsafe { 2270753dece8SMiguel Ojeda self.set_len(at); 2271753dece8SMiguel Ojeda other.set_len(other_len); 2272753dece8SMiguel Ojeda 2273753dece8SMiguel Ojeda ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len()); 2274753dece8SMiguel Ojeda } 2275753dece8SMiguel Ojeda other 2276753dece8SMiguel Ojeda } 2277753dece8SMiguel Ojeda 2278753dece8SMiguel Ojeda /// Resizes the `Vec` in-place so that `len` is equal to `new_len`. 2279753dece8SMiguel Ojeda /// 2280753dece8SMiguel Ojeda /// If `new_len` is greater than `len`, the `Vec` is extended by the 2281753dece8SMiguel Ojeda /// difference, with each additional slot filled with the result of 2282753dece8SMiguel Ojeda /// calling the closure `f`. The return values from `f` will end up 2283753dece8SMiguel Ojeda /// in the `Vec` in the order they have been generated. 2284753dece8SMiguel Ojeda /// 2285753dece8SMiguel Ojeda /// If `new_len` is less than `len`, the `Vec` is simply truncated. 2286753dece8SMiguel Ojeda /// 2287753dece8SMiguel Ojeda /// This method uses a closure to create new values on every push. If 2288753dece8SMiguel Ojeda /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you 2289753dece8SMiguel Ojeda /// want to use the [`Default`] trait to generate values, you can 2290753dece8SMiguel Ojeda /// pass [`Default::default`] as the second argument. 2291753dece8SMiguel Ojeda /// 2292753dece8SMiguel Ojeda /// # Examples 2293753dece8SMiguel Ojeda /// 2294753dece8SMiguel Ojeda /// ``` 2295753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3]; 2296753dece8SMiguel Ojeda /// vec.resize_with(5, Default::default); 2297753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 0, 0]); 2298753dece8SMiguel Ojeda /// 2299753dece8SMiguel Ojeda /// let mut vec = vec![]; 2300753dece8SMiguel Ojeda /// let mut p = 1; 2301753dece8SMiguel Ojeda /// vec.resize_with(4, || { p *= 2; p }); 2302753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 4, 8, 16]); 2303753dece8SMiguel Ojeda /// ``` 2304753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2305753dece8SMiguel Ojeda #[stable(feature = "vec_resize_with", since = "1.33.0")] 2306753dece8SMiguel Ojeda pub fn resize_with<F>(&mut self, new_len: usize, f: F) 2307753dece8SMiguel Ojeda where 2308753dece8SMiguel Ojeda F: FnMut() -> T, 2309753dece8SMiguel Ojeda { 2310753dece8SMiguel Ojeda let len = self.len(); 2311753dece8SMiguel Ojeda if new_len > len { 23123ed03f4dSMiguel Ojeda self.extend_trusted(iter::repeat_with(f).take(new_len - len)); 2313753dece8SMiguel Ojeda } else { 2314753dece8SMiguel Ojeda self.truncate(new_len); 2315753dece8SMiguel Ojeda } 2316753dece8SMiguel Ojeda } 2317753dece8SMiguel Ojeda 2318753dece8SMiguel Ojeda /// Consumes and leaks the `Vec`, returning a mutable reference to the contents, 2319753dece8SMiguel Ojeda /// `&'a mut [T]`. Note that the type `T` must outlive the chosen lifetime 2320753dece8SMiguel Ojeda /// `'a`. If the type has only static references, or none at all, then this 2321753dece8SMiguel Ojeda /// may be chosen to be `'static`. 2322753dece8SMiguel Ojeda /// 2323753dece8SMiguel Ojeda /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`, 2324753dece8SMiguel Ojeda /// so the leaked allocation may include unused capacity that is not part 2325753dece8SMiguel Ojeda /// of the returned slice. 2326753dece8SMiguel Ojeda /// 2327753dece8SMiguel Ojeda /// This function is mainly useful for data that lives for the remainder of 2328753dece8SMiguel Ojeda /// the program's life. Dropping the returned reference will cause a memory 2329753dece8SMiguel Ojeda /// leak. 2330753dece8SMiguel Ojeda /// 2331753dece8SMiguel Ojeda /// # Examples 2332753dece8SMiguel Ojeda /// 2333753dece8SMiguel Ojeda /// Simple usage: 2334753dece8SMiguel Ojeda /// 2335753dece8SMiguel Ojeda /// ``` 2336753dece8SMiguel Ojeda /// let x = vec![1, 2, 3]; 2337753dece8SMiguel Ojeda /// let static_ref: &'static mut [usize] = x.leak(); 2338753dece8SMiguel Ojeda /// static_ref[0] += 1; 2339753dece8SMiguel Ojeda /// assert_eq!(static_ref, &[2, 2, 3]); 2340753dece8SMiguel Ojeda /// ``` 2341753dece8SMiguel Ojeda #[stable(feature = "vec_leak", since = "1.47.0")] 2342753dece8SMiguel Ojeda #[inline] 2343753dece8SMiguel Ojeda pub fn leak<'a>(self) -> &'a mut [T] 2344753dece8SMiguel Ojeda where 2345753dece8SMiguel Ojeda A: 'a, 2346753dece8SMiguel Ojeda { 2347753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self); 2348753dece8SMiguel Ojeda unsafe { slice::from_raw_parts_mut(me.as_mut_ptr(), me.len) } 2349753dece8SMiguel Ojeda } 2350753dece8SMiguel Ojeda 2351753dece8SMiguel Ojeda /// Returns the remaining spare capacity of the vector as a slice of 2352753dece8SMiguel Ojeda /// `MaybeUninit<T>`. 2353753dece8SMiguel Ojeda /// 2354753dece8SMiguel Ojeda /// The returned slice can be used to fill the vector with data (e.g. by 2355753dece8SMiguel Ojeda /// reading from a file) before marking the data as initialized using the 2356753dece8SMiguel Ojeda /// [`set_len`] method. 2357753dece8SMiguel Ojeda /// 2358753dece8SMiguel Ojeda /// [`set_len`]: Vec::set_len 2359753dece8SMiguel Ojeda /// 2360753dece8SMiguel Ojeda /// # Examples 2361753dece8SMiguel Ojeda /// 2362753dece8SMiguel Ojeda /// ``` 2363753dece8SMiguel Ojeda /// // Allocate vector big enough for 10 elements. 2364753dece8SMiguel Ojeda /// let mut v = Vec::with_capacity(10); 2365753dece8SMiguel Ojeda /// 2366753dece8SMiguel Ojeda /// // Fill in the first 3 elements. 2367753dece8SMiguel Ojeda /// let uninit = v.spare_capacity_mut(); 2368753dece8SMiguel Ojeda /// uninit[0].write(0); 2369753dece8SMiguel Ojeda /// uninit[1].write(1); 2370753dece8SMiguel Ojeda /// uninit[2].write(2); 2371753dece8SMiguel Ojeda /// 2372753dece8SMiguel Ojeda /// // Mark the first 3 elements of the vector as being initialized. 2373753dece8SMiguel Ojeda /// unsafe { 2374753dece8SMiguel Ojeda /// v.set_len(3); 2375753dece8SMiguel Ojeda /// } 2376753dece8SMiguel Ojeda /// 2377753dece8SMiguel Ojeda /// assert_eq!(&v, &[0, 1, 2]); 2378753dece8SMiguel Ojeda /// ``` 2379753dece8SMiguel Ojeda #[stable(feature = "vec_spare_capacity", since = "1.60.0")] 2380753dece8SMiguel Ojeda #[inline] 2381753dece8SMiguel Ojeda pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] { 2382753dece8SMiguel Ojeda // Note: 2383753dece8SMiguel Ojeda // This method is not implemented in terms of `split_at_spare_mut`, 2384753dece8SMiguel Ojeda // to prevent invalidation of pointers to the buffer. 2385753dece8SMiguel Ojeda unsafe { 2386753dece8SMiguel Ojeda slice::from_raw_parts_mut( 2387753dece8SMiguel Ojeda self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>, 2388753dece8SMiguel Ojeda self.buf.capacity() - self.len, 2389753dece8SMiguel Ojeda ) 2390753dece8SMiguel Ojeda } 2391753dece8SMiguel Ojeda } 2392753dece8SMiguel Ojeda 2393753dece8SMiguel Ojeda /// Returns vector content as a slice of `T`, along with the remaining spare 2394753dece8SMiguel Ojeda /// capacity of the vector as a slice of `MaybeUninit<T>`. 2395753dece8SMiguel Ojeda /// 2396753dece8SMiguel Ojeda /// The returned spare capacity slice can be used to fill the vector with data 2397753dece8SMiguel Ojeda /// (e.g. by reading from a file) before marking the data as initialized using 2398753dece8SMiguel Ojeda /// the [`set_len`] method. 2399753dece8SMiguel Ojeda /// 2400753dece8SMiguel Ojeda /// [`set_len`]: Vec::set_len 2401753dece8SMiguel Ojeda /// 2402753dece8SMiguel Ojeda /// Note that this is a low-level API, which should be used with care for 2403753dece8SMiguel Ojeda /// optimization purposes. If you need to append data to a `Vec` 2404753dece8SMiguel Ojeda /// you can use [`push`], [`extend`], [`extend_from_slice`], 2405753dece8SMiguel Ojeda /// [`extend_from_within`], [`insert`], [`append`], [`resize`] or 2406753dece8SMiguel Ojeda /// [`resize_with`], depending on your exact needs. 2407753dece8SMiguel Ojeda /// 2408753dece8SMiguel Ojeda /// [`push`]: Vec::push 2409753dece8SMiguel Ojeda /// [`extend`]: Vec::extend 2410753dece8SMiguel Ojeda /// [`extend_from_slice`]: Vec::extend_from_slice 2411753dece8SMiguel Ojeda /// [`extend_from_within`]: Vec::extend_from_within 2412753dece8SMiguel Ojeda /// [`insert`]: Vec::insert 2413753dece8SMiguel Ojeda /// [`append`]: Vec::append 2414753dece8SMiguel Ojeda /// [`resize`]: Vec::resize 2415753dece8SMiguel Ojeda /// [`resize_with`]: Vec::resize_with 2416753dece8SMiguel Ojeda /// 2417753dece8SMiguel Ojeda /// # Examples 2418753dece8SMiguel Ojeda /// 2419753dece8SMiguel Ojeda /// ``` 2420753dece8SMiguel Ojeda /// #![feature(vec_split_at_spare)] 2421753dece8SMiguel Ojeda /// 2422753dece8SMiguel Ojeda /// let mut v = vec![1, 1, 2]; 2423753dece8SMiguel Ojeda /// 2424753dece8SMiguel Ojeda /// // Reserve additional space big enough for 10 elements. 2425753dece8SMiguel Ojeda /// v.reserve(10); 2426753dece8SMiguel Ojeda /// 2427753dece8SMiguel Ojeda /// let (init, uninit) = v.split_at_spare_mut(); 2428753dece8SMiguel Ojeda /// let sum = init.iter().copied().sum::<u32>(); 2429753dece8SMiguel Ojeda /// 2430753dece8SMiguel Ojeda /// // Fill in the next 4 elements. 2431753dece8SMiguel Ojeda /// uninit[0].write(sum); 2432753dece8SMiguel Ojeda /// uninit[1].write(sum * 2); 2433753dece8SMiguel Ojeda /// uninit[2].write(sum * 3); 2434753dece8SMiguel Ojeda /// uninit[3].write(sum * 4); 2435753dece8SMiguel Ojeda /// 2436753dece8SMiguel Ojeda /// // Mark the 4 elements of the vector as being initialized. 2437753dece8SMiguel Ojeda /// unsafe { 2438753dece8SMiguel Ojeda /// let len = v.len(); 2439753dece8SMiguel Ojeda /// v.set_len(len + 4); 2440753dece8SMiguel Ojeda /// } 2441753dece8SMiguel Ojeda /// 2442753dece8SMiguel Ojeda /// assert_eq!(&v, &[1, 1, 2, 4, 8, 12, 16]); 2443753dece8SMiguel Ojeda /// ``` 2444753dece8SMiguel Ojeda #[unstable(feature = "vec_split_at_spare", issue = "81944")] 2445753dece8SMiguel Ojeda #[inline] 2446753dece8SMiguel Ojeda pub fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) { 2447753dece8SMiguel Ojeda // SAFETY: 2448753dece8SMiguel Ojeda // - len is ignored and so never changed 2449753dece8SMiguel Ojeda let (init, spare, _) = unsafe { self.split_at_spare_mut_with_len() }; 2450753dece8SMiguel Ojeda (init, spare) 2451753dece8SMiguel Ojeda } 2452753dece8SMiguel Ojeda 2453753dece8SMiguel Ojeda /// Safety: changing returned .2 (&mut usize) is considered the same as calling `.set_len(_)`. 2454753dece8SMiguel Ojeda /// 2455753dece8SMiguel Ojeda /// This method provides unique access to all vec parts at once in `extend_from_within`. 2456753dece8SMiguel Ojeda unsafe fn split_at_spare_mut_with_len( 2457753dece8SMiguel Ojeda &mut self, 2458753dece8SMiguel Ojeda ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) { 2459753dece8SMiguel Ojeda let ptr = self.as_mut_ptr(); 2460753dece8SMiguel Ojeda // SAFETY: 2461753dece8SMiguel Ojeda // - `ptr` is guaranteed to be valid for `self.len` elements 2462753dece8SMiguel Ojeda // - but the allocation extends out to `self.buf.capacity()` elements, possibly 2463753dece8SMiguel Ojeda // uninitialized 2464753dece8SMiguel Ojeda let spare_ptr = unsafe { ptr.add(self.len) }; 2465753dece8SMiguel Ojeda let spare_ptr = spare_ptr.cast::<MaybeUninit<T>>(); 2466753dece8SMiguel Ojeda let spare_len = self.buf.capacity() - self.len; 2467753dece8SMiguel Ojeda 2468753dece8SMiguel Ojeda // SAFETY: 2469753dece8SMiguel Ojeda // - `ptr` is guaranteed to be valid for `self.len` elements 2470753dece8SMiguel Ojeda // - `spare_ptr` is pointing one element past the buffer, so it doesn't overlap with `initialized` 2471753dece8SMiguel Ojeda unsafe { 2472753dece8SMiguel Ojeda let initialized = slice::from_raw_parts_mut(ptr, self.len); 2473753dece8SMiguel Ojeda let spare = slice::from_raw_parts_mut(spare_ptr, spare_len); 2474753dece8SMiguel Ojeda 2475753dece8SMiguel Ojeda (initialized, spare, &mut self.len) 2476753dece8SMiguel Ojeda } 2477753dece8SMiguel Ojeda } 2478753dece8SMiguel Ojeda } 2479753dece8SMiguel Ojeda 2480753dece8SMiguel Ojeda impl<T: Clone, A: Allocator> Vec<T, A> { 2481753dece8SMiguel Ojeda /// Resizes the `Vec` in-place so that `len` is equal to `new_len`. 2482753dece8SMiguel Ojeda /// 2483753dece8SMiguel Ojeda /// If `new_len` is greater than `len`, the `Vec` is extended by the 2484753dece8SMiguel Ojeda /// difference, with each additional slot filled with `value`. 2485753dece8SMiguel Ojeda /// If `new_len` is less than `len`, the `Vec` is simply truncated. 2486753dece8SMiguel Ojeda /// 2487753dece8SMiguel Ojeda /// This method requires `T` to implement [`Clone`], 2488753dece8SMiguel Ojeda /// in order to be able to clone the passed value. 2489753dece8SMiguel Ojeda /// If you need more flexibility (or want to rely on [`Default`] instead of 2490753dece8SMiguel Ojeda /// [`Clone`]), use [`Vec::resize_with`]. 2491753dece8SMiguel Ojeda /// If you only need to resize to a smaller size, use [`Vec::truncate`]. 2492753dece8SMiguel Ojeda /// 2493753dece8SMiguel Ojeda /// # Examples 2494753dece8SMiguel Ojeda /// 2495753dece8SMiguel Ojeda /// ``` 2496753dece8SMiguel Ojeda /// let mut vec = vec!["hello"]; 2497753dece8SMiguel Ojeda /// vec.resize(3, "world"); 2498753dece8SMiguel Ojeda /// assert_eq!(vec, ["hello", "world", "world"]); 2499753dece8SMiguel Ojeda /// 2500753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4]; 2501753dece8SMiguel Ojeda /// vec.resize(2, 0); 2502753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2]); 2503753dece8SMiguel Ojeda /// ``` 2504753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2505753dece8SMiguel Ojeda #[stable(feature = "vec_resize", since = "1.5.0")] 2506753dece8SMiguel Ojeda pub fn resize(&mut self, new_len: usize, value: T) { 2507753dece8SMiguel Ojeda let len = self.len(); 2508753dece8SMiguel Ojeda 2509753dece8SMiguel Ojeda if new_len > len { 2510753dece8SMiguel Ojeda self.extend_with(new_len - len, ExtendElement(value)) 2511753dece8SMiguel Ojeda } else { 2512753dece8SMiguel Ojeda self.truncate(new_len); 2513753dece8SMiguel Ojeda } 2514753dece8SMiguel Ojeda } 2515753dece8SMiguel Ojeda 2516318c3cc8SMiguel Ojeda /// Tries to resize the `Vec` in-place so that `len` is equal to `new_len`. 2517318c3cc8SMiguel Ojeda /// 2518318c3cc8SMiguel Ojeda /// If `new_len` is greater than `len`, the `Vec` is extended by the 2519318c3cc8SMiguel Ojeda /// difference, with each additional slot filled with `value`. 2520318c3cc8SMiguel Ojeda /// If `new_len` is less than `len`, the `Vec` is simply truncated. 2521318c3cc8SMiguel Ojeda /// 2522318c3cc8SMiguel Ojeda /// This method requires `T` to implement [`Clone`], 2523318c3cc8SMiguel Ojeda /// in order to be able to clone the passed value. 2524318c3cc8SMiguel Ojeda /// If you need more flexibility (or want to rely on [`Default`] instead of 2525318c3cc8SMiguel Ojeda /// [`Clone`]), use [`Vec::resize_with`]. 2526318c3cc8SMiguel Ojeda /// If you only need to resize to a smaller size, use [`Vec::truncate`]. 2527318c3cc8SMiguel Ojeda /// 2528318c3cc8SMiguel Ojeda /// # Examples 2529318c3cc8SMiguel Ojeda /// 2530318c3cc8SMiguel Ojeda /// ``` 2531318c3cc8SMiguel Ojeda /// let mut vec = vec!["hello"]; 2532318c3cc8SMiguel Ojeda /// vec.try_resize(3, "world").unwrap(); 2533318c3cc8SMiguel Ojeda /// assert_eq!(vec, ["hello", "world", "world"]); 2534318c3cc8SMiguel Ojeda /// 2535318c3cc8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4]; 2536318c3cc8SMiguel Ojeda /// vec.try_resize(2, 0).unwrap(); 2537318c3cc8SMiguel Ojeda /// assert_eq!(vec, [1, 2]); 2538318c3cc8SMiguel Ojeda /// 2539318c3cc8SMiguel Ojeda /// let mut vec = vec![42]; 2540318c3cc8SMiguel Ojeda /// let result = vec.try_resize(usize::MAX, 0); 2541318c3cc8SMiguel Ojeda /// assert!(result.is_err()); 2542318c3cc8SMiguel Ojeda /// ``` 2543318c3cc8SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")] 2544318c3cc8SMiguel Ojeda pub fn try_resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> { 2545318c3cc8SMiguel Ojeda let len = self.len(); 2546318c3cc8SMiguel Ojeda 2547318c3cc8SMiguel Ojeda if new_len > len { 2548318c3cc8SMiguel Ojeda self.try_extend_with(new_len - len, ExtendElement(value)) 2549318c3cc8SMiguel Ojeda } else { 2550318c3cc8SMiguel Ojeda self.truncate(new_len); 2551318c3cc8SMiguel Ojeda Ok(()) 2552318c3cc8SMiguel Ojeda } 2553318c3cc8SMiguel Ojeda } 2554318c3cc8SMiguel Ojeda 2555753dece8SMiguel Ojeda /// Clones and appends all elements in a slice to the `Vec`. 2556753dece8SMiguel Ojeda /// 2557753dece8SMiguel Ojeda /// Iterates over the slice `other`, clones each element, and then appends 2558753dece8SMiguel Ojeda /// it to this `Vec`. The `other` slice is traversed in-order. 2559753dece8SMiguel Ojeda /// 2560753dece8SMiguel Ojeda /// Note that this function is same as [`extend`] except that it is 2561753dece8SMiguel Ojeda /// specialized to work with slices instead. If and when Rust gets 2562753dece8SMiguel Ojeda /// specialization this function will likely be deprecated (but still 2563753dece8SMiguel Ojeda /// available). 2564753dece8SMiguel Ojeda /// 2565753dece8SMiguel Ojeda /// # Examples 2566753dece8SMiguel Ojeda /// 2567753dece8SMiguel Ojeda /// ``` 2568753dece8SMiguel Ojeda /// let mut vec = vec![1]; 2569753dece8SMiguel Ojeda /// vec.extend_from_slice(&[2, 3, 4]); 2570753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 4]); 2571753dece8SMiguel Ojeda /// ``` 2572753dece8SMiguel Ojeda /// 2573753dece8SMiguel Ojeda /// [`extend`]: Vec::extend 2574753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2575753dece8SMiguel Ojeda #[stable(feature = "vec_extend_from_slice", since = "1.6.0")] 2576753dece8SMiguel Ojeda pub fn extend_from_slice(&mut self, other: &[T]) { 2577753dece8SMiguel Ojeda self.spec_extend(other.iter()) 2578753dece8SMiguel Ojeda } 2579753dece8SMiguel Ojeda 2580318c3cc8SMiguel Ojeda /// Tries to clone and append all elements in a slice to the `Vec`. 2581318c3cc8SMiguel Ojeda /// 2582318c3cc8SMiguel Ojeda /// Iterates over the slice `other`, clones each element, and then appends 2583318c3cc8SMiguel Ojeda /// it to this `Vec`. The `other` slice is traversed in-order. 2584318c3cc8SMiguel Ojeda /// 2585318c3cc8SMiguel Ojeda /// Note that this function is same as [`extend`] except that it is 2586318c3cc8SMiguel Ojeda /// specialized to work with slices instead. If and when Rust gets 2587318c3cc8SMiguel Ojeda /// specialization this function will likely be deprecated (but still 2588318c3cc8SMiguel Ojeda /// available). 2589318c3cc8SMiguel Ojeda /// 2590318c3cc8SMiguel Ojeda /// # Examples 2591318c3cc8SMiguel Ojeda /// 2592318c3cc8SMiguel Ojeda /// ``` 2593318c3cc8SMiguel Ojeda /// let mut vec = vec![1]; 2594318c3cc8SMiguel Ojeda /// vec.try_extend_from_slice(&[2, 3, 4]).unwrap(); 2595318c3cc8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 4]); 2596318c3cc8SMiguel Ojeda /// ``` 2597318c3cc8SMiguel Ojeda /// 2598318c3cc8SMiguel Ojeda /// [`extend`]: Vec::extend 2599318c3cc8SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")] 2600318c3cc8SMiguel Ojeda pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError> { 2601318c3cc8SMiguel Ojeda self.try_spec_extend(other.iter()) 2602318c3cc8SMiguel Ojeda } 2603318c3cc8SMiguel Ojeda 2604753dece8SMiguel Ojeda /// Copies elements from `src` range to the end of the vector. 2605753dece8SMiguel Ojeda /// 2606753dece8SMiguel Ojeda /// # Panics 2607753dece8SMiguel Ojeda /// 2608753dece8SMiguel Ojeda /// Panics if the starting point is greater than the end point or if 2609753dece8SMiguel Ojeda /// the end point is greater than the length of the vector. 2610753dece8SMiguel Ojeda /// 2611753dece8SMiguel Ojeda /// # Examples 2612753dece8SMiguel Ojeda /// 2613753dece8SMiguel Ojeda /// ``` 2614753dece8SMiguel Ojeda /// let mut vec = vec![0, 1, 2, 3, 4]; 2615753dece8SMiguel Ojeda /// 2616753dece8SMiguel Ojeda /// vec.extend_from_within(2..); 2617753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4]); 2618753dece8SMiguel Ojeda /// 2619753dece8SMiguel Ojeda /// vec.extend_from_within(..2); 2620753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1]); 2621753dece8SMiguel Ojeda /// 2622753dece8SMiguel Ojeda /// vec.extend_from_within(4..8); 2623753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1, 4, 2, 3, 4]); 2624753dece8SMiguel Ojeda /// ``` 2625753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2626753dece8SMiguel Ojeda #[stable(feature = "vec_extend_from_within", since = "1.53.0")] 2627753dece8SMiguel Ojeda pub fn extend_from_within<R>(&mut self, src: R) 2628753dece8SMiguel Ojeda where 2629753dece8SMiguel Ojeda R: RangeBounds<usize>, 2630753dece8SMiguel Ojeda { 2631753dece8SMiguel Ojeda let range = slice::range(src, ..self.len()); 2632753dece8SMiguel Ojeda self.reserve(range.len()); 2633753dece8SMiguel Ojeda 2634753dece8SMiguel Ojeda // SAFETY: 2635753dece8SMiguel Ojeda // - `slice::range` guarantees that the given range is valid for indexing self 2636753dece8SMiguel Ojeda unsafe { 2637753dece8SMiguel Ojeda self.spec_extend_from_within(range); 2638753dece8SMiguel Ojeda } 2639753dece8SMiguel Ojeda } 2640753dece8SMiguel Ojeda } 2641753dece8SMiguel Ojeda 2642753dece8SMiguel Ojeda impl<T, A: Allocator, const N: usize> Vec<[T; N], A> { 2643753dece8SMiguel Ojeda /// Takes a `Vec<[T; N]>` and flattens it into a `Vec<T>`. 2644753dece8SMiguel Ojeda /// 2645753dece8SMiguel Ojeda /// # Panics 2646753dece8SMiguel Ojeda /// 2647753dece8SMiguel Ojeda /// Panics if the length of the resulting vector would overflow a `usize`. 2648753dece8SMiguel Ojeda /// 2649753dece8SMiguel Ojeda /// This is only possible when flattening a vector of arrays of zero-sized 2650753dece8SMiguel Ojeda /// types, and thus tends to be irrelevant in practice. If 2651753dece8SMiguel Ojeda /// `size_of::<T>() > 0`, this will never panic. 2652753dece8SMiguel Ojeda /// 2653753dece8SMiguel Ojeda /// # Examples 2654753dece8SMiguel Ojeda /// 2655753dece8SMiguel Ojeda /// ``` 2656753dece8SMiguel Ojeda /// #![feature(slice_flatten)] 2657753dece8SMiguel Ojeda /// 2658753dece8SMiguel Ojeda /// let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]]; 2659753dece8SMiguel Ojeda /// assert_eq!(vec.pop(), Some([7, 8, 9])); 2660753dece8SMiguel Ojeda /// 2661753dece8SMiguel Ojeda /// let mut flattened = vec.into_flattened(); 2662753dece8SMiguel Ojeda /// assert_eq!(flattened.pop(), Some(6)); 2663753dece8SMiguel Ojeda /// ``` 2664753dece8SMiguel Ojeda #[unstable(feature = "slice_flatten", issue = "95629")] 2665753dece8SMiguel Ojeda pub fn into_flattened(self) -> Vec<T, A> { 2666753dece8SMiguel Ojeda let (ptr, len, cap, alloc) = self.into_raw_parts_with_alloc(); 26673ed03f4dSMiguel Ojeda let (new_len, new_cap) = if T::IS_ZST { 2668753dece8SMiguel Ojeda (len.checked_mul(N).expect("vec len overflow"), usize::MAX) 2669753dece8SMiguel Ojeda } else { 2670753dece8SMiguel Ojeda // SAFETY: 2671753dece8SMiguel Ojeda // - `cap * N` cannot overflow because the allocation is already in 2672753dece8SMiguel Ojeda // the address space. 2673753dece8SMiguel Ojeda // - Each `[T; N]` has `N` valid elements, so there are `len * N` 2674753dece8SMiguel Ojeda // valid elements in the allocation. 2675753dece8SMiguel Ojeda unsafe { (len.unchecked_mul(N), cap.unchecked_mul(N)) } 2676753dece8SMiguel Ojeda }; 2677753dece8SMiguel Ojeda // SAFETY: 2678753dece8SMiguel Ojeda // - `ptr` was allocated by `self` 2679753dece8SMiguel Ojeda // - `ptr` is well-aligned because `[T; N]` has the same alignment as `T`. 2680753dece8SMiguel Ojeda // - `new_cap` refers to the same sized allocation as `cap` because 2681753dece8SMiguel Ojeda // `new_cap * size_of::<T>()` == `cap * size_of::<[T; N]>()` 2682753dece8SMiguel Ojeda // - `len` <= `cap`, so `len * N` <= `cap * N`. 2683753dece8SMiguel Ojeda unsafe { Vec::<T, A>::from_raw_parts_in(ptr.cast(), new_len, new_cap, alloc) } 2684753dece8SMiguel Ojeda } 2685753dece8SMiguel Ojeda } 2686753dece8SMiguel Ojeda 2687753dece8SMiguel Ojeda // This code generalizes `extend_with_{element,default}`. 2688753dece8SMiguel Ojeda trait ExtendWith<T> { 2689753dece8SMiguel Ojeda fn next(&mut self) -> T; 2690753dece8SMiguel Ojeda fn last(self) -> T; 2691753dece8SMiguel Ojeda } 2692753dece8SMiguel Ojeda 2693753dece8SMiguel Ojeda struct ExtendElement<T>(T); 2694753dece8SMiguel Ojeda impl<T: Clone> ExtendWith<T> for ExtendElement<T> { 2695753dece8SMiguel Ojeda fn next(&mut self) -> T { 2696753dece8SMiguel Ojeda self.0.clone() 2697753dece8SMiguel Ojeda } 2698753dece8SMiguel Ojeda fn last(self) -> T { 2699753dece8SMiguel Ojeda self.0 2700753dece8SMiguel Ojeda } 2701753dece8SMiguel Ojeda } 2702753dece8SMiguel Ojeda 2703753dece8SMiguel Ojeda impl<T, A: Allocator> Vec<T, A> { 2704753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2705753dece8SMiguel Ojeda /// Extend the vector by `n` values, using the given generator. 2706753dece8SMiguel Ojeda fn extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) { 2707753dece8SMiguel Ojeda self.reserve(n); 2708753dece8SMiguel Ojeda 2709753dece8SMiguel Ojeda unsafe { 2710753dece8SMiguel Ojeda let mut ptr = self.as_mut_ptr().add(self.len()); 2711753dece8SMiguel Ojeda // Use SetLenOnDrop to work around bug where compiler 2712753dece8SMiguel Ojeda // might not realize the store through `ptr` through self.set_len() 2713753dece8SMiguel Ojeda // don't alias. 2714753dece8SMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len); 2715753dece8SMiguel Ojeda 2716753dece8SMiguel Ojeda // Write all elements except the last one 2717753dece8SMiguel Ojeda for _ in 1..n { 2718753dece8SMiguel Ojeda ptr::write(ptr, value.next()); 27193ed03f4dSMiguel Ojeda ptr = ptr.add(1); 2720753dece8SMiguel Ojeda // Increment the length in every step in case next() panics 2721753dece8SMiguel Ojeda local_len.increment_len(1); 2722753dece8SMiguel Ojeda } 2723753dece8SMiguel Ojeda 2724753dece8SMiguel Ojeda if n > 0 { 2725753dece8SMiguel Ojeda // We can write the last element directly without cloning needlessly 2726753dece8SMiguel Ojeda ptr::write(ptr, value.last()); 2727753dece8SMiguel Ojeda local_len.increment_len(1); 2728753dece8SMiguel Ojeda } 2729753dece8SMiguel Ojeda 2730753dece8SMiguel Ojeda // len set by scope guard 2731753dece8SMiguel Ojeda } 2732753dece8SMiguel Ojeda } 2733318c3cc8SMiguel Ojeda 2734318c3cc8SMiguel Ojeda /// Try to extend the vector by `n` values, using the given generator. 2735318c3cc8SMiguel Ojeda fn try_extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) -> Result<(), TryReserveError> { 2736318c3cc8SMiguel Ojeda self.try_reserve(n)?; 2737318c3cc8SMiguel Ojeda 2738318c3cc8SMiguel Ojeda unsafe { 2739318c3cc8SMiguel Ojeda let mut ptr = self.as_mut_ptr().add(self.len()); 2740318c3cc8SMiguel Ojeda // Use SetLenOnDrop to work around bug where compiler 2741318c3cc8SMiguel Ojeda // might not realize the store through `ptr` through self.set_len() 2742318c3cc8SMiguel Ojeda // don't alias. 2743318c3cc8SMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len); 2744318c3cc8SMiguel Ojeda 2745318c3cc8SMiguel Ojeda // Write all elements except the last one 2746318c3cc8SMiguel Ojeda for _ in 1..n { 2747318c3cc8SMiguel Ojeda ptr::write(ptr, value.next()); 27483ed03f4dSMiguel Ojeda ptr = ptr.add(1); 2749318c3cc8SMiguel Ojeda // Increment the length in every step in case next() panics 2750318c3cc8SMiguel Ojeda local_len.increment_len(1); 2751318c3cc8SMiguel Ojeda } 2752318c3cc8SMiguel Ojeda 2753318c3cc8SMiguel Ojeda if n > 0 { 2754318c3cc8SMiguel Ojeda // We can write the last element directly without cloning needlessly 2755318c3cc8SMiguel Ojeda ptr::write(ptr, value.last()); 2756318c3cc8SMiguel Ojeda local_len.increment_len(1); 2757318c3cc8SMiguel Ojeda } 2758318c3cc8SMiguel Ojeda 2759318c3cc8SMiguel Ojeda // len set by scope guard 2760318c3cc8SMiguel Ojeda Ok(()) 2761318c3cc8SMiguel Ojeda } 2762318c3cc8SMiguel Ojeda } 2763753dece8SMiguel Ojeda } 2764753dece8SMiguel Ojeda 2765753dece8SMiguel Ojeda impl<T: PartialEq, A: Allocator> Vec<T, A> { 2766753dece8SMiguel Ojeda /// Removes consecutive repeated elements in the vector according to the 2767753dece8SMiguel Ojeda /// [`PartialEq`] trait implementation. 2768753dece8SMiguel Ojeda /// 2769753dece8SMiguel Ojeda /// If the vector is sorted, this removes all duplicates. 2770753dece8SMiguel Ojeda /// 2771753dece8SMiguel Ojeda /// # Examples 2772753dece8SMiguel Ojeda /// 2773753dece8SMiguel Ojeda /// ``` 2774753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 2, 3, 2]; 2775753dece8SMiguel Ojeda /// 2776753dece8SMiguel Ojeda /// vec.dedup(); 2777753dece8SMiguel Ojeda /// 2778753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 2]); 2779753dece8SMiguel Ojeda /// ``` 2780753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2781753dece8SMiguel Ojeda #[inline] 2782753dece8SMiguel Ojeda pub fn dedup(&mut self) { 2783753dece8SMiguel Ojeda self.dedup_by(|a, b| a == b) 2784753dece8SMiguel Ojeda } 2785753dece8SMiguel Ojeda } 2786753dece8SMiguel Ojeda 2787753dece8SMiguel Ojeda //////////////////////////////////////////////////////////////////////////////// 2788753dece8SMiguel Ojeda // Internal methods and functions 2789753dece8SMiguel Ojeda //////////////////////////////////////////////////////////////////////////////// 2790753dece8SMiguel Ojeda 2791753dece8SMiguel Ojeda #[doc(hidden)] 2792753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2793753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2794753dece8SMiguel Ojeda pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> { 2795753dece8SMiguel Ojeda <T as SpecFromElem>::from_elem(elem, n, Global) 2796753dece8SMiguel Ojeda } 2797753dece8SMiguel Ojeda 2798753dece8SMiguel Ojeda #[doc(hidden)] 2799753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2800753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")] 2801753dece8SMiguel Ojeda pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> { 2802753dece8SMiguel Ojeda <T as SpecFromElem>::from_elem(elem, n, alloc) 2803753dece8SMiguel Ojeda } 2804753dece8SMiguel Ojeda 2805753dece8SMiguel Ojeda trait ExtendFromWithinSpec { 2806753dece8SMiguel Ojeda /// # Safety 2807753dece8SMiguel Ojeda /// 2808753dece8SMiguel Ojeda /// - `src` needs to be valid index 2809753dece8SMiguel Ojeda /// - `self.capacity() - self.len()` must be `>= src.len()` 2810753dece8SMiguel Ojeda unsafe fn spec_extend_from_within(&mut self, src: Range<usize>); 2811753dece8SMiguel Ojeda } 2812753dece8SMiguel Ojeda 2813753dece8SMiguel Ojeda impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { 2814753dece8SMiguel Ojeda default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) { 2815753dece8SMiguel Ojeda // SAFETY: 2816753dece8SMiguel Ojeda // - len is increased only after initializing elements 2817753dece8SMiguel Ojeda let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() }; 2818753dece8SMiguel Ojeda 2819753dece8SMiguel Ojeda // SAFETY: 28203ed03f4dSMiguel Ojeda // - caller guarantees that src is a valid index 2821753dece8SMiguel Ojeda let to_clone = unsafe { this.get_unchecked(src) }; 2822753dece8SMiguel Ojeda 2823753dece8SMiguel Ojeda iter::zip(to_clone, spare) 2824753dece8SMiguel Ojeda .map(|(src, dst)| dst.write(src.clone())) 2825753dece8SMiguel Ojeda // Note: 2826753dece8SMiguel Ojeda // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len 2827753dece8SMiguel Ojeda // - len is increased after each element to prevent leaks (see issue #82533) 2828753dece8SMiguel Ojeda .for_each(|_| *len += 1); 2829753dece8SMiguel Ojeda } 2830753dece8SMiguel Ojeda } 2831753dece8SMiguel Ojeda 2832753dece8SMiguel Ojeda impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { 2833753dece8SMiguel Ojeda unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) { 2834753dece8SMiguel Ojeda let count = src.len(); 2835753dece8SMiguel Ojeda { 2836753dece8SMiguel Ojeda let (init, spare) = self.split_at_spare_mut(); 2837753dece8SMiguel Ojeda 2838753dece8SMiguel Ojeda // SAFETY: 28393ed03f4dSMiguel Ojeda // - caller guarantees that `src` is a valid index 2840753dece8SMiguel Ojeda let source = unsafe { init.get_unchecked(src) }; 2841753dece8SMiguel Ojeda 2842753dece8SMiguel Ojeda // SAFETY: 2843753dece8SMiguel Ojeda // - Both pointers are created from unique slice references (`&mut [_]`) 2844753dece8SMiguel Ojeda // so they are valid and do not overlap. 28453ed03f4dSMiguel Ojeda // - Elements are :Copy so it's OK to copy them, without doing 2846753dece8SMiguel Ojeda // anything with the original values 2847753dece8SMiguel Ojeda // - `count` is equal to the len of `source`, so source is valid for 2848753dece8SMiguel Ojeda // `count` reads 2849753dece8SMiguel Ojeda // - `.reserve(count)` guarantees that `spare.len() >= count` so spare 2850753dece8SMiguel Ojeda // is valid for `count` writes 2851753dece8SMiguel Ojeda unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) }; 2852753dece8SMiguel Ojeda } 2853753dece8SMiguel Ojeda 2854753dece8SMiguel Ojeda // SAFETY: 2855753dece8SMiguel Ojeda // - The elements were just initialized by `copy_nonoverlapping` 2856753dece8SMiguel Ojeda self.len += count; 2857753dece8SMiguel Ojeda } 2858753dece8SMiguel Ojeda } 2859753dece8SMiguel Ojeda 2860753dece8SMiguel Ojeda //////////////////////////////////////////////////////////////////////////////// 2861753dece8SMiguel Ojeda // Common trait implementations for Vec 2862753dece8SMiguel Ojeda //////////////////////////////////////////////////////////////////////////////// 2863753dece8SMiguel Ojeda 2864753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2865753dece8SMiguel Ojeda impl<T, A: Allocator> ops::Deref for Vec<T, A> { 2866753dece8SMiguel Ojeda type Target = [T]; 2867753dece8SMiguel Ojeda 28683ed03f4dSMiguel Ojeda #[inline] 2869753dece8SMiguel Ojeda fn deref(&self) -> &[T] { 2870753dece8SMiguel Ojeda unsafe { slice::from_raw_parts(self.as_ptr(), self.len) } 2871753dece8SMiguel Ojeda } 2872753dece8SMiguel Ojeda } 2873753dece8SMiguel Ojeda 2874753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2875753dece8SMiguel Ojeda impl<T, A: Allocator> ops::DerefMut for Vec<T, A> { 28763ed03f4dSMiguel Ojeda #[inline] 2877753dece8SMiguel Ojeda fn deref_mut(&mut self) -> &mut [T] { 2878753dece8SMiguel Ojeda unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) } 2879753dece8SMiguel Ojeda } 2880753dece8SMiguel Ojeda } 2881753dece8SMiguel Ojeda 2882753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2883753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2884753dece8SMiguel Ojeda impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> { 2885753dece8SMiguel Ojeda #[cfg(not(test))] 2886753dece8SMiguel Ojeda fn clone(&self) -> Self { 2887753dece8SMiguel Ojeda let alloc = self.allocator().clone(); 2888753dece8SMiguel Ojeda <[T]>::to_vec_in(&**self, alloc) 2889753dece8SMiguel Ojeda } 2890753dece8SMiguel Ojeda 2891753dece8SMiguel Ojeda // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is 2892753dece8SMiguel Ojeda // required for this method definition, is not available. Instead use the 2893753dece8SMiguel Ojeda // `slice::to_vec` function which is only available with cfg(test) 2894753dece8SMiguel Ojeda // NB see the slice::hack module in slice.rs for more information 2895753dece8SMiguel Ojeda #[cfg(test)] 2896753dece8SMiguel Ojeda fn clone(&self) -> Self { 2897753dece8SMiguel Ojeda let alloc = self.allocator().clone(); 2898753dece8SMiguel Ojeda crate::slice::to_vec(&**self, alloc) 2899753dece8SMiguel Ojeda } 2900753dece8SMiguel Ojeda 2901753dece8SMiguel Ojeda fn clone_from(&mut self, other: &Self) { 2902*89eed1abSMiguel Ojeda crate::slice::SpecCloneIntoVec::clone_into(other.as_slice(), self); 2903753dece8SMiguel Ojeda } 2904753dece8SMiguel Ojeda } 2905753dece8SMiguel Ojeda 2906753dece8SMiguel Ojeda /// The hash of a vector is the same as that of the corresponding slice, 2907753dece8SMiguel Ojeda /// as required by the `core::borrow::Borrow` implementation. 2908753dece8SMiguel Ojeda /// 2909753dece8SMiguel Ojeda /// ``` 2910753dece8SMiguel Ojeda /// use std::hash::BuildHasher; 2911753dece8SMiguel Ojeda /// 2912753dece8SMiguel Ojeda /// let b = std::collections::hash_map::RandomState::new(); 2913753dece8SMiguel Ojeda /// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09]; 2914753dece8SMiguel Ojeda /// let s: &[u8] = &[0xa8, 0x3c, 0x09]; 2915753dece8SMiguel Ojeda /// assert_eq!(b.hash_one(v), b.hash_one(s)); 2916753dece8SMiguel Ojeda /// ``` 2917753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2918753dece8SMiguel Ojeda impl<T: Hash, A: Allocator> Hash for Vec<T, A> { 2919753dece8SMiguel Ojeda #[inline] 2920753dece8SMiguel Ojeda fn hash<H: Hasher>(&self, state: &mut H) { 2921753dece8SMiguel Ojeda Hash::hash(&**self, state) 2922753dece8SMiguel Ojeda } 2923753dece8SMiguel Ojeda } 2924753dece8SMiguel Ojeda 2925753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2926753dece8SMiguel Ojeda #[rustc_on_unimplemented( 2927753dece8SMiguel Ojeda message = "vector indices are of type `usize` or ranges of `usize`", 2928753dece8SMiguel Ojeda label = "vector indices are of type `usize` or ranges of `usize`" 2929753dece8SMiguel Ojeda )] 2930753dece8SMiguel Ojeda impl<T, I: SliceIndex<[T]>, A: Allocator> Index<I> for Vec<T, A> { 2931753dece8SMiguel Ojeda type Output = I::Output; 2932753dece8SMiguel Ojeda 2933753dece8SMiguel Ojeda #[inline] 2934753dece8SMiguel Ojeda fn index(&self, index: I) -> &Self::Output { 2935753dece8SMiguel Ojeda Index::index(&**self, index) 2936753dece8SMiguel Ojeda } 2937753dece8SMiguel Ojeda } 2938753dece8SMiguel Ojeda 2939753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2940753dece8SMiguel Ojeda #[rustc_on_unimplemented( 2941753dece8SMiguel Ojeda message = "vector indices are of type `usize` or ranges of `usize`", 2942753dece8SMiguel Ojeda label = "vector indices are of type `usize` or ranges of `usize`" 2943753dece8SMiguel Ojeda )] 2944753dece8SMiguel Ojeda impl<T, I: SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> { 2945753dece8SMiguel Ojeda #[inline] 2946753dece8SMiguel Ojeda fn index_mut(&mut self, index: I) -> &mut Self::Output { 2947753dece8SMiguel Ojeda IndexMut::index_mut(&mut **self, index) 2948753dece8SMiguel Ojeda } 2949753dece8SMiguel Ojeda } 2950753dece8SMiguel Ojeda 2951753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 2952753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2953753dece8SMiguel Ojeda impl<T> FromIterator<T> for Vec<T> { 2954753dece8SMiguel Ojeda #[inline] 2955753dece8SMiguel Ojeda fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> { 2956753dece8SMiguel Ojeda <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter()) 2957753dece8SMiguel Ojeda } 2958753dece8SMiguel Ojeda } 2959753dece8SMiguel Ojeda 2960753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 2961753dece8SMiguel Ojeda impl<T, A: Allocator> IntoIterator for Vec<T, A> { 2962753dece8SMiguel Ojeda type Item = T; 2963753dece8SMiguel Ojeda type IntoIter = IntoIter<T, A>; 2964753dece8SMiguel Ojeda 2965753dece8SMiguel Ojeda /// Creates a consuming iterator, that is, one that moves each value out of 2966753dece8SMiguel Ojeda /// the vector (from start to end). The vector cannot be used after calling 2967753dece8SMiguel Ojeda /// this. 2968753dece8SMiguel Ojeda /// 2969753dece8SMiguel Ojeda /// # Examples 2970753dece8SMiguel Ojeda /// 2971753dece8SMiguel Ojeda /// ``` 2972753dece8SMiguel Ojeda /// let v = vec!["a".to_string(), "b".to_string()]; 29733ed03f4dSMiguel Ojeda /// let mut v_iter = v.into_iter(); 29743ed03f4dSMiguel Ojeda /// 29753ed03f4dSMiguel Ojeda /// let first_element: Option<String> = v_iter.next(); 29763ed03f4dSMiguel Ojeda /// 29773ed03f4dSMiguel Ojeda /// assert_eq!(first_element, Some("a".to_string())); 29783ed03f4dSMiguel Ojeda /// assert_eq!(v_iter.next(), Some("b".to_string())); 29793ed03f4dSMiguel Ojeda /// assert_eq!(v_iter.next(), None); 2980753dece8SMiguel Ojeda /// ``` 2981753dece8SMiguel Ojeda #[inline] 29823ed03f4dSMiguel Ojeda fn into_iter(self) -> Self::IntoIter { 2983753dece8SMiguel Ojeda unsafe { 2984753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self); 2985753dece8SMiguel Ojeda let alloc = ManuallyDrop::new(ptr::read(me.allocator())); 2986753dece8SMiguel Ojeda let begin = me.as_mut_ptr(); 29873ed03f4dSMiguel Ojeda let end = if T::IS_ZST { 29883ed03f4dSMiguel Ojeda begin.wrapping_byte_add(me.len()) 2989753dece8SMiguel Ojeda } else { 2990753dece8SMiguel Ojeda begin.add(me.len()) as *const T 2991753dece8SMiguel Ojeda }; 2992753dece8SMiguel Ojeda let cap = me.buf.capacity(); 2993753dece8SMiguel Ojeda IntoIter { 2994753dece8SMiguel Ojeda buf: NonNull::new_unchecked(begin), 2995753dece8SMiguel Ojeda phantom: PhantomData, 2996753dece8SMiguel Ojeda cap, 2997753dece8SMiguel Ojeda alloc, 2998753dece8SMiguel Ojeda ptr: begin, 2999753dece8SMiguel Ojeda end, 3000753dece8SMiguel Ojeda } 3001753dece8SMiguel Ojeda } 3002753dece8SMiguel Ojeda } 3003753dece8SMiguel Ojeda } 3004753dece8SMiguel Ojeda 3005753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3006753dece8SMiguel Ojeda impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> { 3007753dece8SMiguel Ojeda type Item = &'a T; 3008753dece8SMiguel Ojeda type IntoIter = slice::Iter<'a, T>; 3009753dece8SMiguel Ojeda 30103ed03f4dSMiguel Ojeda fn into_iter(self) -> Self::IntoIter { 3011753dece8SMiguel Ojeda self.iter() 3012753dece8SMiguel Ojeda } 3013753dece8SMiguel Ojeda } 3014753dece8SMiguel Ojeda 3015753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3016753dece8SMiguel Ojeda impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> { 3017753dece8SMiguel Ojeda type Item = &'a mut T; 3018753dece8SMiguel Ojeda type IntoIter = slice::IterMut<'a, T>; 3019753dece8SMiguel Ojeda 30203ed03f4dSMiguel Ojeda fn into_iter(self) -> Self::IntoIter { 3021753dece8SMiguel Ojeda self.iter_mut() 3022753dece8SMiguel Ojeda } 3023753dece8SMiguel Ojeda } 3024753dece8SMiguel Ojeda 3025753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3026753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3027753dece8SMiguel Ojeda impl<T, A: Allocator> Extend<T> for Vec<T, A> { 3028753dece8SMiguel Ojeda #[inline] 3029753dece8SMiguel Ojeda fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { 3030753dece8SMiguel Ojeda <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter()) 3031753dece8SMiguel Ojeda } 3032753dece8SMiguel Ojeda 3033753dece8SMiguel Ojeda #[inline] 3034753dece8SMiguel Ojeda fn extend_one(&mut self, item: T) { 3035753dece8SMiguel Ojeda self.push(item); 3036753dece8SMiguel Ojeda } 3037753dece8SMiguel Ojeda 3038753dece8SMiguel Ojeda #[inline] 3039753dece8SMiguel Ojeda fn extend_reserve(&mut self, additional: usize) { 3040753dece8SMiguel Ojeda self.reserve(additional); 3041753dece8SMiguel Ojeda } 3042753dece8SMiguel Ojeda } 3043753dece8SMiguel Ojeda 3044753dece8SMiguel Ojeda impl<T, A: Allocator> Vec<T, A> { 3045753dece8SMiguel Ojeda // leaf method to which various SpecFrom/SpecExtend implementations delegate when 3046753dece8SMiguel Ojeda // they have no further optimizations to apply 3047753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3048753dece8SMiguel Ojeda fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) { 3049753dece8SMiguel Ojeda // This is the case for a general iterator. 3050753dece8SMiguel Ojeda // 3051753dece8SMiguel Ojeda // This function should be the moral equivalent of: 3052753dece8SMiguel Ojeda // 3053753dece8SMiguel Ojeda // for item in iterator { 3054753dece8SMiguel Ojeda // self.push(item); 3055753dece8SMiguel Ojeda // } 3056753dece8SMiguel Ojeda while let Some(element) = iterator.next() { 3057753dece8SMiguel Ojeda let len = self.len(); 3058753dece8SMiguel Ojeda if len == self.capacity() { 3059753dece8SMiguel Ojeda let (lower, _) = iterator.size_hint(); 3060753dece8SMiguel Ojeda self.reserve(lower.saturating_add(1)); 3061753dece8SMiguel Ojeda } 3062753dece8SMiguel Ojeda unsafe { 3063753dece8SMiguel Ojeda ptr::write(self.as_mut_ptr().add(len), element); 3064753dece8SMiguel Ojeda // Since next() executes user code which can panic we have to bump the length 3065753dece8SMiguel Ojeda // after each step. 3066753dece8SMiguel Ojeda // NB can't overflow since we would have had to alloc the address space 3067753dece8SMiguel Ojeda self.set_len(len + 1); 3068753dece8SMiguel Ojeda } 3069753dece8SMiguel Ojeda } 3070753dece8SMiguel Ojeda } 3071753dece8SMiguel Ojeda 3072318c3cc8SMiguel Ojeda // leaf method to which various SpecFrom/SpecExtend implementations delegate when 3073318c3cc8SMiguel Ojeda // they have no further optimizations to apply 3074318c3cc8SMiguel Ojeda fn try_extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) -> Result<(), TryReserveError> { 3075318c3cc8SMiguel Ojeda // This is the case for a general iterator. 3076318c3cc8SMiguel Ojeda // 3077318c3cc8SMiguel Ojeda // This function should be the moral equivalent of: 3078318c3cc8SMiguel Ojeda // 3079318c3cc8SMiguel Ojeda // for item in iterator { 3080318c3cc8SMiguel Ojeda // self.push(item); 3081318c3cc8SMiguel Ojeda // } 3082318c3cc8SMiguel Ojeda while let Some(element) = iterator.next() { 3083318c3cc8SMiguel Ojeda let len = self.len(); 3084318c3cc8SMiguel Ojeda if len == self.capacity() { 3085318c3cc8SMiguel Ojeda let (lower, _) = iterator.size_hint(); 3086318c3cc8SMiguel Ojeda self.try_reserve(lower.saturating_add(1))?; 3087318c3cc8SMiguel Ojeda } 3088318c3cc8SMiguel Ojeda unsafe { 3089318c3cc8SMiguel Ojeda ptr::write(self.as_mut_ptr().add(len), element); 3090318c3cc8SMiguel Ojeda // Since next() executes user code which can panic we have to bump the length 3091318c3cc8SMiguel Ojeda // after each step. 3092318c3cc8SMiguel Ojeda // NB can't overflow since we would have had to alloc the address space 3093318c3cc8SMiguel Ojeda self.set_len(len + 1); 3094318c3cc8SMiguel Ojeda } 3095318c3cc8SMiguel Ojeda } 3096318c3cc8SMiguel Ojeda 3097318c3cc8SMiguel Ojeda Ok(()) 3098318c3cc8SMiguel Ojeda } 3099318c3cc8SMiguel Ojeda 31003ed03f4dSMiguel Ojeda // specific extend for `TrustedLen` iterators, called both by the specializations 31013ed03f4dSMiguel Ojeda // and internal places where resolving specialization makes compilation slower 31023ed03f4dSMiguel Ojeda #[cfg(not(no_global_oom_handling))] 31033ed03f4dSMiguel Ojeda fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) { 31043ed03f4dSMiguel Ojeda let (low, high) = iterator.size_hint(); 31053ed03f4dSMiguel Ojeda if let Some(additional) = high { 31063ed03f4dSMiguel Ojeda debug_assert_eq!( 31073ed03f4dSMiguel Ojeda low, 31083ed03f4dSMiguel Ojeda additional, 31093ed03f4dSMiguel Ojeda "TrustedLen iterator's size hint is not exact: {:?}", 31103ed03f4dSMiguel Ojeda (low, high) 31113ed03f4dSMiguel Ojeda ); 31123ed03f4dSMiguel Ojeda self.reserve(additional); 31133ed03f4dSMiguel Ojeda unsafe { 31143ed03f4dSMiguel Ojeda let ptr = self.as_mut_ptr(); 31153ed03f4dSMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len); 31163ed03f4dSMiguel Ojeda iterator.for_each(move |element| { 31173ed03f4dSMiguel Ojeda ptr::write(ptr.add(local_len.current_len()), element); 31183ed03f4dSMiguel Ojeda // Since the loop executes user code which can panic we have to update 31193ed03f4dSMiguel Ojeda // the length every step to correctly drop what we've written. 31203ed03f4dSMiguel Ojeda // NB can't overflow since we would have had to alloc the address space 31213ed03f4dSMiguel Ojeda local_len.increment_len(1); 31223ed03f4dSMiguel Ojeda }); 31233ed03f4dSMiguel Ojeda } 31243ed03f4dSMiguel Ojeda } else { 31253ed03f4dSMiguel Ojeda // Per TrustedLen contract a `None` upper bound means that the iterator length 31263ed03f4dSMiguel Ojeda // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway. 31273ed03f4dSMiguel Ojeda // Since the other branch already panics eagerly (via `reserve()`) we do the same here. 31283ed03f4dSMiguel Ojeda // This avoids additional codegen for a fallback code path which would eventually 31293ed03f4dSMiguel Ojeda // panic anyway. 31303ed03f4dSMiguel Ojeda panic!("capacity overflow"); 31313ed03f4dSMiguel Ojeda } 31323ed03f4dSMiguel Ojeda } 31333ed03f4dSMiguel Ojeda 31343ed03f4dSMiguel Ojeda // specific extend for `TrustedLen` iterators, called both by the specializations 31353ed03f4dSMiguel Ojeda // and internal places where resolving specialization makes compilation slower 31363ed03f4dSMiguel Ojeda fn try_extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) -> Result<(), TryReserveError> { 31373ed03f4dSMiguel Ojeda let (low, high) = iterator.size_hint(); 31383ed03f4dSMiguel Ojeda if let Some(additional) = high { 31393ed03f4dSMiguel Ojeda debug_assert_eq!( 31403ed03f4dSMiguel Ojeda low, 31413ed03f4dSMiguel Ojeda additional, 31423ed03f4dSMiguel Ojeda "TrustedLen iterator's size hint is not exact: {:?}", 31433ed03f4dSMiguel Ojeda (low, high) 31443ed03f4dSMiguel Ojeda ); 31453ed03f4dSMiguel Ojeda self.try_reserve(additional)?; 31463ed03f4dSMiguel Ojeda unsafe { 31473ed03f4dSMiguel Ojeda let ptr = self.as_mut_ptr(); 31483ed03f4dSMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len); 31493ed03f4dSMiguel Ojeda iterator.for_each(move |element| { 31503ed03f4dSMiguel Ojeda ptr::write(ptr.add(local_len.current_len()), element); 31513ed03f4dSMiguel Ojeda // Since the loop executes user code which can panic we have to update 31523ed03f4dSMiguel Ojeda // the length every step to correctly drop what we've written. 31533ed03f4dSMiguel Ojeda // NB can't overflow since we would have had to alloc the address space 31543ed03f4dSMiguel Ojeda local_len.increment_len(1); 31553ed03f4dSMiguel Ojeda }); 31563ed03f4dSMiguel Ojeda } 31573ed03f4dSMiguel Ojeda Ok(()) 31583ed03f4dSMiguel Ojeda } else { 31593ed03f4dSMiguel Ojeda Err(TryReserveErrorKind::CapacityOverflow.into()) 31603ed03f4dSMiguel Ojeda } 31613ed03f4dSMiguel Ojeda } 31623ed03f4dSMiguel Ojeda 3163753dece8SMiguel Ojeda /// Creates a splicing iterator that replaces the specified range in the vector 3164753dece8SMiguel Ojeda /// with the given `replace_with` iterator and yields the removed items. 3165753dece8SMiguel Ojeda /// `replace_with` does not need to be the same length as `range`. 3166753dece8SMiguel Ojeda /// 3167753dece8SMiguel Ojeda /// `range` is removed even if the iterator is not consumed until the end. 3168753dece8SMiguel Ojeda /// 3169753dece8SMiguel Ojeda /// It is unspecified how many elements are removed from the vector 3170753dece8SMiguel Ojeda /// if the `Splice` value is leaked. 3171753dece8SMiguel Ojeda /// 3172753dece8SMiguel Ojeda /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped. 3173753dece8SMiguel Ojeda /// 3174753dece8SMiguel Ojeda /// This is optimal if: 3175753dece8SMiguel Ojeda /// 3176753dece8SMiguel Ojeda /// * The tail (elements in the vector after `range`) is empty, 3177753dece8SMiguel Ojeda /// * or `replace_with` yields fewer or equal elements than `range`’s length 3178753dece8SMiguel Ojeda /// * or the lower bound of its `size_hint()` is exact. 3179753dece8SMiguel Ojeda /// 3180753dece8SMiguel Ojeda /// Otherwise, a temporary vector is allocated and the tail is moved twice. 3181753dece8SMiguel Ojeda /// 3182753dece8SMiguel Ojeda /// # Panics 3183753dece8SMiguel Ojeda /// 3184753dece8SMiguel Ojeda /// Panics if the starting point is greater than the end point or if 3185753dece8SMiguel Ojeda /// the end point is greater than the length of the vector. 3186753dece8SMiguel Ojeda /// 3187753dece8SMiguel Ojeda /// # Examples 3188753dece8SMiguel Ojeda /// 3189753dece8SMiguel Ojeda /// ``` 3190753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3, 4]; 3191753dece8SMiguel Ojeda /// let new = [7, 8, 9]; 3192753dece8SMiguel Ojeda /// let u: Vec<_> = v.splice(1..3, new).collect(); 3193753dece8SMiguel Ojeda /// assert_eq!(v, &[1, 7, 8, 9, 4]); 3194753dece8SMiguel Ojeda /// assert_eq!(u, &[2, 3]); 3195753dece8SMiguel Ojeda /// ``` 3196753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3197753dece8SMiguel Ojeda #[inline] 3198753dece8SMiguel Ojeda #[stable(feature = "vec_splice", since = "1.21.0")] 3199753dece8SMiguel Ojeda pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A> 3200753dece8SMiguel Ojeda where 3201753dece8SMiguel Ojeda R: RangeBounds<usize>, 3202753dece8SMiguel Ojeda I: IntoIterator<Item = T>, 3203753dece8SMiguel Ojeda { 3204753dece8SMiguel Ojeda Splice { drain: self.drain(range), replace_with: replace_with.into_iter() } 3205753dece8SMiguel Ojeda } 3206753dece8SMiguel Ojeda 3207753dece8SMiguel Ojeda /// Creates an iterator which uses a closure to determine if an element should be removed. 3208753dece8SMiguel Ojeda /// 3209753dece8SMiguel Ojeda /// If the closure returns true, then the element is removed and yielded. 3210753dece8SMiguel Ojeda /// If the closure returns false, the element will remain in the vector and will not be yielded 3211753dece8SMiguel Ojeda /// by the iterator. 3212753dece8SMiguel Ojeda /// 3213753dece8SMiguel Ojeda /// Using this method is equivalent to the following code: 3214753dece8SMiguel Ojeda /// 3215753dece8SMiguel Ojeda /// ``` 3216753dece8SMiguel Ojeda /// # let some_predicate = |x: &mut i32| { *x == 2 || *x == 3 || *x == 6 }; 3217753dece8SMiguel Ojeda /// # let mut vec = vec![1, 2, 3, 4, 5, 6]; 3218753dece8SMiguel Ojeda /// let mut i = 0; 3219753dece8SMiguel Ojeda /// while i < vec.len() { 3220753dece8SMiguel Ojeda /// if some_predicate(&mut vec[i]) { 3221753dece8SMiguel Ojeda /// let val = vec.remove(i); 3222753dece8SMiguel Ojeda /// // your code here 3223753dece8SMiguel Ojeda /// } else { 3224753dece8SMiguel Ojeda /// i += 1; 3225753dece8SMiguel Ojeda /// } 3226753dece8SMiguel Ojeda /// } 3227753dece8SMiguel Ojeda /// 3228753dece8SMiguel Ojeda /// # assert_eq!(vec, vec![1, 4, 5]); 3229753dece8SMiguel Ojeda /// ``` 3230753dece8SMiguel Ojeda /// 3231753dece8SMiguel Ojeda /// But `drain_filter` is easier to use. `drain_filter` is also more efficient, 3232753dece8SMiguel Ojeda /// because it can backshift the elements of the array in bulk. 3233753dece8SMiguel Ojeda /// 3234753dece8SMiguel Ojeda /// Note that `drain_filter` also lets you mutate every element in the filter closure, 3235753dece8SMiguel Ojeda /// regardless of whether you choose to keep or remove it. 3236753dece8SMiguel Ojeda /// 3237753dece8SMiguel Ojeda /// # Examples 3238753dece8SMiguel Ojeda /// 3239753dece8SMiguel Ojeda /// Splitting an array into evens and odds, reusing the original allocation: 3240753dece8SMiguel Ojeda /// 3241753dece8SMiguel Ojeda /// ``` 3242753dece8SMiguel Ojeda /// #![feature(drain_filter)] 3243753dece8SMiguel Ojeda /// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]; 3244753dece8SMiguel Ojeda /// 3245753dece8SMiguel Ojeda /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>(); 3246753dece8SMiguel Ojeda /// let odds = numbers; 3247753dece8SMiguel Ojeda /// 3248753dece8SMiguel Ojeda /// assert_eq!(evens, vec![2, 4, 6, 8, 14]); 3249753dece8SMiguel Ojeda /// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]); 3250753dece8SMiguel Ojeda /// ``` 3251753dece8SMiguel Ojeda #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] 3252753dece8SMiguel Ojeda pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F, A> 3253753dece8SMiguel Ojeda where 3254753dece8SMiguel Ojeda F: FnMut(&mut T) -> bool, 3255753dece8SMiguel Ojeda { 3256753dece8SMiguel Ojeda let old_len = self.len(); 3257753dece8SMiguel Ojeda 3258753dece8SMiguel Ojeda // Guard against us getting leaked (leak amplification) 3259753dece8SMiguel Ojeda unsafe { 3260753dece8SMiguel Ojeda self.set_len(0); 3261753dece8SMiguel Ojeda } 3262753dece8SMiguel Ojeda 3263753dece8SMiguel Ojeda DrainFilter { vec: self, idx: 0, del: 0, old_len, pred: filter, panic_flag: false } 3264753dece8SMiguel Ojeda } 3265753dece8SMiguel Ojeda } 3266753dece8SMiguel Ojeda 3267753dece8SMiguel Ojeda /// Extend implementation that copies elements out of references before pushing them onto the Vec. 3268753dece8SMiguel Ojeda /// 3269753dece8SMiguel Ojeda /// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to 3270753dece8SMiguel Ojeda /// append the entire slice at once. 3271753dece8SMiguel Ojeda /// 3272753dece8SMiguel Ojeda /// [`copy_from_slice`]: slice::copy_from_slice 3273753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3274753dece8SMiguel Ojeda #[stable(feature = "extend_ref", since = "1.2.0")] 3275753dece8SMiguel Ojeda impl<'a, T: Copy + 'a, A: Allocator + 'a> Extend<&'a T> for Vec<T, A> { 3276753dece8SMiguel Ojeda fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { 3277753dece8SMiguel Ojeda self.spec_extend(iter.into_iter()) 3278753dece8SMiguel Ojeda } 3279753dece8SMiguel Ojeda 3280753dece8SMiguel Ojeda #[inline] 3281753dece8SMiguel Ojeda fn extend_one(&mut self, &item: &'a T) { 3282753dece8SMiguel Ojeda self.push(item); 3283753dece8SMiguel Ojeda } 3284753dece8SMiguel Ojeda 3285753dece8SMiguel Ojeda #[inline] 3286753dece8SMiguel Ojeda fn extend_reserve(&mut self, additional: usize) { 3287753dece8SMiguel Ojeda self.reserve(additional); 3288753dece8SMiguel Ojeda } 3289753dece8SMiguel Ojeda } 3290753dece8SMiguel Ojeda 3291*89eed1abSMiguel Ojeda /// Implements comparison of vectors, [lexicographically](Ord#lexicographical-comparison). 3292753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3293753dece8SMiguel Ojeda impl<T: PartialOrd, A: Allocator> PartialOrd for Vec<T, A> { 3294753dece8SMiguel Ojeda #[inline] 3295753dece8SMiguel Ojeda fn partial_cmp(&self, other: &Self) -> Option<Ordering> { 3296753dece8SMiguel Ojeda PartialOrd::partial_cmp(&**self, &**other) 3297753dece8SMiguel Ojeda } 3298753dece8SMiguel Ojeda } 3299753dece8SMiguel Ojeda 3300753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3301753dece8SMiguel Ojeda impl<T: Eq, A: Allocator> Eq for Vec<T, A> {} 3302753dece8SMiguel Ojeda 3303*89eed1abSMiguel Ojeda /// Implements ordering of vectors, [lexicographically](Ord#lexicographical-comparison). 3304753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3305753dece8SMiguel Ojeda impl<T: Ord, A: Allocator> Ord for Vec<T, A> { 3306753dece8SMiguel Ojeda #[inline] 3307753dece8SMiguel Ojeda fn cmp(&self, other: &Self) -> Ordering { 3308753dece8SMiguel Ojeda Ord::cmp(&**self, &**other) 3309753dece8SMiguel Ojeda } 3310753dece8SMiguel Ojeda } 3311753dece8SMiguel Ojeda 3312753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3313753dece8SMiguel Ojeda unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> { 3314753dece8SMiguel Ojeda fn drop(&mut self) { 3315753dece8SMiguel Ojeda unsafe { 3316753dece8SMiguel Ojeda // use drop for [T] 3317753dece8SMiguel Ojeda // use a raw slice to refer to the elements of the vector as weakest necessary type; 3318753dece8SMiguel Ojeda // could avoid questions of validity in certain cases 3319753dece8SMiguel Ojeda ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len)) 3320753dece8SMiguel Ojeda } 3321753dece8SMiguel Ojeda // RawVec handles deallocation 3322753dece8SMiguel Ojeda } 3323753dece8SMiguel Ojeda } 3324753dece8SMiguel Ojeda 3325753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3326*89eed1abSMiguel Ojeda impl<T> Default for Vec<T> { 3327753dece8SMiguel Ojeda /// Creates an empty `Vec<T>`. 33283ed03f4dSMiguel Ojeda /// 33293ed03f4dSMiguel Ojeda /// The vector will not allocate until elements are pushed onto it. 3330753dece8SMiguel Ojeda fn default() -> Vec<T> { 3331753dece8SMiguel Ojeda Vec::new() 3332753dece8SMiguel Ojeda } 3333753dece8SMiguel Ojeda } 3334753dece8SMiguel Ojeda 3335753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3336753dece8SMiguel Ojeda impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> { 3337753dece8SMiguel Ojeda fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 3338753dece8SMiguel Ojeda fmt::Debug::fmt(&**self, f) 3339753dece8SMiguel Ojeda } 3340753dece8SMiguel Ojeda } 3341753dece8SMiguel Ojeda 3342753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3343753dece8SMiguel Ojeda impl<T, A: Allocator> AsRef<Vec<T, A>> for Vec<T, A> { 3344753dece8SMiguel Ojeda fn as_ref(&self) -> &Vec<T, A> { 3345753dece8SMiguel Ojeda self 3346753dece8SMiguel Ojeda } 3347753dece8SMiguel Ojeda } 3348753dece8SMiguel Ojeda 3349753dece8SMiguel Ojeda #[stable(feature = "vec_as_mut", since = "1.5.0")] 3350753dece8SMiguel Ojeda impl<T, A: Allocator> AsMut<Vec<T, A>> for Vec<T, A> { 3351753dece8SMiguel Ojeda fn as_mut(&mut self) -> &mut Vec<T, A> { 3352753dece8SMiguel Ojeda self 3353753dece8SMiguel Ojeda } 3354753dece8SMiguel Ojeda } 3355753dece8SMiguel Ojeda 3356753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3357753dece8SMiguel Ojeda impl<T, A: Allocator> AsRef<[T]> for Vec<T, A> { 3358753dece8SMiguel Ojeda fn as_ref(&self) -> &[T] { 3359753dece8SMiguel Ojeda self 3360753dece8SMiguel Ojeda } 3361753dece8SMiguel Ojeda } 3362753dece8SMiguel Ojeda 3363753dece8SMiguel Ojeda #[stable(feature = "vec_as_mut", since = "1.5.0")] 3364753dece8SMiguel Ojeda impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> { 3365753dece8SMiguel Ojeda fn as_mut(&mut self) -> &mut [T] { 3366753dece8SMiguel Ojeda self 3367753dece8SMiguel Ojeda } 3368753dece8SMiguel Ojeda } 3369753dece8SMiguel Ojeda 3370753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3371753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3372753dece8SMiguel Ojeda impl<T: Clone> From<&[T]> for Vec<T> { 3373753dece8SMiguel Ojeda /// Allocate a `Vec<T>` and fill it by cloning `s`'s items. 3374753dece8SMiguel Ojeda /// 3375753dece8SMiguel Ojeda /// # Examples 3376753dece8SMiguel Ojeda /// 3377753dece8SMiguel Ojeda /// ``` 3378753dece8SMiguel Ojeda /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]); 3379753dece8SMiguel Ojeda /// ``` 3380753dece8SMiguel Ojeda #[cfg(not(test))] 3381753dece8SMiguel Ojeda fn from(s: &[T]) -> Vec<T> { 3382753dece8SMiguel Ojeda s.to_vec() 3383753dece8SMiguel Ojeda } 3384753dece8SMiguel Ojeda #[cfg(test)] 3385753dece8SMiguel Ojeda fn from(s: &[T]) -> Vec<T> { 3386753dece8SMiguel Ojeda crate::slice::to_vec(s, Global) 3387753dece8SMiguel Ojeda } 3388753dece8SMiguel Ojeda } 3389753dece8SMiguel Ojeda 3390753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3391753dece8SMiguel Ojeda #[stable(feature = "vec_from_mut", since = "1.19.0")] 3392753dece8SMiguel Ojeda impl<T: Clone> From<&mut [T]> for Vec<T> { 3393753dece8SMiguel Ojeda /// Allocate a `Vec<T>` and fill it by cloning `s`'s items. 3394753dece8SMiguel Ojeda /// 3395753dece8SMiguel Ojeda /// # Examples 3396753dece8SMiguel Ojeda /// 3397753dece8SMiguel Ojeda /// ``` 3398753dece8SMiguel Ojeda /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]); 3399753dece8SMiguel Ojeda /// ``` 3400753dece8SMiguel Ojeda #[cfg(not(test))] 3401753dece8SMiguel Ojeda fn from(s: &mut [T]) -> Vec<T> { 3402753dece8SMiguel Ojeda s.to_vec() 3403753dece8SMiguel Ojeda } 3404753dece8SMiguel Ojeda #[cfg(test)] 3405753dece8SMiguel Ojeda fn from(s: &mut [T]) -> Vec<T> { 3406753dece8SMiguel Ojeda crate::slice::to_vec(s, Global) 3407753dece8SMiguel Ojeda } 3408753dece8SMiguel Ojeda } 3409753dece8SMiguel Ojeda 3410753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3411753dece8SMiguel Ojeda #[stable(feature = "vec_from_array", since = "1.44.0")] 3412753dece8SMiguel Ojeda impl<T, const N: usize> From<[T; N]> for Vec<T> { 3413753dece8SMiguel Ojeda /// Allocate a `Vec<T>` and move `s`'s items into it. 3414753dece8SMiguel Ojeda /// 3415753dece8SMiguel Ojeda /// # Examples 3416753dece8SMiguel Ojeda /// 3417753dece8SMiguel Ojeda /// ``` 3418753dece8SMiguel Ojeda /// assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]); 3419753dece8SMiguel Ojeda /// ``` 3420753dece8SMiguel Ojeda #[cfg(not(test))] 3421753dece8SMiguel Ojeda fn from(s: [T; N]) -> Vec<T> { 3422*89eed1abSMiguel Ojeda <[T]>::into_vec(Box::new(s)) 3423753dece8SMiguel Ojeda } 3424753dece8SMiguel Ojeda 3425753dece8SMiguel Ojeda #[cfg(test)] 3426753dece8SMiguel Ojeda fn from(s: [T; N]) -> Vec<T> { 34273ed03f4dSMiguel Ojeda crate::slice::into_vec(Box::new(s)) 3428753dece8SMiguel Ojeda } 3429753dece8SMiguel Ojeda } 3430753dece8SMiguel Ojeda 34318909a80eSMiguel Ojeda #[cfg(not(no_borrow))] 3432753dece8SMiguel Ojeda #[stable(feature = "vec_from_cow_slice", since = "1.14.0")] 3433753dece8SMiguel Ojeda impl<'a, T> From<Cow<'a, [T]>> for Vec<T> 3434753dece8SMiguel Ojeda where 3435753dece8SMiguel Ojeda [T]: ToOwned<Owned = Vec<T>>, 3436753dece8SMiguel Ojeda { 3437753dece8SMiguel Ojeda /// Convert a clone-on-write slice into a vector. 3438753dece8SMiguel Ojeda /// 3439753dece8SMiguel Ojeda /// If `s` already owns a `Vec<T>`, it will be returned directly. 3440753dece8SMiguel Ojeda /// If `s` is borrowing a slice, a new `Vec<T>` will be allocated and 3441753dece8SMiguel Ojeda /// filled by cloning `s`'s items into it. 3442753dece8SMiguel Ojeda /// 3443753dece8SMiguel Ojeda /// # Examples 3444753dece8SMiguel Ojeda /// 3445753dece8SMiguel Ojeda /// ``` 3446753dece8SMiguel Ojeda /// # use std::borrow::Cow; 3447*89eed1abSMiguel Ojeda /// let o: Cow<'_, [i32]> = Cow::Owned(vec![1, 2, 3]); 3448*89eed1abSMiguel Ojeda /// let b: Cow<'_, [i32]> = Cow::Borrowed(&[1, 2, 3]); 3449753dece8SMiguel Ojeda /// assert_eq!(Vec::from(o), Vec::from(b)); 3450753dece8SMiguel Ojeda /// ``` 3451753dece8SMiguel Ojeda fn from(s: Cow<'a, [T]>) -> Vec<T> { 3452753dece8SMiguel Ojeda s.into_owned() 3453753dece8SMiguel Ojeda } 3454753dece8SMiguel Ojeda } 3455753dece8SMiguel Ojeda 34563ed03f4dSMiguel Ojeda // note: test pulls in std, which causes errors here 3457753dece8SMiguel Ojeda #[cfg(not(test))] 3458753dece8SMiguel Ojeda #[stable(feature = "vec_from_box", since = "1.18.0")] 3459753dece8SMiguel Ojeda impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> { 3460753dece8SMiguel Ojeda /// Convert a boxed slice into a vector by transferring ownership of 3461753dece8SMiguel Ojeda /// the existing heap allocation. 3462753dece8SMiguel Ojeda /// 3463753dece8SMiguel Ojeda /// # Examples 3464753dece8SMiguel Ojeda /// 3465753dece8SMiguel Ojeda /// ``` 3466753dece8SMiguel Ojeda /// let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice(); 3467753dece8SMiguel Ojeda /// assert_eq!(Vec::from(b), vec![1, 2, 3]); 3468753dece8SMiguel Ojeda /// ``` 3469753dece8SMiguel Ojeda fn from(s: Box<[T], A>) -> Self { 3470753dece8SMiguel Ojeda s.into_vec() 3471753dece8SMiguel Ojeda } 3472753dece8SMiguel Ojeda } 3473753dece8SMiguel Ojeda 34743ed03f4dSMiguel Ojeda // note: test pulls in std, which causes errors here 3475753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3476753dece8SMiguel Ojeda #[cfg(not(test))] 3477753dece8SMiguel Ojeda #[stable(feature = "box_from_vec", since = "1.20.0")] 3478753dece8SMiguel Ojeda impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> { 3479753dece8SMiguel Ojeda /// Convert a vector into a boxed slice. 3480753dece8SMiguel Ojeda /// 3481753dece8SMiguel Ojeda /// If `v` has excess capacity, its items will be moved into a 3482753dece8SMiguel Ojeda /// newly-allocated buffer with exactly the right capacity. 3483753dece8SMiguel Ojeda /// 3484753dece8SMiguel Ojeda /// # Examples 3485753dece8SMiguel Ojeda /// 3486753dece8SMiguel Ojeda /// ``` 3487753dece8SMiguel Ojeda /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice()); 3488753dece8SMiguel Ojeda /// ``` 34893ed03f4dSMiguel Ojeda /// 34903ed03f4dSMiguel Ojeda /// Any excess capacity is removed: 34913ed03f4dSMiguel Ojeda /// ``` 34923ed03f4dSMiguel Ojeda /// let mut vec = Vec::with_capacity(10); 34933ed03f4dSMiguel Ojeda /// vec.extend([1, 2, 3]); 34943ed03f4dSMiguel Ojeda /// 34953ed03f4dSMiguel Ojeda /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice()); 34963ed03f4dSMiguel Ojeda /// ``` 3497753dece8SMiguel Ojeda fn from(v: Vec<T, A>) -> Self { 3498753dece8SMiguel Ojeda v.into_boxed_slice() 3499753dece8SMiguel Ojeda } 3500753dece8SMiguel Ojeda } 3501753dece8SMiguel Ojeda 3502753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))] 3503753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")] 3504753dece8SMiguel Ojeda impl From<&str> for Vec<u8> { 3505753dece8SMiguel Ojeda /// Allocate a `Vec<u8>` and fill it with a UTF-8 string. 3506753dece8SMiguel Ojeda /// 3507753dece8SMiguel Ojeda /// # Examples 3508753dece8SMiguel Ojeda /// 3509753dece8SMiguel Ojeda /// ``` 3510753dece8SMiguel Ojeda /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']); 3511753dece8SMiguel Ojeda /// ``` 3512753dece8SMiguel Ojeda fn from(s: &str) -> Vec<u8> { 3513753dece8SMiguel Ojeda From::from(s.as_bytes()) 3514753dece8SMiguel Ojeda } 3515753dece8SMiguel Ojeda } 3516753dece8SMiguel Ojeda 3517753dece8SMiguel Ojeda #[stable(feature = "array_try_from_vec", since = "1.48.0")] 3518753dece8SMiguel Ojeda impl<T, A: Allocator, const N: usize> TryFrom<Vec<T, A>> for [T; N] { 3519753dece8SMiguel Ojeda type Error = Vec<T, A>; 3520753dece8SMiguel Ojeda 3521753dece8SMiguel Ojeda /// Gets the entire contents of the `Vec<T>` as an array, 3522753dece8SMiguel Ojeda /// if its size exactly matches that of the requested array. 3523753dece8SMiguel Ojeda /// 3524753dece8SMiguel Ojeda /// # Examples 3525753dece8SMiguel Ojeda /// 3526753dece8SMiguel Ojeda /// ``` 3527753dece8SMiguel Ojeda /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3])); 3528753dece8SMiguel Ojeda /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([])); 3529753dece8SMiguel Ojeda /// ``` 3530753dece8SMiguel Ojeda /// 3531753dece8SMiguel Ojeda /// If the length doesn't match, the input comes back in `Err`: 3532753dece8SMiguel Ojeda /// ``` 3533753dece8SMiguel Ojeda /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into(); 3534753dece8SMiguel Ojeda /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9])); 3535753dece8SMiguel Ojeda /// ``` 3536753dece8SMiguel Ojeda /// 3537753dece8SMiguel Ojeda /// If you're fine with just getting a prefix of the `Vec<T>`, 3538753dece8SMiguel Ojeda /// you can call [`.truncate(N)`](Vec::truncate) first. 3539753dece8SMiguel Ojeda /// ``` 3540753dece8SMiguel Ojeda /// let mut v = String::from("hello world").into_bytes(); 3541753dece8SMiguel Ojeda /// v.sort(); 3542753dece8SMiguel Ojeda /// v.truncate(2); 3543753dece8SMiguel Ojeda /// let [a, b]: [_; 2] = v.try_into().unwrap(); 3544753dece8SMiguel Ojeda /// assert_eq!(a, b' '); 3545753dece8SMiguel Ojeda /// assert_eq!(b, b'd'); 3546753dece8SMiguel Ojeda /// ``` 3547753dece8SMiguel Ojeda fn try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>> { 3548753dece8SMiguel Ojeda if vec.len() != N { 3549753dece8SMiguel Ojeda return Err(vec); 3550753dece8SMiguel Ojeda } 3551753dece8SMiguel Ojeda 3552753dece8SMiguel Ojeda // SAFETY: `.set_len(0)` is always sound. 3553753dece8SMiguel Ojeda unsafe { vec.set_len(0) }; 3554753dece8SMiguel Ojeda 3555753dece8SMiguel Ojeda // SAFETY: A `Vec`'s pointer is always aligned properly, and 3556753dece8SMiguel Ojeda // the alignment the array needs is the same as the items. 3557753dece8SMiguel Ojeda // We checked earlier that we have sufficient items. 3558753dece8SMiguel Ojeda // The items will not double-drop as the `set_len` 3559753dece8SMiguel Ojeda // tells the `Vec` not to also drop them. 3560753dece8SMiguel Ojeda let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) }; 3561753dece8SMiguel Ojeda Ok(array) 3562753dece8SMiguel Ojeda } 3563753dece8SMiguel Ojeda } 3564