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