// SPDX-License-Identifier: Apache-2.0 OR MIT //! A dynamically-sized view into a contiguous sequence, `[T]`.//!//! *[See also the slice primitive type](slice).*//!//! Slices are a view into a block of memory represented as a pointer and a//! length.//!//! ```//! // slicing a Vec//! let vec = vec![1, 2, 3];//! let int_slice = &vec[..];//! // coercing an array to a slice//! let str_slice: &[&str] = &["one", "two", "three"];//! ```//!//! Slices are either mutable or shared. The shared slice type is `&[T]`,//! while the mutable slice type is `&mut [T]`, where `T` represents the element//! type. For example, you can mutate the block of memory that a mutable slice//! points to://!//! ```//! let x = &mut [1, 2, 3];//! x[1] = 7;//! assert_eq!(x, &[1, 7, 3]);//! ```//!//! Here are some of the things this module contains://!//! ## Structs//!//! There are several structs that are useful for slices, such as [`Iter`], which//! represents iteration over a slice.//!//! ## Trait Implementations//!//! There are several implementations of common traits for slices. Some examples//! include://!//! * [`Clone`]//! * [`Eq`], [`Ord`] - for slices whose element type are [`Eq`] or [`Ord`].//! * [`Hash`] - for slices whose element type is [`Hash`].//!//! ## Iteration//!//! The slices implement `IntoIterator`. The iterator yields references to the//! slice elements.//!//! ```//! let numbers = &[0, 1, 2];//! for n in numbers {//! println!("{n} is a number!");//! }//! ```//!//! The mutable slice yields mutable references to the elements://!//! ```//! let mut scores = [7, 8, 9];//! for score in &mut scores[..] {//! *score += 1;//! }//! ```//!//! This iterator yields mutable references to the slice's elements, so while//! the element type of the slice is `i32`, the element type of the iterator is//! `&mut i32`.//!//! * [`.iter`] and [`.iter_mut`] are the explicit methods to return the default//! iterators.//! * Further methods that return iterators are [`.split`], [`.splitn`],//! [`.chunks`], [`.windows`] and more.//!//! [`Hash`]: core::hash::Hash//! [`.iter`]: slice::iter//! [`.iter_mut`]: slice::iter_mut//! [`.split`]: slice::split//! [`.splitn`]: slice::splitn//! [`.chunks`]: slice::chunks//! [`.windows`]: slice::windows#![stable(feature = "rust1", since = "1.0.0")]// Many of the usings in this module are only used in the test configuration.// It's cleaner to just turn off the unused_imports warning than to fix them.#![cfg_attr(test, allow(unused_imports, dead_code))] use core::borrow::{Borrow, BorrowMut};#[cfg(not(no_global_oom_handling))]use core::cmp::Ordering::{self, Less};#[cfg(not(no_global_oom_handling))]use core::mem;#[cfg(not(no_global_oom_handling))]use core::mem::size_of;#[cfg(not(no_global_oom_handling))]use core::ptr; use crate::alloc::Allocator;#[cfg(not(no_global_oom_handling))]use crate::alloc::Global;#[cfg(not(no_global_oom_handling))]use crate::borrow::ToOwned;use crate::boxed::Box;use crate::vec::Vec; #[unstable(feature = "slice_range", issue = "76393")]pub use core::slice::range;#[unstable(feature = "array_chunks", issue = "74985")]pub use core::slice::ArrayChunks;#[unstable(feature = "array_chunks", issue = "74985")]pub use core::slice::ArrayChunksMut;#[unstable(feature = "array_windows", issue = "75027")]pub use core::slice::ArrayWindows;#[stable(feature = "inherent_ascii_escape", since = "1.60.0")]pub use core::slice::EscapeAscii;#[stable(feature = "slice_get_slice", since = "1.28.0")]pub use core::slice::SliceIndex;#[stable(feature = "from_ref", since = "1.28.0")]pub use core::slice::{from_mut, from_ref};#[stable(feature = "rust1", since = "1.0.0")]pub use core::slice::{from_raw_parts, from_raw_parts_mut};#[stable(feature = "rust1", since = "1.0.0")]pub use core::slice::{Chunks, Windows};#[stable(feature = "chunks_exact", since = "1.31.0")]pub use core::slice::{ChunksExact, ChunksExactMut};#[stable(feature = "rust1", since = "1.0.0")]pub use core::slice::{ChunksMut, Split, SplitMut};#[unstable(feature = "slice_group_by", issue = "80552")]pub use core::slice::{GroupBy, GroupByMut};#[stable(feature = "rust1", since = "1.0.0")]pub use core::slice::{Iter, IterMut};#[stable(feature = "rchunks", since = "1.31.0")]pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};#[stable(feature = "slice_rsplit", since = "1.27.0")]pub use core::slice::{RSplit, RSplitMut};#[stable(feature = "rust1", since = "1.0.0")]pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut};#[stable(feature = "split_inclusive", since = "1.51.0")]pub use core::slice::{SplitInclusive, SplitInclusiveMut}; ////////////////////////////////////////////////////////////////////////////////// Basic slice extension methods//////////////////////////////////////////////////////////////////////////////// // HACK(japaric) needed for the implementation of `vec!` macro during testing// N.B., see the `hack` module in this file for more details.#[cfg(test)]pub use hack::into_vec; // HACK(japaric) needed for the implementation of `Vec::clone` during testing// N.B., see the `hack` module in this file for more details.#[cfg(test)]pub use hack::to_vec; // HACK(japaric): With cfg(test) `impl [T]` is not available, these three// functions are actually methods that are in `impl [T]` but not in// `core::slice::SliceExt` - we need to supply these functions for the// `test_permutations` testpub(crate) mod hack { use core::alloc::Allocator; use crate::boxed::Box; use crate::vec::Vec; // We shouldn't add inline attribute to this since this is used in // `vec!` macro mostly and causes perf regression. See #71204 for // discussion and perf results. pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> { unsafe { let len = b.len(); let (b, alloc) = Box::into_raw_with_allocator(b); Vec::from_raw_parts_in(b as *mut T, len, len, alloc) } } #[cfg(not(no_global_oom_handling))] #[inline] pub fn to_vec<T: ConvertVec, A: Allocator>(s: &[T], alloc: A) -> Vec<T, A> { T::to_vec(s, alloc) } #[cfg(not(no_global_oom_handling))] pub trait ConvertVec { fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> where Self: Sized; } #[cfg(not(no_global_oom_handling))] impl<T: Clone> ConvertVec for T { #[inline] default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> { struct DropGuard<'a, T, A: Allocator> { vec: &'a mut Vec<T, A>, num_init: usize, } impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> { #[inline] fn drop(&mut self) { // SAFETY: // items were marked initialized in the loop below unsafe { self.vec.set_len(self.num_init); } } } let mut vec = Vec::with_capacity_in(s.len(), alloc); let mut guard = DropGuard { vec: &mut vec, num_init: 0 }; let slots = guard.vec.spare_capacity_mut(); // .take(slots.len()) is necessary for LLVM to remove bounds checks // and has better codegen than zip. for (i, b) in s.iter().enumerate().take(slots.len()) { guard.num_init = i; slots[i].write(b.clone()); } core::mem::forget(guard); // SAFETY: // the vec was allocated and initialized above to at least this length. unsafe { vec.set_len(s.len()); } vec } } #[cfg(not(no_global_oom_handling))] impl<T: Copy> ConvertVec for T { #[inline] fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> { let mut v = Vec::with_capacity_in(s.len(), alloc); // SAFETY: // allocated above with the capacity of `s`, and initialize to `s.len()` in // ptr::copy_to_non_overlapping below. unsafe { s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len()); v.set_len(s.len()); } v } }} #[cfg(not(test))]impl<T> [T] { /// Sorts the slice. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. /// See [`sort_unstable`](slice::sort_unstable). /// /// # Current implementation /// /// The current algorithm is an adaptive, iterative merge sort inspired by /// [timsort](https://en.wikipedia.org/wiki/Timsort). /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of /// two or more sorted sequences concatenated one after another. /// /// Also, it allocates temporary storage half the size of `self`, but for short slices a /// non-allocating insertion sort is used instead. /// /// # Examples /// /// ``` /// let mut v = [-5, 4, 1, -3, 2]; /// /// v.sort(); /// assert!(v == [-5, -3, 1, 2, 4]); /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn sort(&mut self) where T: Ord, { merge_sort(self, |a, b| a.lt(b)); } /// Sorts the slice with a comparator function. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. /// /// The comparator function must define a total ordering for the elements in the slice. If /// the ordering is not total, the order of the elements is unspecified. An order is a /// total order if it is (for all `a`, `b` and `c`): /// /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. /// /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`. /// /// ``` /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0]; /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap()); /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]); /// ``` /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. /// See [`sort_unstable_by`](slice::sort_unstable_by). /// /// # Current implementation /// /// The current algorithm is an adaptive, iterative merge sort inspired by /// [timsort](https://en.wikipedia.org/wiki/Timsort). /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of /// two or more sorted sequences concatenated one after another. /// /// Also, it allocates temporary storage half the size of `self`, but for short slices a /// non-allocating insertion sort is used instead. /// /// # Examples /// /// ``` /// let mut v = [5, 4, 1, 3, 2]; /// v.sort_by(|a, b| a.cmp(b)); /// assert!(v == [1, 2, 3, 4, 5]); /// /// // reverse sorting /// v.sort_by(|a, b| b.cmp(a)); /// assert!(v == [5, 4, 3, 2, 1]); /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn sort_by<F>(&mut self, mut compare: F) where F: FnMut(&T, &T) -> Ordering, { merge_sort(self, |a, b| compare(a, b) == Less); } /// Sorts the slice with a key extraction function. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*)) /// worst-case, where the key function is *O*(*m*). /// /// For expensive key functions (e.g. functions that are not simple property accesses or /// basic operations), [`sort_by_cached_key`](slice::sort_by_cached_key) is likely to be /// significantly faster, as it does not recompute element keys. /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. /// See [`sort_unstable_by_key`](slice::sort_unstable_by_key). /// /// # Current implementation /// /// The current algorithm is an adaptive, iterative merge sort inspired by /// [timsort](https://en.wikipedia.org/wiki/Timsort). /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of /// two or more sorted sequences concatenated one after another. /// /// Also, it allocates temporary storage half the size of `self`, but for short slices a /// non-allocating insertion sort is used instead. /// /// # Examples /// /// ``` /// let mut v = [-5i32, 4, 1, -3, 2]; /// /// v.sort_by_key(|k| k.abs()); /// assert!(v == [1, 2, -3, 4, -5]); /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_key", since = "1.7.0")] #[inline] pub fn sort_by_key<K, F>(&mut self, mut f: F) where F: FnMut(&T) -> K, K: Ord, { merge_sort(self, |a, b| f(a).lt(&f(b))); } /// Sorts the slice with a key extraction function. /// /// During sorting, the key function is called at most once per element, by using /// temporary storage to remember the results of key evaluation. /// The order of calls to the key function is unspecified and may change in future versions /// of the standard library. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \* log(*n*)) /// worst-case, where the key function is *O*(*m*). /// /// For simple key functions (e.g., functions that are property accesses or /// basic operations), [`sort_by_key`](slice::sort_by_key) is likely to be /// faster. /// /// # Current implementation /// /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, /// which combines the fast average case of randomized quicksort with the fast worst case of /// heapsort, while achieving linear time on slices with certain patterns. It uses some /// randomization to avoid degenerate cases, but with a fixed seed to always provide /// deterministic behavior. /// /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the /// length of the slice. /// /// # Examples /// /// ``` /// let mut v = [-5i32, 4, 32, -3, 2]; /// /// v.sort_by_cached_key(|k| k.to_string()); /// assert!(v == [-3, -5, 2, 32, 4]); /// ``` /// /// [pdqsort]: https://github.com/orlp/pdqsort #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")] #[inline] pub fn sort_by_cached_key<K, F>(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord, { // Helper macro for indexing our vector by the smallest possible type, to reduce allocation. macro_rules! sort_by_key { ($t:ty, $slice:ident, $f:ident) => {{ let mut indices: Vec<_> = $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect(); // The elements of `indices` are unique, as they are indexed, so any sort will be // stable with respect to the original slice. We use `sort_unstable` here because // it requires less memory allocation. indices.sort_unstable(); for i in 0..$slice.len() { let mut index = indices[i].1; while (index as usize) < i { index = indices[index as usize].1; } indices[i].1 = index; $slice.swap(i, index as usize); } }}; } let sz_u8 = mem::size_of::<(K, u8)>(); let sz_u16 = mem::size_of::<(K, u16)>(); let sz_u32 = mem::size_of::<(K, u32)>(); let sz_usize = mem::size_of::<(K, usize)>(); let len = self.len(); if len < 2 { return; } if sz_u8 < sz_u16 && len <= (u8::MAX as usize) { return sort_by_key!(u8, self, f); } if sz_u16 < sz_u32 && len <= (u16::MAX as usize) { return sort_by_key!(u16, self, f); } if sz_u32 < sz_usize && len <= (u32::MAX as usize) { return sort_by_key!(u32, self, f); } sort_by_key!(usize, self, f) } /// Copies `self` into a new `Vec`. /// /// # Examples /// /// ``` /// let s = [10, 40, 30]; /// let x = s.to_vec(); /// // Here, `s` and `x` can be modified independently. /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[rustc_conversion_suggestion] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn to_vec(&self) -> Vec<T> where T: Clone, { self.to_vec_in(Global) } /// Copies `self` into a new `Vec` with an allocator. /// /// # Examples /// /// ``` /// #![feature(allocator_api)] /// /// use std::alloc::System; /// /// let s = [10, 40, 30]; /// let x = s.to_vec_in(System); /// // Here, `s` and `x` can be modified independently. /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl]Lines 1–500 of 1204. Load more
// SPDX-License-Identifier: Apache-2.0 OR MIT //! A dynamically-sized view into a contiguous sequence, `[T]`. //! //! *[See also the slice primitive type](slice).* //! //! Slices are a view into a block of memory represented as a pointer and a //! length. //! //! ``` //! // slicing a Vec //! let vec = vec![1, 2, 3]; //! let int_slice = &vec[..]; //! // coercing an array to a slice //! let str_slice: &[&str] = &["one", "two", "three"]; //! ``` //! //! Slices are either mutable or shared. The shared slice type is `&[T]`, //! while the mutable slice type is `&mut [T]`, where `T` represents the element //! type. For example, you can mutate the block of memory that a mutable slice //! points to: //! //! ``` //! let x = &mut [1, 2, 3]; //! x[1] = 7; //! assert_eq!(x, &[1, 7, 3]); //! ``` //! //! Here are some of the things this module contains: //! //! ## Structs //! //! There are several structs that are useful for slices, such as [`Iter`], which //! represents iteration over a slice. //! //! ## Trait Implementations //! //! There are several implementations of common traits for slices. Some examples //! include: //! //! * [`Clone`] //! * [`Eq`], [`Ord`] - for slices whose element type are [`Eq`] or [`Ord`]. //! * [`Hash`] - for slices whose element type is [`Hash`]. //! //! ## Iteration //! //! The slices implement `IntoIterator`. The iterator yields references to the //! slice elements. //! //! ``` //! let numbers = &[0, 1, 2]; //! for n in numbers { //! println!("{n} is a number!"); //! } //! ``` //! //! The mutable slice yields mutable references to the elements: //! //! ``` //! let mut scores = [7, 8, 9]; //! for score in &mut scores[..] { //! *score += 1; //! } //! ``` //! //! This iterator yields mutable references to the slice's elements, so while //! the element type of the slice is `i32`, the element type of the iterator is //! `&mut i32`. //! //! * [`.iter`] and [`.iter_mut`] are the explicit methods to return the default //! iterators. //! * Further methods that return iterators are [`.split`], [`.splitn`], //! [`.chunks`], [`.windows`] and more. //! //! [`Hash`]: core::hash::Hash //! [`.iter`]: slice::iter //! [`.iter_mut`]: slice::iter_mut //! [`.split`]: slice::split //! [`.splitn`]: slice::splitn //! [`.chunks`]: slice::chunks //! [`.windows`]: slice::windows #![stable(feature = "rust1", since = "1.0.0")] // Many of the usings in this module are only used in the test configuration. // It's cleaner to just turn off the unused_imports warning than to fix them. #![cfg_attr(test, allow(unused_imports, dead_code))] use core::borrow::{Borrow, BorrowMut}; #[cfg(not(no_global_oom_handling))] use core::cmp::Ordering::{self, Less}; #[cfg(not(no_global_oom_handling))] use core::mem; #[cfg(not(no_global_oom_handling))] use core::mem::size_of; #[cfg(not(no_global_oom_handling))] use core::ptr; use crate::alloc::Allocator; #[cfg(not(no_global_oom_handling))] use crate::alloc::Global; #[cfg(not(no_global_oom_handling))] use crate::borrow::ToOwned; use crate::boxed::Box; use crate::vec::Vec; #[unstable(feature = "slice_range", issue = "76393")] pub use core::slice::range; #[unstable(feature = "array_chunks", issue = "74985")] pub use core::slice::ArrayChunks; #[unstable(feature = "array_chunks", issue = "74985")] pub use core::slice::ArrayChunksMut; #[unstable(feature = "array_windows", issue = "75027")] pub use core::slice::ArrayWindows; #[stable(feature = "inherent_ascii_escape", since = "1.60.0")] pub use core::slice::EscapeAscii; #[stable(feature = "slice_get_slice", since = "1.28.0")] pub use core::slice::SliceIndex; #[stable(feature = "from_ref", since = "1.28.0")] pub use core::slice::{from_mut, from_ref}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::slice::{from_raw_parts, from_raw_parts_mut}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::slice::{Chunks, Windows}; #[stable(feature = "chunks_exact", since = "1.31.0")] pub use core::slice::{ChunksExact, ChunksExactMut}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::slice::{ChunksMut, Split, SplitMut}; #[unstable(feature = "slice_group_by", issue = "80552")] pub use core::slice::{GroupBy, GroupByMut}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::slice::{Iter, IterMut}; #[stable(feature = "rchunks", since = "1.31.0")] pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut}; #[stable(feature = "slice_rsplit", since = "1.27.0")] pub use core::slice::{RSplit, RSplitMut}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut}; #[stable(feature = "split_inclusive", since = "1.51.0")] pub use core::slice::{SplitInclusive, SplitInclusiveMut}; //////////////////////////////////////////////////////////////////////////////// // Basic slice extension methods //////////////////////////////////////////////////////////////////////////////// // HACK(japaric) needed for the implementation of `vec!` macro during testing // N.B., see the `hack` module in this file for more details. #[cfg(test)] pub use hack::into_vec; // HACK(japaric) needed for the implementation of `Vec::clone` during testing // N.B., see the `hack` module in this file for more details. #[cfg(test)] pub use hack::to_vec; // HACK(japaric): With cfg(test) `impl [T]` is not available, these three // functions are actually methods that are in `impl [T]` but not in // `core::slice::SliceExt` - we need to supply these functions for the // `test_permutations` test pub(crate) mod hack { use core::alloc::Allocator; use crate::boxed::Box; use crate::vec::Vec; // We shouldn't add inline attribute to this since this is used in // `vec!` macro mostly and causes perf regression. See #71204 for // discussion and perf results. pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> { unsafe { let len = b.len(); let (b, alloc) = Box::into_raw_with_allocator(b); Vec::from_raw_parts_in(b as *mut T, len, len, alloc) } } #[cfg(not(no_global_oom_handling))] #[inline] pub fn to_vec<T: ConvertVec, A: Allocator>(s: &[T], alloc: A) -> Vec<T, A> { T::to_vec(s, alloc) } #[cfg(not(no_global_oom_handling))] pub trait ConvertVec { fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> where Self: Sized; } #[cfg(not(no_global_oom_handling))] impl<T: Clone> ConvertVec for T { #[inline] default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> { struct DropGuard<'a, T, A: Allocator> { vec: &'a mut Vec<T, A>, num_init: usize, } impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> { #[inline] fn drop(&mut self) { // SAFETY: // items were marked initialized in the loop below unsafe { self.vec.set_len(self.num_init); } } } let mut vec = Vec::with_capacity_in(s.len(), alloc); let mut guard = DropGuard { vec: &mut vec, num_init: 0 }; let slots = guard.vec.spare_capacity_mut(); // .take(slots.len()) is necessary for LLVM to remove bounds checks // and has better codegen than zip. for (i, b) in s.iter().enumerate().take(slots.len()) { guard.num_init = i; slots[i].write(b.clone()); } core::mem::forget(guard); // SAFETY: // the vec was allocated and initialized above to at least this length. unsafe { vec.set_len(s.len()); } vec } } #[cfg(not(no_global_oom_handling))] impl<T: Copy> ConvertVec for T { #[inline] fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> { let mut v = Vec::with_capacity_in(s.len(), alloc); // SAFETY: // allocated above with the capacity of `s`, and initialize to `s.len()` in // ptr::copy_to_non_overlapping below. unsafe { s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len()); v.set_len(s.len()); } v } } } #[cfg(not(test))] impl<T> [T] { /// Sorts the slice. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. /// See [`sort_unstable`](slice::sort_unstable). /// /// # Current implementation /// /// The current algorithm is an adaptive, iterative merge sort inspired by /// [timsort](https://en.wikipedia.org/wiki/Timsort). /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of /// two or more sorted sequences concatenated one after another. /// /// Also, it allocates temporary storage half the size of `self`, but for short slices a /// non-allocating insertion sort is used instead. /// /// # Examples /// /// ``` /// let mut v = [-5, 4, 1, -3, 2]; /// /// v.sort(); /// assert!(v == [-5, -3, 1, 2, 4]); /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn sort(&mut self) where T: Ord, { merge_sort(self, |a, b| a.lt(b)); } /// Sorts the slice with a comparator function. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. /// /// The comparator function must define a total ordering for the elements in the slice. If /// the ordering is not total, the order of the elements is unspecified. An order is a /// total order if it is (for all `a`, `b` and `c`): /// /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. /// /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`. /// /// ``` /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0]; /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap()); /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]); /// ``` /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. /// See [`sort_unstable_by`](slice::sort_unstable_by). /// /// # Current implementation /// /// The current algorithm is an adaptive, iterative merge sort inspired by /// [timsort](https://en.wikipedia.org/wiki/Timsort). /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of /// two or more sorted sequences concatenated one after another. /// /// Also, it allocates temporary storage half the size of `self`, but for short slices a /// non-allocating insertion sort is used instead. /// /// # Examples /// /// ``` /// let mut v = [5, 4, 1, 3, 2]; /// v.sort_by(|a, b| a.cmp(b)); /// assert!(v == [1, 2, 3, 4, 5]); /// /// // reverse sorting /// v.sort_by(|a, b| b.cmp(a)); /// assert!(v == [5, 4, 3, 2, 1]); /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn sort_by<F>(&mut self, mut compare: F) where F: FnMut(&T, &T) -> Ordering, { merge_sort(self, |a, b| compare(a, b) == Less); } /// Sorts the slice with a key extraction function. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*)) /// worst-case, where the key function is *O*(*m*). /// /// For expensive key functions (e.g. functions that are not simple property accesses or /// basic operations), [`sort_by_cached_key`](slice::sort_by_cached_key) is likely to be /// significantly faster, as it does not recompute element keys. /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. /// See [`sort_unstable_by_key`](slice::sort_unstable_by_key). /// /// # Current implementation /// /// The current algorithm is an adaptive, iterative merge sort inspired by /// [timsort](https://en.wikipedia.org/wiki/Timsort). /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of /// two or more sorted sequences concatenated one after another. /// /// Also, it allocates temporary storage half the size of `self`, but for short slices a /// non-allocating insertion sort is used instead. /// /// # Examples /// /// ``` /// let mut v = [-5i32, 4, 1, -3, 2]; /// /// v.sort_by_key(|k| k.abs()); /// assert!(v == [1, 2, -3, 4, -5]); /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_key", since = "1.7.0")] #[inline] pub fn sort_by_key<K, F>(&mut self, mut f: F) where F: FnMut(&T) -> K, K: Ord, { merge_sort(self, |a, b| f(a).lt(&f(b))); } /// Sorts the slice with a key extraction function. /// /// During sorting, the key function is called at most once per element, by using /// temporary storage to remember the results of key evaluation. /// The order of calls to the key function is unspecified and may change in future versions /// of the standard library. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \* log(*n*)) /// worst-case, where the key function is *O*(*m*). /// /// For simple key functions (e.g., functions that are property accesses or /// basic operations), [`sort_by_key`](slice::sort_by_key) is likely to be /// faster. /// /// # Current implementation /// /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, /// which combines the fast average case of randomized quicksort with the fast worst case of /// heapsort, while achieving linear time on slices with certain patterns. It uses some /// randomization to avoid degenerate cases, but with a fixed seed to always provide /// deterministic behavior. /// /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the /// length of the slice. /// /// # Examples /// /// ``` /// let mut v = [-5i32, 4, 32, -3, 2]; /// /// v.sort_by_cached_key(|k| k.to_string()); /// assert!(v == [-3, -5, 2, 32, 4]); /// ``` /// /// [pdqsort]: https://github.com/orlp/pdqsort #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")] #[inline] pub fn sort_by_cached_key<K, F>(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord, { // Helper macro for indexing our vector by the smallest possible type, to reduce allocation. macro_rules! sort_by_key { ($t:ty, $slice:ident, $f:ident) => {{ let mut indices: Vec<_> = $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect(); // The elements of `indices` are unique, as they are indexed, so any sort will be // stable with respect to the original slice. We use `sort_unstable` here because // it requires less memory allocation. indices.sort_unstable(); for i in 0..$slice.len() { let mut index = indices[i].1; while (index as usize) < i { index = indices[index as usize].1; } indices[i].1 = index; $slice.swap(i, index as usize); } }}; } let sz_u8 = mem::size_of::<(K, u8)>(); let sz_u16 = mem::size_of::<(K, u16)>(); let sz_u32 = mem::size_of::<(K, u32)>(); let sz_usize = mem::size_of::<(K, usize)>(); let len = self.len(); if len < 2 { return; } if sz_u8 < sz_u16 && len <= (u8::MAX as usize) { return sort_by_key!(u8, self, f); } if sz_u16 < sz_u32 && len <= (u16::MAX as usize) { return sort_by_key!(u16, self, f); } if sz_u32 < sz_usize && len <= (u32::MAX as usize) { return sort_by_key!(u32, self, f); } sort_by_key!(usize, self, f) } /// Copies `self` into a new `Vec`. /// /// # Examples /// /// ``` /// let s = [10, 40, 30]; /// let x = s.to_vec(); /// // Here, `s` and `x` can be modified independently. /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[rustc_conversion_suggestion] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn to_vec(&self) -> Vec<T> where T: Clone, { self.to_vec_in(Global) } /// Copies `self` into a new `Vec` with an allocator. /// /// # Examples /// /// ``` /// #![feature(allocator_api)] /// /// use std::alloc::System; /// /// let s = [10, 40, 30]; /// let x = s.to_vec_in(System); /// // Here, `s` and `x` can be modified independently. /// ``` #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl]