core/slice/
mod.rs

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