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