alloc/slice.rs
1//! Utilities for the slice primitive type.
2//!
3//! *[See also the slice primitive type](slice).*
4//!
5//! Most of the structs in this module are iterator types which can only be created
6//! using a certain function. For example, `slice.iter()` yields an [`Iter`].
7//!
8//! A few functions are provided to create a slice from a value reference
9//! or from a raw pointer.
10#![stable(feature = "rust1", since = "1.0.0")]
11
12use core::borrow::{Borrow, BorrowMut};
13#[cfg(not(no_global_oom_handling))]
14use core::clone::TrivialClone;
15#[cfg(not(no_global_oom_handling))]
16use core::cmp::Ordering::{self, Less};
17#[cfg(not(no_global_oom_handling))]
18use core::mem::MaybeUninit;
19#[cfg(not(no_global_oom_handling))]
20use core::ptr;
21#[stable(feature = "array_windows", since = "1.94.0")]
22pub use core::slice::ArrayWindows;
23#[stable(feature = "inherent_ascii_escape", since = "1.60.0")]
24pub use core::slice::EscapeAscii;
25#[stable(feature = "get_many_mut", since = "1.86.0")]
26pub use core::slice::GetDisjointMutError;
27#[stable(feature = "slice_get_slice", since = "1.28.0")]
28pub use core::slice::SliceIndex;
29#[cfg(not(no_global_oom_handling))]
30use core::slice::sort;
31#[stable(feature = "slice_group_by", since = "1.77.0")]
32pub use core::slice::{ChunkBy, ChunkByMut};
33#[stable(feature = "rust1", since = "1.0.0")]
34pub use core::slice::{Chunks, Windows};
35#[stable(feature = "chunks_exact", since = "1.31.0")]
36pub use core::slice::{ChunksExact, ChunksExactMut};
37#[stable(feature = "rust1", since = "1.0.0")]
38pub use core::slice::{ChunksMut, Split, SplitMut};
39#[stable(feature = "rust1", since = "1.0.0")]
40pub use core::slice::{Iter, IterMut};
41#[stable(feature = "rchunks", since = "1.31.0")]
42pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
43#[stable(feature = "slice_rsplit", since = "1.27.0")]
44pub use core::slice::{RSplit, RSplitMut};
45#[stable(feature = "rust1", since = "1.0.0")]
46pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut};
47#[stable(feature = "split_inclusive", since = "1.51.0")]
48pub use core::slice::{SplitInclusive, SplitInclusiveMut};
49#[stable(feature = "from_ref", since = "1.28.0")]
50pub use core::slice::{from_mut, from_ref};
51#[unstable(feature = "slice_from_ptr_range", issue = "89792")]
52pub use core::slice::{from_mut_ptr_range, from_ptr_range};
53#[stable(feature = "rust1", since = "1.0.0")]
54pub use core::slice::{from_raw_parts, from_raw_parts_mut};
55#[unstable(feature = "slice_range", issue = "76393")]
56pub use core::slice::{range, try_range};
57
58////////////////////////////////////////////////////////////////////////////////
59// Basic slice extension methods
60////////////////////////////////////////////////////////////////////////////////
61use crate::alloc::Allocator;
62#[cfg(not(no_global_oom_handling))]
63use crate::alloc::Global;
64#[cfg(not(no_global_oom_handling))]
65use crate::borrow::ToOwned;
66use crate::boxed::Box;
67use crate::vec::Vec;
68
69impl<T> [T] {
70 /// Sorts the slice in ascending order, preserving initial order of equal elements.
71 ///
72 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*))
73 /// worst-case.
74 ///
75 /// If the implementation of [`Ord`] for `T` does not implement a [total order], the function
76 /// may panic; even if the function exits normally, the resulting order of elements in the slice
77 /// is unspecified. See also the note on panicking below.
78 ///
79 /// When applicable, unstable sorting is preferred because it is generally faster than stable
80 /// sorting and it doesn't allocate auxiliary memory. See
81 /// [`sort_unstable`](slice::sort_unstable). The exception are partially sorted slices, which
82 /// may be better served with `slice::sort`.
83 ///
84 /// Sorting types that only implement [`PartialOrd`] such as [`f32`] and [`f64`] require
85 /// additional precautions. For example, `f32::NAN != f32::NAN`, which doesn't fulfill the
86 /// reflexivity requirement of [`Ord`]. By using an alternative comparison function with
87 /// `slice::sort_by` such as [`f32::total_cmp`] or [`f64::total_cmp`] that defines a [total
88 /// order] users can sort slices containing floating-point values. Alternatively, if all values
89 /// in the slice are guaranteed to be in a subset for which [`PartialOrd::partial_cmp`] forms a
90 /// [total order], it's possible to sort the slice with `sort_by(|a, b|
91 /// a.partial_cmp(b).unwrap())`.
92 ///
93 /// # Current implementation
94 ///
95 /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which
96 /// combines the fast average case of quicksort with the fast worst case and partial run
97 /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs
98 /// with k distinct elements, the expected time to sort the data is *O*(*n* \* log(*k*)).
99 ///
100 /// The auxiliary memory allocation behavior depends on the input length. Short slices are
101 /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it
102 /// clamps at `self.len() / 2`.
103 ///
104 /// # Panics
105 ///
106 /// May panic if the implementation of [`Ord`] for `T` does not implement a [total order], or if
107 /// the [`Ord`] implementation itself panics.
108 ///
109 /// All safe functions on slices preserve the invariant that even if the function panics, all
110 /// original elements will remain in the slice and any possible modifications via interior
111 /// mutability are observed in the input. This ensures that recovery code (for instance inside
112 /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
113 /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
114 /// to dispose of all contained elements.
115 ///
116 /// # Examples
117 ///
118 /// ```
119 /// let mut v = [4, -5, 1, -3, 2];
120 ///
121 /// v.sort();
122 /// assert_eq!(v, [-5, -3, 1, 2, 4]);
123 /// ```
124 ///
125 /// [driftsort]: https://github.com/Voultapher/driftsort
126 /// [total order]: https://en.wikipedia.org/wiki/Total_order
127 #[cfg(not(no_global_oom_handling))]
128 #[rustc_allow_incoherent_impl]
129 #[stable(feature = "rust1", since = "1.0.0")]
130 #[inline]
131 pub fn sort(&mut self)
132 where
133 T: Ord,
134 {
135 stable_sort(self, T::lt);
136 }
137
138 /// Sorts the slice in ascending order with a comparison function, preserving initial order of
139 /// equal elements.
140 ///
141 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*))
142 /// worst-case.
143 ///
144 /// If the comparison function `compare` does not implement a [total order], the function may
145 /// panic; even if the function exits normally, the resulting order of elements in the slice is
146 /// unspecified. See also the note on panicking below.
147 ///
148 /// For example `|a, b| (a - b).cmp(a)` is a comparison function that is neither transitive nor
149 /// reflexive nor total, `a < b < c < a` with `a = 1, b = 2, c = 3`. For more information and
150 /// examples see the [`Ord`] documentation.
151 ///
152 /// # Current implementation
153 ///
154 /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which
155 /// combines the fast average case of quicksort with the fast worst case and partial run
156 /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs
157 /// with k distinct elements, the expected time to sort the data is *O*(*n* \* log(*k*)).
158 ///
159 /// The auxiliary memory allocation behavior depends on the input length. Short slices are
160 /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it
161 /// clamps at `self.len() / 2`.
162 ///
163 /// # Panics
164 ///
165 /// May panic if `compare` does not implement a [total order], or if `compare` itself panics.
166 ///
167 /// All safe functions on slices preserve the invariant that even if the function panics, all
168 /// original elements will remain in the slice and any possible modifications via interior
169 /// mutability are observed in the input. This ensures that recovery code (for instance inside
170 /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
171 /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
172 /// to dispose of all contained elements.
173 ///
174 /// # Examples
175 ///
176 /// ```
177 /// let mut v = [4, -5, 1, -3, 2];
178 /// v.sort_by(|a, b| a.cmp(b));
179 /// assert_eq!(v, [-5, -3, 1, 2, 4]);
180 ///
181 /// // reverse sorting
182 /// v.sort_by(|a, b| b.cmp(a));
183 /// assert_eq!(v, [4, 2, 1, -3, -5]);
184 /// ```
185 ///
186 /// [driftsort]: https://github.com/Voultapher/driftsort
187 /// [total order]: https://en.wikipedia.org/wiki/Total_order
188 #[cfg(not(no_global_oom_handling))]
189 #[rustc_allow_incoherent_impl]
190 #[stable(feature = "rust1", since = "1.0.0")]
191 #[inline]
192 pub fn sort_by<F>(&mut self, mut compare: F)
193 where
194 F: FnMut(&T, &T) -> Ordering,
195 {
196 stable_sort(self, |a, b| compare(a, b) == Less);
197 }
198
199 /// Sorts the slice in ascending order with a key extraction function, preserving initial order
200 /// of equal elements.
201 ///
202 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*))
203 /// worst-case, where the key function is *O*(*m*).
204 ///
205 /// If the implementation of [`Ord`] for `K` does not implement a [total order], the function
206 /// may panic; even if the function exits normally, the resulting order of elements in the slice
207 /// is unspecified. See also the note on panicking below.
208 ///
209 /// # Current implementation
210 ///
211 /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which
212 /// combines the fast average case of quicksort with the fast worst case and partial run
213 /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs
214 /// with k distinct elements, the expected time to sort the data is *O*(*n* \* log(*k*)).
215 ///
216 /// The auxiliary memory allocation behavior depends on the input length. Short slices are
217 /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it
218 /// clamps at `self.len() / 2`.
219 ///
220 /// # Panics
221 ///
222 /// May panic if the implementation of [`Ord`] for `K` does not implement a [total order], or if
223 /// the [`Ord`] implementation or the key-function `f` panics.
224 ///
225 /// All safe functions on slices preserve the invariant that even if the function panics, all
226 /// original elements will remain in the slice and any possible modifications via interior
227 /// mutability are observed in the input. This ensures that recovery code (for instance inside
228 /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
229 /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
230 /// to dispose of all contained elements.
231 ///
232 /// # Examples
233 ///
234 /// ```
235 /// let mut v = [4i32, -5, 1, -3, 2];
236 ///
237 /// v.sort_by_key(|k| k.abs());
238 /// assert_eq!(v, [1, 2, -3, 4, -5]);
239 /// ```
240 ///
241 /// [driftsort]: https://github.com/Voultapher/driftsort
242 /// [total order]: https://en.wikipedia.org/wiki/Total_order
243 #[cfg(not(no_global_oom_handling))]
244 #[rustc_allow_incoherent_impl]
245 #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
246 #[inline]
247 pub fn sort_by_key<K, F>(&mut self, mut f: F)
248 where
249 F: FnMut(&T) -> K,
250 K: Ord,
251 {
252 stable_sort(self, |a, b| f(a).lt(&f(b)));
253 }
254
255 /// Sorts the slice in ascending order with a key extraction function, preserving initial order
256 /// of equal elements.
257 ///
258 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \*
259 /// log(*n*)) worst-case, where the key function is *O*(*m*).
260 ///
261 /// During sorting, the key function is called at most once per element, by using temporary
262 /// storage to remember the results of key evaluation. The order of calls to the key function is
263 /// unspecified and may change in future versions of the standard library.
264 ///
265 /// If the implementation of [`Ord`] for `K` does not implement a [total order], the function
266 /// may panic; even if the function exits normally, the resulting order of elements in the slice
267 /// is unspecified. See also the note on panicking below.
268 ///
269 /// For simple key functions (e.g., functions that are property accesses or basic operations),
270 /// [`sort_by_key`](slice::sort_by_key) is likely to be faster.
271 ///
272 /// # Current implementation
273 ///
274 /// The current implementation is based on [instruction-parallel-network sort][ipnsort] by Lukas
275 /// Bergdoll, which combines the fast average case of randomized quicksort with the fast worst
276 /// case of heapsort, while achieving linear time on fully sorted and reversed inputs. And
277 /// *O*(*k* \* log(*n*)) where *k* is the number of distinct elements in the input. It leverages
278 /// superscalar out-of-order execution capabilities commonly found in CPUs, to efficiently
279 /// perform the operation.
280 ///
281 /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the
282 /// length of the slice.
283 ///
284 /// # Panics
285 ///
286 /// May panic if the implementation of [`Ord`] for `K` does not implement a [total order], or if
287 /// the [`Ord`] implementation panics.
288 ///
289 /// All safe functions on slices preserve the invariant that even if the function panics, all
290 /// original elements will remain in the slice and any possible modifications via interior
291 /// mutability are observed in the input. This ensures that recovery code (for instance inside
292 /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
293 /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
294 /// to dispose of all contained elements.
295 ///
296 /// # Examples
297 ///
298 /// ```
299 /// let mut v = [4i32, -5, 1, -3, 2, 10];
300 ///
301 /// // Strings are sorted by lexicographical order.
302 /// v.sort_by_cached_key(|k| k.to_string());
303 /// assert_eq!(v, [-3, -5, 1, 10, 2, 4]);
304 /// ```
305 ///
306 /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
307 /// [total order]: https://en.wikipedia.org/wiki/Total_order
308 #[cfg(not(no_global_oom_handling))]
309 #[rustc_allow_incoherent_impl]
310 #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")]
311 #[inline]
312 pub fn sort_by_cached_key<K, F>(&mut self, f: F)
313 where
314 F: FnMut(&T) -> K,
315 K: Ord,
316 {
317 // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.
318 macro_rules! sort_by_key {
319 ($t:ty, $slice:ident, $f:ident) => {{
320 let mut indices: Vec<_> =
321 $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
322 // The elements of `indices` are unique, as they are indexed, so any sort will be
323 // stable with respect to the original slice. We use `sort_unstable` here because
324 // it requires no memory allocation.
325 indices.sort_unstable();
326 for i in 0..$slice.len() {
327 let mut index = indices[i].1;
328 while (index as usize) < i {
329 index = indices[index as usize].1;
330 }
331 indices[i].1 = index;
332 $slice.swap(i, index as usize);
333 }
334 }};
335 }
336
337 let len = self.len();
338 if len < 2 {
339 return;
340 }
341
342 // Avoids binary-size usage in cases where the alignment doesn't work out to make this
343 // beneficial or on 32-bit platforms.
344 let is_using_u32_as_idx_type_helpful =
345 const { size_of::<(K, u32)>() < size_of::<(K, usize)>() };
346
347 // It's possible to instantiate this for u8 and u16 but, doing so is very wasteful in terms
348 // of compile-times and binary-size, the peak saved heap memory for u16 is (u8 + u16) -> 4
349 // bytes * u16::MAX vs (u8 + u32) -> 8 bytes * u16::MAX, the saved heap memory is at peak
350 // ~262KB.
351 if is_using_u32_as_idx_type_helpful && len <= (u32::MAX as usize) {
352 return sort_by_key!(u32, self, f);
353 }
354
355 sort_by_key!(usize, self, f)
356 }
357
358 /// Copies `self` into a new `Vec`.
359 ///
360 /// # Examples
361 ///
362 /// ```
363 /// let s = [10, 40, 30];
364 /// let x = s.to_vec();
365 /// // Here, `s` and `x` can be modified independently.
366 /// ```
367 #[cfg(not(no_global_oom_handling))]
368 #[rustc_allow_incoherent_impl]
369 #[rustc_conversion_suggestion]
370 #[stable(feature = "rust1", since = "1.0.0")]
371 #[inline]
372 pub fn to_vec(&self) -> Vec<T>
373 where
374 T: Clone,
375 {
376 self.to_vec_in(Global)
377 }
378
379 /// Copies `self` into a new `Vec` with an allocator.
380 ///
381 /// # Examples
382 ///
383 /// ```
384 /// #![feature(allocator_api)]
385 ///
386 /// use std::alloc::System;
387 ///
388 /// let s = [10, 40, 30];
389 /// let x = s.to_vec_in(System);
390 /// // Here, `s` and `x` can be modified independently.
391 /// ```
392 #[cfg(not(no_global_oom_handling))]
393 #[rustc_allow_incoherent_impl]
394 #[inline]
395 #[unstable(feature = "allocator_api", issue = "32838")]
396 pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
397 where
398 T: Clone,
399 {
400 return T::to_vec(self, alloc);
401
402 trait ConvertVec {
403 fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A>
404 where
405 Self: Sized;
406 }
407
408 impl<T: Clone> ConvertVec for T {
409 #[inline]
410 default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
411 struct DropGuard<'a, T, A: Allocator> {
412 vec: &'a mut Vec<T, A>,
413 num_init: usize,
414 }
415 impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
416 #[inline]
417 fn drop(&mut self) {
418 // SAFETY:
419 // items were marked initialized in the loop below
420 unsafe {
421 self.vec.set_len(self.num_init);
422 }
423 }
424 }
425 let mut vec = Vec::with_capacity_in(s.len(), alloc);
426 let mut guard = DropGuard { vec: &mut vec, num_init: 0 };
427 let slots = guard.vec.spare_capacity_mut();
428 // .take(slots.len()) is necessary for LLVM to remove bounds checks
429 // and has better codegen than zip.
430 for (i, b) in s.iter().enumerate().take(slots.len()) {
431 guard.num_init = i;
432 slots[i].write(b.clone());
433 }
434 core::mem::forget(guard);
435 // SAFETY:
436 // the vec was allocated and initialized above to at least this length.
437 unsafe {
438 vec.set_len(s.len());
439 }
440 vec
441 }
442 }
443
444 impl<T: TrivialClone> ConvertVec for T {
445 #[inline]
446 fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
447 let len = s.len();
448 let mut v = Vec::with_capacity_in(len, alloc);
449 if len > 0 {
450 // SAFETY:
451 // allocated above with the capacity of `s`, and initialize to `s.len()` in
452 // ptr::copy_to_non_overlapping below.
453 unsafe {
454 s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), len);
455 v.set_len(len);
456 }
457 }
458 v
459 }
460 }
461 }
462
463 /// Converts `self` into a vector without clones or allocation.
464 ///
465 /// The resulting vector can be converted back into a box via
466 /// `Vec<T>`'s `into_boxed_slice` method.
467 ///
468 /// # Examples
469 ///
470 /// ```
471 /// let s: Box<[i32]> = Box::new([10, 40, 30]);
472 /// let x = s.into_vec();
473 /// // `s` cannot be used anymore because it has been converted into `x`.
474 ///
475 /// assert_eq!(x, vec![10, 40, 30]);
476 /// ```
477 #[rustc_allow_incoherent_impl]
478 #[stable(feature = "rust1", since = "1.0.0")]
479 #[rustc_const_unstable(feature = "const_heap", issue = "79597")]
480 #[inline]
481 pub const fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> {
482 let len = self.len();
483 let (b, alloc) = Box::into_raw_with_allocator(self);
484 // SAFETY: `b` is currently allocated with `alloc` and was allocated with the
485 // matching layout for an array of `T * len`, the length is equal to the capacity,
486 // and the existence of a `Box<[T]>` is proof that the first `len` elements are
487 // valid `T`s.
488 unsafe { Vec::from_raw_parts_in(b as *mut T, len, len, alloc) }
489 }
490
491 /// Creates a vector by copying a slice `n` times.
492 ///
493 /// # Panics
494 ///
495 /// This function will panic if the capacity would overflow.
496 ///
497 /// # Examples
498 ///
499 /// ```
500 /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
501 /// ```
502 ///
503 /// A panic upon overflow:
504 ///
505 /// ```should_panic
506 /// // this will panic at runtime
507 /// b"0123456789abcdef".repeat(usize::MAX);
508 /// ```
509 #[rustc_allow_incoherent_impl]
510 #[cfg(not(no_global_oom_handling))]
511 #[stable(feature = "repeat_generic_slice", since = "1.40.0")]
512 pub fn repeat(&self, n: usize) -> Vec<T>
513 where
514 T: Copy,
515 {
516 if n == 0 {
517 return Vec::new();
518 }
519
520 // If `n` is larger than zero, it can be split as
521 // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
522 // `2^expn` is the number represented by the leftmost '1' bit of `n`,
523 // and `rem` is the remaining part of `n`.
524
525 // Using `Vec` to access `set_len()`.
526 let capacity = self.len().checked_mul(n).expect("capacity overflow");
527 let mut buf = Vec::with_capacity(capacity);
528
529 // `2^expn` repetition is done by doubling `buf` `expn`-times.
530 buf.extend(self);
531 {
532 let mut m = n >> 1;
533 // If `m > 0`, there are remaining bits up to the leftmost '1'.
534 while m > 0 {
535 // `buf.extend(buf)`:
536 // SAFETY: We're copying `len` elements after offsetting by `len`,
537 // with the previous call to `extend` ensuring that the first `len`
538 // elements are valid `T`s and the call to `with_capacity` ensuring
539 // we have `len * n` space to write the new elements.
540 // Each iteration of this loop doubles the number of initialised elements,
541 // which is tracked via `m` - when `m == 0`, we've written `most_significant_bit(n)`
542 // elements to the buffer.
543 unsafe {
544 ptr::copy_nonoverlapping::<T>(
545 buf.as_ptr(),
546 (buf.as_mut_ptr()).add(buf.len()),
547 buf.len(),
548 );
549 }
550 // `buf` has capacity of `self.len() * n`.
551 let buf_len = buf.len();
552 // SAFETY: We initialised another `buf_len` elements above.
553 unsafe { buf.set_len(buf_len * 2) };
554
555 m >>= 1;
556 }
557 }
558
559 // `rem` (`= n - 2^expn`) repetition is done by copying
560 // first `rem` repetitions from `buf` itself.
561 let rem_len = capacity - buf.len(); // `self.len() * rem`
562 if rem_len > 0 {
563 // `buf.extend(buf[0 .. rem_len])`:
564 // SAFETY: We're copying `rem_len` elements after offsetting by `len`. The previous
565 // looping `copy_nonoverlapping` always doubled the number of instantiated elements,
566 // and so if `rem_len` was greater than `len` it would have allowed for another such
567 // doubling, until such time that `rem_len < len`. Thus, the space for these remaining
568 // `rem_len` elements must be preceded by more than `rem_len` previously-copied
569 // elements.
570 // Setting the length is correct since we've initialised the whole `capacity`-length
571 // space with copies of the previous `len` elements.
572 unsafe {
573 // This is non-overlapping since `2^expn > rem`.
574 ptr::copy_nonoverlapping::<T>(
575 buf.as_ptr(),
576 (buf.as_mut_ptr()).add(buf.len()),
577 rem_len,
578 );
579 // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
580 buf.set_len(capacity);
581 }
582 }
583 buf
584 }
585
586 /// Flattens a slice of `T` into a single value `Self::Output`.
587 ///
588 /// # Examples
589 ///
590 /// ```
591 /// assert_eq!(["hello", "world"].concat(), "helloworld");
592 /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
593 /// ```
594 #[rustc_allow_incoherent_impl]
595 #[stable(feature = "rust1", since = "1.0.0")]
596 pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
597 where
598 Self: Concat<Item>,
599 {
600 Concat::concat(self)
601 }
602
603 /// Flattens a slice of `T` into a single value `Self::Output`, placing a
604 /// given separator between each.
605 ///
606 /// # Examples
607 ///
608 /// ```
609 /// assert_eq!(["hello", "world"].join(" "), "hello world");
610 /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
611 /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
612 /// ```
613 #[rustc_allow_incoherent_impl]
614 #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
615 pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
616 where
617 Self: Join<Separator>,
618 {
619 Join::join(self, sep)
620 }
621
622 /// Flattens a slice of `T` into a single value `Self::Output`, placing a
623 /// given separator between each.
624 ///
625 /// # Examples
626 ///
627 /// ```
628 /// # #![allow(deprecated)]
629 /// assert_eq!(["hello", "world"].connect(" "), "hello world");
630 /// assert_eq!([[1, 2], [3, 4]].connect(&0), [1, 2, 0, 3, 4]);
631 /// ```
632 #[rustc_allow_incoherent_impl]
633 #[stable(feature = "rust1", since = "1.0.0")]
634 #[deprecated(since = "1.3.0", note = "renamed to join", suggestion = "join")]
635 pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
636 where
637 Self: Join<Separator>,
638 {
639 Join::join(self, sep)
640 }
641}
642
643impl [u8] {
644 /// Returns a vector containing a copy of this slice where each byte
645 /// is mapped to its ASCII upper case equivalent.
646 ///
647 /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
648 /// but non-ASCII letters are unchanged.
649 ///
650 /// To uppercase the value in-place, use [`make_ascii_uppercase`].
651 ///
652 /// [`make_ascii_uppercase`]: slice::make_ascii_uppercase
653 #[cfg(not(no_global_oom_handling))]
654 #[rustc_allow_incoherent_impl]
655 #[must_use = "this returns the uppercase bytes as a new Vec, \
656 without modifying the original"]
657 #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
658 #[inline]
659 pub fn to_ascii_uppercase(&self) -> Vec<u8> {
660 self.iter().map(|b| b.to_ascii_uppercase()).collect()
661 }
662
663 /// Returns a vector containing a copy of this slice where each byte
664 /// is mapped to its ASCII lower case equivalent.
665 ///
666 /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
667 /// but non-ASCII letters are unchanged.
668 ///
669 /// To lowercase the value in-place, use [`make_ascii_lowercase`].
670 ///
671 /// [`make_ascii_lowercase`]: slice::make_ascii_lowercase
672 #[cfg(not(no_global_oom_handling))]
673 #[rustc_allow_incoherent_impl]
674 #[must_use = "this returns the lowercase bytes as a new Vec, \
675 without modifying the original"]
676 #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
677 #[inline]
678 pub fn to_ascii_lowercase(&self) -> Vec<u8> {
679 self.iter().map(|b| b.to_ascii_lowercase()).collect()
680 }
681}
682
683////////////////////////////////////////////////////////////////////////////////
684// Extension traits for slices over specific kinds of data
685////////////////////////////////////////////////////////////////////////////////
686
687/// Helper trait for [`[T]::concat`](slice::concat).
688///
689/// Note: the `Item` type parameter is not used in this trait,
690/// but it allows impls to be more generic.
691/// Without it, we get this error:
692///
693/// ```error
694/// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica
695/// --> library/alloc/src/slice.rs:608:6
696/// |
697/// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
698/// | ^ unconstrained type parameter
699/// ```
700///
701/// This is because there could exist `V` types with multiple `Borrow<[_]>` impls,
702/// such that multiple `T` types would apply:
703///
704/// ```
705/// # #[allow(dead_code)]
706/// pub struct Foo(Vec<u32>, Vec<String>);
707///
708/// impl std::borrow::Borrow<[u32]> for Foo {
709/// fn borrow(&self) -> &[u32] { &self.0 }
710/// }
711///
712/// impl std::borrow::Borrow<[String]> for Foo {
713/// fn borrow(&self) -> &[String] { &self.1 }
714/// }
715/// ```
716#[unstable(feature = "slice_concat_trait", issue = "27747")]
717pub trait Concat<Item: ?Sized> {
718 #[unstable(feature = "slice_concat_trait", issue = "27747")]
719 /// The resulting type after concatenation
720 type Output;
721
722 /// Implementation of [`[T]::concat`](slice::concat)
723 #[unstable(feature = "slice_concat_trait", issue = "27747")]
724 fn concat(slice: &Self) -> Self::Output;
725}
726
727/// Helper trait for [`[T]::join`](slice::join)
728#[unstable(feature = "slice_concat_trait", issue = "27747")]
729pub trait Join<Separator> {
730 #[unstable(feature = "slice_concat_trait", issue = "27747")]
731 /// The resulting type after concatenation
732 type Output;
733
734 /// Implementation of [`[T]::join`](slice::join)
735 #[unstable(feature = "slice_concat_trait", issue = "27747")]
736 fn join(slice: &Self, sep: Separator) -> Self::Output;
737}
738
739#[cfg(not(no_global_oom_handling))]
740#[unstable(feature = "slice_concat_ext", issue = "27747")]
741impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] {
742 type Output = Vec<T>;
743
744 fn concat(slice: &Self) -> Vec<T> {
745 let size = slice.iter().map(|slice| slice.borrow().len()).sum();
746 let mut result = Vec::with_capacity(size);
747 for v in slice {
748 result.extend_from_slice(v.borrow())
749 }
750 result
751 }
752}
753
754#[cfg(not(no_global_oom_handling))]
755#[unstable(feature = "slice_concat_ext", issue = "27747")]
756impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
757 type Output = Vec<T>;
758
759 fn join(slice: &Self, sep: &T) -> Vec<T> {
760 let mut iter = slice.iter();
761 let first = match iter.next() {
762 Some(first) => first,
763 None => return vec![],
764 };
765 let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
766 let mut result = Vec::with_capacity(size);
767 result.extend_from_slice(first.borrow());
768
769 for v in iter {
770 result.push(sep.clone());
771 result.extend_from_slice(v.borrow())
772 }
773 result
774 }
775}
776
777#[cfg(not(no_global_oom_handling))]
778#[unstable(feature = "slice_concat_ext", issue = "27747")]
779impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
780 type Output = Vec<T>;
781
782 fn join(slice: &Self, sep: &[T]) -> Vec<T> {
783 let mut iter = slice.iter();
784 let first = match iter.next() {
785 Some(first) => first,
786 None => return vec![],
787 };
788 let size =
789 slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
790 let mut result = Vec::with_capacity(size);
791 result.extend_from_slice(first.borrow());
792
793 for v in iter {
794 result.extend_from_slice(sep);
795 result.extend_from_slice(v.borrow())
796 }
797 result
798 }
799}
800
801////////////////////////////////////////////////////////////////////////////////
802// Standard trait implementations for slices
803////////////////////////////////////////////////////////////////////////////////
804
805#[stable(feature = "rust1", since = "1.0.0")]
806impl<T, A: Allocator> Borrow<[T]> for Vec<T, A> {
807 fn borrow(&self) -> &[T] {
808 &self[..]
809 }
810}
811
812#[stable(feature = "rust1", since = "1.0.0")]
813impl<T, A: Allocator> BorrowMut<[T]> for Vec<T, A> {
814 fn borrow_mut(&mut self) -> &mut [T] {
815 &mut self[..]
816 }
817}
818
819// Specializable trait for implementing ToOwned::clone_into. This is
820// public in the crate and has the Allocator parameter so that
821// vec::clone_from use it too.
822#[cfg(not(no_global_oom_handling))]
823pub(crate) trait SpecCloneIntoVec<T, A: Allocator> {
824 fn clone_into(&self, target: &mut Vec<T, A>);
825}
826
827#[cfg(not(no_global_oom_handling))]
828impl<T: Clone, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
829 default fn clone_into(&self, target: &mut Vec<T, A>) {
830 // drop anything in target that will not be overwritten
831 target.truncate(self.len());
832
833 // target.len <= self.len due to the truncate above, so the
834 // slices here are always in-bounds.
835 let (init, tail) = self.split_at(target.len());
836
837 // reuse the contained values' allocations/resources.
838 target.clone_from_slice(init);
839 target.extend_from_slice(tail);
840 }
841}
842
843#[cfg(not(no_global_oom_handling))]
844impl<T: TrivialClone, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
845 fn clone_into(&self, target: &mut Vec<T, A>) {
846 target.clear();
847 target.extend_from_slice(self);
848 }
849}
850
851#[cfg(not(no_global_oom_handling))]
852#[stable(feature = "rust1", since = "1.0.0")]
853impl<T: Clone> ToOwned for [T] {
854 type Owned = Vec<T>;
855
856 fn to_owned(&self) -> Vec<T> {
857 self.to_vec()
858 }
859
860 fn clone_into(&self, target: &mut Vec<T>) {
861 SpecCloneIntoVec::clone_into(self, target);
862 }
863}
864
865////////////////////////////////////////////////////////////////////////////////
866// Sorting
867////////////////////////////////////////////////////////////////////////////////
868
869#[inline]
870#[cfg(not(no_global_oom_handling))]
871fn stable_sort<T, F>(v: &mut [T], mut is_less: F)
872where
873 F: FnMut(&T, &T) -> bool,
874{
875 sort::stable::sort::<T, F, Vec<T>>(v, &mut is_less);
876}
877
878#[cfg(not(no_global_oom_handling))]
879#[unstable(issue = "none", feature = "std_internals")]
880impl<T> sort::stable::BufGuard<T> for Vec<T> {
881 fn with_capacity(capacity: usize) -> Self {
882 Vec::with_capacity(capacity)
883 }
884
885 fn as_uninit_slice_mut(&mut self) -> &mut [MaybeUninit<T>] {
886 self.spare_capacity_mut()
887 }
888}