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