1//! A contiguous growable array type with heap-allocated contents, written
2//! `Vec<T>`.
3//!
4//! Vectors have *O*(1) indexing, amortized *O*(1) push (to the end) and
5//! *O*(1) pop (from the end).
6//!
7//! Vectors ensure they never allocate more than `isize::MAX` bytes.
8//!
9//! # Examples
10//!
11//! You can explicitly create a [`Vec`] with [`Vec::new`]:
12//!
13//! ```
14//! let v: Vec<i32> = Vec::new();
15//! ```
16//!
17//! ...or by using the [`vec!`] macro:
18//!
19//! ```
20//! let v: Vec<i32> = vec![];
21//!
22//! let v = vec![1, 2, 3, 4, 5];
23//!
24//! let v = vec![0; 10]; // ten zeroes
25//! ```
26//!
27//! You can [`push`] values onto the end of a vector (which will grow the vector
28//! as needed):
29//!
30//! ```
31//! let mut v = vec![1, 2];
32//!
33//! v.push(3);
34//! ```
35//!
36//! Popping values works in much the same way:
37//!
38//! ```
39//! let mut v = vec![1, 2];
40//!
41//! let two = v.pop();
42//! ```
43//!
44//! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits):
45//!
46//! ```
47//! let mut v = vec![1, 2, 3];
48//! let three = v[2];
49//! v[1] = v[1] + 5;
50//! ```
51//!
52//! [`push`]: Vec::push
53
54#[cfg(not(no_global_oom_handling))]
55use core::cmp;
56use core::cmp::Ordering;
57use core::convert::TryFrom;
58use core::fmt;
59use core::hash::{Hash, Hasher};
60#[cfg(not(no_global_oom_handling))]
61use core::iter;
62#[cfg(not(no_global_oom_handling))]
63use core::iter::FromIterator;
64use core::marker::PhantomData;
65use core::mem::{self, size_of, ManuallyDrop, MaybeUninit};
66use core::ops::{self, Bound, Index, IndexMut, Range, RangeBounds};
67use core::ptr::{self, NonNull};
68use core::slice::{self, SliceIndex};
69
70use super::{
71 alloc::{Allocator, Global},
72 assume,
73 boxed::Box,
74 raw_vec::{RawVec, TryReserveError},
75};
76
77#[cfg(not(no_global_oom_handling))]
78pub use self::splice::Splice;
79
80#[cfg(not(no_global_oom_handling))]
81mod splice;
82
83pub use self::drain::Drain;
84
85mod drain;
86
87pub use self::into_iter::IntoIter;
88
89mod into_iter;
90
91mod partial_eq;
92
93#[cfg(not(no_global_oom_handling))]
94mod set_len_on_drop;
95
96#[cfg(not(no_global_oom_handling))]
97use self::set_len_on_drop::SetLenOnDrop;
98
99/// A contiguous growable array type, written as `Vec<T>`, short for 'vector'.
100///
101/// # Examples
102///
103/// ```
104/// let mut vec = Vec::new();
105/// vec.push(1);
106/// vec.push(2);
107///
108/// assert_eq!(vec.len(), 2);
109/// assert_eq!(vec[0], 1);
110///
111/// assert_eq!(vec.pop(), Some(2));
112/// assert_eq!(vec.len(), 1);
113///
114/// vec[0] = 7;
115/// assert_eq!(vec[0], 7);
116///
117/// vec.extend([1, 2, 3].iter().copied());
118///
119/// for x in &vec {
120/// println!("{x}");
121/// }
122/// assert_eq!(vec, [7, 1, 2, 3]);
123/// ```
124///
125/// The [`vec!`] macro is provided for convenient initialization:
126///
127/// ```
128/// let mut vec1 = vec![1, 2, 3];
129/// vec1.push(4);
130/// let vec2 = Vec::from([1, 2, 3, 4]);
131/// assert_eq!(vec1, vec2);
132/// ```
133///
134/// It can also initialize each element of a `Vec<T>` with a given value.
135/// This may be more efficient than performing allocation and initialization
136/// in separate steps, especially when initializing a vector of zeros:
137///
138/// ```
139/// let vec = vec![0; 5];
140/// assert_eq!(vec, [0, 0, 0, 0, 0]);
141///
142/// // The following is equivalent, but potentially slower:
143/// let mut vec = Vec::with_capacity(5);
144/// vec.resize(5, 0);
145/// assert_eq!(vec, [0, 0, 0, 0, 0]);
146/// ```
147///
148/// For more information, see
149/// [Capacity and Reallocation](#capacity-and-reallocation).
150///
151/// Use a `Vec<T>` as an efficient stack:
152///
153/// ```
154/// let mut stack = Vec::new();
155///
156/// stack.push(1);
157/// stack.push(2);
158/// stack.push(3);
159///
160/// while let Some(top) = stack.pop() {
161/// // Prints 3, 2, 1
162/// println!("{top}");
163/// }
164/// ```
165///
166/// # Indexing
167///
168/// The `Vec` type allows to access values by index, because it implements the
169/// [`Index`] trait. An example will be more explicit:
170///
171/// ```
172/// let v = vec![0, 2, 4, 6];
173/// println!("{}", v[1]); // it will display '2'
174/// ```
175///
176/// However be careful: if you try to access an index which isn't in the `Vec`,
177/// your software will panic! You cannot do this:
178///
179/// ```should_panic
180/// let v = vec![0, 2, 4, 6];
181/// println!("{}", v[6]); // it will panic!
182/// ```
183///
184/// Use [`get`] and [`get_mut`] if you want to check whether the index is in
185/// the `Vec`.
186///
187/// # Slicing
188///
189/// A `Vec` can be mutable. On the other hand, slices are read-only objects.
190/// To get a [slice][prim@slice], use [`&`]. Example:
191///
192/// ```
193/// fn read_slice(slice: &[usize]) {
194/// // ...
195/// }
196///
197/// let v = vec![0, 1];
198/// read_slice(&v);
199///
200/// // ... and that's all!
201/// // you can also do it like this:
202/// let u: &[usize] = &v;
203/// // or like this:
204/// let u: &[_] = &v;
205/// ```
206///
207/// In Rust, it's more common to pass slices as arguments rather than vectors
208/// when you just want to provide read access. The same goes for [`String`] and
209/// [`&str`].
210///
211/// # Capacity and reallocation
212///
213/// The capacity of a vector is the amount of space allocated for any future
214/// elements that will be added onto the vector. This is not to be confused with
215/// the *length* of a vector, which specifies the number of actual elements
216/// within the vector. If a vector's length exceeds its capacity, its capacity
217/// will automatically be increased, but its elements will have to be
218/// reallocated.
219///
220/// For example, a vector with capacity 10 and length 0 would be an empty vector
221/// with space for 10 more elements. Pushing 10 or fewer elements onto the
222/// vector will not change its capacity or cause reallocation to occur. However,
223/// if the vector's length is increased to 11, it will have to reallocate, which
224/// can be slow. For this reason, it is recommended to use [`Vec::with_capacity`]
225/// whenever possible to specify how big the vector is expected to get.
226///
227/// # Guarantees
228///
229/// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees
230/// about its design. This ensures that it's as low-overhead as possible in
231/// the general case, and can be correctly manipulated in primitive ways
232/// by unsafe code. Note that these guarantees refer to an unqualified `Vec<T>`.
233/// If additional type parameters are added (e.g., to support custom allocators),
234/// overriding their defaults may change the behavior.
235///
236/// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length)
237/// triplet. No more, no less. The order of these fields is completely
238/// unspecified, and you should use the appropriate methods to modify these.
239/// The pointer will never be null, so this type is null-pointer-optimized.
240///
241/// However, the pointer might not actually point to allocated memory. In particular,
242/// if you construct a `Vec` with capacity 0 via [`Vec::new`], [`vec![]`][`vec!`],
243/// [`Vec::with_capacity(0)`][`Vec::with_capacity`], or by calling [`shrink_to_fit`]
244/// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized
245/// types inside a `Vec`, it will not allocate space for them. *Note that in this case
246/// the `Vec` might not report a [`capacity`] of 0*. `Vec` will allocate if and only
247/// if <code>[mem::size_of::\<T>]\() * [capacity]\() > 0</code>. In general, `Vec`'s allocation
248/// details are very subtle --- if you intend to allocate memory using a `Vec`
249/// and use it for something else (either to pass to unsafe code, or to build your
250/// own memory-backed collection), be sure to deallocate this memory by using
251/// `from_raw_parts` to recover the `Vec` and then dropping it.
252///
253/// If a `Vec` *has* allocated memory, then the memory it points to is on the heap
254/// (as defined by the allocator Rust is configured to use by default), and its
255/// pointer points to [`len`] initialized, contiguous elements in order (what
256/// you would see if you coerced it to a slice), followed by <code>[capacity] - [len]</code>
257/// logically uninitialized, contiguous elements.
258///
259/// A vector containing the elements `'a'` and `'b'` with capacity 4 can be
260/// visualized as below. The top part is the `Vec` struct, it contains a
261/// pointer to the head of the allocation in the heap, length and capacity.
262/// The bottom part is the allocation on the heap, a contiguous memory block.
263///
264/// ```text
265/// ptr len capacity
266/// +--------+--------+--------+
267/// | 0x0123 | 2 | 4 |
268/// +--------+--------+--------+
269/// |
270/// v
271/// Heap +--------+--------+--------+--------+
272/// | 'a' | 'b' | uninit | uninit |
273/// +--------+--------+--------+--------+
274/// ```
275///
276/// - **uninit** represents memory that is not initialized, see [`MaybeUninit`].
277/// - Note: the ABI is not stable and `Vec` makes no guarantees about its memory
278/// layout (including the order of fields).
279///
280/// `Vec` will never perform a "small optimization" where elements are actually
281/// stored on the stack for two reasons:
282///
283/// * It would make it more difficult for unsafe code to correctly manipulate
284/// a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were
285/// only moved, and it would be more difficult to determine if a `Vec` had
286/// actually allocated memory.
287///
288/// * It would penalize the general case, incurring an additional branch
289/// on every access.
290///
291/// `Vec` will never automatically shrink itself, even if completely empty. This
292/// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec`
293/// and then filling it back up to the same [`len`] should incur no calls to
294/// the allocator. If you wish to free up unused memory, use
295/// [`shrink_to_fit`] or [`shrink_to`].
296///
297/// [`push`] and [`insert`] will never (re)allocate if the reported capacity is
298/// sufficient. [`push`] and [`insert`] *will* (re)allocate if
299/// <code>[len] == [capacity]</code>. That is, the reported capacity is completely
300/// accurate, and can be relied on. It can even be used to manually free the memory
301/// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even
302/// when not necessary.
303///
304/// `Vec` does not guarantee any particular growth strategy when reallocating
305/// when full, nor when [`reserve`] is called. The current strategy is basic
306/// and it may prove desirable to use a non-constant growth factor. Whatever
307/// strategy is used will of course guarantee *O*(1) amortized [`push`].
308///
309/// `vec![x; n]`, `vec![a, b, c, d]`, and
310/// [`Vec::with_capacity(n)`][`Vec::with_capacity`], will all produce a `Vec`
311/// with exactly the requested capacity. If <code>[len] == [capacity]</code>,
312/// (as is the case for the [`vec!`] macro), then a `Vec<T>` can be converted to
313/// and from a [`Box<[T]>`][owned slice] without reallocating or moving the elements.
314///
315/// `Vec` will not specifically overwrite any data that is removed from it,
316/// but also won't specifically preserve it. Its uninitialized memory is
317/// scratch space that it may use however it wants. It will generally just do
318/// whatever is most efficient or otherwise easy to implement. Do not rely on
319/// removed data to be erased for security purposes. Even if you drop a `Vec`, its
320/// buffer may simply be reused by another allocation. Even if you zero a `Vec`'s memory
321/// first, that might not actually happen because the optimizer does not consider
322/// this a side-effect that must be preserved. There is one case which we will
323/// not break, however: using `unsafe` code to write to the excess capacity,
324/// and then increasing the length to match, is always valid.
325///
326/// Currently, `Vec` does not guarantee the order in which elements are dropped.
327/// The order has changed in the past and may change again.
328///
329/// [`get`]: ../../std/vec/struct.Vec.html#method.get
330/// [`get_mut`]: ../../std/vec/struct.Vec.html#method.get_mut
331/// [`String`]: alloc_crate::string::String
332/// [`&str`]: type@str
333/// [`shrink_to_fit`]: Vec::shrink_to_fit
334/// [`shrink_to`]: Vec::shrink_to
335/// [capacity]: Vec::capacity
336/// [`capacity`]: Vec::capacity
337/// [mem::size_of::\<T>]: core::mem::size_of
338/// [len]: Vec::len
339/// [`len`]: Vec::len
340/// [`push`]: Vec::push
341/// [`insert`]: Vec::insert
342/// [`reserve`]: Vec::reserve
343/// [`MaybeUninit`]: core::mem::MaybeUninit
344/// [owned slice]: Box
345pub struct Vec<T, A: Allocator = Global> {
346 buf: RawVec<T, A>,
347 len: usize,
348}
349
350////////////////////////////////////////////////////////////////////////////////
351// Inherent methods
352////////////////////////////////////////////////////////////////////////////////
353
354impl<T> Vec<T> {
355 /// Constructs a new, empty `Vec<T>`.
356 ///
357 /// The vector will not allocate until elements are pushed onto it.
358 ///
359 /// # Examples
360 ///
361 /// ```
362 /// # #![allow(unused_mut)]
363 /// let mut vec: Vec<i32> = Vec::new();
364 /// ```
365 #[inline(always)]
366 #[must_use]
367 pub const fn new() -> Self {
368 Vec {
369 buf: RawVec::new(),
370 len: 0,
371 }
372 }
373
374 /// Constructs a new, empty `Vec<T>` with at least the specified capacity.
375 ///
376 /// The vector will be able to hold at least `capacity` elements without
377 /// reallocating. This method is allowed to allocate for more elements than
378 /// `capacity`. If `capacity` is 0, the vector will not allocate.
379 ///
380 /// It is important to note that although the returned vector has the
381 /// minimum *capacity* specified, the vector will have a zero *length*. For
382 /// an explanation of the difference between length and capacity, see
383 /// *[Capacity and reallocation]*.
384 ///
385 /// If it is important to know the exact allocated capacity of a `Vec`,
386 /// always use the [`capacity`] method after construction.
387 ///
388 /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation
389 /// and the capacity will always be `usize::MAX`.
390 ///
391 /// [Capacity and reallocation]: #capacity-and-reallocation
392 /// [`capacity`]: Vec::capacity
393 ///
394 /// # Panics
395 ///
396 /// Panics if the new capacity exceeds `isize::MAX` bytes.
397 ///
398 /// # Examples
399 ///
400 /// ```
401 /// let mut vec = Vec::with_capacity(10);
402 ///
403 /// // The vector contains no items, even though it has capacity for more
404 /// assert_eq!(vec.len(), 0);
405 /// assert!(vec.capacity() >= 10);
406 ///
407 /// // These are all done without reallocating...
408 /// for i in 0..10 {
409 /// vec.push(i);
410 /// }
411 /// assert_eq!(vec.len(), 10);
412 /// assert!(vec.capacity() >= 10);
413 ///
414 /// // ...but this may make the vector reallocate
415 /// vec.push(11);
416 /// assert_eq!(vec.len(), 11);
417 /// assert!(vec.capacity() >= 11);
418 ///
419 /// // A vector of a zero-sized type will always over-allocate, since no
420 /// // allocation is necessary
421 /// let vec_units = Vec::<()>::with_capacity(10);
422 /// assert_eq!(vec_units.capacity(), usize::MAX);
423 /// ```
424 #[cfg(not(no_global_oom_handling))]
425 #[inline(always)]
426 #[must_use]
427 pub fn with_capacity(capacity: usize) -> Self {
428 Self::with_capacity_in(capacity, Global)
429 }
430
431 /// Creates a `Vec<T>` directly from a pointer, a capacity, and a length.
432 ///
433 /// # Safety
434 ///
435 /// This is highly unsafe, due to the number of invariants that aren't
436 /// checked:
437 ///
438 /// * `T` needs to have the same alignment as what `ptr` was allocated with.
439 /// (`T` having a less strict alignment is not sufficient, the alignment really
440 /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be
441 /// allocated and deallocated with the same layout.)
442 /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs
443 /// to be the same size as the pointer was allocated with. (Because similar to
444 /// alignment, [`dealloc`] must be called with the same layout `size`.)
445 /// * `length` needs to be less than or equal to `capacity`.
446 /// * The first `length` values must be properly initialized values of type `T`.
447 /// * `capacity` needs to be the capacity that the pointer was allocated with.
448 /// * The allocated size in bytes must be no larger than `isize::MAX`.
449 /// See the safety documentation of [`pointer::offset`](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.offset).
450 ///
451 /// These requirements are always upheld by any `ptr` that has been allocated
452 /// via `Vec<T>`. Other allocation sources are allowed if the invariants are
453 /// upheld.
454 ///
455 /// Violating these may cause problems like corrupting the allocator's
456 /// internal data structures. For example it is normally **not** safe
457 /// to build a `Vec<u8>` from a pointer to a C `char` array with length
458 /// `size_t`, doing so is only safe if the array was initially allocated by
459 /// a `Vec` or `String`.
460 /// It's also not safe to build one from a `Vec<u16>` and its length, because
461 /// the allocator cares about the alignment, and these two types have different
462 /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
463 /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1. To avoid
464 /// these issues, it is often preferable to do casting/transmuting using
465 /// [`slice::from_raw_parts`] instead.
466 ///
467 /// The ownership of `ptr` is effectively transferred to the
468 /// `Vec<T>` which may then deallocate, reallocate or change the
469 /// contents of memory pointed to by the pointer at will. Ensure
470 /// that nothing else uses the pointer after calling this
471 /// function.
472 ///
473 /// [`String`]: alloc_crate::string::String
474 /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
475 ///
476 /// # Examples
477 ///
478 /// ```
479 /// use std::ptr;
480 /// use std::mem;
481 ///
482 /// let v = vec![1, 2, 3];
483 ///
484 // FIXME Update this when vec_into_raw_parts is stabilized
485 /// // Prevent running `v`'s destructor so we are in complete control
486 /// // of the allocation.
487 /// let mut v = mem::ManuallyDrop::new(v);
488 ///
489 /// // Pull out the various important pieces of information about `v`
490 /// let p = v.as_mut_ptr();
491 /// let len = v.len();
492 /// let cap = v.capacity();
493 ///
494 /// unsafe {
495 /// // Overwrite memory with 4, 5, 6
496 /// for i in 0..len {
497 /// ptr::write(p.add(i), 4 + i);
498 /// }
499 ///
500 /// // Put everything back together into a Vec
501 /// let rebuilt = Vec::from_raw_parts(p, len, cap);
502 /// assert_eq!(rebuilt, [4, 5, 6]);
503 /// }
504 /// ```
505 ///
506 /// Using memory that was allocated elsewhere:
507 ///
508 /// ```rust
509 /// #![feature(allocator_api)]
510 ///
511 /// use std::alloc::{AllocError, Allocator, Global, Layout};
512 ///
513 /// fn main() {
514 /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
515 ///
516 /// let vec = unsafe {
517 /// let mem = match Global.allocate(layout) {
518 /// Ok(mem) => mem.cast::<u32>().as_ptr(),
519 /// Err(AllocError) => return,
520 /// };
521 ///
522 /// mem.write(1_000_000);
523 ///
524 /// Vec::from_raw_parts_in(mem, 1, 16, Global)
525 /// };
526 ///
527 /// assert_eq!(vec, &[1_000_000]);
528 /// assert_eq!(vec.capacity(), 16);
529 /// }
530 /// ```
531 #[inline(always)]
532 pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
533 unsafe { Self::from_raw_parts_in(ptr, length, capacity, Global) }
534 }
535}
536
537impl<T, A: Allocator> Vec<T, A> {
538 /// Constructs a new, empty `Vec<T, A>`.
539 ///
540 /// The vector will not allocate until elements are pushed onto it.
541 ///
542 /// # Examples
543 ///
544 /// ```
545 /// use std::alloc::System;
546 ///
547 /// # #[allow(unused_mut)]
548 /// let mut vec: Vec<i32, _> = Vec::new_in(System);
549 /// ```
550 #[inline(always)]
551 pub const fn new_in(alloc: A) -> Self {
552 Vec {
553 buf: RawVec::new_in(alloc),
554 len: 0,
555 }
556 }
557
558 /// Constructs a new, empty `Vec<T, A>` with at least the specified capacity
559 /// with the provided allocator.
560 ///
561 /// The vector will be able to hold at least `capacity` elements without
562 /// reallocating. This method is allowed to allocate for more elements than
563 /// `capacity`. If `capacity` is 0, the vector will not allocate.
564 ///
565 /// It is important to note that although the returned vector has the
566 /// minimum *capacity* specified, the vector will have a zero *length*. For
567 /// an explanation of the difference between length and capacity, see
568 /// *[Capacity and reallocation]*.
569 ///
570 /// If it is important to know the exact allocated capacity of a `Vec`,
571 /// always use the [`capacity`] method after construction.
572 ///
573 /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation
574 /// and the capacity will always be `usize::MAX`.
575 ///
576 /// [Capacity and reallocation]: #capacity-and-reallocation
577 /// [`capacity`]: Vec::capacity
578 ///
579 /// # Panics
580 ///
581 /// Panics if the new capacity exceeds `isize::MAX` bytes.
582 ///
583 /// # Examples
584 ///
585 /// ```
586 /// use std::alloc::System;
587 ///
588 /// let mut vec = Vec::with_capacity_in(10, System);
589 ///
590 /// // The vector contains no items, even though it has capacity for more
591 /// assert_eq!(vec.len(), 0);
592 /// assert_eq!(vec.capacity(), 10);
593 ///
594 /// // These are all done without reallocating...
595 /// for i in 0..10 {
596 /// vec.push(i);
597 /// }
598 /// assert_eq!(vec.len(), 10);
599 /// assert_eq!(vec.capacity(), 10);
600 ///
601 /// // ...but this may make the vector reallocate
602 /// vec.push(11);
603 /// assert_eq!(vec.len(), 11);
604 /// assert!(vec.capacity() >= 11);
605 ///
606 /// // A vector of a zero-sized type will always over-allocate, since no
607 /// // allocation is necessary
608 /// let vec_units = Vec::<(), System>::with_capacity_in(10, System);
609 /// assert_eq!(vec_units.capacity(), usize::MAX);
610 /// ```
611 #[cfg(not(no_global_oom_handling))]
612 #[inline(always)]
613 pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
614 Vec {
615 buf: RawVec::with_capacity_in(capacity, alloc),
616 len: 0,
617 }
618 }
619
620 /// Creates a `Vec<T, A>` directly from a pointer, a capacity, a length,
621 /// and an allocator.
622 ///
623 /// # Safety
624 ///
625 /// This is highly unsafe, due to the number of invariants that aren't
626 /// checked:
627 ///
628 /// * `T` needs to have the same alignment as what `ptr` was allocated with.
629 /// (`T` having a less strict alignment is not sufficient, the alignment really
630 /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be
631 /// allocated and deallocated with the same layout.)
632 /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs
633 /// to be the same size as the pointer was allocated with. (Because similar to
634 /// alignment, [`dealloc`] must be called with the same layout `size`.)
635 /// * `length` needs to be less than or equal to `capacity`.
636 /// * The first `length` values must be properly initialized values of type `T`.
637 /// * `capacity` needs to [*fit*] the layout size that the pointer was allocated with.
638 /// * The allocated size in bytes must be no larger than `isize::MAX`.
639 /// See the safety documentation of [`pointer::offset`](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.offset).
640 ///
641 /// These requirements are always upheld by any `ptr` that has been allocated
642 /// via `Vec<T, A>`. Other allocation sources are allowed if the invariants are
643 /// upheld.
644 ///
645 /// Violating these may cause problems like corrupting the allocator's
646 /// internal data structures. For example it is **not** safe
647 /// to build a `Vec<u8>` from a pointer to a C `char` array with length `size_t`.
648 /// It's also not safe to build one from a `Vec<u16>` and its length, because
649 /// the allocator cares about the alignment, and these two types have different
650 /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after
651 /// turning it into a `Vec<u8>` it'll be deallocated with alignment 1.
652 ///
653 /// The ownership of `ptr` is effectively transferred to the
654 /// `Vec<T>` which may then deallocate, reallocate or change the
655 /// contents of memory pointed to by the pointer at will. Ensure
656 /// that nothing else uses the pointer after calling this
657 /// function.
658 ///
659 /// [`String`]: alloc_crate::string::String
660 /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc
661 /// [*fit*]: crate::alloc::Allocator#memory-fitting
662 ///
663 /// # Examples
664 ///
665 /// ```
666 /// use std::alloc::System;
667 ///
668 /// use std::ptr;
669 /// use std::mem;
670 ///
671 ///
672 /// # use allocator_api2::vec::Vec;
673 /// let mut v = Vec::with_capacity_in(3, System);
674 /// v.push(1);
675 /// v.push(2);
676 /// v.push(3);
677 ///
678 // FIXME Update this when vec_into_raw_parts is stabilized
679 /// // Prevent running `v`'s destructor so we are in complete control
680 /// // of the allocation.
681 /// let mut v = mem::ManuallyDrop::new(v);
682 ///
683 /// // Pull out the various important pieces of information about `v`
684 /// let p = v.as_mut_ptr();
685 /// let len = v.len();
686 /// let cap = v.capacity();
687 /// let alloc = v.allocator();
688 ///
689 /// unsafe {
690 /// // Overwrite memory with 4, 5, 6
691 /// for i in 0..len {
692 /// ptr::write(p.add(i), 4 + i);
693 /// }
694 ///
695 /// // Put everything back together into a Vec
696 /// let rebuilt = Vec::from_raw_parts_in(p, len, cap, alloc.clone());
697 /// assert_eq!(rebuilt, [4, 5, 6]);
698 /// }
699 /// ```
700 ///
701 /// Using memory that was allocated elsewhere:
702 ///
703 /// ```rust
704 /// use std::alloc::{alloc, Layout};
705 ///
706 /// fn main() {
707 /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
708 /// let vec = unsafe {
709 /// let mem = alloc(layout).cast::<u32>();
710 /// if mem.is_null() {
711 /// return;
712 /// }
713 ///
714 /// mem.write(1_000_000);
715 ///
716 /// Vec::from_raw_parts(mem, 1, 16)
717 /// };
718 ///
719 /// assert_eq!(vec, &[1_000_000]);
720 /// assert_eq!(vec.capacity(), 16);
721 /// }
722 /// ```
723 #[inline(always)]
724 pub unsafe fn from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self {
725 unsafe {
726 Vec {
727 buf: RawVec::from_raw_parts_in(ptr, capacity, alloc),
728 len: length,
729 }
730 }
731 }
732
733 /// Decomposes a `Vec<T>` into its raw components.
734 ///
735 /// Returns the raw pointer to the underlying data, the length of
736 /// the vector (in elements), and the allocated capacity of the
737 /// data (in elements). These are the same arguments in the same
738 /// order as the arguments to [`from_raw_parts`].
739 ///
740 /// After calling this function, the caller is responsible for the
741 /// memory previously managed by the `Vec`. The only way to do
742 /// this is to convert the raw pointer, length, and capacity back
743 /// into a `Vec` with the [`from_raw_parts`] function, allowing
744 /// the destructor to perform the cleanup.
745 ///
746 /// [`from_raw_parts`]: Vec::from_raw_parts
747 ///
748 /// # Examples
749 ///
750 /// ```
751 /// #![feature(vec_into_raw_parts)]
752 /// let v: Vec<i32> = vec![-1, 0, 1];
753 ///
754 /// let (ptr, len, cap) = v.into_raw_parts();
755 ///
756 /// let rebuilt = unsafe {
757 /// // We can now make changes to the components, such as
758 /// // transmuting the raw pointer to a compatible type.
759 /// let ptr = ptr as *mut u32;
760 ///
761 /// Vec::from_raw_parts(ptr, len, cap)
762 /// };
763 /// assert_eq!(rebuilt, [4294967295, 0, 1]);
764 /// ```
765 pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
766 let mut me = ManuallyDrop::new(self);
767 (me.as_mut_ptr(), me.len(), me.capacity())
768 }
769
770 /// Decomposes a `Vec<T>` into its raw components.
771 ///
772 /// Returns the raw pointer to the underlying data, the length of the vector (in elements),
773 /// the allocated capacity of the data (in elements), and the allocator. These are the same
774 /// arguments in the same order as the arguments to [`from_raw_parts_in`].
775 ///
776 /// After calling this function, the caller is responsible for the
777 /// memory previously managed by the `Vec`. The only way to do
778 /// this is to convert the raw pointer, length, and capacity back
779 /// into a `Vec` with the [`from_raw_parts_in`] function, allowing
780 /// the destructor to perform the cleanup.
781 ///
782 /// [`from_raw_parts_in`]: Vec::from_raw_parts_in
783 ///
784 /// # Examples
785 ///
786 /// ```
787 /// #![feature(allocator_api, vec_into_raw_parts)]
788 ///
789 /// use std::alloc::System;
790 ///
791 /// let mut v: Vec<i32, System> = Vec::new_in(System);
792 /// v.push(-1);
793 /// v.push(0);
794 /// v.push(1);
795 ///
796 /// let (ptr, len, cap, alloc) = v.into_raw_parts_with_alloc();
797 ///
798 /// let rebuilt = unsafe {
799 /// // We can now make changes to the components, such as
800 /// // transmuting the raw pointer to a compatible type.
801 /// let ptr = ptr as *mut u32;
802 ///
803 /// Vec::from_raw_parts_in(ptr, len, cap, alloc)
804 /// };
805 /// assert_eq!(rebuilt, [4294967295, 0, 1]);
806 /// ```
807 // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")]
808 pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) {
809 let mut me = ManuallyDrop::new(self);
810 let len = me.len();
811 let capacity = me.capacity();
812 let ptr = me.as_mut_ptr();
813 let alloc = unsafe { ptr::read(me.allocator()) };
814 (ptr, len, capacity, alloc)
815 }
816
817 /// Returns the total number of elements the vector can hold without
818 /// reallocating.
819 ///
820 /// # Examples
821 ///
822 /// ```
823 /// let mut vec: Vec<i32> = Vec::with_capacity(10);
824 /// vec.push(42);
825 /// assert_eq!(vec.capacity(), 10);
826 /// ```
827 #[inline(always)]
828 pub fn capacity(&self) -> usize {
829 self.buf.capacity()
830 }
831
832 /// Reserves capacity for at least `additional` more elements to be inserted
833 /// in the given `Vec<T>`. The collection may reserve more space to
834 /// speculatively avoid frequent reallocations. After calling `reserve`,
835 /// capacity will be greater than or equal to `self.len() + additional`.
836 /// Does nothing if capacity is already sufficient.
837 ///
838 /// # Panics
839 ///
840 /// Panics if the new capacity exceeds `isize::MAX` bytes.
841 ///
842 /// # Examples
843 ///
844 /// ```
845 /// let mut vec = vec![1];
846 /// vec.reserve(10);
847 /// assert!(vec.capacity() >= 11);
848 /// ```
849 #[cfg(not(no_global_oom_handling))]
850 #[inline(always)]
851 pub fn reserve(&mut self, additional: usize) {
852 self.buf.reserve(self.len, additional);
853 }
854
855 /// Reserves the minimum capacity for at least `additional` more elements to
856 /// be inserted in the given `Vec<T>`. Unlike [`reserve`], this will not
857 /// deliberately over-allocate to speculatively avoid frequent allocations.
858 /// After calling `reserve_exact`, capacity will be greater than or equal to
859 /// `self.len() + additional`. Does nothing if the capacity is already
860 /// sufficient.
861 ///
862 /// Note that the allocator may give the collection more space than it
863 /// requests. Therefore, capacity can not be relied upon to be precisely
864 /// minimal. Prefer [`reserve`] if future insertions are expected.
865 ///
866 /// [`reserve`]: Vec::reserve
867 ///
868 /// # Panics
869 ///
870 /// Panics if the new capacity exceeds `isize::MAX` bytes.
871 ///
872 /// # Examples
873 ///
874 /// ```
875 /// let mut vec = vec![1];
876 /// vec.reserve_exact(10);
877 /// assert!(vec.capacity() >= 11);
878 /// ```
879 #[cfg(not(no_global_oom_handling))]
880 #[inline(always)]
881 pub fn reserve_exact(&mut self, additional: usize) {
882 self.buf.reserve_exact(self.len, additional);
883 }
884
885 /// Tries to reserve capacity for at least `additional` more elements to be inserted
886 /// in the given `Vec<T>`. The collection may reserve more space to speculatively avoid
887 /// frequent reallocations. After calling `try_reserve`, capacity will be
888 /// greater than or equal to `self.len() + additional` if it returns
889 /// `Ok(())`. Does nothing if capacity is already sufficient. This method
890 /// preserves the contents even if an error occurs.
891 ///
892 /// # Errors
893 ///
894 /// If the capacity overflows, or the allocator reports a failure, then an error
895 /// is returned.
896 ///
897 /// # Examples
898 ///
899 /// ```
900 /// use std::collections::TryReserveError;
901 ///
902 /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
903 /// let mut output = Vec::new();
904 ///
905 /// // Pre-reserve the memory, exiting if we can't
906 /// output.try_reserve(data.len())?;
907 ///
908 /// // Now we know this can't OOM in the middle of our complex work
909 /// output.extend(data.iter().map(|&val| {
910 /// val * 2 + 5 // very complicated
911 /// }));
912 ///
913 /// Ok(output)
914 /// }
915 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
916 /// ```
917 #[inline(always)]
918 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
919 self.buf.try_reserve(self.len, additional)
920 }
921
922 /// Tries to reserve the minimum capacity for at least `additional`
923 /// elements to be inserted in the given `Vec<T>`. Unlike [`try_reserve`],
924 /// this will not deliberately over-allocate to speculatively avoid frequent
925 /// allocations. After calling `try_reserve_exact`, capacity will be greater
926 /// than or equal to `self.len() + additional` if it returns `Ok(())`.
927 /// Does nothing if the capacity is already sufficient.
928 ///
929 /// Note that the allocator may give the collection more space than it
930 /// requests. Therefore, capacity can not be relied upon to be precisely
931 /// minimal. Prefer [`try_reserve`] if future insertions are expected.
932 ///
933 /// [`try_reserve`]: Vec::try_reserve
934 ///
935 /// # Errors
936 ///
937 /// If the capacity overflows, or the allocator reports a failure, then an error
938 /// is returned.
939 ///
940 /// # Examples
941 ///
942 /// ```
943 /// use std::collections::TryReserveError;
944 ///
945 /// fn process_data(data: &[u32]) -> Result<Vec<u32>, TryReserveError> {
946 /// let mut output = Vec::new();
947 ///
948 /// // Pre-reserve the memory, exiting if we can't
949 /// output.try_reserve_exact(data.len())?;
950 ///
951 /// // Now we know this can't OOM in the middle of our complex work
952 /// output.extend(data.iter().map(|&val| {
953 /// val * 2 + 5 // very complicated
954 /// }));
955 ///
956 /// Ok(output)
957 /// }
958 /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
959 /// ```
960 #[inline(always)]
961 pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
962 self.buf.try_reserve_exact(self.len, additional)
963 }
964
965 /// Shrinks the capacity of the vector as much as possible.
966 ///
967 /// It will drop down as close as possible to the length but the allocator
968 /// may still inform the vector that there is space for a few more elements.
969 ///
970 /// # Examples
971 ///
972 /// ```
973 /// let mut vec = Vec::with_capacity(10);
974 /// vec.extend([1, 2, 3]);
975 /// assert_eq!(vec.capacity(), 10);
976 /// vec.shrink_to_fit();
977 /// assert!(vec.capacity() >= 3);
978 /// ```
979 #[cfg(not(no_global_oom_handling))]
980 #[inline(always)]
981 pub fn shrink_to_fit(&mut self) {
982 // The capacity is never less than the length, and there's nothing to do when
983 // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit`
984 // by only calling it with a greater capacity.
985 if self.capacity() > self.len {
986 self.buf.shrink_to_fit(self.len);
987 }
988 }
989
990 /// Shrinks the capacity of the vector with a lower bound.
991 ///
992 /// The capacity will remain at least as large as both the length
993 /// and the supplied value.
994 ///
995 /// If the current capacity is less than the lower limit, this is a no-op.
996 ///
997 /// # Examples
998 ///
999 /// ```
1000 /// let mut vec = Vec::with_capacity(10);
1001 /// vec.extend([1, 2, 3]);
1002 /// assert_eq!(vec.capacity(), 10);
1003 /// vec.shrink_to(4);
1004 /// assert!(vec.capacity() >= 4);
1005 /// vec.shrink_to(0);
1006 /// assert!(vec.capacity() >= 3);
1007 /// ```
1008 #[cfg(not(no_global_oom_handling))]
1009 #[inline(always)]
1010 pub fn shrink_to(&mut self, min_capacity: usize) {
1011 if self.capacity() > min_capacity {
1012 self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
1013 }
1014 }
1015
1016 /// Converts the vector into [`Box<[T]>`][owned slice].
1017 ///
1018 /// If the vector has excess capacity, its items will be moved into a
1019 /// newly-allocated buffer with exactly the right capacity.
1020 ///
1021 /// [owned slice]: Box
1022 ///
1023 /// # Examples
1024 ///
1025 /// ```
1026 /// let v = vec![1, 2, 3];
1027 ///
1028 /// let slice = v.into_boxed_slice();
1029 /// ```
1030 ///
1031 /// Any excess capacity is removed:
1032 ///
1033 /// ```
1034 /// let mut vec = Vec::with_capacity(10);
1035 /// vec.extend([1, 2, 3]);
1036 ///
1037 /// assert_eq!(vec.capacity(), 10);
1038 /// let slice = vec.into_boxed_slice();
1039 /// assert_eq!(slice.into_vec().capacity(), 3);
1040 /// ```
1041 #[cfg(not(no_global_oom_handling))]
1042 #[inline(always)]
1043 pub fn into_boxed_slice(mut self) -> Box<[T], A> {
1044 unsafe {
1045 self.shrink_to_fit();
1046 let me = ManuallyDrop::new(self);
1047 let buf = ptr::read(&me.buf);
1048 let len = me.len();
1049 buf.into_box(len).assume_init()
1050 }
1051 }
1052
1053 /// Shortens the vector, keeping the first `len` elements and dropping
1054 /// the rest.
1055 ///
1056 /// If `len` is greater than the vector's current length, this has no
1057 /// effect.
1058 ///
1059 /// The [`drain`] method can emulate `truncate`, but causes the excess
1060 /// elements to be returned instead of dropped.
1061 ///
1062 /// Note that this method has no effect on the allocated capacity
1063 /// of the vector.
1064 ///
1065 /// # Examples
1066 ///
1067 /// Truncating a five element vector to two elements:
1068 ///
1069 /// ```
1070 /// let mut vec = vec![1, 2, 3, 4, 5];
1071 /// vec.truncate(2);
1072 /// assert_eq!(vec, [1, 2]);
1073 /// ```
1074 ///
1075 /// No truncation occurs when `len` is greater than the vector's current
1076 /// length:
1077 ///
1078 /// ```
1079 /// let mut vec = vec![1, 2, 3];
1080 /// vec.truncate(8);
1081 /// assert_eq!(vec, [1, 2, 3]);
1082 /// ```
1083 ///
1084 /// Truncating when `len == 0` is equivalent to calling the [`clear`]
1085 /// method.
1086 ///
1087 /// ```
1088 /// let mut vec = vec![1, 2, 3];
1089 /// vec.truncate(0);
1090 /// assert_eq!(vec, []);
1091 /// ```
1092 ///
1093 /// [`clear`]: Vec::clear
1094 /// [`drain`]: Vec::drain
1095 #[inline(always)]
1096 pub fn truncate(&mut self, len: usize) {
1097 // This is safe because:
1098 //
1099 // * the slice passed to `drop_in_place` is valid; the `len > self.len`
1100 // case avoids creating an invalid slice, and
1101 // * the `len` of the vector is shrunk before calling `drop_in_place`,
1102 // such that no value will be dropped twice in case `drop_in_place`
1103 // were to panic once (if it panics twice, the program aborts).
1104 unsafe {
1105 // Note: It's intentional that this is `>` and not `>=`.
1106 // Changing it to `>=` has negative performance
1107 // implications in some cases. See #78884 for more.
1108 if len > self.len {
1109 return;
1110 }
1111 let remaining_len = self.len - len;
1112 let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
1113 self.len = len;
1114 ptr::drop_in_place(s);
1115 }
1116 }
1117
1118 /// Extracts a slice containing the entire vector.
1119 ///
1120 /// Equivalent to `&s[..]`.
1121 ///
1122 /// # Examples
1123 ///
1124 /// ```
1125 /// use std::io::{self, Write};
1126 /// let buffer = vec![1, 2, 3, 5, 8];
1127 /// io::sink().write(buffer.as_slice()).unwrap();
1128 /// ```
1129 #[inline(always)]
1130 pub fn as_slice(&self) -> &[T] {
1131 self
1132 }
1133
1134 /// Extracts a mutable slice of the entire vector.
1135 ///
1136 /// Equivalent to `&mut s[..]`.
1137 ///
1138 /// # Examples
1139 ///
1140 /// ```
1141 /// use std::io::{self, Read};
1142 /// let mut buffer = vec![0; 3];
1143 /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
1144 /// ```
1145 #[inline(always)]
1146 pub fn as_mut_slice(&mut self) -> &mut [T] {
1147 self
1148 }
1149
1150 /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
1151 /// valid for zero sized reads if the vector didn't allocate.
1152 ///
1153 /// The caller must ensure that the vector outlives the pointer this
1154 /// function returns, or else it will end up pointing to garbage.
1155 /// Modifying the vector may cause its buffer to be reallocated,
1156 /// which would also make any pointers to it invalid.
1157 ///
1158 /// The caller must also ensure that the memory the pointer (non-transitively) points to
1159 /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1160 /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1161 ///
1162 /// # Examples
1163 ///
1164 /// ```
1165 /// let x = vec![1, 2, 4];
1166 /// let x_ptr = x.as_ptr();
1167 ///
1168 /// unsafe {
1169 /// for i in 0..x.len() {
1170 /// assert_eq!(*x_ptr.add(i), 1 << i);
1171 /// }
1172 /// }
1173 /// ```
1174 ///
1175 /// [`as_mut_ptr`]: Vec::as_mut_ptr
1176 #[inline(always)]
1177 pub fn as_ptr(&self) -> *const T {
1178 // We shadow the slice method of the same name to avoid going through
1179 // `deref`, which creates an intermediate reference.
1180 let ptr = self.buf.ptr();
1181 unsafe {
1182 assume(!ptr.is_null());
1183 }
1184 ptr
1185 }
1186
1187 /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling
1188 /// raw pointer valid for zero sized reads if the vector didn't allocate.
1189 ///
1190 /// The caller must ensure that the vector outlives the pointer this
1191 /// function returns, or else it will end up pointing to garbage.
1192 /// Modifying the vector may cause its buffer to be reallocated,
1193 /// which would also make any pointers to it invalid.
1194 ///
1195 /// # Examples
1196 ///
1197 /// ```
1198 /// // Allocate vector big enough for 4 elements.
1199 /// let size = 4;
1200 /// let mut x: Vec<i32> = Vec::with_capacity(size);
1201 /// let x_ptr = x.as_mut_ptr();
1202 ///
1203 /// // Initialize elements via raw pointer writes, then set length.
1204 /// unsafe {
1205 /// for i in 0..size {
1206 /// *x_ptr.add(i) = i as i32;
1207 /// }
1208 /// x.set_len(size);
1209 /// }
1210 /// assert_eq!(&*x, &[0, 1, 2, 3]);
1211 /// ```
1212 #[inline(always)]
1213 pub fn as_mut_ptr(&mut self) -> *mut T {
1214 // We shadow the slice method of the same name to avoid going through
1215 // `deref_mut`, which creates an intermediate reference.
1216 let ptr = self.buf.ptr();
1217 unsafe {
1218 assume(!ptr.is_null());
1219 }
1220 ptr
1221 }
1222
1223 /// Returns a reference to the underlying allocator.
1224 #[inline(always)]
1225 pub fn allocator(&self) -> &A {
1226 self.buf.allocator()
1227 }
1228
1229 /// Forces the length of the vector to `new_len`.
1230 ///
1231 /// This is a low-level operation that maintains none of the normal
1232 /// invariants of the type. Normally changing the length of a vector
1233 /// is done using one of the safe operations instead, such as
1234 /// [`truncate`], [`resize`], [`extend`], or [`clear`].
1235 ///
1236 /// [`truncate`]: Vec::truncate
1237 /// [`resize`]: Vec::resize
1238 /// [`extend`]: Extend::extend
1239 /// [`clear`]: Vec::clear
1240 ///
1241 /// # Safety
1242 ///
1243 /// - `new_len` must be less than or equal to [`capacity()`].
1244 /// - The elements at `old_len..new_len` must be initialized.
1245 ///
1246 /// [`capacity()`]: Vec::capacity
1247 ///
1248 /// # Examples
1249 ///
1250 /// This method can be useful for situations in which the vector
1251 /// is serving as a buffer for other code, particularly over FFI:
1252 ///
1253 /// ```no_run
1254 /// # #![allow(dead_code)]
1255 /// # // This is just a minimal skeleton for the doc example;
1256 /// # // don't use this as a starting point for a real library.
1257 /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void }
1258 /// # const Z_OK: i32 = 0;
1259 /// # extern "C" {
1260 /// # fn deflateGetDictionary(
1261 /// # strm: *mut std::ffi::c_void,
1262 /// # dictionary: *mut u8,
1263 /// # dictLength: *mut usize,
1264 /// # ) -> i32;
1265 /// # }
1266 /// # impl StreamWrapper {
1267 /// pub fn get_dictionary(&self) -> Option<Vec<u8>> {
1268 /// // Per the FFI method's docs, "32768 bytes is always enough".
1269 /// let mut dict = Vec::with_capacity(32_768);
1270 /// let mut dict_length = 0;
1271 /// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
1272 /// // 1. `dict_length` elements were initialized.
1273 /// // 2. `dict_length` <= the capacity (32_768)
1274 /// // which makes `set_len` safe to call.
1275 /// unsafe {
1276 /// // Make the FFI call...
1277 /// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
1278 /// if r == Z_OK {
1279 /// // ...and update the length to what was initialized.
1280 /// dict.set_len(dict_length);
1281 /// Some(dict)
1282 /// } else {
1283 /// None
1284 /// }
1285 /// }
1286 /// }
1287 /// # }
1288 /// ```
1289 ///
1290 /// While the following example is sound, there is a memory leak since
1291 /// the inner vectors were not freed prior to the `set_len` call:
1292 ///
1293 /// ```
1294 /// let mut vec = vec![vec![1, 0, 0],
1295 /// vec![0, 1, 0],
1296 /// vec![0, 0, 1]];
1297 /// // SAFETY:
1298 /// // 1. `old_len..0` is empty so no elements need to be initialized.
1299 /// // 2. `0 <= capacity` always holds whatever `capacity` is.
1300 /// unsafe {
1301 /// vec.set_len(0);
1302 /// }
1303 /// ```
1304 ///
1305 /// Normally, here, one would use [`clear`] instead to correctly drop
1306 /// the contents and thus not leak memory.
1307 #[inline(always)]
1308 pub unsafe fn set_len(&mut self, new_len: usize) {
1309 debug_assert!(new_len <= self.capacity());
1310
1311 self.len = new_len;
1312 }
1313
1314 /// Removes an element from the vector and returns it.
1315 ///
1316 /// The removed element is replaced by the last element of the vector.
1317 ///
1318 /// This does not preserve ordering, but is *O*(1).
1319 /// If you need to preserve the element order, use [`remove`] instead.
1320 ///
1321 /// [`remove`]: Vec::remove
1322 ///
1323 /// # Panics
1324 ///
1325 /// Panics if `index` is out of bounds.
1326 ///
1327 /// # Examples
1328 ///
1329 /// ```
1330 /// let mut v = vec!["foo", "bar", "baz", "qux"];
1331 ///
1332 /// assert_eq!(v.swap_remove(1), "bar");
1333 /// assert_eq!(v, ["foo", "qux", "baz"]);
1334 ///
1335 /// assert_eq!(v.swap_remove(0), "foo");
1336 /// assert_eq!(v, ["baz", "qux"]);
1337 /// ```
1338 #[inline(always)]
1339 pub fn swap_remove(&mut self, index: usize) -> T {
1340 #[cold]
1341 #[inline(never)]
1342 fn assert_failed(index: usize, len: usize) -> ! {
1343 panic!(
1344 "swap_remove index (is {}) should be < len (is {})",
1345 index, len
1346 );
1347 }
1348
1349 let len = self.len();
1350 if index >= len {
1351 assert_failed(index, len);
1352 }
1353 unsafe {
1354 // We replace self[index] with the last element. Note that if the
1355 // bounds check above succeeds there must be a last element (which
1356 // can be self[index] itself).
1357 let value = ptr::read(self.as_ptr().add(index));
1358 let base_ptr = self.as_mut_ptr();
1359 ptr::copy(base_ptr.add(len - 1), base_ptr.add(index), 1);
1360 self.set_len(len - 1);
1361 value
1362 }
1363 }
1364
1365 /// Inserts an element at position `index` within the vector, shifting all
1366 /// elements after it to the right.
1367 ///
1368 /// # Panics
1369 ///
1370 /// Panics if `index > len`.
1371 ///
1372 /// # Examples
1373 ///
1374 /// ```
1375 /// let mut vec = vec![1, 2, 3];
1376 /// vec.insert(1, 4);
1377 /// assert_eq!(vec, [1, 4, 2, 3]);
1378 /// vec.insert(4, 5);
1379 /// assert_eq!(vec, [1, 4, 2, 3, 5]);
1380 /// ```
1381 #[cfg(not(no_global_oom_handling))]
1382 pub fn insert(&mut self, index: usize, element: T) {
1383 #[cold]
1384 #[inline(never)]
1385 fn assert_failed(index: usize, len: usize) -> ! {
1386 panic!(
1387 "insertion index (is {}) should be <= len (is {})",
1388 index, len
1389 );
1390 }
1391
1392 let len = self.len();
1393
1394 // space for the new element
1395 if len == self.buf.capacity() {
1396 self.reserve(1);
1397 }
1398
1399 unsafe {
1400 // infallible
1401 // The spot to put the new value
1402 {
1403 let p = self.as_mut_ptr().add(index);
1404 match cmp::Ord::cmp(&index, &len) {
1405 Ordering::Less => {
1406 // Shift everything over to make space. (Duplicating the
1407 // `index`th element into two consecutive places.)
1408 ptr::copy(p, p.add(1), len - index);
1409 }
1410 Ordering::Equal => {
1411 // No elements need shifting.
1412 }
1413 Ordering::Greater => {
1414 assert_failed(index, len);
1415 }
1416 }
1417 // Write it in, overwriting the first copy of the `index`th
1418 // element.
1419 ptr::write(p, element);
1420 }
1421 self.set_len(len + 1);
1422 }
1423 }
1424
1425 /// Removes and returns the element at position `index` within the vector,
1426 /// shifting all elements after it to the left.
1427 ///
1428 /// Note: Because this shifts over the remaining elements, it has a
1429 /// worst-case performance of *O*(*n*). If you don't need the order of elements
1430 /// to be preserved, use [`swap_remove`] instead. If you'd like to remove
1431 /// elements from the beginning of the `Vec`, consider using
1432 /// [`VecDeque::pop_front`] instead.
1433 ///
1434 /// [`swap_remove`]: Vec::swap_remove
1435 /// [`VecDeque::pop_front`]: alloc_crate::collections::VecDeque::pop_front
1436 ///
1437 /// # Panics
1438 ///
1439 /// Panics if `index` is out of bounds.
1440 ///
1441 /// # Examples
1442 ///
1443 /// ```
1444 /// let mut v = vec![1, 2, 3];
1445 /// assert_eq!(v.remove(1), 2);
1446 /// assert_eq!(v, [1, 3]);
1447 /// ```
1448 #[track_caller]
1449 #[inline(always)]
1450 pub fn remove(&mut self, index: usize) -> T {
1451 #[cold]
1452 #[inline(never)]
1453 #[track_caller]
1454 fn assert_failed(index: usize, len: usize) -> ! {
1455 panic!("removal index (is {}) should be < len (is {})", index, len);
1456 }
1457
1458 let len = self.len();
1459 if index >= len {
1460 assert_failed(index, len);
1461 }
1462 unsafe {
1463 // infallible
1464 let ret;
1465 {
1466 // the place we are taking from.
1467 let ptr = self.as_mut_ptr().add(index);
1468 // copy it out, unsafely having a copy of the value on
1469 // the stack and in the vector at the same time.
1470 ret = ptr::read(ptr);
1471
1472 // Shift everything down to fill in that spot.
1473 ptr::copy(ptr.add(1), ptr, len - index - 1);
1474 }
1475 self.set_len(len - 1);
1476 ret
1477 }
1478 }
1479
1480 /// Retains only the elements specified by the predicate.
1481 ///
1482 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
1483 /// This method operates in place, visiting each element exactly once in the
1484 /// original order, and preserves the order of the retained elements.
1485 ///
1486 /// # Examples
1487 ///
1488 /// ```
1489 /// let mut vec = vec![1, 2, 3, 4];
1490 /// vec.retain(|&x| x % 2 == 0);
1491 /// assert_eq!(vec, [2, 4]);
1492 /// ```
1493 ///
1494 /// Because the elements are visited exactly once in the original order,
1495 /// external state may be used to decide which elements to keep.
1496 ///
1497 /// ```
1498 /// let mut vec = vec![1, 2, 3, 4, 5];
1499 /// let keep = [false, true, true, false, true];
1500 /// let mut iter = keep.iter();
1501 /// vec.retain(|_| *iter.next().unwrap());
1502 /// assert_eq!(vec, [2, 3, 5]);
1503 /// ```
1504 #[inline(always)]
1505 pub fn retain<F>(&mut self, mut f: F)
1506 where
1507 F: FnMut(&T) -> bool,
1508 {
1509 self.retain_mut(|elem| f(elem));
1510 }
1511
1512 /// Retains only the elements specified by the predicate, passing a mutable reference to it.
1513 ///
1514 /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
1515 /// This method operates in place, visiting each element exactly once in the
1516 /// original order, and preserves the order of the retained elements.
1517 ///
1518 /// # Examples
1519 ///
1520 /// ```
1521 /// let mut vec = vec![1, 2, 3, 4];
1522 /// vec.retain_mut(|x| if *x <= 3 {
1523 /// *x += 1;
1524 /// true
1525 /// } else {
1526 /// false
1527 /// });
1528 /// assert_eq!(vec, [2, 3, 4]);
1529 /// ```
1530 #[inline]
1531 pub fn retain_mut<F>(&mut self, mut f: F)
1532 where
1533 F: FnMut(&mut T) -> bool,
1534 {
1535 let original_len = self.len();
1536 // Avoid double drop if the drop guard is not executed,
1537 // since we may make some holes during the process.
1538 unsafe { self.set_len(0) };
1539
1540 // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
1541 // |<- processed len ->| ^- next to check
1542 // |<- deleted cnt ->|
1543 // |<- original_len ->|
1544 // Kept: Elements which predicate returns true on.
1545 // Hole: Moved or dropped element slot.
1546 // Unchecked: Unchecked valid elements.
1547 //
1548 // This drop guard will be invoked when predicate or `drop` of element panicked.
1549 // It shifts unchecked elements to cover holes and `set_len` to the correct length.
1550 // In cases when predicate and `drop` never panick, it will be optimized out.
1551 struct BackshiftOnDrop<'a, T, A: Allocator> {
1552 v: &'a mut Vec<T, A>,
1553 processed_len: usize,
1554 deleted_cnt: usize,
1555 original_len: usize,
1556 }
1557
1558 impl<T, A: Allocator> Drop for BackshiftOnDrop<'_, T, A> {
1559 fn drop(&mut self) {
1560 if self.deleted_cnt > 0 {
1561 // SAFETY: Trailing unchecked items must be valid since we never touch them.
1562 unsafe {
1563 ptr::copy(
1564 self.v.as_ptr().add(self.processed_len),
1565 self.v
1566 .as_mut_ptr()
1567 .add(self.processed_len - self.deleted_cnt),
1568 self.original_len - self.processed_len,
1569 );
1570 }
1571 }
1572 // SAFETY: After filling holes, all items are in contiguous memory.
1573 unsafe {
1574 self.v.set_len(self.original_len - self.deleted_cnt);
1575 }
1576 }
1577 }
1578
1579 let mut g = BackshiftOnDrop {
1580 v: self,
1581 processed_len: 0,
1582 deleted_cnt: 0,
1583 original_len,
1584 };
1585
1586 fn process_loop<F, T, A: Allocator, const DELETED: bool>(
1587 original_len: usize,
1588 f: &mut F,
1589 g: &mut BackshiftOnDrop<'_, T, A>,
1590 ) where
1591 F: FnMut(&mut T) -> bool,
1592 {
1593 while g.processed_len != original_len {
1594 // SAFETY: Unchecked element must be valid.
1595 let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) };
1596 if !f(cur) {
1597 // Advance early to avoid double drop if `drop_in_place` panicked.
1598 g.processed_len += 1;
1599 g.deleted_cnt += 1;
1600 // SAFETY: We never touch this element again after dropped.
1601 unsafe { ptr::drop_in_place(cur) };
1602 // We already advanced the counter.
1603 if DELETED {
1604 continue;
1605 } else {
1606 break;
1607 }
1608 }
1609 if DELETED {
1610 // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
1611 // We use copy for move, and never touch this element again.
1612 unsafe {
1613 let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
1614 ptr::copy_nonoverlapping(cur, hole_slot, 1);
1615 }
1616 }
1617 g.processed_len += 1;
1618 }
1619 }
1620
1621 // Stage 1: Nothing was deleted.
1622 process_loop::<F, T, A, false>(original_len, &mut f, &mut g);
1623
1624 // Stage 2: Some elements were deleted.
1625 process_loop::<F, T, A, true>(original_len, &mut f, &mut g);
1626
1627 // All item are processed. This can be optimized to `set_len` by LLVM.
1628 drop(g);
1629 }
1630
1631 /// Removes all but the first of consecutive elements in the vector that resolve to the same
1632 /// key.
1633 ///
1634 /// If the vector is sorted, this removes all duplicates.
1635 ///
1636 /// # Examples
1637 ///
1638 /// ```
1639 /// let mut vec = vec![10, 20, 21, 30, 20];
1640 ///
1641 /// vec.dedup_by_key(|i| *i / 10);
1642 ///
1643 /// assert_eq!(vec, [10, 20, 30, 20]);
1644 /// ```
1645 #[inline(always)]
1646 pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1647 where
1648 F: FnMut(&mut T) -> K,
1649 K: PartialEq,
1650 {
1651 self.dedup_by(|a, b| key(a) == key(b))
1652 }
1653
1654 /// Removes all but the first of consecutive elements in the vector satisfying a given equality
1655 /// relation.
1656 ///
1657 /// The `same_bucket` function is passed references to two elements from the vector and
1658 /// must determine if the elements compare equal. The elements are passed in opposite order
1659 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
1660 ///
1661 /// If the vector is sorted, this removes all duplicates.
1662 ///
1663 /// # Examples
1664 ///
1665 /// ```
1666 /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
1667 ///
1668 /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
1669 ///
1670 /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
1671 /// ```
1672 #[inline]
1673 pub fn dedup_by<F>(&mut self, mut same_bucket: F)
1674 where
1675 F: FnMut(&mut T, &mut T) -> bool,
1676 {
1677 let len = self.len();
1678 if len <= 1 {
1679 return;
1680 }
1681
1682 /* INVARIANT: vec.len() > read >= write > write-1 >= 0 */
1683 struct FillGapOnDrop<'a, T, A: Allocator> {
1684 /* Offset of the element we want to check if it is duplicate */
1685 read: usize,
1686
1687 /* Offset of the place where we want to place the non-duplicate
1688 * when we find it. */
1689 write: usize,
1690
1691 /* The Vec that would need correction if `same_bucket` panicked */
1692 vec: &'a mut Vec<T, A>,
1693 }
1694
1695 impl<'a, T, A: Allocator> Drop for FillGapOnDrop<'a, T, A> {
1696 fn drop(&mut self) {
1697 /* This code gets executed when `same_bucket` panics */
1698
1699 /* SAFETY: invariant guarantees that `read - write`
1700 * and `len - read` never overflow and that the copy is always
1701 * in-bounds. */
1702 unsafe {
1703 let ptr = self.vec.as_mut_ptr();
1704 let len = self.vec.len();
1705
1706 /* How many items were left when `same_bucket` panicked.
1707 * Basically vec[read..].len() */
1708 let items_left = len.wrapping_sub(self.read);
1709
1710 /* Pointer to first item in vec[write..write+items_left] slice */
1711 let dropped_ptr = ptr.add(self.write);
1712 /* Pointer to first item in vec[read..] slice */
1713 let valid_ptr = ptr.add(self.read);
1714
1715 /* Copy `vec[read..]` to `vec[write..write+items_left]`.
1716 * The slices can overlap, so `copy_nonoverlapping` cannot be used */
1717 ptr::copy(valid_ptr, dropped_ptr, items_left);
1718
1719 /* How many items have been already dropped
1720 * Basically vec[read..write].len() */
1721 let dropped = self.read.wrapping_sub(self.write);
1722
1723 self.vec.set_len(len - dropped);
1724 }
1725 }
1726 }
1727
1728 let mut gap = FillGapOnDrop {
1729 read: 1,
1730 write: 1,
1731 vec: self,
1732 };
1733 let ptr = gap.vec.as_mut_ptr();
1734
1735 /* Drop items while going through Vec, it should be more efficient than
1736 * doing slice partition_dedup + truncate */
1737
1738 /* SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr
1739 * are always in-bounds and read_ptr never aliases prev_ptr */
1740 unsafe {
1741 while gap.read < len {
1742 let read_ptr = ptr.add(gap.read);
1743 let prev_ptr = ptr.add(gap.write.wrapping_sub(1));
1744
1745 if same_bucket(&mut *read_ptr, &mut *prev_ptr) {
1746 // Increase `gap.read` now since the drop may panic.
1747 gap.read += 1;
1748 /* We have found duplicate, drop it in-place */
1749 ptr::drop_in_place(read_ptr);
1750 } else {
1751 let write_ptr = ptr.add(gap.write);
1752
1753 /* Because `read_ptr` can be equal to `write_ptr`, we either
1754 * have to use `copy` or conditional `copy_nonoverlapping`.
1755 * Looks like the first option is faster. */
1756 ptr::copy(read_ptr, write_ptr, 1);
1757
1758 /* We have filled that place, so go further */
1759 gap.write += 1;
1760 gap.read += 1;
1761 }
1762 }
1763
1764 /* Technically we could let `gap` clean up with its Drop, but
1765 * when `same_bucket` is guaranteed to not panic, this bloats a little
1766 * the codegen, so we just do it manually */
1767 gap.vec.set_len(gap.write);
1768 mem::forget(gap);
1769 }
1770 }
1771
1772 /// Appends an element to the back of a collection.
1773 ///
1774 /// # Panics
1775 ///
1776 /// Panics if the new capacity exceeds `isize::MAX` bytes.
1777 ///
1778 /// # Examples
1779 ///
1780 /// ```
1781 /// let mut vec = vec![1, 2];
1782 /// vec.push(3);
1783 /// assert_eq!(vec, [1, 2, 3]);
1784 /// ```
1785 #[cfg(not(no_global_oom_handling))]
1786 #[inline(always)]
1787 pub fn push(&mut self, value: T) {
1788 // This will panic or abort if we would allocate > isize::MAX bytes
1789 // or if the length increment would overflow for zero-sized types.
1790 if self.len == self.buf.capacity() {
1791 self.buf.reserve_for_push(self.len);
1792 }
1793 unsafe {
1794 let end = self.as_mut_ptr().add(self.len);
1795 ptr::write(end, value);
1796 self.len += 1;
1797 }
1798 }
1799
1800 /// Appends an element if there is sufficient spare capacity, otherwise an error is returned
1801 /// with the element.
1802 ///
1803 /// Unlike [`push`] this method will not reallocate when there's insufficient capacity.
1804 /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity.
1805 ///
1806 /// [`push`]: Vec::push
1807 /// [`reserve`]: Vec::reserve
1808 /// [`try_reserve`]: Vec::try_reserve
1809 ///
1810 /// # Examples
1811 ///
1812 /// A manual, panic-free alternative to [`FromIterator`]:
1813 ///
1814 /// ```
1815 /// #![feature(vec_push_within_capacity)]
1816 ///
1817 /// use std::collections::TryReserveError;
1818 /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> {
1819 /// let mut vec = Vec::new();
1820 /// for value in iter {
1821 /// if let Err(value) = vec.push_within_capacity(value) {
1822 /// vec.try_reserve(1)?;
1823 /// // this cannot fail, the previous line either returned or added at least 1 free slot
1824 /// let _ = vec.push_within_capacity(value);
1825 /// }
1826 /// }
1827 /// Ok(vec)
1828 /// }
1829 /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100)));
1830 /// ```
1831 #[inline(always)]
1832 pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> {
1833 if self.len == self.buf.capacity() {
1834 return Err(value);
1835 }
1836 unsafe {
1837 let end = self.as_mut_ptr().add(self.len);
1838 ptr::write(end, value);
1839 self.len += 1;
1840 }
1841 Ok(())
1842 }
1843
1844 /// Removes the last element from a vector and returns it, or [`None`] if it
1845 /// is empty.
1846 ///
1847 /// If you'd like to pop the first element, consider using
1848 /// [`VecDeque::pop_front`] instead.
1849 ///
1850 /// [`VecDeque::pop_front`]: alloc_crate::collections::VecDeque::pop_front
1851 ///
1852 /// # Examples
1853 ///
1854 /// ```
1855 /// let mut vec = vec![1, 2, 3];
1856 /// assert_eq!(vec.pop(), Some(3));
1857 /// assert_eq!(vec, [1, 2]);
1858 /// ```
1859 #[inline(always)]
1860 pub fn pop(&mut self) -> Option<T> {
1861 if self.len == 0 {
1862 None
1863 } else {
1864 unsafe {
1865 self.len -= 1;
1866 Some(ptr::read(self.as_ptr().add(self.len())))
1867 }
1868 }
1869 }
1870
1871 /// Moves all the elements of `other` into `self`, leaving `other` empty.
1872 ///
1873 /// # Panics
1874 ///
1875 /// Panics if the new capacity exceeds `isize::MAX` bytes.
1876 ///
1877 /// # Examples
1878 ///
1879 /// ```
1880 /// let mut vec = vec![1, 2, 3];
1881 /// let mut vec2 = vec![4, 5, 6];
1882 /// vec.append(&mut vec2);
1883 /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
1884 /// assert_eq!(vec2, []);
1885 /// ```
1886 #[cfg(not(no_global_oom_handling))]
1887 #[inline(always)]
1888 pub fn append(&mut self, other: &mut Self) {
1889 unsafe {
1890 self.append_elements(other.as_slice() as _);
1891 other.set_len(0);
1892 }
1893 }
1894
1895 /// Appends elements to `self` from other buffer.
1896 #[cfg(not(no_global_oom_handling))]
1897 #[inline(always)]
1898 unsafe fn append_elements(&mut self, other: *const [T]) {
1899 let count = unsafe { (*other).len() };
1900 self.reserve(count);
1901 let len = self.len();
1902 unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) };
1903 self.len += count;
1904 }
1905
1906 /// Removes the specified range from the vector in bulk, returning all
1907 /// removed elements as an iterator. If the iterator is dropped before
1908 /// being fully consumed, it drops the remaining removed elements.
1909 ///
1910 /// The returned iterator keeps a mutable borrow on the vector to optimize
1911 /// its implementation.
1912 ///
1913 /// # Panics
1914 ///
1915 /// Panics if the starting point is greater than the end point or if
1916 /// the end point is greater than the length of the vector.
1917 ///
1918 /// # Leaking
1919 ///
1920 /// If the returned iterator goes out of scope without being dropped (due to
1921 /// [`mem::forget`], for example), the vector may have lost and leaked
1922 /// elements arbitrarily, including elements outside the range.
1923 ///
1924 /// # Examples
1925 ///
1926 /// ```
1927 /// let mut v = vec![1, 2, 3];
1928 /// let u: Vec<_> = v.drain(1..).collect();
1929 /// assert_eq!(v, &[1]);
1930 /// assert_eq!(u, &[2, 3]);
1931 ///
1932 /// // A full range clears the vector, like `clear()` does
1933 /// v.drain(..);
1934 /// assert_eq!(v, &[]);
1935 /// ```
1936 #[inline(always)]
1937 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
1938 where
1939 R: RangeBounds<usize>,
1940 {
1941 // Memory safety
1942 //
1943 // When the Drain is first created, it shortens the length of
1944 // the source vector to make sure no uninitialized or moved-from elements
1945 // are accessible at all if the Drain's destructor never gets to run.
1946 //
1947 // Drain will ptr::read out the values to remove.
1948 // When finished, remaining tail of the vec is copied back to cover
1949 // the hole, and the vector length is restored to the new length.
1950 //
1951 let len = self.len();
1952
1953 // Replaced by code below
1954 // let Range { start, end } = slice::range(range, ..len);
1955
1956 // Panics if range is out of bounds
1957 let _ = &self.as_slice()[(range.start_bound().cloned(), range.end_bound().cloned())];
1958
1959 let start = match range.start_bound() {
1960 Bound::Included(&n) => n,
1961 Bound::Excluded(&n) => n + 1,
1962 Bound::Unbounded => 0,
1963 };
1964 let end = match range.end_bound() {
1965 Bound::Included(&n) => n + 1,
1966 Bound::Excluded(&n) => n,
1967 Bound::Unbounded => len,
1968 };
1969
1970 unsafe {
1971 // set self.vec length's to start, to be safe in case Drain is leaked
1972 self.set_len(start);
1973 let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start);
1974 Drain {
1975 tail_start: end,
1976 tail_len: len - end,
1977 iter: range_slice.iter(),
1978 vec: NonNull::from(self),
1979 }
1980 }
1981 }
1982
1983 /// Clears the vector, removing all values.
1984 ///
1985 /// Note that this method has no effect on the allocated capacity
1986 /// of the vector.
1987 ///
1988 /// # Examples
1989 ///
1990 /// ```
1991 /// let mut v = vec![1, 2, 3];
1992 ///
1993 /// v.clear();
1994 ///
1995 /// assert!(v.is_empty());
1996 /// ```
1997 #[inline(always)]
1998 pub fn clear(&mut self) {
1999 let elems: *mut [T] = self.as_mut_slice();
2000
2001 // SAFETY:
2002 // - `elems` comes directly from `as_mut_slice` and is therefore valid.
2003 // - Setting `self.len` before calling `drop_in_place` means that,
2004 // if an element's `Drop` impl panics, the vector's `Drop` impl will
2005 // do nothing (leaking the rest of the elements) instead of dropping
2006 // some twice.
2007 unsafe {
2008 self.len = 0;
2009 ptr::drop_in_place(elems);
2010 }
2011 }
2012
2013 /// Returns the number of elements in the vector, also referred to
2014 /// as its 'length'.
2015 ///
2016 /// # Examples
2017 ///
2018 /// ```
2019 /// let a = vec![1, 2, 3];
2020 /// assert_eq!(a.len(), 3);
2021 /// ```
2022 #[inline(always)]
2023 pub fn len(&self) -> usize {
2024 self.len
2025 }
2026
2027 /// Returns `true` if the vector contains no elements.
2028 ///
2029 /// # Examples
2030 ///
2031 /// ```
2032 /// let mut v = Vec::new();
2033 /// assert!(v.is_empty());
2034 ///
2035 /// v.push(1);
2036 /// assert!(!v.is_empty());
2037 /// ```
2038 #[inline(always)]
2039 pub fn is_empty(&self) -> bool {
2040 self.len() == 0
2041 }
2042
2043 /// Splits the collection into two at the given index.
2044 ///
2045 /// Returns a newly allocated vector containing the elements in the range
2046 /// `[at, len)`. After the call, the original vector will be left containing
2047 /// the elements `[0, at)` with its previous capacity unchanged.
2048 ///
2049 /// # Panics
2050 ///
2051 /// Panics if `at > len`.
2052 ///
2053 /// # Examples
2054 ///
2055 /// ```
2056 /// let mut vec = vec![1, 2, 3];
2057 /// let vec2 = vec.split_off(1);
2058 /// assert_eq!(vec, [1]);
2059 /// assert_eq!(vec2, [2, 3]);
2060 /// ```
2061 #[cfg(not(no_global_oom_handling))]
2062 #[inline(always)]
2063 #[must_use = "use `.truncate()` if you don't need the other half"]
2064 pub fn split_off(&mut self, at: usize) -> Self
2065 where
2066 A: Clone,
2067 {
2068 #[cold]
2069 #[inline(never)]
2070 fn assert_failed(at: usize, len: usize) -> ! {
2071 panic!("`at` split index (is {}) should be <= len (is {})", at, len);
2072 }
2073
2074 if at > self.len() {
2075 assert_failed(at, self.len());
2076 }
2077
2078 if at == 0 {
2079 // the new vector can take over the original buffer and avoid the copy
2080 return mem::replace(
2081 self,
2082 Vec::with_capacity_in(self.capacity(), self.allocator().clone()),
2083 );
2084 }
2085
2086 let other_len = self.len - at;
2087 let mut other = Vec::with_capacity_in(other_len, self.allocator().clone());
2088
2089 // Unsafely `set_len` and copy items to `other`.
2090 unsafe {
2091 self.set_len(at);
2092 other.set_len(other_len);
2093
2094 ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
2095 }
2096 other
2097 }
2098
2099 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
2100 ///
2101 /// If `new_len` is greater than `len`, the `Vec` is extended by the
2102 /// difference, with each additional slot filled with the result of
2103 /// calling the closure `f`. The return values from `f` will end up
2104 /// in the `Vec` in the order they have been generated.
2105 ///
2106 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2107 ///
2108 /// This method uses a closure to create new values on every push. If
2109 /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you
2110 /// want to use the [`Default`] trait to generate values, you can
2111 /// pass [`Default::default`] as the second argument.
2112 ///
2113 /// # Examples
2114 ///
2115 /// ```
2116 /// let mut vec = vec![1, 2, 3];
2117 /// vec.resize_with(5, Default::default);
2118 /// assert_eq!(vec, [1, 2, 3, 0, 0]);
2119 ///
2120 /// let mut vec = vec![];
2121 /// let mut p = 1;
2122 /// vec.resize_with(4, || { p *= 2; p });
2123 /// assert_eq!(vec, [2, 4, 8, 16]);
2124 /// ```
2125 #[cfg(not(no_global_oom_handling))]
2126 #[inline(always)]
2127 pub fn resize_with<F>(&mut self, new_len: usize, f: F)
2128 where
2129 F: FnMut() -> T,
2130 {
2131 let len = self.len();
2132 if new_len > len {
2133 self.extend(iter::repeat_with(f).take(new_len - len));
2134 } else {
2135 self.truncate(new_len);
2136 }
2137 }
2138
2139 /// Consumes and leaks the `Vec`, returning a mutable reference to the contents,
2140 /// `&'a mut [T]`. Note that the type `T` must outlive the chosen lifetime
2141 /// `'a`. If the type has only static references, or none at all, then this
2142 /// may be chosen to be `'static`.
2143 ///
2144 /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`,
2145 /// so the leaked allocation may include unused capacity that is not part
2146 /// of the returned slice.
2147 ///
2148 /// This function is mainly useful for data that lives for the remainder of
2149 /// the program's life. Dropping the returned reference will cause a memory
2150 /// leak.
2151 ///
2152 /// # Examples
2153 ///
2154 /// Simple usage:
2155 ///
2156 /// ```
2157 /// let x = vec![1, 2, 3];
2158 /// let static_ref: &'static mut [usize] = x.leak();
2159 /// static_ref[0] += 1;
2160 /// assert_eq!(static_ref, &[2, 2, 3]);
2161 /// ```
2162 #[inline(always)]
2163 pub fn leak<'a>(self) -> &'a mut [T]
2164 where
2165 A: 'a,
2166 {
2167 let mut me = ManuallyDrop::new(self);
2168 unsafe { slice::from_raw_parts_mut(me.as_mut_ptr(), me.len) }
2169 }
2170
2171 /// Returns the remaining spare capacity of the vector as a slice of
2172 /// `MaybeUninit<T>`.
2173 ///
2174 /// The returned slice can be used to fill the vector with data (e.g. by
2175 /// reading from a file) before marking the data as initialized using the
2176 /// [`set_len`] method.
2177 ///
2178 /// [`set_len`]: Vec::set_len
2179 ///
2180 /// # Examples
2181 ///
2182 /// ```
2183 /// // Allocate vector big enough for 10 elements.
2184 /// let mut v = Vec::with_capacity(10);
2185 ///
2186 /// // Fill in the first 3 elements.
2187 /// let uninit = v.spare_capacity_mut();
2188 /// uninit[0].write(0);
2189 /// uninit[1].write(1);
2190 /// uninit[2].write(2);
2191 ///
2192 /// // Mark the first 3 elements of the vector as being initialized.
2193 /// unsafe {
2194 /// v.set_len(3);
2195 /// }
2196 ///
2197 /// assert_eq!(&v, &[0, 1, 2]);
2198 /// ```
2199 #[inline(always)]
2200 pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
2201 // Note:
2202 // This method is not implemented in terms of `split_at_spare_mut`,
2203 // to prevent invalidation of pointers to the buffer.
2204 unsafe {
2205 slice::from_raw_parts_mut(
2206 self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
2207 self.buf.capacity() - self.len,
2208 )
2209 }
2210 }
2211
2212 /// Returns vector content as a slice of `T`, along with the remaining spare
2213 /// capacity of the vector as a slice of `MaybeUninit<T>`.
2214 ///
2215 /// The returned spare capacity slice can be used to fill the vector with data
2216 /// (e.g. by reading from a file) before marking the data as initialized using
2217 /// the [`set_len`] method.
2218 ///
2219 /// [`set_len`]: Vec::set_len
2220 ///
2221 /// Note that this is a low-level API, which should be used with care for
2222 /// optimization purposes. If you need to append data to a `Vec`
2223 /// you can use [`push`], [`extend`], [`extend_from_slice`],
2224 /// [`extend_from_within`], [`insert`], [`append`], [`resize`] or
2225 /// [`resize_with`], depending on your exact needs.
2226 ///
2227 /// [`push`]: Vec::push
2228 /// [`extend`]: Vec::extend
2229 /// [`extend_from_slice`]: Vec::extend_from_slice
2230 /// [`extend_from_within`]: Vec::extend_from_within
2231 /// [`insert`]: Vec::insert
2232 /// [`append`]: Vec::append
2233 /// [`resize`]: Vec::resize
2234 /// [`resize_with`]: Vec::resize_with
2235 ///
2236 /// # Examples
2237 ///
2238 /// ```
2239 /// #![feature(vec_split_at_spare)]
2240 ///
2241 /// let mut v = vec![1, 1, 2];
2242 ///
2243 /// // Reserve additional space big enough for 10 elements.
2244 /// v.reserve(10);
2245 ///
2246 /// let (init, uninit) = v.split_at_spare_mut();
2247 /// let sum = init.iter().copied().sum::<u32>();
2248 ///
2249 /// // Fill in the next 4 elements.
2250 /// uninit[0].write(sum);
2251 /// uninit[1].write(sum * 2);
2252 /// uninit[2].write(sum * 3);
2253 /// uninit[3].write(sum * 4);
2254 ///
2255 /// // Mark the 4 elements of the vector as being initialized.
2256 /// unsafe {
2257 /// let len = v.len();
2258 /// v.set_len(len + 4);
2259 /// }
2260 ///
2261 /// assert_eq!(&v, &[1, 1, 2, 4, 8, 12, 16]);
2262 /// ```
2263 #[inline(always)]
2264 pub fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) {
2265 // SAFETY:
2266 // - len is ignored and so never changed
2267 let (init, spare, _) = unsafe { self.split_at_spare_mut_with_len() };
2268 (init, spare)
2269 }
2270
2271 /// Safety: changing returned .2 (&mut usize) is considered the same as calling `.set_len(_)`.
2272 ///
2273 /// This method provides unique access to all vec parts at once in `extend_from_within`.
2274 unsafe fn split_at_spare_mut_with_len(
2275 &mut self,
2276 ) -> (&mut [T], &mut [MaybeUninit<T>], &mut usize) {
2277 let ptr = self.as_mut_ptr();
2278 // SAFETY:
2279 // - `ptr` is guaranteed to be valid for `self.len` elements
2280 // - but the allocation extends out to `self.buf.capacity()` elements, possibly
2281 // uninitialized
2282 let spare_ptr = unsafe { ptr.add(self.len) };
2283 let spare_ptr = spare_ptr.cast::<MaybeUninit<T>>();
2284 let spare_len = self.buf.capacity() - self.len;
2285
2286 // SAFETY:
2287 // - `ptr` is guaranteed to be valid for `self.len` elements
2288 // - `spare_ptr` is pointing one element past the buffer, so it doesn't overlap with `initialized`
2289 unsafe {
2290 let initialized = slice::from_raw_parts_mut(ptr, self.len);
2291 let spare = slice::from_raw_parts_mut(spare_ptr, spare_len);
2292
2293 (initialized, spare, &mut self.len)
2294 }
2295 }
2296}
2297
2298impl<T: Clone, A: Allocator> Vec<T, A> {
2299 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
2300 ///
2301 /// If `new_len` is greater than `len`, the `Vec` is extended by the
2302 /// difference, with each additional slot filled with `value`.
2303 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
2304 ///
2305 /// This method requires `T` to implement [`Clone`],
2306 /// in order to be able to clone the passed value.
2307 /// If you need more flexibility (or want to rely on [`Default`] instead of
2308 /// [`Clone`]), use [`Vec::resize_with`].
2309 /// If you only need to resize to a smaller size, use [`Vec::truncate`].
2310 ///
2311 /// # Examples
2312 ///
2313 /// ```
2314 /// let mut vec = vec!["hello"];
2315 /// vec.resize(3, "world");
2316 /// assert_eq!(vec, ["hello", "world", "world"]);
2317 ///
2318 /// let mut vec = vec![1, 2, 3, 4];
2319 /// vec.resize(2, 0);
2320 /// assert_eq!(vec, [1, 2]);
2321 /// ```
2322 #[cfg(not(no_global_oom_handling))]
2323 #[inline(always)]
2324 pub fn resize(&mut self, new_len: usize, value: T) {
2325 let len = self.len();
2326
2327 if new_len > len {
2328 self.extend_with(new_len - len, ExtendElement(value))
2329 } else {
2330 self.truncate(new_len);
2331 }
2332 }
2333
2334 /// Clones and appends all elements in a slice to the `Vec`.
2335 ///
2336 /// Iterates over the slice `other`, clones each element, and then appends
2337 /// it to this `Vec`. The `other` slice is traversed in-order.
2338 ///
2339 /// Note that this function is same as [`extend`] except that it is
2340 /// specialized to work with slices instead. If and when Rust gets
2341 /// specialization this function will likely be deprecated (but still
2342 /// available).
2343 ///
2344 /// # Examples
2345 ///
2346 /// ```
2347 /// let mut vec = vec![1];
2348 /// vec.extend_from_slice(&[2, 3, 4]);
2349 /// assert_eq!(vec, [1, 2, 3, 4]);
2350 /// ```
2351 ///
2352 /// [`extend`]: Vec::extend
2353 #[cfg(not(no_global_oom_handling))]
2354 #[inline(always)]
2355 pub fn extend_from_slice(&mut self, other: &[T]) {
2356 self.extend(other.iter().cloned())
2357 }
2358
2359 /// Copies elements from `src` range to the end of the vector.
2360 ///
2361 /// # Panics
2362 ///
2363 /// Panics if the starting point is greater than the end point or if
2364 /// the end point is greater than the length of the vector.
2365 ///
2366 /// # Examples
2367 ///
2368 /// ```
2369 /// let mut vec = vec![0, 1, 2, 3, 4];
2370 ///
2371 /// vec.extend_from_within(2..);
2372 /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4]);
2373 ///
2374 /// vec.extend_from_within(..2);
2375 /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1]);
2376 ///
2377 /// vec.extend_from_within(4..8);
2378 /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1, 4, 2, 3, 4]);
2379 /// ```
2380 #[cfg(not(no_global_oom_handling))]
2381 #[inline(always)]
2382 pub fn extend_from_within<R>(&mut self, src: R)
2383 where
2384 R: RangeBounds<usize>,
2385 {
2386 // let range = slice::range(src, ..self.len());
2387
2388 let _ = &self.as_slice()[(src.start_bound().cloned(), src.end_bound().cloned())];
2389
2390 let len = self.len();
2391
2392 let start: ops::Bound<&usize> = src.start_bound();
2393 let start = match start {
2394 ops::Bound::Included(&start) => start,
2395 ops::Bound::Excluded(start) => start + 1,
2396 ops::Bound::Unbounded => 0,
2397 };
2398
2399 let end: ops::Bound<&usize> = src.end_bound();
2400 let end = match end {
2401 ops::Bound::Included(end) => end + 1,
2402 ops::Bound::Excluded(&end) => end,
2403 ops::Bound::Unbounded => len,
2404 };
2405
2406 let range = start..end;
2407
2408 self.reserve(range.len());
2409
2410 // SAFETY:
2411 // - len is increased only after initializing elements
2412 let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() };
2413
2414 // SAFETY:
2415 // - caller guarantees that src is a valid index
2416 let to_clone = unsafe { this.get_unchecked(range) };
2417
2418 iter::zip(to_clone, spare)
2419 .map(|(src, dst)| dst.write(src.clone()))
2420 // Note:
2421 // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len
2422 // - len is increased after each element to prevent leaks (see issue #82533)
2423 .for_each(|_| *len += 1);
2424 }
2425}
2426
2427impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
2428 /// Takes a `Vec<[T; N]>` and flattens it into a `Vec<T>`.
2429 ///
2430 /// # Panics
2431 ///
2432 /// Panics if the length of the resulting vector would overflow a `usize`.
2433 ///
2434 /// This is only possible when flattening a vector of arrays of zero-sized
2435 /// types, and thus tends to be irrelevant in practice. If
2436 /// `size_of::<T>() > 0`, this will never panic.
2437 ///
2438 /// # Examples
2439 ///
2440 /// ```
2441 /// #![feature(slice_flatten)]
2442 ///
2443 /// let mut vec = vec![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
2444 /// assert_eq!(vec.pop(), Some([7, 8, 9]));
2445 ///
2446 /// let mut flattened = vec.into_flattened();
2447 /// assert_eq!(flattened.pop(), Some(6));
2448 /// ```
2449 #[inline(always)]
2450 pub fn into_flattened(self) -> Vec<T, A> {
2451 let (ptr, len, cap, alloc) = self.into_raw_parts_with_alloc();
2452 let (new_len, new_cap) = if size_of::<T>() == 0 {
2453 (len.checked_mul(N).expect("vec len overflow"), usize::MAX)
2454 } else {
2455 // SAFETY:
2456 // - `cap * N` cannot overflow because the allocation is already in
2457 // the address space.
2458 // - Each `[T; N]` has `N` valid elements, so there are `len * N`
2459 // valid elements in the allocation.
2460 (len * N, cap * N)
2461 };
2462 // SAFETY:
2463 // - `ptr` was allocated by `self`
2464 // - `ptr` is well-aligned because `[T; N]` has the same alignment as `T`.
2465 // - `new_cap` refers to the same sized allocation as `cap` because
2466 // `new_cap * size_of::<T>()` == `cap * size_of::<[T; N]>()`
2467 // - `len` <= `cap`, so `len * N` <= `cap * N`.
2468 unsafe { Vec::<T, A>::from_raw_parts_in(ptr.cast(), new_len, new_cap, alloc) }
2469 }
2470}
2471
2472// This code generalizes `extend_with_{element,default}`.
2473trait ExtendWith<T> {
2474 fn next(&mut self) -> T;
2475 fn last(self) -> T;
2476}
2477
2478struct ExtendElement<T>(T);
2479impl<T: Clone> ExtendWith<T> for ExtendElement<T> {
2480 #[inline(always)]
2481 fn next(&mut self) -> T {
2482 self.0.clone()
2483 }
2484
2485 #[inline(always)]
2486 fn last(self) -> T {
2487 self.0
2488 }
2489}
2490
2491impl<T, A: Allocator> Vec<T, A> {
2492 #[cfg(not(no_global_oom_handling))]
2493 #[inline(always)]
2494 /// Extend the vector by `n` values, using the given generator.
2495 fn extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) {
2496 self.reserve(n);
2497
2498 unsafe {
2499 let mut ptr = self.as_mut_ptr().add(self.len());
2500 // Use SetLenOnDrop to work around bug where compiler
2501 // might not realize the store through `ptr` through self.set_len()
2502 // don't alias.
2503 let mut local_len = SetLenOnDrop::new(&mut self.len);
2504
2505 // Write all elements except the last one
2506 for _ in 1..n {
2507 ptr::write(ptr, value.next());
2508 ptr = ptr.add(1);
2509 // Increment the length in every step in case next() panics
2510 local_len.increment_len(1);
2511 }
2512
2513 if n > 0 {
2514 // We can write the last element directly without cloning needlessly
2515 ptr::write(ptr, value.last());
2516 local_len.increment_len(1);
2517 }
2518
2519 // len set by scope guard
2520 }
2521 }
2522}
2523
2524impl<T: PartialEq, A: Allocator> Vec<T, A> {
2525 /// Removes consecutive repeated elements in the vector according to the
2526 /// [`PartialEq`] trait implementation.
2527 ///
2528 /// If the vector is sorted, this removes all duplicates.
2529 ///
2530 /// # Examples
2531 ///
2532 /// ```
2533 /// let mut vec = vec![1, 2, 2, 3, 2];
2534 ///
2535 /// vec.dedup();
2536 ///
2537 /// assert_eq!(vec, [1, 2, 3, 2]);
2538 /// ```
2539 #[inline(always)]
2540 pub fn dedup(&mut self) {
2541 self.dedup_by(|a: &mut T, b: &mut T| a == b)
2542 }
2543}
2544
2545trait ExtendFromWithinSpec {
2546 /// # Safety
2547 ///
2548 /// - `src` needs to be valid index
2549 /// - `self.capacity() - self.len()` must be `>= src.len()`
2550 unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
2551}
2552
2553// impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
2554// default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
2555// // SAFETY:
2556// // - len is increased only after initializing elements
2557// let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() };
2558
2559// // SAFETY:
2560// // - caller guarantees that src is a valid index
2561// let to_clone = unsafe { this.get_unchecked(src) };
2562
2563// iter::zip(to_clone, spare)
2564// .map(|(src, dst)| dst.write(src.clone()))
2565// // Note:
2566// // - Element was just initialized with `MaybeUninit::write`, so it's ok to increase len
2567// // - len is increased after each element to prevent leaks (see issue #82533)
2568// .for_each(|_| *len += 1);
2569// }
2570// }
2571
2572impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
2573 #[inline(always)]
2574 unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
2575 let count = src.len();
2576 {
2577 let (init, spare) = self.split_at_spare_mut();
2578
2579 // SAFETY:
2580 // - caller guarantees that `src` is a valid index
2581 let source = unsafe { init.get_unchecked(src) };
2582
2583 // SAFETY:
2584 // - Both pointers are created from unique slice references (`&mut [_]`)
2585 // so they are valid and do not overlap.
2586 // - Elements are :Copy so it's OK to copy them, without doing
2587 // anything with the original values
2588 // - `count` is equal to the len of `source`, so source is valid for
2589 // `count` reads
2590 // - `.reserve(count)` guarantees that `spare.len() >= count` so spare
2591 // is valid for `count` writes
2592 unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) };
2593 }
2594
2595 // SAFETY:
2596 // - The elements were just initialized by `copy_nonoverlapping`
2597 self.len += count;
2598 }
2599}
2600
2601////////////////////////////////////////////////////////////////////////////////
2602// Common trait implementations for Vec
2603////////////////////////////////////////////////////////////////////////////////
2604
2605impl<T, A: Allocator> ops::Deref for Vec<T, A> {
2606 type Target = [T];
2607
2608 #[inline(always)]
2609 fn deref(&self) -> &[T] {
2610 unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
2611 }
2612}
2613
2614impl<T, A: Allocator> ops::DerefMut for Vec<T, A> {
2615 #[inline(always)]
2616 fn deref_mut(&mut self) -> &mut [T] {
2617 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
2618 }
2619}
2620
2621#[cfg(not(no_global_oom_handling))]
2622impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> {
2623 #[inline(always)]
2624 fn clone(&self) -> Self {
2625 let alloc: A = self.allocator().clone();
2626 let mut vec: Vec = Vec::with_capacity_in(self.len(), alloc);
2627 vec.extend_from_slice(self);
2628 vec
2629 }
2630
2631 #[inline(always)]
2632 fn clone_from(&mut self, other: &Self) {
2633 // drop anything that will not be overwritten
2634 self.truncate(other.len());
2635
2636 // self.len <= other.len due to the truncate above, so the
2637 // slices here are always in-bounds.
2638 let (init: &[T], tail: &[T]) = other.split_at(self.len());
2639
2640 // reuse the contained values' allocations/resources.
2641 self.clone_from_slice(src:init);
2642 self.extend_from_slice(tail);
2643 }
2644}
2645
2646/// The hash of a vector is the same as that of the corresponding slice,
2647/// as required by the `core::borrow::Borrow` implementation.
2648///
2649/// ```
2650/// #![feature(build_hasher_simple_hash_one)]
2651/// use std::hash::BuildHasher;
2652///
2653/// let b = std::collections::hash_map::RandomState::new();
2654/// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09];
2655/// let s: &[u8] = &[0xa8, 0x3c, 0x09];
2656/// assert_eq!(b.hash_one(v), b.hash_one(s));
2657/// ```
2658impl<T: Hash, A: Allocator> Hash for Vec<T, A> {
2659 #[inline(always)]
2660 fn hash<H: Hasher>(&self, state: &mut H) {
2661 Hash::hash(&**self, state)
2662 }
2663}
2664
2665impl<T, I: SliceIndex<[T]>, A: Allocator> Index<I> for Vec<T, A> {
2666 type Output = I::Output;
2667
2668 #[inline(always)]
2669 fn index(&self, index: I) -> &Self::Output {
2670 Index::index(&**self, index)
2671 }
2672}
2673
2674impl<T, I: SliceIndex<[T]>, A: Allocator> IndexMut<I> for Vec<T, A> {
2675 #[inline(always)]
2676 fn index_mut(&mut self, index: I) -> &mut Self::Output {
2677 IndexMut::index_mut(&mut **self, index)
2678 }
2679}
2680
2681#[cfg(not(no_global_oom_handling))]
2682impl<T> FromIterator<T> for Vec<T> {
2683 #[inline(always)]
2684 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
2685 let mut vec: Vec = Vec::new();
2686 vec.extend(iter);
2687 vec
2688 }
2689}
2690
2691impl<T, A: Allocator> IntoIterator for Vec<T, A> {
2692 type Item = T;
2693 type IntoIter = IntoIter<T, A>;
2694
2695 /// Creates a consuming iterator, that is, one that moves each value out of
2696 /// the vector (from start to end). The vector cannot be used after calling
2697 /// this.
2698 ///
2699 /// # Examples
2700 ///
2701 /// ```
2702 /// let v = vec!["a".to_string(), "b".to_string()];
2703 /// let mut v_iter = v.into_iter();
2704 ///
2705 /// let first_element: Option<String> = v_iter.next();
2706 ///
2707 /// assert_eq!(first_element, Some("a".to_string()));
2708 /// assert_eq!(v_iter.next(), Some("b".to_string()));
2709 /// assert_eq!(v_iter.next(), None);
2710 /// ```
2711 #[inline(always)]
2712 fn into_iter(self) -> Self::IntoIter {
2713 unsafe {
2714 let mut me = ManuallyDrop::new(self);
2715 let alloc = ManuallyDrop::new(ptr::read(me.allocator()));
2716 let begin = me.as_mut_ptr();
2717 let end = if size_of::<T>() == 0 {
2718 begin.cast::<u8>().wrapping_add(me.len()).cast()
2719 } else {
2720 begin.add(me.len()) as *const T
2721 };
2722 let cap = me.buf.capacity();
2723 IntoIter {
2724 buf: NonNull::new_unchecked(begin),
2725 phantom: PhantomData,
2726 cap,
2727 alloc,
2728 ptr: begin,
2729 end,
2730 }
2731 }
2732 }
2733}
2734
2735impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> {
2736 type Item = &'a T;
2737 type IntoIter = slice::Iter<'a, T>;
2738
2739 #[inline(always)]
2740 fn into_iter(self) -> Self::IntoIter {
2741 self.iter()
2742 }
2743}
2744
2745impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> {
2746 type Item = &'a mut T;
2747 type IntoIter = slice::IterMut<'a, T>;
2748
2749 fn into_iter(self) -> Self::IntoIter {
2750 self.iter_mut()
2751 }
2752}
2753
2754#[cfg(not(no_global_oom_handling))]
2755impl<T, A: Allocator> Extend<T> for Vec<T, A> {
2756 #[inline(always)]
2757 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2758 // This is the case for a general iter.
2759 //
2760 // This function should be the moral equivalent of:
2761 //
2762 // for item in iter {
2763 // self.push(item);
2764 // }
2765
2766 let mut iter = iter.into_iter();
2767 while let Some(element) = iter.next() {
2768 let len = self.len();
2769 if len == self.capacity() {
2770 let (lower, _) = iter.size_hint();
2771 self.reserve(lower.saturating_add(1));
2772 }
2773 unsafe {
2774 ptr::write(self.as_mut_ptr().add(len), element);
2775 // Since next() executes user code which can panic we have to bump the length
2776 // after each step.
2777 // NB can't overflow since we would have had to alloc the address space
2778 self.set_len(len + 1);
2779 }
2780 }
2781 }
2782}
2783
2784impl<T, A: Allocator> Vec<T, A> {
2785 /// Creates a splicing iterator that replaces the specified range in the vector
2786 /// with the given `replace_with` iterator and yields the removed items.
2787 /// `replace_with` does not need to be the same length as `range`.
2788 ///
2789 /// `range` is removed even if the iterator is not consumed until the end.
2790 ///
2791 /// It is unspecified how many elements are removed from the vector
2792 /// if the `Splice` value is leaked.
2793 ///
2794 /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
2795 ///
2796 /// This is optimal if:
2797 ///
2798 /// * The tail (elements in the vector after `range`) is empty,
2799 /// * or `replace_with` yields fewer or equal elements than `range`’s length
2800 /// * or the lower bound of its `size_hint()` is exact.
2801 ///
2802 /// Otherwise, a temporary vector is allocated and the tail is moved twice.
2803 ///
2804 /// # Panics
2805 ///
2806 /// Panics if the starting point is greater than the end point or if
2807 /// the end point is greater than the length of the vector.
2808 ///
2809 /// # Examples
2810 ///
2811 /// ```
2812 /// let mut v = vec![1, 2, 3, 4];
2813 /// let new = [7, 8, 9];
2814 /// let u: Vec<_> = v.splice(1..3, new).collect();
2815 /// assert_eq!(v, &[1, 7, 8, 9, 4]);
2816 /// assert_eq!(u, &[2, 3]);
2817 /// ```
2818 #[cfg(not(no_global_oom_handling))]
2819 #[inline(always)]
2820 pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
2821 where
2822 R: RangeBounds<usize>,
2823 I: IntoIterator<Item = T>,
2824 {
2825 Splice {
2826 drain: self.drain(range),
2827 replace_with: replace_with.into_iter(),
2828 }
2829 }
2830}
2831
2832/// Extend implementation that copies elements out of references before pushing them onto the Vec.
2833///
2834/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
2835/// append the entire slice at once.
2836///
2837/// [`copy_from_slice`]: slice::copy_from_slice
2838#[cfg(not(no_global_oom_handling))]
2839impl<'a, T: Copy + 'a, A: Allocator + 'a> Extend<&'a T> for Vec<T, A> {
2840 #[inline(always)]
2841 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2842 let mut iter: ::IntoIter = iter.into_iter();
2843 while let Some(element: &T) = iter.next() {
2844 let len: usize = self.len();
2845 if len == self.capacity() {
2846 let (lower: usize, _) = iter.size_hint();
2847 self.reserve(additional:lower.saturating_add(1));
2848 }
2849 unsafe {
2850 ptr::write(self.as_mut_ptr().add(len), *element);
2851 // Since next() executes user code which can panic we have to bump the length
2852 // after each step.
2853 // NB can't overflow since we would have had to alloc the address space
2854 self.set_len(new_len:len + 1);
2855 }
2856 }
2857 }
2858}
2859
2860/// Implements comparison of vectors, [lexicographically](core::cmp::Ord#lexicographical-comparison).
2861impl<T: PartialOrd, A: Allocator> PartialOrd for Vec<T, A> {
2862 #[inline(always)]
2863 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2864 PartialOrd::partial_cmp(&**self, &**other)
2865 }
2866}
2867
2868impl<T: Eq, A: Allocator> Eq for Vec<T, A> {}
2869
2870/// Implements ordering of vectors, [lexicographically](core::cmp::Ord#lexicographical-comparison).
2871impl<T: Ord, A: Allocator> Ord for Vec<T, A> {
2872 #[inline(always)]
2873 fn cmp(&self, other: &Self) -> Ordering {
2874 Ord::cmp(&**self, &**other)
2875 }
2876}
2877
2878impl<T, A: Allocator> Drop for Vec<T, A> {
2879 #[inline(always)]
2880 fn drop(&mut self) {
2881 unsafe {
2882 // use drop for [T]
2883 // use a raw slice to refer to the elements of the vector as weakest necessary type;
2884 // could avoid questions of validity in certain cases
2885 ptr::drop_in_place(to_drop:ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
2886 }
2887 // RawVec handles deallocation
2888 }
2889}
2890
2891impl<T> Default for Vec<T> {
2892 /// Creates an empty `Vec<T>`.
2893 ///
2894 /// The vector will not allocate until elements are pushed onto it.
2895 #[inline(always)]
2896 fn default() -> Vec<T> {
2897 Vec::new()
2898 }
2899}
2900
2901impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
2902 #[inline(always)]
2903 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2904 fmt::Debug::fmt(&**self, f)
2905 }
2906}
2907
2908impl<T, A: Allocator> AsRef<Vec<T, A>> for Vec<T, A> {
2909 #[inline(always)]
2910 fn as_ref(&self) -> &Vec<T, A> {
2911 self
2912 }
2913}
2914
2915impl<T, A: Allocator> AsMut<Vec<T, A>> for Vec<T, A> {
2916 #[inline(always)]
2917 fn as_mut(&mut self) -> &mut Vec<T, A> {
2918 self
2919 }
2920}
2921
2922impl<T, A: Allocator> AsRef<[T]> for Vec<T, A> {
2923 #[inline(always)]
2924 fn as_ref(&self) -> &[T] {
2925 self
2926 }
2927}
2928
2929impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> {
2930 #[inline(always)]
2931 fn as_mut(&mut self) -> &mut [T] {
2932 self
2933 }
2934}
2935
2936#[cfg(not(no_global_oom_handling))]
2937impl<T: Clone> From<&[T]> for Vec<T> {
2938 /// Allocate a `Vec<T>` and fill it by cloning `s`'s items.
2939 ///
2940 /// # Examples
2941 ///
2942 /// ```
2943 /// assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);
2944 /// ```
2945 #[inline(always)]
2946 fn from(s: &[T]) -> Vec<T> {
2947 let mut vec: Vec = Vec::with_capacity(s.len());
2948 vec.extend_from_slice(s);
2949 vec
2950 }
2951}
2952
2953#[cfg(not(no_global_oom_handling))]
2954impl<T: Clone> From<&mut [T]> for Vec<T> {
2955 /// Allocate a `Vec<T>` and fill it by cloning `s`'s items.
2956 ///
2957 /// # Examples
2958 ///
2959 /// ```
2960 /// assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]);
2961 /// ```
2962 #[inline(always)]
2963 fn from(s: &mut [T]) -> Vec<T> {
2964 let mut vec: Vec = Vec::with_capacity(s.len());
2965 vec.extend_from_slice(s);
2966 vec
2967 }
2968}
2969
2970#[cfg(not(no_global_oom_handling))]
2971impl<T, const N: usize> From<[T; N]> for Vec<T> {
2972 #[inline(always)]
2973 fn from(s: [T; N]) -> Vec<T> {
2974 Box::slice(Box::new(s)).into_vec()
2975 }
2976}
2977
2978impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> {
2979 /// Convert a boxed slice into a vector by transferring ownership of
2980 /// the existing heap allocation.
2981 ///
2982 /// # Examples
2983 ///
2984 /// ```
2985 /// let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice();
2986 /// assert_eq!(Vec::from(b), vec![1, 2, 3]);
2987 /// ```
2988 #[inline(always)]
2989 fn from(s: Box<[T], A>) -> Self {
2990 s.into_vec()
2991 }
2992}
2993
2994impl<T, A: Allocator, const N: usize> From<Box<[T; N], A>> for Vec<T, A> {
2995 /// Convert a boxed array into a vector by transferring ownership of
2996 /// the existing heap allocation.
2997 ///
2998 /// # Examples
2999 ///
3000 /// ```
3001 /// let b: Box<[i32; 3]> = Box::new([1, 2, 3]);
3002 /// assert_eq!(Vec::from(b), vec![1, 2, 3]);
3003 /// ```
3004 #[inline(always)]
3005 fn from(s: Box<[T; N], A>) -> Self {
3006 s.into_vec()
3007 }
3008}
3009
3010// note: test pulls in libstd, which causes errors here
3011#[cfg(not(no_global_oom_handling))]
3012impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> {
3013 /// Convert a vector into a boxed slice.
3014 ///
3015 /// If `v` has excess capacity, its items will be moved into a
3016 /// newly-allocated buffer with exactly the right capacity.
3017 ///
3018 /// # Examples
3019 ///
3020 /// ```
3021 /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice());
3022 /// ```
3023 ///
3024 /// Any excess capacity is removed:
3025 /// ```
3026 /// let mut vec = Vec::with_capacity(10);
3027 /// vec.extend([1, 2, 3]);
3028 ///
3029 /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice());
3030 /// ```
3031 #[inline(always)]
3032 fn from(v: Vec<T, A>) -> Self {
3033 v.into_boxed_slice()
3034 }
3035}
3036
3037#[cfg(not(no_global_oom_handling))]
3038impl From<&str> for Vec<u8> {
3039 /// Allocate a `Vec<u8>` and fill it with a UTF-8 string.
3040 ///
3041 /// # Examples
3042 ///
3043 /// ```
3044 /// assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);
3045 /// ```
3046 #[inline(always)]
3047 fn from(s: &str) -> Vec<u8> {
3048 From::from(s.as_bytes())
3049 }
3050}
3051
3052impl<T, A: Allocator, const N: usize> TryFrom<Vec<T, A>> for [T; N] {
3053 type Error = Vec<T, A>;
3054
3055 /// Gets the entire contents of the `Vec<T>` as an array,
3056 /// if its size exactly matches that of the requested array.
3057 ///
3058 /// # Examples
3059 ///
3060 /// ```
3061 /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3]));
3062 /// assert_eq!(<Vec<i32>>::new().try_into(), Ok([]));
3063 /// ```
3064 ///
3065 /// If the length doesn't match, the input comes back in `Err`:
3066 /// ```
3067 /// let r: Result<[i32; 4], _> = (0..10).collect::<Vec<_>>().try_into();
3068 /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
3069 /// ```
3070 ///
3071 /// If you're fine with just getting a prefix of the `Vec<T>`,
3072 /// you can call [`.truncate(N)`](Vec::truncate) first.
3073 /// ```
3074 /// let mut v = String::from("hello world").into_bytes();
3075 /// v.sort();
3076 /// v.truncate(2);
3077 /// let [a, b]: [_; 2] = v.try_into().unwrap();
3078 /// assert_eq!(a, b' ');
3079 /// assert_eq!(b, b'd');
3080 /// ```
3081 #[inline(always)]
3082 fn try_from(mut vec: Vec<T, A>) -> Result<[T; N], Vec<T, A>> {
3083 if vec.len() != N {
3084 return Err(vec);
3085 }
3086
3087 // SAFETY: `.set_len(0)` is always sound.
3088 unsafe { vec.set_len(0) };
3089
3090 // SAFETY: A `Vec`'s pointer is always aligned properly, and
3091 // the alignment the array needs is the same as the items.
3092 // We checked earlier that we have sufficient items.
3093 // The items will not double-drop as the `set_len`
3094 // tells the `Vec` not to also drop them.
3095 let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) };
3096 Ok(array)
3097 }
3098}
3099
3100#[inline(always)]
3101#[cfg(not(no_global_oom_handling))]
3102#[doc(hidden)]
3103pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<T, A> {
3104 let mut v: Vec = Vec::with_capacity_in(capacity:n, alloc);
3105 v.extend_with(n, value:ExtendElement(elem));
3106 v
3107}
3108
3109#[inline(always)]
3110#[cfg(not(no_global_oom_handling))]
3111#[doc(hidden)]
3112pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
3113 let mut v: Vec = Vec::with_capacity(n);
3114 v.extend_with(n, value:ExtendElement(elem));
3115 v
3116}
3117
3118#[cfg(feature = "serde")]
3119impl<T, A> serde::Serialize for Vec<T, A>
3120where
3121 T: serde::Serialize,
3122 A: Allocator,
3123{
3124 #[inline(always)]
3125 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
3126 where
3127 S: serde::ser::Serializer,
3128 {
3129 serializer.collect_seq(self)
3130 }
3131}
3132
3133#[cfg(feature = "serde")]
3134impl<'de, T, A> serde::de::Deserialize<'de> for Vec<T, A>
3135where
3136 T: serde::de::Deserialize<'de>,
3137 A: Allocator + Default,
3138{
3139 #[inline(always)]
3140 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
3141 where
3142 D: serde::de::Deserializer<'de>,
3143 {
3144 struct VecVisitor<T, A> {
3145 marker: PhantomData<(T, A)>,
3146 }
3147
3148 impl<'de, T, A> serde::de::Visitor<'de> for VecVisitor<T, A>
3149 where
3150 T: serde::de::Deserialize<'de>,
3151 A: Allocator + Default,
3152 {
3153 type Value = Vec<T, A>;
3154
3155 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
3156 formatter.write_str("a sequence")
3157 }
3158
3159 fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
3160 where
3161 S: serde::de::SeqAccess<'de>,
3162 {
3163 let mut values = Vec::with_capacity_in(cautious(seq.size_hint()), A::default());
3164
3165 while let Some(value) = seq.next_element()? {
3166 values.push(value);
3167 }
3168
3169 Ok(values)
3170 }
3171 }
3172
3173 let visitor = VecVisitor {
3174 marker: PhantomData,
3175 };
3176 deserializer.deserialize_seq(visitor)
3177 }
3178
3179 #[inline(always)]
3180 fn deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error>
3181 where
3182 D: serde::de::Deserializer<'de>,
3183 {
3184 struct VecInPlaceVisitor<'a, T: 'a, A: Allocator + 'a>(&'a mut Vec<T, A>);
3185
3186 impl<'a, 'de, T, A> serde::de::Visitor<'de> for VecInPlaceVisitor<'a, T, A>
3187 where
3188 T: serde::de::Deserialize<'de>,
3189 A: Allocator + Default,
3190 {
3191 type Value = ();
3192
3193 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
3194 formatter.write_str("a sequence")
3195 }
3196
3197 fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
3198 where
3199 S: serde::de::SeqAccess<'de>,
3200 {
3201 let hint = cautious(seq.size_hint());
3202 if let Some(additional) = hint.checked_sub(self.0.len()) {
3203 self.0.reserve(additional);
3204 }
3205
3206 for i in 0..self.0.len() {
3207 let next = {
3208 let next_place = InPlaceSeed(&mut self.0[i]);
3209 seq.next_element_seed(next_place)?
3210 };
3211 if next.is_none() {
3212 self.0.truncate(i);
3213 return Ok(());
3214 }
3215 }
3216
3217 while let Some(value) = seq.next_element()? {
3218 self.0.push(value);
3219 }
3220
3221 Ok(())
3222 }
3223 }
3224
3225 deserializer.deserialize_seq(VecInPlaceVisitor(place))
3226 }
3227}
3228
3229#[cfg(feature = "serde")]
3230pub fn cautious(hint: Option<usize>) -> usize {
3231 cmp::min(hint.unwrap_or(0), 4096)
3232}
3233
3234/// A DeserializeSeed helper for implementing deserialize_in_place Visitors.
3235///
3236/// Wraps a mutable reference and calls deserialize_in_place on it.
3237
3238#[cfg(feature = "serde")]
3239pub struct InPlaceSeed<'a, T: 'a>(pub &'a mut T);
3240
3241#[cfg(feature = "serde")]
3242impl<'a, 'de, T> serde::de::DeserializeSeed<'de> for InPlaceSeed<'a, T>
3243where
3244 T: serde::de::Deserialize<'de>,
3245{
3246 type Value = ();
3247 fn deserialize<D>(self, deserializer: D) -> Result<Self::Value, D::Error>
3248 where
3249 D: serde::de::Deserializer<'de>,
3250 {
3251 T::deserialize_in_place(deserializer, self.0)
3252 }
3253}
3254