1//! Slice management and manipulation.
2//!
3//! For more details see [`std::slice`].
4//!
5//! [`std::slice`]: ../../std/slice/index.html
6
7#![stable(feature = "rust1", since = "1.0.0")]
8
9use crate::cmp::Ordering::{self, Equal, Greater, Less};
10use crate::fmt;
11use crate::hint;
12use crate::intrinsics::exact_div;
13use crate::mem::{self, SizedTypeProperties};
14use crate::num::NonZeroUsize;
15use crate::ops::{Bound, OneSidedRange, Range, RangeBounds};
16use crate::panic::debug_assert_nounwind;
17use crate::ptr;
18use crate::simd::{self, Simd};
19use crate::slice;
20
21#[unstable(
22 feature = "slice_internals",
23 issue = "none",
24 reason = "exposed from core to be reused in std; use the memchr crate"
25)]
26/// Pure rust memchr implementation, taken from rust-memchr
27pub mod memchr;
28
29#[unstable(
30 feature = "slice_internals",
31 issue = "none",
32 reason = "exposed from core to be reused in std;"
33)]
34pub mod sort;
35
36mod ascii;
37mod cmp;
38pub(crate) mod index;
39mod iter;
40mod raw;
41mod rotate;
42mod select;
43mod specialize;
44
45#[unstable(feature = "str_internals", issue = "none")]
46#[doc(hidden)]
47pub use ascii::is_ascii_simple;
48
49#[stable(feature = "rust1", since = "1.0.0")]
50pub use iter::{Chunks, ChunksMut, Windows};
51#[stable(feature = "rust1", since = "1.0.0")]
52pub use iter::{Iter, IterMut};
53#[stable(feature = "rust1", since = "1.0.0")]
54pub use iter::{RSplitN, RSplitNMut, Split, SplitMut, SplitN, SplitNMut};
55
56#[stable(feature = "slice_rsplit", since = "1.27.0")]
57pub use iter::{RSplit, RSplitMut};
58
59#[stable(feature = "chunks_exact", since = "1.31.0")]
60pub use iter::{ChunksExact, ChunksExactMut};
61
62#[stable(feature = "rchunks", since = "1.31.0")]
63pub use iter::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
64
65#[unstable(feature = "array_chunks", issue = "74985")]
66pub use iter::{ArrayChunks, ArrayChunksMut};
67
68#[unstable(feature = "array_windows", issue = "75027")]
69pub use iter::ArrayWindows;
70
71#[stable(feature = "slice_group_by", since = "1.77.0")]
72pub use iter::{ChunkBy, ChunkByMut};
73
74#[stable(feature = "split_inclusive", since = "1.51.0")]
75pub use iter::{SplitInclusive, SplitInclusiveMut};
76
77#[stable(feature = "rust1", since = "1.0.0")]
78pub use raw::{from_raw_parts, from_raw_parts_mut};
79
80#[stable(feature = "from_ref", since = "1.28.0")]
81pub use raw::{from_mut, from_ref};
82
83#[unstable(feature = "slice_from_ptr_range", issue = "89792")]
84pub use raw::{from_mut_ptr_range, from_ptr_range};
85
86// This function is public only because there is no other way to unit test heapsort.
87#[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "none")]
88pub use sort::heapsort;
89
90#[stable(feature = "slice_get_slice", since = "1.28.0")]
91pub use index::SliceIndex;
92
93#[unstable(feature = "slice_range", issue = "76393")]
94pub use index::range;
95
96#[stable(feature = "inherent_ascii_escape", since = "1.60.0")]
97pub use ascii::EscapeAscii;
98
99/// Calculates the direction and split point of a one-sided range.
100///
101/// This is a helper function for `take` and `take_mut` that returns
102/// the direction of the split (front or back) as well as the index at
103/// which to split. Returns `None` if the split index would overflow.
104#[inline]
105fn split_point_of(range: impl OneSidedRange<usize>) -> Option<(Direction, usize)> {
106 use Bound::*;
107
108 Some(match (range.start_bound(), range.end_bound()) {
109 (Unbounded, Excluded(i: &usize)) => (Direction::Front, *i),
110 (Unbounded, Included(i: &usize)) => (Direction::Front, i.checked_add(1)?),
111 (Excluded(i: &usize), Unbounded) => (Direction::Back, i.checked_add(1)?),
112 (Included(i: &usize), Unbounded) => (Direction::Back, *i),
113 _ => unreachable!(),
114 })
115}
116
117enum Direction {
118 Front,
119 Back,
120}
121
122#[cfg(not(test))]
123impl<T> [T] {
124 /// Returns the number of elements in the slice.
125 ///
126 /// # Examples
127 ///
128 /// ```
129 /// let a = [1, 2, 3];
130 /// assert_eq!(a.len(), 3);
131 /// ```
132 #[lang = "slice_len_fn"]
133 #[stable(feature = "rust1", since = "1.0.0")]
134 #[rustc_const_stable(feature = "const_slice_len", since = "1.39.0")]
135 #[rustc_allow_const_fn_unstable(ptr_metadata)]
136 #[inline]
137 #[must_use]
138 pub const fn len(&self) -> usize {
139 ptr::metadata(self)
140 }
141
142 /// Returns `true` if the slice has a length of 0.
143 ///
144 /// # Examples
145 ///
146 /// ```
147 /// let a = [1, 2, 3];
148 /// assert!(!a.is_empty());
149 /// ```
150 #[stable(feature = "rust1", since = "1.0.0")]
151 #[rustc_const_stable(feature = "const_slice_is_empty", since = "1.39.0")]
152 #[inline]
153 #[must_use]
154 pub const fn is_empty(&self) -> bool {
155 self.len() == 0
156 }
157
158 /// Returns the first element of the slice, or `None` if it is empty.
159 ///
160 /// # Examples
161 ///
162 /// ```
163 /// let v = [10, 40, 30];
164 /// assert_eq!(Some(&10), v.first());
165 ///
166 /// let w: &[i32] = &[];
167 /// assert_eq!(None, w.first());
168 /// ```
169 #[stable(feature = "rust1", since = "1.0.0")]
170 #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
171 #[inline]
172 #[must_use]
173 pub const fn first(&self) -> Option<&T> {
174 if let [first, ..] = self { Some(first) } else { None }
175 }
176
177 /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty.
178 ///
179 /// # Examples
180 ///
181 /// ```
182 /// let x = &mut [0, 1, 2];
183 ///
184 /// if let Some(first) = x.first_mut() {
185 /// *first = 5;
186 /// }
187 /// assert_eq!(x, &[5, 1, 2]);
188 /// ```
189 #[stable(feature = "rust1", since = "1.0.0")]
190 #[rustc_const_unstable(feature = "const_slice_first_last", issue = "83570")]
191 #[inline]
192 #[must_use]
193 pub const fn first_mut(&mut self) -> Option<&mut T> {
194 if let [first, ..] = self { Some(first) } else { None }
195 }
196
197 /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
198 ///
199 /// # Examples
200 ///
201 /// ```
202 /// let x = &[0, 1, 2];
203 ///
204 /// if let Some((first, elements)) = x.split_first() {
205 /// assert_eq!(first, &0);
206 /// assert_eq!(elements, &[1, 2]);
207 /// }
208 /// ```
209 #[stable(feature = "slice_splits", since = "1.5.0")]
210 #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
211 #[inline]
212 #[must_use]
213 pub const fn split_first(&self) -> Option<(&T, &[T])> {
214 if let [first, tail @ ..] = self { Some((first, tail)) } else { None }
215 }
216
217 /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
218 ///
219 /// # Examples
220 ///
221 /// ```
222 /// let x = &mut [0, 1, 2];
223 ///
224 /// if let Some((first, elements)) = x.split_first_mut() {
225 /// *first = 3;
226 /// elements[0] = 4;
227 /// elements[1] = 5;
228 /// }
229 /// assert_eq!(x, &[3, 4, 5]);
230 /// ```
231 #[stable(feature = "slice_splits", since = "1.5.0")]
232 #[rustc_const_unstable(feature = "const_slice_first_last", issue = "83570")]
233 #[inline]
234 #[must_use]
235 pub const fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
236 if let [first, tail @ ..] = self { Some((first, tail)) } else { None }
237 }
238
239 /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
240 ///
241 /// # Examples
242 ///
243 /// ```
244 /// let x = &[0, 1, 2];
245 ///
246 /// if let Some((last, elements)) = x.split_last() {
247 /// assert_eq!(last, &2);
248 /// assert_eq!(elements, &[0, 1]);
249 /// }
250 /// ```
251 #[stable(feature = "slice_splits", since = "1.5.0")]
252 #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
253 #[inline]
254 #[must_use]
255 pub const fn split_last(&self) -> Option<(&T, &[T])> {
256 if let [init @ .., last] = self { Some((last, init)) } else { None }
257 }
258
259 /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
260 ///
261 /// # Examples
262 ///
263 /// ```
264 /// let x = &mut [0, 1, 2];
265 ///
266 /// if let Some((last, elements)) = x.split_last_mut() {
267 /// *last = 3;
268 /// elements[0] = 4;
269 /// elements[1] = 5;
270 /// }
271 /// assert_eq!(x, &[4, 5, 3]);
272 /// ```
273 #[stable(feature = "slice_splits", since = "1.5.0")]
274 #[rustc_const_unstable(feature = "const_slice_first_last", issue = "83570")]
275 #[inline]
276 #[must_use]
277 pub const fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
278 if let [init @ .., last] = self { Some((last, init)) } else { None }
279 }
280
281 /// Returns the last element of the slice, or `None` if it is empty.
282 ///
283 /// # Examples
284 ///
285 /// ```
286 /// let v = [10, 40, 30];
287 /// assert_eq!(Some(&30), v.last());
288 ///
289 /// let w: &[i32] = &[];
290 /// assert_eq!(None, w.last());
291 /// ```
292 #[stable(feature = "rust1", since = "1.0.0")]
293 #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
294 #[inline]
295 #[must_use]
296 pub const fn last(&self) -> Option<&T> {
297 if let [.., last] = self { Some(last) } else { None }
298 }
299
300 /// Returns a mutable reference to the last item in the slice.
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// let x = &mut [0, 1, 2];
306 ///
307 /// if let Some(last) = x.last_mut() {
308 /// *last = 10;
309 /// }
310 /// assert_eq!(x, &[0, 1, 10]);
311 /// ```
312 #[stable(feature = "rust1", since = "1.0.0")]
313 #[rustc_const_unstable(feature = "const_slice_first_last", issue = "83570")]
314 #[inline]
315 #[must_use]
316 pub const fn last_mut(&mut self) -> Option<&mut T> {
317 if let [.., last] = self { Some(last) } else { None }
318 }
319
320 /// Return an array reference to the first `N` items in the slice.
321 ///
322 /// If the slice is not at least `N` in length, this will return `None`.
323 ///
324 /// # Examples
325 ///
326 /// ```
327 /// let u = [10, 40, 30];
328 /// assert_eq!(Some(&[10, 40]), u.first_chunk::<2>());
329 ///
330 /// let v: &[i32] = &[10];
331 /// assert_eq!(None, v.first_chunk::<2>());
332 ///
333 /// let w: &[i32] = &[];
334 /// assert_eq!(Some(&[]), w.first_chunk::<0>());
335 /// ```
336 #[inline]
337 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
338 #[rustc_const_stable(feature = "slice_first_last_chunk", since = "1.77.0")]
339 pub const fn first_chunk<const N: usize>(&self) -> Option<&[T; N]> {
340 if self.len() < N {
341 None
342 } else {
343 // SAFETY: We explicitly check for the correct number of elements,
344 // and do not let the reference outlive the slice.
345 Some(unsafe { &*(self.as_ptr().cast::<[T; N]>()) })
346 }
347 }
348
349 /// Return a mutable array reference to the first `N` items in the slice.
350 ///
351 /// If the slice is not at least `N` in length, this will return `None`.
352 ///
353 /// # Examples
354 ///
355 /// ```
356 /// let x = &mut [0, 1, 2];
357 ///
358 /// if let Some(first) = x.first_chunk_mut::<2>() {
359 /// first[0] = 5;
360 /// first[1] = 4;
361 /// }
362 /// assert_eq!(x, &[5, 4, 2]);
363 ///
364 /// assert_eq!(None, x.first_chunk_mut::<4>());
365 /// ```
366 #[inline]
367 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
368 #[rustc_const_unstable(feature = "const_slice_first_last_chunk", issue = "111774")]
369 pub const fn first_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> {
370 if self.len() < N {
371 None
372 } else {
373 // SAFETY: We explicitly check for the correct number of elements,
374 // do not let the reference outlive the slice,
375 // and require exclusive access to the entire slice to mutate the chunk.
376 Some(unsafe { &mut *(self.as_mut_ptr().cast::<[T; N]>()) })
377 }
378 }
379
380 /// Return an array reference to the first `N` items in the slice and the remaining slice.
381 ///
382 /// If the slice is not at least `N` in length, this will return `None`.
383 ///
384 /// # Examples
385 ///
386 /// ```
387 /// let x = &[0, 1, 2];
388 ///
389 /// if let Some((first, elements)) = x.split_first_chunk::<2>() {
390 /// assert_eq!(first, &[0, 1]);
391 /// assert_eq!(elements, &[2]);
392 /// }
393 ///
394 /// assert_eq!(None, x.split_first_chunk::<4>());
395 /// ```
396 #[inline]
397 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
398 #[rustc_const_stable(feature = "slice_first_last_chunk", since = "1.77.0")]
399 pub const fn split_first_chunk<const N: usize>(&self) -> Option<(&[T; N], &[T])> {
400 if self.len() < N {
401 None
402 } else {
403 // SAFETY: We manually verified the bounds of the split.
404 let (first, tail) = unsafe { self.split_at_unchecked(N) };
405
406 // SAFETY: We explicitly check for the correct number of elements,
407 // and do not let the references outlive the slice.
408 Some((unsafe { &*(first.as_ptr().cast::<[T; N]>()) }, tail))
409 }
410 }
411
412 /// Return a mutable array reference to the first `N` items in the slice and the remaining
413 /// slice.
414 ///
415 /// If the slice is not at least `N` in length, this will return `None`.
416 ///
417 /// # Examples
418 ///
419 /// ```
420 /// let x = &mut [0, 1, 2];
421 ///
422 /// if let Some((first, elements)) = x.split_first_chunk_mut::<2>() {
423 /// first[0] = 3;
424 /// first[1] = 4;
425 /// elements[0] = 5;
426 /// }
427 /// assert_eq!(x, &[3, 4, 5]);
428 ///
429 /// assert_eq!(None, x.split_first_chunk_mut::<4>());
430 /// ```
431 #[inline]
432 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
433 #[rustc_const_unstable(feature = "const_slice_first_last_chunk", issue = "111774")]
434 pub const fn split_first_chunk_mut<const N: usize>(
435 &mut self,
436 ) -> Option<(&mut [T; N], &mut [T])> {
437 if self.len() < N {
438 None
439 } else {
440 // SAFETY: We manually verified the bounds of the split.
441 let (first, tail) = unsafe { self.split_at_mut_unchecked(N) };
442
443 // SAFETY: We explicitly check for the correct number of elements,
444 // do not let the reference outlive the slice,
445 // and enforce exclusive mutability of the chunk by the split.
446 Some((unsafe { &mut *(first.as_mut_ptr().cast::<[T; N]>()) }, tail))
447 }
448 }
449
450 /// Return an array reference to the last `N` items in the slice and the remaining slice.
451 ///
452 /// If the slice is not at least `N` in length, this will return `None`.
453 ///
454 /// # Examples
455 ///
456 /// ```
457 /// let x = &[0, 1, 2];
458 ///
459 /// if let Some((elements, last)) = x.split_last_chunk::<2>() {
460 /// assert_eq!(elements, &[0]);
461 /// assert_eq!(last, &[1, 2]);
462 /// }
463 ///
464 /// assert_eq!(None, x.split_last_chunk::<4>());
465 /// ```
466 #[inline]
467 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
468 #[rustc_const_stable(feature = "slice_first_last_chunk", since = "1.77.0")]
469 pub const fn split_last_chunk<const N: usize>(&self) -> Option<(&[T], &[T; N])> {
470 if self.len() < N {
471 None
472 } else {
473 // SAFETY: We manually verified the bounds of the split.
474 let (init, last) = unsafe { self.split_at_unchecked(self.len() - N) };
475
476 // SAFETY: We explicitly check for the correct number of elements,
477 // and do not let the references outlive the slice.
478 Some((init, unsafe { &*(last.as_ptr().cast::<[T; N]>()) }))
479 }
480 }
481
482 /// Return a mutable array reference to the last `N` items in the slice and the remaining
483 /// slice.
484 ///
485 /// If the slice is not at least `N` in length, this will return `None`.
486 ///
487 /// # Examples
488 ///
489 /// ```
490 /// let x = &mut [0, 1, 2];
491 ///
492 /// if let Some((elements, last)) = x.split_last_chunk_mut::<2>() {
493 /// last[0] = 3;
494 /// last[1] = 4;
495 /// elements[0] = 5;
496 /// }
497 /// assert_eq!(x, &[5, 3, 4]);
498 ///
499 /// assert_eq!(None, x.split_last_chunk_mut::<4>());
500 /// ```
501 #[inline]
502 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
503 #[rustc_const_unstable(feature = "const_slice_first_last_chunk", issue = "111774")]
504 pub const fn split_last_chunk_mut<const N: usize>(
505 &mut self,
506 ) -> Option<(&mut [T], &mut [T; N])> {
507 if self.len() < N {
508 None
509 } else {
510 // SAFETY: We manually verified the bounds of the split.
511 let (init, last) = unsafe { self.split_at_mut_unchecked(self.len() - N) };
512
513 // SAFETY: We explicitly check for the correct number of elements,
514 // do not let the reference outlive the slice,
515 // and enforce exclusive mutability of the chunk by the split.
516 Some((init, unsafe { &mut *(last.as_mut_ptr().cast::<[T; N]>()) }))
517 }
518 }
519
520 /// Return an array reference to the last `N` items in the slice.
521 ///
522 /// If the slice is not at least `N` in length, this will return `None`.
523 ///
524 /// # Examples
525 ///
526 /// ```
527 /// let u = [10, 40, 30];
528 /// assert_eq!(Some(&[40, 30]), u.last_chunk::<2>());
529 ///
530 /// let v: &[i32] = &[10];
531 /// assert_eq!(None, v.last_chunk::<2>());
532 ///
533 /// let w: &[i32] = &[];
534 /// assert_eq!(Some(&[]), w.last_chunk::<0>());
535 /// ```
536 #[inline]
537 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
538 #[rustc_const_unstable(feature = "const_slice_first_last_chunk", issue = "111774")]
539 pub const fn last_chunk<const N: usize>(&self) -> Option<&[T; N]> {
540 if self.len() < N {
541 None
542 } else {
543 // SAFETY: We manually verified the bounds of the slice.
544 // FIXME: Without const traits, we need this instead of `get_unchecked`.
545 let last = unsafe { self.split_at_unchecked(self.len() - N).1 };
546
547 // SAFETY: We explicitly check for the correct number of elements,
548 // and do not let the references outlive the slice.
549 Some(unsafe { &*(last.as_ptr().cast::<[T; N]>()) })
550 }
551 }
552
553 /// Return a mutable array reference to the last `N` items in the slice.
554 ///
555 /// If the slice is not at least `N` in length, this will return `None`.
556 ///
557 /// # Examples
558 ///
559 /// ```
560 /// let x = &mut [0, 1, 2];
561 ///
562 /// if let Some(last) = x.last_chunk_mut::<2>() {
563 /// last[0] = 10;
564 /// last[1] = 20;
565 /// }
566 /// assert_eq!(x, &[0, 10, 20]);
567 ///
568 /// assert_eq!(None, x.last_chunk_mut::<4>());
569 /// ```
570 #[inline]
571 #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
572 #[rustc_const_unstable(feature = "const_slice_first_last_chunk", issue = "111774")]
573 pub const fn last_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> {
574 if self.len() < N {
575 None
576 } else {
577 // SAFETY: We manually verified the bounds of the slice.
578 // FIXME: Without const traits, we need this instead of `get_unchecked`.
579 let last = unsafe { self.split_at_mut_unchecked(self.len() - N).1 };
580
581 // SAFETY: We explicitly check for the correct number of elements,
582 // do not let the reference outlive the slice,
583 // and require exclusive access to the entire slice to mutate the chunk.
584 Some(unsafe { &mut *(last.as_mut_ptr().cast::<[T; N]>()) })
585 }
586 }
587
588 /// Returns a reference to an element or subslice depending on the type of
589 /// index.
590 ///
591 /// - If given a position, returns a reference to the element at that
592 /// position or `None` if out of bounds.
593 /// - If given a range, returns the subslice corresponding to that range,
594 /// or `None` if out of bounds.
595 ///
596 /// # Examples
597 ///
598 /// ```
599 /// let v = [10, 40, 30];
600 /// assert_eq!(Some(&40), v.get(1));
601 /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
602 /// assert_eq!(None, v.get(3));
603 /// assert_eq!(None, v.get(0..4));
604 /// ```
605 #[stable(feature = "rust1", since = "1.0.0")]
606 #[inline]
607 #[must_use]
608 pub fn get<I>(&self, index: I) -> Option<&I::Output>
609 where
610 I: SliceIndex<Self>,
611 {
612 index.get(self)
613 }
614
615 /// Returns a mutable reference to an element or subslice depending on the
616 /// type of index (see [`get`]) or `None` if the index is out of bounds.
617 ///
618 /// [`get`]: slice::get
619 ///
620 /// # Examples
621 ///
622 /// ```
623 /// let x = &mut [0, 1, 2];
624 ///
625 /// if let Some(elem) = x.get_mut(1) {
626 /// *elem = 42;
627 /// }
628 /// assert_eq!(x, &[0, 42, 2]);
629 /// ```
630 #[stable(feature = "rust1", since = "1.0.0")]
631 #[inline]
632 #[must_use]
633 pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
634 where
635 I: SliceIndex<Self>,
636 {
637 index.get_mut(self)
638 }
639
640 /// Returns a reference to an element or subslice, without doing bounds
641 /// checking.
642 ///
643 /// For a safe alternative see [`get`].
644 ///
645 /// # Safety
646 ///
647 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
648 /// even if the resulting reference is not used.
649 ///
650 /// You can think of this like `.get(index).unwrap_unchecked()`. It's UB
651 /// to call `.get_unchecked(len)`, even if you immediately convert to a
652 /// pointer. And it's UB to call `.get_unchecked(..len + 1)`,
653 /// `.get_unchecked(..=len)`, or similar.
654 ///
655 /// [`get`]: slice::get
656 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
657 ///
658 /// # Examples
659 ///
660 /// ```
661 /// let x = &[1, 2, 4];
662 ///
663 /// unsafe {
664 /// assert_eq!(x.get_unchecked(1), &2);
665 /// }
666 /// ```
667 #[stable(feature = "rust1", since = "1.0.0")]
668 #[inline]
669 #[must_use]
670 pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
671 where
672 I: SliceIndex<Self>,
673 {
674 // SAFETY: the caller must uphold most of the safety requirements for `get_unchecked`;
675 // the slice is dereferenceable because `self` is a safe reference.
676 // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is.
677 unsafe { &*index.get_unchecked(self) }
678 }
679
680 /// Returns a mutable reference to an element or subslice, without doing
681 /// bounds checking.
682 ///
683 /// For a safe alternative see [`get_mut`].
684 ///
685 /// # Safety
686 ///
687 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
688 /// even if the resulting reference is not used.
689 ///
690 /// You can think of this like `.get_mut(index).unwrap_unchecked()`. It's
691 /// UB to call `.get_unchecked_mut(len)`, even if you immediately convert
692 /// to a pointer. And it's UB to call `.get_unchecked_mut(..len + 1)`,
693 /// `.get_unchecked_mut(..=len)`, or similar.
694 ///
695 /// [`get_mut`]: slice::get_mut
696 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
697 ///
698 /// # Examples
699 ///
700 /// ```
701 /// let x = &mut [1, 2, 4];
702 ///
703 /// unsafe {
704 /// let elem = x.get_unchecked_mut(1);
705 /// *elem = 13;
706 /// }
707 /// assert_eq!(x, &[1, 13, 4]);
708 /// ```
709 #[stable(feature = "rust1", since = "1.0.0")]
710 #[inline]
711 #[must_use]
712 pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
713 where
714 I: SliceIndex<Self>,
715 {
716 // SAFETY: the caller must uphold the safety requirements for `get_unchecked_mut`;
717 // the slice is dereferenceable because `self` is a safe reference.
718 // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is.
719 unsafe { &mut *index.get_unchecked_mut(self) }
720 }
721
722 /// Returns a raw pointer to the slice's buffer.
723 ///
724 /// The caller must ensure that the slice outlives the pointer this
725 /// function returns, or else it will end up pointing to garbage.
726 ///
727 /// The caller must also ensure that the memory the pointer (non-transitively) points to
728 /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
729 /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
730 ///
731 /// Modifying the container referenced by this slice may cause its buffer
732 /// to be reallocated, which would also make any pointers to it invalid.
733 ///
734 /// # Examples
735 ///
736 /// ```
737 /// let x = &[1, 2, 4];
738 /// let x_ptr = x.as_ptr();
739 ///
740 /// unsafe {
741 /// for i in 0..x.len() {
742 /// assert_eq!(x.get_unchecked(i), &*x_ptr.add(i));
743 /// }
744 /// }
745 /// ```
746 ///
747 /// [`as_mut_ptr`]: slice::as_mut_ptr
748 #[stable(feature = "rust1", since = "1.0.0")]
749 #[rustc_const_stable(feature = "const_slice_as_ptr", since = "1.32.0")]
750 #[rustc_never_returns_null_ptr]
751 #[inline(always)]
752 #[must_use]
753 pub const fn as_ptr(&self) -> *const T {
754 self as *const [T] as *const T
755 }
756
757 /// Returns an unsafe mutable pointer to the slice's buffer.
758 ///
759 /// The caller must ensure that the slice outlives the pointer this
760 /// function returns, or else it will end up pointing to garbage.
761 ///
762 /// Modifying the container referenced by this slice may cause its buffer
763 /// to be reallocated, which would also make any pointers to it invalid.
764 ///
765 /// # Examples
766 ///
767 /// ```
768 /// let x = &mut [1, 2, 4];
769 /// let x_ptr = x.as_mut_ptr();
770 ///
771 /// unsafe {
772 /// for i in 0..x.len() {
773 /// *x_ptr.add(i) += 2;
774 /// }
775 /// }
776 /// assert_eq!(x, &[3, 4, 6]);
777 /// ```
778 #[stable(feature = "rust1", since = "1.0.0")]
779 #[rustc_const_stable(feature = "const_ptr_offset", since = "1.61.0")]
780 #[rustc_allow_const_fn_unstable(const_mut_refs)]
781 #[rustc_never_returns_null_ptr]
782 #[inline(always)]
783 #[must_use]
784 pub const fn as_mut_ptr(&mut self) -> *mut T {
785 self as *mut [T] as *mut T
786 }
787
788 /// Returns the two raw pointers spanning the slice.
789 ///
790 /// The returned range is half-open, which means that the end pointer
791 /// points *one past* the last element of the slice. This way, an empty
792 /// slice is represented by two equal pointers, and the difference between
793 /// the two pointers represents the size of the slice.
794 ///
795 /// See [`as_ptr`] for warnings on using these pointers. The end pointer
796 /// requires extra caution, as it does not point to a valid element in the
797 /// slice.
798 ///
799 /// This function is useful for interacting with foreign interfaces which
800 /// use two pointers to refer to a range of elements in memory, as is
801 /// common in C++.
802 ///
803 /// It can also be useful to check if a pointer to an element refers to an
804 /// element of this slice:
805 ///
806 /// ```
807 /// let a = [1, 2, 3];
808 /// let x = &a[1] as *const _;
809 /// let y = &5 as *const _;
810 ///
811 /// assert!(a.as_ptr_range().contains(&x));
812 /// assert!(!a.as_ptr_range().contains(&y));
813 /// ```
814 ///
815 /// [`as_ptr`]: slice::as_ptr
816 #[stable(feature = "slice_ptr_range", since = "1.48.0")]
817 #[rustc_const_stable(feature = "const_ptr_offset", since = "1.61.0")]
818 #[inline]
819 #[must_use]
820 pub const fn as_ptr_range(&self) -> Range<*const T> {
821 let start = self.as_ptr();
822 // SAFETY: The `add` here is safe, because:
823 //
824 // - Both pointers are part of the same object, as pointing directly
825 // past the object also counts.
826 //
827 // - The size of the slice is never larger than isize::MAX bytes, as
828 // noted here:
829 // - https://github.com/rust-lang/unsafe-code-guidelines/issues/102#issuecomment-473340447
830 // - https://doc.rust-lang.org/reference/behavior-considered-undefined.html
831 // - https://doc.rust-lang.org/core/slice/fn.from_raw_parts.html#safety
832 // (This doesn't seem normative yet, but the very same assumption is
833 // made in many places, including the Index implementation of slices.)
834 //
835 // - There is no wrapping around involved, as slices do not wrap past
836 // the end of the address space.
837 //
838 // See the documentation of pointer::add.
839 let end = unsafe { start.add(self.len()) };
840 start..end
841 }
842
843 /// Returns the two unsafe mutable pointers spanning the slice.
844 ///
845 /// The returned range is half-open, which means that the end pointer
846 /// points *one past* the last element of the slice. This way, an empty
847 /// slice is represented by two equal pointers, and the difference between
848 /// the two pointers represents the size of the slice.
849 ///
850 /// See [`as_mut_ptr`] for warnings on using these pointers. The end
851 /// pointer requires extra caution, as it does not point to a valid element
852 /// in the slice.
853 ///
854 /// This function is useful for interacting with foreign interfaces which
855 /// use two pointers to refer to a range of elements in memory, as is
856 /// common in C++.
857 ///
858 /// [`as_mut_ptr`]: slice::as_mut_ptr
859 #[stable(feature = "slice_ptr_range", since = "1.48.0")]
860 #[rustc_const_stable(feature = "const_ptr_offset", since = "1.61.0")]
861 #[rustc_allow_const_fn_unstable(const_mut_refs)]
862 #[inline]
863 #[must_use]
864 pub const fn as_mut_ptr_range(&mut self) -> Range<*mut T> {
865 let start = self.as_mut_ptr();
866 // SAFETY: See as_ptr_range() above for why `add` here is safe.
867 let end = unsafe { start.add(self.len()) };
868 start..end
869 }
870
871 /// Swaps two elements in the slice.
872 ///
873 /// If `a` equals to `b`, it's guaranteed that elements won't change value.
874 ///
875 /// # Arguments
876 ///
877 /// * a - The index of the first element
878 /// * b - The index of the second element
879 ///
880 /// # Panics
881 ///
882 /// Panics if `a` or `b` are out of bounds.
883 ///
884 /// # Examples
885 ///
886 /// ```
887 /// let mut v = ["a", "b", "c", "d", "e"];
888 /// v.swap(2, 4);
889 /// assert!(v == ["a", "b", "e", "d", "c"]);
890 /// ```
891 #[stable(feature = "rust1", since = "1.0.0")]
892 #[rustc_const_unstable(feature = "const_swap", issue = "83163")]
893 #[inline]
894 #[track_caller]
895 pub const fn swap(&mut self, a: usize, b: usize) {
896 // FIXME: use swap_unchecked here (https://github.com/rust-lang/rust/pull/88540#issuecomment-944344343)
897 // Can't take two mutable loans from one vector, so instead use raw pointers.
898 let pa = ptr::addr_of_mut!(self[a]);
899 let pb = ptr::addr_of_mut!(self[b]);
900 // SAFETY: `pa` and `pb` have been created from safe mutable references and refer
901 // to elements in the slice and therefore are guaranteed to be valid and aligned.
902 // Note that accessing the elements behind `a` and `b` is checked and will
903 // panic when out of bounds.
904 unsafe {
905 ptr::swap(pa, pb);
906 }
907 }
908
909 /// Swaps two elements in the slice, without doing bounds checking.
910 ///
911 /// For a safe alternative see [`swap`].
912 ///
913 /// # Arguments
914 ///
915 /// * a - The index of the first element
916 /// * b - The index of the second element
917 ///
918 /// # Safety
919 ///
920 /// Calling this method with an out-of-bounds index is *[undefined behavior]*.
921 /// The caller has to ensure that `a < self.len()` and `b < self.len()`.
922 ///
923 /// # Examples
924 ///
925 /// ```
926 /// #![feature(slice_swap_unchecked)]
927 ///
928 /// let mut v = ["a", "b", "c", "d"];
929 /// // SAFETY: we know that 1 and 3 are both indices of the slice
930 /// unsafe { v.swap_unchecked(1, 3) };
931 /// assert!(v == ["a", "d", "c", "b"]);
932 /// ```
933 ///
934 /// [`swap`]: slice::swap
935 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
936 #[unstable(feature = "slice_swap_unchecked", issue = "88539")]
937 #[rustc_const_unstable(feature = "const_swap", issue = "83163")]
938 pub const unsafe fn swap_unchecked(&mut self, a: usize, b: usize) {
939 debug_assert_nounwind!(
940 a < self.len() && b < self.len(),
941 "slice::swap_unchecked requires that the indices are within the slice",
942 );
943
944 let ptr = self.as_mut_ptr();
945 // SAFETY: caller has to guarantee that `a < self.len()` and `b < self.len()`
946 unsafe {
947 ptr::swap(ptr.add(a), ptr.add(b));
948 }
949 }
950
951 /// Reverses the order of elements in the slice, in place.
952 ///
953 /// # Examples
954 ///
955 /// ```
956 /// let mut v = [1, 2, 3];
957 /// v.reverse();
958 /// assert!(v == [3, 2, 1]);
959 /// ```
960 #[stable(feature = "rust1", since = "1.0.0")]
961 #[inline]
962 pub fn reverse(&mut self) {
963 let half_len = self.len() / 2;
964 let Range { start, end } = self.as_mut_ptr_range();
965
966 // These slices will skip the middle item for an odd length,
967 // since that one doesn't need to move.
968 let (front_half, back_half) =
969 // SAFETY: Both are subparts of the original slice, so the memory
970 // range is valid, and they don't overlap because they're each only
971 // half (or less) of the original slice.
972 unsafe {
973 (
974 slice::from_raw_parts_mut(start, half_len),
975 slice::from_raw_parts_mut(end.sub(half_len), half_len),
976 )
977 };
978
979 // Introducing a function boundary here means that the two halves
980 // get `noalias` markers, allowing better optimization as LLVM
981 // knows that they're disjoint, unlike in the original slice.
982 revswap(front_half, back_half, half_len);
983
984 #[inline]
985 fn revswap<T>(a: &mut [T], b: &mut [T], n: usize) {
986 debug_assert!(a.len() == n);
987 debug_assert!(b.len() == n);
988
989 // Because this function is first compiled in isolation,
990 // this check tells LLVM that the indexing below is
991 // in-bounds. Then after inlining -- once the actual
992 // lengths of the slices are known -- it's removed.
993 let (a, b) = (&mut a[..n], &mut b[..n]);
994
995 let mut i = 0;
996 while i < n {
997 mem::swap(&mut a[i], &mut b[n - 1 - i]);
998 i += 1;
999 }
1000 }
1001 }
1002
1003 /// Returns an iterator over the slice.
1004 ///
1005 /// The iterator yields all items from start to end.
1006 ///
1007 /// # Examples
1008 ///
1009 /// ```
1010 /// let x = &[1, 2, 4];
1011 /// let mut iterator = x.iter();
1012 ///
1013 /// assert_eq!(iterator.next(), Some(&1));
1014 /// assert_eq!(iterator.next(), Some(&2));
1015 /// assert_eq!(iterator.next(), Some(&4));
1016 /// assert_eq!(iterator.next(), None);
1017 /// ```
1018 #[stable(feature = "rust1", since = "1.0.0")]
1019 #[inline]
1020 pub fn iter(&self) -> Iter<'_, T> {
1021 Iter::new(self)
1022 }
1023
1024 /// Returns an iterator that allows modifying each value.
1025 ///
1026 /// The iterator yields all items from start to end.
1027 ///
1028 /// # Examples
1029 ///
1030 /// ```
1031 /// let x = &mut [1, 2, 4];
1032 /// for elem in x.iter_mut() {
1033 /// *elem += 2;
1034 /// }
1035 /// assert_eq!(x, &[3, 4, 6]);
1036 /// ```
1037 #[stable(feature = "rust1", since = "1.0.0")]
1038 #[inline]
1039 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
1040 IterMut::new(self)
1041 }
1042
1043 /// Returns an iterator over all contiguous windows of length
1044 /// `size`. The windows overlap. If the slice is shorter than
1045 /// `size`, the iterator returns no values.
1046 ///
1047 /// # Panics
1048 ///
1049 /// Panics if `size` is 0.
1050 ///
1051 /// # Examples
1052 ///
1053 /// ```
1054 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1055 /// let mut iter = slice.windows(3);
1056 /// assert_eq!(iter.next().unwrap(), &['l', 'o', 'r']);
1057 /// assert_eq!(iter.next().unwrap(), &['o', 'r', 'e']);
1058 /// assert_eq!(iter.next().unwrap(), &['r', 'e', 'm']);
1059 /// assert!(iter.next().is_none());
1060 /// ```
1061 ///
1062 /// If the slice is shorter than `size`:
1063 ///
1064 /// ```
1065 /// let slice = ['f', 'o', 'o'];
1066 /// let mut iter = slice.windows(4);
1067 /// assert!(iter.next().is_none());
1068 /// ```
1069 ///
1070 /// There's no `windows_mut`, as that existing would let safe code violate the
1071 /// "only one `&mut` at a time to the same thing" rule. However, you can sometimes
1072 /// use [`Cell::as_slice_of_cells`](crate::cell::Cell::as_slice_of_cells) in
1073 /// conjunction with `windows` to accomplish something similar:
1074 /// ```
1075 /// use std::cell::Cell;
1076 ///
1077 /// let mut array = ['R', 'u', 's', 't', ' ', '2', '0', '1', '5'];
1078 /// let slice = &mut array[..];
1079 /// let slice_of_cells: &[Cell<char>] = Cell::from_mut(slice).as_slice_of_cells();
1080 /// for w in slice_of_cells.windows(3) {
1081 /// Cell::swap(&w[0], &w[2]);
1082 /// }
1083 /// assert_eq!(array, ['s', 't', ' ', '2', '0', '1', '5', 'u', 'R']);
1084 /// ```
1085 #[stable(feature = "rust1", since = "1.0.0")]
1086 #[inline]
1087 #[track_caller]
1088 pub fn windows(&self, size: usize) -> Windows<'_, T> {
1089 let size = NonZeroUsize::new(size).expect("window size must be non-zero");
1090 Windows::new(self, size)
1091 }
1092
1093 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1094 /// beginning of the slice.
1095 ///
1096 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1097 /// slice, then the last chunk will not have length `chunk_size`.
1098 ///
1099 /// See [`chunks_exact`] for a variant of this iterator that returns chunks of always exactly
1100 /// `chunk_size` elements, and [`rchunks`] for the same iterator but starting at the end of the
1101 /// slice.
1102 ///
1103 /// # Panics
1104 ///
1105 /// Panics if `chunk_size` is 0.
1106 ///
1107 /// # Examples
1108 ///
1109 /// ```
1110 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1111 /// let mut iter = slice.chunks(2);
1112 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
1113 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
1114 /// assert_eq!(iter.next().unwrap(), &['m']);
1115 /// assert!(iter.next().is_none());
1116 /// ```
1117 ///
1118 /// [`chunks_exact`]: slice::chunks_exact
1119 /// [`rchunks`]: slice::rchunks
1120 #[stable(feature = "rust1", since = "1.0.0")]
1121 #[inline]
1122 #[track_caller]
1123 pub fn chunks(&self, chunk_size: usize) -> Chunks<'_, T> {
1124 assert!(chunk_size != 0, "chunk size must be non-zero");
1125 Chunks::new(self, chunk_size)
1126 }
1127
1128 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1129 /// beginning of the slice.
1130 ///
1131 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1132 /// length of the slice, then the last chunk will not have length `chunk_size`.
1133 ///
1134 /// See [`chunks_exact_mut`] for a variant of this iterator that returns chunks of always
1135 /// exactly `chunk_size` elements, and [`rchunks_mut`] for the same iterator but starting at
1136 /// the end of the slice.
1137 ///
1138 /// # Panics
1139 ///
1140 /// Panics if `chunk_size` is 0.
1141 ///
1142 /// # Examples
1143 ///
1144 /// ```
1145 /// let v = &mut [0, 0, 0, 0, 0];
1146 /// let mut count = 1;
1147 ///
1148 /// for chunk in v.chunks_mut(2) {
1149 /// for elem in chunk.iter_mut() {
1150 /// *elem += count;
1151 /// }
1152 /// count += 1;
1153 /// }
1154 /// assert_eq!(v, &[1, 1, 2, 2, 3]);
1155 /// ```
1156 ///
1157 /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1158 /// [`rchunks_mut`]: slice::rchunks_mut
1159 #[stable(feature = "rust1", since = "1.0.0")]
1160 #[inline]
1161 #[track_caller]
1162 pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T> {
1163 assert!(chunk_size != 0, "chunk size must be non-zero");
1164 ChunksMut::new(self, chunk_size)
1165 }
1166
1167 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1168 /// beginning of the slice.
1169 ///
1170 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1171 /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
1172 /// from the `remainder` function of the iterator.
1173 ///
1174 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1175 /// resulting code better than in the case of [`chunks`].
1176 ///
1177 /// See [`chunks`] for a variant of this iterator that also returns the remainder as a smaller
1178 /// chunk, and [`rchunks_exact`] for the same iterator but starting at the end of the slice.
1179 ///
1180 /// # Panics
1181 ///
1182 /// Panics if `chunk_size` is 0.
1183 ///
1184 /// # Examples
1185 ///
1186 /// ```
1187 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1188 /// let mut iter = slice.chunks_exact(2);
1189 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
1190 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
1191 /// assert!(iter.next().is_none());
1192 /// assert_eq!(iter.remainder(), &['m']);
1193 /// ```
1194 ///
1195 /// [`chunks`]: slice::chunks
1196 /// [`rchunks_exact`]: slice::rchunks_exact
1197 #[stable(feature = "chunks_exact", since = "1.31.0")]
1198 #[inline]
1199 #[track_caller]
1200 pub fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T> {
1201 assert!(chunk_size != 0, "chunk size must be non-zero");
1202 ChunksExact::new(self, chunk_size)
1203 }
1204
1205 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1206 /// beginning of the slice.
1207 ///
1208 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1209 /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
1210 /// retrieved from the `into_remainder` function of the iterator.
1211 ///
1212 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1213 /// resulting code better than in the case of [`chunks_mut`].
1214 ///
1215 /// See [`chunks_mut`] for a variant of this iterator that also returns the remainder as a
1216 /// smaller chunk, and [`rchunks_exact_mut`] for the same iterator but starting at the end of
1217 /// the slice.
1218 ///
1219 /// # Panics
1220 ///
1221 /// Panics if `chunk_size` is 0.
1222 ///
1223 /// # Examples
1224 ///
1225 /// ```
1226 /// let v = &mut [0, 0, 0, 0, 0];
1227 /// let mut count = 1;
1228 ///
1229 /// for chunk in v.chunks_exact_mut(2) {
1230 /// for elem in chunk.iter_mut() {
1231 /// *elem += count;
1232 /// }
1233 /// count += 1;
1234 /// }
1235 /// assert_eq!(v, &[1, 1, 2, 2, 0]);
1236 /// ```
1237 ///
1238 /// [`chunks_mut`]: slice::chunks_mut
1239 /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
1240 #[stable(feature = "chunks_exact", since = "1.31.0")]
1241 #[inline]
1242 #[track_caller]
1243 pub fn chunks_exact_mut(&mut self, chunk_size: usize) -> ChunksExactMut<'_, T> {
1244 assert!(chunk_size != 0, "chunk size must be non-zero");
1245 ChunksExactMut::new(self, chunk_size)
1246 }
1247
1248 /// Splits the slice into a slice of `N`-element arrays,
1249 /// assuming that there's no remainder.
1250 ///
1251 /// # Safety
1252 ///
1253 /// This may only be called when
1254 /// - The slice splits exactly into `N`-element chunks (aka `self.len() % N == 0`).
1255 /// - `N != 0`.
1256 ///
1257 /// # Examples
1258 ///
1259 /// ```
1260 /// #![feature(slice_as_chunks)]
1261 /// let slice: &[char] = &['l', 'o', 'r', 'e', 'm', '!'];
1262 /// let chunks: &[[char; 1]] =
1263 /// // SAFETY: 1-element chunks never have remainder
1264 /// unsafe { slice.as_chunks_unchecked() };
1265 /// assert_eq!(chunks, &[['l'], ['o'], ['r'], ['e'], ['m'], ['!']]);
1266 /// let chunks: &[[char; 3]] =
1267 /// // SAFETY: The slice length (6) is a multiple of 3
1268 /// unsafe { slice.as_chunks_unchecked() };
1269 /// assert_eq!(chunks, &[['l', 'o', 'r'], ['e', 'm', '!']]);
1270 ///
1271 /// // These would be unsound:
1272 /// // let chunks: &[[_; 5]] = slice.as_chunks_unchecked() // The slice length is not a multiple of 5
1273 /// // let chunks: &[[_; 0]] = slice.as_chunks_unchecked() // Zero-length chunks are never allowed
1274 /// ```
1275 #[unstable(feature = "slice_as_chunks", issue = "74985")]
1276 #[inline]
1277 #[must_use]
1278 pub const unsafe fn as_chunks_unchecked<const N: usize>(&self) -> &[[T; N]] {
1279 debug_assert_nounwind!(
1280 N != 0 && self.len() % N == 0,
1281 "slice::as_chunks_unchecked requires `N != 0` and the slice to split exactly into `N`-element chunks",
1282 );
1283 // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length
1284 let new_len = unsafe { exact_div(self.len(), N) };
1285 // SAFETY: We cast a slice of `new_len * N` elements into
1286 // a slice of `new_len` many `N` elements chunks.
1287 unsafe { from_raw_parts(self.as_ptr().cast(), new_len) }
1288 }
1289
1290 /// Splits the slice into a slice of `N`-element arrays,
1291 /// starting at the beginning of the slice,
1292 /// and a remainder slice with length strictly less than `N`.
1293 ///
1294 /// # Panics
1295 ///
1296 /// Panics if `N` is 0. This check will most probably get changed to a compile time
1297 /// error before this method gets stabilized.
1298 ///
1299 /// # Examples
1300 ///
1301 /// ```
1302 /// #![feature(slice_as_chunks)]
1303 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1304 /// let (chunks, remainder) = slice.as_chunks();
1305 /// assert_eq!(chunks, &[['l', 'o'], ['r', 'e']]);
1306 /// assert_eq!(remainder, &['m']);
1307 /// ```
1308 ///
1309 /// If you expect the slice to be an exact multiple, you can combine
1310 /// `let`-`else` with an empty slice pattern:
1311 /// ```
1312 /// #![feature(slice_as_chunks)]
1313 /// let slice = ['R', 'u', 's', 't'];
1314 /// let (chunks, []) = slice.as_chunks::<2>() else {
1315 /// panic!("slice didn't have even length")
1316 /// };
1317 /// assert_eq!(chunks, &[['R', 'u'], ['s', 't']]);
1318 /// ```
1319 #[unstable(feature = "slice_as_chunks", issue = "74985")]
1320 #[inline]
1321 #[track_caller]
1322 #[must_use]
1323 pub const fn as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]) {
1324 assert!(N != 0, "chunk size must be non-zero");
1325 let len = self.len() / N;
1326 let (multiple_of_n, remainder) = self.split_at(len * N);
1327 // SAFETY: We already panicked for zero, and ensured by construction
1328 // that the length of the subslice is a multiple of N.
1329 let array_slice = unsafe { multiple_of_n.as_chunks_unchecked() };
1330 (array_slice, remainder)
1331 }
1332
1333 /// Splits the slice into a slice of `N`-element arrays,
1334 /// starting at the end of the slice,
1335 /// and a remainder slice with length strictly less than `N`.
1336 ///
1337 /// # Panics
1338 ///
1339 /// Panics if `N` is 0. This check will most probably get changed to a compile time
1340 /// error before this method gets stabilized.
1341 ///
1342 /// # Examples
1343 ///
1344 /// ```
1345 /// #![feature(slice_as_chunks)]
1346 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1347 /// let (remainder, chunks) = slice.as_rchunks();
1348 /// assert_eq!(remainder, &['l']);
1349 /// assert_eq!(chunks, &[['o', 'r'], ['e', 'm']]);
1350 /// ```
1351 #[unstable(feature = "slice_as_chunks", issue = "74985")]
1352 #[inline]
1353 #[track_caller]
1354 #[must_use]
1355 pub const fn as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]) {
1356 assert!(N != 0, "chunk size must be non-zero");
1357 let len = self.len() / N;
1358 let (remainder, multiple_of_n) = self.split_at(self.len() - len * N);
1359 // SAFETY: We already panicked for zero, and ensured by construction
1360 // that the length of the subslice is a multiple of N.
1361 let array_slice = unsafe { multiple_of_n.as_chunks_unchecked() };
1362 (remainder, array_slice)
1363 }
1364
1365 /// Returns an iterator over `N` elements of the slice at a time, starting at the
1366 /// beginning of the slice.
1367 ///
1368 /// The chunks are array references and do not overlap. If `N` does not divide the
1369 /// length of the slice, then the last up to `N-1` elements will be omitted and can be
1370 /// retrieved from the `remainder` function of the iterator.
1371 ///
1372 /// This method is the const generic equivalent of [`chunks_exact`].
1373 ///
1374 /// # Panics
1375 ///
1376 /// Panics if `N` is 0. This check will most probably get changed to a compile time
1377 /// error before this method gets stabilized.
1378 ///
1379 /// # Examples
1380 ///
1381 /// ```
1382 /// #![feature(array_chunks)]
1383 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1384 /// let mut iter = slice.array_chunks();
1385 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
1386 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
1387 /// assert!(iter.next().is_none());
1388 /// assert_eq!(iter.remainder(), &['m']);
1389 /// ```
1390 ///
1391 /// [`chunks_exact`]: slice::chunks_exact
1392 #[unstable(feature = "array_chunks", issue = "74985")]
1393 #[inline]
1394 #[track_caller]
1395 pub fn array_chunks<const N: usize>(&self) -> ArrayChunks<'_, T, N> {
1396 assert!(N != 0, "chunk size must be non-zero");
1397 ArrayChunks::new(self)
1398 }
1399
1400 /// Splits the slice into a slice of `N`-element arrays,
1401 /// assuming that there's no remainder.
1402 ///
1403 /// # Safety
1404 ///
1405 /// This may only be called when
1406 /// - The slice splits exactly into `N`-element chunks (aka `self.len() % N == 0`).
1407 /// - `N != 0`.
1408 ///
1409 /// # Examples
1410 ///
1411 /// ```
1412 /// #![feature(slice_as_chunks)]
1413 /// let slice: &mut [char] = &mut ['l', 'o', 'r', 'e', 'm', '!'];
1414 /// let chunks: &mut [[char; 1]] =
1415 /// // SAFETY: 1-element chunks never have remainder
1416 /// unsafe { slice.as_chunks_unchecked_mut() };
1417 /// chunks[0] = ['L'];
1418 /// assert_eq!(chunks, &[['L'], ['o'], ['r'], ['e'], ['m'], ['!']]);
1419 /// let chunks: &mut [[char; 3]] =
1420 /// // SAFETY: The slice length (6) is a multiple of 3
1421 /// unsafe { slice.as_chunks_unchecked_mut() };
1422 /// chunks[1] = ['a', 'x', '?'];
1423 /// assert_eq!(slice, &['L', 'o', 'r', 'a', 'x', '?']);
1424 ///
1425 /// // These would be unsound:
1426 /// // let chunks: &[[_; 5]] = slice.as_chunks_unchecked_mut() // The slice length is not a multiple of 5
1427 /// // let chunks: &[[_; 0]] = slice.as_chunks_unchecked_mut() // Zero-length chunks are never allowed
1428 /// ```
1429 #[unstable(feature = "slice_as_chunks", issue = "74985")]
1430 #[inline]
1431 #[must_use]
1432 pub const unsafe fn as_chunks_unchecked_mut<const N: usize>(&mut self) -> &mut [[T; N]] {
1433 debug_assert_nounwind!(
1434 N != 0 && self.len() % N == 0,
1435 "slice::as_chunks_unchecked requires `N != 0` and the slice to split exactly into `N`-element chunks",
1436 );
1437 // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length
1438 let new_len = unsafe { exact_div(self.len(), N) };
1439 // SAFETY: We cast a slice of `new_len * N` elements into
1440 // a slice of `new_len` many `N` elements chunks.
1441 unsafe { from_raw_parts_mut(self.as_mut_ptr().cast(), new_len) }
1442 }
1443
1444 /// Splits the slice into a slice of `N`-element arrays,
1445 /// starting at the beginning of the slice,
1446 /// and a remainder slice with length strictly less than `N`.
1447 ///
1448 /// # Panics
1449 ///
1450 /// Panics if `N` is 0. This check will most probably get changed to a compile time
1451 /// error before this method gets stabilized.
1452 ///
1453 /// # Examples
1454 ///
1455 /// ```
1456 /// #![feature(slice_as_chunks)]
1457 /// let v = &mut [0, 0, 0, 0, 0];
1458 /// let mut count = 1;
1459 ///
1460 /// let (chunks, remainder) = v.as_chunks_mut();
1461 /// remainder[0] = 9;
1462 /// for chunk in chunks {
1463 /// *chunk = [count; 2];
1464 /// count += 1;
1465 /// }
1466 /// assert_eq!(v, &[1, 1, 2, 2, 9]);
1467 /// ```
1468 #[unstable(feature = "slice_as_chunks", issue = "74985")]
1469 #[inline]
1470 #[track_caller]
1471 #[must_use]
1472 pub const fn as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]) {
1473 assert!(N != 0, "chunk size must be non-zero");
1474 let len = self.len() / N;
1475 let (multiple_of_n, remainder) = self.split_at_mut(len * N);
1476 // SAFETY: We already panicked for zero, and ensured by construction
1477 // that the length of the subslice is a multiple of N.
1478 let array_slice = unsafe { multiple_of_n.as_chunks_unchecked_mut() };
1479 (array_slice, remainder)
1480 }
1481
1482 /// Splits the slice into a slice of `N`-element arrays,
1483 /// starting at the end of the slice,
1484 /// and a remainder slice with length strictly less than `N`.
1485 ///
1486 /// # Panics
1487 ///
1488 /// Panics if `N` is 0. This check will most probably get changed to a compile time
1489 /// error before this method gets stabilized.
1490 ///
1491 /// # Examples
1492 ///
1493 /// ```
1494 /// #![feature(slice_as_chunks)]
1495 /// let v = &mut [0, 0, 0, 0, 0];
1496 /// let mut count = 1;
1497 ///
1498 /// let (remainder, chunks) = v.as_rchunks_mut();
1499 /// remainder[0] = 9;
1500 /// for chunk in chunks {
1501 /// *chunk = [count; 2];
1502 /// count += 1;
1503 /// }
1504 /// assert_eq!(v, &[9, 1, 1, 2, 2]);
1505 /// ```
1506 #[unstable(feature = "slice_as_chunks", issue = "74985")]
1507 #[inline]
1508 #[track_caller]
1509 #[must_use]
1510 pub const fn as_rchunks_mut<const N: usize>(&mut self) -> (&mut [T], &mut [[T; N]]) {
1511 assert!(N != 0, "chunk size must be non-zero");
1512 let len = self.len() / N;
1513 let (remainder, multiple_of_n) = self.split_at_mut(self.len() - len * N);
1514 // SAFETY: We already panicked for zero, and ensured by construction
1515 // that the length of the subslice is a multiple of N.
1516 let array_slice = unsafe { multiple_of_n.as_chunks_unchecked_mut() };
1517 (remainder, array_slice)
1518 }
1519
1520 /// Returns an iterator over `N` elements of the slice at a time, starting at the
1521 /// beginning of the slice.
1522 ///
1523 /// The chunks are mutable array references and do not overlap. If `N` does not divide
1524 /// the length of the slice, then the last up to `N-1` elements will be omitted and
1525 /// can be retrieved from the `into_remainder` function of the iterator.
1526 ///
1527 /// This method is the const generic equivalent of [`chunks_exact_mut`].
1528 ///
1529 /// # Panics
1530 ///
1531 /// Panics if `N` is 0. This check will most probably get changed to a compile time
1532 /// error before this method gets stabilized.
1533 ///
1534 /// # Examples
1535 ///
1536 /// ```
1537 /// #![feature(array_chunks)]
1538 /// let v = &mut [0, 0, 0, 0, 0];
1539 /// let mut count = 1;
1540 ///
1541 /// for chunk in v.array_chunks_mut() {
1542 /// *chunk = [count; 2];
1543 /// count += 1;
1544 /// }
1545 /// assert_eq!(v, &[1, 1, 2, 2, 0]);
1546 /// ```
1547 ///
1548 /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1549 #[unstable(feature = "array_chunks", issue = "74985")]
1550 #[inline]
1551 #[track_caller]
1552 pub fn array_chunks_mut<const N: usize>(&mut self) -> ArrayChunksMut<'_, T, N> {
1553 assert!(N != 0, "chunk size must be non-zero");
1554 ArrayChunksMut::new(self)
1555 }
1556
1557 /// Returns an iterator over overlapping windows of `N` elements of a slice,
1558 /// starting at the beginning of the slice.
1559 ///
1560 /// This is the const generic equivalent of [`windows`].
1561 ///
1562 /// If `N` is greater than the size of the slice, it will return no windows.
1563 ///
1564 /// # Panics
1565 ///
1566 /// Panics if `N` is 0. This check will most probably get changed to a compile time
1567 /// error before this method gets stabilized.
1568 ///
1569 /// # Examples
1570 ///
1571 /// ```
1572 /// #![feature(array_windows)]
1573 /// let slice = [0, 1, 2, 3];
1574 /// let mut iter = slice.array_windows();
1575 /// assert_eq!(iter.next().unwrap(), &[0, 1]);
1576 /// assert_eq!(iter.next().unwrap(), &[1, 2]);
1577 /// assert_eq!(iter.next().unwrap(), &[2, 3]);
1578 /// assert!(iter.next().is_none());
1579 /// ```
1580 ///
1581 /// [`windows`]: slice::windows
1582 #[unstable(feature = "array_windows", issue = "75027")]
1583 #[inline]
1584 #[track_caller]
1585 pub fn array_windows<const N: usize>(&self) -> ArrayWindows<'_, T, N> {
1586 assert!(N != 0, "window size must be non-zero");
1587 ArrayWindows::new(self)
1588 }
1589
1590 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1591 /// of the slice.
1592 ///
1593 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1594 /// slice, then the last chunk will not have length `chunk_size`.
1595 ///
1596 /// See [`rchunks_exact`] for a variant of this iterator that returns chunks of always exactly
1597 /// `chunk_size` elements, and [`chunks`] for the same iterator but starting at the beginning
1598 /// of the slice.
1599 ///
1600 /// # Panics
1601 ///
1602 /// Panics if `chunk_size` is 0.
1603 ///
1604 /// # Examples
1605 ///
1606 /// ```
1607 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1608 /// let mut iter = slice.rchunks(2);
1609 /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
1610 /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
1611 /// assert_eq!(iter.next().unwrap(), &['l']);
1612 /// assert!(iter.next().is_none());
1613 /// ```
1614 ///
1615 /// [`rchunks_exact`]: slice::rchunks_exact
1616 /// [`chunks`]: slice::chunks
1617 #[stable(feature = "rchunks", since = "1.31.0")]
1618 #[inline]
1619 #[track_caller]
1620 pub fn rchunks(&self, chunk_size: usize) -> RChunks<'_, T> {
1621 assert!(chunk_size != 0, "chunk size must be non-zero");
1622 RChunks::new(self, chunk_size)
1623 }
1624
1625 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1626 /// of the slice.
1627 ///
1628 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1629 /// length of the slice, then the last chunk will not have length `chunk_size`.
1630 ///
1631 /// See [`rchunks_exact_mut`] for a variant of this iterator that returns chunks of always
1632 /// exactly `chunk_size` elements, and [`chunks_mut`] for the same iterator but starting at the
1633 /// beginning of the slice.
1634 ///
1635 /// # Panics
1636 ///
1637 /// Panics if `chunk_size` is 0.
1638 ///
1639 /// # Examples
1640 ///
1641 /// ```
1642 /// let v = &mut [0, 0, 0, 0, 0];
1643 /// let mut count = 1;
1644 ///
1645 /// for chunk in v.rchunks_mut(2) {
1646 /// for elem in chunk.iter_mut() {
1647 /// *elem += count;
1648 /// }
1649 /// count += 1;
1650 /// }
1651 /// assert_eq!(v, &[3, 2, 2, 1, 1]);
1652 /// ```
1653 ///
1654 /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
1655 /// [`chunks_mut`]: slice::chunks_mut
1656 #[stable(feature = "rchunks", since = "1.31.0")]
1657 #[inline]
1658 #[track_caller]
1659 pub fn rchunks_mut(&mut self, chunk_size: usize) -> RChunksMut<'_, T> {
1660 assert!(chunk_size != 0, "chunk size must be non-zero");
1661 RChunksMut::new(self, chunk_size)
1662 }
1663
1664 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1665 /// end of the slice.
1666 ///
1667 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1668 /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
1669 /// from the `remainder` function of the iterator.
1670 ///
1671 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1672 /// resulting code better than in the case of [`rchunks`].
1673 ///
1674 /// See [`rchunks`] for a variant of this iterator that also returns the remainder as a smaller
1675 /// chunk, and [`chunks_exact`] for the same iterator but starting at the beginning of the
1676 /// slice.
1677 ///
1678 /// # Panics
1679 ///
1680 /// Panics if `chunk_size` is 0.
1681 ///
1682 /// # Examples
1683 ///
1684 /// ```
1685 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1686 /// let mut iter = slice.rchunks_exact(2);
1687 /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
1688 /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
1689 /// assert!(iter.next().is_none());
1690 /// assert_eq!(iter.remainder(), &['l']);
1691 /// ```
1692 ///
1693 /// [`chunks`]: slice::chunks
1694 /// [`rchunks`]: slice::rchunks
1695 /// [`chunks_exact`]: slice::chunks_exact
1696 #[stable(feature = "rchunks", since = "1.31.0")]
1697 #[inline]
1698 #[track_caller]
1699 pub fn rchunks_exact(&self, chunk_size: usize) -> RChunksExact<'_, T> {
1700 assert!(chunk_size != 0, "chunk size must be non-zero");
1701 RChunksExact::new(self, chunk_size)
1702 }
1703
1704 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1705 /// of the slice.
1706 ///
1707 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1708 /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
1709 /// retrieved from the `into_remainder` function of the iterator.
1710 ///
1711 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1712 /// resulting code better than in the case of [`chunks_mut`].
1713 ///
1714 /// See [`rchunks_mut`] for a variant of this iterator that also returns the remainder as a
1715 /// smaller chunk, and [`chunks_exact_mut`] for the same iterator but starting at the beginning
1716 /// of the slice.
1717 ///
1718 /// # Panics
1719 ///
1720 /// Panics if `chunk_size` is 0.
1721 ///
1722 /// # Examples
1723 ///
1724 /// ```
1725 /// let v = &mut [0, 0, 0, 0, 0];
1726 /// let mut count = 1;
1727 ///
1728 /// for chunk in v.rchunks_exact_mut(2) {
1729 /// for elem in chunk.iter_mut() {
1730 /// *elem += count;
1731 /// }
1732 /// count += 1;
1733 /// }
1734 /// assert_eq!(v, &[0, 2, 2, 1, 1]);
1735 /// ```
1736 ///
1737 /// [`chunks_mut`]: slice::chunks_mut
1738 /// [`rchunks_mut`]: slice::rchunks_mut
1739 /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1740 #[stable(feature = "rchunks", since = "1.31.0")]
1741 #[inline]
1742 #[track_caller]
1743 pub fn rchunks_exact_mut(&mut self, chunk_size: usize) -> RChunksExactMut<'_, T> {
1744 assert!(chunk_size != 0, "chunk size must be non-zero");
1745 RChunksExactMut::new(self, chunk_size)
1746 }
1747
1748 /// Returns an iterator over the slice producing non-overlapping runs
1749 /// of elements using the predicate to separate them.
1750 ///
1751 /// The predicate is called for every pair of consecutive elements,
1752 /// meaning that it is called on `slice[0]` and `slice[1]`,
1753 /// followed by `slice[1]` and `slice[2]`, and so on.
1754 ///
1755 /// # Examples
1756 ///
1757 /// ```
1758 /// let slice = &[1, 1, 1, 3, 3, 2, 2, 2];
1759 ///
1760 /// let mut iter = slice.chunk_by(|a, b| a == b);
1761 ///
1762 /// assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
1763 /// assert_eq!(iter.next(), Some(&[3, 3][..]));
1764 /// assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
1765 /// assert_eq!(iter.next(), None);
1766 /// ```
1767 ///
1768 /// This method can be used to extract the sorted subslices:
1769 ///
1770 /// ```
1771 /// let slice = &[1, 1, 2, 3, 2, 3, 2, 3, 4];
1772 ///
1773 /// let mut iter = slice.chunk_by(|a, b| a <= b);
1774 ///
1775 /// assert_eq!(iter.next(), Some(&[1, 1, 2, 3][..]));
1776 /// assert_eq!(iter.next(), Some(&[2, 3][..]));
1777 /// assert_eq!(iter.next(), Some(&[2, 3, 4][..]));
1778 /// assert_eq!(iter.next(), None);
1779 /// ```
1780 #[stable(feature = "slice_group_by", since = "1.77.0")]
1781 #[inline]
1782 pub fn chunk_by<F>(&self, pred: F) -> ChunkBy<'_, T, F>
1783 where
1784 F: FnMut(&T, &T) -> bool,
1785 {
1786 ChunkBy::new(self, pred)
1787 }
1788
1789 /// Returns an iterator over the slice producing non-overlapping mutable
1790 /// runs of elements using the predicate to separate them.
1791 ///
1792 /// The predicate is called for every pair of consecutive elements,
1793 /// meaning that it is called on `slice[0]` and `slice[1]`,
1794 /// followed by `slice[1]` and `slice[2]`, and so on.
1795 ///
1796 /// # Examples
1797 ///
1798 /// ```
1799 /// let slice = &mut [1, 1, 1, 3, 3, 2, 2, 2];
1800 ///
1801 /// let mut iter = slice.chunk_by_mut(|a, b| a == b);
1802 ///
1803 /// assert_eq!(iter.next(), Some(&mut [1, 1, 1][..]));
1804 /// assert_eq!(iter.next(), Some(&mut [3, 3][..]));
1805 /// assert_eq!(iter.next(), Some(&mut [2, 2, 2][..]));
1806 /// assert_eq!(iter.next(), None);
1807 /// ```
1808 ///
1809 /// This method can be used to extract the sorted subslices:
1810 ///
1811 /// ```
1812 /// let slice = &mut [1, 1, 2, 3, 2, 3, 2, 3, 4];
1813 ///
1814 /// let mut iter = slice.chunk_by_mut(|a, b| a <= b);
1815 ///
1816 /// assert_eq!(iter.next(), Some(&mut [1, 1, 2, 3][..]));
1817 /// assert_eq!(iter.next(), Some(&mut [2, 3][..]));
1818 /// assert_eq!(iter.next(), Some(&mut [2, 3, 4][..]));
1819 /// assert_eq!(iter.next(), None);
1820 /// ```
1821 #[stable(feature = "slice_group_by", since = "1.77.0")]
1822 #[inline]
1823 pub fn chunk_by_mut<F>(&mut self, pred: F) -> ChunkByMut<'_, T, F>
1824 where
1825 F: FnMut(&T, &T) -> bool,
1826 {
1827 ChunkByMut::new(self, pred)
1828 }
1829
1830 /// Divides one slice into two at an index.
1831 ///
1832 /// The first will contain all indices from `[0, mid)` (excluding
1833 /// the index `mid` itself) and the second will contain all
1834 /// indices from `[mid, len)` (excluding the index `len` itself).
1835 ///
1836 /// # Panics
1837 ///
1838 /// Panics if `mid > len`. For a non-panicking alternative see
1839 /// [`split_at_checked`](slice::split_at_checked).
1840 ///
1841 /// # Examples
1842 ///
1843 /// ```
1844 /// let v = [1, 2, 3, 4, 5, 6];
1845 ///
1846 /// {
1847 /// let (left, right) = v.split_at(0);
1848 /// assert_eq!(left, []);
1849 /// assert_eq!(right, [1, 2, 3, 4, 5, 6]);
1850 /// }
1851 ///
1852 /// {
1853 /// let (left, right) = v.split_at(2);
1854 /// assert_eq!(left, [1, 2]);
1855 /// assert_eq!(right, [3, 4, 5, 6]);
1856 /// }
1857 ///
1858 /// {
1859 /// let (left, right) = v.split_at(6);
1860 /// assert_eq!(left, [1, 2, 3, 4, 5, 6]);
1861 /// assert_eq!(right, []);
1862 /// }
1863 /// ```
1864 #[stable(feature = "rust1", since = "1.0.0")]
1865 #[rustc_const_stable(feature = "const_slice_split_at_not_mut", since = "1.71.0")]
1866 #[rustc_allow_const_fn_unstable(split_at_checked)]
1867 #[inline]
1868 #[track_caller]
1869 #[must_use]
1870 pub const fn split_at(&self, mid: usize) -> (&[T], &[T]) {
1871 match self.split_at_checked(mid) {
1872 Some(pair) => pair,
1873 None => panic!("mid > len"),
1874 }
1875 }
1876
1877 /// Divides one mutable slice into two at an index.
1878 ///
1879 /// The first will contain all indices from `[0, mid)` (excluding
1880 /// the index `mid` itself) and the second will contain all
1881 /// indices from `[mid, len)` (excluding the index `len` itself).
1882 ///
1883 /// # Panics
1884 ///
1885 /// Panics if `mid > len`. For a non-panicking alternative see
1886 /// [`split_at_mut_checked`](slice::split_at_mut_checked).
1887 ///
1888 /// # Examples
1889 ///
1890 /// ```
1891 /// let mut v = [1, 0, 3, 0, 5, 6];
1892 /// let (left, right) = v.split_at_mut(2);
1893 /// assert_eq!(left, [1, 0]);
1894 /// assert_eq!(right, [3, 0, 5, 6]);
1895 /// left[1] = 2;
1896 /// right[1] = 4;
1897 /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
1898 /// ```
1899 #[stable(feature = "rust1", since = "1.0.0")]
1900 #[inline]
1901 #[track_caller]
1902 #[must_use]
1903 #[rustc_const_unstable(feature = "const_slice_split_at_mut", issue = "101804")]
1904 pub const fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
1905 match self.split_at_mut_checked(mid) {
1906 Some(pair) => pair,
1907 None => panic!("mid > len"),
1908 }
1909 }
1910
1911 /// Divides one slice into two at an index, without doing bounds checking.
1912 ///
1913 /// The first will contain all indices from `[0, mid)` (excluding
1914 /// the index `mid` itself) and the second will contain all
1915 /// indices from `[mid, len)` (excluding the index `len` itself).
1916 ///
1917 /// For a safe alternative see [`split_at`].
1918 ///
1919 /// # Safety
1920 ///
1921 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
1922 /// even if the resulting reference is not used. The caller has to ensure that
1923 /// `0 <= mid <= self.len()`.
1924 ///
1925 /// [`split_at`]: slice::split_at
1926 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1927 ///
1928 /// # Examples
1929 ///
1930 /// ```
1931 /// #![feature(slice_split_at_unchecked)]
1932 ///
1933 /// let v = [1, 2, 3, 4, 5, 6];
1934 ///
1935 /// unsafe {
1936 /// let (left, right) = v.split_at_unchecked(0);
1937 /// assert_eq!(left, []);
1938 /// assert_eq!(right, [1, 2, 3, 4, 5, 6]);
1939 /// }
1940 ///
1941 /// unsafe {
1942 /// let (left, right) = v.split_at_unchecked(2);
1943 /// assert_eq!(left, [1, 2]);
1944 /// assert_eq!(right, [3, 4, 5, 6]);
1945 /// }
1946 ///
1947 /// unsafe {
1948 /// let (left, right) = v.split_at_unchecked(6);
1949 /// assert_eq!(left, [1, 2, 3, 4, 5, 6]);
1950 /// assert_eq!(right, []);
1951 /// }
1952 /// ```
1953 #[unstable(feature = "slice_split_at_unchecked", reason = "new API", issue = "76014")]
1954 #[rustc_const_stable(
1955 feature = "const_slice_split_at_unchecked",
1956 since = "1.77.0"
1957 )]
1958 #[inline]
1959 #[must_use]
1960 pub const unsafe fn split_at_unchecked(&self, mid: usize) -> (&[T], &[T]) {
1961 // HACK: the const function `from_raw_parts` is used to make this
1962 // function const; previously the implementation used
1963 // `(self.get_unchecked(..mid), self.get_unchecked(mid..))`
1964
1965 let len = self.len();
1966 let ptr = self.as_ptr();
1967
1968 debug_assert_nounwind!(
1969 mid <= len,
1970 "slice::split_at_unchecked requires the index to be within the slice",
1971 );
1972
1973 // SAFETY: Caller has to check that `0 <= mid <= self.len()`
1974 unsafe { (from_raw_parts(ptr, mid), from_raw_parts(ptr.add(mid), len - mid)) }
1975 }
1976
1977 /// Divides one mutable slice into two at an index, without doing bounds checking.
1978 ///
1979 /// The first will contain all indices from `[0, mid)` (excluding
1980 /// the index `mid` itself) and the second will contain all
1981 /// indices from `[mid, len)` (excluding the index `len` itself).
1982 ///
1983 /// For a safe alternative see [`split_at_mut`].
1984 ///
1985 /// # Safety
1986 ///
1987 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
1988 /// even if the resulting reference is not used. The caller has to ensure that
1989 /// `0 <= mid <= self.len()`.
1990 ///
1991 /// [`split_at_mut`]: slice::split_at_mut
1992 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1993 ///
1994 /// # Examples
1995 ///
1996 /// ```
1997 /// #![feature(slice_split_at_unchecked)]
1998 ///
1999 /// let mut v = [1, 0, 3, 0, 5, 6];
2000 /// // scoped to restrict the lifetime of the borrows
2001 /// unsafe {
2002 /// let (left, right) = v.split_at_mut_unchecked(2);
2003 /// assert_eq!(left, [1, 0]);
2004 /// assert_eq!(right, [3, 0, 5, 6]);
2005 /// left[1] = 2;
2006 /// right[1] = 4;
2007 /// }
2008 /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
2009 /// ```
2010 #[unstable(feature = "slice_split_at_unchecked", reason = "new API", issue = "76014")]
2011 #[rustc_const_unstable(feature = "const_slice_split_at_mut", issue = "101804")]
2012 #[inline]
2013 #[must_use]
2014 pub const unsafe fn split_at_mut_unchecked(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
2015 let len = self.len();
2016 let ptr = self.as_mut_ptr();
2017
2018 debug_assert_nounwind!(
2019 mid <= len,
2020 "slice::split_at_mut_unchecked requires the index to be within the slice",
2021 );
2022
2023 // SAFETY: Caller has to check that `0 <= mid <= self.len()`.
2024 //
2025 // `[ptr; mid]` and `[mid; len]` are not overlapping, so returning a mutable reference
2026 // is fine.
2027 unsafe { (from_raw_parts_mut(ptr, mid), from_raw_parts_mut(ptr.add(mid), len - mid)) }
2028 }
2029
2030 /// Divides one slice into two at an index, returning `None` if the slice is
2031 /// too short.
2032 ///
2033 /// If `mid ≤ len` returns a pair of slices where the first will contain all
2034 /// indices from `[0, mid)` (excluding the index `mid` itself) and the
2035 /// second will contain all indices from `[mid, len)` (excluding the index
2036 /// `len` itself).
2037 ///
2038 /// Otherwise, if `mid > len`, returns `None`.
2039 ///
2040 /// # Examples
2041 ///
2042 /// ```
2043 /// #![feature(split_at_checked)]
2044 ///
2045 /// let v = [1, -2, 3, -4, 5, -6];
2046 ///
2047 /// {
2048 /// let (left, right) = v.split_at_checked(0).unwrap();
2049 /// assert_eq!(left, []);
2050 /// assert_eq!(right, [1, -2, 3, -4, 5, -6]);
2051 /// }
2052 ///
2053 /// {
2054 /// let (left, right) = v.split_at_checked(2).unwrap();
2055 /// assert_eq!(left, [1, -2]);
2056 /// assert_eq!(right, [3, -4, 5, -6]);
2057 /// }
2058 ///
2059 /// {
2060 /// let (left, right) = v.split_at_checked(6).unwrap();
2061 /// assert_eq!(left, [1, -2, 3, -4, 5, -6]);
2062 /// assert_eq!(right, []);
2063 /// }
2064 ///
2065 /// assert_eq!(None, v.split_at_checked(7));
2066 /// ```
2067 #[unstable(feature = "split_at_checked", reason = "new API", issue = "119128")]
2068 #[rustc_const_unstable(feature = "split_at_checked", issue = "119128")]
2069 #[inline]
2070 #[must_use]
2071 pub const fn split_at_checked(&self, mid: usize) -> Option<(&[T], &[T])> {
2072 if mid <= self.len() {
2073 // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which
2074 // fulfills the requirements of `split_at_unchecked`.
2075 Some(unsafe { self.split_at_unchecked(mid) })
2076 } else {
2077 None
2078 }
2079 }
2080
2081 /// Divides one mutable slice into two at an index, returning `None` if the
2082 /// slice is too short.
2083 ///
2084 /// If `mid ≤ len` returns a pair of slices where the first will contain all
2085 /// indices from `[0, mid)` (excluding the index `mid` itself) and the
2086 /// second will contain all indices from `[mid, len)` (excluding the index
2087 /// `len` itself).
2088 ///
2089 /// Otherwise, if `mid > len`, returns `None`.
2090 ///
2091 /// # Examples
2092 ///
2093 /// ```
2094 /// #![feature(split_at_checked)]
2095 ///
2096 /// let mut v = [1, 0, 3, 0, 5, 6];
2097 ///
2098 /// if let Some((left, right)) = v.split_at_mut_checked(2) {
2099 /// assert_eq!(left, [1, 0]);
2100 /// assert_eq!(right, [3, 0, 5, 6]);
2101 /// left[1] = 2;
2102 /// right[1] = 4;
2103 /// }
2104 /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
2105 ///
2106 /// assert_eq!(None, v.split_at_mut_checked(7));
2107 /// ```
2108 #[unstable(feature = "split_at_checked", reason = "new API", issue = "119128")]
2109 #[rustc_const_unstable(feature = "split_at_checked", issue = "119128")]
2110 #[inline]
2111 #[must_use]
2112 pub const fn split_at_mut_checked(&mut self, mid: usize) -> Option<(&mut [T], &mut [T])> {
2113 if mid <= self.len() {
2114 // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which
2115 // fulfills the requirements of `split_at_unchecked`.
2116 Some(unsafe { self.split_at_mut_unchecked(mid) })
2117 } else {
2118 None
2119 }
2120 }
2121
2122 /// Returns an iterator over subslices separated by elements that match
2123 /// `pred`. The matched element is not contained in the subslices.
2124 ///
2125 /// # Examples
2126 ///
2127 /// ```
2128 /// let slice = [10, 40, 33, 20];
2129 /// let mut iter = slice.split(|num| num % 3 == 0);
2130 ///
2131 /// assert_eq!(iter.next().unwrap(), &[10, 40]);
2132 /// assert_eq!(iter.next().unwrap(), &[20]);
2133 /// assert!(iter.next().is_none());
2134 /// ```
2135 ///
2136 /// If the first element is matched, an empty slice will be the first item
2137 /// returned by the iterator. Similarly, if the last element in the slice
2138 /// is matched, an empty slice will be the last item returned by the
2139 /// iterator:
2140 ///
2141 /// ```
2142 /// let slice = [10, 40, 33];
2143 /// let mut iter = slice.split(|num| num % 3 == 0);
2144 ///
2145 /// assert_eq!(iter.next().unwrap(), &[10, 40]);
2146 /// assert_eq!(iter.next().unwrap(), &[]);
2147 /// assert!(iter.next().is_none());
2148 /// ```
2149 ///
2150 /// If two matched elements are directly adjacent, an empty slice will be
2151 /// present between them:
2152 ///
2153 /// ```
2154 /// let slice = [10, 6, 33, 20];
2155 /// let mut iter = slice.split(|num| num % 3 == 0);
2156 ///
2157 /// assert_eq!(iter.next().unwrap(), &[10]);
2158 /// assert_eq!(iter.next().unwrap(), &[]);
2159 /// assert_eq!(iter.next().unwrap(), &[20]);
2160 /// assert!(iter.next().is_none());
2161 /// ```
2162 #[stable(feature = "rust1", since = "1.0.0")]
2163 #[inline]
2164 pub fn split<F>(&self, pred: F) -> Split<'_, T, F>
2165 where
2166 F: FnMut(&T) -> bool,
2167 {
2168 Split::new(self, pred)
2169 }
2170
2171 /// Returns an iterator over mutable subslices separated by elements that
2172 /// match `pred`. The matched element is not contained in the subslices.
2173 ///
2174 /// # Examples
2175 ///
2176 /// ```
2177 /// let mut v = [10, 40, 30, 20, 60, 50];
2178 ///
2179 /// for group in v.split_mut(|num| *num % 3 == 0) {
2180 /// group[0] = 1;
2181 /// }
2182 /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
2183 /// ```
2184 #[stable(feature = "rust1", since = "1.0.0")]
2185 #[inline]
2186 pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<'_, T, F>
2187 where
2188 F: FnMut(&T) -> bool,
2189 {
2190 SplitMut::new(self, pred)
2191 }
2192
2193 /// Returns an iterator over subslices separated by elements that match
2194 /// `pred`. The matched element is contained in the end of the previous
2195 /// subslice as a terminator.
2196 ///
2197 /// # Examples
2198 ///
2199 /// ```
2200 /// let slice = [10, 40, 33, 20];
2201 /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
2202 ///
2203 /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
2204 /// assert_eq!(iter.next().unwrap(), &[20]);
2205 /// assert!(iter.next().is_none());
2206 /// ```
2207 ///
2208 /// If the last element of the slice is matched,
2209 /// that element will be considered the terminator of the preceding slice.
2210 /// That slice will be the last item returned by the iterator.
2211 ///
2212 /// ```
2213 /// let slice = [3, 10, 40, 33];
2214 /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
2215 ///
2216 /// assert_eq!(iter.next().unwrap(), &[3]);
2217 /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
2218 /// assert!(iter.next().is_none());
2219 /// ```
2220 #[stable(feature = "split_inclusive", since = "1.51.0")]
2221 #[inline]
2222 pub fn split_inclusive<F>(&self, pred: F) -> SplitInclusive<'_, T, F>
2223 where
2224 F: FnMut(&T) -> bool,
2225 {
2226 SplitInclusive::new(self, pred)
2227 }
2228
2229 /// Returns an iterator over mutable subslices separated by elements that
2230 /// match `pred`. The matched element is contained in the previous
2231 /// subslice as a terminator.
2232 ///
2233 /// # Examples
2234 ///
2235 /// ```
2236 /// let mut v = [10, 40, 30, 20, 60, 50];
2237 ///
2238 /// for group in v.split_inclusive_mut(|num| *num % 3 == 0) {
2239 /// let terminator_idx = group.len()-1;
2240 /// group[terminator_idx] = 1;
2241 /// }
2242 /// assert_eq!(v, [10, 40, 1, 20, 1, 1]);
2243 /// ```
2244 #[stable(feature = "split_inclusive", since = "1.51.0")]
2245 #[inline]
2246 pub fn split_inclusive_mut<F>(&mut self, pred: F) -> SplitInclusiveMut<'_, T, F>
2247 where
2248 F: FnMut(&T) -> bool,
2249 {
2250 SplitInclusiveMut::new(self, pred)
2251 }
2252
2253 /// Returns an iterator over subslices separated by elements that match
2254 /// `pred`, starting at the end of the slice and working backwards.
2255 /// The matched element is not contained in the subslices.
2256 ///
2257 /// # Examples
2258 ///
2259 /// ```
2260 /// let slice = [11, 22, 33, 0, 44, 55];
2261 /// let mut iter = slice.rsplit(|num| *num == 0);
2262 ///
2263 /// assert_eq!(iter.next().unwrap(), &[44, 55]);
2264 /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
2265 /// assert_eq!(iter.next(), None);
2266 /// ```
2267 ///
2268 /// As with `split()`, if the first or last element is matched, an empty
2269 /// slice will be the first (or last) item returned by the iterator.
2270 ///
2271 /// ```
2272 /// let v = &[0, 1, 1, 2, 3, 5, 8];
2273 /// let mut it = v.rsplit(|n| *n % 2 == 0);
2274 /// assert_eq!(it.next().unwrap(), &[]);
2275 /// assert_eq!(it.next().unwrap(), &[3, 5]);
2276 /// assert_eq!(it.next().unwrap(), &[1, 1]);
2277 /// assert_eq!(it.next().unwrap(), &[]);
2278 /// assert_eq!(it.next(), None);
2279 /// ```
2280 #[stable(feature = "slice_rsplit", since = "1.27.0")]
2281 #[inline]
2282 pub fn rsplit<F>(&self, pred: F) -> RSplit<'_, T, F>
2283 where
2284 F: FnMut(&T) -> bool,
2285 {
2286 RSplit::new(self, pred)
2287 }
2288
2289 /// Returns an iterator over mutable subslices separated by elements that
2290 /// match `pred`, starting at the end of the slice and working
2291 /// backwards. The matched element is not contained in the subslices.
2292 ///
2293 /// # Examples
2294 ///
2295 /// ```
2296 /// let mut v = [100, 400, 300, 200, 600, 500];
2297 ///
2298 /// let mut count = 0;
2299 /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
2300 /// count += 1;
2301 /// group[0] = count;
2302 /// }
2303 /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
2304 /// ```
2305 ///
2306 #[stable(feature = "slice_rsplit", since = "1.27.0")]
2307 #[inline]
2308 pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<'_, T, F>
2309 where
2310 F: FnMut(&T) -> bool,
2311 {
2312 RSplitMut::new(self, pred)
2313 }
2314
2315 /// Returns an iterator over subslices separated by elements that match
2316 /// `pred`, limited to returning at most `n` items. The matched element is
2317 /// not contained in the subslices.
2318 ///
2319 /// The last element returned, if any, will contain the remainder of the
2320 /// slice.
2321 ///
2322 /// # Examples
2323 ///
2324 /// Print the slice split once by numbers divisible by 3 (i.e., `[10, 40]`,
2325 /// `[20, 60, 50]`):
2326 ///
2327 /// ```
2328 /// let v = [10, 40, 30, 20, 60, 50];
2329 ///
2330 /// for group in v.splitn(2, |num| *num % 3 == 0) {
2331 /// println!("{group:?}");
2332 /// }
2333 /// ```
2334 #[stable(feature = "rust1", since = "1.0.0")]
2335 #[inline]
2336 pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<'_, T, F>
2337 where
2338 F: FnMut(&T) -> bool,
2339 {
2340 SplitN::new(self.split(pred), n)
2341 }
2342
2343 /// Returns an iterator over mutable subslices separated by elements that match
2344 /// `pred`, limited to returning at most `n` items. The matched element is
2345 /// not contained in the subslices.
2346 ///
2347 /// The last element returned, if any, will contain the remainder of the
2348 /// slice.
2349 ///
2350 /// # Examples
2351 ///
2352 /// ```
2353 /// let mut v = [10, 40, 30, 20, 60, 50];
2354 ///
2355 /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
2356 /// group[0] = 1;
2357 /// }
2358 /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
2359 /// ```
2360 #[stable(feature = "rust1", since = "1.0.0")]
2361 #[inline]
2362 pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<'_, T, F>
2363 where
2364 F: FnMut(&T) -> bool,
2365 {
2366 SplitNMut::new(self.split_mut(pred), n)
2367 }
2368
2369 /// Returns an iterator over subslices separated by elements that match
2370 /// `pred` limited to returning at most `n` items. This starts at the end of
2371 /// the slice and works backwards. The matched element is not contained in
2372 /// the subslices.
2373 ///
2374 /// The last element returned, if any, will contain the remainder of the
2375 /// slice.
2376 ///
2377 /// # Examples
2378 ///
2379 /// Print the slice split once, starting from the end, by numbers divisible
2380 /// by 3 (i.e., `[50]`, `[10, 40, 30, 20]`):
2381 ///
2382 /// ```
2383 /// let v = [10, 40, 30, 20, 60, 50];
2384 ///
2385 /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
2386 /// println!("{group:?}");
2387 /// }
2388 /// ```
2389 #[stable(feature = "rust1", since = "1.0.0")]
2390 #[inline]
2391 pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<'_, T, F>
2392 where
2393 F: FnMut(&T) -> bool,
2394 {
2395 RSplitN::new(self.rsplit(pred), n)
2396 }
2397
2398 /// Returns an iterator over subslices separated by elements that match
2399 /// `pred` limited to returning at most `n` items. This starts at the end of
2400 /// the slice and works backwards. The matched element is not contained in
2401 /// the subslices.
2402 ///
2403 /// The last element returned, if any, will contain the remainder of the
2404 /// slice.
2405 ///
2406 /// # Examples
2407 ///
2408 /// ```
2409 /// let mut s = [10, 40, 30, 20, 60, 50];
2410 ///
2411 /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
2412 /// group[0] = 1;
2413 /// }
2414 /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
2415 /// ```
2416 #[stable(feature = "rust1", since = "1.0.0")]
2417 #[inline]
2418 pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<'_, T, F>
2419 where
2420 F: FnMut(&T) -> bool,
2421 {
2422 RSplitNMut::new(self.rsplit_mut(pred), n)
2423 }
2424
2425 /// Splits the slice on the first element that matches the specified
2426 /// predicate.
2427 ///
2428 /// If any matching elements are present in the slice, returns the prefix
2429 /// before the match and suffix after. The matching element itself is not
2430 /// included. If no elements match, returns `None`.
2431 ///
2432 /// # Examples
2433 ///
2434 /// ```
2435 /// #![feature(slice_split_once)]
2436 /// let s = [1, 2, 3, 2, 4];
2437 /// assert_eq!(s.split_once(|&x| x == 2), Some((
2438 /// &[1][..],
2439 /// &[3, 2, 4][..]
2440 /// )));
2441 /// assert_eq!(s.split_once(|&x| x == 0), None);
2442 /// ```
2443 #[unstable(feature = "slice_split_once", reason = "newly added", issue = "112811")]
2444 #[inline]
2445 pub fn split_once<F>(&self, pred: F) -> Option<(&[T], &[T])>
2446 where
2447 F: FnMut(&T) -> bool,
2448 {
2449 let index = self.iter().position(pred)?;
2450 Some((&self[..index], &self[index + 1..]))
2451 }
2452
2453 /// Splits the slice on the last element that matches the specified
2454 /// predicate.
2455 ///
2456 /// If any matching elements are present in the slice, returns the prefix
2457 /// before the match and suffix after. The matching element itself is not
2458 /// included. If no elements match, returns `None`.
2459 ///
2460 /// # Examples
2461 ///
2462 /// ```
2463 /// #![feature(slice_split_once)]
2464 /// let s = [1, 2, 3, 2, 4];
2465 /// assert_eq!(s.rsplit_once(|&x| x == 2), Some((
2466 /// &[1, 2, 3][..],
2467 /// &[4][..]
2468 /// )));
2469 /// assert_eq!(s.rsplit_once(|&x| x == 0), None);
2470 /// ```
2471 #[unstable(feature = "slice_split_once", reason = "newly added", issue = "112811")]
2472 #[inline]
2473 pub fn rsplit_once<F>(&self, pred: F) -> Option<(&[T], &[T])>
2474 where
2475 F: FnMut(&T) -> bool,
2476 {
2477 let index = self.iter().rposition(pred)?;
2478 Some((&self[..index], &self[index + 1..]))
2479 }
2480
2481 /// Returns `true` if the slice contains an element with the given value.
2482 ///
2483 /// This operation is *O*(*n*).
2484 ///
2485 /// Note that if you have a sorted slice, [`binary_search`] may be faster.
2486 ///
2487 /// [`binary_search`]: slice::binary_search
2488 ///
2489 /// # Examples
2490 ///
2491 /// ```
2492 /// let v = [10, 40, 30];
2493 /// assert!(v.contains(&30));
2494 /// assert!(!v.contains(&50));
2495 /// ```
2496 ///
2497 /// If you do not have a `&T`, but some other value that you can compare
2498 /// with one (for example, `String` implements `PartialEq<str>`), you can
2499 /// use `iter().any`:
2500 ///
2501 /// ```
2502 /// let v = [String::from("hello"), String::from("world")]; // slice of `String`
2503 /// assert!(v.iter().any(|e| e == "hello")); // search with `&str`
2504 /// assert!(!v.iter().any(|e| e == "hi"));
2505 /// ```
2506 #[stable(feature = "rust1", since = "1.0.0")]
2507 #[inline]
2508 #[must_use]
2509 pub fn contains(&self, x: &T) -> bool
2510 where
2511 T: PartialEq,
2512 {
2513 cmp::SliceContains::slice_contains(x, self)
2514 }
2515
2516 /// Returns `true` if `needle` is a prefix of the slice.
2517 ///
2518 /// # Examples
2519 ///
2520 /// ```
2521 /// let v = [10, 40, 30];
2522 /// assert!(v.starts_with(&[10]));
2523 /// assert!(v.starts_with(&[10, 40]));
2524 /// assert!(!v.starts_with(&[50]));
2525 /// assert!(!v.starts_with(&[10, 50]));
2526 /// ```
2527 ///
2528 /// Always returns `true` if `needle` is an empty slice:
2529 ///
2530 /// ```
2531 /// let v = &[10, 40, 30];
2532 /// assert!(v.starts_with(&[]));
2533 /// let v: &[u8] = &[];
2534 /// assert!(v.starts_with(&[]));
2535 /// ```
2536 #[stable(feature = "rust1", since = "1.0.0")]
2537 #[must_use]
2538 pub fn starts_with(&self, needle: &[T]) -> bool
2539 where
2540 T: PartialEq,
2541 {
2542 let n = needle.len();
2543 self.len() >= n && needle == &self[..n]
2544 }
2545
2546 /// Returns `true` if `needle` is a suffix of the slice.
2547 ///
2548 /// # Examples
2549 ///
2550 /// ```
2551 /// let v = [10, 40, 30];
2552 /// assert!(v.ends_with(&[30]));
2553 /// assert!(v.ends_with(&[40, 30]));
2554 /// assert!(!v.ends_with(&[50]));
2555 /// assert!(!v.ends_with(&[50, 30]));
2556 /// ```
2557 ///
2558 /// Always returns `true` if `needle` is an empty slice:
2559 ///
2560 /// ```
2561 /// let v = &[10, 40, 30];
2562 /// assert!(v.ends_with(&[]));
2563 /// let v: &[u8] = &[];
2564 /// assert!(v.ends_with(&[]));
2565 /// ```
2566 #[stable(feature = "rust1", since = "1.0.0")]
2567 #[must_use]
2568 pub fn ends_with(&self, needle: &[T]) -> bool
2569 where
2570 T: PartialEq,
2571 {
2572 let (m, n) = (self.len(), needle.len());
2573 m >= n && needle == &self[m - n..]
2574 }
2575
2576 /// Returns a subslice with the prefix removed.
2577 ///
2578 /// If the slice starts with `prefix`, returns the subslice after the prefix, wrapped in `Some`.
2579 /// If `prefix` is empty, simply returns the original slice.
2580 ///
2581 /// If the slice does not start with `prefix`, returns `None`.
2582 ///
2583 /// # Examples
2584 ///
2585 /// ```
2586 /// let v = &[10, 40, 30];
2587 /// assert_eq!(v.strip_prefix(&[10]), Some(&[40, 30][..]));
2588 /// assert_eq!(v.strip_prefix(&[10, 40]), Some(&[30][..]));
2589 /// assert_eq!(v.strip_prefix(&[50]), None);
2590 /// assert_eq!(v.strip_prefix(&[10, 50]), None);
2591 ///
2592 /// let prefix : &str = "he";
2593 /// assert_eq!(b"hello".strip_prefix(prefix.as_bytes()),
2594 /// Some(b"llo".as_ref()));
2595 /// ```
2596 #[must_use = "returns the subslice without modifying the original"]
2597 #[stable(feature = "slice_strip", since = "1.51.0")]
2598 pub fn strip_prefix<P: SlicePattern<Item = T> + ?Sized>(&self, prefix: &P) -> Option<&[T]>
2599 where
2600 T: PartialEq,
2601 {
2602 // This function will need rewriting if and when SlicePattern becomes more sophisticated.
2603 let prefix = prefix.as_slice();
2604 let n = prefix.len();
2605 if n <= self.len() {
2606 let (head, tail) = self.split_at(n);
2607 if head == prefix {
2608 return Some(tail);
2609 }
2610 }
2611 None
2612 }
2613
2614 /// Returns a subslice with the suffix removed.
2615 ///
2616 /// If the slice ends with `suffix`, returns the subslice before the suffix, wrapped in `Some`.
2617 /// If `suffix` is empty, simply returns the original slice.
2618 ///
2619 /// If the slice does not end with `suffix`, returns `None`.
2620 ///
2621 /// # Examples
2622 ///
2623 /// ```
2624 /// let v = &[10, 40, 30];
2625 /// assert_eq!(v.strip_suffix(&[30]), Some(&[10, 40][..]));
2626 /// assert_eq!(v.strip_suffix(&[40, 30]), Some(&[10][..]));
2627 /// assert_eq!(v.strip_suffix(&[50]), None);
2628 /// assert_eq!(v.strip_suffix(&[50, 30]), None);
2629 /// ```
2630 #[must_use = "returns the subslice without modifying the original"]
2631 #[stable(feature = "slice_strip", since = "1.51.0")]
2632 pub fn strip_suffix<P: SlicePattern<Item = T> + ?Sized>(&self, suffix: &P) -> Option<&[T]>
2633 where
2634 T: PartialEq,
2635 {
2636 // This function will need rewriting if and when SlicePattern becomes more sophisticated.
2637 let suffix = suffix.as_slice();
2638 let (len, n) = (self.len(), suffix.len());
2639 if n <= len {
2640 let (head, tail) = self.split_at(len - n);
2641 if tail == suffix {
2642 return Some(head);
2643 }
2644 }
2645 None
2646 }
2647
2648 /// Binary searches this slice for a given element.
2649 /// If the slice is not sorted, the returned result is unspecified and
2650 /// meaningless.
2651 ///
2652 /// If the value is found then [`Result::Ok`] is returned, containing the
2653 /// index of the matching element. If there are multiple matches, then any
2654 /// one of the matches could be returned. The index is chosen
2655 /// deterministically, but is subject to change in future versions of Rust.
2656 /// If the value is not found then [`Result::Err`] is returned, containing
2657 /// the index where a matching element could be inserted while maintaining
2658 /// sorted order.
2659 ///
2660 /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
2661 ///
2662 /// [`binary_search_by`]: slice::binary_search_by
2663 /// [`binary_search_by_key`]: slice::binary_search_by_key
2664 /// [`partition_point`]: slice::partition_point
2665 ///
2666 /// # Examples
2667 ///
2668 /// Looks up a series of four elements. The first is found, with a
2669 /// uniquely determined position; the second and third are not
2670 /// found; the fourth could match any position in `[1, 4]`.
2671 ///
2672 /// ```
2673 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2674 ///
2675 /// assert_eq!(s.binary_search(&13), Ok(9));
2676 /// assert_eq!(s.binary_search(&4), Err(7));
2677 /// assert_eq!(s.binary_search(&100), Err(13));
2678 /// let r = s.binary_search(&1);
2679 /// assert!(match r { Ok(1..=4) => true, _ => false, });
2680 /// ```
2681 ///
2682 /// If you want to find that whole *range* of matching items, rather than
2683 /// an arbitrary matching one, that can be done using [`partition_point`]:
2684 /// ```
2685 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2686 ///
2687 /// let low = s.partition_point(|x| x < &1);
2688 /// assert_eq!(low, 1);
2689 /// let high = s.partition_point(|x| x <= &1);
2690 /// assert_eq!(high, 5);
2691 /// let r = s.binary_search(&1);
2692 /// assert!((low..high).contains(&r.unwrap()));
2693 ///
2694 /// assert!(s[..low].iter().all(|&x| x < 1));
2695 /// assert!(s[low..high].iter().all(|&x| x == 1));
2696 /// assert!(s[high..].iter().all(|&x| x > 1));
2697 ///
2698 /// // For something not found, the "range" of equal items is empty
2699 /// assert_eq!(s.partition_point(|x| x < &11), 9);
2700 /// assert_eq!(s.partition_point(|x| x <= &11), 9);
2701 /// assert_eq!(s.binary_search(&11), Err(9));
2702 /// ```
2703 ///
2704 /// If you want to insert an item to a sorted vector, while maintaining
2705 /// sort order, consider using [`partition_point`]:
2706 ///
2707 /// ```
2708 /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2709 /// let num = 42;
2710 /// let idx = s.partition_point(|&x| x < num);
2711 /// // The above is equivalent to `let idx = s.binary_search(&num).unwrap_or_else(|x| x);`
2712 /// s.insert(idx, num);
2713 /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
2714 /// ```
2715 #[stable(feature = "rust1", since = "1.0.0")]
2716 pub fn binary_search(&self, x: &T) -> Result<usize, usize>
2717 where
2718 T: Ord,
2719 {
2720 self.binary_search_by(|p| p.cmp(x))
2721 }
2722
2723 /// Binary searches this slice with a comparator function.
2724 ///
2725 /// The comparator function should return an order code that indicates
2726 /// whether its argument is `Less`, `Equal` or `Greater` the desired
2727 /// target.
2728 /// If the slice is not sorted or if the comparator function does not
2729 /// implement an order consistent with the sort order of the underlying
2730 /// slice, the returned result is unspecified and meaningless.
2731 ///
2732 /// If the value is found then [`Result::Ok`] is returned, containing the
2733 /// index of the matching element. If there are multiple matches, then any
2734 /// one of the matches could be returned. The index is chosen
2735 /// deterministically, but is subject to change in future versions of Rust.
2736 /// If the value is not found then [`Result::Err`] is returned, containing
2737 /// the index where a matching element could be inserted while maintaining
2738 /// sorted order.
2739 ///
2740 /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
2741 ///
2742 /// [`binary_search`]: slice::binary_search
2743 /// [`binary_search_by_key`]: slice::binary_search_by_key
2744 /// [`partition_point`]: slice::partition_point
2745 ///
2746 /// # Examples
2747 ///
2748 /// Looks up a series of four elements. The first is found, with a
2749 /// uniquely determined position; the second and third are not
2750 /// found; the fourth could match any position in `[1, 4]`.
2751 ///
2752 /// ```
2753 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2754 ///
2755 /// let seek = 13;
2756 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
2757 /// let seek = 4;
2758 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
2759 /// let seek = 100;
2760 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
2761 /// let seek = 1;
2762 /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
2763 /// assert!(match r { Ok(1..=4) => true, _ => false, });
2764 /// ```
2765 #[stable(feature = "rust1", since = "1.0.0")]
2766 #[inline]
2767 pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
2768 where
2769 F: FnMut(&'a T) -> Ordering,
2770 {
2771 // INVARIANTS:
2772 // - 0 <= left <= left + size = right <= self.len()
2773 // - f returns Less for everything in self[..left]
2774 // - f returns Greater for everything in self[right..]
2775 let mut size = self.len();
2776 let mut left = 0;
2777 let mut right = size;
2778 while left < right {
2779 let mid = left + size / 2;
2780
2781 // SAFETY: the while condition means `size` is strictly positive, so
2782 // `size/2 < size`. Thus `left + size/2 < left + size`, which
2783 // coupled with the `left + size <= self.len()` invariant means
2784 // we have `left + size/2 < self.len()`, and this is in-bounds.
2785 let cmp = f(unsafe { self.get_unchecked(mid) });
2786
2787 // This control flow produces conditional moves, which results in
2788 // fewer branches and instructions than if/else or matching on
2789 // cmp::Ordering.
2790 // This is x86 asm for u8: https://rust.godbolt.org/z/698eYffTx.
2791 left = if cmp == Less { mid + 1 } else { left };
2792 right = if cmp == Greater { mid } else { right };
2793 if cmp == Equal {
2794 // SAFETY: same as the `get_unchecked` above
2795 unsafe { hint::assert_unchecked(mid < self.len()) };
2796 return Ok(mid);
2797 }
2798
2799 size = right - left;
2800 }
2801
2802 // SAFETY: directly true from the overall invariant.
2803 // Note that this is `<=`, unlike the assume in the `Ok` path.
2804 unsafe { hint::assert_unchecked(left <= self.len()) };
2805 Err(left)
2806 }
2807
2808 /// Binary searches this slice with a key extraction function.
2809 ///
2810 /// Assumes that the slice is sorted by the key, for instance with
2811 /// [`sort_by_key`] using the same key extraction function.
2812 /// If the slice is not sorted by the key, the returned result is
2813 /// unspecified and meaningless.
2814 ///
2815 /// If the value is found then [`Result::Ok`] is returned, containing the
2816 /// index of the matching element. If there are multiple matches, then any
2817 /// one of the matches could be returned. The index is chosen
2818 /// deterministically, but is subject to change in future versions of Rust.
2819 /// If the value is not found then [`Result::Err`] is returned, containing
2820 /// the index where a matching element could be inserted while maintaining
2821 /// sorted order.
2822 ///
2823 /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
2824 ///
2825 /// [`sort_by_key`]: slice::sort_by_key
2826 /// [`binary_search`]: slice::binary_search
2827 /// [`binary_search_by`]: slice::binary_search_by
2828 /// [`partition_point`]: slice::partition_point
2829 ///
2830 /// # Examples
2831 ///
2832 /// Looks up a series of four elements in a slice of pairs sorted by
2833 /// their second elements. The first is found, with a uniquely
2834 /// determined position; the second and third are not found; the
2835 /// fourth could match any position in `[1, 4]`.
2836 ///
2837 /// ```
2838 /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
2839 /// (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
2840 /// (1, 21), (2, 34), (4, 55)];
2841 ///
2842 /// assert_eq!(s.binary_search_by_key(&13, |&(a, b)| b), Ok(9));
2843 /// assert_eq!(s.binary_search_by_key(&4, |&(a, b)| b), Err(7));
2844 /// assert_eq!(s.binary_search_by_key(&100, |&(a, b)| b), Err(13));
2845 /// let r = s.binary_search_by_key(&1, |&(a, b)| b);
2846 /// assert!(match r { Ok(1..=4) => true, _ => false, });
2847 /// ```
2848 // Lint rustdoc::broken_intra_doc_links is allowed as `slice::sort_by_key` is
2849 // in crate `alloc`, and as such doesn't exists yet when building `core`: #74481.
2850 // This breaks links when slice is displayed in core, but changing it to use relative links
2851 // would break when the item is re-exported. So allow the core links to be broken for now.
2852 #[allow(rustdoc::broken_intra_doc_links)]
2853 #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
2854 #[inline]
2855 pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
2856 where
2857 F: FnMut(&'a T) -> B,
2858 B: Ord,
2859 {
2860 self.binary_search_by(|k| f(k).cmp(b))
2861 }
2862
2863 /// Sorts the slice, but might not preserve the order of equal elements.
2864 ///
2865 /// This sort is unstable (i.e., may reorder equal elements), in-place
2866 /// (i.e., does not allocate), and *O*(*n* \* log(*n*)) worst-case.
2867 ///
2868 /// # Current implementation
2869 ///
2870 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
2871 /// which combines the fast average case of randomized quicksort with the fast worst case of
2872 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
2873 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
2874 /// deterministic behavior.
2875 ///
2876 /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
2877 /// slice consists of several concatenated sorted sequences.
2878 ///
2879 /// # Examples
2880 ///
2881 /// ```
2882 /// let mut v = [-5, 4, 1, -3, 2];
2883 ///
2884 /// v.sort_unstable();
2885 /// assert!(v == [-5, -3, 1, 2, 4]);
2886 /// ```
2887 ///
2888 /// [pdqsort]: https://github.com/orlp/pdqsort
2889 #[stable(feature = "sort_unstable", since = "1.20.0")]
2890 #[inline]
2891 pub fn sort_unstable(&mut self)
2892 where
2893 T: Ord,
2894 {
2895 sort::quicksort(self, T::lt);
2896 }
2897
2898 /// Sorts the slice with a comparator function, but might not preserve the order of equal
2899 /// elements.
2900 ///
2901 /// This sort is unstable (i.e., may reorder equal elements), in-place
2902 /// (i.e., does not allocate), and *O*(*n* \* log(*n*)) worst-case.
2903 ///
2904 /// The comparator function must define a total ordering for the elements in the slice. If
2905 /// the ordering is not total, the order of the elements is unspecified. An order is a
2906 /// total order if it is (for all `a`, `b` and `c`):
2907 ///
2908 /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and
2909 /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
2910 ///
2911 /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use
2912 /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`.
2913 ///
2914 /// ```
2915 /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
2916 /// floats.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());
2917 /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
2918 /// ```
2919 ///
2920 /// # Current implementation
2921 ///
2922 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
2923 /// which combines the fast average case of randomized quicksort with the fast worst case of
2924 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
2925 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
2926 /// deterministic behavior.
2927 ///
2928 /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
2929 /// slice consists of several concatenated sorted sequences.
2930 ///
2931 /// # Examples
2932 ///
2933 /// ```
2934 /// let mut v = [5, 4, 1, 3, 2];
2935 /// v.sort_unstable_by(|a, b| a.cmp(b));
2936 /// assert!(v == [1, 2, 3, 4, 5]);
2937 ///
2938 /// // reverse sorting
2939 /// v.sort_unstable_by(|a, b| b.cmp(a));
2940 /// assert!(v == [5, 4, 3, 2, 1]);
2941 /// ```
2942 ///
2943 /// [pdqsort]: https://github.com/orlp/pdqsort
2944 #[stable(feature = "sort_unstable", since = "1.20.0")]
2945 #[inline]
2946 pub fn sort_unstable_by<F>(&mut self, mut compare: F)
2947 where
2948 F: FnMut(&T, &T) -> Ordering,
2949 {
2950 sort::quicksort(self, |a, b| compare(a, b) == Ordering::Less);
2951 }
2952
2953 /// Sorts the slice with a key extraction function, but might not preserve the order of equal
2954 /// elements.
2955 ///
2956 /// This sort is unstable (i.e., may reorder equal elements), in-place
2957 /// (i.e., does not allocate), and *O*(*m* \* *n* \* log(*n*)) worst-case, where the key function is
2958 /// *O*(*m*).
2959 ///
2960 /// # Current implementation
2961 ///
2962 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
2963 /// which combines the fast average case of randomized quicksort with the fast worst case of
2964 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
2965 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
2966 /// deterministic behavior.
2967 ///
2968 /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key)
2969 /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_cached_key) in
2970 /// cases where the key function is expensive.
2971 ///
2972 /// # Examples
2973 ///
2974 /// ```
2975 /// let mut v = [-5i32, 4, 1, -3, 2];
2976 ///
2977 /// v.sort_unstable_by_key(|k| k.abs());
2978 /// assert!(v == [1, 2, -3, 4, -5]);
2979 /// ```
2980 ///
2981 /// [pdqsort]: https://github.com/orlp/pdqsort
2982 #[stable(feature = "sort_unstable", since = "1.20.0")]
2983 #[inline]
2984 pub fn sort_unstable_by_key<K, F>(&mut self, mut f: F)
2985 where
2986 F: FnMut(&T) -> K,
2987 K: Ord,
2988 {
2989 sort::quicksort(self, |a, b| f(a).lt(&f(b)));
2990 }
2991
2992 /// Reorder the slice such that the element at `index` is at its final sorted position.
2993 ///
2994 /// This reordering has the additional property that any value at position `i < index` will be
2995 /// less than or equal to any value at a position `j > index`. Additionally, this reordering is
2996 /// unstable (i.e. any number of equal elements may end up at position `index`), in-place
2997 /// (i.e. does not allocate), and runs in *O*(*n*) time.
2998 /// This function is also known as "kth element" in other libraries.
2999 ///
3000 /// It returns a triplet of the following from the reordered slice:
3001 /// the subslice prior to `index`, the element at `index`, and the subslice after `index`;
3002 /// accordingly, the values in those two subslices will respectively all be less-than-or-equal-to
3003 /// and greater-than-or-equal-to the value of the element at `index`.
3004 ///
3005 /// # Current implementation
3006 ///
3007 /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also
3008 /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for
3009 /// pivot selection, which guarantees linear runtime for all inputs.
3010 ///
3011 /// [`sort_unstable`]: slice::sort_unstable
3012 ///
3013 /// # Panics
3014 ///
3015 /// Panics when `index >= len()`, meaning it always panics on empty slices.
3016 ///
3017 /// # Examples
3018 ///
3019 /// ```
3020 /// let mut v = [-5i32, 4, 1, -3, 2];
3021 ///
3022 /// // Find the median
3023 /// v.select_nth_unstable(2);
3024 ///
3025 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
3026 /// // about the specified index.
3027 /// assert!(v == [-3, -5, 1, 2, 4] ||
3028 /// v == [-5, -3, 1, 2, 4] ||
3029 /// v == [-3, -5, 1, 4, 2] ||
3030 /// v == [-5, -3, 1, 4, 2]);
3031 /// ```
3032 #[stable(feature = "slice_select_nth_unstable", since = "1.49.0")]
3033 #[inline]
3034 pub fn select_nth_unstable(&mut self, index: usize) -> (&mut [T], &mut T, &mut [T])
3035 where
3036 T: Ord,
3037 {
3038 select::partition_at_index(self, index, T::lt)
3039 }
3040
3041 /// Reorder the slice with a comparator function such that the element at `index` is at its
3042 /// final sorted position.
3043 ///
3044 /// This reordering has the additional property that any value at position `i < index` will be
3045 /// less than or equal to any value at a position `j > index` using the comparator function.
3046 /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
3047 /// position `index`), in-place (i.e. does not allocate), and runs in *O*(*n*) time.
3048 /// This function is also known as "kth element" in other libraries.
3049 ///
3050 /// It returns a triplet of the following from
3051 /// the slice reordered according to the provided comparator function: the subslice prior to
3052 /// `index`, the element at `index`, and the subslice after `index`; accordingly, the values in
3053 /// those two subslices will respectively all be less-than-or-equal-to and greater-than-or-equal-to
3054 /// the value of the element at `index`.
3055 ///
3056 /// # Current implementation
3057 ///
3058 /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also
3059 /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for
3060 /// pivot selection, which guarantees linear runtime for all inputs.
3061 ///
3062 /// [`sort_unstable`]: slice::sort_unstable
3063 ///
3064 /// # Panics
3065 ///
3066 /// Panics when `index >= len()`, meaning it always panics on empty slices.
3067 ///
3068 /// # Examples
3069 ///
3070 /// ```
3071 /// let mut v = [-5i32, 4, 1, -3, 2];
3072 ///
3073 /// // Find the median as if the slice were sorted in descending order.
3074 /// v.select_nth_unstable_by(2, |a, b| b.cmp(a));
3075 ///
3076 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
3077 /// // about the specified index.
3078 /// assert!(v == [2, 4, 1, -5, -3] ||
3079 /// v == [2, 4, 1, -3, -5] ||
3080 /// v == [4, 2, 1, -5, -3] ||
3081 /// v == [4, 2, 1, -3, -5]);
3082 /// ```
3083 #[stable(feature = "slice_select_nth_unstable", since = "1.49.0")]
3084 #[inline]
3085 pub fn select_nth_unstable_by<F>(
3086 &mut self,
3087 index: usize,
3088 mut compare: F,
3089 ) -> (&mut [T], &mut T, &mut [T])
3090 where
3091 F: FnMut(&T, &T) -> Ordering,
3092 {
3093 select::partition_at_index(self, index, |a: &T, b: &T| compare(a, b) == Less)
3094 }
3095
3096 /// Reorder the slice with a key extraction function such that the element at `index` is at its
3097 /// final sorted position.
3098 ///
3099 /// This reordering has the additional property that any value at position `i < index` will be
3100 /// less than or equal to any value at a position `j > index` using the key extraction function.
3101 /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
3102 /// position `index`), in-place (i.e. does not allocate), and runs in *O*(*n*) time.
3103 /// This function is also known as "kth element" in other libraries.
3104 ///
3105 /// It returns a triplet of the following from
3106 /// the slice reordered according to the provided key extraction function: the subslice prior to
3107 /// `index`, the element at `index`, and the subslice after `index`; accordingly, the values in
3108 /// those two subslices will respectively all be less-than-or-equal-to and greater-than-or-equal-to
3109 /// the value of the element at `index`.
3110 ///
3111 /// # Current implementation
3112 ///
3113 /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also
3114 /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for
3115 /// pivot selection, which guarantees linear runtime for all inputs.
3116 ///
3117 /// [`sort_unstable`]: slice::sort_unstable
3118 ///
3119 /// # Panics
3120 ///
3121 /// Panics when `index >= len()`, meaning it always panics on empty slices.
3122 ///
3123 /// # Examples
3124 ///
3125 /// ```
3126 /// let mut v = [-5i32, 4, 1, -3, 2];
3127 ///
3128 /// // Return the median as if the array were sorted according to absolute value.
3129 /// v.select_nth_unstable_by_key(2, |a| a.abs());
3130 ///
3131 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
3132 /// // about the specified index.
3133 /// assert!(v == [1, 2, -3, 4, -5] ||
3134 /// v == [1, 2, -3, -5, 4] ||
3135 /// v == [2, 1, -3, 4, -5] ||
3136 /// v == [2, 1, -3, -5, 4]);
3137 /// ```
3138 #[stable(feature = "slice_select_nth_unstable", since = "1.49.0")]
3139 #[inline]
3140 pub fn select_nth_unstable_by_key<K, F>(
3141 &mut self,
3142 index: usize,
3143 mut f: F,
3144 ) -> (&mut [T], &mut T, &mut [T])
3145 where
3146 F: FnMut(&T) -> K,
3147 K: Ord,
3148 {
3149 select::partition_at_index(self, index, |a: &T, b: &T| f(a).lt(&f(b)))
3150 }
3151
3152 /// Moves all consecutive repeated elements to the end of the slice according to the
3153 /// [`PartialEq`] trait implementation.
3154 ///
3155 /// Returns two slices. The first contains no consecutive repeated elements.
3156 /// The second contains all the duplicates in no specified order.
3157 ///
3158 /// If the slice is sorted, the first returned slice contains no duplicates.
3159 ///
3160 /// # Examples
3161 ///
3162 /// ```
3163 /// #![feature(slice_partition_dedup)]
3164 ///
3165 /// let mut slice = [1, 2, 2, 3, 3, 2, 1, 1];
3166 ///
3167 /// let (dedup, duplicates) = slice.partition_dedup();
3168 ///
3169 /// assert_eq!(dedup, [1, 2, 3, 2, 1]);
3170 /// assert_eq!(duplicates, [2, 3, 1]);
3171 /// ```
3172 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
3173 #[inline]
3174 pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T])
3175 where
3176 T: PartialEq,
3177 {
3178 self.partition_dedup_by(|a, b| a == b)
3179 }
3180
3181 /// Moves all but the first of consecutive elements to the end of the slice satisfying
3182 /// a given equality relation.
3183 ///
3184 /// Returns two slices. The first contains no consecutive repeated elements.
3185 /// The second contains all the duplicates in no specified order.
3186 ///
3187 /// The `same_bucket` function is passed references to two elements from the slice and
3188 /// must determine if the elements compare equal. The elements are passed in opposite order
3189 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is moved
3190 /// at the end of the slice.
3191 ///
3192 /// If the slice is sorted, the first returned slice contains no duplicates.
3193 ///
3194 /// # Examples
3195 ///
3196 /// ```
3197 /// #![feature(slice_partition_dedup)]
3198 ///
3199 /// let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];
3200 ///
3201 /// let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b));
3202 ///
3203 /// assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
3204 /// assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);
3205 /// ```
3206 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
3207 #[inline]
3208 pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T])
3209 where
3210 F: FnMut(&mut T, &mut T) -> bool,
3211 {
3212 // Although we have a mutable reference to `self`, we cannot make
3213 // *arbitrary* changes. The `same_bucket` calls could panic, so we
3214 // must ensure that the slice is in a valid state at all times.
3215 //
3216 // The way that we handle this is by using swaps; we iterate
3217 // over all the elements, swapping as we go so that at the end
3218 // the elements we wish to keep are in the front, and those we
3219 // wish to reject are at the back. We can then split the slice.
3220 // This operation is still `O(n)`.
3221 //
3222 // Example: We start in this state, where `r` represents "next
3223 // read" and `w` represents "next_write".
3224 //
3225 // r
3226 // +---+---+---+---+---+---+
3227 // | 0 | 1 | 1 | 2 | 3 | 3 |
3228 // +---+---+---+---+---+---+
3229 // w
3230 //
3231 // Comparing self[r] against self[w-1], this is not a duplicate, so
3232 // we swap self[r] and self[w] (no effect as r==w) and then increment both
3233 // r and w, leaving us with:
3234 //
3235 // r
3236 // +---+---+---+---+---+---+
3237 // | 0 | 1 | 1 | 2 | 3 | 3 |
3238 // +---+---+---+---+---+---+
3239 // w
3240 //
3241 // Comparing self[r] against self[w-1], this value is a duplicate,
3242 // so we increment `r` but leave everything else unchanged:
3243 //
3244 // r
3245 // +---+---+---+---+---+---+
3246 // | 0 | 1 | 1 | 2 | 3 | 3 |
3247 // +---+---+---+---+---+---+
3248 // w
3249 //
3250 // Comparing self[r] against self[w-1], this is not a duplicate,
3251 // so swap self[r] and self[w] and advance r and w:
3252 //
3253 // r
3254 // +---+---+---+---+---+---+
3255 // | 0 | 1 | 2 | 1 | 3 | 3 |
3256 // +---+---+---+---+---+---+
3257 // w
3258 //
3259 // Not a duplicate, repeat:
3260 //
3261 // r
3262 // +---+---+---+---+---+---+
3263 // | 0 | 1 | 2 | 3 | 1 | 3 |
3264 // +---+---+---+---+---+---+
3265 // w
3266 //
3267 // Duplicate, advance r. End of slice. Split at w.
3268
3269 let len = self.len();
3270 if len <= 1 {
3271 return (self, &mut []);
3272 }
3273
3274 let ptr = self.as_mut_ptr();
3275 let mut next_read: usize = 1;
3276 let mut next_write: usize = 1;
3277
3278 // SAFETY: the `while` condition guarantees `next_read` and `next_write`
3279 // are less than `len`, thus are inside `self`. `prev_ptr_write` points to
3280 // one element before `ptr_write`, but `next_write` starts at 1, so
3281 // `prev_ptr_write` is never less than 0 and is inside the slice.
3282 // This fulfils the requirements for dereferencing `ptr_read`, `prev_ptr_write`
3283 // and `ptr_write`, and for using `ptr.add(next_read)`, `ptr.add(next_write - 1)`
3284 // and `prev_ptr_write.offset(1)`.
3285 //
3286 // `next_write` is also incremented at most once per loop at most meaning
3287 // no element is skipped when it may need to be swapped.
3288 //
3289 // `ptr_read` and `prev_ptr_write` never point to the same element. This
3290 // is required for `&mut *ptr_read`, `&mut *prev_ptr_write` to be safe.
3291 // The explanation is simply that `next_read >= next_write` is always true,
3292 // thus `next_read > next_write - 1` is too.
3293 unsafe {
3294 // Avoid bounds checks by using raw pointers.
3295 while next_read < len {
3296 let ptr_read = ptr.add(next_read);
3297 let prev_ptr_write = ptr.add(next_write - 1);
3298 if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) {
3299 if next_read != next_write {
3300 let ptr_write = prev_ptr_write.add(1);
3301 mem::swap(&mut *ptr_read, &mut *ptr_write);
3302 }
3303 next_write += 1;
3304 }
3305 next_read += 1;
3306 }
3307 }
3308
3309 self.split_at_mut(next_write)
3310 }
3311
3312 /// Moves all but the first of consecutive elements to the end of the slice that resolve
3313 /// to the same key.
3314 ///
3315 /// Returns two slices. The first contains no consecutive repeated elements.
3316 /// The second contains all the duplicates in no specified order.
3317 ///
3318 /// If the slice is sorted, the first returned slice contains no duplicates.
3319 ///
3320 /// # Examples
3321 ///
3322 /// ```
3323 /// #![feature(slice_partition_dedup)]
3324 ///
3325 /// let mut slice = [10, 20, 21, 30, 30, 20, 11, 13];
3326 ///
3327 /// let (dedup, duplicates) = slice.partition_dedup_by_key(|i| *i / 10);
3328 ///
3329 /// assert_eq!(dedup, [10, 20, 30, 20, 11]);
3330 /// assert_eq!(duplicates, [21, 30, 13]);
3331 /// ```
3332 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
3333 #[inline]
3334 pub fn partition_dedup_by_key<K, F>(&mut self, mut key: F) -> (&mut [T], &mut [T])
3335 where
3336 F: FnMut(&mut T) -> K,
3337 K: PartialEq,
3338 {
3339 self.partition_dedup_by(|a, b| key(a) == key(b))
3340 }
3341
3342 /// Rotates the slice in-place such that the first `mid` elements of the
3343 /// slice move to the end while the last `self.len() - mid` elements move to
3344 /// the front. After calling `rotate_left`, the element previously at index
3345 /// `mid` will become the first element in the slice.
3346 ///
3347 /// # Panics
3348 ///
3349 /// This function will panic if `mid` is greater than the length of the
3350 /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op
3351 /// rotation.
3352 ///
3353 /// # Complexity
3354 ///
3355 /// Takes linear (in `self.len()`) time.
3356 ///
3357 /// # Examples
3358 ///
3359 /// ```
3360 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3361 /// a.rotate_left(2);
3362 /// assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
3363 /// ```
3364 ///
3365 /// Rotating a subslice:
3366 ///
3367 /// ```
3368 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3369 /// a[1..5].rotate_left(1);
3370 /// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
3371 /// ```
3372 #[stable(feature = "slice_rotate", since = "1.26.0")]
3373 pub fn rotate_left(&mut self, mid: usize) {
3374 assert!(mid <= self.len());
3375 let k = self.len() - mid;
3376 let p = self.as_mut_ptr();
3377
3378 // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially
3379 // valid for reading and writing, as required by `ptr_rotate`.
3380 unsafe {
3381 rotate::ptr_rotate(mid, p.add(mid), k);
3382 }
3383 }
3384
3385 /// Rotates the slice in-place such that the first `self.len() - k`
3386 /// elements of the slice move to the end while the last `k` elements move
3387 /// to the front. After calling `rotate_right`, the element previously at
3388 /// index `self.len() - k` will become the first element in the slice.
3389 ///
3390 /// # Panics
3391 ///
3392 /// This function will panic if `k` is greater than the length of the
3393 /// slice. Note that `k == self.len()` does _not_ panic and is a no-op
3394 /// rotation.
3395 ///
3396 /// # Complexity
3397 ///
3398 /// Takes linear (in `self.len()`) time.
3399 ///
3400 /// # Examples
3401 ///
3402 /// ```
3403 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3404 /// a.rotate_right(2);
3405 /// assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
3406 /// ```
3407 ///
3408 /// Rotating a subslice:
3409 ///
3410 /// ```
3411 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3412 /// a[1..5].rotate_right(1);
3413 /// assert_eq!(a, ['a', 'e', 'b', 'c', 'd', 'f']);
3414 /// ```
3415 #[stable(feature = "slice_rotate", since = "1.26.0")]
3416 pub fn rotate_right(&mut self, k: usize) {
3417 assert!(k <= self.len());
3418 let mid = self.len() - k;
3419 let p = self.as_mut_ptr();
3420
3421 // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially
3422 // valid for reading and writing, as required by `ptr_rotate`.
3423 unsafe {
3424 rotate::ptr_rotate(mid, p.add(mid), k);
3425 }
3426 }
3427
3428 /// Fills `self` with elements by cloning `value`.
3429 ///
3430 /// # Examples
3431 ///
3432 /// ```
3433 /// let mut buf = vec![0; 10];
3434 /// buf.fill(1);
3435 /// assert_eq!(buf, vec![1; 10]);
3436 /// ```
3437 #[doc(alias = "memset")]
3438 #[stable(feature = "slice_fill", since = "1.50.0")]
3439 pub fn fill(&mut self, value: T)
3440 where
3441 T: Clone,
3442 {
3443 specialize::SpecFill::spec_fill(self, value);
3444 }
3445
3446 /// Fills `self` with elements returned by calling a closure repeatedly.
3447 ///
3448 /// This method uses a closure to create new values. If you'd rather
3449 /// [`Clone`] a given value, use [`fill`]. If you want to use the [`Default`]
3450 /// trait to generate values, you can pass [`Default::default`] as the
3451 /// argument.
3452 ///
3453 /// [`fill`]: slice::fill
3454 ///
3455 /// # Examples
3456 ///
3457 /// ```
3458 /// let mut buf = vec![1; 10];
3459 /// buf.fill_with(Default::default);
3460 /// assert_eq!(buf, vec![0; 10]);
3461 /// ```
3462 #[stable(feature = "slice_fill_with", since = "1.51.0")]
3463 pub fn fill_with<F>(&mut self, mut f: F)
3464 where
3465 F: FnMut() -> T,
3466 {
3467 for el in self {
3468 *el = f();
3469 }
3470 }
3471
3472 /// Copies the elements from `src` into `self`.
3473 ///
3474 /// The length of `src` must be the same as `self`.
3475 ///
3476 /// # Panics
3477 ///
3478 /// This function will panic if the two slices have different lengths.
3479 ///
3480 /// # Examples
3481 ///
3482 /// Cloning two elements from a slice into another:
3483 ///
3484 /// ```
3485 /// let src = [1, 2, 3, 4];
3486 /// let mut dst = [0, 0];
3487 ///
3488 /// // Because the slices have to be the same length,
3489 /// // we slice the source slice from four elements
3490 /// // to two. It will panic if we don't do this.
3491 /// dst.clone_from_slice(&src[2..]);
3492 ///
3493 /// assert_eq!(src, [1, 2, 3, 4]);
3494 /// assert_eq!(dst, [3, 4]);
3495 /// ```
3496 ///
3497 /// Rust enforces that there can only be one mutable reference with no
3498 /// immutable references to a particular piece of data in a particular
3499 /// scope. Because of this, attempting to use `clone_from_slice` on a
3500 /// single slice will result in a compile failure:
3501 ///
3502 /// ```compile_fail
3503 /// let mut slice = [1, 2, 3, 4, 5];
3504 ///
3505 /// slice[..2].clone_from_slice(&slice[3..]); // compile fail!
3506 /// ```
3507 ///
3508 /// To work around this, we can use [`split_at_mut`] to create two distinct
3509 /// sub-slices from a slice:
3510 ///
3511 /// ```
3512 /// let mut slice = [1, 2, 3, 4, 5];
3513 ///
3514 /// {
3515 /// let (left, right) = slice.split_at_mut(2);
3516 /// left.clone_from_slice(&right[1..]);
3517 /// }
3518 ///
3519 /// assert_eq!(slice, [4, 5, 3, 4, 5]);
3520 /// ```
3521 ///
3522 /// [`copy_from_slice`]: slice::copy_from_slice
3523 /// [`split_at_mut`]: slice::split_at_mut
3524 #[stable(feature = "clone_from_slice", since = "1.7.0")]
3525 #[track_caller]
3526 pub fn clone_from_slice(&mut self, src: &[T])
3527 where
3528 T: Clone,
3529 {
3530 self.spec_clone_from(src);
3531 }
3532
3533 /// Copies all elements from `src` into `self`, using a memcpy.
3534 ///
3535 /// The length of `src` must be the same as `self`.
3536 ///
3537 /// If `T` does not implement `Copy`, use [`clone_from_slice`].
3538 ///
3539 /// # Panics
3540 ///
3541 /// This function will panic if the two slices have different lengths.
3542 ///
3543 /// # Examples
3544 ///
3545 /// Copying two elements from a slice into another:
3546 ///
3547 /// ```
3548 /// let src = [1, 2, 3, 4];
3549 /// let mut dst = [0, 0];
3550 ///
3551 /// // Because the slices have to be the same length,
3552 /// // we slice the source slice from four elements
3553 /// // to two. It will panic if we don't do this.
3554 /// dst.copy_from_slice(&src[2..]);
3555 ///
3556 /// assert_eq!(src, [1, 2, 3, 4]);
3557 /// assert_eq!(dst, [3, 4]);
3558 /// ```
3559 ///
3560 /// Rust enforces that there can only be one mutable reference with no
3561 /// immutable references to a particular piece of data in a particular
3562 /// scope. Because of this, attempting to use `copy_from_slice` on a
3563 /// single slice will result in a compile failure:
3564 ///
3565 /// ```compile_fail
3566 /// let mut slice = [1, 2, 3, 4, 5];
3567 ///
3568 /// slice[..2].copy_from_slice(&slice[3..]); // compile fail!
3569 /// ```
3570 ///
3571 /// To work around this, we can use [`split_at_mut`] to create two distinct
3572 /// sub-slices from a slice:
3573 ///
3574 /// ```
3575 /// let mut slice = [1, 2, 3, 4, 5];
3576 ///
3577 /// {
3578 /// let (left, right) = slice.split_at_mut(2);
3579 /// left.copy_from_slice(&right[1..]);
3580 /// }
3581 ///
3582 /// assert_eq!(slice, [4, 5, 3, 4, 5]);
3583 /// ```
3584 ///
3585 /// [`clone_from_slice`]: slice::clone_from_slice
3586 /// [`split_at_mut`]: slice::split_at_mut
3587 #[doc(alias = "memcpy")]
3588 #[stable(feature = "copy_from_slice", since = "1.9.0")]
3589 #[track_caller]
3590 pub fn copy_from_slice(&mut self, src: &[T])
3591 where
3592 T: Copy,
3593 {
3594 // The panic code path was put into a cold function to not bloat the
3595 // call site.
3596 #[inline(never)]
3597 #[cold]
3598 #[track_caller]
3599 fn len_mismatch_fail(dst_len: usize, src_len: usize) -> ! {
3600 panic!(
3601 "source slice length ({}) does not match destination slice length ({})",
3602 src_len, dst_len,
3603 );
3604 }
3605
3606 if self.len() != src.len() {
3607 len_mismatch_fail(self.len(), src.len());
3608 }
3609
3610 // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was
3611 // checked to have the same length. The slices cannot overlap because
3612 // mutable references are exclusive.
3613 unsafe {
3614 ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr(), self.len());
3615 }
3616 }
3617
3618 /// Copies elements from one part of the slice to another part of itself,
3619 /// using a memmove.
3620 ///
3621 /// `src` is the range within `self` to copy from. `dest` is the starting
3622 /// index of the range within `self` to copy to, which will have the same
3623 /// length as `src`. The two ranges may overlap. The ends of the two ranges
3624 /// must be less than or equal to `self.len()`.
3625 ///
3626 /// # Panics
3627 ///
3628 /// This function will panic if either range exceeds the end of the slice,
3629 /// or if the end of `src` is before the start.
3630 ///
3631 /// # Examples
3632 ///
3633 /// Copying four bytes within a slice:
3634 ///
3635 /// ```
3636 /// let mut bytes = *b"Hello, World!";
3637 ///
3638 /// bytes.copy_within(1..5, 8);
3639 ///
3640 /// assert_eq!(&bytes, b"Hello, Wello!");
3641 /// ```
3642 #[stable(feature = "copy_within", since = "1.37.0")]
3643 #[track_caller]
3644 pub fn copy_within<R: RangeBounds<usize>>(&mut self, src: R, dest: usize)
3645 where
3646 T: Copy,
3647 {
3648 let Range { start: src_start, end: src_end } = slice::range(src, ..self.len());
3649 let count = src_end - src_start;
3650 assert!(dest <= self.len() - count, "dest is out of bounds");
3651 // SAFETY: the conditions for `ptr::copy` have all been checked above,
3652 // as have those for `ptr::add`.
3653 unsafe {
3654 // Derive both `src_ptr` and `dest_ptr` from the same loan
3655 let ptr = self.as_mut_ptr();
3656 let src_ptr = ptr.add(src_start);
3657 let dest_ptr = ptr.add(dest);
3658 ptr::copy(src_ptr, dest_ptr, count);
3659 }
3660 }
3661
3662 /// Swaps all elements in `self` with those in `other`.
3663 ///
3664 /// The length of `other` must be the same as `self`.
3665 ///
3666 /// # Panics
3667 ///
3668 /// This function will panic if the two slices have different lengths.
3669 ///
3670 /// # Example
3671 ///
3672 /// Swapping two elements across slices:
3673 ///
3674 /// ```
3675 /// let mut slice1 = [0, 0];
3676 /// let mut slice2 = [1, 2, 3, 4];
3677 ///
3678 /// slice1.swap_with_slice(&mut slice2[2..]);
3679 ///
3680 /// assert_eq!(slice1, [3, 4]);
3681 /// assert_eq!(slice2, [1, 2, 0, 0]);
3682 /// ```
3683 ///
3684 /// Rust enforces that there can only be one mutable reference to a
3685 /// particular piece of data in a particular scope. Because of this,
3686 /// attempting to use `swap_with_slice` on a single slice will result in
3687 /// a compile failure:
3688 ///
3689 /// ```compile_fail
3690 /// let mut slice = [1, 2, 3, 4, 5];
3691 /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail!
3692 /// ```
3693 ///
3694 /// To work around this, we can use [`split_at_mut`] to create two distinct
3695 /// mutable sub-slices from a slice:
3696 ///
3697 /// ```
3698 /// let mut slice = [1, 2, 3, 4, 5];
3699 ///
3700 /// {
3701 /// let (left, right) = slice.split_at_mut(2);
3702 /// left.swap_with_slice(&mut right[1..]);
3703 /// }
3704 ///
3705 /// assert_eq!(slice, [4, 5, 3, 1, 2]);
3706 /// ```
3707 ///
3708 /// [`split_at_mut`]: slice::split_at_mut
3709 #[stable(feature = "swap_with_slice", since = "1.27.0")]
3710 #[track_caller]
3711 pub fn swap_with_slice(&mut self, other: &mut [T]) {
3712 assert!(self.len() == other.len(), "destination and source slices have different lengths");
3713 // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was
3714 // checked to have the same length. The slices cannot overlap because
3715 // mutable references are exclusive.
3716 unsafe {
3717 ptr::swap_nonoverlapping(self.as_mut_ptr(), other.as_mut_ptr(), self.len());
3718 }
3719 }
3720
3721 /// Function to calculate lengths of the middle and trailing slice for `align_to{,_mut}`.
3722 fn align_to_offsets<U>(&self) -> (usize, usize) {
3723 // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
3724 // lowest number of `T`s. And how many `T`s we need for each such "multiple".
3725 //
3726 // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
3727 // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
3728 // place of every 3 Ts in the `rest` slice. A bit more complicated.
3729 //
3730 // Formula to calculate this is:
3731 //
3732 // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
3733 // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
3734 //
3735 // Expanded and simplified:
3736 //
3737 // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
3738 // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
3739 //
3740 // Luckily since all this is constant-evaluated... performance here matters not!
3741 const fn gcd(a: usize, b: usize) -> usize {
3742 if b == 0 { a } else { gcd(b, a % b) }
3743 }
3744
3745 // Explicitly wrap the function call in a const block so it gets
3746 // constant-evaluated even in debug mode.
3747 let gcd: usize = const { gcd(mem::size_of::<T>(), mem::size_of::<U>()) };
3748 let ts: usize = mem::size_of::<U>() / gcd;
3749 let us: usize = mem::size_of::<T>() / gcd;
3750
3751 // Armed with this knowledge, we can find how many `U`s we can fit!
3752 let us_len = self.len() / ts * us;
3753 // And how many `T`s will be in the trailing slice!
3754 let ts_len = self.len() % ts;
3755 (us_len, ts_len)
3756 }
3757
3758 /// Transmute the slice to a slice of another type, ensuring alignment of the types is
3759 /// maintained.
3760 ///
3761 /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
3762 /// slice of a new type, and the suffix slice. How exactly the slice is split up is not
3763 /// specified; the middle part may be smaller than necessary. However, if this fails to return a
3764 /// maximal middle part, that is because code is running in a context where performance does not
3765 /// matter, such as a sanitizer attempting to find alignment bugs. Regular code running
3766 /// in a default (debug or release) execution *will* return a maximal middle part.
3767 ///
3768 /// This method has no purpose when either input element `T` or output element `U` are
3769 /// zero-sized and will return the original slice without splitting anything.
3770 ///
3771 /// # Safety
3772 ///
3773 /// This method is essentially a `transmute` with respect to the elements in the returned
3774 /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
3775 ///
3776 /// # Examples
3777 ///
3778 /// Basic usage:
3779 ///
3780 /// ```
3781 /// unsafe {
3782 /// let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
3783 /// let (prefix, shorts, suffix) = bytes.align_to::<u16>();
3784 /// // less_efficient_algorithm_for_bytes(prefix);
3785 /// // more_efficient_algorithm_for_aligned_shorts(shorts);
3786 /// // less_efficient_algorithm_for_bytes(suffix);
3787 /// }
3788 /// ```
3789 #[stable(feature = "slice_align_to", since = "1.30.0")]
3790 #[must_use]
3791 pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) {
3792 // Note that most of this function will be constant-evaluated,
3793 if U::IS_ZST || T::IS_ZST {
3794 // handle ZSTs specially, which is – don't handle them at all.
3795 return (self, &[], &[]);
3796 }
3797
3798 // First, find at what point do we split between the first and 2nd slice. Easy with
3799 // ptr.align_offset.
3800 let ptr = self.as_ptr();
3801 // SAFETY: See the `align_to_mut` method for the detailed safety comment.
3802 let offset = unsafe { crate::ptr::align_offset(ptr, mem::align_of::<U>()) };
3803 if offset > self.len() {
3804 (self, &[], &[])
3805 } else {
3806 let (left, rest) = self.split_at(offset);
3807 let (us_len, ts_len) = rest.align_to_offsets::<U>();
3808 // Inform Miri that we want to consider the "middle" pointer to be suitably aligned.
3809 #[cfg(miri)]
3810 crate::intrinsics::miri_promise_symbolic_alignment(
3811 rest.as_ptr().cast(),
3812 mem::align_of::<U>(),
3813 );
3814 // SAFETY: now `rest` is definitely aligned, so `from_raw_parts` below is okay,
3815 // since the caller guarantees that we can transmute `T` to `U` safely.
3816 unsafe {
3817 (
3818 left,
3819 from_raw_parts(rest.as_ptr() as *const U, us_len),
3820 from_raw_parts(rest.as_ptr().add(rest.len() - ts_len), ts_len),
3821 )
3822 }
3823 }
3824 }
3825
3826 /// Transmute the mutable slice to a mutable slice of another type, ensuring alignment of the
3827 /// types is maintained.
3828 ///
3829 /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
3830 /// slice of a new type, and the suffix slice. How exactly the slice is split up is not
3831 /// specified; the middle part may be smaller than necessary. However, if this fails to return a
3832 /// maximal middle part, that is because code is running in a context where performance does not
3833 /// matter, such as a sanitizer attempting to find alignment bugs. Regular code running
3834 /// in a default (debug or release) execution *will* return a maximal middle part.
3835 ///
3836 /// This method has no purpose when either input element `T` or output element `U` are
3837 /// zero-sized and will return the original slice without splitting anything.
3838 ///
3839 /// # Safety
3840 ///
3841 /// This method is essentially a `transmute` with respect to the elements in the returned
3842 /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
3843 ///
3844 /// # Examples
3845 ///
3846 /// Basic usage:
3847 ///
3848 /// ```
3849 /// unsafe {
3850 /// let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
3851 /// let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
3852 /// // less_efficient_algorithm_for_bytes(prefix);
3853 /// // more_efficient_algorithm_for_aligned_shorts(shorts);
3854 /// // less_efficient_algorithm_for_bytes(suffix);
3855 /// }
3856 /// ```
3857 #[stable(feature = "slice_align_to", since = "1.30.0")]
3858 #[must_use]
3859 pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) {
3860 // Note that most of this function will be constant-evaluated,
3861 if U::IS_ZST || T::IS_ZST {
3862 // handle ZSTs specially, which is – don't handle them at all.
3863 return (self, &mut [], &mut []);
3864 }
3865
3866 // First, find at what point do we split between the first and 2nd slice. Easy with
3867 // ptr.align_offset.
3868 let ptr = self.as_ptr();
3869 // SAFETY: Here we are ensuring we will use aligned pointers for U for the
3870 // rest of the method. This is done by passing a pointer to &[T] with an
3871 // alignment targeted for U.
3872 // `crate::ptr::align_offset` is called with a correctly aligned and
3873 // valid pointer `ptr` (it comes from a reference to `self`) and with
3874 // a size that is a power of two (since it comes from the alignment for U),
3875 // satisfying its safety constraints.
3876 let offset = unsafe { crate::ptr::align_offset(ptr, mem::align_of::<U>()) };
3877 if offset > self.len() {
3878 (self, &mut [], &mut [])
3879 } else {
3880 let (left, rest) = self.split_at_mut(offset);
3881 let (us_len, ts_len) = rest.align_to_offsets::<U>();
3882 let rest_len = rest.len();
3883 let mut_ptr = rest.as_mut_ptr();
3884 // Inform Miri that we want to consider the "middle" pointer to be suitably aligned.
3885 #[cfg(miri)]
3886 crate::intrinsics::miri_promise_symbolic_alignment(
3887 mut_ptr.cast() as *const (),
3888 mem::align_of::<U>(),
3889 );
3890 // We can't use `rest` again after this, that would invalidate its alias `mut_ptr`!
3891 // SAFETY: see comments for `align_to`.
3892 unsafe {
3893 (
3894 left,
3895 from_raw_parts_mut(mut_ptr as *mut U, us_len),
3896 from_raw_parts_mut(mut_ptr.add(rest_len - ts_len), ts_len),
3897 )
3898 }
3899 }
3900 }
3901
3902 /// Split a slice into a prefix, a middle of aligned SIMD types, and a suffix.
3903 ///
3904 /// This is a safe wrapper around [`slice::align_to`], so has the same weak
3905 /// postconditions as that method. You're only assured that
3906 /// `self.len() == prefix.len() + middle.len() * LANES + suffix.len()`.
3907 ///
3908 /// Notably, all of the following are possible:
3909 /// - `prefix.len() >= LANES`.
3910 /// - `middle.is_empty()` despite `self.len() >= 3 * LANES`.
3911 /// - `suffix.len() >= LANES`.
3912 ///
3913 /// That said, this is a safe method, so if you're only writing safe code,
3914 /// then this can at most cause incorrect logic, not unsoundness.
3915 ///
3916 /// # Panics
3917 ///
3918 /// This will panic if the size of the SIMD type is different from
3919 /// `LANES` times that of the scalar.
3920 ///
3921 /// At the time of writing, the trait restrictions on `Simd<T, LANES>` keeps
3922 /// that from ever happening, as only power-of-two numbers of lanes are
3923 /// supported. It's possible that, in the future, those restrictions might
3924 /// be lifted in a way that would make it possible to see panics from this
3925 /// method for something like `LANES == 3`.
3926 ///
3927 /// # Examples
3928 ///
3929 /// ```
3930 /// #![feature(portable_simd)]
3931 /// use core::simd::prelude::*;
3932 ///
3933 /// let short = &[1, 2, 3];
3934 /// let (prefix, middle, suffix) = short.as_simd::<4>();
3935 /// assert_eq!(middle, []); // Not enough elements for anything in the middle
3936 ///
3937 /// // They might be split in any possible way between prefix and suffix
3938 /// let it = prefix.iter().chain(suffix).copied();
3939 /// assert_eq!(it.collect::<Vec<_>>(), vec![1, 2, 3]);
3940 ///
3941 /// fn basic_simd_sum(x: &[f32]) -> f32 {
3942 /// use std::ops::Add;
3943 /// let (prefix, middle, suffix) = x.as_simd();
3944 /// let sums = f32x4::from_array([
3945 /// prefix.iter().copied().sum(),
3946 /// 0.0,
3947 /// 0.0,
3948 /// suffix.iter().copied().sum(),
3949 /// ]);
3950 /// let sums = middle.iter().copied().fold(sums, f32x4::add);
3951 /// sums.reduce_sum()
3952 /// }
3953 ///
3954 /// let numbers: Vec<f32> = (1..101).map(|x| x as _).collect();
3955 /// assert_eq!(basic_simd_sum(&numbers[1..99]), 4949.0);
3956 /// ```
3957 #[unstable(feature = "portable_simd", issue = "86656")]
3958 #[must_use]
3959 pub fn as_simd<const LANES: usize>(&self) -> (&[T], &[Simd<T, LANES>], &[T])
3960 where
3961 Simd<T, LANES>: AsRef<[T; LANES]>,
3962 T: simd::SimdElement,
3963 simd::LaneCount<LANES>: simd::SupportedLaneCount,
3964 {
3965 // These are expected to always match, as vector types are laid out like
3966 // arrays per <https://llvm.org/docs/LangRef.html#vector-type>, but we
3967 // might as well double-check since it'll optimize away anyhow.
3968 assert_eq!(mem::size_of::<Simd<T, LANES>>(), mem::size_of::<[T; LANES]>());
3969
3970 // SAFETY: The simd types have the same layout as arrays, just with
3971 // potentially-higher alignment, so the de-facto transmutes are sound.
3972 unsafe { self.align_to() }
3973 }
3974
3975 /// Split a mutable slice into a mutable prefix, a middle of aligned SIMD types,
3976 /// and a mutable suffix.
3977 ///
3978 /// This is a safe wrapper around [`slice::align_to_mut`], so has the same weak
3979 /// postconditions as that method. You're only assured that
3980 /// `self.len() == prefix.len() + middle.len() * LANES + suffix.len()`.
3981 ///
3982 /// Notably, all of the following are possible:
3983 /// - `prefix.len() >= LANES`.
3984 /// - `middle.is_empty()` despite `self.len() >= 3 * LANES`.
3985 /// - `suffix.len() >= LANES`.
3986 ///
3987 /// That said, this is a safe method, so if you're only writing safe code,
3988 /// then this can at most cause incorrect logic, not unsoundness.
3989 ///
3990 /// This is the mutable version of [`slice::as_simd`]; see that for examples.
3991 ///
3992 /// # Panics
3993 ///
3994 /// This will panic if the size of the SIMD type is different from
3995 /// `LANES` times that of the scalar.
3996 ///
3997 /// At the time of writing, the trait restrictions on `Simd<T, LANES>` keeps
3998 /// that from ever happening, as only power-of-two numbers of lanes are
3999 /// supported. It's possible that, in the future, those restrictions might
4000 /// be lifted in a way that would make it possible to see panics from this
4001 /// method for something like `LANES == 3`.
4002 #[unstable(feature = "portable_simd", issue = "86656")]
4003 #[must_use]
4004 pub fn as_simd_mut<const LANES: usize>(&mut self) -> (&mut [T], &mut [Simd<T, LANES>], &mut [T])
4005 where
4006 Simd<T, LANES>: AsMut<[T; LANES]>,
4007 T: simd::SimdElement,
4008 simd::LaneCount<LANES>: simd::SupportedLaneCount,
4009 {
4010 // These are expected to always match, as vector types are laid out like
4011 // arrays per <https://llvm.org/docs/LangRef.html#vector-type>, but we
4012 // might as well double-check since it'll optimize away anyhow.
4013 assert_eq!(mem::size_of::<Simd<T, LANES>>(), mem::size_of::<[T; LANES]>());
4014
4015 // SAFETY: The simd types have the same layout as arrays, just with
4016 // potentially-higher alignment, so the de-facto transmutes are sound.
4017 unsafe { self.align_to_mut() }
4018 }
4019
4020 /// Checks if the elements of this slice are sorted.
4021 ///
4022 /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
4023 /// slice yields exactly zero or one element, `true` is returned.
4024 ///
4025 /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
4026 /// implies that this function returns `false` if any two consecutive items are not
4027 /// comparable.
4028 ///
4029 /// # Examples
4030 ///
4031 /// ```
4032 /// #![feature(is_sorted)]
4033 /// let empty: [i32; 0] = [];
4034 ///
4035 /// assert!([1, 2, 2, 9].is_sorted());
4036 /// assert!(![1, 3, 2, 4].is_sorted());
4037 /// assert!([0].is_sorted());
4038 /// assert!(empty.is_sorted());
4039 /// assert!(![0.0, 1.0, f32::NAN].is_sorted());
4040 /// ```
4041 #[inline]
4042 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
4043 #[must_use]
4044 pub fn is_sorted(&self) -> bool
4045 where
4046 T: PartialOrd,
4047 {
4048 self.is_sorted_by(|a, b| a <= b)
4049 }
4050
4051 /// Checks if the elements of this slice are sorted using the given comparator function.
4052 ///
4053 /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
4054 /// function to determine whether two elements are to be considered in sorted order.
4055 ///
4056 /// # Examples
4057 ///
4058 /// ```
4059 /// #![feature(is_sorted)]
4060 ///
4061 /// assert!([1, 2, 2, 9].is_sorted_by(|a, b| a <= b));
4062 /// assert!(![1, 2, 2, 9].is_sorted_by(|a, b| a < b));
4063 ///
4064 /// assert!([0].is_sorted_by(|a, b| true));
4065 /// assert!([0].is_sorted_by(|a, b| false));
4066 ///
4067 /// let empty: [i32; 0] = [];
4068 /// assert!(empty.is_sorted_by(|a, b| false));
4069 /// assert!(empty.is_sorted_by(|a, b| true));
4070 /// ```
4071 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
4072 #[must_use]
4073 pub fn is_sorted_by<'a, F>(&'a self, mut compare: F) -> bool
4074 where
4075 F: FnMut(&'a T, &'a T) -> bool,
4076 {
4077 self.array_windows().all(|[a, b]| compare(a, b))
4078 }
4079
4080 /// Checks if the elements of this slice are sorted using the given key extraction function.
4081 ///
4082 /// Instead of comparing the slice's elements directly, this function compares the keys of the
4083 /// elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see its
4084 /// documentation for more information.
4085 ///
4086 /// [`is_sorted`]: slice::is_sorted
4087 ///
4088 /// # Examples
4089 ///
4090 /// ```
4091 /// #![feature(is_sorted)]
4092 ///
4093 /// assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
4094 /// assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
4095 /// ```
4096 #[inline]
4097 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
4098 #[must_use]
4099 pub fn is_sorted_by_key<'a, F, K>(&'a self, f: F) -> bool
4100 where
4101 F: FnMut(&'a T) -> K,
4102 K: PartialOrd,
4103 {
4104 self.iter().is_sorted_by_key(f)
4105 }
4106
4107 /// Returns the index of the partition point according to the given predicate
4108 /// (the index of the first element of the second partition).
4109 ///
4110 /// The slice is assumed to be partitioned according to the given predicate.
4111 /// This means that all elements for which the predicate returns true are at the start of the slice
4112 /// and all elements for which the predicate returns false are at the end.
4113 /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0`
4114 /// (all odd numbers are at the start, all even at the end).
4115 ///
4116 /// If this slice is not partitioned, the returned result is unspecified and meaningless,
4117 /// as this method performs a kind of binary search.
4118 ///
4119 /// See also [`binary_search`], [`binary_search_by`], and [`binary_search_by_key`].
4120 ///
4121 /// [`binary_search`]: slice::binary_search
4122 /// [`binary_search_by`]: slice::binary_search_by
4123 /// [`binary_search_by_key`]: slice::binary_search_by_key
4124 ///
4125 /// # Examples
4126 ///
4127 /// ```
4128 /// let v = [1, 2, 3, 3, 5, 6, 7];
4129 /// let i = v.partition_point(|&x| x < 5);
4130 ///
4131 /// assert_eq!(i, 4);
4132 /// assert!(v[..i].iter().all(|&x| x < 5));
4133 /// assert!(v[i..].iter().all(|&x| !(x < 5)));
4134 /// ```
4135 ///
4136 /// If all elements of the slice match the predicate, including if the slice
4137 /// is empty, then the length of the slice will be returned:
4138 ///
4139 /// ```
4140 /// let a = [2, 4, 8];
4141 /// assert_eq!(a.partition_point(|x| x < &100), a.len());
4142 /// let a: [i32; 0] = [];
4143 /// assert_eq!(a.partition_point(|x| x < &100), 0);
4144 /// ```
4145 ///
4146 /// If you want to insert an item to a sorted vector, while maintaining
4147 /// sort order:
4148 ///
4149 /// ```
4150 /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
4151 /// let num = 42;
4152 /// let idx = s.partition_point(|&x| x < num);
4153 /// s.insert(idx, num);
4154 /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
4155 /// ```
4156 #[stable(feature = "partition_point", since = "1.52.0")]
4157 #[must_use]
4158 pub fn partition_point<P>(&self, mut pred: P) -> usize
4159 where
4160 P: FnMut(&T) -> bool,
4161 {
4162 self.binary_search_by(|x| if pred(x) { Less } else { Greater }).unwrap_or_else(|i| i)
4163 }
4164
4165 /// Removes the subslice corresponding to the given range
4166 /// and returns a reference to it.
4167 ///
4168 /// Returns `None` and does not modify the slice if the given
4169 /// range is out of bounds.
4170 ///
4171 /// Note that this method only accepts one-sided ranges such as
4172 /// `2..` or `..6`, but not `2..6`.
4173 ///
4174 /// # Examples
4175 ///
4176 /// Taking the first three elements of a slice:
4177 ///
4178 /// ```
4179 /// #![feature(slice_take)]
4180 ///
4181 /// let mut slice: &[_] = &['a', 'b', 'c', 'd'];
4182 /// let mut first_three = slice.take(..3).unwrap();
4183 ///
4184 /// assert_eq!(slice, &['d']);
4185 /// assert_eq!(first_three, &['a', 'b', 'c']);
4186 /// ```
4187 ///
4188 /// Taking the last two elements of a slice:
4189 ///
4190 /// ```
4191 /// #![feature(slice_take)]
4192 ///
4193 /// let mut slice: &[_] = &['a', 'b', 'c', 'd'];
4194 /// let mut tail = slice.take(2..).unwrap();
4195 ///
4196 /// assert_eq!(slice, &['a', 'b']);
4197 /// assert_eq!(tail, &['c', 'd']);
4198 /// ```
4199 ///
4200 /// Getting `None` when `range` is out of bounds:
4201 ///
4202 /// ```
4203 /// #![feature(slice_take)]
4204 ///
4205 /// let mut slice: &[_] = &['a', 'b', 'c', 'd'];
4206 ///
4207 /// assert_eq!(None, slice.take(5..));
4208 /// assert_eq!(None, slice.take(..5));
4209 /// assert_eq!(None, slice.take(..=4));
4210 /// let expected: &[char] = &['a', 'b', 'c', 'd'];
4211 /// assert_eq!(Some(expected), slice.take(..4));
4212 /// ```
4213 #[inline]
4214 #[must_use = "method does not modify the slice if the range is out of bounds"]
4215 #[unstable(feature = "slice_take", issue = "62280")]
4216 pub fn take<'a, R: OneSidedRange<usize>>(self: &mut &'a Self, range: R) -> Option<&'a Self> {
4217 let (direction, split_index) = split_point_of(range)?;
4218 if split_index > self.len() {
4219 return None;
4220 }
4221 let (front, back) = self.split_at(split_index);
4222 match direction {
4223 Direction::Front => {
4224 *self = back;
4225 Some(front)
4226 }
4227 Direction::Back => {
4228 *self = front;
4229 Some(back)
4230 }
4231 }
4232 }
4233
4234 /// Removes the subslice corresponding to the given range
4235 /// and returns a mutable reference to it.
4236 ///
4237 /// Returns `None` and does not modify the slice if the given
4238 /// range is out of bounds.
4239 ///
4240 /// Note that this method only accepts one-sided ranges such as
4241 /// `2..` or `..6`, but not `2..6`.
4242 ///
4243 /// # Examples
4244 ///
4245 /// Taking the first three elements of a slice:
4246 ///
4247 /// ```
4248 /// #![feature(slice_take)]
4249 ///
4250 /// let mut slice: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4251 /// let mut first_three = slice.take_mut(..3).unwrap();
4252 ///
4253 /// assert_eq!(slice, &mut ['d']);
4254 /// assert_eq!(first_three, &mut ['a', 'b', 'c']);
4255 /// ```
4256 ///
4257 /// Taking the last two elements of a slice:
4258 ///
4259 /// ```
4260 /// #![feature(slice_take)]
4261 ///
4262 /// let mut slice: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4263 /// let mut tail = slice.take_mut(2..).unwrap();
4264 ///
4265 /// assert_eq!(slice, &mut ['a', 'b']);
4266 /// assert_eq!(tail, &mut ['c', 'd']);
4267 /// ```
4268 ///
4269 /// Getting `None` when `range` is out of bounds:
4270 ///
4271 /// ```
4272 /// #![feature(slice_take)]
4273 ///
4274 /// let mut slice: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4275 ///
4276 /// assert_eq!(None, slice.take_mut(5..));
4277 /// assert_eq!(None, slice.take_mut(..5));
4278 /// assert_eq!(None, slice.take_mut(..=4));
4279 /// let expected: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4280 /// assert_eq!(Some(expected), slice.take_mut(..4));
4281 /// ```
4282 #[inline]
4283 #[must_use = "method does not modify the slice if the range is out of bounds"]
4284 #[unstable(feature = "slice_take", issue = "62280")]
4285 pub fn take_mut<'a, R: OneSidedRange<usize>>(
4286 self: &mut &'a mut Self,
4287 range: R,
4288 ) -> Option<&'a mut Self> {
4289 let (direction, split_index) = split_point_of(range)?;
4290 if split_index > self.len() {
4291 return None;
4292 }
4293 let (front, back) = mem::take(self).split_at_mut(split_index);
4294 match direction {
4295 Direction::Front => {
4296 *self = back;
4297 Some(front)
4298 }
4299 Direction::Back => {
4300 *self = front;
4301 Some(back)
4302 }
4303 }
4304 }
4305
4306 /// Removes the first element of the slice and returns a reference
4307 /// to it.
4308 ///
4309 /// Returns `None` if the slice is empty.
4310 ///
4311 /// # Examples
4312 ///
4313 /// ```
4314 /// #![feature(slice_take)]
4315 ///
4316 /// let mut slice: &[_] = &['a', 'b', 'c'];
4317 /// let first = slice.take_first().unwrap();
4318 ///
4319 /// assert_eq!(slice, &['b', 'c']);
4320 /// assert_eq!(first, &'a');
4321 /// ```
4322 #[inline]
4323 #[unstable(feature = "slice_take", issue = "62280")]
4324 pub fn take_first<'a>(self: &mut &'a Self) -> Option<&'a T> {
4325 let (first, rem) = self.split_first()?;
4326 *self = rem;
4327 Some(first)
4328 }
4329
4330 /// Removes the first element of the slice and returns a mutable
4331 /// reference to it.
4332 ///
4333 /// Returns `None` if the slice is empty.
4334 ///
4335 /// # Examples
4336 ///
4337 /// ```
4338 /// #![feature(slice_take)]
4339 ///
4340 /// let mut slice: &mut [_] = &mut ['a', 'b', 'c'];
4341 /// let first = slice.take_first_mut().unwrap();
4342 /// *first = 'd';
4343 ///
4344 /// assert_eq!(slice, &['b', 'c']);
4345 /// assert_eq!(first, &'d');
4346 /// ```
4347 #[inline]
4348 #[unstable(feature = "slice_take", issue = "62280")]
4349 pub fn take_first_mut<'a>(self: &mut &'a mut Self) -> Option<&'a mut T> {
4350 let (first, rem) = mem::take(self).split_first_mut()?;
4351 *self = rem;
4352 Some(first)
4353 }
4354
4355 /// Removes the last element of the slice and returns a reference
4356 /// to it.
4357 ///
4358 /// Returns `None` if the slice is empty.
4359 ///
4360 /// # Examples
4361 ///
4362 /// ```
4363 /// #![feature(slice_take)]
4364 ///
4365 /// let mut slice: &[_] = &['a', 'b', 'c'];
4366 /// let last = slice.take_last().unwrap();
4367 ///
4368 /// assert_eq!(slice, &['a', 'b']);
4369 /// assert_eq!(last, &'c');
4370 /// ```
4371 #[inline]
4372 #[unstable(feature = "slice_take", issue = "62280")]
4373 pub fn take_last<'a>(self: &mut &'a Self) -> Option<&'a T> {
4374 let (last, rem) = self.split_last()?;
4375 *self = rem;
4376 Some(last)
4377 }
4378
4379 /// Removes the last element of the slice and returns a mutable
4380 /// reference to it.
4381 ///
4382 /// Returns `None` if the slice is empty.
4383 ///
4384 /// # Examples
4385 ///
4386 /// ```
4387 /// #![feature(slice_take)]
4388 ///
4389 /// let mut slice: &mut [_] = &mut ['a', 'b', 'c'];
4390 /// let last = slice.take_last_mut().unwrap();
4391 /// *last = 'd';
4392 ///
4393 /// assert_eq!(slice, &['a', 'b']);
4394 /// assert_eq!(last, &'d');
4395 /// ```
4396 #[inline]
4397 #[unstable(feature = "slice_take", issue = "62280")]
4398 pub fn take_last_mut<'a>(self: &mut &'a mut Self) -> Option<&'a mut T> {
4399 let (last, rem) = mem::take(self).split_last_mut()?;
4400 *self = rem;
4401 Some(last)
4402 }
4403
4404 /// Returns mutable references to many indices at once, without doing any checks.
4405 ///
4406 /// For a safe alternative see [`get_many_mut`].
4407 ///
4408 /// # Safety
4409 ///
4410 /// Calling this method with overlapping or out-of-bounds indices is *[undefined behavior]*
4411 /// even if the resulting references are not used.
4412 ///
4413 /// # Examples
4414 ///
4415 /// ```
4416 /// #![feature(get_many_mut)]
4417 ///
4418 /// let x = &mut [1, 2, 4];
4419 ///
4420 /// unsafe {
4421 /// let [a, b] = x.get_many_unchecked_mut([0, 2]);
4422 /// *a *= 10;
4423 /// *b *= 100;
4424 /// }
4425 /// assert_eq!(x, &[10, 2, 400]);
4426 /// ```
4427 ///
4428 /// [`get_many_mut`]: slice::get_many_mut
4429 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
4430 #[unstable(feature = "get_many_mut", issue = "104642")]
4431 #[inline]
4432 pub unsafe fn get_many_unchecked_mut<const N: usize>(
4433 &mut self,
4434 indices: [usize; N],
4435 ) -> [&mut T; N] {
4436 // NB: This implementation is written as it is because any variation of
4437 // `indices.map(|i| self.get_unchecked_mut(i))` would make miri unhappy,
4438 // or generate worse code otherwise. This is also why we need to go
4439 // through a raw pointer here.
4440 let slice: *mut [T] = self;
4441 let mut arr: mem::MaybeUninit<[&mut T; N]> = mem::MaybeUninit::uninit();
4442 let arr_ptr = arr.as_mut_ptr();
4443
4444 // SAFETY: We expect `indices` to contain disjunct values that are
4445 // in bounds of `self`.
4446 unsafe {
4447 for i in 0..N {
4448 let idx = *indices.get_unchecked(i);
4449 *(*arr_ptr).get_unchecked_mut(i) = &mut *slice.get_unchecked_mut(idx);
4450 }
4451 arr.assume_init()
4452 }
4453 }
4454
4455 /// Returns mutable references to many indices at once.
4456 ///
4457 /// Returns an error if any index is out-of-bounds, or if the same index was
4458 /// passed more than once.
4459 ///
4460 /// # Examples
4461 ///
4462 /// ```
4463 /// #![feature(get_many_mut)]
4464 ///
4465 /// let v = &mut [1, 2, 3];
4466 /// if let Ok([a, b]) = v.get_many_mut([0, 2]) {
4467 /// *a = 413;
4468 /// *b = 612;
4469 /// }
4470 /// assert_eq!(v, &[413, 2, 612]);
4471 /// ```
4472 #[unstable(feature = "get_many_mut", issue = "104642")]
4473 #[inline]
4474 pub fn get_many_mut<const N: usize>(
4475 &mut self,
4476 indices: [usize; N],
4477 ) -> Result<[&mut T; N], GetManyMutError<N>> {
4478 if !get_many_check_valid(&indices, self.len()) {
4479 return Err(GetManyMutError { _private: () });
4480 }
4481 // SAFETY: The `get_many_check_valid()` call checked that all indices
4482 // are disjunct and in bounds.
4483 unsafe { Ok(self.get_many_unchecked_mut(indices)) }
4484 }
4485}
4486
4487impl<T, const N: usize> [[T; N]] {
4488 /// Takes a `&[[T; N]]`, and flattens it to a `&[T]`.
4489 ///
4490 /// # Panics
4491 ///
4492 /// This panics if the length of the resulting slice would overflow a `usize`.
4493 ///
4494 /// This is only possible when flattening a slice of arrays of zero-sized
4495 /// types, and thus tends to be irrelevant in practice. If
4496 /// `size_of::<T>() > 0`, this will never panic.
4497 ///
4498 /// # Examples
4499 ///
4500 /// ```
4501 /// #![feature(slice_flatten)]
4502 ///
4503 /// assert_eq!([[1, 2, 3], [4, 5, 6]].flatten(), &[1, 2, 3, 4, 5, 6]);
4504 ///
4505 /// assert_eq!(
4506 /// [[1, 2, 3], [4, 5, 6]].flatten(),
4507 /// [[1, 2], [3, 4], [5, 6]].flatten(),
4508 /// );
4509 ///
4510 /// let slice_of_empty_arrays: &[[i32; 0]] = &[[], [], [], [], []];
4511 /// assert!(slice_of_empty_arrays.flatten().is_empty());
4512 ///
4513 /// let empty_slice_of_arrays: &[[u32; 10]] = &[];
4514 /// assert!(empty_slice_of_arrays.flatten().is_empty());
4515 /// ```
4516 #[unstable(feature = "slice_flatten", issue = "95629")]
4517 pub const fn flatten(&self) -> &[T] {
4518 let len = if T::IS_ZST {
4519 self.len().checked_mul(N).expect("slice len overflow")
4520 } else {
4521 // SAFETY: `self.len() * N` cannot overflow because `self` is
4522 // already in the address space.
4523 unsafe { self.len().unchecked_mul(N) }
4524 };
4525 // SAFETY: `[T]` is layout-identical to `[T; N]`
4526 unsafe { from_raw_parts(self.as_ptr().cast(), len) }
4527 }
4528
4529 /// Takes a `&mut [[T; N]]`, and flattens it to a `&mut [T]`.
4530 ///
4531 /// # Panics
4532 ///
4533 /// This panics if the length of the resulting slice would overflow a `usize`.
4534 ///
4535 /// This is only possible when flattening a slice of arrays of zero-sized
4536 /// types, and thus tends to be irrelevant in practice. If
4537 /// `size_of::<T>() > 0`, this will never panic.
4538 ///
4539 /// # Examples
4540 ///
4541 /// ```
4542 /// #![feature(slice_flatten)]
4543 ///
4544 /// fn add_5_to_all(slice: &mut [i32]) {
4545 /// for i in slice {
4546 /// *i += 5;
4547 /// }
4548 /// }
4549 ///
4550 /// let mut array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
4551 /// add_5_to_all(array.flatten_mut());
4552 /// assert_eq!(array, [[6, 7, 8], [9, 10, 11], [12, 13, 14]]);
4553 /// ```
4554 #[unstable(feature = "slice_flatten", issue = "95629")]
4555 pub fn flatten_mut(&mut self) -> &mut [T] {
4556 let len = if T::IS_ZST {
4557 self.len().checked_mul(N).expect("slice len overflow")
4558 } else {
4559 // SAFETY: `self.len() * N` cannot overflow because `self` is
4560 // already in the address space.
4561 unsafe { self.len().unchecked_mul(N) }
4562 };
4563 // SAFETY: `[T]` is layout-identical to `[T; N]`
4564 unsafe { from_raw_parts_mut(self.as_mut_ptr().cast(), len) }
4565 }
4566}
4567
4568#[cfg(not(test))]
4569impl [f32] {
4570 /// Sorts the slice of floats.
4571 ///
4572 /// This sort is in-place (i.e. does not allocate), *O*(*n* \* log(*n*)) worst-case, and uses
4573 /// the ordering defined by [`f32::total_cmp`].
4574 ///
4575 /// # Current implementation
4576 ///
4577 /// This uses the same sorting algorithm as [`sort_unstable_by`](slice::sort_unstable_by).
4578 ///
4579 /// # Examples
4580 ///
4581 /// ```
4582 /// #![feature(sort_floats)]
4583 /// let mut v = [2.6, -5e-8, f32::NAN, 8.29, f32::INFINITY, -1.0, 0.0, -f32::INFINITY, -0.0];
4584 ///
4585 /// v.sort_floats();
4586 /// let sorted = [-f32::INFINITY, -1.0, -5e-8, -0.0, 0.0, 2.6, 8.29, f32::INFINITY, f32::NAN];
4587 /// assert_eq!(&v[..8], &sorted[..8]);
4588 /// assert!(v[8].is_nan());
4589 /// ```
4590 #[unstable(feature = "sort_floats", issue = "93396")]
4591 #[inline]
4592 pub fn sort_floats(&mut self) {
4593 self.sort_unstable_by(f32::total_cmp);
4594 }
4595}
4596
4597#[cfg(not(test))]
4598impl [f64] {
4599 /// Sorts the slice of floats.
4600 ///
4601 /// This sort is in-place (i.e. does not allocate), *O*(*n* \* log(*n*)) worst-case, and uses
4602 /// the ordering defined by [`f64::total_cmp`].
4603 ///
4604 /// # Current implementation
4605 ///
4606 /// This uses the same sorting algorithm as [`sort_unstable_by`](slice::sort_unstable_by).
4607 ///
4608 /// # Examples
4609 ///
4610 /// ```
4611 /// #![feature(sort_floats)]
4612 /// let mut v = [2.6, -5e-8, f64::NAN, 8.29, f64::INFINITY, -1.0, 0.0, -f64::INFINITY, -0.0];
4613 ///
4614 /// v.sort_floats();
4615 /// let sorted = [-f64::INFINITY, -1.0, -5e-8, -0.0, 0.0, 2.6, 8.29, f64::INFINITY, f64::NAN];
4616 /// assert_eq!(&v[..8], &sorted[..8]);
4617 /// assert!(v[8].is_nan());
4618 /// ```
4619 #[unstable(feature = "sort_floats", issue = "93396")]
4620 #[inline]
4621 pub fn sort_floats(&mut self) {
4622 self.sort_unstable_by(f64::total_cmp);
4623 }
4624}
4625
4626trait CloneFromSpec<T> {
4627 fn spec_clone_from(&mut self, src: &[T]);
4628}
4629
4630impl<T> CloneFromSpec<T> for [T]
4631where
4632 T: Clone,
4633{
4634 #[track_caller]
4635 default fn spec_clone_from(&mut self, src: &[T]) {
4636 assert!(self.len() == src.len(), "destination and source slices have different lengths");
4637 // NOTE: We need to explicitly slice them to the same length
4638 // to make it easier for the optimizer to elide bounds checking.
4639 // But since it can't be relied on we also have an explicit specialization for T: Copy.
4640 let len: usize = self.len();
4641 let src: &[T] = &src[..len];
4642 for i: usize in 0..len {
4643 self[i].clone_from(&src[i]);
4644 }
4645 }
4646}
4647
4648impl<T> CloneFromSpec<T> for [T]
4649where
4650 T: Copy,
4651{
4652 #[track_caller]
4653 fn spec_clone_from(&mut self, src: &[T]) {
4654 self.copy_from_slice(src);
4655 }
4656}
4657
4658#[stable(feature = "rust1", since = "1.0.0")]
4659impl<T> Default for &[T] {
4660 /// Creates an empty slice.
4661 fn default() -> Self {
4662 &[]
4663 }
4664}
4665
4666#[stable(feature = "mut_slice_default", since = "1.5.0")]
4667impl<T> Default for &mut [T] {
4668 /// Creates a mutable empty slice.
4669 fn default() -> Self {
4670 &mut []
4671 }
4672}
4673
4674#[unstable(feature = "slice_pattern", reason = "stopgap trait for slice patterns", issue = "56345")]
4675/// Patterns in slices - currently, only used by `strip_prefix` and `strip_suffix`. At a future
4676/// point, we hope to generalise `core::str::Pattern` (which at the time of writing is limited to
4677/// `str`) to slices, and then this trait will be replaced or abolished.
4678pub trait SlicePattern {
4679 /// The element type of the slice being matched on.
4680 type Item;
4681
4682 /// Currently, the consumers of `SlicePattern` need a slice.
4683 fn as_slice(&self) -> &[Self::Item];
4684}
4685
4686#[stable(feature = "slice_strip", since = "1.51.0")]
4687impl<T> SlicePattern for [T] {
4688 type Item = T;
4689
4690 #[inline]
4691 fn as_slice(&self) -> &[Self::Item] {
4692 self
4693 }
4694}
4695
4696#[stable(feature = "slice_strip", since = "1.51.0")]
4697impl<T, const N: usize> SlicePattern for [T; N] {
4698 type Item = T;
4699
4700 #[inline]
4701 fn as_slice(&self) -> &[Self::Item] {
4702 self
4703 }
4704}
4705
4706/// This checks every index against each other, and against `len`.
4707///
4708/// This will do `binomial(N + 1, 2) = N * (N + 1) / 2 = 0, 1, 3, 6, 10, ..`
4709/// comparison operations.
4710fn get_many_check_valid<const N: usize>(indices: &[usize; N], len: usize) -> bool {
4711 // NB: The optimizer should inline the loops into a sequence
4712 // of instructions without additional branching.
4713 let mut valid: bool = true;
4714 for (i: usize, &idx: usize) in indices.iter().enumerate() {
4715 valid &= idx < len;
4716 for &idx2: usize in &indices[..i] {
4717 valid &= idx != idx2;
4718 }
4719 }
4720 valid
4721}
4722
4723/// The error type returned by [`get_many_mut<N>`][`slice::get_many_mut`].
4724///
4725/// It indicates one of two possible errors:
4726/// - An index is out-of-bounds.
4727/// - The same index appeared multiple times in the array.
4728///
4729/// # Examples
4730///
4731/// ```
4732/// #![feature(get_many_mut)]
4733///
4734/// let v = &mut [1, 2, 3];
4735/// assert!(v.get_many_mut([0, 999]).is_err());
4736/// assert!(v.get_many_mut([1, 1]).is_err());
4737/// ```
4738#[unstable(feature = "get_many_mut", issue = "104642")]
4739// NB: The N here is there to be forward-compatible with adding more details
4740// to the error type at a later point
4741pub struct GetManyMutError<const N: usize> {
4742 _private: (),
4743}
4744
4745#[unstable(feature = "get_many_mut", issue = "104642")]
4746impl<const N: usize> fmt::Debug for GetManyMutError<N> {
4747 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4748 f.debug_struct(name:"GetManyMutError").finish_non_exhaustive()
4749 }
4750}
4751
4752#[unstable(feature = "get_many_mut", issue = "104642")]
4753impl<const N: usize> fmt::Display for GetManyMutError<N> {
4754 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4755 fmt::Display::fmt(self:"an index is out of bounds or appeared multiple times in the array", f)
4756 }
4757}
4758