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
779b33bb25SMiguel Ojeda #[unstable(feature = "extract_if", reason = "recently added", issue = "43244")]
789b33bb25SMiguel Ojeda pub use self::extract_if::ExtractIf;
79753dece8SMiguel Ojeda
809b33bb25SMiguel Ojeda mod extract_if;
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 ///
219*73596f5aSMiguel Ojeda /// The `Vec` type allows access to 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 ///
38089eed1abSMiguel Ojeda /// [`get`]: slice::get
38189eed1abSMiguel 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]
new() -> Self423753dece8SMiguel 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]
with_capacity(capacity: usize) -> Self481753dece8SMiguel 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")]
try_with_capacity(capacity: usize) -> Result<Self, TryReserveError>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
6219b33bb25SMiguel Ojeda /// use std::alloc::{alloc, Layout};
6223ed03f4dSMiguel Ojeda ///
6233ed03f4dSMiguel Ojeda /// fn main() {
6243ed03f4dSMiguel Ojeda /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
6253ed03f4dSMiguel Ojeda ///
6263ed03f4dSMiguel Ojeda /// let vec = unsafe {
6279b33bb25SMiguel Ojeda /// let mem = alloc(layout).cast::<u32>();
6289b33bb25SMiguel Ojeda /// if mem.is_null() {
6299b33bb25SMiguel Ojeda /// return;
6309b33bb25SMiguel Ojeda /// }
6313ed03f4dSMiguel Ojeda ///
6323ed03f4dSMiguel Ojeda /// mem.write(1_000_000);
6333ed03f4dSMiguel Ojeda ///
6349b33bb25SMiguel Ojeda /// Vec::from_raw_parts(mem, 1, 16)
6353ed03f4dSMiguel Ojeda /// };
6363ed03f4dSMiguel Ojeda ///
6373ed03f4dSMiguel Ojeda /// assert_eq!(vec, &[1_000_000]);
6383ed03f4dSMiguel Ojeda /// assert_eq!(vec.capacity(), 16);
6393ed03f4dSMiguel Ojeda /// }
6403ed03f4dSMiguel Ojeda /// ```
641753dece8SMiguel Ojeda #[inline]
642753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self643753dece8SMiguel Ojeda pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
644753dece8SMiguel Ojeda unsafe { Self::from_raw_parts_in(ptr, length, capacity, Global) }
645753dece8SMiguel Ojeda }
646753dece8SMiguel Ojeda }
647753dece8SMiguel Ojeda
648753dece8SMiguel Ojeda impl<T, A: Allocator> Vec<T, A> {
649753dece8SMiguel Ojeda /// Constructs a new, empty `Vec<T, A>`.
650753dece8SMiguel Ojeda ///
651753dece8SMiguel Ojeda /// The vector will not allocate until elements are pushed onto it.
652753dece8SMiguel Ojeda ///
653753dece8SMiguel Ojeda /// # Examples
654753dece8SMiguel Ojeda ///
655753dece8SMiguel Ojeda /// ```
656753dece8SMiguel Ojeda /// #![feature(allocator_api)]
657753dece8SMiguel Ojeda ///
658753dece8SMiguel Ojeda /// use std::alloc::System;
659753dece8SMiguel Ojeda ///
660753dece8SMiguel Ojeda /// # #[allow(unused_mut)]
661753dece8SMiguel Ojeda /// let mut vec: Vec<i32, _> = Vec::new_in(System);
662753dece8SMiguel Ojeda /// ```
663753dece8SMiguel Ojeda #[inline]
664753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")]
new_in(alloc: A) -> Self665753dece8SMiguel Ojeda pub const fn new_in(alloc: A) -> Self {
666753dece8SMiguel Ojeda Vec { buf: RawVec::new_in(alloc), len: 0 }
667753dece8SMiguel Ojeda }
668753dece8SMiguel Ojeda
6693ed03f4dSMiguel Ojeda /// Constructs a new, empty `Vec<T, A>` with at least the specified capacity
6703ed03f4dSMiguel Ojeda /// with the provided allocator.
671753dece8SMiguel Ojeda ///
6723ed03f4dSMiguel Ojeda /// The vector will be able to hold at least `capacity` elements without
6733ed03f4dSMiguel Ojeda /// reallocating. This method is allowed to allocate for more elements than
6743ed03f4dSMiguel Ojeda /// `capacity`. If `capacity` is 0, the vector will not allocate.
675753dece8SMiguel Ojeda ///
676753dece8SMiguel Ojeda /// It is important to note that although the returned vector has the
6773ed03f4dSMiguel Ojeda /// minimum *capacity* specified, the vector will have a zero *length*. For
6783ed03f4dSMiguel Ojeda /// an explanation of the difference between length and capacity, see
679753dece8SMiguel Ojeda /// *[Capacity and reallocation]*.
680753dece8SMiguel Ojeda ///
6813ed03f4dSMiguel Ojeda /// If it is important to know the exact allocated capacity of a `Vec`,
6823ed03f4dSMiguel Ojeda /// always use the [`capacity`] method after construction.
6833ed03f4dSMiguel Ojeda ///
6843ed03f4dSMiguel Ojeda /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation
6853ed03f4dSMiguel Ojeda /// and the capacity will always be `usize::MAX`.
6863ed03f4dSMiguel Ojeda ///
687753dece8SMiguel Ojeda /// [Capacity and reallocation]: #capacity-and-reallocation
6883ed03f4dSMiguel Ojeda /// [`capacity`]: Vec::capacity
689753dece8SMiguel Ojeda ///
690753dece8SMiguel Ojeda /// # Panics
691753dece8SMiguel Ojeda ///
692753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes.
693753dece8SMiguel Ojeda ///
694753dece8SMiguel Ojeda /// # Examples
695753dece8SMiguel Ojeda ///
696753dece8SMiguel Ojeda /// ```
697753dece8SMiguel Ojeda /// #![feature(allocator_api)]
698753dece8SMiguel Ojeda ///
699753dece8SMiguel Ojeda /// use std::alloc::System;
700753dece8SMiguel Ojeda ///
701753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity_in(10, System);
702753dece8SMiguel Ojeda ///
703753dece8SMiguel Ojeda /// // The vector contains no items, even though it has capacity for more
704753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 0);
70589eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
706753dece8SMiguel Ojeda ///
707753dece8SMiguel Ojeda /// // These are all done without reallocating...
708753dece8SMiguel Ojeda /// for i in 0..10 {
709753dece8SMiguel Ojeda /// vec.push(i);
710753dece8SMiguel Ojeda /// }
711753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 10);
71289eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
713753dece8SMiguel Ojeda ///
714753dece8SMiguel Ojeda /// // ...but this may make the vector reallocate
715753dece8SMiguel Ojeda /// vec.push(11);
716753dece8SMiguel Ojeda /// assert_eq!(vec.len(), 11);
717753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 11);
7183ed03f4dSMiguel Ojeda ///
7193ed03f4dSMiguel Ojeda /// // A vector of a zero-sized type will always over-allocate, since no
7203ed03f4dSMiguel Ojeda /// // allocation is necessary
7213ed03f4dSMiguel Ojeda /// let vec_units = Vec::<(), System>::with_capacity_in(10, System);
7223ed03f4dSMiguel Ojeda /// assert_eq!(vec_units.capacity(), usize::MAX);
723753dece8SMiguel Ojeda /// ```
724753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
725753dece8SMiguel Ojeda #[inline]
726753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")]
with_capacity_in(capacity: usize, alloc: A) -> Self727753dece8SMiguel Ojeda pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
728753dece8SMiguel Ojeda Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 }
729753dece8SMiguel Ojeda }
730753dece8SMiguel Ojeda
7313ed03f4dSMiguel Ojeda /// Tries to construct a new, empty `Vec<T, A>` with at least the specified capacity
732feadd062SMiguel Ojeda /// with the provided allocator.
733feadd062SMiguel Ojeda ///
7343ed03f4dSMiguel Ojeda /// The vector will be able to hold at least `capacity` elements without
7353ed03f4dSMiguel Ojeda /// reallocating. This method is allowed to allocate for more elements than
7363ed03f4dSMiguel Ojeda /// `capacity`. If `capacity` is 0, the vector will not allocate.
737feadd062SMiguel Ojeda ///
738feadd062SMiguel Ojeda /// It is important to note that although the returned vector has the
7393ed03f4dSMiguel Ojeda /// minimum *capacity* specified, the vector will have a zero *length*. For
7403ed03f4dSMiguel Ojeda /// an explanation of the difference between length and capacity, see
741feadd062SMiguel Ojeda /// *[Capacity and reallocation]*.
742feadd062SMiguel Ojeda ///
7433ed03f4dSMiguel Ojeda /// If it is important to know the exact allocated capacity of a `Vec`,
7443ed03f4dSMiguel Ojeda /// always use the [`capacity`] method after construction.
7453ed03f4dSMiguel Ojeda ///
7463ed03f4dSMiguel Ojeda /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation
7473ed03f4dSMiguel Ojeda /// and the capacity will always be `usize::MAX`.
7483ed03f4dSMiguel Ojeda ///
749feadd062SMiguel Ojeda /// [Capacity and reallocation]: #capacity-and-reallocation
7503ed03f4dSMiguel Ojeda /// [`capacity`]: Vec::capacity
751feadd062SMiguel Ojeda ///
752feadd062SMiguel Ojeda /// # Examples
753feadd062SMiguel Ojeda ///
754feadd062SMiguel Ojeda /// ```
755feadd062SMiguel Ojeda /// #![feature(allocator_api)]
756feadd062SMiguel Ojeda ///
757feadd062SMiguel Ojeda /// use std::alloc::System;
758feadd062SMiguel Ojeda ///
759feadd062SMiguel Ojeda /// let mut vec = Vec::try_with_capacity_in(10, System).unwrap();
760feadd062SMiguel Ojeda ///
761feadd062SMiguel Ojeda /// // The vector contains no items, even though it has capacity for more
762feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 0);
76389eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
764feadd062SMiguel Ojeda ///
765feadd062SMiguel Ojeda /// // These are all done without reallocating...
766feadd062SMiguel Ojeda /// for i in 0..10 {
767feadd062SMiguel Ojeda /// vec.push(i);
768feadd062SMiguel Ojeda /// }
769feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 10);
77089eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
771feadd062SMiguel Ojeda ///
772feadd062SMiguel Ojeda /// // ...but this may make the vector reallocate
773feadd062SMiguel Ojeda /// vec.push(11);
774feadd062SMiguel Ojeda /// assert_eq!(vec.len(), 11);
775feadd062SMiguel Ojeda /// assert!(vec.capacity() >= 11);
776feadd062SMiguel Ojeda ///
777feadd062SMiguel Ojeda /// let mut result = Vec::try_with_capacity_in(usize::MAX, System);
778feadd062SMiguel Ojeda /// assert!(result.is_err());
7793ed03f4dSMiguel Ojeda ///
7803ed03f4dSMiguel Ojeda /// // A vector of a zero-sized type will always over-allocate, since no
7813ed03f4dSMiguel Ojeda /// // allocation is necessary
7823ed03f4dSMiguel Ojeda /// let vec_units = Vec::<(), System>::try_with_capacity_in(10, System).unwrap();
7833ed03f4dSMiguel Ojeda /// assert_eq!(vec_units.capacity(), usize::MAX);
784feadd062SMiguel Ojeda /// ```
785feadd062SMiguel Ojeda #[inline]
786feadd062SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")]
try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError>787feadd062SMiguel Ojeda pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {
788feadd062SMiguel Ojeda Ok(Vec { buf: RawVec::try_with_capacity_in(capacity, alloc)?, len: 0 })
789feadd062SMiguel Ojeda }
790feadd062SMiguel Ojeda
7913ed03f4dSMiguel Ojeda /// Creates a `Vec<T, A>` directly from a pointer, a capacity, a length,
7923ed03f4dSMiguel Ojeda /// and an allocator.
793753dece8SMiguel Ojeda ///
794753dece8SMiguel Ojeda /// # Safety
795753dece8SMiguel Ojeda ///
796753dece8SMiguel Ojeda /// This is highly unsafe, due to the number of invariants that aren't
797753dece8SMiguel Ojeda /// checked:
798753dece8SMiguel Ojeda ///
7993ed03f4dSMiguel Ojeda /// * `ptr` must be [*currently allocated*] via the given allocator `alloc`.
8003ed03f4dSMiguel Ojeda /// * `T` needs to have the same alignment as what `ptr` was allocated with.
801753dece8SMiguel Ojeda /// (`T` having a less strict alignment is not sufficient, the alignment really
802753dece8SMiguel Ojeda /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be
803753dece8SMiguel Ojeda /// allocated and deallocated with the same layout.)
8043ed03f4dSMiguel Ojeda /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs
8053ed03f4dSMiguel Ojeda /// to be the same size as the pointer was allocated with. (Because similar to
8063ed03f4dSMiguel Ojeda /// alignment, [`dealloc`] must be called with the same layout `size`.)
807753dece8SMiguel Ojeda /// * `length` needs to be less than or equal to `capacity`.
8083ed03f4dSMiguel Ojeda /// * The first `length` values must be properly initialized values of type `T`.
8093ed03f4dSMiguel Ojeda /// * `capacity` needs to [*fit*] the layout size that the pointer was allocated with.
8103ed03f4dSMiguel Ojeda /// * The allocated size in bytes must be no larger than `isize::MAX`.
8113ed03f4dSMiguel Ojeda /// See the safety documentation of [`pointer::offset`].
8123ed03f4dSMiguel Ojeda ///
8133ed03f4dSMiguel Ojeda /// These requirements are always upheld by any `ptr` that has been allocated
8143ed03f4dSMiguel Ojeda /// via `Vec<T, A>`. Other allocation sources are allowed if the invariants are
8153ed03f4dSMiguel Ojeda /// upheld.
816753dece8SMiguel Ojeda ///
817753dece8SMiguel Ojeda /// Violating these may cause problems like corrupting the allocator's
818753dece8SMiguel Ojeda /// internal data structures. For example it is **not** safe
819753dece8SMiguel Ojeda /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.
820753dece8SMiguel Ojeda /// It's also not safe to build one from a `Vec<u16>` and its length, because
821753dece8SMiguel Ojeda /// the allocator cares about the alignment, and these two types have different
822753dece8SMiguel Ojeda /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
823753dece8SMiguel Ojeda /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.
824753dece8SMiguel Ojeda ///
825753dece8SMiguel Ojeda /// The ownership of `ptr` is effectively transferred to the
826753dece8SMiguel Ojeda /// `Vec<T>` which may then deallocate, reallocate or change the
827753dece8SMiguel Ojeda /// contents of memory pointed to by the pointer at will. Ensure
828753dece8SMiguel Ojeda /// that nothing else uses the pointer after calling this
829753dece8SMiguel Ojeda /// function.
830753dece8SMiguel Ojeda ///
831753dece8SMiguel Ojeda /// [`String`]: crate::string::String
832753dece8SMiguel Ojeda /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
8333ed03f4dSMiguel Ojeda /// [*currently allocated*]: crate::alloc::Allocator#currently-allocated-memory
8343ed03f4dSMiguel Ojeda /// [*fit*]: crate::alloc::Allocator#memory-fitting
835753dece8SMiguel Ojeda ///
836753dece8SMiguel Ojeda /// # Examples
837753dece8SMiguel Ojeda ///
838753dece8SMiguel Ojeda /// ```
839753dece8SMiguel Ojeda /// #![feature(allocator_api)]
840753dece8SMiguel Ojeda ///
841753dece8SMiguel Ojeda /// use std::alloc::System;
842753dece8SMiguel Ojeda ///
843753dece8SMiguel Ojeda /// use std::ptr;
844753dece8SMiguel Ojeda /// use std::mem;
845753dece8SMiguel Ojeda ///
846753dece8SMiguel Ojeda /// let mut v = Vec::with_capacity_in(3, System);
847753dece8SMiguel Ojeda /// v.push(1);
848753dece8SMiguel Ojeda /// v.push(2);
849753dece8SMiguel Ojeda /// v.push(3);
850753dece8SMiguel Ojeda ///
851753dece8SMiguel Ojeda // FIXME Update this when vec_into_raw_parts is stabilized
852753dece8SMiguel Ojeda /// // Prevent running `v`'s destructor so we are in complete control
853753dece8SMiguel Ojeda /// // of the allocation.
854753dece8SMiguel Ojeda /// let mut v = mem::ManuallyDrop::new(v);
855753dece8SMiguel Ojeda ///
856753dece8SMiguel Ojeda /// // Pull out the various important pieces of information about `v`
857753dece8SMiguel Ojeda /// let p = v.as_mut_ptr();
858753dece8SMiguel Ojeda /// let len = v.len();
859753dece8SMiguel Ojeda /// let cap = v.capacity();
860753dece8SMiguel Ojeda /// let alloc = v.allocator();
861753dece8SMiguel Ojeda ///
862753dece8SMiguel Ojeda /// unsafe {
863753dece8SMiguel Ojeda /// // Overwrite memory with 4, 5, 6
8643ed03f4dSMiguel Ojeda /// for i in 0..len {
8653ed03f4dSMiguel Ojeda /// ptr::write(p.add(i), 4 + i);
866753dece8SMiguel Ojeda /// }
867753dece8SMiguel Ojeda ///
868753dece8SMiguel Ojeda /// // Put everything back together into a Vec
869753dece8SMiguel Ojeda /// let rebuilt = Vec::from_raw_parts_in(p, len, cap, alloc.clone());
870753dece8SMiguel Ojeda /// assert_eq!(rebuilt, [4, 5, 6]);
871753dece8SMiguel Ojeda /// }
872753dece8SMiguel Ojeda /// ```
8733ed03f4dSMiguel Ojeda ///
8743ed03f4dSMiguel Ojeda /// Using memory that was allocated elsewhere:
8753ed03f4dSMiguel Ojeda ///
8763ed03f4dSMiguel Ojeda /// ```rust
8779b33bb25SMiguel Ojeda /// #![feature(allocator_api)]
8789b33bb25SMiguel Ojeda ///
8799b33bb25SMiguel Ojeda /// use std::alloc::{AllocError, Allocator, Global, Layout};
8803ed03f4dSMiguel Ojeda ///
8813ed03f4dSMiguel Ojeda /// fn main() {
8823ed03f4dSMiguel Ojeda /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
8839b33bb25SMiguel Ojeda ///
8843ed03f4dSMiguel Ojeda /// let vec = unsafe {
8859b33bb25SMiguel Ojeda /// let mem = match Global.allocate(layout) {
8869b33bb25SMiguel Ojeda /// Ok(mem) => mem.cast::<u32>().as_ptr(),
8879b33bb25SMiguel Ojeda /// Err(AllocError) => return,
8889b33bb25SMiguel Ojeda /// };
8893ed03f4dSMiguel Ojeda ///
8903ed03f4dSMiguel Ojeda /// mem.write(1_000_000);
8913ed03f4dSMiguel Ojeda ///
8929b33bb25SMiguel Ojeda /// Vec::from_raw_parts_in(mem, 1, 16, Global)
8933ed03f4dSMiguel Ojeda /// };
8943ed03f4dSMiguel Ojeda ///
8953ed03f4dSMiguel Ojeda /// assert_eq!(vec, &[1_000_000]);
8963ed03f4dSMiguel Ojeda /// assert_eq!(vec.capacity(), 16);
8973ed03f4dSMiguel Ojeda /// }
8983ed03f4dSMiguel Ojeda /// ```
899753dece8SMiguel Ojeda #[inline]
900753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")]
from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self901753dece8SMiguel Ojeda pub unsafe fn from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self {
902753dece8SMiguel Ojeda unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } }
903753dece8SMiguel Ojeda }
904753dece8SMiguel Ojeda
905753dece8SMiguel Ojeda /// Decomposes a `Vec<T>` into its raw components.
906753dece8SMiguel Ojeda ///
907753dece8SMiguel Ojeda /// Returns the raw pointer to the underlying data, the length of
908753dece8SMiguel Ojeda /// the vector (in elements), and the allocated capacity of the
909753dece8SMiguel Ojeda /// data (in elements). These are the same arguments in the same
910753dece8SMiguel Ojeda /// order as the arguments to [`from_raw_parts`].
911753dece8SMiguel Ojeda ///
912753dece8SMiguel Ojeda /// After calling this function, the caller is responsible for the
913753dece8SMiguel Ojeda /// memory previously managed by the `Vec`. The only way to do
914753dece8SMiguel Ojeda /// this is to convert the raw pointer, length, and capacity back
915753dece8SMiguel Ojeda /// into a `Vec` with the [`from_raw_parts`] function, allowing
916753dece8SMiguel Ojeda /// the destructor to perform the cleanup.
917753dece8SMiguel Ojeda ///
918753dece8SMiguel Ojeda /// [`from_raw_parts`]: Vec::from_raw_parts
919753dece8SMiguel Ojeda ///
920753dece8SMiguel Ojeda /// # Examples
921753dece8SMiguel Ojeda ///
922753dece8SMiguel Ojeda /// ```
923753dece8SMiguel Ojeda /// #![feature(vec_into_raw_parts)]
924753dece8SMiguel Ojeda /// let v: Vec<i32> = vec![-1, 0, 1];
925753dece8SMiguel Ojeda ///
926753dece8SMiguel Ojeda /// let (ptr, len, cap) = v.into_raw_parts();
927753dece8SMiguel Ojeda ///
928753dece8SMiguel Ojeda /// let rebuilt = unsafe {
929753dece8SMiguel Ojeda /// // We can now make changes to the components, such as
930753dece8SMiguel Ojeda /// // transmuting the raw pointer to a compatible type.
931753dece8SMiguel Ojeda /// let ptr = ptr as *mut u32;
932753dece8SMiguel Ojeda ///
933753dece8SMiguel Ojeda /// Vec::from_raw_parts(ptr, len, cap)
934753dece8SMiguel Ojeda /// };
935753dece8SMiguel Ojeda /// assert_eq!(rebuilt, [4294967295, 0, 1]);
936753dece8SMiguel Ojeda /// ```
937753dece8SMiguel Ojeda #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
into_raw_parts(self) -> (*mut T, usize, usize)938753dece8SMiguel Ojeda pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
939753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self);
940753dece8SMiguel Ojeda (me.as_mut_ptr(), me.len(), me.capacity())
941753dece8SMiguel Ojeda }
942753dece8SMiguel Ojeda
943753dece8SMiguel Ojeda /// Decomposes a `Vec<T>` into its raw components.
944753dece8SMiguel Ojeda ///
945753dece8SMiguel Ojeda /// Returns the raw pointer to the underlying data, the length of the vector (in elements),
946753dece8SMiguel Ojeda /// the allocated capacity of the data (in elements), and the allocator. These are the same
947753dece8SMiguel Ojeda /// arguments in the same order as the arguments to [`from_raw_parts_in`].
948753dece8SMiguel Ojeda ///
949753dece8SMiguel Ojeda /// After calling this function, the caller is responsible for the
950753dece8SMiguel Ojeda /// memory previously managed by the `Vec`. The only way to do
951753dece8SMiguel Ojeda /// this is to convert the raw pointer, length, and capacity back
952753dece8SMiguel Ojeda /// into a `Vec` with the [`from_raw_parts_in`] function, allowing
953753dece8SMiguel Ojeda /// the destructor to perform the cleanup.
954753dece8SMiguel Ojeda ///
955753dece8SMiguel Ojeda /// [`from_raw_parts_in`]: Vec::from_raw_parts_in
956753dece8SMiguel Ojeda ///
957753dece8SMiguel Ojeda /// # Examples
958753dece8SMiguel Ojeda ///
959753dece8SMiguel Ojeda /// ```
960753dece8SMiguel Ojeda /// #![feature(allocator_api, vec_into_raw_parts)]
961753dece8SMiguel Ojeda ///
962753dece8SMiguel Ojeda /// use std::alloc::System;
963753dece8SMiguel Ojeda ///
964753dece8SMiguel Ojeda /// let mut v: Vec<i32, System> = Vec::new_in(System);
965753dece8SMiguel Ojeda /// v.push(-1);
966753dece8SMiguel Ojeda /// v.push(0);
967753dece8SMiguel Ojeda /// v.push(1);
968753dece8SMiguel Ojeda ///
969753dece8SMiguel Ojeda /// let (ptr, len, cap, alloc) = v.into_raw_parts_with_alloc();
970753dece8SMiguel Ojeda ///
971753dece8SMiguel Ojeda /// let rebuilt = unsafe {
972753dece8SMiguel Ojeda /// // We can now make changes to the components, such as
973753dece8SMiguel Ojeda /// // transmuting the raw pointer to a compatible type.
974753dece8SMiguel Ojeda /// let ptr = ptr as *mut u32;
975753dece8SMiguel Ojeda ///
976753dece8SMiguel Ojeda /// Vec::from_raw_parts_in(ptr, len, cap, alloc)
977753dece8SMiguel Ojeda /// };
978753dece8SMiguel Ojeda /// assert_eq!(rebuilt, [4294967295, 0, 1]);
979753dece8SMiguel Ojeda /// ```
980753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")]
981753dece8SMiguel Ojeda // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A)982753dece8SMiguel Ojeda pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) {
983753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self);
984753dece8SMiguel Ojeda let len = me.len();
985753dece8SMiguel Ojeda let capacity = me.capacity();
986753dece8SMiguel Ojeda let ptr = me.as_mut_ptr();
987753dece8SMiguel Ojeda let alloc = unsafe { ptr::read(me.allocator()) };
988753dece8SMiguel Ojeda (ptr, len, capacity, alloc)
989753dece8SMiguel Ojeda }
990753dece8SMiguel Ojeda
9913ed03f4dSMiguel Ojeda /// Returns the total number of elements the vector can hold without
992753dece8SMiguel Ojeda /// reallocating.
993753dece8SMiguel Ojeda ///
994753dece8SMiguel Ojeda /// # Examples
995753dece8SMiguel Ojeda ///
996753dece8SMiguel Ojeda /// ```
9973ed03f4dSMiguel Ojeda /// let mut vec: Vec<i32> = Vec::with_capacity(10);
9983ed03f4dSMiguel Ojeda /// vec.push(42);
99989eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
1000753dece8SMiguel Ojeda /// ```
1001753dece8SMiguel Ojeda #[inline]
1002753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
capacity(&self) -> usize1003753dece8SMiguel Ojeda pub fn capacity(&self) -> usize {
1004753dece8SMiguel Ojeda self.buf.capacity()
1005753dece8SMiguel Ojeda }
1006753dece8SMiguel Ojeda
1007753dece8SMiguel Ojeda /// Reserves capacity for at least `additional` more elements to be inserted
10083ed03f4dSMiguel Ojeda /// in the given `Vec<T>`. The collection may reserve more space to
10093ed03f4dSMiguel Ojeda /// speculatively avoid frequent reallocations. After calling `reserve`,
10103ed03f4dSMiguel Ojeda /// capacity will be greater than or equal to `self.len() + additional`.
10113ed03f4dSMiguel Ojeda /// Does nothing if capacity is already sufficient.
1012753dece8SMiguel Ojeda ///
1013753dece8SMiguel Ojeda /// # Panics
1014753dece8SMiguel Ojeda ///
1015753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes.
1016753dece8SMiguel Ojeda ///
1017753dece8SMiguel Ojeda /// # Examples
1018753dece8SMiguel Ojeda ///
1019753dece8SMiguel Ojeda /// ```
1020753dece8SMiguel Ojeda /// let mut vec = vec![1];
1021753dece8SMiguel Ojeda /// vec.reserve(10);
1022753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 11);
1023753dece8SMiguel Ojeda /// ```
1024753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
1025753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
reserve(&mut self, additional: usize)1026753dece8SMiguel Ojeda pub fn reserve(&mut self, additional: usize) {
1027753dece8SMiguel Ojeda self.buf.reserve(self.len, additional);
1028753dece8SMiguel Ojeda }
1029753dece8SMiguel Ojeda
10303ed03f4dSMiguel Ojeda /// Reserves the minimum capacity for at least `additional` more elements to
10313ed03f4dSMiguel Ojeda /// be inserted in the given `Vec<T>`. Unlike [`reserve`], this will not
10323ed03f4dSMiguel Ojeda /// deliberately over-allocate to speculatively avoid frequent allocations.
10333ed03f4dSMiguel Ojeda /// After calling `reserve_exact`, capacity will be greater than or equal to
10343ed03f4dSMiguel Ojeda /// `self.len() + additional`. Does nothing if the capacity is already
10353ed03f4dSMiguel Ojeda /// sufficient.
1036753dece8SMiguel Ojeda ///
1037753dece8SMiguel Ojeda /// Note that the allocator may give the collection more space than it
1038753dece8SMiguel Ojeda /// requests. Therefore, capacity can not be relied upon to be precisely
1039753dece8SMiguel Ojeda /// minimal. Prefer [`reserve`] if future insertions are expected.
1040753dece8SMiguel Ojeda ///
1041753dece8SMiguel Ojeda /// [`reserve`]: Vec::reserve
1042753dece8SMiguel Ojeda ///
1043753dece8SMiguel Ojeda /// # Panics
1044753dece8SMiguel Ojeda ///
1045753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes.
1046753dece8SMiguel Ojeda ///
1047753dece8SMiguel Ojeda /// # Examples
1048753dece8SMiguel Ojeda ///
1049753dece8SMiguel Ojeda /// ```
1050753dece8SMiguel Ojeda /// let mut vec = vec![1];
1051753dece8SMiguel Ojeda /// vec.reserve_exact(10);
1052753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 11);
1053753dece8SMiguel Ojeda /// ```
1054753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
1055753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
reserve_exact(&mut self, additional: usize)1056753dece8SMiguel Ojeda pub fn reserve_exact(&mut self, additional: usize) {
1057753dece8SMiguel Ojeda self.buf.reserve_exact(self.len, additional);
1058753dece8SMiguel Ojeda }
1059753dece8SMiguel Ojeda
1060753dece8SMiguel Ojeda /// Tries to reserve capacity for at least `additional` more elements to be inserted
10613ed03f4dSMiguel Ojeda /// in the given `Vec<T>`. The collection may reserve more space to speculatively avoid
1062753dece8SMiguel Ojeda /// frequent reallocations. After calling `try_reserve`, capacity will be
10633ed03f4dSMiguel Ojeda /// greater than or equal to `self.len() + additional` if it returns
10643ed03f4dSMiguel Ojeda /// `Ok(())`. Does nothing if capacity is already sufficient. This method
10653ed03f4dSMiguel Ojeda /// preserves the contents even if an error occurs.
1066753dece8SMiguel Ojeda ///
1067753dece8SMiguel Ojeda /// # Errors
1068753dece8SMiguel Ojeda ///
1069753dece8SMiguel Ojeda /// If the capacity overflows, or the allocator reports a failure, then an error
1070753dece8SMiguel Ojeda /// is returned.
1071753dece8SMiguel Ojeda ///
1072753dece8SMiguel Ojeda /// # Examples
1073753dece8SMiguel Ojeda ///
1074753dece8SMiguel Ojeda /// ```
1075753dece8SMiguel Ojeda /// use std::collections::TryReserveError;
1076753dece8SMiguel Ojeda ///
1077753dece8SMiguel Ojeda /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1078753dece8SMiguel Ojeda /// let mut output = Vec::new();
1079753dece8SMiguel Ojeda ///
1080753dece8SMiguel Ojeda /// // Pre-reserve the memory, exiting if we can't
1081753dece8SMiguel Ojeda /// output.try_reserve(data.len())?;
1082753dece8SMiguel Ojeda ///
1083753dece8SMiguel Ojeda /// // Now we know this can't OOM in the middle of our complex work
1084753dece8SMiguel Ojeda /// output.extend(data.iter().map(|&val| {
1085753dece8SMiguel Ojeda /// val * 2 + 5 // very complicated
1086753dece8SMiguel Ojeda /// }));
1087753dece8SMiguel Ojeda ///
1088753dece8SMiguel Ojeda /// Ok(output)
1089753dece8SMiguel Ojeda /// }
1090753dece8SMiguel Ojeda /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
1091753dece8SMiguel Ojeda /// ```
1092753dece8SMiguel Ojeda #[stable(feature = "try_reserve", since = "1.57.0")]
try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>1093753dece8SMiguel Ojeda pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
1094753dece8SMiguel Ojeda self.buf.try_reserve(self.len, additional)
1095753dece8SMiguel Ojeda }
1096753dece8SMiguel Ojeda
10973ed03f4dSMiguel Ojeda /// Tries to reserve the minimum capacity for at least `additional`
10983ed03f4dSMiguel Ojeda /// elements to be inserted in the given `Vec<T>`. Unlike [`try_reserve`],
10993ed03f4dSMiguel Ojeda /// this will not deliberately over-allocate to speculatively avoid frequent
11003ed03f4dSMiguel Ojeda /// allocations. After calling `try_reserve_exact`, capacity will be greater
11013ed03f4dSMiguel Ojeda /// than or equal to `self.len() + additional` if it returns `Ok(())`.
1102753dece8SMiguel Ojeda /// Does nothing if the capacity is already sufficient.
1103753dece8SMiguel Ojeda ///
1104753dece8SMiguel Ojeda /// Note that the allocator may give the collection more space than it
1105753dece8SMiguel Ojeda /// requests. Therefore, capacity can not be relied upon to be precisely
1106753dece8SMiguel Ojeda /// minimal. Prefer [`try_reserve`] if future insertions are expected.
1107753dece8SMiguel Ojeda ///
1108753dece8SMiguel Ojeda /// [`try_reserve`]: Vec::try_reserve
1109753dece8SMiguel Ojeda ///
1110753dece8SMiguel Ojeda /// # Errors
1111753dece8SMiguel Ojeda ///
1112753dece8SMiguel Ojeda /// If the capacity overflows, or the allocator reports a failure, then an error
1113753dece8SMiguel Ojeda /// is returned.
1114753dece8SMiguel Ojeda ///
1115753dece8SMiguel Ojeda /// # Examples
1116753dece8SMiguel Ojeda ///
1117753dece8SMiguel Ojeda /// ```
1118753dece8SMiguel Ojeda /// use std::collections::TryReserveError;
1119753dece8SMiguel Ojeda ///
1120753dece8SMiguel Ojeda /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
1121753dece8SMiguel Ojeda /// let mut output = Vec::new();
1122753dece8SMiguel Ojeda ///
1123753dece8SMiguel Ojeda /// // Pre-reserve the memory, exiting if we can't
1124753dece8SMiguel Ojeda /// output.try_reserve_exact(data.len())?;
1125753dece8SMiguel Ojeda ///
1126753dece8SMiguel Ojeda /// // Now we know this can't OOM in the middle of our complex work
1127753dece8SMiguel Ojeda /// output.extend(data.iter().map(|&val| {
1128753dece8SMiguel Ojeda /// val * 2 + 5 // very complicated
1129753dece8SMiguel Ojeda /// }));
1130753dece8SMiguel Ojeda ///
1131753dece8SMiguel Ojeda /// Ok(output)
1132753dece8SMiguel Ojeda /// }
1133753dece8SMiguel Ojeda /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
1134753dece8SMiguel Ojeda /// ```
1135753dece8SMiguel Ojeda #[stable(feature = "try_reserve", since = "1.57.0")]
try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError>1136753dece8SMiguel Ojeda pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
1137753dece8SMiguel Ojeda self.buf.try_reserve_exact(self.len, additional)
1138753dece8SMiguel Ojeda }
1139753dece8SMiguel Ojeda
1140753dece8SMiguel Ojeda /// Shrinks the capacity of the vector as much as possible.
1141753dece8SMiguel Ojeda ///
1142753dece8SMiguel Ojeda /// It will drop down as close as possible to the length but the allocator
1143753dece8SMiguel Ojeda /// may still inform the vector that there is space for a few more elements.
1144753dece8SMiguel Ojeda ///
1145753dece8SMiguel Ojeda /// # Examples
1146753dece8SMiguel Ojeda ///
1147753dece8SMiguel Ojeda /// ```
1148753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(10);
1149753dece8SMiguel Ojeda /// vec.extend([1, 2, 3]);
115089eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
1151753dece8SMiguel Ojeda /// vec.shrink_to_fit();
1152753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 3);
1153753dece8SMiguel Ojeda /// ```
1154753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
1155753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
shrink_to_fit(&mut self)1156753dece8SMiguel Ojeda pub fn shrink_to_fit(&mut self) {
1157753dece8SMiguel Ojeda // The capacity is never less than the length, and there's nothing to do when
1158753dece8SMiguel Ojeda // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit`
1159753dece8SMiguel Ojeda // by only calling it with a greater capacity.
1160753dece8SMiguel Ojeda if self.capacity() > self.len {
1161753dece8SMiguel Ojeda self.buf.shrink_to_fit(self.len);
1162753dece8SMiguel Ojeda }
1163753dece8SMiguel Ojeda }
1164753dece8SMiguel Ojeda
1165753dece8SMiguel Ojeda /// Shrinks the capacity of the vector with a lower bound.
1166753dece8SMiguel Ojeda ///
1167753dece8SMiguel Ojeda /// The capacity will remain at least as large as both the length
1168753dece8SMiguel Ojeda /// and the supplied value.
1169753dece8SMiguel Ojeda ///
1170753dece8SMiguel Ojeda /// If the current capacity is less than the lower limit, this is a no-op.
1171753dece8SMiguel Ojeda ///
1172753dece8SMiguel Ojeda /// # Examples
1173753dece8SMiguel Ojeda ///
1174753dece8SMiguel Ojeda /// ```
1175753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(10);
1176753dece8SMiguel Ojeda /// vec.extend([1, 2, 3]);
117789eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
1178753dece8SMiguel Ojeda /// vec.shrink_to(4);
1179753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 4);
1180753dece8SMiguel Ojeda /// vec.shrink_to(0);
1181753dece8SMiguel Ojeda /// assert!(vec.capacity() >= 3);
1182753dece8SMiguel Ojeda /// ```
1183753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
1184753dece8SMiguel Ojeda #[stable(feature = "shrink_to", since = "1.56.0")]
shrink_to(&mut self, min_capacity: usize)1185753dece8SMiguel Ojeda pub fn shrink_to(&mut self, min_capacity: usize) {
1186753dece8SMiguel Ojeda if self.capacity() > min_capacity {
1187753dece8SMiguel Ojeda self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
1188753dece8SMiguel Ojeda }
1189753dece8SMiguel Ojeda }
1190753dece8SMiguel Ojeda
1191753dece8SMiguel Ojeda /// Converts the vector into [`Box<[T]>`][owned slice].
1192753dece8SMiguel Ojeda ///
11933ed03f4dSMiguel Ojeda /// If the vector has excess capacity, its items will be moved into a
11943ed03f4dSMiguel Ojeda /// newly-allocated buffer with exactly the right capacity.
1195753dece8SMiguel Ojeda ///
1196753dece8SMiguel Ojeda /// [owned slice]: Box
1197753dece8SMiguel Ojeda ///
1198753dece8SMiguel Ojeda /// # Examples
1199753dece8SMiguel Ojeda ///
1200753dece8SMiguel Ojeda /// ```
1201753dece8SMiguel Ojeda /// let v = vec![1, 2, 3];
1202753dece8SMiguel Ojeda ///
1203753dece8SMiguel Ojeda /// let slice = v.into_boxed_slice();
1204753dece8SMiguel Ojeda /// ```
1205753dece8SMiguel Ojeda ///
1206753dece8SMiguel Ojeda /// Any excess capacity is removed:
1207753dece8SMiguel Ojeda ///
1208753dece8SMiguel Ojeda /// ```
1209753dece8SMiguel Ojeda /// let mut vec = Vec::with_capacity(10);
1210753dece8SMiguel Ojeda /// vec.extend([1, 2, 3]);
1211753dece8SMiguel Ojeda ///
121289eed1abSMiguel Ojeda /// assert!(vec.capacity() >= 10);
1213753dece8SMiguel Ojeda /// let slice = vec.into_boxed_slice();
1214753dece8SMiguel Ojeda /// assert_eq!(slice.into_vec().capacity(), 3);
1215753dece8SMiguel Ojeda /// ```
1216753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
1217753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
into_boxed_slice(mut self) -> Box<[T], A>1218753dece8SMiguel Ojeda pub fn into_boxed_slice(mut self) -> Box<[T], A> {
1219753dece8SMiguel Ojeda unsafe {
1220753dece8SMiguel Ojeda self.shrink_to_fit();
1221753dece8SMiguel Ojeda let me = ManuallyDrop::new(self);
1222753dece8SMiguel Ojeda let buf = ptr::read(&me.buf);
1223753dece8SMiguel Ojeda let len = me.len();
1224753dece8SMiguel Ojeda buf.into_box(len).assume_init()
1225753dece8SMiguel Ojeda }
1226753dece8SMiguel Ojeda }
1227753dece8SMiguel Ojeda
1228753dece8SMiguel Ojeda /// Shortens the vector, keeping the first `len` elements and dropping
1229753dece8SMiguel Ojeda /// the rest.
1230753dece8SMiguel Ojeda ///
1231753dece8SMiguel Ojeda /// If `len` is greater than the vector's current length, this has no
1232753dece8SMiguel Ojeda /// effect.
1233753dece8SMiguel Ojeda ///
1234753dece8SMiguel Ojeda /// The [`drain`] method can emulate `truncate`, but causes the excess
1235753dece8SMiguel Ojeda /// elements to be returned instead of dropped.
1236753dece8SMiguel Ojeda ///
1237753dece8SMiguel Ojeda /// Note that this method has no effect on the allocated capacity
1238753dece8SMiguel Ojeda /// of the vector.
1239753dece8SMiguel Ojeda ///
1240753dece8SMiguel Ojeda /// # Examples
1241753dece8SMiguel Ojeda ///
1242753dece8SMiguel Ojeda /// Truncating a five element vector to two elements:
1243753dece8SMiguel Ojeda ///
1244753dece8SMiguel Ojeda /// ```
1245753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4, 5];
1246753dece8SMiguel Ojeda /// vec.truncate(2);
1247753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2]);
1248753dece8SMiguel Ojeda /// ```
1249753dece8SMiguel Ojeda ///
1250753dece8SMiguel Ojeda /// No truncation occurs when `len` is greater than the vector's current
1251753dece8SMiguel Ojeda /// length:
1252753dece8SMiguel Ojeda ///
1253753dece8SMiguel Ojeda /// ```
1254753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3];
1255753dece8SMiguel Ojeda /// vec.truncate(8);
1256753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3]);
1257753dece8SMiguel Ojeda /// ```
1258753dece8SMiguel Ojeda ///
1259753dece8SMiguel Ojeda /// Truncating when `len == 0` is equivalent to calling the [`clear`]
1260753dece8SMiguel Ojeda /// method.
1261753dece8SMiguel Ojeda ///
1262753dece8SMiguel Ojeda /// ```
1263753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3];
1264753dece8SMiguel Ojeda /// vec.truncate(0);
1265753dece8SMiguel Ojeda /// assert_eq!(vec, []);
1266753dece8SMiguel Ojeda /// ```
1267753dece8SMiguel Ojeda ///
1268753dece8SMiguel Ojeda /// [`clear`]: Vec::clear
1269753dece8SMiguel Ojeda /// [`drain`]: Vec::drain
1270753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
truncate(&mut self, len: usize)1271753dece8SMiguel Ojeda pub fn truncate(&mut self, len: usize) {
1272753dece8SMiguel Ojeda // This is safe because:
1273753dece8SMiguel Ojeda //
1274753dece8SMiguel Ojeda // * the slice passed to `drop_in_place` is valid; the `len > self.len`
1275753dece8SMiguel Ojeda // case avoids creating an invalid slice, and
1276753dece8SMiguel Ojeda // * the `len` of the vector is shrunk before calling `drop_in_place`,
1277753dece8SMiguel Ojeda // such that no value will be dropped twice in case `drop_in_place`
1278753dece8SMiguel Ojeda // were to panic once (if it panics twice, the program aborts).
1279753dece8SMiguel Ojeda unsafe {
1280753dece8SMiguel Ojeda // Note: It's intentional that this is `>` and not `>=`.
1281753dece8SMiguel Ojeda // Changing it to `>=` has negative performance
1282753dece8SMiguel Ojeda // implications in some cases. See #78884 for more.
1283753dece8SMiguel Ojeda if len > self.len {
1284753dece8SMiguel Ojeda return;
1285753dece8SMiguel Ojeda }
1286753dece8SMiguel Ojeda let remaining_len = self.len - len;
1287753dece8SMiguel Ojeda let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
1288753dece8SMiguel Ojeda self.len = len;
1289753dece8SMiguel Ojeda ptr::drop_in_place(s);
1290753dece8SMiguel Ojeda }
1291753dece8SMiguel Ojeda }
1292753dece8SMiguel Ojeda
1293753dece8SMiguel Ojeda /// Extracts a slice containing the entire vector.
1294753dece8SMiguel Ojeda ///
1295753dece8SMiguel Ojeda /// Equivalent to `&s[..]`.
1296753dece8SMiguel Ojeda ///
1297753dece8SMiguel Ojeda /// # Examples
1298753dece8SMiguel Ojeda ///
1299753dece8SMiguel Ojeda /// ```
1300753dece8SMiguel Ojeda /// use std::io::{self, Write};
1301753dece8SMiguel Ojeda /// let buffer = vec![1, 2, 3, 5, 8];
1302753dece8SMiguel Ojeda /// io::sink().write(buffer.as_slice()).unwrap();
1303753dece8SMiguel Ojeda /// ```
1304753dece8SMiguel Ojeda #[inline]
1305753dece8SMiguel Ojeda #[stable(feature = "vec_as_slice", since = "1.7.0")]
as_slice(&self) -> &[T]1306753dece8SMiguel Ojeda pub fn as_slice(&self) -> &[T] {
1307753dece8SMiguel Ojeda self
1308753dece8SMiguel Ojeda }
1309753dece8SMiguel Ojeda
1310753dece8SMiguel Ojeda /// Extracts a mutable slice of the entire vector.
1311753dece8SMiguel Ojeda ///
1312753dece8SMiguel Ojeda /// Equivalent to `&mut s[..]`.
1313753dece8SMiguel Ojeda ///
1314753dece8SMiguel Ojeda /// # Examples
1315753dece8SMiguel Ojeda ///
1316753dece8SMiguel Ojeda /// ```
1317753dece8SMiguel Ojeda /// use std::io::{self, Read};
1318753dece8SMiguel Ojeda /// let mut buffer = vec![0; 3];
1319753dece8SMiguel Ojeda /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
1320753dece8SMiguel Ojeda /// ```
1321753dece8SMiguel Ojeda #[inline]
1322753dece8SMiguel Ojeda #[stable(feature = "vec_as_slice", since = "1.7.0")]
as_mut_slice(&mut self) -> &mut [T]1323753dece8SMiguel Ojeda pub fn as_mut_slice(&mut self) -> &mut [T] {
1324753dece8SMiguel Ojeda self
1325753dece8SMiguel Ojeda }
1326753dece8SMiguel Ojeda
13273ed03f4dSMiguel Ojeda /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
13283ed03f4dSMiguel Ojeda /// valid for zero sized reads if the vector didn't allocate.
1329753dece8SMiguel Ojeda ///
1330753dece8SMiguel Ojeda /// The caller must ensure that the vector outlives the pointer this
1331753dece8SMiguel Ojeda /// function returns, or else it will end up pointing to garbage.
1332753dece8SMiguel Ojeda /// Modifying the vector may cause its buffer to be reallocated,
1333753dece8SMiguel Ojeda /// which would also make any pointers to it invalid.
1334753dece8SMiguel Ojeda ///
1335753dece8SMiguel Ojeda /// The caller must also ensure that the memory the pointer (non-transitively) points to
1336753dece8SMiguel Ojeda /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1337753dece8SMiguel Ojeda /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1338753dece8SMiguel Ojeda ///
1339753dece8SMiguel Ojeda /// # Examples
1340753dece8SMiguel Ojeda ///
1341753dece8SMiguel Ojeda /// ```
1342753dece8SMiguel Ojeda /// let x = vec![1, 2, 4];
1343753dece8SMiguel Ojeda /// let x_ptr = x.as_ptr();
1344753dece8SMiguel Ojeda ///
1345753dece8SMiguel Ojeda /// unsafe {
1346753dece8SMiguel Ojeda /// for i in 0..x.len() {
1347753dece8SMiguel Ojeda /// assert_eq!(*x_ptr.add(i), 1 << i);
1348753dece8SMiguel Ojeda /// }
1349753dece8SMiguel Ojeda /// }
1350753dece8SMiguel Ojeda /// ```
1351753dece8SMiguel Ojeda ///
1352753dece8SMiguel Ojeda /// [`as_mut_ptr`]: Vec::as_mut_ptr
1353753dece8SMiguel Ojeda #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1354753dece8SMiguel Ojeda #[inline]
as_ptr(&self) -> *const T1355753dece8SMiguel Ojeda pub fn as_ptr(&self) -> *const T {
1356753dece8SMiguel Ojeda // We shadow the slice method of the same name to avoid going through
1357753dece8SMiguel Ojeda // `deref`, which creates an intermediate reference.
135889eed1abSMiguel Ojeda self.buf.ptr()
1359753dece8SMiguel Ojeda }
1360753dece8SMiguel Ojeda
13613ed03f4dSMiguel Ojeda /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling
13623ed03f4dSMiguel Ojeda /// raw pointer valid for zero sized reads if the vector didn't allocate.
1363753dece8SMiguel Ojeda ///
1364753dece8SMiguel Ojeda /// The caller must ensure that the vector outlives the pointer this
1365753dece8SMiguel Ojeda /// function returns, or else it will end up pointing to garbage.
1366753dece8SMiguel Ojeda /// Modifying the vector may cause its buffer to be reallocated,
1367753dece8SMiguel Ojeda /// which would also make any pointers to it invalid.
1368753dece8SMiguel Ojeda ///
1369753dece8SMiguel Ojeda /// # Examples
1370753dece8SMiguel Ojeda ///
1371753dece8SMiguel Ojeda /// ```
1372753dece8SMiguel Ojeda /// // Allocate vector big enough for 4 elements.
1373753dece8SMiguel Ojeda /// let size = 4;
1374753dece8SMiguel Ojeda /// let mut x: Vec<i32> = Vec::with_capacity(size);
1375753dece8SMiguel Ojeda /// let x_ptr = x.as_mut_ptr();
1376753dece8SMiguel Ojeda ///
1377753dece8SMiguel Ojeda /// // Initialize elements via raw pointer writes, then set length.
1378753dece8SMiguel Ojeda /// unsafe {
1379753dece8SMiguel Ojeda /// for i in 0..size {
1380753dece8SMiguel Ojeda /// *x_ptr.add(i) = i as i32;
1381753dece8SMiguel Ojeda /// }
1382753dece8SMiguel Ojeda /// x.set_len(size);
1383753dece8SMiguel Ojeda /// }
1384753dece8SMiguel Ojeda /// assert_eq!(&*x, &[0, 1, 2, 3]);
1385753dece8SMiguel Ojeda /// ```
1386753dece8SMiguel Ojeda #[stable(feature = "vec_as_ptr", since = "1.37.0")]
1387753dece8SMiguel Ojeda #[inline]
as_mut_ptr(&mut self) -> *mut T1388753dece8SMiguel Ojeda pub fn as_mut_ptr(&mut self) -> *mut T {
1389753dece8SMiguel Ojeda // We shadow the slice method of the same name to avoid going through
1390753dece8SMiguel Ojeda // `deref_mut`, which creates an intermediate reference.
139189eed1abSMiguel Ojeda self.buf.ptr()
1392753dece8SMiguel Ojeda }
1393753dece8SMiguel Ojeda
1394753dece8SMiguel Ojeda /// Returns a reference to the underlying allocator.
1395753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")]
1396753dece8SMiguel Ojeda #[inline]
allocator(&self) -> &A1397753dece8SMiguel Ojeda pub fn allocator(&self) -> &A {
1398753dece8SMiguel Ojeda self.buf.allocator()
1399753dece8SMiguel Ojeda }
1400753dece8SMiguel Ojeda
1401753dece8SMiguel Ojeda /// Forces the length of the vector to `new_len`.
1402753dece8SMiguel Ojeda ///
1403753dece8SMiguel Ojeda /// This is a low-level operation that maintains none of the normal
1404753dece8SMiguel Ojeda /// invariants of the type. Normally changing the length of a vector
1405753dece8SMiguel Ojeda /// is done using one of the safe operations instead, such as
1406753dece8SMiguel Ojeda /// [`truncate`], [`resize`], [`extend`], or [`clear`].
1407753dece8SMiguel Ojeda ///
1408753dece8SMiguel Ojeda /// [`truncate`]: Vec::truncate
1409753dece8SMiguel Ojeda /// [`resize`]: Vec::resize
1410753dece8SMiguel Ojeda /// [`extend`]: Extend::extend
1411753dece8SMiguel Ojeda /// [`clear`]: Vec::clear
1412753dece8SMiguel Ojeda ///
1413753dece8SMiguel Ojeda /// # Safety
1414753dece8SMiguel Ojeda ///
1415753dece8SMiguel Ojeda /// - `new_len` must be less than or equal to [`capacity()`].
1416753dece8SMiguel Ojeda /// - The elements at `old_len..new_len` must be initialized.
1417753dece8SMiguel Ojeda ///
1418753dece8SMiguel Ojeda /// [`capacity()`]: Vec::capacity
1419753dece8SMiguel Ojeda ///
1420753dece8SMiguel Ojeda /// # Examples
1421753dece8SMiguel Ojeda ///
1422753dece8SMiguel Ojeda /// This method can be useful for situations in which the vector
1423753dece8SMiguel Ojeda /// is serving as a buffer for other code, particularly over FFI:
1424753dece8SMiguel Ojeda ///
1425753dece8SMiguel Ojeda /// ```no_run
1426753dece8SMiguel Ojeda /// # #![allow(dead_code)]
1427753dece8SMiguel Ojeda /// # // This is just a minimal skeleton for the doc example;
1428753dece8SMiguel Ojeda /// # // don't use this as a starting point for a real library.
1429753dece8SMiguel Ojeda /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void }
1430753dece8SMiguel Ojeda /// # const Z_OK: i32 = 0;
1431753dece8SMiguel Ojeda /// # extern "C" {
1432753dece8SMiguel Ojeda /// # fn deflateGetDictionary(
1433753dece8SMiguel Ojeda /// # strm: *mut std::ffi::c_void,
1434753dece8SMiguel Ojeda /// # dictionary: *mut u8,
1435753dece8SMiguel Ojeda /// # dictLength: *mut usize,
1436753dece8SMiguel Ojeda /// # ) -> i32;
1437753dece8SMiguel Ojeda /// # }
1438753dece8SMiguel Ojeda /// # impl StreamWrapper {
1439753dece8SMiguel Ojeda /// pub fn get_dictionary(&self) -> Option<Vec<u8>> {
1440753dece8SMiguel Ojeda /// // Per the FFI method's docs, "32768 bytes is always enough".
1441753dece8SMiguel Ojeda /// let mut dict = Vec::with_capacity(32_768);
1442753dece8SMiguel Ojeda /// let mut dict_length = 0;
1443753dece8SMiguel Ojeda /// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
1444753dece8SMiguel Ojeda /// // 1. `dict_length` elements were initialized.
1445753dece8SMiguel Ojeda /// // 2. `dict_length` <= the capacity (32_768)
1446753dece8SMiguel Ojeda /// // which makes `set_len` safe to call.
1447753dece8SMiguel Ojeda /// unsafe {
1448753dece8SMiguel Ojeda /// // Make the FFI call...
1449753dece8SMiguel Ojeda /// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
1450753dece8SMiguel Ojeda /// if r == Z_OK {
1451753dece8SMiguel Ojeda /// // ...and update the length to what was initialized.
1452753dece8SMiguel Ojeda /// dict.set_len(dict_length);
1453753dece8SMiguel Ojeda /// Some(dict)
1454753dece8SMiguel Ojeda /// } else {
1455753dece8SMiguel Ojeda /// None
1456753dece8SMiguel Ojeda /// }
1457753dece8SMiguel Ojeda /// }
1458753dece8SMiguel Ojeda /// }
1459753dece8SMiguel Ojeda /// # }
1460753dece8SMiguel Ojeda /// ```
1461753dece8SMiguel Ojeda ///
1462753dece8SMiguel Ojeda /// While the following example is sound, there is a memory leak since
1463753dece8SMiguel Ojeda /// the inner vectors were not freed prior to the `set_len` call:
1464753dece8SMiguel Ojeda ///
1465753dece8SMiguel Ojeda /// ```
1466753dece8SMiguel Ojeda /// let mut vec = vec![vec![1, 0, 0],
1467753dece8SMiguel Ojeda /// vec![0, 1, 0],
1468753dece8SMiguel Ojeda /// vec![0, 0, 1]];
1469753dece8SMiguel Ojeda /// // SAFETY:
1470753dece8SMiguel Ojeda /// // 1. `old_len..0` is empty so no elements need to be initialized.
1471753dece8SMiguel Ojeda /// // 2. `0 <= capacity` always holds whatever `capacity` is.
1472753dece8SMiguel Ojeda /// unsafe {
1473753dece8SMiguel Ojeda /// vec.set_len(0);
1474753dece8SMiguel Ojeda /// }
1475753dece8SMiguel Ojeda /// ```
1476753dece8SMiguel Ojeda ///
1477753dece8SMiguel Ojeda /// Normally, here, one would use [`clear`] instead to correctly drop
1478753dece8SMiguel Ojeda /// the contents and thus not leak memory.
1479753dece8SMiguel Ojeda #[inline]
1480753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
set_len(&mut self, new_len: usize)1481753dece8SMiguel Ojeda pub unsafe fn set_len(&mut self, new_len: usize) {
1482753dece8SMiguel Ojeda debug_assert!(new_len <= self.capacity());
1483753dece8SMiguel Ojeda
1484753dece8SMiguel Ojeda self.len = new_len;
1485753dece8SMiguel Ojeda }
1486753dece8SMiguel Ojeda
1487753dece8SMiguel Ojeda /// Removes an element from the vector and returns it.
1488753dece8SMiguel Ojeda ///
1489753dece8SMiguel Ojeda /// The removed element is replaced by the last element of the vector.
1490753dece8SMiguel Ojeda ///
1491753dece8SMiguel Ojeda /// This does not preserve ordering, but is *O*(1).
1492753dece8SMiguel Ojeda /// If you need to preserve the element order, use [`remove`] instead.
1493753dece8SMiguel Ojeda ///
1494753dece8SMiguel Ojeda /// [`remove`]: Vec::remove
1495753dece8SMiguel Ojeda ///
1496753dece8SMiguel Ojeda /// # Panics
1497753dece8SMiguel Ojeda ///
1498753dece8SMiguel Ojeda /// Panics if `index` is out of bounds.
1499753dece8SMiguel Ojeda ///
1500753dece8SMiguel Ojeda /// # Examples
1501753dece8SMiguel Ojeda ///
1502753dece8SMiguel Ojeda /// ```
1503753dece8SMiguel Ojeda /// let mut v = vec!["foo", "bar", "baz", "qux"];
1504753dece8SMiguel Ojeda ///
1505753dece8SMiguel Ojeda /// assert_eq!(v.swap_remove(1), "bar");
1506753dece8SMiguel Ojeda /// assert_eq!(v, ["foo", "qux", "baz"]);
1507753dece8SMiguel Ojeda ///
1508753dece8SMiguel Ojeda /// assert_eq!(v.swap_remove(0), "foo");
1509753dece8SMiguel Ojeda /// assert_eq!(v, ["baz", "qux"]);
1510753dece8SMiguel Ojeda /// ```
1511753dece8SMiguel Ojeda #[inline]
1512753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
swap_remove(&mut self, index: usize) -> T1513753dece8SMiguel Ojeda pub fn swap_remove(&mut self, index: usize) -> T {
1514753dece8SMiguel Ojeda #[cold]
1515753dece8SMiguel Ojeda #[inline(never)]
1516753dece8SMiguel Ojeda fn assert_failed(index: usize, len: usize) -> ! {
1517753dece8SMiguel Ojeda panic!("swap_remove index (is {index}) should be < len (is {len})");
1518753dece8SMiguel Ojeda }
1519753dece8SMiguel Ojeda
1520753dece8SMiguel Ojeda let len = self.len();
1521753dece8SMiguel Ojeda if index >= len {
1522753dece8SMiguel Ojeda assert_failed(index, len);
1523753dece8SMiguel Ojeda }
1524753dece8SMiguel Ojeda unsafe {
1525753dece8SMiguel Ojeda // We replace self[index] with the last element. Note that if the
1526753dece8SMiguel Ojeda // bounds check above succeeds there must be a last element (which
1527753dece8SMiguel Ojeda // can be self[index] itself).
1528753dece8SMiguel Ojeda let value = ptr::read(self.as_ptr().add(index));
1529753dece8SMiguel Ojeda let base_ptr = self.as_mut_ptr();
1530753dece8SMiguel Ojeda ptr::copy(base_ptr.add(len - 1), base_ptr.add(index), 1);
1531753dece8SMiguel Ojeda self.set_len(len - 1);
1532753dece8SMiguel Ojeda value
1533753dece8SMiguel Ojeda }
1534753dece8SMiguel Ojeda }
1535753dece8SMiguel Ojeda
1536753dece8SMiguel Ojeda /// Inserts an element at position `index` within the vector, shifting all
1537753dece8SMiguel Ojeda /// elements after it to the right.
1538753dece8SMiguel Ojeda ///
1539753dece8SMiguel Ojeda /// # Panics
1540753dece8SMiguel Ojeda ///
1541753dece8SMiguel Ojeda /// Panics if `index > len`.
1542753dece8SMiguel Ojeda ///
1543753dece8SMiguel Ojeda /// # Examples
1544753dece8SMiguel Ojeda ///
1545753dece8SMiguel Ojeda /// ```
1546753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3];
1547753dece8SMiguel Ojeda /// vec.insert(1, 4);
1548753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 4, 2, 3]);
1549753dece8SMiguel Ojeda /// vec.insert(4, 5);
1550753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 4, 2, 3, 5]);
1551753dece8SMiguel Ojeda /// ```
1552753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
1553753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
insert(&mut self, index: usize, element: T)1554753dece8SMiguel Ojeda pub fn insert(&mut self, index: usize, element: T) {
1555753dece8SMiguel Ojeda #[cold]
1556753dece8SMiguel Ojeda #[inline(never)]
1557753dece8SMiguel Ojeda fn assert_failed(index: usize, len: usize) -> ! {
1558753dece8SMiguel Ojeda panic!("insertion index (is {index}) should be <= len (is {len})");
1559753dece8SMiguel Ojeda }
1560753dece8SMiguel Ojeda
1561753dece8SMiguel Ojeda let len = self.len();
1562753dece8SMiguel Ojeda
1563753dece8SMiguel Ojeda // space for the new element
1564753dece8SMiguel Ojeda if len == self.buf.capacity() {
1565753dece8SMiguel Ojeda self.reserve(1);
1566753dece8SMiguel Ojeda }
1567753dece8SMiguel Ojeda
1568753dece8SMiguel Ojeda unsafe {
1569753dece8SMiguel Ojeda // infallible
1570753dece8SMiguel Ojeda // The spot to put the new value
1571753dece8SMiguel Ojeda {
1572753dece8SMiguel Ojeda let p = self.as_mut_ptr().add(index);
15733ed03f4dSMiguel Ojeda if index < len {
1574753dece8SMiguel Ojeda // Shift everything over to make space. (Duplicating the
1575753dece8SMiguel Ojeda // `index`th element into two consecutive places.)
15763ed03f4dSMiguel Ojeda ptr::copy(p, p.add(1), len - index);
15773ed03f4dSMiguel Ojeda } else if index == len {
15783ed03f4dSMiguel Ojeda // No elements need shifting.
15793ed03f4dSMiguel Ojeda } else {
15803ed03f4dSMiguel Ojeda assert_failed(index, len);
15813ed03f4dSMiguel Ojeda }
1582753dece8SMiguel Ojeda // Write it in, overwriting the first copy of the `index`th
1583753dece8SMiguel Ojeda // element.
1584753dece8SMiguel Ojeda ptr::write(p, element);
1585753dece8SMiguel Ojeda }
1586753dece8SMiguel Ojeda self.set_len(len + 1);
1587753dece8SMiguel Ojeda }
1588753dece8SMiguel Ojeda }
1589753dece8SMiguel Ojeda
1590753dece8SMiguel Ojeda /// Removes and returns the element at position `index` within the vector,
1591753dece8SMiguel Ojeda /// shifting all elements after it to the left.
1592753dece8SMiguel Ojeda ///
1593753dece8SMiguel Ojeda /// Note: Because this shifts over the remaining elements, it has a
1594753dece8SMiguel Ojeda /// worst-case performance of *O*(*n*). If you don't need the order of elements
1595753dece8SMiguel Ojeda /// to be preserved, use [`swap_remove`] instead. If you'd like to remove
1596753dece8SMiguel Ojeda /// elements from the beginning of the `Vec`, consider using
1597753dece8SMiguel Ojeda /// [`VecDeque::pop_front`] instead.
1598753dece8SMiguel Ojeda ///
1599753dece8SMiguel Ojeda /// [`swap_remove`]: Vec::swap_remove
1600753dece8SMiguel Ojeda /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
1601753dece8SMiguel Ojeda ///
1602753dece8SMiguel Ojeda /// # Panics
1603753dece8SMiguel Ojeda ///
1604753dece8SMiguel Ojeda /// Panics if `index` is out of bounds.
1605753dece8SMiguel Ojeda ///
1606753dece8SMiguel Ojeda /// # Examples
1607753dece8SMiguel Ojeda ///
1608753dece8SMiguel Ojeda /// ```
1609753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3];
1610753dece8SMiguel Ojeda /// assert_eq!(v.remove(1), 2);
1611753dece8SMiguel Ojeda /// assert_eq!(v, [1, 3]);
1612753dece8SMiguel Ojeda /// ```
1613753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
1614753dece8SMiguel Ojeda #[track_caller]
remove(&mut self, index: usize) -> T1615753dece8SMiguel Ojeda pub fn remove(&mut self, index: usize) -> T {
1616753dece8SMiguel Ojeda #[cold]
1617753dece8SMiguel Ojeda #[inline(never)]
1618753dece8SMiguel Ojeda #[track_caller]
1619753dece8SMiguel Ojeda fn assert_failed(index: usize, len: usize) -> ! {
1620753dece8SMiguel Ojeda panic!("removal index (is {index}) should be < len (is {len})");
1621753dece8SMiguel Ojeda }
1622753dece8SMiguel Ojeda
1623753dece8SMiguel Ojeda let len = self.len();
1624753dece8SMiguel Ojeda if index >= len {
1625753dece8SMiguel Ojeda assert_failed(index, len);
1626753dece8SMiguel Ojeda }
1627753dece8SMiguel Ojeda unsafe {
1628753dece8SMiguel Ojeda // infallible
1629753dece8SMiguel Ojeda let ret;
1630753dece8SMiguel Ojeda {
1631753dece8SMiguel Ojeda // the place we are taking from.
1632753dece8SMiguel Ojeda let ptr = self.as_mut_ptr().add(index);
1633753dece8SMiguel Ojeda // copy it out, unsafely having a copy of the value on
1634753dece8SMiguel Ojeda // the stack and in the vector at the same time.
1635753dece8SMiguel Ojeda ret = ptr::read(ptr);
1636753dece8SMiguel Ojeda
1637753dece8SMiguel Ojeda // Shift everything down to fill in that spot.
16383ed03f4dSMiguel Ojeda ptr::copy(ptr.add(1), ptr, len - index - 1);
1639753dece8SMiguel Ojeda }
1640753dece8SMiguel Ojeda self.set_len(len - 1);
1641753dece8SMiguel Ojeda ret
1642753dece8SMiguel Ojeda }
1643753dece8SMiguel Ojeda }
1644753dece8SMiguel Ojeda
1645753dece8SMiguel Ojeda /// Retains only the elements specified by the predicate.
1646753dece8SMiguel Ojeda ///
1647753dece8SMiguel Ojeda /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
1648753dece8SMiguel Ojeda /// This method operates in place, visiting each element exactly once in the
1649753dece8SMiguel Ojeda /// original order, and preserves the order of the retained elements.
1650753dece8SMiguel Ojeda ///
1651753dece8SMiguel Ojeda /// # Examples
1652753dece8SMiguel Ojeda ///
1653753dece8SMiguel Ojeda /// ```
1654753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4];
1655753dece8SMiguel Ojeda /// vec.retain(|&x| x % 2 == 0);
1656753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 4]);
1657753dece8SMiguel Ojeda /// ```
1658753dece8SMiguel Ojeda ///
1659753dece8SMiguel Ojeda /// Because the elements are visited exactly once in the original order,
1660753dece8SMiguel Ojeda /// external state may be used to decide which elements to keep.
1661753dece8SMiguel Ojeda ///
1662753dece8SMiguel Ojeda /// ```
1663753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4, 5];
1664753dece8SMiguel Ojeda /// let keep = [false, true, true, false, true];
1665753dece8SMiguel Ojeda /// let mut iter = keep.iter();
1666753dece8SMiguel Ojeda /// vec.retain(|_| *iter.next().unwrap());
1667753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 3, 5]);
1668753dece8SMiguel Ojeda /// ```
1669753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool,1670753dece8SMiguel Ojeda pub fn retain<F>(&mut self, mut f: F)
1671753dece8SMiguel Ojeda where
1672753dece8SMiguel Ojeda F: FnMut(&T) -> bool,
1673753dece8SMiguel Ojeda {
1674753dece8SMiguel Ojeda self.retain_mut(|elem| f(elem));
1675753dece8SMiguel Ojeda }
1676753dece8SMiguel Ojeda
1677753dece8SMiguel Ojeda /// Retains only the elements specified by the predicate, passing a mutable reference to it.
1678753dece8SMiguel Ojeda ///
1679753dece8SMiguel Ojeda /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
1680753dece8SMiguel Ojeda /// This method operates in place, visiting each element exactly once in the
1681753dece8SMiguel Ojeda /// original order, and preserves the order of the retained elements.
1682753dece8SMiguel Ojeda ///
1683753dece8SMiguel Ojeda /// # Examples
1684753dece8SMiguel Ojeda ///
1685753dece8SMiguel Ojeda /// ```
1686753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4];
16873ed03f4dSMiguel Ojeda /// vec.retain_mut(|x| if *x <= 3 {
1688753dece8SMiguel Ojeda /// *x += 1;
1689753dece8SMiguel Ojeda /// true
16903ed03f4dSMiguel Ojeda /// } else {
16913ed03f4dSMiguel Ojeda /// false
1692753dece8SMiguel Ojeda /// });
1693753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 3, 4]);
1694753dece8SMiguel Ojeda /// ```
1695753dece8SMiguel Ojeda #[stable(feature = "vec_retain_mut", since = "1.61.0")]
retain_mut<F>(&mut self, mut f: F) where F: FnMut(&mut T) -> bool,1696753dece8SMiguel Ojeda pub fn retain_mut<F>(&mut self, mut f: F)
1697753dece8SMiguel Ojeda where
1698753dece8SMiguel Ojeda F: FnMut(&mut T) -> bool,
1699753dece8SMiguel Ojeda {
1700753dece8SMiguel Ojeda let original_len = self.len();
1701753dece8SMiguel Ojeda // Avoid double drop if the drop guard is not executed,
1702753dece8SMiguel Ojeda // since we may make some holes during the process.
1703753dece8SMiguel Ojeda unsafe { self.set_len(0) };
1704753dece8SMiguel Ojeda
1705753dece8SMiguel Ojeda // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
1706753dece8SMiguel Ojeda // |<- processed len ->| ^- next to check
1707753dece8SMiguel Ojeda // |<- deleted cnt ->|
1708753dece8SMiguel Ojeda // |<- original_len ->|
1709753dece8SMiguel Ojeda // Kept: Elements which predicate returns true on.
1710753dece8SMiguel Ojeda // Hole: Moved or dropped element slot.
1711753dece8SMiguel Ojeda // Unchecked: Unchecked valid elements.
1712753dece8SMiguel Ojeda //
1713753dece8SMiguel Ojeda // This drop guard will be invoked when predicate or `drop` of element panicked.
1714753dece8SMiguel Ojeda // It shifts unchecked elements to cover holes and `set_len` to the correct length.
1715753dece8SMiguel Ojeda // In cases when predicate and `drop` never panick, it will be optimized out.
1716753dece8SMiguel Ojeda struct BackshiftOnDrop<'a, T, A: Allocator> {
1717753dece8SMiguel Ojeda v: &'a mut Vec<T, A>,
1718753dece8SMiguel Ojeda processed_len: usize,
1719753dece8SMiguel Ojeda deleted_cnt: usize,
1720753dece8SMiguel Ojeda original_len: usize,
1721753dece8SMiguel Ojeda }
1722753dece8SMiguel Ojeda
1723753dece8SMiguel Ojeda impl<T, A: Allocator> Drop for BackshiftOnDrop<'_, T, A> {
1724753dece8SMiguel Ojeda fn drop(&mut self) {
1725753dece8SMiguel Ojeda if self.deleted_cnt > 0 {
1726753dece8SMiguel Ojeda // SAFETY: Trailing unchecked items must be valid since we never touch them.
1727753dece8SMiguel Ojeda unsafe {
1728753dece8SMiguel Ojeda ptr::copy(
1729753dece8SMiguel Ojeda self.v.as_ptr().add(self.processed_len),
1730753dece8SMiguel Ojeda self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
1731753dece8SMiguel Ojeda self.original_len - self.processed_len,
1732753dece8SMiguel Ojeda );
1733753dece8SMiguel Ojeda }
1734753dece8SMiguel Ojeda }
1735753dece8SMiguel Ojeda // SAFETY: After filling holes, all items are in contiguous memory.
1736753dece8SMiguel Ojeda unsafe {
1737753dece8SMiguel Ojeda self.v.set_len(self.original_len - self.deleted_cnt);
1738753dece8SMiguel Ojeda }
1739753dece8SMiguel Ojeda }
1740753dece8SMiguel Ojeda }
1741753dece8SMiguel Ojeda
1742753dece8SMiguel Ojeda let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };
1743753dece8SMiguel Ojeda
1744753dece8SMiguel Ojeda fn process_loop<F, T, A: Allocator, const DELETED: bool>(
1745753dece8SMiguel Ojeda original_len: usize,
1746753dece8SMiguel Ojeda f: &mut F,
1747753dece8SMiguel Ojeda g: &mut BackshiftOnDrop<'_, T, A>,
1748753dece8SMiguel Ojeda ) where
1749753dece8SMiguel Ojeda F: FnMut(&mut T) -> bool,
1750753dece8SMiguel Ojeda {
1751753dece8SMiguel Ojeda while g.processed_len != original_len {
1752753dece8SMiguel Ojeda // SAFETY: Unchecked element must be valid.
1753753dece8SMiguel Ojeda let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) };
1754753dece8SMiguel Ojeda if !f(cur) {
1755753dece8SMiguel Ojeda // Advance early to avoid double drop if `drop_in_place` panicked.
1756753dece8SMiguel Ojeda g.processed_len += 1;
1757753dece8SMiguel Ojeda g.deleted_cnt += 1;
1758753dece8SMiguel Ojeda // SAFETY: We never touch this element again after dropped.
1759753dece8SMiguel Ojeda unsafe { ptr::drop_in_place(cur) };
1760753dece8SMiguel Ojeda // We already advanced the counter.
1761753dece8SMiguel Ojeda if DELETED {
1762753dece8SMiguel Ojeda continue;
1763753dece8SMiguel Ojeda } else {
1764753dece8SMiguel Ojeda break;
1765753dece8SMiguel Ojeda }
1766753dece8SMiguel Ojeda }
1767753dece8SMiguel Ojeda if DELETED {
1768753dece8SMiguel Ojeda // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
1769753dece8SMiguel Ojeda // We use copy for move, and never touch this element again.
1770753dece8SMiguel Ojeda unsafe {
1771753dece8SMiguel Ojeda let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
1772753dece8SMiguel Ojeda ptr::copy_nonoverlapping(cur, hole_slot, 1);
1773753dece8SMiguel Ojeda }
1774753dece8SMiguel Ojeda }
1775753dece8SMiguel Ojeda g.processed_len += 1;
1776753dece8SMiguel Ojeda }
1777753dece8SMiguel Ojeda }
1778753dece8SMiguel Ojeda
1779753dece8SMiguel Ojeda // Stage 1: Nothing was deleted.
1780753dece8SMiguel Ojeda process_loop::<F, T, A, false>(original_len, &mut f, &mut g);
1781753dece8SMiguel Ojeda
1782753dece8SMiguel Ojeda // Stage 2: Some elements were deleted.
1783753dece8SMiguel Ojeda process_loop::<F, T, A, true>(original_len, &mut f, &mut g);
1784753dece8SMiguel Ojeda
1785753dece8SMiguel Ojeda // All item are processed. This can be optimized to `set_len` by LLVM.
1786753dece8SMiguel Ojeda drop(g);
1787753dece8SMiguel Ojeda }
1788753dece8SMiguel Ojeda
1789753dece8SMiguel Ojeda /// Removes all but the first of consecutive elements in the vector that resolve to the same
1790753dece8SMiguel Ojeda /// key.
1791753dece8SMiguel Ojeda ///
1792753dece8SMiguel Ojeda /// If the vector is sorted, this removes all duplicates.
1793753dece8SMiguel Ojeda ///
1794753dece8SMiguel Ojeda /// # Examples
1795753dece8SMiguel Ojeda ///
1796753dece8SMiguel Ojeda /// ```
1797753dece8SMiguel Ojeda /// let mut vec = vec![10, 20, 21, 30, 20];
1798753dece8SMiguel Ojeda ///
1799753dece8SMiguel Ojeda /// vec.dedup_by_key(|i| *i / 10);
1800753dece8SMiguel Ojeda ///
1801753dece8SMiguel Ojeda /// assert_eq!(vec, [10, 20, 30, 20]);
1802753dece8SMiguel Ojeda /// ```
1803753dece8SMiguel Ojeda #[stable(feature = "dedup_by", since = "1.16.0")]
1804753dece8SMiguel Ojeda #[inline]
dedup_by_key<F, K>(&mut self, mut key: F) where F: FnMut(&mut T) -> K, K: PartialEq,1805753dece8SMiguel Ojeda pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1806753dece8SMiguel Ojeda where
1807753dece8SMiguel Ojeda F: FnMut(&mut T) -> K,
1808753dece8SMiguel Ojeda K: PartialEq,
1809753dece8SMiguel Ojeda {
1810753dece8SMiguel Ojeda self.dedup_by(|a, b| key(a) == key(b))
1811753dece8SMiguel Ojeda }
1812753dece8SMiguel Ojeda
1813753dece8SMiguel Ojeda /// Removes all but the first of consecutive elements in the vector satisfying a given equality
1814753dece8SMiguel Ojeda /// relation.
1815753dece8SMiguel Ojeda ///
1816753dece8SMiguel Ojeda /// The `same_bucket` function is passed references to two elements from the vector and
1817753dece8SMiguel Ojeda /// must determine if the elements compare equal. The elements are passed in opposite order
1818753dece8SMiguel Ojeda /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
1819753dece8SMiguel Ojeda ///
1820753dece8SMiguel Ojeda /// If the vector is sorted, this removes all duplicates.
1821753dece8SMiguel Ojeda ///
1822753dece8SMiguel Ojeda /// # Examples
1823753dece8SMiguel Ojeda ///
1824753dece8SMiguel Ojeda /// ```
1825753dece8SMiguel Ojeda /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
1826753dece8SMiguel Ojeda ///
1827753dece8SMiguel Ojeda /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
1828753dece8SMiguel Ojeda ///
1829753dece8SMiguel Ojeda /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
1830753dece8SMiguel Ojeda /// ```
1831753dece8SMiguel Ojeda #[stable(feature = "dedup_by", since = "1.16.0")]
dedup_by<F>(&mut self, mut same_bucket: F) where F: FnMut(&mut T, &mut T) -> bool,1832753dece8SMiguel Ojeda pub fn dedup_by<F>(&mut self, mut same_bucket: F)
1833753dece8SMiguel Ojeda where
1834753dece8SMiguel Ojeda F: FnMut(&mut T, &mut T) -> bool,
1835753dece8SMiguel Ojeda {
1836753dece8SMiguel Ojeda let len = self.len();
1837753dece8SMiguel Ojeda if len <= 1 {
1838753dece8SMiguel Ojeda return;
1839753dece8SMiguel Ojeda }
1840753dece8SMiguel Ojeda
1841753dece8SMiguel Ojeda /* INVARIANT: vec.len() > read >= write > write-1 >= 0 */
1842753dece8SMiguel Ojeda struct FillGapOnDrop<'a, T, A: core::alloc::Allocator> {
1843753dece8SMiguel Ojeda /* Offset of the element we want to check if it is duplicate */
1844753dece8SMiguel Ojeda read: usize,
1845753dece8SMiguel Ojeda
1846753dece8SMiguel Ojeda /* Offset of the place where we want to place the non-duplicate
1847753dece8SMiguel Ojeda * when we find it. */
1848753dece8SMiguel Ojeda write: usize,
1849753dece8SMiguel Ojeda
1850753dece8SMiguel Ojeda /* The Vec that would need correction if `same_bucket` panicked */
1851753dece8SMiguel Ojeda vec: &'a mut Vec<T, A>,
1852753dece8SMiguel Ojeda }
1853753dece8SMiguel Ojeda
1854753dece8SMiguel Ojeda impl<'a, T, A: core::alloc::Allocator> Drop for FillGapOnDrop<'a, T, A> {
1855753dece8SMiguel Ojeda fn drop(&mut self) {
1856753dece8SMiguel Ojeda /* This code gets executed when `same_bucket` panics */
1857753dece8SMiguel Ojeda
1858753dece8SMiguel Ojeda /* SAFETY: invariant guarantees that `read - write`
1859753dece8SMiguel Ojeda * and `len - read` never overflow and that the copy is always
1860753dece8SMiguel Ojeda * in-bounds. */
1861753dece8SMiguel Ojeda unsafe {
1862753dece8SMiguel Ojeda let ptr = self.vec.as_mut_ptr();
1863753dece8SMiguel Ojeda let len = self.vec.len();
1864753dece8SMiguel Ojeda
1865753dece8SMiguel Ojeda /* How many items were left when `same_bucket` panicked.
1866753dece8SMiguel Ojeda * Basically vec[read..].len() */
1867753dece8SMiguel Ojeda let items_left = len.wrapping_sub(self.read);
1868753dece8SMiguel Ojeda
1869753dece8SMiguel Ojeda /* Pointer to first item in vec[write..write+items_left] slice */
1870753dece8SMiguel Ojeda let dropped_ptr = ptr.add(self.write);
1871753dece8SMiguel Ojeda /* Pointer to first item in vec[read..] slice */
1872753dece8SMiguel Ojeda let valid_ptr = ptr.add(self.read);
1873753dece8SMiguel Ojeda
1874753dece8SMiguel Ojeda /* Copy `vec[read..]` to `vec[write..write+items_left]`.
1875753dece8SMiguel Ojeda * The slices can overlap, so `copy_nonoverlapping` cannot be used */
1876753dece8SMiguel Ojeda ptr::copy(valid_ptr, dropped_ptr, items_left);
1877753dece8SMiguel Ojeda
1878753dece8SMiguel Ojeda /* How many items have been already dropped
1879753dece8SMiguel Ojeda * Basically vec[read..write].len() */
1880753dece8SMiguel Ojeda let dropped = self.read.wrapping_sub(self.write);
1881753dece8SMiguel Ojeda
1882753dece8SMiguel Ojeda self.vec.set_len(len - dropped);
1883753dece8SMiguel Ojeda }
1884753dece8SMiguel Ojeda }
1885753dece8SMiguel Ojeda }
1886753dece8SMiguel Ojeda
1887753dece8SMiguel Ojeda let mut gap = FillGapOnDrop { read: 1, write: 1, vec: self };
1888753dece8SMiguel Ojeda let ptr = gap.vec.as_mut_ptr();
1889753dece8SMiguel Ojeda
1890753dece8SMiguel Ojeda /* Drop items while going through Vec, it should be more efficient than
1891753dece8SMiguel Ojeda * doing slice partition_dedup + truncate */
1892753dece8SMiguel Ojeda
1893753dece8SMiguel Ojeda /* SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr
1894753dece8SMiguel Ojeda * are always in-bounds and read_ptr never aliases prev_ptr */
1895753dece8SMiguel Ojeda unsafe {
1896753dece8SMiguel Ojeda while gap.read < len {
1897753dece8SMiguel Ojeda let read_ptr = ptr.add(gap.read);
1898753dece8SMiguel Ojeda let prev_ptr = ptr.add(gap.write.wrapping_sub(1));
1899753dece8SMiguel Ojeda
1900753dece8SMiguel Ojeda if same_bucket(&mut *read_ptr, &mut *prev_ptr) {
1901753dece8SMiguel Ojeda // Increase `gap.read` now since the drop may panic.
1902753dece8SMiguel Ojeda gap.read += 1;
1903753dece8SMiguel Ojeda /* We have found duplicate, drop it in-place */
1904753dece8SMiguel Ojeda ptr::drop_in_place(read_ptr);
1905753dece8SMiguel Ojeda } else {
1906753dece8SMiguel Ojeda let write_ptr = ptr.add(gap.write);
1907753dece8SMiguel Ojeda
1908753dece8SMiguel Ojeda /* Because `read_ptr` can be equal to `write_ptr`, we either
1909753dece8SMiguel Ojeda * have to use `copy` or conditional `copy_nonoverlapping`.
1910753dece8SMiguel Ojeda * Looks like the first option is faster. */
1911753dece8SMiguel Ojeda ptr::copy(read_ptr, write_ptr, 1);
1912753dece8SMiguel Ojeda
1913753dece8SMiguel Ojeda /* We have filled that place, so go further */
1914753dece8SMiguel Ojeda gap.write += 1;
1915753dece8SMiguel Ojeda gap.read += 1;
1916753dece8SMiguel Ojeda }
1917753dece8SMiguel Ojeda }
1918753dece8SMiguel Ojeda
1919753dece8SMiguel Ojeda /* Technically we could let `gap` clean up with its Drop, but
1920753dece8SMiguel Ojeda * when `same_bucket` is guaranteed to not panic, this bloats a little
1921753dece8SMiguel Ojeda * the codegen, so we just do it manually */
1922753dece8SMiguel Ojeda gap.vec.set_len(gap.write);
1923753dece8SMiguel Ojeda mem::forget(gap);
1924753dece8SMiguel Ojeda }
1925753dece8SMiguel Ojeda }
1926753dece8SMiguel Ojeda
1927753dece8SMiguel Ojeda /// Appends an element to the back of a collection.
1928753dece8SMiguel Ojeda ///
1929753dece8SMiguel Ojeda /// # Panics
1930753dece8SMiguel Ojeda ///
1931753dece8SMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes.
1932753dece8SMiguel Ojeda ///
1933753dece8SMiguel Ojeda /// # Examples
1934753dece8SMiguel Ojeda ///
1935753dece8SMiguel Ojeda /// ```
1936753dece8SMiguel Ojeda /// let mut vec = vec![1, 2];
1937753dece8SMiguel Ojeda /// vec.push(3);
1938753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3]);
1939753dece8SMiguel Ojeda /// ```
1940753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
1941753dece8SMiguel Ojeda #[inline]
1942753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
push(&mut self, value: T)1943753dece8SMiguel Ojeda pub fn push(&mut self, value: T) {
1944753dece8SMiguel Ojeda // This will panic or abort if we would allocate > isize::MAX bytes
1945753dece8SMiguel Ojeda // or if the length increment would overflow for zero-sized types.
1946753dece8SMiguel Ojeda if self.len == self.buf.capacity() {
1947753dece8SMiguel Ojeda self.buf.reserve_for_push(self.len);
1948753dece8SMiguel Ojeda }
1949753dece8SMiguel Ojeda unsafe {
1950753dece8SMiguel Ojeda let end = self.as_mut_ptr().add(self.len);
1951753dece8SMiguel Ojeda ptr::write(end, value);
1952753dece8SMiguel Ojeda self.len += 1;
1953753dece8SMiguel Ojeda }
1954753dece8SMiguel Ojeda }
1955753dece8SMiguel Ojeda
1956057b8d25SMiguel Ojeda /// Tries to append an element to the back of a collection.
1957057b8d25SMiguel Ojeda ///
1958057b8d25SMiguel Ojeda /// # Examples
1959057b8d25SMiguel Ojeda ///
1960057b8d25SMiguel Ojeda /// ```
1961057b8d25SMiguel Ojeda /// let mut vec = vec![1, 2];
1962057b8d25SMiguel Ojeda /// vec.try_push(3).unwrap();
1963057b8d25SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3]);
1964057b8d25SMiguel Ojeda /// ```
1965057b8d25SMiguel Ojeda #[inline]
1966057b8d25SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")]
try_push(&mut self, value: T) -> Result<(), TryReserveError>1967057b8d25SMiguel Ojeda pub fn try_push(&mut self, value: T) -> Result<(), TryReserveError> {
1968057b8d25SMiguel Ojeda if self.len == self.buf.capacity() {
1969057b8d25SMiguel Ojeda self.buf.try_reserve_for_push(self.len)?;
1970057b8d25SMiguel Ojeda }
1971057b8d25SMiguel Ojeda unsafe {
1972057b8d25SMiguel Ojeda let end = self.as_mut_ptr().add(self.len);
1973057b8d25SMiguel Ojeda ptr::write(end, value);
1974057b8d25SMiguel Ojeda self.len += 1;
1975057b8d25SMiguel Ojeda }
1976057b8d25SMiguel Ojeda Ok(())
1977057b8d25SMiguel Ojeda }
1978057b8d25SMiguel Ojeda
19793ed03f4dSMiguel Ojeda /// Appends an element if there is sufficient spare capacity, otherwise an error is returned
19803ed03f4dSMiguel Ojeda /// with the element.
19813ed03f4dSMiguel Ojeda ///
19823ed03f4dSMiguel Ojeda /// Unlike [`push`] this method will not reallocate when there's insufficient capacity.
19833ed03f4dSMiguel Ojeda /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity.
19843ed03f4dSMiguel Ojeda ///
19853ed03f4dSMiguel Ojeda /// [`push`]: Vec::push
19863ed03f4dSMiguel Ojeda /// [`reserve`]: Vec::reserve
19873ed03f4dSMiguel Ojeda /// [`try_reserve`]: Vec::try_reserve
19883ed03f4dSMiguel Ojeda ///
19893ed03f4dSMiguel Ojeda /// # Examples
19903ed03f4dSMiguel Ojeda ///
19913ed03f4dSMiguel Ojeda /// A manual, panic-free alternative to [`FromIterator`]:
19923ed03f4dSMiguel Ojeda ///
19933ed03f4dSMiguel Ojeda /// ```
19943ed03f4dSMiguel Ojeda /// #![feature(vec_push_within_capacity)]
19953ed03f4dSMiguel Ojeda ///
19963ed03f4dSMiguel Ojeda /// use std::collections::TryReserveError;
19973ed03f4dSMiguel Ojeda /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> {
19983ed03f4dSMiguel Ojeda /// let mut vec = Vec::new();
19993ed03f4dSMiguel Ojeda /// for value in iter {
20003ed03f4dSMiguel Ojeda /// if let Err(value) = vec.push_within_capacity(value) {
20013ed03f4dSMiguel Ojeda /// vec.try_reserve(1)?;
20023ed03f4dSMiguel Ojeda /// // this cannot fail, the previous line either returned or added at least 1 free slot
20033ed03f4dSMiguel Ojeda /// let _ = vec.push_within_capacity(value);
20043ed03f4dSMiguel Ojeda /// }
20053ed03f4dSMiguel Ojeda /// }
20063ed03f4dSMiguel Ojeda /// Ok(vec)
20073ed03f4dSMiguel Ojeda /// }
20083ed03f4dSMiguel Ojeda /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100)));
20093ed03f4dSMiguel Ojeda /// ```
20103ed03f4dSMiguel Ojeda #[inline]
20113ed03f4dSMiguel Ojeda #[unstable(feature = "vec_push_within_capacity", issue = "100486")]
push_within_capacity(&mut self, value: T) -> Result<(), T>20123ed03f4dSMiguel Ojeda pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> {
20133ed03f4dSMiguel Ojeda if self.len == self.buf.capacity() {
20143ed03f4dSMiguel Ojeda return Err(value);
20153ed03f4dSMiguel Ojeda }
20163ed03f4dSMiguel Ojeda unsafe {
20173ed03f4dSMiguel Ojeda let end = self.as_mut_ptr().add(self.len);
20183ed03f4dSMiguel Ojeda ptr::write(end, value);
20193ed03f4dSMiguel Ojeda self.len += 1;
20203ed03f4dSMiguel Ojeda }
20213ed03f4dSMiguel Ojeda Ok(())
20223ed03f4dSMiguel Ojeda }
20233ed03f4dSMiguel Ojeda
2024753dece8SMiguel Ojeda /// Removes the last element from a vector and returns it, or [`None`] if it
2025753dece8SMiguel Ojeda /// is empty.
2026753dece8SMiguel Ojeda ///
2027753dece8SMiguel Ojeda /// If you'd like to pop the first element, consider using
2028753dece8SMiguel Ojeda /// [`VecDeque::pop_front`] instead.
2029753dece8SMiguel Ojeda ///
2030753dece8SMiguel Ojeda /// [`VecDeque::pop_front`]: crate::collections::VecDeque::pop_front
2031753dece8SMiguel Ojeda ///
2032753dece8SMiguel Ojeda /// # Examples
2033753dece8SMiguel Ojeda ///
2034753dece8SMiguel Ojeda /// ```
2035753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3];
2036753dece8SMiguel Ojeda /// assert_eq!(vec.pop(), Some(3));
2037753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2]);
2038753dece8SMiguel Ojeda /// ```
2039753dece8SMiguel Ojeda #[inline]
2040753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
pop(&mut self) -> Option<T>2041753dece8SMiguel Ojeda pub fn pop(&mut self) -> Option<T> {
2042753dece8SMiguel Ojeda if self.len == 0 {
2043753dece8SMiguel Ojeda None
2044753dece8SMiguel Ojeda } else {
2045753dece8SMiguel Ojeda unsafe {
2046753dece8SMiguel Ojeda self.len -= 1;
2047753dece8SMiguel Ojeda Some(ptr::read(self.as_ptr().add(self.len())))
2048753dece8SMiguel Ojeda }
2049753dece8SMiguel Ojeda }
2050753dece8SMiguel Ojeda }
2051753dece8SMiguel Ojeda
2052753dece8SMiguel Ojeda /// Moves all the elements of `other` into `self`, leaving `other` empty.
2053753dece8SMiguel Ojeda ///
2054753dece8SMiguel Ojeda /// # Panics
2055753dece8SMiguel Ojeda ///
20563ed03f4dSMiguel Ojeda /// Panics if the new capacity exceeds `isize::MAX` bytes.
2057753dece8SMiguel Ojeda ///
2058753dece8SMiguel Ojeda /// # Examples
2059753dece8SMiguel Ojeda ///
2060753dece8SMiguel Ojeda /// ```
2061753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3];
2062753dece8SMiguel Ojeda /// let mut vec2 = vec![4, 5, 6];
2063753dece8SMiguel Ojeda /// vec.append(&mut vec2);
2064753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
2065753dece8SMiguel Ojeda /// assert_eq!(vec2, []);
2066753dece8SMiguel Ojeda /// ```
2067753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2068753dece8SMiguel Ojeda #[inline]
2069753dece8SMiguel Ojeda #[stable(feature = "append", since = "1.4.0")]
append(&mut self, other: &mut Self)2070753dece8SMiguel Ojeda pub fn append(&mut self, other: &mut Self) {
2071753dece8SMiguel Ojeda unsafe {
2072753dece8SMiguel Ojeda self.append_elements(other.as_slice() as _);
2073753dece8SMiguel Ojeda other.set_len(0);
2074753dece8SMiguel Ojeda }
2075753dece8SMiguel Ojeda }
2076753dece8SMiguel Ojeda
2077753dece8SMiguel Ojeda /// Appends elements to `self` from other buffer.
2078753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2079753dece8SMiguel Ojeda #[inline]
append_elements(&mut self, other: *const [T])2080753dece8SMiguel Ojeda unsafe fn append_elements(&mut self, other: *const [T]) {
2081753dece8SMiguel Ojeda let count = unsafe { (*other).len() };
2082753dece8SMiguel Ojeda self.reserve(count);
2083753dece8SMiguel Ojeda let len = self.len();
2084753dece8SMiguel Ojeda unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) };
2085753dece8SMiguel Ojeda self.len += count;
2086753dece8SMiguel Ojeda }
2087753dece8SMiguel Ojeda
2088318c3cc8SMiguel Ojeda /// Tries to append elements to `self` from other buffer.
2089318c3cc8SMiguel Ojeda #[inline]
try_append_elements(&mut self, other: *const [T]) -> Result<(), TryReserveError>2090318c3cc8SMiguel Ojeda unsafe fn try_append_elements(&mut self, other: *const [T]) -> Result<(), TryReserveError> {
2091318c3cc8SMiguel Ojeda let count = unsafe { (*other).len() };
2092318c3cc8SMiguel Ojeda self.try_reserve(count)?;
2093318c3cc8SMiguel Ojeda let len = self.len();
2094318c3cc8SMiguel Ojeda unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) };
2095318c3cc8SMiguel Ojeda self.len += count;
2096318c3cc8SMiguel Ojeda Ok(())
2097318c3cc8SMiguel Ojeda }
2098318c3cc8SMiguel Ojeda
2099753dece8SMiguel Ojeda /// Removes the specified range from the vector in bulk, returning all
2100753dece8SMiguel Ojeda /// removed elements as an iterator. If the iterator is dropped before
2101753dece8SMiguel Ojeda /// being fully consumed, it drops the remaining removed elements.
2102753dece8SMiguel Ojeda ///
2103753dece8SMiguel Ojeda /// The returned iterator keeps a mutable borrow on the vector to optimize
2104753dece8SMiguel Ojeda /// its implementation.
2105753dece8SMiguel Ojeda ///
2106753dece8SMiguel Ojeda /// # Panics
2107753dece8SMiguel Ojeda ///
2108753dece8SMiguel Ojeda /// Panics if the starting point is greater than the end point or if
2109753dece8SMiguel Ojeda /// the end point is greater than the length of the vector.
2110753dece8SMiguel Ojeda ///
2111753dece8SMiguel Ojeda /// # Leaking
2112753dece8SMiguel Ojeda ///
2113753dece8SMiguel Ojeda /// If the returned iterator goes out of scope without being dropped (due to
2114753dece8SMiguel Ojeda /// [`mem::forget`], for example), the vector may have lost and leaked
2115753dece8SMiguel Ojeda /// elements arbitrarily, including elements outside the range.
2116753dece8SMiguel Ojeda ///
2117753dece8SMiguel Ojeda /// # Examples
2118753dece8SMiguel Ojeda ///
2119753dece8SMiguel Ojeda /// ```
2120753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3];
2121753dece8SMiguel Ojeda /// let u: Vec<_> = v.drain(1..).collect();
2122753dece8SMiguel Ojeda /// assert_eq!(v, &[1]);
2123753dece8SMiguel Ojeda /// assert_eq!(u, &[2, 3]);
2124753dece8SMiguel Ojeda ///
2125753dece8SMiguel Ojeda /// // A full range clears the vector, like `clear()` does
2126753dece8SMiguel Ojeda /// v.drain(..);
2127753dece8SMiguel Ojeda /// assert_eq!(v, &[]);
2128753dece8SMiguel Ojeda /// ```
2129753dece8SMiguel Ojeda #[stable(feature = "drain", since = "1.6.0")]
drain<R>(&mut self, range: R) -> Drain<'_, T, A> where R: RangeBounds<usize>,2130753dece8SMiguel Ojeda pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
2131753dece8SMiguel Ojeda where
2132753dece8SMiguel Ojeda R: RangeBounds<usize>,
2133753dece8SMiguel Ojeda {
2134753dece8SMiguel Ojeda // Memory safety
2135753dece8SMiguel Ojeda //
2136753dece8SMiguel Ojeda // When the Drain is first created, it shortens the length of
2137753dece8SMiguel Ojeda // the source vector to make sure no uninitialized or moved-from elements
2138753dece8SMiguel Ojeda // are accessible at all if the Drain's destructor never gets to run.
2139753dece8SMiguel Ojeda //
2140753dece8SMiguel Ojeda // Drain will ptr::read out the values to remove.
2141753dece8SMiguel Ojeda // When finished, remaining tail of the vec is copied back to cover
2142753dece8SMiguel Ojeda // the hole, and the vector length is restored to the new length.
2143753dece8SMiguel Ojeda //
2144753dece8SMiguel Ojeda let len = self.len();
2145753dece8SMiguel Ojeda let Range { start, end } = slice::range(range, ..len);
2146753dece8SMiguel Ojeda
2147753dece8SMiguel Ojeda unsafe {
2148753dece8SMiguel Ojeda // set self.vec length's to start, to be safe in case Drain is leaked
2149753dece8SMiguel Ojeda self.set_len(start);
21503ed03f4dSMiguel Ojeda let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
2151753dece8SMiguel Ojeda Drain {
2152753dece8SMiguel Ojeda tail_start: end,
2153753dece8SMiguel Ojeda tail_len: len - end,
2154753dece8SMiguel Ojeda iter: range_slice.iter(),
2155753dece8SMiguel Ojeda vec: NonNull::from(self),
2156753dece8SMiguel Ojeda }
2157753dece8SMiguel Ojeda }
2158753dece8SMiguel Ojeda }
2159753dece8SMiguel Ojeda
2160753dece8SMiguel Ojeda /// Clears the vector, removing all values.
2161753dece8SMiguel Ojeda ///
2162753dece8SMiguel Ojeda /// Note that this method has no effect on the allocated capacity
2163753dece8SMiguel Ojeda /// of the vector.
2164753dece8SMiguel Ojeda ///
2165753dece8SMiguel Ojeda /// # Examples
2166753dece8SMiguel Ojeda ///
2167753dece8SMiguel Ojeda /// ```
2168753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3];
2169753dece8SMiguel Ojeda ///
2170753dece8SMiguel Ojeda /// v.clear();
2171753dece8SMiguel Ojeda ///
2172753dece8SMiguel Ojeda /// assert!(v.is_empty());
2173753dece8SMiguel Ojeda /// ```
2174753dece8SMiguel Ojeda #[inline]
2175753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
clear(&mut self)2176753dece8SMiguel Ojeda pub fn clear(&mut self) {
2177753dece8SMiguel Ojeda let elems: *mut [T] = self.as_mut_slice();
2178753dece8SMiguel Ojeda
2179753dece8SMiguel Ojeda // SAFETY:
2180753dece8SMiguel Ojeda // - `elems` comes directly from `as_mut_slice` and is therefore valid.
2181753dece8SMiguel Ojeda // - Setting `self.len` before calling `drop_in_place` means that,
2182753dece8SMiguel Ojeda // if an element's `Drop` impl panics, the vector's `Drop` impl will
2183753dece8SMiguel Ojeda // do nothing (leaking the rest of the elements) instead of dropping
2184753dece8SMiguel Ojeda // some twice.
2185753dece8SMiguel Ojeda unsafe {
2186753dece8SMiguel Ojeda self.len = 0;
2187753dece8SMiguel Ojeda ptr::drop_in_place(elems);
2188753dece8SMiguel Ojeda }
2189753dece8SMiguel Ojeda }
2190753dece8SMiguel Ojeda
2191753dece8SMiguel Ojeda /// Returns the number of elements in the vector, also referred to
2192753dece8SMiguel Ojeda /// as its 'length'.
2193753dece8SMiguel Ojeda ///
2194753dece8SMiguel Ojeda /// # Examples
2195753dece8SMiguel Ojeda ///
2196753dece8SMiguel Ojeda /// ```
2197753dece8SMiguel Ojeda /// let a = vec![1, 2, 3];
2198753dece8SMiguel Ojeda /// assert_eq!(a.len(), 3);
2199753dece8SMiguel Ojeda /// ```
2200753dece8SMiguel Ojeda #[inline]
2201753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
len(&self) -> usize2202753dece8SMiguel Ojeda pub fn len(&self) -> usize {
2203753dece8SMiguel Ojeda self.len
2204753dece8SMiguel Ojeda }
2205753dece8SMiguel Ojeda
2206753dece8SMiguel Ojeda /// Returns `true` if the vector contains no elements.
2207753dece8SMiguel Ojeda ///
2208753dece8SMiguel Ojeda /// # Examples
2209753dece8SMiguel Ojeda ///
2210753dece8SMiguel Ojeda /// ```
2211753dece8SMiguel Ojeda /// let mut v = Vec::new();
2212753dece8SMiguel Ojeda /// assert!(v.is_empty());
2213753dece8SMiguel Ojeda ///
2214753dece8SMiguel Ojeda /// v.push(1);
2215753dece8SMiguel Ojeda /// assert!(!v.is_empty());
2216753dece8SMiguel Ojeda /// ```
2217753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
is_empty(&self) -> bool2218753dece8SMiguel Ojeda pub fn is_empty(&self) -> bool {
2219753dece8SMiguel Ojeda self.len() == 0
2220753dece8SMiguel Ojeda }
2221753dece8SMiguel Ojeda
2222753dece8SMiguel Ojeda /// Splits the collection into two at the given index.
2223753dece8SMiguel Ojeda ///
2224753dece8SMiguel Ojeda /// Returns a newly allocated vector containing the elements in the range
2225753dece8SMiguel Ojeda /// `[at, len)`. After the call, the original vector will be left containing
2226753dece8SMiguel Ojeda /// the elements `[0, at)` with its previous capacity unchanged.
2227753dece8SMiguel Ojeda ///
2228753dece8SMiguel Ojeda /// # Panics
2229753dece8SMiguel Ojeda ///
2230753dece8SMiguel Ojeda /// Panics if `at > len`.
2231753dece8SMiguel Ojeda ///
2232753dece8SMiguel Ojeda /// # Examples
2233753dece8SMiguel Ojeda ///
2234753dece8SMiguel Ojeda /// ```
2235753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3];
2236753dece8SMiguel Ojeda /// let vec2 = vec.split_off(1);
2237753dece8SMiguel Ojeda /// assert_eq!(vec, [1]);
2238753dece8SMiguel Ojeda /// assert_eq!(vec2, [2, 3]);
2239753dece8SMiguel Ojeda /// ```
2240753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2241753dece8SMiguel Ojeda #[inline]
2242753dece8SMiguel Ojeda #[must_use = "use `.truncate()` if you don't need the other half"]
2243753dece8SMiguel Ojeda #[stable(feature = "split_off", since = "1.4.0")]
split_off(&mut self, at: usize) -> Self where A: Clone,2244753dece8SMiguel Ojeda pub fn split_off(&mut self, at: usize) -> Self
2245753dece8SMiguel Ojeda where
2246753dece8SMiguel Ojeda A: Clone,
2247753dece8SMiguel Ojeda {
2248753dece8SMiguel Ojeda #[cold]
2249753dece8SMiguel Ojeda #[inline(never)]
2250753dece8SMiguel Ojeda fn assert_failed(at: usize, len: usize) -> ! {
2251753dece8SMiguel Ojeda panic!("`at` split index (is {at}) should be <= len (is {len})");
2252753dece8SMiguel Ojeda }
2253753dece8SMiguel Ojeda
2254753dece8SMiguel Ojeda if at > self.len() {
2255753dece8SMiguel Ojeda assert_failed(at, self.len());
2256753dece8SMiguel Ojeda }
2257753dece8SMiguel Ojeda
2258753dece8SMiguel Ojeda if at == 0 {
2259753dece8SMiguel Ojeda // the new vector can take over the original buffer and avoid the copy
2260753dece8SMiguel Ojeda return mem::replace(
2261753dece8SMiguel Ojeda self,
2262753dece8SMiguel Ojeda Vec::with_capacity_in(self.capacity(), self.allocator().clone()),
2263753dece8SMiguel Ojeda );
2264753dece8SMiguel Ojeda }
2265753dece8SMiguel Ojeda
2266753dece8SMiguel Ojeda let other_len = self.len - at;
2267753dece8SMiguel Ojeda let mut other = Vec::with_capacity_in(other_len, self.allocator().clone());
2268753dece8SMiguel Ojeda
2269753dece8SMiguel Ojeda // Unsafely `set_len` and copy items to `other`.
2270753dece8SMiguel Ojeda unsafe {
2271753dece8SMiguel Ojeda self.set_len(at);
2272753dece8SMiguel Ojeda other.set_len(other_len);
2273753dece8SMiguel Ojeda
2274753dece8SMiguel Ojeda ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
2275753dece8SMiguel Ojeda }
2276753dece8SMiguel Ojeda other
2277753dece8SMiguel Ojeda }
2278753dece8SMiguel Ojeda
2279753dece8SMiguel Ojeda /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
2280753dece8SMiguel Ojeda ///
2281753dece8SMiguel Ojeda /// If `new_len` is greater than `len`, the `Vec` is extended by the
2282753dece8SMiguel Ojeda /// difference, with each additional slot filled with the result of
2283753dece8SMiguel Ojeda /// calling the closure `f`. The return values from `f` will end up
2284753dece8SMiguel Ojeda /// in the `Vec` in the order they have been generated.
2285753dece8SMiguel Ojeda ///
2286753dece8SMiguel Ojeda /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2287753dece8SMiguel Ojeda ///
2288753dece8SMiguel Ojeda /// This method uses a closure to create new values on every push. If
2289753dece8SMiguel Ojeda /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you
2290753dece8SMiguel Ojeda /// want to use the [`Default`] trait to generate values, you can
2291753dece8SMiguel Ojeda /// pass [`Default::default`] as the second argument.
2292753dece8SMiguel Ojeda ///
2293753dece8SMiguel Ojeda /// # Examples
2294753dece8SMiguel Ojeda ///
2295753dece8SMiguel Ojeda /// ```
2296753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3];
2297753dece8SMiguel Ojeda /// vec.resize_with(5, Default::default);
2298753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 0, 0]);
2299753dece8SMiguel Ojeda ///
2300753dece8SMiguel Ojeda /// let mut vec = vec![];
2301753dece8SMiguel Ojeda /// let mut p = 1;
2302753dece8SMiguel Ojeda /// vec.resize_with(4, || { p *= 2; p });
2303753dece8SMiguel Ojeda /// assert_eq!(vec, [2, 4, 8, 16]);
2304753dece8SMiguel Ojeda /// ```
2305753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2306753dece8SMiguel Ojeda #[stable(feature = "vec_resize_with", since = "1.33.0")]
resize_with<F>(&mut self, new_len: usize, f: F) where F: FnMut() -> T,2307753dece8SMiguel Ojeda pub fn resize_with<F>(&mut self, new_len: usize, f: F)
2308753dece8SMiguel Ojeda where
2309753dece8SMiguel Ojeda F: FnMut() -> T,
2310753dece8SMiguel Ojeda {
2311753dece8SMiguel Ojeda let len = self.len();
2312753dece8SMiguel Ojeda if new_len > len {
23133ed03f4dSMiguel Ojeda self.extend_trusted(iter::repeat_with(f).take(new_len - len));
2314753dece8SMiguel Ojeda } else {
2315753dece8SMiguel Ojeda self.truncate(new_len);
2316753dece8SMiguel Ojeda }
2317753dece8SMiguel Ojeda }
2318753dece8SMiguel Ojeda
2319753dece8SMiguel Ojeda /// Consumes and leaks the `Vec`, returning a mutable reference to the contents,
2320753dece8SMiguel Ojeda /// `&'a mut [T]`. Note that the type `T` must outlive the chosen lifetime
2321753dece8SMiguel Ojeda /// `'a`. If the type has only static references, or none at all, then this
2322753dece8SMiguel Ojeda /// may be chosen to be `'static`.
2323753dece8SMiguel Ojeda ///
2324753dece8SMiguel Ojeda /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`,
2325753dece8SMiguel Ojeda /// so the leaked allocation may include unused capacity that is not part
2326753dece8SMiguel Ojeda /// of the returned slice.
2327753dece8SMiguel Ojeda ///
2328753dece8SMiguel Ojeda /// This function is mainly useful for data that lives for the remainder of
2329753dece8SMiguel Ojeda /// the program's life. Dropping the returned reference will cause a memory
2330753dece8SMiguel Ojeda /// leak.
2331753dece8SMiguel Ojeda ///
2332753dece8SMiguel Ojeda /// # Examples
2333753dece8SMiguel Ojeda ///
2334753dece8SMiguel Ojeda /// Simple usage:
2335753dece8SMiguel Ojeda ///
2336753dece8SMiguel Ojeda /// ```
2337753dece8SMiguel Ojeda /// let x = vec![1, 2, 3];
2338753dece8SMiguel Ojeda /// let static_ref: &'static mut [usize] = x.leak();
2339753dece8SMiguel Ojeda /// static_ref[0] += 1;
2340753dece8SMiguel Ojeda /// assert_eq!(static_ref, &[2, 2, 3]);
2341753dece8SMiguel Ojeda /// ```
2342753dece8SMiguel Ojeda #[stable(feature = "vec_leak", since = "1.47.0")]
2343753dece8SMiguel Ojeda #[inline]
leak<'a>(self) -> &'a mut [T] where A: 'a,2344753dece8SMiguel Ojeda pub fn leak<'a>(self) -> &'a mut [T]
2345753dece8SMiguel Ojeda where
2346753dece8SMiguel Ojeda A: 'a,
2347753dece8SMiguel Ojeda {
2348753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self);
2349753dece8SMiguel Ojeda unsafe { slice::from_raw_parts_mut(me.as_mut_ptr(), me.len) }
2350753dece8SMiguel Ojeda }
2351753dece8SMiguel Ojeda
2352753dece8SMiguel Ojeda /// Returns the remaining spare capacity of the vector as a slice of
2353753dece8SMiguel Ojeda /// `MaybeUninit<T>`.
2354753dece8SMiguel Ojeda ///
2355753dece8SMiguel Ojeda /// The returned slice can be used to fill the vector with data (e.g. by
2356753dece8SMiguel Ojeda /// reading from a file) before marking the data as initialized using the
2357753dece8SMiguel Ojeda /// [`set_len`] method.
2358753dece8SMiguel Ojeda ///
2359753dece8SMiguel Ojeda /// [`set_len`]: Vec::set_len
2360753dece8SMiguel Ojeda ///
2361753dece8SMiguel Ojeda /// # Examples
2362753dece8SMiguel Ojeda ///
2363753dece8SMiguel Ojeda /// ```
2364753dece8SMiguel Ojeda /// // Allocate vector big enough for 10 elements.
2365753dece8SMiguel Ojeda /// let mut v = Vec::with_capacity(10);
2366753dece8SMiguel Ojeda ///
2367753dece8SMiguel Ojeda /// // Fill in the first 3 elements.
2368753dece8SMiguel Ojeda /// let uninit = v.spare_capacity_mut();
2369753dece8SMiguel Ojeda /// uninit[0].write(0);
2370753dece8SMiguel Ojeda /// uninit[1].write(1);
2371753dece8SMiguel Ojeda /// uninit[2].write(2);
2372753dece8SMiguel Ojeda ///
2373753dece8SMiguel Ojeda /// // Mark the first 3 elements of the vector as being initialized.
2374753dece8SMiguel Ojeda /// unsafe {
2375753dece8SMiguel Ojeda /// v.set_len(3);
2376753dece8SMiguel Ojeda /// }
2377753dece8SMiguel Ojeda ///
2378753dece8SMiguel Ojeda /// assert_eq!(&v, &[0, 1, 2]);
2379753dece8SMiguel Ojeda /// ```
2380753dece8SMiguel Ojeda #[stable(feature = "vec_spare_capacity", since = "1.60.0")]
2381753dece8SMiguel Ojeda #[inline]
spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>]2382753dece8SMiguel Ojeda pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
2383753dece8SMiguel Ojeda // Note:
2384753dece8SMiguel Ojeda // This method is not implemented in terms of `split_at_spare_mut`,
2385753dece8SMiguel Ojeda // to prevent invalidation of pointers to the buffer.
2386753dece8SMiguel Ojeda unsafe {
2387753dece8SMiguel Ojeda slice::from_raw_parts_mut(
2388753dece8SMiguel Ojeda self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
2389753dece8SMiguel Ojeda self.buf.capacity() - self.len,
2390753dece8SMiguel Ojeda )
2391753dece8SMiguel Ojeda }
2392753dece8SMiguel Ojeda }
2393753dece8SMiguel Ojeda
2394753dece8SMiguel Ojeda /// Returns vector content as a slice of `T`, along with the remaining spare
2395753dece8SMiguel Ojeda /// capacity of the vector as a slice of `MaybeUninit<T>`.
2396753dece8SMiguel Ojeda ///
2397753dece8SMiguel Ojeda /// The returned spare capacity slice can be used to fill the vector with data
2398753dece8SMiguel Ojeda /// (e.g. by reading from a file) before marking the data as initialized using
2399753dece8SMiguel Ojeda /// the [`set_len`] method.
2400753dece8SMiguel Ojeda ///
2401753dece8SMiguel Ojeda /// [`set_len`]: Vec::set_len
2402753dece8SMiguel Ojeda ///
2403753dece8SMiguel Ojeda /// Note that this is a low-level API, which should be used with care for
2404753dece8SMiguel Ojeda /// optimization purposes. If you need to append data to a `Vec`
2405753dece8SMiguel Ojeda /// you can use [`push`], [`extend`], [`extend_from_slice`],
2406753dece8SMiguel Ojeda /// [`extend_from_within`], [`insert`], [`append`], [`resize`] or
2407753dece8SMiguel Ojeda /// [`resize_with`], depending on your exact needs.
2408753dece8SMiguel Ojeda ///
2409753dece8SMiguel Ojeda /// [`push`]: Vec::push
2410753dece8SMiguel Ojeda /// [`extend`]: Vec::extend
2411753dece8SMiguel Ojeda /// [`extend_from_slice`]: Vec::extend_from_slice
2412753dece8SMiguel Ojeda /// [`extend_from_within`]: Vec::extend_from_within
2413753dece8SMiguel Ojeda /// [`insert`]: Vec::insert
2414753dece8SMiguel Ojeda /// [`append`]: Vec::append
2415753dece8SMiguel Ojeda /// [`resize`]: Vec::resize
2416753dece8SMiguel Ojeda /// [`resize_with`]: Vec::resize_with
2417753dece8SMiguel Ojeda ///
2418753dece8SMiguel Ojeda /// # Examples
2419753dece8SMiguel Ojeda ///
2420753dece8SMiguel Ojeda /// ```
2421753dece8SMiguel Ojeda /// #![feature(vec_split_at_spare)]
2422753dece8SMiguel Ojeda ///
2423753dece8SMiguel Ojeda /// let mut v = vec![1, 1, 2];
2424753dece8SMiguel Ojeda ///
2425753dece8SMiguel Ojeda /// // Reserve additional space big enough for 10 elements.
2426753dece8SMiguel Ojeda /// v.reserve(10);
2427753dece8SMiguel Ojeda ///
2428753dece8SMiguel Ojeda /// let (init, uninit) = v.split_at_spare_mut();
2429753dece8SMiguel Ojeda /// let sum = init.iter().copied().sum::<u32>();
2430753dece8SMiguel Ojeda ///
2431753dece8SMiguel Ojeda /// // Fill in the next 4 elements.
2432753dece8SMiguel Ojeda /// uninit[0].write(sum);
2433753dece8SMiguel Ojeda /// uninit[1].write(sum * 2);
2434753dece8SMiguel Ojeda /// uninit[2].write(sum * 3);
2435753dece8SMiguel Ojeda /// uninit[3].write(sum * 4);
2436753dece8SMiguel Ojeda ///
2437753dece8SMiguel Ojeda /// // Mark the 4 elements of the vector as being initialized.
2438753dece8SMiguel Ojeda /// unsafe {
2439753dece8SMiguel Ojeda /// let len = v.len();
2440753dece8SMiguel Ojeda /// v.set_len(len + 4);
2441753dece8SMiguel Ojeda /// }
2442753dece8SMiguel Ojeda ///
2443753dece8SMiguel Ojeda /// assert_eq!(&v, &[1, 1, 2, 4, 8, 12, 16]);
2444753dece8SMiguel Ojeda /// ```
2445753dece8SMiguel Ojeda #[unstable(feature = "vec_split_at_spare", issue = "81944")]
2446753dece8SMiguel Ojeda #[inline]
split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>])2447753dece8SMiguel Ojeda pub fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) {
2448753dece8SMiguel Ojeda // SAFETY:
2449753dece8SMiguel Ojeda // - len is ignored and so never changed
2450753dece8SMiguel Ojeda let (init, spare, _) = unsafe { self.split_at_spare_mut_with_len() };
2451753dece8SMiguel Ojeda (init, spare)
2452753dece8SMiguel Ojeda }
2453753dece8SMiguel Ojeda
2454753dece8SMiguel Ojeda /// Safety: changing returned .2 (&mut usize) is considered the same as calling `.set_len(_)`.
2455753dece8SMiguel Ojeda ///
2456753dece8SMiguel Ojeda /// This method provides unique access to all vec parts at once in `extend_from_within`.
split_at_spare_mut_with_len( &mut self, ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize)2457753dece8SMiguel Ojeda unsafe fn split_at_spare_mut_with_len(
2458753dece8SMiguel Ojeda &mut self,
2459753dece8SMiguel Ojeda ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) {
2460753dece8SMiguel Ojeda let ptr = self.as_mut_ptr();
2461753dece8SMiguel Ojeda // SAFETY:
2462753dece8SMiguel Ojeda // - `ptr` is guaranteed to be valid for `self.len` elements
2463753dece8SMiguel Ojeda // - but the allocation extends out to `self.buf.capacity()` elements, possibly
2464753dece8SMiguel Ojeda // uninitialized
2465753dece8SMiguel Ojeda let spare_ptr = unsafe { ptr.add(self.len) };
2466753dece8SMiguel Ojeda let spare_ptr = spare_ptr.cast::<MaybeUninit<T>>();
2467753dece8SMiguel Ojeda let spare_len = self.buf.capacity() - self.len;
2468753dece8SMiguel Ojeda
2469753dece8SMiguel Ojeda // SAFETY:
2470753dece8SMiguel Ojeda // - `ptr` is guaranteed to be valid for `self.len` elements
2471753dece8SMiguel Ojeda // - `spare_ptr` is pointing one element past the buffer, so it doesn't overlap with `initialized`
2472753dece8SMiguel Ojeda unsafe {
2473753dece8SMiguel Ojeda let initialized = slice::from_raw_parts_mut(ptr, self.len);
2474753dece8SMiguel Ojeda let spare = slice::from_raw_parts_mut(spare_ptr, spare_len);
2475753dece8SMiguel Ojeda
2476753dece8SMiguel Ojeda (initialized, spare, &mut self.len)
2477753dece8SMiguel Ojeda }
2478753dece8SMiguel Ojeda }
2479753dece8SMiguel Ojeda }
2480753dece8SMiguel Ojeda
2481753dece8SMiguel Ojeda impl<T: Clone, A: Allocator> Vec<T, A> {
2482753dece8SMiguel Ojeda /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
2483753dece8SMiguel Ojeda ///
2484753dece8SMiguel Ojeda /// If `new_len` is greater than `len`, the `Vec` is extended by the
2485753dece8SMiguel Ojeda /// difference, with each additional slot filled with `value`.
2486753dece8SMiguel Ojeda /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2487753dece8SMiguel Ojeda ///
2488753dece8SMiguel Ojeda /// This method requires `T` to implement [`Clone`],
2489753dece8SMiguel Ojeda /// in order to be able to clone the passed value.
2490753dece8SMiguel Ojeda /// If you need more flexibility (or want to rely on [`Default`] instead of
2491753dece8SMiguel Ojeda /// [`Clone`]), use [`Vec::resize_with`].
2492753dece8SMiguel Ojeda /// If you only need to resize to a smaller size, use [`Vec::truncate`].
2493753dece8SMiguel Ojeda ///
2494753dece8SMiguel Ojeda /// # Examples
2495753dece8SMiguel Ojeda ///
2496753dece8SMiguel Ojeda /// ```
2497753dece8SMiguel Ojeda /// let mut vec = vec!["hello"];
2498753dece8SMiguel Ojeda /// vec.resize(3, "world");
2499753dece8SMiguel Ojeda /// assert_eq!(vec, ["hello", "world", "world"]);
2500753dece8SMiguel Ojeda ///
2501753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4];
2502753dece8SMiguel Ojeda /// vec.resize(2, 0);
2503753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2]);
2504753dece8SMiguel Ojeda /// ```
2505753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2506753dece8SMiguel Ojeda #[stable(feature = "vec_resize", since = "1.5.0")]
resize(&mut self, new_len: usize, value: T)2507753dece8SMiguel Ojeda pub fn resize(&mut self, new_len: usize, value: T) {
2508753dece8SMiguel Ojeda let len = self.len();
2509753dece8SMiguel Ojeda
2510753dece8SMiguel Ojeda if new_len > len {
25119b33bb25SMiguel Ojeda self.extend_with(new_len - len, value)
2512753dece8SMiguel Ojeda } else {
2513753dece8SMiguel Ojeda self.truncate(new_len);
2514753dece8SMiguel Ojeda }
2515753dece8SMiguel Ojeda }
2516753dece8SMiguel Ojeda
2517318c3cc8SMiguel Ojeda /// Tries to resize the `Vec` in-place so that `len` is equal to `new_len`.
2518318c3cc8SMiguel Ojeda ///
2519318c3cc8SMiguel Ojeda /// If `new_len` is greater than `len`, the `Vec` is extended by the
2520318c3cc8SMiguel Ojeda /// difference, with each additional slot filled with `value`.
2521318c3cc8SMiguel Ojeda /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2522318c3cc8SMiguel Ojeda ///
2523318c3cc8SMiguel Ojeda /// This method requires `T` to implement [`Clone`],
2524318c3cc8SMiguel Ojeda /// in order to be able to clone the passed value.
2525318c3cc8SMiguel Ojeda /// If you need more flexibility (or want to rely on [`Default`] instead of
2526318c3cc8SMiguel Ojeda /// [`Clone`]), use [`Vec::resize_with`].
2527318c3cc8SMiguel Ojeda /// If you only need to resize to a smaller size, use [`Vec::truncate`].
2528318c3cc8SMiguel Ojeda ///
2529318c3cc8SMiguel Ojeda /// # Examples
2530318c3cc8SMiguel Ojeda ///
2531318c3cc8SMiguel Ojeda /// ```
2532318c3cc8SMiguel Ojeda /// let mut vec = vec!["hello"];
2533318c3cc8SMiguel Ojeda /// vec.try_resize(3, "world").unwrap();
2534318c3cc8SMiguel Ojeda /// assert_eq!(vec, ["hello", "world", "world"]);
2535318c3cc8SMiguel Ojeda ///
2536318c3cc8SMiguel Ojeda /// let mut vec = vec![1, 2, 3, 4];
2537318c3cc8SMiguel Ojeda /// vec.try_resize(2, 0).unwrap();
2538318c3cc8SMiguel Ojeda /// assert_eq!(vec, [1, 2]);
2539318c3cc8SMiguel Ojeda ///
2540318c3cc8SMiguel Ojeda /// let mut vec = vec![42];
2541318c3cc8SMiguel Ojeda /// let result = vec.try_resize(usize::MAX, 0);
2542318c3cc8SMiguel Ojeda /// assert!(result.is_err());
2543318c3cc8SMiguel Ojeda /// ```
2544318c3cc8SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")]
try_resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError>2545318c3cc8SMiguel Ojeda pub fn try_resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> {
2546318c3cc8SMiguel Ojeda let len = self.len();
2547318c3cc8SMiguel Ojeda
2548318c3cc8SMiguel Ojeda if new_len > len {
25499b33bb25SMiguel Ojeda self.try_extend_with(new_len - len, value)
2550318c3cc8SMiguel Ojeda } else {
2551318c3cc8SMiguel Ojeda self.truncate(new_len);
2552318c3cc8SMiguel Ojeda Ok(())
2553318c3cc8SMiguel Ojeda }
2554318c3cc8SMiguel Ojeda }
2555318c3cc8SMiguel Ojeda
2556753dece8SMiguel Ojeda /// Clones and appends all elements in a slice to the `Vec`.
2557753dece8SMiguel Ojeda ///
2558753dece8SMiguel Ojeda /// Iterates over the slice `other`, clones each element, and then appends
2559753dece8SMiguel Ojeda /// it to this `Vec`. The `other` slice is traversed in-order.
2560753dece8SMiguel Ojeda ///
2561753dece8SMiguel Ojeda /// Note that this function is same as [`extend`] except that it is
2562753dece8SMiguel Ojeda /// specialized to work with slices instead. If and when Rust gets
2563753dece8SMiguel Ojeda /// specialization this function will likely be deprecated (but still
2564753dece8SMiguel Ojeda /// available).
2565753dece8SMiguel Ojeda ///
2566753dece8SMiguel Ojeda /// # Examples
2567753dece8SMiguel Ojeda ///
2568753dece8SMiguel Ojeda /// ```
2569753dece8SMiguel Ojeda /// let mut vec = vec![1];
2570753dece8SMiguel Ojeda /// vec.extend_from_slice(&[2, 3, 4]);
2571753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 4]);
2572753dece8SMiguel Ojeda /// ```
2573753dece8SMiguel Ojeda ///
2574753dece8SMiguel Ojeda /// [`extend`]: Vec::extend
2575753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2576753dece8SMiguel Ojeda #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
extend_from_slice(&mut self, other: &[T])2577753dece8SMiguel Ojeda pub fn extend_from_slice(&mut self, other: &[T]) {
2578753dece8SMiguel Ojeda self.spec_extend(other.iter())
2579753dece8SMiguel Ojeda }
2580753dece8SMiguel Ojeda
2581318c3cc8SMiguel Ojeda /// Tries to clone and append all elements in a slice to the `Vec`.
2582318c3cc8SMiguel Ojeda ///
2583318c3cc8SMiguel Ojeda /// Iterates over the slice `other`, clones each element, and then appends
2584318c3cc8SMiguel Ojeda /// it to this `Vec`. The `other` slice is traversed in-order.
2585318c3cc8SMiguel Ojeda ///
2586318c3cc8SMiguel Ojeda /// Note that this function is same as [`extend`] except that it is
2587318c3cc8SMiguel Ojeda /// specialized to work with slices instead. If and when Rust gets
2588318c3cc8SMiguel Ojeda /// specialization this function will likely be deprecated (but still
2589318c3cc8SMiguel Ojeda /// available).
2590318c3cc8SMiguel Ojeda ///
2591318c3cc8SMiguel Ojeda /// # Examples
2592318c3cc8SMiguel Ojeda ///
2593318c3cc8SMiguel Ojeda /// ```
2594318c3cc8SMiguel Ojeda /// let mut vec = vec![1];
2595318c3cc8SMiguel Ojeda /// vec.try_extend_from_slice(&[2, 3, 4]).unwrap();
2596318c3cc8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 4]);
2597318c3cc8SMiguel Ojeda /// ```
2598318c3cc8SMiguel Ojeda ///
2599318c3cc8SMiguel Ojeda /// [`extend`]: Vec::extend
2600318c3cc8SMiguel Ojeda #[stable(feature = "kernel", since = "1.0.0")]
try_extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError>2601318c3cc8SMiguel Ojeda pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError> {
2602318c3cc8SMiguel Ojeda self.try_spec_extend(other.iter())
2603318c3cc8SMiguel Ojeda }
2604318c3cc8SMiguel Ojeda
2605753dece8SMiguel Ojeda /// Copies elements from `src` range to the end of the vector.
2606753dece8SMiguel Ojeda ///
2607753dece8SMiguel Ojeda /// # Panics
2608753dece8SMiguel Ojeda ///
2609753dece8SMiguel Ojeda /// Panics if the starting point is greater than the end point or if
2610753dece8SMiguel Ojeda /// the end point is greater than the length of the vector.
2611753dece8SMiguel Ojeda ///
2612753dece8SMiguel Ojeda /// # Examples
2613753dece8SMiguel Ojeda ///
2614753dece8SMiguel Ojeda /// ```
2615753dece8SMiguel Ojeda /// let mut vec = vec![0, 1, 2, 3, 4];
2616753dece8SMiguel Ojeda ///
2617753dece8SMiguel Ojeda /// vec.extend_from_within(2..);
2618753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4]);
2619753dece8SMiguel Ojeda ///
2620753dece8SMiguel Ojeda /// vec.extend_from_within(..2);
2621753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1]);
2622753dece8SMiguel Ojeda ///
2623753dece8SMiguel Ojeda /// vec.extend_from_within(4..8);
2624753dece8SMiguel Ojeda /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1, 4, 2, 3, 4]);
2625753dece8SMiguel Ojeda /// ```
2626753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2627753dece8SMiguel Ojeda #[stable(feature = "vec_extend_from_within", since = "1.53.0")]
extend_from_within<R>(&mut self, src: R) where R: RangeBounds<usize>,2628753dece8SMiguel Ojeda pub fn extend_from_within<R>(&mut self, src: R)
2629753dece8SMiguel Ojeda where
2630753dece8SMiguel Ojeda R: RangeBounds<usize>,
2631753dece8SMiguel Ojeda {
2632753dece8SMiguel Ojeda let range = slice::range(src, ..self.len());
2633753dece8SMiguel Ojeda self.reserve(range.len());
2634753dece8SMiguel Ojeda
2635753dece8SMiguel Ojeda // SAFETY:
2636753dece8SMiguel Ojeda // - `slice::range` guarantees that the given range is valid for indexing self
2637753dece8SMiguel Ojeda unsafe {
2638753dece8SMiguel Ojeda self.spec_extend_from_within(range);
2639753dece8SMiguel Ojeda }
2640753dece8SMiguel Ojeda }
2641753dece8SMiguel Ojeda }
2642753dece8SMiguel Ojeda
2643753dece8SMiguel Ojeda impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
2644753dece8SMiguel Ojeda /// Takes a `Vec<[T; N]>` and flattens it into a `Vec<T>`.
2645753dece8SMiguel Ojeda ///
2646753dece8SMiguel Ojeda /// # Panics
2647753dece8SMiguel Ojeda ///
2648753dece8SMiguel Ojeda /// Panics if the length of the resulting vector would overflow a `usize`.
2649753dece8SMiguel Ojeda ///
2650753dece8SMiguel Ojeda /// This is only possible when flattening a vector of arrays of zero-sized
2651753dece8SMiguel Ojeda /// types, and thus tends to be irrelevant in practice. If
2652753dece8SMiguel Ojeda /// `size_of::<T>() > 0`, this will never panic.
2653753dece8SMiguel Ojeda ///
2654753dece8SMiguel Ojeda /// # Examples
2655753dece8SMiguel Ojeda ///
2656753dece8SMiguel Ojeda /// ```
2657753dece8SMiguel Ojeda /// #![feature(slice_flatten)]
2658753dece8SMiguel Ojeda ///
2659753dece8SMiguel Ojeda /// let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
2660753dece8SMiguel Ojeda /// assert_eq!(vec.pop(), Some([7, 8, 9]));
2661753dece8SMiguel Ojeda ///
2662753dece8SMiguel Ojeda /// let mut flattened = vec.into_flattened();
2663753dece8SMiguel Ojeda /// assert_eq!(flattened.pop(), Some(6));
2664753dece8SMiguel Ojeda /// ```
2665753dece8SMiguel Ojeda #[unstable(feature = "slice_flatten", issue = "95629")]
into_flattened(self) -> Vec<T, A>2666753dece8SMiguel Ojeda pub fn into_flattened(self) -> Vec<T, A> {
2667753dece8SMiguel Ojeda let (ptr, len, cap, alloc) = self.into_raw_parts_with_alloc();
26683ed03f4dSMiguel Ojeda let (new_len, new_cap) = if T::IS_ZST {
2669753dece8SMiguel Ojeda (len.checked_mul(N).expect("vec len overflow"), usize::MAX)
2670753dece8SMiguel Ojeda } else {
2671753dece8SMiguel Ojeda // SAFETY:
2672753dece8SMiguel Ojeda // - `cap * N` cannot overflow because the allocation is already in
2673753dece8SMiguel Ojeda // the address space.
2674753dece8SMiguel Ojeda // - Each `[T; N]` has `N` valid elements, so there are `len * N`
2675753dece8SMiguel Ojeda // valid elements in the allocation.
2676753dece8SMiguel Ojeda unsafe { (len.unchecked_mul(N), cap.unchecked_mul(N)) }
2677753dece8SMiguel Ojeda };
2678753dece8SMiguel Ojeda // SAFETY:
2679753dece8SMiguel Ojeda // - `ptr` was allocated by `self`
2680753dece8SMiguel Ojeda // - `ptr` is well-aligned because `[T; N]` has the same alignment as `T`.
2681753dece8SMiguel Ojeda // - `new_cap` refers to the same sized allocation as `cap` because
2682753dece8SMiguel Ojeda // `new_cap * size_of::<T>()` == `cap * size_of::<[T; N]>()`
2683753dece8SMiguel Ojeda // - `len` <= `cap`, so `len * N` <= `cap * N`.
2684753dece8SMiguel Ojeda unsafe { Vec::<T, A>::from_raw_parts_in(ptr.cast(), new_len, new_cap, alloc) }
2685753dece8SMiguel Ojeda }
2686753dece8SMiguel Ojeda }
2687753dece8SMiguel Ojeda
26889b33bb25SMiguel Ojeda impl<T: Clone, A: Allocator> Vec<T, A> {
2689753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
26909b33bb25SMiguel Ojeda /// Extend the vector by `n` clones of value.
extend_with(&mut self, n: usize, value: T)26919b33bb25SMiguel Ojeda fn extend_with(&mut self, n: usize, value: T) {
2692753dece8SMiguel Ojeda self.reserve(n);
2693753dece8SMiguel Ojeda
2694753dece8SMiguel Ojeda unsafe {
2695753dece8SMiguel Ojeda let mut ptr = self.as_mut_ptr().add(self.len());
2696753dece8SMiguel Ojeda // Use SetLenOnDrop to work around bug where compiler
2697753dece8SMiguel Ojeda // might not realize the store through `ptr` through self.set_len()
2698753dece8SMiguel Ojeda // don't alias.
2699753dece8SMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len);
2700753dece8SMiguel Ojeda
2701753dece8SMiguel Ojeda // Write all elements except the last one
2702753dece8SMiguel Ojeda for _ in 1..n {
27039b33bb25SMiguel Ojeda ptr::write(ptr, value.clone());
27043ed03f4dSMiguel Ojeda ptr = ptr.add(1);
27059b33bb25SMiguel Ojeda // Increment the length in every step in case clone() panics
2706753dece8SMiguel Ojeda local_len.increment_len(1);
2707753dece8SMiguel Ojeda }
2708753dece8SMiguel Ojeda
2709753dece8SMiguel Ojeda if n > 0 {
2710753dece8SMiguel Ojeda // We can write the last element directly without cloning needlessly
27119b33bb25SMiguel Ojeda ptr::write(ptr, value);
2712753dece8SMiguel Ojeda local_len.increment_len(1);
2713753dece8SMiguel Ojeda }
2714753dece8SMiguel Ojeda
2715753dece8SMiguel Ojeda // len set by scope guard
2716753dece8SMiguel Ojeda }
2717753dece8SMiguel Ojeda }
2718318c3cc8SMiguel Ojeda
27199b33bb25SMiguel Ojeda /// Try to extend the vector by `n` clones of value.
try_extend_with(&mut self, n: usize, value: T) -> Result<(), TryReserveError>27209b33bb25SMiguel Ojeda fn try_extend_with(&mut self, n: usize, value: T) -> Result<(), TryReserveError> {
2721318c3cc8SMiguel Ojeda self.try_reserve(n)?;
2722318c3cc8SMiguel Ojeda
2723318c3cc8SMiguel Ojeda unsafe {
2724318c3cc8SMiguel Ojeda let mut ptr = self.as_mut_ptr().add(self.len());
2725318c3cc8SMiguel Ojeda // Use SetLenOnDrop to work around bug where compiler
2726318c3cc8SMiguel Ojeda // might not realize the store through `ptr` through self.set_len()
2727318c3cc8SMiguel Ojeda // don't alias.
2728318c3cc8SMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len);
2729318c3cc8SMiguel Ojeda
2730318c3cc8SMiguel Ojeda // Write all elements except the last one
2731318c3cc8SMiguel Ojeda for _ in 1..n {
27329b33bb25SMiguel Ojeda ptr::write(ptr, value.clone());
27333ed03f4dSMiguel Ojeda ptr = ptr.add(1);
27349b33bb25SMiguel Ojeda // Increment the length in every step in case clone() panics
2735318c3cc8SMiguel Ojeda local_len.increment_len(1);
2736318c3cc8SMiguel Ojeda }
2737318c3cc8SMiguel Ojeda
2738318c3cc8SMiguel Ojeda if n > 0 {
2739318c3cc8SMiguel Ojeda // We can write the last element directly without cloning needlessly
27409b33bb25SMiguel Ojeda ptr::write(ptr, value);
2741318c3cc8SMiguel Ojeda local_len.increment_len(1);
2742318c3cc8SMiguel Ojeda }
2743318c3cc8SMiguel Ojeda
2744318c3cc8SMiguel Ojeda // len set by scope guard
2745318c3cc8SMiguel Ojeda Ok(())
2746318c3cc8SMiguel Ojeda }
2747318c3cc8SMiguel Ojeda }
2748753dece8SMiguel Ojeda }
2749753dece8SMiguel Ojeda
2750753dece8SMiguel Ojeda impl<T: PartialEq, A: Allocator> Vec<T, A> {
2751753dece8SMiguel Ojeda /// Removes consecutive repeated elements in the vector according to the
2752753dece8SMiguel Ojeda /// [`PartialEq`] trait implementation.
2753753dece8SMiguel Ojeda ///
2754753dece8SMiguel Ojeda /// If the vector is sorted, this removes all duplicates.
2755753dece8SMiguel Ojeda ///
2756753dece8SMiguel Ojeda /// # Examples
2757753dece8SMiguel Ojeda ///
2758753dece8SMiguel Ojeda /// ```
2759753dece8SMiguel Ojeda /// let mut vec = vec![1, 2, 2, 3, 2];
2760753dece8SMiguel Ojeda ///
2761753dece8SMiguel Ojeda /// vec.dedup();
2762753dece8SMiguel Ojeda ///
2763753dece8SMiguel Ojeda /// assert_eq!(vec, [1, 2, 3, 2]);
2764753dece8SMiguel Ojeda /// ```
2765753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2766753dece8SMiguel Ojeda #[inline]
dedup(&mut self)2767753dece8SMiguel Ojeda pub fn dedup(&mut self) {
2768753dece8SMiguel Ojeda self.dedup_by(|a, b| a == b)
2769753dece8SMiguel Ojeda }
2770753dece8SMiguel Ojeda }
2771753dece8SMiguel Ojeda
2772753dece8SMiguel Ojeda ////////////////////////////////////////////////////////////////////////////////
2773753dece8SMiguel Ojeda // Internal methods and functions
2774753dece8SMiguel Ojeda ////////////////////////////////////////////////////////////////////////////////
2775753dece8SMiguel Ojeda
2776753dece8SMiguel Ojeda #[doc(hidden)]
2777753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2778753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
from_elem<T: Clone>(elem: T, n: usize) -> Vec<T>2779753dece8SMiguel Ojeda pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
2780753dece8SMiguel Ojeda <T as SpecFromElem>::from_elem(elem, n, Global)
2781753dece8SMiguel Ojeda }
2782753dece8SMiguel Ojeda
2783753dece8SMiguel Ojeda #[doc(hidden)]
2784753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2785753dece8SMiguel Ojeda #[unstable(feature = "allocator_api", issue = "32838")]
from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A>2786753dece8SMiguel Ojeda pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> {
2787753dece8SMiguel Ojeda <T as SpecFromElem>::from_elem(elem, n, alloc)
2788753dece8SMiguel Ojeda }
2789753dece8SMiguel Ojeda
2790753dece8SMiguel Ojeda trait ExtendFromWithinSpec {
2791753dece8SMiguel Ojeda /// # Safety
2792753dece8SMiguel Ojeda ///
2793753dece8SMiguel Ojeda /// - `src` needs to be valid index
2794753dece8SMiguel Ojeda /// - `self.capacity() - self.len()` must be `>= src.len()`
spec_extend_from_within(&mut self, src: Range<usize>)2795753dece8SMiguel Ojeda unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
2796753dece8SMiguel Ojeda }
2797753dece8SMiguel Ojeda
2798753dece8SMiguel Ojeda impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
spec_extend_from_within(&mut self, src: Range<usize>)2799753dece8SMiguel Ojeda default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
2800753dece8SMiguel Ojeda // SAFETY:
2801753dece8SMiguel Ojeda // - len is increased only after initializing elements
2802753dece8SMiguel Ojeda let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() };
2803753dece8SMiguel Ojeda
2804753dece8SMiguel Ojeda // SAFETY:
28053ed03f4dSMiguel Ojeda // - caller guarantees that src is a valid index
2806753dece8SMiguel Ojeda let to_clone = unsafe { this.get_unchecked(src) };
2807753dece8SMiguel Ojeda
2808753dece8SMiguel Ojeda iter::zip(to_clone, spare)
2809753dece8SMiguel Ojeda .map(|(src, dst)| dst.write(src.clone()))
2810753dece8SMiguel Ojeda // Note:
2811753dece8SMiguel Ojeda // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len
2812753dece8SMiguel Ojeda // - len is increased after each element to prevent leaks (see issue #82533)
2813753dece8SMiguel Ojeda .for_each(|_| *len += 1);
2814753dece8SMiguel Ojeda }
2815753dece8SMiguel Ojeda }
2816753dece8SMiguel Ojeda
2817753dece8SMiguel Ojeda impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
spec_extend_from_within(&mut self, src: Range<usize>)2818753dece8SMiguel Ojeda unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
2819753dece8SMiguel Ojeda let count = src.len();
2820753dece8SMiguel Ojeda {
2821753dece8SMiguel Ojeda let (init, spare) = self.split_at_spare_mut();
2822753dece8SMiguel Ojeda
2823753dece8SMiguel Ojeda // SAFETY:
28243ed03f4dSMiguel Ojeda // - caller guarantees that `src` is a valid index
2825753dece8SMiguel Ojeda let source = unsafe { init.get_unchecked(src) };
2826753dece8SMiguel Ojeda
2827753dece8SMiguel Ojeda // SAFETY:
2828753dece8SMiguel Ojeda // - Both pointers are created from unique slice references (`&mut [_]`)
2829753dece8SMiguel Ojeda // so they are valid and do not overlap.
28303ed03f4dSMiguel Ojeda // - Elements are :Copy so it's OK to copy them, without doing
2831753dece8SMiguel Ojeda // anything with the original values
2832753dece8SMiguel Ojeda // - `count` is equal to the len of `source`, so source is valid for
2833753dece8SMiguel Ojeda // `count` reads
2834753dece8SMiguel Ojeda // - `.reserve(count)` guarantees that `spare.len() >= count` so spare
2835753dece8SMiguel Ojeda // is valid for `count` writes
2836753dece8SMiguel Ojeda unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) };
2837753dece8SMiguel Ojeda }
2838753dece8SMiguel Ojeda
2839753dece8SMiguel Ojeda // SAFETY:
2840753dece8SMiguel Ojeda // - The elements were just initialized by `copy_nonoverlapping`
2841753dece8SMiguel Ojeda self.len += count;
2842753dece8SMiguel Ojeda }
2843753dece8SMiguel Ojeda }
2844753dece8SMiguel Ojeda
2845753dece8SMiguel Ojeda ////////////////////////////////////////////////////////////////////////////////
2846753dece8SMiguel Ojeda // Common trait implementations for Vec
2847753dece8SMiguel Ojeda ////////////////////////////////////////////////////////////////////////////////
2848753dece8SMiguel Ojeda
2849753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2850753dece8SMiguel Ojeda impl<T, A: Allocator> ops::Deref for Vec<T, A> {
2851753dece8SMiguel Ojeda type Target = [T];
2852753dece8SMiguel Ojeda
28533ed03f4dSMiguel Ojeda #[inline]
deref(&self) -> &[T]2854753dece8SMiguel Ojeda fn deref(&self) -> &[T] {
2855753dece8SMiguel Ojeda unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
2856753dece8SMiguel Ojeda }
2857753dece8SMiguel Ojeda }
2858753dece8SMiguel Ojeda
2859753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2860753dece8SMiguel Ojeda impl<T, A: Allocator> ops::DerefMut for Vec<T, A> {
28613ed03f4dSMiguel Ojeda #[inline]
deref_mut(&mut self) -> &mut [T]2862753dece8SMiguel Ojeda fn deref_mut(&mut self) -> &mut [T] {
2863753dece8SMiguel Ojeda unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
2864753dece8SMiguel Ojeda }
2865753dece8SMiguel Ojeda }
2866753dece8SMiguel Ojeda
2867753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2868753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2869753dece8SMiguel Ojeda impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
2870753dece8SMiguel Ojeda #[cfg(not(test))]
clone(&self) -> Self2871753dece8SMiguel Ojeda fn clone(&self) -> Self {
2872753dece8SMiguel Ojeda let alloc = self.allocator().clone();
2873753dece8SMiguel Ojeda <[T]>::to_vec_in(&**self, alloc)
2874753dece8SMiguel Ojeda }
2875753dece8SMiguel Ojeda
2876753dece8SMiguel Ojeda // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
2877753dece8SMiguel Ojeda // required for this method definition, is not available. Instead use the
2878753dece8SMiguel Ojeda // `slice::to_vec` function which is only available with cfg(test)
2879753dece8SMiguel Ojeda // NB see the slice::hack module in slice.rs for more information
2880753dece8SMiguel Ojeda #[cfg(test)]
clone(&self) -> Self2881753dece8SMiguel Ojeda fn clone(&self) -> Self {
2882753dece8SMiguel Ojeda let alloc = self.allocator().clone();
2883753dece8SMiguel Ojeda crate::slice::to_vec(&**self, alloc)
2884753dece8SMiguel Ojeda }
2885753dece8SMiguel Ojeda
clone_from(&mut self, other: &Self)2886753dece8SMiguel Ojeda fn clone_from(&mut self, other: &Self) {
288789eed1abSMiguel Ojeda crate::slice::SpecCloneIntoVec::clone_into(other.as_slice(), self);
2888753dece8SMiguel Ojeda }
2889753dece8SMiguel Ojeda }
2890753dece8SMiguel Ojeda
2891753dece8SMiguel Ojeda /// The hash of a vector is the same as that of the corresponding slice,
2892753dece8SMiguel Ojeda /// as required by the `core::borrow::Borrow` implementation.
2893753dece8SMiguel Ojeda ///
2894753dece8SMiguel Ojeda /// ```
2895753dece8SMiguel Ojeda /// use std::hash::BuildHasher;
2896753dece8SMiguel Ojeda ///
2897753dece8SMiguel Ojeda /// let b = std::collections::hash_map::RandomState::new();
2898753dece8SMiguel Ojeda /// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09];
2899753dece8SMiguel Ojeda /// let s: &[u8] = &[0xa8, 0x3c, 0x09];
2900753dece8SMiguel Ojeda /// assert_eq!(b.hash_one(v), b.hash_one(s));
2901753dece8SMiguel Ojeda /// ```
2902753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2903753dece8SMiguel Ojeda impl<T: Hash, A: Allocator> Hash for Vec<T, A> {
2904753dece8SMiguel Ojeda #[inline]
hash<H: Hasher>(&self, state: &mut H)2905753dece8SMiguel Ojeda fn hash<H: Hasher>(&self, state: &mut H) {
2906753dece8SMiguel Ojeda Hash::hash(&**self, state)
2907753dece8SMiguel Ojeda }
2908753dece8SMiguel Ojeda }
2909753dece8SMiguel Ojeda
2910753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2911753dece8SMiguel Ojeda #[rustc_on_unimplemented(
2912753dece8SMiguel Ojeda message = "vector indices are of type `usize` or ranges of `usize`",
2913753dece8SMiguel Ojeda label = "vector indices are of type `usize` or ranges of `usize`"
2914753dece8SMiguel Ojeda )]
2915753dece8SMiguel Ojeda impl<T, I: SliceIndex<[T]>, A: Allocator> Index<I> for Vec<T, A> {
2916753dece8SMiguel Ojeda type Output = I::Output;
2917753dece8SMiguel Ojeda
2918753dece8SMiguel Ojeda #[inline]
index(&self, index: I) -> &Self::Output2919753dece8SMiguel Ojeda fn index(&self, index: I) -> &Self::Output {
2920753dece8SMiguel Ojeda Index::index(&**self, index)
2921753dece8SMiguel Ojeda }
2922753dece8SMiguel Ojeda }
2923753dece8SMiguel Ojeda
2924753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2925753dece8SMiguel Ojeda #[rustc_on_unimplemented(
2926753dece8SMiguel Ojeda message = "vector indices are of type `usize` or ranges of `usize`",
2927753dece8SMiguel Ojeda label = "vector indices are of type `usize` or ranges of `usize`"
2928753dece8SMiguel Ojeda )]
2929753dece8SMiguel Ojeda impl<T, I: SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> {
2930753dece8SMiguel Ojeda #[inline]
index_mut(&mut self, index: I) -> &mut Self::Output2931753dece8SMiguel Ojeda fn index_mut(&mut self, index: I) -> &mut Self::Output {
2932753dece8SMiguel Ojeda IndexMut::index_mut(&mut **self, index)
2933753dece8SMiguel Ojeda }
2934753dece8SMiguel Ojeda }
2935753dece8SMiguel Ojeda
2936753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
2937753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2938753dece8SMiguel Ojeda impl<T> FromIterator<T> for Vec<T> {
2939753dece8SMiguel Ojeda #[inline]
from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T>2940753dece8SMiguel Ojeda fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
2941753dece8SMiguel Ojeda <Self as SpecFromIter<T, I::IntoIter>>::from_iter(iter.into_iter())
2942753dece8SMiguel Ojeda }
2943753dece8SMiguel Ojeda }
2944753dece8SMiguel Ojeda
2945753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2946753dece8SMiguel Ojeda impl<T, A: Allocator> IntoIterator for Vec<T, A> {
2947753dece8SMiguel Ojeda type Item = T;
2948753dece8SMiguel Ojeda type IntoIter = IntoIter<T, A>;
2949753dece8SMiguel Ojeda
2950753dece8SMiguel Ojeda /// Creates a consuming iterator, that is, one that moves each value out of
2951753dece8SMiguel Ojeda /// the vector (from start to end). The vector cannot be used after calling
2952753dece8SMiguel Ojeda /// this.
2953753dece8SMiguel Ojeda ///
2954753dece8SMiguel Ojeda /// # Examples
2955753dece8SMiguel Ojeda ///
2956753dece8SMiguel Ojeda /// ```
2957753dece8SMiguel Ojeda /// let v = vec!["a".to_string(), "b".to_string()];
29583ed03f4dSMiguel Ojeda /// let mut v_iter = v.into_iter();
29593ed03f4dSMiguel Ojeda ///
29603ed03f4dSMiguel Ojeda /// let first_element: Option<String> = v_iter.next();
29613ed03f4dSMiguel Ojeda ///
29623ed03f4dSMiguel Ojeda /// assert_eq!(first_element, Some("a".to_string()));
29633ed03f4dSMiguel Ojeda /// assert_eq!(v_iter.next(), Some("b".to_string()));
29643ed03f4dSMiguel Ojeda /// assert_eq!(v_iter.next(), None);
2965753dece8SMiguel Ojeda /// ```
2966753dece8SMiguel Ojeda #[inline]
into_iter(self) -> Self::IntoIter29673ed03f4dSMiguel Ojeda fn into_iter(self) -> Self::IntoIter {
2968753dece8SMiguel Ojeda unsafe {
2969753dece8SMiguel Ojeda let mut me = ManuallyDrop::new(self);
2970753dece8SMiguel Ojeda let alloc = ManuallyDrop::new(ptr::read(me.allocator()));
2971753dece8SMiguel Ojeda let begin = me.as_mut_ptr();
29723ed03f4dSMiguel Ojeda let end = if T::IS_ZST {
29733ed03f4dSMiguel Ojeda begin.wrapping_byte_add(me.len())
2974753dece8SMiguel Ojeda } else {
2975753dece8SMiguel Ojeda begin.add(me.len()) as *const T
2976753dece8SMiguel Ojeda };
2977753dece8SMiguel Ojeda let cap = me.buf.capacity();
2978753dece8SMiguel Ojeda IntoIter {
2979753dece8SMiguel Ojeda buf: NonNull::new_unchecked(begin),
2980753dece8SMiguel Ojeda phantom: PhantomData,
2981753dece8SMiguel Ojeda cap,
2982753dece8SMiguel Ojeda alloc,
2983753dece8SMiguel Ojeda ptr: begin,
2984753dece8SMiguel Ojeda end,
2985753dece8SMiguel Ojeda }
2986753dece8SMiguel Ojeda }
2987753dece8SMiguel Ojeda }
2988753dece8SMiguel Ojeda }
2989753dece8SMiguel Ojeda
2990753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
2991753dece8SMiguel Ojeda impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> {
2992753dece8SMiguel Ojeda type Item = &'a T;
2993753dece8SMiguel Ojeda type IntoIter = slice::Iter<'a, T>;
2994753dece8SMiguel Ojeda
into_iter(self) -> Self::IntoIter29953ed03f4dSMiguel Ojeda fn into_iter(self) -> Self::IntoIter {
2996753dece8SMiguel Ojeda self.iter()
2997753dece8SMiguel Ojeda }
2998753dece8SMiguel Ojeda }
2999753dece8SMiguel Ojeda
3000753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3001753dece8SMiguel Ojeda impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> {
3002753dece8SMiguel Ojeda type Item = &'a mut T;
3003753dece8SMiguel Ojeda type IntoIter = slice::IterMut<'a, T>;
3004753dece8SMiguel Ojeda
into_iter(self) -> Self::IntoIter30053ed03f4dSMiguel Ojeda fn into_iter(self) -> Self::IntoIter {
3006753dece8SMiguel Ojeda self.iter_mut()
3007753dece8SMiguel Ojeda }
3008753dece8SMiguel Ojeda }
3009753dece8SMiguel Ojeda
3010753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3011753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3012753dece8SMiguel Ojeda impl<T, A: Allocator> Extend<T> for Vec<T, A> {
3013753dece8SMiguel Ojeda #[inline]
extend<I: IntoIterator<Item = T>>(&mut self, iter: I)3014753dece8SMiguel Ojeda fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
3015753dece8SMiguel Ojeda <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
3016753dece8SMiguel Ojeda }
3017753dece8SMiguel Ojeda
3018753dece8SMiguel Ojeda #[inline]
extend_one(&mut self, item: T)3019753dece8SMiguel Ojeda fn extend_one(&mut self, item: T) {
3020753dece8SMiguel Ojeda self.push(item);
3021753dece8SMiguel Ojeda }
3022753dece8SMiguel Ojeda
3023753dece8SMiguel Ojeda #[inline]
extend_reserve(&mut self, additional: usize)3024753dece8SMiguel Ojeda fn extend_reserve(&mut self, additional: usize) {
3025753dece8SMiguel Ojeda self.reserve(additional);
3026753dece8SMiguel Ojeda }
3027753dece8SMiguel Ojeda }
3028753dece8SMiguel Ojeda
3029753dece8SMiguel Ojeda impl<T, A: Allocator> Vec<T, A> {
3030753dece8SMiguel Ojeda // leaf method to which various SpecFrom/SpecExtend implementations delegate when
3031753dece8SMiguel Ojeda // they have no further optimizations to apply
3032753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I)3033753dece8SMiguel Ojeda fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
3034753dece8SMiguel Ojeda // This is the case for a general iterator.
3035753dece8SMiguel Ojeda //
3036753dece8SMiguel Ojeda // This function should be the moral equivalent of:
3037753dece8SMiguel Ojeda //
3038753dece8SMiguel Ojeda // for item in iterator {
3039753dece8SMiguel Ojeda // self.push(item);
3040753dece8SMiguel Ojeda // }
3041753dece8SMiguel Ojeda while let Some(element) = iterator.next() {
3042753dece8SMiguel Ojeda let len = self.len();
3043753dece8SMiguel Ojeda if len == self.capacity() {
3044753dece8SMiguel Ojeda let (lower, _) = iterator.size_hint();
3045753dece8SMiguel Ojeda self.reserve(lower.saturating_add(1));
3046753dece8SMiguel Ojeda }
3047753dece8SMiguel Ojeda unsafe {
3048753dece8SMiguel Ojeda ptr::write(self.as_mut_ptr().add(len), element);
3049753dece8SMiguel Ojeda // Since next() executes user code which can panic we have to bump the length
3050753dece8SMiguel Ojeda // after each step.
3051753dece8SMiguel Ojeda // NB can't overflow since we would have had to alloc the address space
3052753dece8SMiguel Ojeda self.set_len(len + 1);
3053753dece8SMiguel Ojeda }
3054753dece8SMiguel Ojeda }
3055753dece8SMiguel Ojeda }
3056753dece8SMiguel Ojeda
3057318c3cc8SMiguel Ojeda // leaf method to which various SpecFrom/SpecExtend implementations delegate when
3058318c3cc8SMiguel Ojeda // they have no further optimizations to apply
try_extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) -> Result<(), TryReserveError>3059318c3cc8SMiguel Ojeda fn try_extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) -> Result<(), TryReserveError> {
3060318c3cc8SMiguel Ojeda // This is the case for a general iterator.
3061318c3cc8SMiguel Ojeda //
3062318c3cc8SMiguel Ojeda // This function should be the moral equivalent of:
3063318c3cc8SMiguel Ojeda //
3064318c3cc8SMiguel Ojeda // for item in iterator {
3065318c3cc8SMiguel Ojeda // self.push(item);
3066318c3cc8SMiguel Ojeda // }
3067318c3cc8SMiguel Ojeda while let Some(element) = iterator.next() {
3068318c3cc8SMiguel Ojeda let len = self.len();
3069318c3cc8SMiguel Ojeda if len == self.capacity() {
3070318c3cc8SMiguel Ojeda let (lower, _) = iterator.size_hint();
3071318c3cc8SMiguel Ojeda self.try_reserve(lower.saturating_add(1))?;
3072318c3cc8SMiguel Ojeda }
3073318c3cc8SMiguel Ojeda unsafe {
3074318c3cc8SMiguel Ojeda ptr::write(self.as_mut_ptr().add(len), element);
3075318c3cc8SMiguel Ojeda // Since next() executes user code which can panic we have to bump the length
3076318c3cc8SMiguel Ojeda // after each step.
3077318c3cc8SMiguel Ojeda // NB can't overflow since we would have had to alloc the address space
3078318c3cc8SMiguel Ojeda self.set_len(len + 1);
3079318c3cc8SMiguel Ojeda }
3080318c3cc8SMiguel Ojeda }
3081318c3cc8SMiguel Ojeda
3082318c3cc8SMiguel Ojeda Ok(())
3083318c3cc8SMiguel Ojeda }
3084318c3cc8SMiguel Ojeda
30853ed03f4dSMiguel Ojeda // specific extend for `TrustedLen` iterators, called both by the specializations
30863ed03f4dSMiguel Ojeda // and internal places where resolving specialization makes compilation slower
30873ed03f4dSMiguel Ojeda #[cfg(not(no_global_oom_handling))]
extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>)30883ed03f4dSMiguel Ojeda fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) {
30893ed03f4dSMiguel Ojeda let (low, high) = iterator.size_hint();
30903ed03f4dSMiguel Ojeda if let Some(additional) = high {
30913ed03f4dSMiguel Ojeda debug_assert_eq!(
30923ed03f4dSMiguel Ojeda low,
30933ed03f4dSMiguel Ojeda additional,
30943ed03f4dSMiguel Ojeda "TrustedLen iterator's size hint is not exact: {:?}",
30953ed03f4dSMiguel Ojeda (low, high)
30963ed03f4dSMiguel Ojeda );
30973ed03f4dSMiguel Ojeda self.reserve(additional);
30983ed03f4dSMiguel Ojeda unsafe {
30993ed03f4dSMiguel Ojeda let ptr = self.as_mut_ptr();
31003ed03f4dSMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len);
31013ed03f4dSMiguel Ojeda iterator.for_each(move |element| {
31023ed03f4dSMiguel Ojeda ptr::write(ptr.add(local_len.current_len()), element);
31033ed03f4dSMiguel Ojeda // Since the loop executes user code which can panic we have to update
31043ed03f4dSMiguel Ojeda // the length every step to correctly drop what we've written.
31053ed03f4dSMiguel Ojeda // NB can't overflow since we would have had to alloc the address space
31063ed03f4dSMiguel Ojeda local_len.increment_len(1);
31073ed03f4dSMiguel Ojeda });
31083ed03f4dSMiguel Ojeda }
31093ed03f4dSMiguel Ojeda } else {
31103ed03f4dSMiguel Ojeda // Per TrustedLen contract a `None` upper bound means that the iterator length
31113ed03f4dSMiguel Ojeda // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway.
31123ed03f4dSMiguel Ojeda // Since the other branch already panics eagerly (via `reserve()`) we do the same here.
31133ed03f4dSMiguel Ojeda // This avoids additional codegen for a fallback code path which would eventually
31143ed03f4dSMiguel Ojeda // panic anyway.
31153ed03f4dSMiguel Ojeda panic!("capacity overflow");
31163ed03f4dSMiguel Ojeda }
31173ed03f4dSMiguel Ojeda }
31183ed03f4dSMiguel Ojeda
31193ed03f4dSMiguel Ojeda // specific extend for `TrustedLen` iterators, called both by the specializations
31203ed03f4dSMiguel Ojeda // and internal places where resolving specialization makes compilation slower
try_extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) -> Result<(), TryReserveError>31213ed03f4dSMiguel Ojeda fn try_extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) -> Result<(), TryReserveError> {
31223ed03f4dSMiguel Ojeda let (low, high) = iterator.size_hint();
31233ed03f4dSMiguel Ojeda if let Some(additional) = high {
31243ed03f4dSMiguel Ojeda debug_assert_eq!(
31253ed03f4dSMiguel Ojeda low,
31263ed03f4dSMiguel Ojeda additional,
31273ed03f4dSMiguel Ojeda "TrustedLen iterator's size hint is not exact: {:?}",
31283ed03f4dSMiguel Ojeda (low, high)
31293ed03f4dSMiguel Ojeda );
31303ed03f4dSMiguel Ojeda self.try_reserve(additional)?;
31313ed03f4dSMiguel Ojeda unsafe {
31323ed03f4dSMiguel Ojeda let ptr = self.as_mut_ptr();
31333ed03f4dSMiguel Ojeda let mut local_len = SetLenOnDrop::new(&mut self.len);
31343ed03f4dSMiguel Ojeda iterator.for_each(move |element| {
31353ed03f4dSMiguel Ojeda ptr::write(ptr.add(local_len.current_len()), element);
31363ed03f4dSMiguel Ojeda // Since the loop executes user code which can panic we have to update
31373ed03f4dSMiguel Ojeda // the length every step to correctly drop what we've written.
31383ed03f4dSMiguel Ojeda // NB can't overflow since we would have had to alloc the address space
31393ed03f4dSMiguel Ojeda local_len.increment_len(1);
31403ed03f4dSMiguel Ojeda });
31413ed03f4dSMiguel Ojeda }
31423ed03f4dSMiguel Ojeda Ok(())
31433ed03f4dSMiguel Ojeda } else {
31443ed03f4dSMiguel Ojeda Err(TryReserveErrorKind::CapacityOverflow.into())
31453ed03f4dSMiguel Ojeda }
31463ed03f4dSMiguel Ojeda }
31473ed03f4dSMiguel Ojeda
3148753dece8SMiguel Ojeda /// Creates a splicing iterator that replaces the specified range in the vector
3149753dece8SMiguel Ojeda /// with the given `replace_with` iterator and yields the removed items.
3150753dece8SMiguel Ojeda /// `replace_with` does not need to be the same length as `range`.
3151753dece8SMiguel Ojeda ///
3152753dece8SMiguel Ojeda /// `range` is removed even if the iterator is not consumed until the end.
3153753dece8SMiguel Ojeda ///
3154753dece8SMiguel Ojeda /// It is unspecified how many elements are removed from the vector
3155753dece8SMiguel Ojeda /// if the `Splice` value is leaked.
3156753dece8SMiguel Ojeda ///
3157753dece8SMiguel Ojeda /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
3158753dece8SMiguel Ojeda ///
3159753dece8SMiguel Ojeda /// This is optimal if:
3160753dece8SMiguel Ojeda ///
3161753dece8SMiguel Ojeda /// * The tail (elements in the vector after `range`) is empty,
3162753dece8SMiguel Ojeda /// * or `replace_with` yields fewer or equal elements than `range`’s length
3163753dece8SMiguel Ojeda /// * or the lower bound of its `size_hint()` is exact.
3164753dece8SMiguel Ojeda ///
3165753dece8SMiguel Ojeda /// Otherwise, a temporary vector is allocated and the tail is moved twice.
3166753dece8SMiguel Ojeda ///
3167753dece8SMiguel Ojeda /// # Panics
3168753dece8SMiguel Ojeda ///
3169753dece8SMiguel Ojeda /// Panics if the starting point is greater than the end point or if
3170753dece8SMiguel Ojeda /// the end point is greater than the length of the vector.
3171753dece8SMiguel Ojeda ///
3172753dece8SMiguel Ojeda /// # Examples
3173753dece8SMiguel Ojeda ///
3174753dece8SMiguel Ojeda /// ```
3175753dece8SMiguel Ojeda /// let mut v = vec![1, 2, 3, 4];
3176753dece8SMiguel Ojeda /// let new = [7, 8, 9];
3177753dece8SMiguel Ojeda /// let u: Vec<_> = v.splice(1..3, new).collect();
3178753dece8SMiguel Ojeda /// assert_eq!(v, &[1, 7, 8, 9, 4]);
3179753dece8SMiguel Ojeda /// assert_eq!(u, &[2, 3]);
3180753dece8SMiguel Ojeda /// ```
3181753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3182753dece8SMiguel Ojeda #[inline]
3183753dece8SMiguel Ojeda #[stable(feature = "vec_splice", since = "1.21.0")]
splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A> where R: RangeBounds<usize>, I: IntoIterator<Item = T>,3184753dece8SMiguel Ojeda pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
3185753dece8SMiguel Ojeda where
3186753dece8SMiguel Ojeda R: RangeBounds<usize>,
3187753dece8SMiguel Ojeda I: IntoIterator<Item = T>,
3188753dece8SMiguel Ojeda {
3189753dece8SMiguel Ojeda Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
3190753dece8SMiguel Ojeda }
3191753dece8SMiguel Ojeda
3192753dece8SMiguel Ojeda /// Creates an iterator which uses a closure to determine if an element should be removed.
3193753dece8SMiguel Ojeda ///
3194753dece8SMiguel Ojeda /// If the closure returns true, then the element is removed and yielded.
3195753dece8SMiguel Ojeda /// If the closure returns false, the element will remain in the vector and will not be yielded
3196753dece8SMiguel Ojeda /// by the iterator.
3197753dece8SMiguel Ojeda ///
31989b33bb25SMiguel Ojeda /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
31999b33bb25SMiguel Ojeda /// or the iteration short-circuits, then the remaining elements will be retained.
32009b33bb25SMiguel Ojeda /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
32019b33bb25SMiguel Ojeda ///
32029b33bb25SMiguel Ojeda /// [`retain`]: Vec::retain
32039b33bb25SMiguel Ojeda ///
3204753dece8SMiguel Ojeda /// Using this method is equivalent to the following code:
3205753dece8SMiguel Ojeda ///
3206753dece8SMiguel Ojeda /// ```
3207753dece8SMiguel Ojeda /// # let some_predicate = |x: &mut i32| { *x == 2 || *x == 3 || *x == 6 };
3208753dece8SMiguel Ojeda /// # let mut vec = vec![1, 2, 3, 4, 5, 6];
3209753dece8SMiguel Ojeda /// let mut i = 0;
3210753dece8SMiguel Ojeda /// while i < vec.len() {
3211753dece8SMiguel Ojeda /// if some_predicate(&mut vec[i]) {
3212753dece8SMiguel Ojeda /// let val = vec.remove(i);
3213753dece8SMiguel Ojeda /// // your code here
3214753dece8SMiguel Ojeda /// } else {
3215753dece8SMiguel Ojeda /// i += 1;
3216753dece8SMiguel Ojeda /// }
3217753dece8SMiguel Ojeda /// }
3218753dece8SMiguel Ojeda ///
3219753dece8SMiguel Ojeda /// # assert_eq!(vec, vec![1, 4, 5]);
3220753dece8SMiguel Ojeda /// ```
3221753dece8SMiguel Ojeda ///
32229b33bb25SMiguel Ojeda /// But `extract_if` is easier to use. `extract_if` is also more efficient,
3223753dece8SMiguel Ojeda /// because it can backshift the elements of the array in bulk.
3224753dece8SMiguel Ojeda ///
32259b33bb25SMiguel Ojeda /// Note that `extract_if` also lets you mutate every element in the filter closure,
3226753dece8SMiguel Ojeda /// regardless of whether you choose to keep or remove it.
3227753dece8SMiguel Ojeda ///
3228753dece8SMiguel Ojeda /// # Examples
3229753dece8SMiguel Ojeda ///
3230753dece8SMiguel Ojeda /// Splitting an array into evens and odds, reusing the original allocation:
3231753dece8SMiguel Ojeda ///
3232753dece8SMiguel Ojeda /// ```
32339b33bb25SMiguel Ojeda /// #![feature(extract_if)]
3234753dece8SMiguel Ojeda /// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];
3235753dece8SMiguel Ojeda ///
32369b33bb25SMiguel Ojeda /// let evens = numbers.extract_if(|x| *x % 2 == 0).collect::<Vec<_>>();
3237753dece8SMiguel Ojeda /// let odds = numbers;
3238753dece8SMiguel Ojeda ///
3239753dece8SMiguel Ojeda /// assert_eq!(evens, vec![2, 4, 6, 8, 14]);
3240753dece8SMiguel Ojeda /// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]);
3241753dece8SMiguel Ojeda /// ```
32429b33bb25SMiguel Ojeda #[unstable(feature = "extract_if", reason = "recently added", issue = "43244")]
extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A> where F: FnMut(&mut T) -> bool,32439b33bb25SMiguel Ojeda pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
3244753dece8SMiguel Ojeda where
3245753dece8SMiguel Ojeda F: FnMut(&mut T) -> bool,
3246753dece8SMiguel Ojeda {
3247753dece8SMiguel Ojeda let old_len = self.len();
3248753dece8SMiguel Ojeda
3249753dece8SMiguel Ojeda // Guard against us getting leaked (leak amplification)
3250753dece8SMiguel Ojeda unsafe {
3251753dece8SMiguel Ojeda self.set_len(0);
3252753dece8SMiguel Ojeda }
3253753dece8SMiguel Ojeda
32549b33bb25SMiguel Ojeda ExtractIf { vec: self, idx: 0, del: 0, old_len, pred: filter }
3255753dece8SMiguel Ojeda }
3256753dece8SMiguel Ojeda }
3257753dece8SMiguel Ojeda
3258753dece8SMiguel Ojeda /// Extend implementation that copies elements out of references before pushing them onto the Vec.
3259753dece8SMiguel Ojeda ///
3260753dece8SMiguel Ojeda /// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
3261753dece8SMiguel Ojeda /// append the entire slice at once.
3262753dece8SMiguel Ojeda ///
3263753dece8SMiguel Ojeda /// [`copy_from_slice`]: slice::copy_from_slice
3264753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3265753dece8SMiguel Ojeda #[stable(feature = "extend_ref", since = "1.2.0")]
3266*73596f5aSMiguel Ojeda impl<'a, T: Copy + 'a, A: Allocator> Extend<&'a T> for Vec<T, A> {
extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)3267753dece8SMiguel Ojeda fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
3268753dece8SMiguel Ojeda self.spec_extend(iter.into_iter())
3269753dece8SMiguel Ojeda }
3270753dece8SMiguel Ojeda
3271753dece8SMiguel Ojeda #[inline]
extend_one(&mut self, &item: &'a T)3272753dece8SMiguel Ojeda fn extend_one(&mut self, &item: &'a T) {
3273753dece8SMiguel Ojeda self.push(item);
3274753dece8SMiguel Ojeda }
3275753dece8SMiguel Ojeda
3276753dece8SMiguel Ojeda #[inline]
extend_reserve(&mut self, additional: usize)3277753dece8SMiguel Ojeda fn extend_reserve(&mut self, additional: usize) {
3278753dece8SMiguel Ojeda self.reserve(additional);
3279753dece8SMiguel Ojeda }
3280753dece8SMiguel Ojeda }
3281753dece8SMiguel Ojeda
328289eed1abSMiguel Ojeda /// Implements comparison of vectors, [lexicographically](Ord#lexicographical-comparison).
3283753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
32849b33bb25SMiguel Ojeda impl<T, A1, A2> PartialOrd<Vec<T, A2>> for Vec<T, A1>
32859b33bb25SMiguel Ojeda where
32869b33bb25SMiguel Ojeda T: PartialOrd,
32879b33bb25SMiguel Ojeda A1: Allocator,
32889b33bb25SMiguel Ojeda A2: Allocator,
32899b33bb25SMiguel Ojeda {
3290753dece8SMiguel Ojeda #[inline]
partial_cmp(&self, other: &Vec<T, A2>) -> Option<Ordering>32919b33bb25SMiguel Ojeda fn partial_cmp(&self, other: &Vec<T, A2>) -> Option<Ordering> {
3292753dece8SMiguel Ojeda PartialOrd::partial_cmp(&**self, &**other)
3293753dece8SMiguel Ojeda }
3294753dece8SMiguel Ojeda }
3295753dece8SMiguel Ojeda
3296753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3297753dece8SMiguel Ojeda impl<T: Eq, A: Allocator> Eq for Vec<T, A> {}
3298753dece8SMiguel Ojeda
329989eed1abSMiguel Ojeda /// Implements ordering of vectors, [lexicographically](Ord#lexicographical-comparison).
3300753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3301753dece8SMiguel Ojeda impl<T: Ord, A: Allocator> Ord for Vec<T, A> {
3302753dece8SMiguel Ojeda #[inline]
cmp(&self, other: &Self) -> Ordering3303753dece8SMiguel Ojeda fn cmp(&self, other: &Self) -> Ordering {
3304753dece8SMiguel Ojeda Ord::cmp(&**self, &**other)
3305753dece8SMiguel Ojeda }
3306753dece8SMiguel Ojeda }
3307753dece8SMiguel Ojeda
3308753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3309753dece8SMiguel Ojeda unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> {
drop(&mut self)3310753dece8SMiguel Ojeda fn drop(&mut self) {
3311753dece8SMiguel Ojeda unsafe {
3312753dece8SMiguel Ojeda // use drop for [T]
3313753dece8SMiguel Ojeda // use a raw slice to refer to the elements of the vector as weakest necessary type;
3314753dece8SMiguel Ojeda // could avoid questions of validity in certain cases
3315753dece8SMiguel Ojeda ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
3316753dece8SMiguel Ojeda }
3317753dece8SMiguel Ojeda // RawVec handles deallocation
3318753dece8SMiguel Ojeda }
3319753dece8SMiguel Ojeda }
3320753dece8SMiguel Ojeda
3321753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
332289eed1abSMiguel Ojeda impl<T> Default for Vec<T> {
3323753dece8SMiguel Ojeda /// Creates an empty `Vec<T>`.
33243ed03f4dSMiguel Ojeda ///
33253ed03f4dSMiguel Ojeda /// The vector will not allocate until elements are pushed onto it.
default() -> Vec<T>3326753dece8SMiguel Ojeda fn default() -> Vec<T> {
3327753dece8SMiguel Ojeda Vec::new()
3328753dece8SMiguel Ojeda }
3329753dece8SMiguel Ojeda }
3330753dece8SMiguel Ojeda
3331753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3332753dece8SMiguel Ojeda impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result3333753dece8SMiguel Ojeda fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3334753dece8SMiguel Ojeda fmt::Debug::fmt(&**self, f)
3335753dece8SMiguel Ojeda }
3336753dece8SMiguel Ojeda }
3337753dece8SMiguel Ojeda
3338753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3339753dece8SMiguel Ojeda impl<T, A: Allocator> AsRef<Vec<T, A>> for Vec<T, A> {
as_ref(&self) -> &Vec<T, A>3340753dece8SMiguel Ojeda fn as_ref(&self) -> &Vec<T, A> {
3341753dece8SMiguel Ojeda self
3342753dece8SMiguel Ojeda }
3343753dece8SMiguel Ojeda }
3344753dece8SMiguel Ojeda
3345753dece8SMiguel Ojeda #[stable(feature = "vec_as_mut", since = "1.5.0")]
3346753dece8SMiguel Ojeda impl<T, A: Allocator> AsMut<Vec<T, A>> for Vec<T, A> {
as_mut(&mut self) -> &mut Vec<T, A>3347753dece8SMiguel Ojeda fn as_mut(&mut self) -> &mut Vec<T, A> {
3348753dece8SMiguel Ojeda self
3349753dece8SMiguel Ojeda }
3350753dece8SMiguel Ojeda }
3351753dece8SMiguel Ojeda
3352753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3353753dece8SMiguel Ojeda impl<T, A: Allocator> AsRef<[T]> for Vec<T, A> {
as_ref(&self) -> &[T]3354753dece8SMiguel Ojeda fn as_ref(&self) -> &[T] {
3355753dece8SMiguel Ojeda self
3356753dece8SMiguel Ojeda }
3357753dece8SMiguel Ojeda }
3358753dece8SMiguel Ojeda
3359753dece8SMiguel Ojeda #[stable(feature = "vec_as_mut", since = "1.5.0")]
3360753dece8SMiguel Ojeda impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> {
as_mut(&mut self) -> &mut [T]3361753dece8SMiguel Ojeda fn as_mut(&mut self) -> &mut [T] {
3362753dece8SMiguel Ojeda self
3363753dece8SMiguel Ojeda }
3364753dece8SMiguel Ojeda }
3365753dece8SMiguel Ojeda
3366753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3367753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3368753dece8SMiguel Ojeda impl<T: Clone> From<&[T]> for Vec<T> {
3369753dece8SMiguel Ojeda /// Allocate a `Vec<T>` and fill it by cloning `s`'s items.
3370753dece8SMiguel Ojeda ///
3371753dece8SMiguel Ojeda /// # Examples
3372753dece8SMiguel Ojeda ///
3373753dece8SMiguel Ojeda /// ```
3374753dece8SMiguel Ojeda /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);
3375753dece8SMiguel Ojeda /// ```
3376753dece8SMiguel Ojeda #[cfg(not(test))]
from(s: &[T]) -> Vec<T>3377753dece8SMiguel Ojeda fn from(s: &[T]) -> Vec<T> {
3378753dece8SMiguel Ojeda s.to_vec()
3379753dece8SMiguel Ojeda }
3380753dece8SMiguel Ojeda #[cfg(test)]
from(s: &[T]) -> Vec<T>3381753dece8SMiguel Ojeda fn from(s: &[T]) -> Vec<T> {
3382753dece8SMiguel Ojeda crate::slice::to_vec(s, Global)
3383753dece8SMiguel Ojeda }
3384753dece8SMiguel Ojeda }
3385753dece8SMiguel Ojeda
3386753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3387753dece8SMiguel Ojeda #[stable(feature = "vec_from_mut", since = "1.19.0")]
3388753dece8SMiguel Ojeda impl<T: Clone> From<&mut [T]> for Vec<T> {
3389753dece8SMiguel Ojeda /// Allocate a `Vec<T>` and fill it by cloning `s`'s items.
3390753dece8SMiguel Ojeda ///
3391753dece8SMiguel Ojeda /// # Examples
3392753dece8SMiguel Ojeda ///
3393753dece8SMiguel Ojeda /// ```
3394753dece8SMiguel Ojeda /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]);
3395753dece8SMiguel Ojeda /// ```
3396753dece8SMiguel Ojeda #[cfg(not(test))]
from(s: &mut [T]) -> Vec<T>3397753dece8SMiguel Ojeda fn from(s: &mut [T]) -> Vec<T> {
3398753dece8SMiguel Ojeda s.to_vec()
3399753dece8SMiguel Ojeda }
3400753dece8SMiguel Ojeda #[cfg(test)]
from(s: &mut [T]) -> Vec<T>3401753dece8SMiguel Ojeda fn from(s: &mut [T]) -> Vec<T> {
3402753dece8SMiguel Ojeda crate::slice::to_vec(s, Global)
3403753dece8SMiguel Ojeda }
3404753dece8SMiguel Ojeda }
3405753dece8SMiguel Ojeda
3406753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3407753dece8SMiguel Ojeda #[stable(feature = "vec_from_array", since = "1.44.0")]
3408753dece8SMiguel Ojeda impl<T, const N: usize> From<[T; N]> for Vec<T> {
3409753dece8SMiguel Ojeda /// Allocate a `Vec<T>` and move `s`'s items into it.
3410753dece8SMiguel Ojeda ///
3411753dece8SMiguel Ojeda /// # Examples
3412753dece8SMiguel Ojeda ///
3413753dece8SMiguel Ojeda /// ```
3414753dece8SMiguel Ojeda /// assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]);
3415753dece8SMiguel Ojeda /// ```
3416753dece8SMiguel Ojeda #[cfg(not(test))]
from(s: [T; N]) -> Vec<T>3417753dece8SMiguel Ojeda fn from(s: [T; N]) -> Vec<T> {
341889eed1abSMiguel Ojeda <[T]>::into_vec(Box::new(s))
3419753dece8SMiguel Ojeda }
3420753dece8SMiguel Ojeda
3421753dece8SMiguel Ojeda #[cfg(test)]
from(s: [T; N]) -> Vec<T>3422753dece8SMiguel Ojeda fn from(s: [T; N]) -> Vec<T> {
34233ed03f4dSMiguel Ojeda crate::slice::into_vec(Box::new(s))
3424753dece8SMiguel Ojeda }
3425753dece8SMiguel Ojeda }
3426753dece8SMiguel Ojeda
34278909a80eSMiguel Ojeda #[cfg(not(no_borrow))]
3428753dece8SMiguel Ojeda #[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
3429753dece8SMiguel Ojeda impl<'a, T> From<Cow<'a, [T]>> for Vec<T>
3430753dece8SMiguel Ojeda where
3431753dece8SMiguel Ojeda [T]: ToOwned<Owned = Vec<T>>,
3432753dece8SMiguel Ojeda {
3433753dece8SMiguel Ojeda /// Convert a clone-on-write slice into a vector.
3434753dece8SMiguel Ojeda ///
3435753dece8SMiguel Ojeda /// If `s` already owns a `Vec<T>`, it will be returned directly.
3436753dece8SMiguel Ojeda /// If `s` is borrowing a slice, a new `Vec<T>` will be allocated and
3437753dece8SMiguel Ojeda /// filled by cloning `s`'s items into it.
3438753dece8SMiguel Ojeda ///
3439753dece8SMiguel Ojeda /// # Examples
3440753dece8SMiguel Ojeda ///
3441753dece8SMiguel Ojeda /// ```
3442753dece8SMiguel Ojeda /// # use std::borrow::Cow;
344389eed1abSMiguel Ojeda /// let o: Cow<'_, [i32]> = Cow::Owned(vec![1, 2, 3]);
344489eed1abSMiguel Ojeda /// let b: Cow<'_, [i32]> = Cow::Borrowed(&[1, 2, 3]);
3445753dece8SMiguel Ojeda /// assert_eq!(Vec::from(o), Vec::from(b));
3446753dece8SMiguel Ojeda /// ```
from(s: Cow<'a, [T]>) -> Vec<T>3447753dece8SMiguel Ojeda fn from(s: Cow<'a, [T]>) -> Vec<T> {
3448753dece8SMiguel Ojeda s.into_owned()
3449753dece8SMiguel Ojeda }
3450753dece8SMiguel Ojeda }
3451753dece8SMiguel Ojeda
34523ed03f4dSMiguel Ojeda // note: test pulls in std, which causes errors here
3453753dece8SMiguel Ojeda #[cfg(not(test))]
3454753dece8SMiguel Ojeda #[stable(feature = "vec_from_box", since = "1.18.0")]
3455753dece8SMiguel Ojeda impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> {
3456753dece8SMiguel Ojeda /// Convert a boxed slice into a vector by transferring ownership of
3457753dece8SMiguel Ojeda /// the existing heap allocation.
3458753dece8SMiguel Ojeda ///
3459753dece8SMiguel Ojeda /// # Examples
3460753dece8SMiguel Ojeda ///
3461753dece8SMiguel Ojeda /// ```
3462753dece8SMiguel Ojeda /// let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice();
3463753dece8SMiguel Ojeda /// assert_eq!(Vec::from(b), vec![1, 2, 3]);
3464753dece8SMiguel Ojeda /// ```
from(s: Box<[T], A>) -> Self3465753dece8SMiguel Ojeda fn from(s: Box<[T], A>) -> Self {
3466753dece8SMiguel Ojeda s.into_vec()
3467753dece8SMiguel Ojeda }
3468753dece8SMiguel Ojeda }
3469753dece8SMiguel Ojeda
34703ed03f4dSMiguel Ojeda // note: test pulls in std, which causes errors here
3471753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3472753dece8SMiguel Ojeda #[cfg(not(test))]
3473753dece8SMiguel Ojeda #[stable(feature = "box_from_vec", since = "1.20.0")]
3474753dece8SMiguel Ojeda impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> {
3475753dece8SMiguel Ojeda /// Convert a vector into a boxed slice.
3476753dece8SMiguel Ojeda ///
3477753dece8SMiguel Ojeda /// If `v` has excess capacity, its items will be moved into a
3478753dece8SMiguel Ojeda /// newly-allocated buffer with exactly the right capacity.
3479753dece8SMiguel Ojeda ///
3480753dece8SMiguel Ojeda /// # Examples
3481753dece8SMiguel Ojeda ///
3482753dece8SMiguel Ojeda /// ```
3483753dece8SMiguel Ojeda /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice());
3484753dece8SMiguel Ojeda /// ```
34853ed03f4dSMiguel Ojeda ///
34863ed03f4dSMiguel Ojeda /// Any excess capacity is removed:
34873ed03f4dSMiguel Ojeda /// ```
34883ed03f4dSMiguel Ojeda /// let mut vec = Vec::with_capacity(10);
34893ed03f4dSMiguel Ojeda /// vec.extend([1, 2, 3]);
34903ed03f4dSMiguel Ojeda ///
34913ed03f4dSMiguel Ojeda /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice());
34923ed03f4dSMiguel Ojeda /// ```
from(v: Vec<T, A>) -> Self3493753dece8SMiguel Ojeda fn from(v: Vec<T, A>) -> Self {
3494753dece8SMiguel Ojeda v.into_boxed_slice()
3495753dece8SMiguel Ojeda }
3496753dece8SMiguel Ojeda }
3497753dece8SMiguel Ojeda
3498753dece8SMiguel Ojeda #[cfg(not(no_global_oom_handling))]
3499753dece8SMiguel Ojeda #[stable(feature = "rust1", since = "1.0.0")]
3500753dece8SMiguel Ojeda impl From<&str> for Vec<u8> {
3501753dece8SMiguel Ojeda /// Allocate a `Vec<u8>` and fill it with a UTF-8 string.
3502753dece8SMiguel Ojeda ///
3503753dece8SMiguel Ojeda /// # Examples
3504753dece8SMiguel Ojeda ///
3505753dece8SMiguel Ojeda /// ```
3506753dece8SMiguel Ojeda /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);
3507753dece8SMiguel Ojeda /// ```
from(s: &str) -> Vec<u8>3508753dece8SMiguel Ojeda fn from(s: &str) -> Vec<u8> {
3509753dece8SMiguel Ojeda From::from(s.as_bytes())
3510753dece8SMiguel Ojeda }
3511753dece8SMiguel Ojeda }
3512753dece8SMiguel Ojeda
3513753dece8SMiguel Ojeda #[stable(feature = "array_try_from_vec", since = "1.48.0")]
3514753dece8SMiguel Ojeda impl<T, A: Allocator, const N: usize> TryFrom<Vec<T, A>> for [T; N] {
3515753dece8SMiguel Ojeda type Error = Vec<T, A>;
3516753dece8SMiguel Ojeda
3517753dece8SMiguel Ojeda /// Gets the entire contents of the `Vec<T>` as an array,
3518753dece8SMiguel Ojeda /// if its size exactly matches that of the requested array.
3519753dece8SMiguel Ojeda ///
3520753dece8SMiguel Ojeda /// # Examples
3521753dece8SMiguel Ojeda ///
3522753dece8SMiguel Ojeda /// ```
3523753dece8SMiguel Ojeda /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3]));
3524753dece8SMiguel Ojeda /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([]));
3525753dece8SMiguel Ojeda /// ```
3526753dece8SMiguel Ojeda ///
3527753dece8SMiguel Ojeda /// If the length doesn't match, the input comes back in `Err`:
3528753dece8SMiguel Ojeda /// ```
3529753dece8SMiguel Ojeda /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into();
3530753dece8SMiguel Ojeda /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
3531753dece8SMiguel Ojeda /// ```
3532753dece8SMiguel Ojeda ///
3533753dece8SMiguel Ojeda /// If you're fine with just getting a prefix of the `Vec<T>`,
3534753dece8SMiguel Ojeda /// you can call [`.truncate(N)`](Vec::truncate) first.
3535753dece8SMiguel Ojeda /// ```
3536753dece8SMiguel Ojeda /// let mut v = String::from("hello world").into_bytes();
3537753dece8SMiguel Ojeda /// v.sort();
3538753dece8SMiguel Ojeda /// v.truncate(2);
3539753dece8SMiguel Ojeda /// let [a, b]: [_; 2] = v.try_into().unwrap();
3540753dece8SMiguel Ojeda /// assert_eq!(a, b' ');
3541753dece8SMiguel Ojeda /// assert_eq!(b, b'd');
3542753dece8SMiguel Ojeda /// ```
try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>>3543753dece8SMiguel Ojeda fn try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>> {
3544753dece8SMiguel Ojeda if vec.len() != N {
3545753dece8SMiguel Ojeda return Err(vec);
3546753dece8SMiguel Ojeda }
3547753dece8SMiguel Ojeda
3548753dece8SMiguel Ojeda // SAFETY: `.set_len(0)` is always sound.
3549753dece8SMiguel Ojeda unsafe { vec.set_len(0) };
3550753dece8SMiguel Ojeda
3551753dece8SMiguel Ojeda // SAFETY: A `Vec`'s pointer is always aligned properly, and
3552753dece8SMiguel Ojeda // the alignment the array needs is the same as the items.
3553753dece8SMiguel Ojeda // We checked earlier that we have sufficient items.
3554753dece8SMiguel Ojeda // The items will not double-drop as the `set_len`
3555753dece8SMiguel Ojeda // tells the `Vec` not to also drop them.
3556753dece8SMiguel Ojeda let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) };
3557753dece8SMiguel Ojeda Ok(array)
3558753dece8SMiguel Ojeda }
3559753dece8SMiguel Ojeda }
3560