// SPDX-License-Identifier: Apache-2.0 OR MIT //! Utilities for the slice primitive type.//!//! *[See also the slice primitive type](slice).*//!//! Most of the structs in this module are iterator types which can only be created//! using a certain function. For example, `slice.iter()` yields an [`Iter`].//!//! A few functions are provided to create a slice from a value reference//! or from a raw pointer.#![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::{self, SizedTypeProperties};#[cfg(not(no_global_oom_handling))]use core::ptr;#[cfg(not(no_global_oom_handling))]use core::slice::sort; use crate::alloc::Allocator;#[cfg(not(no_global_oom_handling))]use crate::alloc::{self, Global};#[cfg(not(no_global_oom_handling))]use crate::borrow::ToOwned;use crate::boxed::Box;use crate::vec::Vec; #[cfg(test)]mod tests; #[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};#[unstable(feature = "slice_from_ptr_range", issue = "89792")]pub use core::slice::{from_mut_ptr_range, from_ptr_range};#[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, { stable_sort(self, T::lt); } /// 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, { stable_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, { stable_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] #[inline] #[unstable(feature = "allocator_api", issue = "32838")] pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A> where T: Clone, { // N.B., see the `hack` module in this file for more details. hack::to_vec(self, alloc) } /// Converts `self` into a vector without clones or allocation. /// /// The resulting vector can be converted back into a box via /// `Vec<T>`'s `into_boxed_slice` method. /// /// # Examples /// /// ``` /// let s: Box<[i32]> = Box::new([10, 40, 30]); /// let x = s.into_vec(); /// // `s` cannot be used anymore because it has been converted into `x`. /// /// assert_eq!(x, vec![10, 40, 30]); /// ``` #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> { // N.B., see the `hack` module in this file for more details. hack::into_vec(self) } /// Creates a vector by copying a slice `n` times. /// /// # Panics /// /// This function will panic if the capacity would overflow. /// /// # Examples /// /// Basic usage: /// /// ``` /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]); /// ``` /// /// A panic upon overflow: /// /// ```should_panic /// // this will panic at runtime /// b"0123456789abcdef".repeat(usize::MAX); /// ``` #[rustc_allow_incoherent_impl] #[cfg(not(no_global_oom_handling))] #[stable(feature = "repeat_generic_slice", since = "1.40.0")] pub fn repeat(&self, n: usize) -> Vec<T> where T: Copy, { if n == 0 { return Vec::new(); } // If `n` is larger than zero, it can be split as // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.Lines 1–500 of 867. Load more
// SPDX-License-Identifier: Apache-2.0 OR MIT //! Utilities for the slice primitive type. //! //! *[See also the slice primitive type](slice).* //! //! Most of the structs in this module are iterator types which can only be created //! using a certain function. For example, `slice.iter()` yields an [`Iter`]. //! //! A few functions are provided to create a slice from a value reference //! or from a raw pointer. #![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::{self, SizedTypeProperties}; #[cfg(not(no_global_oom_handling))] use core::ptr; #[cfg(not(no_global_oom_handling))] use core::slice::sort; use crate::alloc::Allocator; #[cfg(not(no_global_oom_handling))] use crate::alloc::{self, Global}; #[cfg(not(no_global_oom_handling))] use crate::borrow::ToOwned; use crate::boxed::Box; use crate::vec::Vec; #[cfg(test)] mod tests; #[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}; #[unstable(feature = "slice_from_ptr_range", issue = "89792")] pub use core::slice::{from_mut_ptr_range, from_ptr_range}; #[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, { stable_sort(self, T::lt); } /// 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, { stable_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, { stable_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] #[inline] #[unstable(feature = "allocator_api", issue = "32838")] pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A> where T: Clone, { // N.B., see the `hack` module in this file for more details. hack::to_vec(self, alloc) } /// Converts `self` into a vector without clones or allocation. /// /// The resulting vector can be converted back into a box via /// `Vec<T>`'s `into_boxed_slice` method. /// /// # Examples /// /// ``` /// let s: Box<[i32]> = Box::new([10, 40, 30]); /// let x = s.into_vec(); /// // `s` cannot be used anymore because it has been converted into `x`. /// /// assert_eq!(x, vec![10, 40, 30]); /// ``` #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> { // N.B., see the `hack` module in this file for more details. hack::into_vec(self) } /// Creates a vector by copying a slice `n` times. /// /// # Panics /// /// This function will panic if the capacity would overflow. /// /// # Examples /// /// Basic usage: /// /// ``` /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]); /// ``` /// /// A panic upon overflow: /// /// ```should_panic /// // this will panic at runtime /// b"0123456789abcdef".repeat(usize::MAX); /// ``` #[rustc_allow_incoherent_impl] #[cfg(not(no_global_oom_handling))] #[stable(feature = "repeat_generic_slice", since = "1.40.0")] pub fn repeat(&self, n: usize) -> Vec<T> where T: Copy, { if n == 0 { return Vec::new(); } // If `n` is larger than zero, it can be split as // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.