1 // ignore-tidy-filelength
3 //! Slice management and manipulation.
5 //! For more details see [`std::slice`].
7 //! [`std::slice`]: ../../std/slice/index.html
9 #![stable(feature = "rust1", since = "1.0.0")]
11 use crate::cmp
::Ordering
::{self, Equal, Greater, Less}
;
12 use crate::marker
::Copy
;
14 use crate::ops
::{FnMut, Range, RangeBounds}
;
15 use crate::option
::Option
;
16 use crate::option
::Option
::{None, Some}
;
18 use crate::result
::Result
;
19 use crate::result
::Result
::{Err, Ok}
;
22 feature
= "slice_internals",
24 reason
= "exposed from core to be reused in std; use the memchr crate"
26 /// Pure rust memchr implementation, taken from rust-memchr
37 #[stable(feature = "rust1", since = "1.0.0")]
38 pub use iter
::{Chunks, ChunksMut, Windows}
;
39 #[stable(feature = "rust1", since = "1.0.0")]
40 pub use iter
::{Iter, IterMut}
;
41 #[stable(feature = "rust1", since = "1.0.0")]
42 pub use iter
::{RSplitN, RSplitNMut, Split, SplitMut, SplitN, SplitNMut}
;
44 #[stable(feature = "slice_rsplit", since = "1.27.0")]
45 pub use iter
::{RSplit, RSplitMut}
;
47 #[stable(feature = "chunks_exact", since = "1.31.0")]
48 pub use iter
::{ChunksExact, ChunksExactMut}
;
50 #[stable(feature = "rchunks", since = "1.31.0")]
51 pub use iter
::{RChunks, RChunksExact, RChunksExactMut, RChunksMut}
;
53 #[unstable(feature = "array_chunks", issue = "74985")]
54 pub use iter
::{ArrayChunks, ArrayChunksMut}
;
56 #[unstable(feature = "array_windows", issue = "75027")]
57 pub use iter
::ArrayWindows
;
59 #[unstable(feature = "split_inclusive", issue = "72360")]
60 pub use iter
::{SplitInclusive, SplitInclusiveMut}
;
62 #[stable(feature = "rust1", since = "1.0.0")]
63 pub use raw
::{from_raw_parts, from_raw_parts_mut}
;
65 #[stable(feature = "from_ref", since = "1.28.0")]
66 pub use raw
::{from_mut, from_ref}
;
68 // This function is public only because there is no other way to unit test heapsort.
69 #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "none")]
70 pub use sort
::heapsort
;
72 #[stable(feature = "slice_get_slice", since = "1.28.0")]
73 pub use index
::SliceIndex
;
75 #[unstable(feature = "slice_check_range", issue = "76393")]
76 pub use index
::check_range
;
81 /// Returns the number of elements in the slice.
86 /// let a = [1, 2, 3];
87 /// assert_eq!(a.len(), 3);
89 #[stable(feature = "rust1", since = "1.0.0")]
90 #[rustc_const_stable(feature = "const_slice_len", since = "1.32.0")]
92 // SAFETY: const sound because we transmute out the length field as a usize (which it must be)
93 #[allow_internal_unstable(const_fn_union)]
94 pub const fn len(&self) -> usize {
95 // SAFETY: this is safe because `&[T]` and `FatPtr<T>` have the same layout.
96 // Only `std` can make this guarantee.
97 unsafe { crate::ptr::Repr { rust: self }
.raw
.len
}
100 /// Returns `true` if the slice has a length of 0.
105 /// let a = [1, 2, 3];
106 /// assert!(!a.is_empty());
108 #[stable(feature = "rust1", since = "1.0.0")]
109 #[rustc_const_stable(feature = "const_slice_is_empty", since = "1.32.0")]
111 pub const fn is_empty(&self) -> bool
{
115 /// Returns the first element of the slice, or `None` if it is empty.
120 /// let v = [10, 40, 30];
121 /// assert_eq!(Some(&10), v.first());
123 /// let w: &[i32] = &[];
124 /// assert_eq!(None, w.first());
126 #[stable(feature = "rust1", since = "1.0.0")]
128 pub fn first(&self) -> Option
<&T
> {
129 if let [first
, ..] = self { Some(first) }
else { None }
132 /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty.
137 /// let x = &mut [0, 1, 2];
139 /// if let Some(first) = x.first_mut() {
142 /// assert_eq!(x, &[5, 1, 2]);
144 #[stable(feature = "rust1", since = "1.0.0")]
146 pub fn first_mut(&mut self) -> Option
<&mut T
> {
147 if let [first
, ..] = self { Some(first) }
else { None }
150 /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
155 /// let x = &[0, 1, 2];
157 /// if let Some((first, elements)) = x.split_first() {
158 /// assert_eq!(first, &0);
159 /// assert_eq!(elements, &[1, 2]);
162 #[stable(feature = "slice_splits", since = "1.5.0")]
164 pub fn split_first(&self) -> Option
<(&T
, &[T
])> {
165 if let [first
, tail @
..] = self { Some((first, tail)) }
else { None }
168 /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
173 /// let x = &mut [0, 1, 2];
175 /// if let Some((first, elements)) = x.split_first_mut() {
180 /// assert_eq!(x, &[3, 4, 5]);
182 #[stable(feature = "slice_splits", since = "1.5.0")]
184 pub fn split_first_mut(&mut self) -> Option
<(&mut T
, &mut [T
])> {
185 if let [first
, tail @
..] = self { Some((first, tail)) }
else { None }
188 /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
193 /// let x = &[0, 1, 2];
195 /// if let Some((last, elements)) = x.split_last() {
196 /// assert_eq!(last, &2);
197 /// assert_eq!(elements, &[0, 1]);
200 #[stable(feature = "slice_splits", since = "1.5.0")]
202 pub fn split_last(&self) -> Option
<(&T
, &[T
])> {
203 if let [init @
.., last
] = self { Some((last, init)) }
else { None }
206 /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
211 /// let x = &mut [0, 1, 2];
213 /// if let Some((last, elements)) = x.split_last_mut() {
218 /// assert_eq!(x, &[4, 5, 3]);
220 #[stable(feature = "slice_splits", since = "1.5.0")]
222 pub fn split_last_mut(&mut self) -> Option
<(&mut T
, &mut [T
])> {
223 if let [init @
.., last
] = self { Some((last, init)) }
else { None }
226 /// Returns the last element of the slice, or `None` if it is empty.
231 /// let v = [10, 40, 30];
232 /// assert_eq!(Some(&30), v.last());
234 /// let w: &[i32] = &[];
235 /// assert_eq!(None, w.last());
237 #[stable(feature = "rust1", since = "1.0.0")]
239 pub fn last(&self) -> Option
<&T
> {
240 if let [.., last
] = self { Some(last) }
else { None }
243 /// Returns a mutable pointer to the last item in the slice.
248 /// let x = &mut [0, 1, 2];
250 /// if let Some(last) = x.last_mut() {
253 /// assert_eq!(x, &[0, 1, 10]);
255 #[stable(feature = "rust1", since = "1.0.0")]
257 pub fn last_mut(&mut self) -> Option
<&mut T
> {
258 if let [.., last
] = self { Some(last) }
else { None }
261 /// Returns a reference to an element or subslice depending on the type of
264 /// - If given a position, returns a reference to the element at that
265 /// position or `None` if out of bounds.
266 /// - If given a range, returns the subslice corresponding to that range,
267 /// or `None` if out of bounds.
272 /// let v = [10, 40, 30];
273 /// assert_eq!(Some(&40), v.get(1));
274 /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
275 /// assert_eq!(None, v.get(3));
276 /// assert_eq!(None, v.get(0..4));
278 #[stable(feature = "rust1", since = "1.0.0")]
280 pub fn get
<I
>(&self, index
: I
) -> Option
<&I
::Output
>
287 /// Returns a mutable reference to an element or subslice depending on the
288 /// type of index (see [`get`]) or `None` if the index is out of bounds.
290 /// [`get`]: #method.get
295 /// let x = &mut [0, 1, 2];
297 /// if let Some(elem) = x.get_mut(1) {
300 /// assert_eq!(x, &[0, 42, 2]);
302 #[stable(feature = "rust1", since = "1.0.0")]
304 pub fn get_mut
<I
>(&mut self, index
: I
) -> Option
<&mut I
::Output
>
311 /// Returns a reference to an element or subslice, without doing bounds
314 /// For a safe alternative see [`get`].
318 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
319 /// even if the resulting reference is not used.
321 /// [`get`]: #method.get
322 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
327 /// let x = &[1, 2, 4];
330 /// assert_eq!(x.get_unchecked(1), &2);
333 #[stable(feature = "rust1", since = "1.0.0")]
335 pub unsafe fn get_unchecked
<I
>(&self, index
: I
) -> &I
::Output
339 // SAFETY: the caller must uphold most of the safety requirements for `get_unchecked`;
340 // the slice is dereferencable because `self` is a safe reference.
341 // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is.
342 unsafe { &*index.get_unchecked(self) }
345 /// Returns a mutable reference to an element or subslice, without doing
348 /// For a safe alternative see [`get_mut`].
352 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
353 /// even if the resulting reference is not used.
355 /// [`get_mut`]: #method.get_mut
356 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
361 /// let x = &mut [1, 2, 4];
364 /// let elem = x.get_unchecked_mut(1);
367 /// assert_eq!(x, &[1, 13, 4]);
369 #[stable(feature = "rust1", since = "1.0.0")]
371 pub unsafe fn get_unchecked_mut
<I
>(&mut self, index
: I
) -> &mut I
::Output
375 // SAFETY: the caller must uphold the safety requirements for `get_unchecked_mut`;
376 // the slice is dereferencable because `self` is a safe reference.
377 // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is.
378 unsafe { &mut *index.get_unchecked_mut(self) }
381 /// Returns a raw pointer to the slice's buffer.
383 /// The caller must ensure that the slice outlives the pointer this
384 /// function returns, or else it will end up pointing to garbage.
386 /// The caller must also ensure that the memory the pointer (non-transitively) points to
387 /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
388 /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
390 /// Modifying the container referenced by this slice may cause its buffer
391 /// to be reallocated, which would also make any pointers to it invalid.
396 /// let x = &[1, 2, 4];
397 /// let x_ptr = x.as_ptr();
400 /// for i in 0..x.len() {
401 /// assert_eq!(x.get_unchecked(i), &*x_ptr.add(i));
406 /// [`as_mut_ptr`]: #method.as_mut_ptr
407 #[stable(feature = "rust1", since = "1.0.0")]
408 #[rustc_const_stable(feature = "const_slice_as_ptr", since = "1.32.0")]
410 pub const fn as_ptr(&self) -> *const T
{
411 self as *const [T
] as *const T
414 /// Returns an unsafe mutable pointer to the slice's buffer.
416 /// The caller must ensure that the slice outlives the pointer this
417 /// function returns, or else it will end up pointing to garbage.
419 /// Modifying the container referenced by this slice may cause its buffer
420 /// to be reallocated, which would also make any pointers to it invalid.
425 /// let x = &mut [1, 2, 4];
426 /// let x_ptr = x.as_mut_ptr();
429 /// for i in 0..x.len() {
430 /// *x_ptr.add(i) += 2;
433 /// assert_eq!(x, &[3, 4, 6]);
435 #[stable(feature = "rust1", since = "1.0.0")]
436 #[rustc_const_unstable(feature = "const_ptr_offset", issue = "71499")]
438 pub const fn as_mut_ptr(&mut self) -> *mut T
{
439 self as *mut [T
] as *mut T
442 /// Returns the two raw pointers spanning the slice.
444 /// The returned range is half-open, which means that the end pointer
445 /// points *one past* the last element of the slice. This way, an empty
446 /// slice is represented by two equal pointers, and the difference between
447 /// the two pointers represents the size of the slice.
449 /// See [`as_ptr`] for warnings on using these pointers. The end pointer
450 /// requires extra caution, as it does not point to a valid element in the
453 /// This function is useful for interacting with foreign interfaces which
454 /// use two pointers to refer to a range of elements in memory, as is
457 /// It can also be useful to check if a pointer to an element refers to an
458 /// element of this slice:
461 /// let a = [1, 2, 3];
462 /// let x = &a[1] as *const _;
463 /// let y = &5 as *const _;
465 /// assert!(a.as_ptr_range().contains(&x));
466 /// assert!(!a.as_ptr_range().contains(&y));
469 /// [`as_ptr`]: #method.as_ptr
470 #[stable(feature = "slice_ptr_range", since = "1.48.0")]
471 #[rustc_const_unstable(feature = "const_ptr_offset", issue = "71499")]
473 pub const fn as_ptr_range(&self) -> Range
<*const T
> {
474 let start
= self.as_ptr();
475 // SAFETY: The `add` here is safe, because:
477 // - Both pointers are part of the same object, as pointing directly
478 // past the object also counts.
480 // - The size of the slice is never larger than isize::MAX bytes, as
482 // - https://github.com/rust-lang/unsafe-code-guidelines/issues/102#issuecomment-473340447
483 // - https://doc.rust-lang.org/reference/behavior-considered-undefined.html
484 // - https://doc.rust-lang.org/core/slice/fn.from_raw_parts.html#safety
485 // (This doesn't seem normative yet, but the very same assumption is
486 // made in many places, including the Index implementation of slices.)
488 // - There is no wrapping around involved, as slices do not wrap past
489 // the end of the address space.
491 // See the documentation of pointer::add.
492 let end
= unsafe { start.add(self.len()) }
;
496 /// Returns the two unsafe mutable pointers spanning the slice.
498 /// The returned range is half-open, which means that the end pointer
499 /// points *one past* the last element of the slice. This way, an empty
500 /// slice is represented by two equal pointers, and the difference between
501 /// the two pointers represents the size of the slice.
503 /// See [`as_mut_ptr`] for warnings on using these pointers. The end
504 /// pointer requires extra caution, as it does not point to a valid element
507 /// This function is useful for interacting with foreign interfaces which
508 /// use two pointers to refer to a range of elements in memory, as is
511 /// [`as_mut_ptr`]: #method.as_mut_ptr
512 #[stable(feature = "slice_ptr_range", since = "1.48.0")]
513 #[rustc_const_unstable(feature = "const_ptr_offset", issue = "71499")]
515 pub const fn as_mut_ptr_range(&mut self) -> Range
<*mut T
> {
516 let start
= self.as_mut_ptr();
517 // SAFETY: See as_ptr_range() above for why `add` here is safe.
518 let end
= unsafe { start.add(self.len()) }
;
522 /// Swaps two elements in the slice.
526 /// * a - The index of the first element
527 /// * b - The index of the second element
531 /// Panics if `a` or `b` are out of bounds.
536 /// let mut v = ["a", "b", "c", "d"];
538 /// assert!(v == ["a", "d", "c", "b"]);
540 #[stable(feature = "rust1", since = "1.0.0")]
542 pub fn swap(&mut self, a
: usize, b
: usize) {
543 // Can't take two mutable loans from one vector, so instead just cast
544 // them to their raw pointers to do the swap.
545 let pa
: *mut T
= &mut self[a
];
546 let pb
: *mut T
= &mut self[b
];
547 // SAFETY: `pa` and `pb` have been created from safe mutable references and refer
548 // to elements in the slice and therefore are guaranteed to be valid and aligned.
549 // Note that accessing the elements behind `a` and `b` is checked and will
550 // panic when out of bounds.
556 /// Reverses the order of elements in the slice, in place.
561 /// let mut v = [1, 2, 3];
563 /// assert!(v == [3, 2, 1]);
565 #[stable(feature = "rust1", since = "1.0.0")]
567 pub fn reverse(&mut self) {
568 let mut i
: usize = 0;
571 // For very small types, all the individual reads in the normal
572 // path perform poorly. We can do better, given efficient unaligned
573 // load/store, by loading a larger chunk and reversing a register.
575 // Ideally LLVM would do this for us, as it knows better than we do
576 // whether unaligned reads are efficient (since that changes between
577 // different ARM versions, for example) and what the best chunk size
578 // would be. Unfortunately, as of LLVM 4.0 (2017-05) it only unrolls
579 // the loop, so we need to do this ourselves. (Hypothesis: reverse
580 // is troublesome because the sides can be aligned differently --
581 // will be, when the length is odd -- so there's no way of emitting
582 // pre- and postludes to use fully-aligned SIMD in the middle.)
584 let fast_unaligned
= cfg
!(any(target_arch
= "x86", target_arch
= "x86_64"));
586 if fast_unaligned
&& mem
::size_of
::<T
>() == 1 {
587 // Use the llvm.bswap intrinsic to reverse u8s in a usize
588 let chunk
= mem
::size_of
::<usize>();
589 while i
+ chunk
- 1 < ln
/ 2 {
590 // SAFETY: There are several things to check here:
592 // - Note that `chunk` is either 4 or 8 due to the cfg check
593 // above. So `chunk - 1` is positive.
594 // - Indexing with index `i` is fine as the loop check guarantees
595 // `i + chunk - 1 < ln / 2`
596 // <=> `i < ln / 2 - (chunk - 1) < ln / 2 < ln`.
597 // - Indexing with index `ln - i - chunk = ln - (i + chunk)` is fine:
598 // - `i + chunk > 0` is trivially true.
599 // - The loop check guarantees:
600 // `i + chunk - 1 < ln / 2`
601 // <=> `i + chunk ≤ ln / 2 ≤ ln`, thus subtraction does not underflow.
602 // - The `read_unaligned` and `write_unaligned` calls are fine:
603 // - `pa` points to index `i` where `i < ln / 2 - (chunk - 1)`
604 // (see above) and `pb` points to index `ln - i - chunk`, so
605 // both are at least `chunk`
606 // many bytes away from the end of `self`.
607 // - Any initialized memory is valid `usize`.
609 let pa
: *mut T
= self.get_unchecked_mut(i
);
610 let pb
: *mut T
= self.get_unchecked_mut(ln
- i
- chunk
);
611 let va
= ptr
::read_unaligned(pa
as *mut usize);
612 let vb
= ptr
::read_unaligned(pb
as *mut usize);
613 ptr
::write_unaligned(pa
as *mut usize, vb
.swap_bytes());
614 ptr
::write_unaligned(pb
as *mut usize, va
.swap_bytes());
620 if fast_unaligned
&& mem
::size_of
::<T
>() == 2 {
621 // Use rotate-by-16 to reverse u16s in a u32
622 let chunk
= mem
::size_of
::<u32>() / 2;
623 while i
+ chunk
- 1 < ln
/ 2 {
624 // SAFETY: An unaligned u32 can be read from `i` if `i + 1 < ln`
625 // (and obviously `i < ln`), because each element is 2 bytes and
628 // `i + chunk - 1 < ln / 2` # while condition
629 // `i + 2 - 1 < ln / 2`
632 // Since it's less than the length divided by 2, then it must be
635 // This also means that the condition `0 < i + chunk <= ln` is
636 // always respected, ensuring the `pb` pointer can be used
639 let pa
: *mut T
= self.get_unchecked_mut(i
);
640 let pb
: *mut T
= self.get_unchecked_mut(ln
- i
- chunk
);
641 let va
= ptr
::read_unaligned(pa
as *mut u32);
642 let vb
= ptr
::read_unaligned(pb
as *mut u32);
643 ptr
::write_unaligned(pa
as *mut u32, vb
.rotate_left(16));
644 ptr
::write_unaligned(pb
as *mut u32, va
.rotate_left(16));
651 // SAFETY: `i` is inferior to half the length of the slice so
652 // accessing `i` and `ln - i - 1` is safe (`i` starts at 0 and
653 // will not go further than `ln / 2 - 1`).
654 // The resulting pointers `pa` and `pb` are therefore valid and
655 // aligned, and can be read from and written to.
657 // Unsafe swap to avoid the bounds check in safe swap.
658 let pa
: *mut T
= self.get_unchecked_mut(i
);
659 let pb
: *mut T
= self.get_unchecked_mut(ln
- i
- 1);
666 /// Returns an iterator over the slice.
671 /// let x = &[1, 2, 4];
672 /// let mut iterator = x.iter();
674 /// assert_eq!(iterator.next(), Some(&1));
675 /// assert_eq!(iterator.next(), Some(&2));
676 /// assert_eq!(iterator.next(), Some(&4));
677 /// assert_eq!(iterator.next(), None);
679 #[stable(feature = "rust1", since = "1.0.0")]
681 pub fn iter(&self) -> Iter
<'_
, T
> {
685 /// Returns an iterator that allows modifying each value.
690 /// let x = &mut [1, 2, 4];
691 /// for elem in x.iter_mut() {
694 /// assert_eq!(x, &[3, 4, 6]);
696 #[stable(feature = "rust1", since = "1.0.0")]
698 pub fn iter_mut(&mut self) -> IterMut
<'_
, T
> {
702 /// Returns an iterator over all contiguous windows of length
703 /// `size`. The windows overlap. If the slice is shorter than
704 /// `size`, the iterator returns no values.
708 /// Panics if `size` is 0.
713 /// let slice = ['r', 'u', 's', 't'];
714 /// let mut iter = slice.windows(2);
715 /// assert_eq!(iter.next().unwrap(), &['r', 'u']);
716 /// assert_eq!(iter.next().unwrap(), &['u', 's']);
717 /// assert_eq!(iter.next().unwrap(), &['s', 't']);
718 /// assert!(iter.next().is_none());
721 /// If the slice is shorter than `size`:
724 /// let slice = ['f', 'o', 'o'];
725 /// let mut iter = slice.windows(4);
726 /// assert!(iter.next().is_none());
728 #[stable(feature = "rust1", since = "1.0.0")]
730 pub fn windows(&self, size
: usize) -> Windows
<'_
, T
> {
732 Windows
::new(self, size
)
735 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
736 /// beginning of the slice.
738 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
739 /// slice, then the last chunk will not have length `chunk_size`.
741 /// See [`chunks_exact`] for a variant of this iterator that returns chunks of always exactly
742 /// `chunk_size` elements, and [`rchunks`] for the same iterator but starting at the end of the
747 /// Panics if `chunk_size` is 0.
752 /// let slice = ['l', 'o', 'r', 'e', 'm'];
753 /// let mut iter = slice.chunks(2);
754 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
755 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
756 /// assert_eq!(iter.next().unwrap(), &['m']);
757 /// assert!(iter.next().is_none());
760 /// [`chunks_exact`]: #method.chunks_exact
761 /// [`rchunks`]: #method.rchunks
762 #[stable(feature = "rust1", since = "1.0.0")]
764 pub fn chunks(&self, chunk_size
: usize) -> Chunks
<'_
, T
> {
765 assert_ne
!(chunk_size
, 0);
766 Chunks
::new(self, chunk_size
)
769 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
770 /// beginning of the slice.
772 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
773 /// length of the slice, then the last chunk will not have length `chunk_size`.
775 /// See [`chunks_exact_mut`] for a variant of this iterator that returns chunks of always
776 /// exactly `chunk_size` elements, and [`rchunks_mut`] for the same iterator but starting at
777 /// the end of the slice.
781 /// Panics if `chunk_size` is 0.
786 /// let v = &mut [0, 0, 0, 0, 0];
787 /// let mut count = 1;
789 /// for chunk in v.chunks_mut(2) {
790 /// for elem in chunk.iter_mut() {
795 /// assert_eq!(v, &[1, 1, 2, 2, 3]);
798 /// [`chunks_exact_mut`]: #method.chunks_exact_mut
799 /// [`rchunks_mut`]: #method.rchunks_mut
800 #[stable(feature = "rust1", since = "1.0.0")]
802 pub fn chunks_mut(&mut self, chunk_size
: usize) -> ChunksMut
<'_
, T
> {
803 assert_ne
!(chunk_size
, 0);
804 ChunksMut
::new(self, chunk_size
)
807 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
808 /// beginning of the slice.
810 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
811 /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
812 /// from the `remainder` function of the iterator.
814 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
815 /// resulting code better than in the case of [`chunks`].
817 /// See [`chunks`] for a variant of this iterator that also returns the remainder as a smaller
818 /// chunk, and [`rchunks_exact`] for the same iterator but starting at the end of the slice.
822 /// Panics if `chunk_size` is 0.
827 /// let slice = ['l', 'o', 'r', 'e', 'm'];
828 /// let mut iter = slice.chunks_exact(2);
829 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
830 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
831 /// assert!(iter.next().is_none());
832 /// assert_eq!(iter.remainder(), &['m']);
835 /// [`chunks`]: #method.chunks
836 /// [`rchunks_exact`]: #method.rchunks_exact
837 #[stable(feature = "chunks_exact", since = "1.31.0")]
839 pub fn chunks_exact(&self, chunk_size
: usize) -> ChunksExact
<'_
, T
> {
840 assert_ne
!(chunk_size
, 0);
841 ChunksExact
::new(self, chunk_size
)
844 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
845 /// beginning of the slice.
847 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
848 /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
849 /// retrieved from the `into_remainder` function of the iterator.
851 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
852 /// resulting code better than in the case of [`chunks_mut`].
854 /// See [`chunks_mut`] for a variant of this iterator that also returns the remainder as a
855 /// smaller chunk, and [`rchunks_exact_mut`] for the same iterator but starting at the end of
860 /// Panics if `chunk_size` is 0.
865 /// let v = &mut [0, 0, 0, 0, 0];
866 /// let mut count = 1;
868 /// for chunk in v.chunks_exact_mut(2) {
869 /// for elem in chunk.iter_mut() {
874 /// assert_eq!(v, &[1, 1, 2, 2, 0]);
877 /// [`chunks_mut`]: #method.chunks_mut
878 /// [`rchunks_exact_mut`]: #method.rchunks_exact_mut
879 #[stable(feature = "chunks_exact", since = "1.31.0")]
881 pub fn chunks_exact_mut(&mut self, chunk_size
: usize) -> ChunksExactMut
<'_
, T
> {
882 assert_ne
!(chunk_size
, 0);
883 ChunksExactMut
::new(self, chunk_size
)
886 /// Returns an iterator over `N` elements of the slice at a time, starting at the
887 /// beginning of the slice.
889 /// The chunks are array references and do not overlap. If `N` does not divide the
890 /// length of the slice, then the last up to `N-1` elements will be omitted and can be
891 /// retrieved from the `remainder` function of the iterator.
893 /// This method is the const generic equivalent of [`chunks_exact`].
897 /// Panics if `N` is 0. This check will most probably get changed to a compile time
898 /// error before this method gets stabilized.
903 /// #![feature(array_chunks)]
904 /// let slice = ['l', 'o', 'r', 'e', 'm'];
905 /// let mut iter = slice.array_chunks();
906 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
907 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
908 /// assert!(iter.next().is_none());
909 /// assert_eq!(iter.remainder(), &['m']);
912 /// [`chunks_exact`]: #method.chunks_exact
913 #[unstable(feature = "array_chunks", issue = "74985")]
915 pub fn array_chunks
<const N
: usize>(&self) -> ArrayChunks
<'_
, T
, N
> {
917 ArrayChunks
::new(self)
920 /// Returns an iterator over `N` elements of the slice at a time, starting at the
921 /// beginning of the slice.
923 /// The chunks are mutable array references and do not overlap. If `N` does not divide
924 /// the length of the slice, then the last up to `N-1` elements will be omitted and
925 /// can be retrieved from the `into_remainder` function of the iterator.
927 /// This method is the const generic equivalent of [`chunks_exact_mut`].
931 /// Panics if `N` is 0. This check will most probably get changed to a compile time
932 /// error before this method gets stabilized.
937 /// #![feature(array_chunks)]
938 /// let v = &mut [0, 0, 0, 0, 0];
939 /// let mut count = 1;
941 /// for chunk in v.array_chunks_mut() {
942 /// *chunk = [count; 2];
945 /// assert_eq!(v, &[1, 1, 2, 2, 0]);
948 /// [`chunks_exact_mut`]: #method.chunks_exact_mut
949 #[unstable(feature = "array_chunks", issue = "74985")]
951 pub fn array_chunks_mut
<const N
: usize>(&mut self) -> ArrayChunksMut
<'_
, T
, N
> {
953 ArrayChunksMut
::new(self)
956 /// Returns an iterator over overlapping windows of `N` elements of a slice,
957 /// starting at the beginning of the slice.
959 /// This is the const generic equivalent of [`windows`].
961 /// If `N` is greater than the size of the slice, it will return no windows.
965 /// Panics if `N` is 0. This check will most probably get changed to a compile time
966 /// error before this method gets stabilized.
971 /// #![feature(array_windows)]
972 /// let slice = [0, 1, 2, 3];
973 /// let mut iter = slice.array_windows();
974 /// assert_eq!(iter.next().unwrap(), &[0, 1]);
975 /// assert_eq!(iter.next().unwrap(), &[1, 2]);
976 /// assert_eq!(iter.next().unwrap(), &[2, 3]);
977 /// assert!(iter.next().is_none());
980 /// [`windows`]: #method.windows
981 #[unstable(feature = "array_windows", issue = "75027")]
983 pub fn array_windows
<const N
: usize>(&self) -> ArrayWindows
<'_
, T
, N
> {
985 ArrayWindows
::new(self)
988 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
991 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
992 /// slice, then the last chunk will not have length `chunk_size`.
994 /// See [`rchunks_exact`] for a variant of this iterator that returns chunks of always exactly
995 /// `chunk_size` elements, and [`chunks`] for the same iterator but starting at the beginning
1000 /// Panics if `chunk_size` is 0.
1005 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1006 /// let mut iter = slice.rchunks(2);
1007 /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
1008 /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
1009 /// assert_eq!(iter.next().unwrap(), &['l']);
1010 /// assert!(iter.next().is_none());
1013 /// [`rchunks_exact`]: #method.rchunks_exact
1014 /// [`chunks`]: #method.chunks
1015 #[stable(feature = "rchunks", since = "1.31.0")]
1017 pub fn rchunks(&self, chunk_size
: usize) -> RChunks
<'_
, T
> {
1018 assert
!(chunk_size
!= 0);
1019 RChunks
::new(self, chunk_size
)
1022 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1025 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1026 /// length of the slice, then the last chunk will not have length `chunk_size`.
1028 /// See [`rchunks_exact_mut`] for a variant of this iterator that returns chunks of always
1029 /// exactly `chunk_size` elements, and [`chunks_mut`] for the same iterator but starting at the
1030 /// beginning of the slice.
1034 /// Panics if `chunk_size` is 0.
1039 /// let v = &mut [0, 0, 0, 0, 0];
1040 /// let mut count = 1;
1042 /// for chunk in v.rchunks_mut(2) {
1043 /// for elem in chunk.iter_mut() {
1048 /// assert_eq!(v, &[3, 2, 2, 1, 1]);
1051 /// [`rchunks_exact_mut`]: #method.rchunks_exact_mut
1052 /// [`chunks_mut`]: #method.chunks_mut
1053 #[stable(feature = "rchunks", since = "1.31.0")]
1055 pub fn rchunks_mut(&mut self, chunk_size
: usize) -> RChunksMut
<'_
, T
> {
1056 assert
!(chunk_size
!= 0);
1057 RChunksMut
::new(self, chunk_size
)
1060 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1061 /// end of the slice.
1063 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1064 /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
1065 /// from the `remainder` function of the iterator.
1067 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1068 /// resulting code better than in the case of [`chunks`].
1070 /// See [`rchunks`] for a variant of this iterator that also returns the remainder as a smaller
1071 /// chunk, and [`chunks_exact`] for the same iterator but starting at the beginning of the
1076 /// Panics if `chunk_size` is 0.
1081 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1082 /// let mut iter = slice.rchunks_exact(2);
1083 /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
1084 /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
1085 /// assert!(iter.next().is_none());
1086 /// assert_eq!(iter.remainder(), &['l']);
1089 /// [`chunks`]: #method.chunks
1090 /// [`rchunks`]: #method.rchunks
1091 /// [`chunks_exact`]: #method.chunks_exact
1092 #[stable(feature = "rchunks", since = "1.31.0")]
1094 pub fn rchunks_exact(&self, chunk_size
: usize) -> RChunksExact
<'_
, T
> {
1095 assert
!(chunk_size
!= 0);
1096 RChunksExact
::new(self, chunk_size
)
1099 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1102 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1103 /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
1104 /// retrieved from the `into_remainder` function of the iterator.
1106 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1107 /// resulting code better than in the case of [`chunks_mut`].
1109 /// See [`rchunks_mut`] for a variant of this iterator that also returns the remainder as a
1110 /// smaller chunk, and [`chunks_exact_mut`] for the same iterator but starting at the beginning
1115 /// Panics if `chunk_size` is 0.
1120 /// let v = &mut [0, 0, 0, 0, 0];
1121 /// let mut count = 1;
1123 /// for chunk in v.rchunks_exact_mut(2) {
1124 /// for elem in chunk.iter_mut() {
1129 /// assert_eq!(v, &[0, 2, 2, 1, 1]);
1132 /// [`chunks_mut`]: #method.chunks_mut
1133 /// [`rchunks_mut`]: #method.rchunks_mut
1134 /// [`chunks_exact_mut`]: #method.chunks_exact_mut
1135 #[stable(feature = "rchunks", since = "1.31.0")]
1137 pub fn rchunks_exact_mut(&mut self, chunk_size
: usize) -> RChunksExactMut
<'_
, T
> {
1138 assert
!(chunk_size
!= 0);
1139 RChunksExactMut
::new(self, chunk_size
)
1142 /// Divides one slice into two at an index.
1144 /// The first will contain all indices from `[0, mid)` (excluding
1145 /// the index `mid` itself) and the second will contain all
1146 /// indices from `[mid, len)` (excluding the index `len` itself).
1150 /// Panics if `mid > len`.
1155 /// let v = [1, 2, 3, 4, 5, 6];
1158 /// let (left, right) = v.split_at(0);
1159 /// assert_eq!(left, []);
1160 /// assert_eq!(right, [1, 2, 3, 4, 5, 6]);
1164 /// let (left, right) = v.split_at(2);
1165 /// assert_eq!(left, [1, 2]);
1166 /// assert_eq!(right, [3, 4, 5, 6]);
1170 /// let (left, right) = v.split_at(6);
1171 /// assert_eq!(left, [1, 2, 3, 4, 5, 6]);
1172 /// assert_eq!(right, []);
1175 #[stable(feature = "rust1", since = "1.0.0")]
1177 pub fn split_at(&self, mid
: usize) -> (&[T
], &[T
]) {
1178 assert
!(mid
<= self.len());
1179 // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which
1180 // fulfills the requirements of `from_raw_parts_mut`.
1181 unsafe { self.split_at_unchecked(mid) }
1184 /// Divides one mutable slice into two at an index.
1186 /// The first will contain all indices from `[0, mid)` (excluding
1187 /// the index `mid` itself) and the second will contain all
1188 /// indices from `[mid, len)` (excluding the index `len` itself).
1192 /// Panics if `mid > len`.
1197 /// let mut v = [1, 0, 3, 0, 5, 6];
1198 /// // scoped to restrict the lifetime of the borrows
1200 /// let (left, right) = v.split_at_mut(2);
1201 /// assert_eq!(left, [1, 0]);
1202 /// assert_eq!(right, [3, 0, 5, 6]);
1206 /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
1208 #[stable(feature = "rust1", since = "1.0.0")]
1210 pub fn split_at_mut(&mut self, mid
: usize) -> (&mut [T
], &mut [T
]) {
1211 assert
!(mid
<= self.len());
1212 // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which
1213 // fulfills the requirements of `from_raw_parts_mut`.
1214 unsafe { self.split_at_mut_unchecked(mid) }
1217 /// Divides one slice into two at an index, without doing bounds checking.
1219 /// The first will contain all indices from `[0, mid)` (excluding
1220 /// the index `mid` itself) and the second will contain all
1221 /// indices from `[mid, len)` (excluding the index `len` itself).
1223 /// For a safe alternative see [`split_at`].
1227 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
1228 /// even if the resulting reference is not used. The caller has to ensure that
1229 /// `0 <= mid <= self.len()`.
1231 /// [`split_at`]: #method.split_at
1232 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1237 /// #![feature(slice_split_at_unchecked)]
1239 /// let v = [1, 2, 3, 4, 5, 6];
1242 /// let (left, right) = v.split_at_unchecked(0);
1243 /// assert_eq!(left, []);
1244 /// assert_eq!(right, [1, 2, 3, 4, 5, 6]);
1248 /// let (left, right) = v.split_at_unchecked(2);
1249 /// assert_eq!(left, [1, 2]);
1250 /// assert_eq!(right, [3, 4, 5, 6]);
1254 /// let (left, right) = v.split_at_unchecked(6);
1255 /// assert_eq!(left, [1, 2, 3, 4, 5, 6]);
1256 /// assert_eq!(right, []);
1259 #[unstable(feature = "slice_split_at_unchecked", reason = "new API", issue = "76014")]
1261 unsafe fn split_at_unchecked(&self, mid
: usize) -> (&[T
], &[T
]) {
1262 // SAFETY: Caller has to check that `0 <= mid <= self.len()`
1263 unsafe { (self.get_unchecked(..mid), self.get_unchecked(mid..)) }
1266 /// Divides one mutable slice into two at an index, without doing bounds checking.
1268 /// The first will contain all indices from `[0, mid)` (excluding
1269 /// the index `mid` itself) and the second will contain all
1270 /// indices from `[mid, len)` (excluding the index `len` itself).
1272 /// For a safe alternative see [`split_at_mut`].
1276 /// Calling this method with an out-of-bounds index is *[undefined behavior]*
1277 /// even if the resulting reference is not used. The caller has to ensure that
1278 /// `0 <= mid <= self.len()`.
1280 /// [`split_at_mut`]: #method.split_at_mut
1281 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1286 /// #![feature(slice_split_at_unchecked)]
1288 /// let mut v = [1, 0, 3, 0, 5, 6];
1289 /// // scoped to restrict the lifetime of the borrows
1291 /// let (left, right) = v.split_at_mut_unchecked(2);
1292 /// assert_eq!(left, [1, 0]);
1293 /// assert_eq!(right, [3, 0, 5, 6]);
1297 /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
1299 #[unstable(feature = "slice_split_at_unchecked", reason = "new API", issue = "76014")]
1301 unsafe fn split_at_mut_unchecked(&mut self, mid
: usize) -> (&mut [T
], &mut [T
]) {
1302 let len
= self.len();
1303 let ptr
= self.as_mut_ptr();
1305 // SAFETY: Caller has to check that `0 <= mid <= self.len()`.
1307 // `[ptr; mid]` and `[mid; len]` are not overlapping, so returning a mutable reference
1309 unsafe { (from_raw_parts_mut(ptr, mid), from_raw_parts_mut(ptr.add(mid), len - mid)) }
1312 /// Returns an iterator over subslices separated by elements that match
1313 /// `pred`. The matched element is not contained in the subslices.
1318 /// let slice = [10, 40, 33, 20];
1319 /// let mut iter = slice.split(|num| num % 3 == 0);
1321 /// assert_eq!(iter.next().unwrap(), &[10, 40]);
1322 /// assert_eq!(iter.next().unwrap(), &[20]);
1323 /// assert!(iter.next().is_none());
1326 /// If the first element is matched, an empty slice will be the first item
1327 /// returned by the iterator. Similarly, if the last element in the slice
1328 /// is matched, an empty slice will be the last item returned by the
1332 /// let slice = [10, 40, 33];
1333 /// let mut iter = slice.split(|num| num % 3 == 0);
1335 /// assert_eq!(iter.next().unwrap(), &[10, 40]);
1336 /// assert_eq!(iter.next().unwrap(), &[]);
1337 /// assert!(iter.next().is_none());
1340 /// If two matched elements are directly adjacent, an empty slice will be
1341 /// present between them:
1344 /// let slice = [10, 6, 33, 20];
1345 /// let mut iter = slice.split(|num| num % 3 == 0);
1347 /// assert_eq!(iter.next().unwrap(), &[10]);
1348 /// assert_eq!(iter.next().unwrap(), &[]);
1349 /// assert_eq!(iter.next().unwrap(), &[20]);
1350 /// assert!(iter.next().is_none());
1352 #[stable(feature = "rust1", since = "1.0.0")]
1354 pub fn split
<F
>(&self, pred
: F
) -> Split
<'_
, T
, F
>
1356 F
: FnMut(&T
) -> bool
,
1358 Split
::new(self, pred
)
1361 /// Returns an iterator over mutable subslices separated by elements that
1362 /// match `pred`. The matched element is not contained in the subslices.
1367 /// let mut v = [10, 40, 30, 20, 60, 50];
1369 /// for group in v.split_mut(|num| *num % 3 == 0) {
1372 /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
1374 #[stable(feature = "rust1", since = "1.0.0")]
1376 pub fn split_mut
<F
>(&mut self, pred
: F
) -> SplitMut
<'_
, T
, F
>
1378 F
: FnMut(&T
) -> bool
,
1380 SplitMut
::new(self, pred
)
1383 /// Returns an iterator over subslices separated by elements that match
1384 /// `pred`. The matched element is contained in the end of the previous
1385 /// subslice as a terminator.
1390 /// #![feature(split_inclusive)]
1391 /// let slice = [10, 40, 33, 20];
1392 /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
1394 /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
1395 /// assert_eq!(iter.next().unwrap(), &[20]);
1396 /// assert!(iter.next().is_none());
1399 /// If the last element of the slice is matched,
1400 /// that element will be considered the terminator of the preceding slice.
1401 /// That slice will be the last item returned by the iterator.
1404 /// #![feature(split_inclusive)]
1405 /// let slice = [3, 10, 40, 33];
1406 /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
1408 /// assert_eq!(iter.next().unwrap(), &[3]);
1409 /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
1410 /// assert!(iter.next().is_none());
1412 #[unstable(feature = "split_inclusive", issue = "72360")]
1414 pub fn split_inclusive
<F
>(&self, pred
: F
) -> SplitInclusive
<'_
, T
, F
>
1416 F
: FnMut(&T
) -> bool
,
1418 SplitInclusive
::new(self, pred
)
1421 /// Returns an iterator over mutable subslices separated by elements that
1422 /// match `pred`. The matched element is contained in the previous
1423 /// subslice as a terminator.
1428 /// #![feature(split_inclusive)]
1429 /// let mut v = [10, 40, 30, 20, 60, 50];
1431 /// for group in v.split_inclusive_mut(|num| *num % 3 == 0) {
1432 /// let terminator_idx = group.len()-1;
1433 /// group[terminator_idx] = 1;
1435 /// assert_eq!(v, [10, 40, 1, 20, 1, 1]);
1437 #[unstable(feature = "split_inclusive", issue = "72360")]
1439 pub fn split_inclusive_mut
<F
>(&mut self, pred
: F
) -> SplitInclusiveMut
<'_
, T
, F
>
1441 F
: FnMut(&T
) -> bool
,
1443 SplitInclusiveMut
::new(self, pred
)
1446 /// Returns an iterator over subslices separated by elements that match
1447 /// `pred`, starting at the end of the slice and working backwards.
1448 /// The matched element is not contained in the subslices.
1453 /// let slice = [11, 22, 33, 0, 44, 55];
1454 /// let mut iter = slice.rsplit(|num| *num == 0);
1456 /// assert_eq!(iter.next().unwrap(), &[44, 55]);
1457 /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
1458 /// assert_eq!(iter.next(), None);
1461 /// As with `split()`, if the first or last element is matched, an empty
1462 /// slice will be the first (or last) item returned by the iterator.
1465 /// let v = &[0, 1, 1, 2, 3, 5, 8];
1466 /// let mut it = v.rsplit(|n| *n % 2 == 0);
1467 /// assert_eq!(it.next().unwrap(), &[]);
1468 /// assert_eq!(it.next().unwrap(), &[3, 5]);
1469 /// assert_eq!(it.next().unwrap(), &[1, 1]);
1470 /// assert_eq!(it.next().unwrap(), &[]);
1471 /// assert_eq!(it.next(), None);
1473 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1475 pub fn rsplit
<F
>(&self, pred
: F
) -> RSplit
<'_
, T
, F
>
1477 F
: FnMut(&T
) -> bool
,
1479 RSplit
::new(self, pred
)
1482 /// Returns an iterator over mutable subslices separated by elements that
1483 /// match `pred`, starting at the end of the slice and working
1484 /// backwards. The matched element is not contained in the subslices.
1489 /// let mut v = [100, 400, 300, 200, 600, 500];
1491 /// let mut count = 0;
1492 /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
1494 /// group[0] = count;
1496 /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
1499 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1501 pub fn rsplit_mut
<F
>(&mut self, pred
: F
) -> RSplitMut
<'_
, T
, F
>
1503 F
: FnMut(&T
) -> bool
,
1505 RSplitMut
::new(self, pred
)
1508 /// Returns an iterator over subslices separated by elements that match
1509 /// `pred`, limited to returning at most `n` items. The matched element is
1510 /// not contained in the subslices.
1512 /// The last element returned, if any, will contain the remainder of the
1517 /// Print the slice split once by numbers divisible by 3 (i.e., `[10, 40]`,
1518 /// `[20, 60, 50]`):
1521 /// let v = [10, 40, 30, 20, 60, 50];
1523 /// for group in v.splitn(2, |num| *num % 3 == 0) {
1524 /// println!("{:?}", group);
1527 #[stable(feature = "rust1", since = "1.0.0")]
1529 pub fn splitn
<F
>(&self, n
: usize, pred
: F
) -> SplitN
<'_
, T
, F
>
1531 F
: FnMut(&T
) -> bool
,
1533 SplitN
::new(self.split(pred
), n
)
1536 /// Returns an iterator over subslices separated by elements that match
1537 /// `pred`, limited to returning at most `n` items. The matched element is
1538 /// not contained in the subslices.
1540 /// The last element returned, if any, will contain the remainder of the
1546 /// let mut v = [10, 40, 30, 20, 60, 50];
1548 /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
1551 /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
1553 #[stable(feature = "rust1", since = "1.0.0")]
1555 pub fn splitn_mut
<F
>(&mut self, n
: usize, pred
: F
) -> SplitNMut
<'_
, T
, F
>
1557 F
: FnMut(&T
) -> bool
,
1559 SplitNMut
::new(self.split_mut(pred
), n
)
1562 /// Returns an iterator over subslices separated by elements that match
1563 /// `pred` limited to returning at most `n` items. This starts at the end of
1564 /// the slice and works backwards. The matched element is not contained in
1567 /// The last element returned, if any, will contain the remainder of the
1572 /// Print the slice split once, starting from the end, by numbers divisible
1573 /// by 3 (i.e., `[50]`, `[10, 40, 30, 20]`):
1576 /// let v = [10, 40, 30, 20, 60, 50];
1578 /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
1579 /// println!("{:?}", group);
1582 #[stable(feature = "rust1", since = "1.0.0")]
1584 pub fn rsplitn
<F
>(&self, n
: usize, pred
: F
) -> RSplitN
<'_
, T
, F
>
1586 F
: FnMut(&T
) -> bool
,
1588 RSplitN
::new(self.rsplit(pred
), n
)
1591 /// Returns an iterator over subslices separated by elements that match
1592 /// `pred` limited to returning at most `n` items. This starts at the end of
1593 /// the slice and works backwards. The matched element is not contained in
1596 /// The last element returned, if any, will contain the remainder of the
1602 /// let mut s = [10, 40, 30, 20, 60, 50];
1604 /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
1607 /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
1609 #[stable(feature = "rust1", since = "1.0.0")]
1611 pub fn rsplitn_mut
<F
>(&mut self, n
: usize, pred
: F
) -> RSplitNMut
<'_
, T
, F
>
1613 F
: FnMut(&T
) -> bool
,
1615 RSplitNMut
::new(self.rsplit_mut(pred
), n
)
1618 /// Returns `true` if the slice contains an element with the given value.
1623 /// let v = [10, 40, 30];
1624 /// assert!(v.contains(&30));
1625 /// assert!(!v.contains(&50));
1628 /// If you do not have an `&T`, but just an `&U` such that `T: Borrow<U>`
1629 /// (e.g. `String: Borrow<str>`), you can use `iter().any`:
1632 /// let v = [String::from("hello"), String::from("world")]; // slice of `String`
1633 /// assert!(v.iter().any(|e| e == "hello")); // search with `&str`
1634 /// assert!(!v.iter().any(|e| e == "hi"));
1636 #[stable(feature = "rust1", since = "1.0.0")]
1638 pub fn contains(&self, x
: &T
) -> bool
1642 cmp
::SliceContains
::slice_contains(x
, self)
1645 /// Returns `true` if `needle` is a prefix of the slice.
1650 /// let v = [10, 40, 30];
1651 /// assert!(v.starts_with(&[10]));
1652 /// assert!(v.starts_with(&[10, 40]));
1653 /// assert!(!v.starts_with(&[50]));
1654 /// assert!(!v.starts_with(&[10, 50]));
1657 /// Always returns `true` if `needle` is an empty slice:
1660 /// let v = &[10, 40, 30];
1661 /// assert!(v.starts_with(&[]));
1662 /// let v: &[u8] = &[];
1663 /// assert!(v.starts_with(&[]));
1665 #[stable(feature = "rust1", since = "1.0.0")]
1666 pub fn starts_with(&self, needle
: &[T
]) -> bool
1670 let n
= needle
.len();
1671 self.len() >= n
&& needle
== &self[..n
]
1674 /// Returns `true` if `needle` is a suffix of the slice.
1679 /// let v = [10, 40, 30];
1680 /// assert!(v.ends_with(&[30]));
1681 /// assert!(v.ends_with(&[40, 30]));
1682 /// assert!(!v.ends_with(&[50]));
1683 /// assert!(!v.ends_with(&[50, 30]));
1686 /// Always returns `true` if `needle` is an empty slice:
1689 /// let v = &[10, 40, 30];
1690 /// assert!(v.ends_with(&[]));
1691 /// let v: &[u8] = &[];
1692 /// assert!(v.ends_with(&[]));
1694 #[stable(feature = "rust1", since = "1.0.0")]
1695 pub fn ends_with(&self, needle
: &[T
]) -> bool
1699 let (m
, n
) = (self.len(), needle
.len());
1700 m
>= n
&& needle
== &self[m
- n
..]
1703 /// Returns a subslice with the prefix removed.
1705 /// This method returns [`None`] if slice does not start with `prefix`.
1706 /// Also it returns the original slice if `prefix` is an empty slice.
1711 /// #![feature(slice_strip)]
1712 /// let v = &[10, 40, 30];
1713 /// assert_eq!(v.strip_prefix(&[10]), Some(&[40, 30][..]));
1714 /// assert_eq!(v.strip_prefix(&[10, 40]), Some(&[30][..]));
1715 /// assert_eq!(v.strip_prefix(&[50]), None);
1716 /// assert_eq!(v.strip_prefix(&[10, 50]), None);
1718 #[must_use = "returns the subslice without modifying the original"]
1719 #[unstable(feature = "slice_strip", issue = "73413")]
1720 pub fn strip_prefix(&self, prefix
: &[T
]) -> Option
<&[T
]>
1724 let n
= prefix
.len();
1725 if n
<= self.len() {
1726 let (head
, tail
) = self.split_at(n
);
1734 /// Returns a subslice with the suffix removed.
1736 /// This method returns [`None`] if slice does not end with `suffix`.
1737 /// Also it returns the original slice if `suffix` is an empty slice
1742 /// #![feature(slice_strip)]
1743 /// let v = &[10, 40, 30];
1744 /// assert_eq!(v.strip_suffix(&[30]), Some(&[10, 40][..]));
1745 /// assert_eq!(v.strip_suffix(&[40, 30]), Some(&[10][..]));
1746 /// assert_eq!(v.strip_suffix(&[50]), None);
1747 /// assert_eq!(v.strip_suffix(&[50, 30]), None);
1749 #[must_use = "returns the subslice without modifying the original"]
1750 #[unstable(feature = "slice_strip", issue = "73413")]
1751 pub fn strip_suffix(&self, suffix
: &[T
]) -> Option
<&[T
]>
1755 let (len
, n
) = (self.len(), suffix
.len());
1757 let (head
, tail
) = self.split_at(len
- n
);
1765 /// Binary searches this sorted slice for a given element.
1767 /// If the value is found then [`Result::Ok`] is returned, containing the
1768 /// index of the matching element. If there are multiple matches, then any
1769 /// one of the matches could be returned. If the value is not found then
1770 /// [`Result::Err`] is returned, containing the index where a matching
1771 /// element could be inserted while maintaining sorted order.
1775 /// Looks up a series of four elements. The first is found, with a
1776 /// uniquely determined position; the second and third are not
1777 /// found; the fourth could match any position in `[1, 4]`.
1780 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1782 /// assert_eq!(s.binary_search(&13), Ok(9));
1783 /// assert_eq!(s.binary_search(&4), Err(7));
1784 /// assert_eq!(s.binary_search(&100), Err(13));
1785 /// let r = s.binary_search(&1);
1786 /// assert!(match r { Ok(1..=4) => true, _ => false, });
1789 /// If you want to insert an item to a sorted vector, while maintaining
1793 /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1795 /// let idx = s.binary_search(&num).unwrap_or_else(|x| x);
1796 /// s.insert(idx, num);
1797 /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
1799 #[stable(feature = "rust1", since = "1.0.0")]
1800 pub fn binary_search(&self, x
: &T
) -> Result
<usize, usize>
1804 self.binary_search_by(|p
| p
.cmp(x
))
1807 /// Binary searches this sorted slice with a comparator function.
1809 /// The comparator function should implement an order consistent
1810 /// with the sort order of the underlying slice, returning an
1811 /// order code that indicates whether its argument is `Less`,
1812 /// `Equal` or `Greater` the desired target.
1814 /// If the value is found then [`Result::Ok`] is returned, containing the
1815 /// index of the matching element. If there are multiple matches, then any
1816 /// one of the matches could be returned. If the value is not found then
1817 /// [`Result::Err`] is returned, containing the index where a matching
1818 /// element could be inserted while maintaining sorted order.
1822 /// Looks up a series of four elements. The first is found, with a
1823 /// uniquely determined position; the second and third are not
1824 /// found; the fourth could match any position in `[1, 4]`.
1827 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1830 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
1832 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
1834 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
1836 /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
1837 /// assert!(match r { Ok(1..=4) => true, _ => false, });
1839 #[stable(feature = "rust1", since = "1.0.0")]
1841 pub fn binary_search_by
<'a
, F
>(&'a
self, mut f
: F
) -> Result
<usize, usize>
1843 F
: FnMut(&'a T
) -> Ordering
,
1846 let mut size
= s
.len();
1850 let mut base
= 0usize
;
1852 let half
= size
/ 2;
1853 let mid
= base
+ half
;
1854 // SAFETY: the call is made safe by the following inconstants:
1855 // - `mid >= 0`: by definition
1856 // - `mid < size`: `mid = size / 2 + size / 4 + size / 8 ...`
1857 let cmp
= f(unsafe { s.get_unchecked(mid) }
);
1858 base
= if cmp
== Greater { base }
else { mid }
;
1861 // SAFETY: base is always in [0, size) because base <= mid.
1862 let cmp
= f(unsafe { s.get_unchecked(base) }
);
1863 if cmp
== Equal { Ok(base) }
else { Err(base + (cmp == Less) as usize) }
1866 /// Binary searches this sorted slice with a key extraction function.
1868 /// Assumes that the slice is sorted by the key, for instance with
1869 /// [`sort_by_key`] using the same key extraction function.
1871 /// If the value is found then [`Result::Ok`] is returned, containing the
1872 /// index of the matching element. If there are multiple matches, then any
1873 /// one of the matches could be returned. If the value is not found then
1874 /// [`Result::Err`] is returned, containing the index where a matching
1875 /// element could be inserted while maintaining sorted order.
1877 /// [`sort_by_key`]: #method.sort_by_key
1881 /// Looks up a series of four elements in a slice of pairs sorted by
1882 /// their second elements. The first is found, with a uniquely
1883 /// determined position; the second and third are not found; the
1884 /// fourth could match any position in `[1, 4]`.
1887 /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
1888 /// (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
1889 /// (1, 21), (2, 34), (4, 55)];
1891 /// assert_eq!(s.binary_search_by_key(&13, |&(a,b)| b), Ok(9));
1892 /// assert_eq!(s.binary_search_by_key(&4, |&(a,b)| b), Err(7));
1893 /// assert_eq!(s.binary_search_by_key(&100, |&(a,b)| b), Err(13));
1894 /// let r = s.binary_search_by_key(&1, |&(a,b)| b);
1895 /// assert!(match r { Ok(1..=4) => true, _ => false, });
1897 #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
1899 pub fn binary_search_by_key
<'a
, B
, F
>(&'a
self, b
: &B
, mut f
: F
) -> Result
<usize, usize>
1901 F
: FnMut(&'a T
) -> B
,
1904 self.binary_search_by(|k
| f(k
).cmp(b
))
1907 /// Sorts the slice, but may not preserve the order of equal elements.
1909 /// This sort is unstable (i.e., may reorder equal elements), in-place
1910 /// (i.e., does not allocate), and *O*(*n* \* log(*n*)) worst-case.
1912 /// # Current implementation
1914 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1915 /// which combines the fast average case of randomized quicksort with the fast worst case of
1916 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1917 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1918 /// deterministic behavior.
1920 /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
1921 /// slice consists of several concatenated sorted sequences.
1926 /// let mut v = [-5, 4, 1, -3, 2];
1928 /// v.sort_unstable();
1929 /// assert!(v == [-5, -3, 1, 2, 4]);
1932 /// [pdqsort]: https://github.com/orlp/pdqsort
1933 #[stable(feature = "sort_unstable", since = "1.20.0")]
1935 pub fn sort_unstable(&mut self)
1939 sort
::quicksort(self, |a
, b
| a
.lt(b
));
1942 /// Sorts the slice with a comparator function, but may not preserve the order of equal
1945 /// This sort is unstable (i.e., may reorder equal elements), in-place
1946 /// (i.e., does not allocate), and *O*(*n* \* log(*n*)) worst-case.
1948 /// The comparator function must define a total ordering for the elements in the slice. If
1949 /// the ordering is not total, the order of the elements is unspecified. An order is a
1950 /// total order if it is (for all a, b and c):
1952 /// * total and antisymmetric: exactly one of a < b, a == b or a > b is true; and
1953 /// * transitive, a < b and b < c implies a < c. The same must hold for both == and >.
1955 /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use
1956 /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`.
1959 /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
1960 /// floats.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());
1961 /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
1964 /// # Current implementation
1966 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1967 /// which combines the fast average case of randomized quicksort with the fast worst case of
1968 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1969 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1970 /// deterministic behavior.
1972 /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
1973 /// slice consists of several concatenated sorted sequences.
1978 /// let mut v = [5, 4, 1, 3, 2];
1979 /// v.sort_unstable_by(|a, b| a.cmp(b));
1980 /// assert!(v == [1, 2, 3, 4, 5]);
1982 /// // reverse sorting
1983 /// v.sort_unstable_by(|a, b| b.cmp(a));
1984 /// assert!(v == [5, 4, 3, 2, 1]);
1987 /// [pdqsort]: https://github.com/orlp/pdqsort
1988 #[stable(feature = "sort_unstable", since = "1.20.0")]
1990 pub fn sort_unstable_by
<F
>(&mut self, mut compare
: F
)
1992 F
: FnMut(&T
, &T
) -> Ordering
,
1994 sort
::quicksort(self, |a
, b
| compare(a
, b
) == Ordering
::Less
);
1997 /// Sorts the slice with a key extraction function, but may not preserve the order of equal
2000 /// This sort is unstable (i.e., may reorder equal elements), in-place
2001 /// (i.e., does not allocate), and *O*(m \* *n* \* log(*n*)) worst-case, where the key function is
2004 /// # Current implementation
2006 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
2007 /// which combines the fast average case of randomized quicksort with the fast worst case of
2008 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
2009 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
2010 /// deterministic behavior.
2012 /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key)
2013 /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_cached_key) in
2014 /// cases where the key function is expensive.
2019 /// let mut v = [-5i32, 4, 1, -3, 2];
2021 /// v.sort_unstable_by_key(|k| k.abs());
2022 /// assert!(v == [1, 2, -3, 4, -5]);
2025 /// [pdqsort]: https://github.com/orlp/pdqsort
2026 #[stable(feature = "sort_unstable", since = "1.20.0")]
2028 pub fn sort_unstable_by_key
<K
, F
>(&mut self, mut f
: F
)
2033 sort
::quicksort(self, |a
, b
| f(a
).lt(&f(b
)));
2036 /// Reorder the slice such that the element at `index` is at its final sorted position.
2038 /// This reordering has the additional property that any value at position `i < index` will be
2039 /// less than or equal to any value at a position `j > index`. Additionally, this reordering is
2040 /// unstable (i.e. any number of equal elements may end up at position `index`), in-place
2041 /// (i.e. does not allocate), and *O*(*n*) worst-case. This function is also/ known as "kth
2042 /// element" in other libraries. It returns a triplet of the following values: all elements less
2043 /// than the one at the given index, the value at the given index, and all elements greater than
2044 /// the one at the given index.
2046 /// # Current implementation
2048 /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
2049 /// used for [`sort_unstable`].
2051 /// [`sort_unstable`]: #method.sort_unstable
2055 /// Panics when `index >= len()`, meaning it always panics on empty slices.
2060 /// #![feature(slice_partition_at_index)]
2062 /// let mut v = [-5i32, 4, 1, -3, 2];
2064 /// // Find the median
2065 /// v.partition_at_index(2);
2067 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
2068 /// // about the specified index.
2069 /// assert!(v == [-3, -5, 1, 2, 4] ||
2070 /// v == [-5, -3, 1, 2, 4] ||
2071 /// v == [-3, -5, 1, 4, 2] ||
2072 /// v == [-5, -3, 1, 4, 2]);
2074 #[unstable(feature = "slice_partition_at_index", issue = "55300")]
2076 pub fn partition_at_index(&mut self, index
: usize) -> (&mut [T
], &mut T
, &mut [T
])
2080 let mut f
= |a
: &T
, b
: &T
| a
.lt(b
);
2081 sort
::partition_at_index(self, index
, &mut f
)
2084 /// Reorder the slice with a comparator function such that the element at `index` is at its
2085 /// final sorted position.
2087 /// This reordering has the additional property that any value at position `i < index` will be
2088 /// less than or equal to any value at a position `j > index` using the comparator function.
2089 /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
2090 /// position `index`), in-place (i.e. does not allocate), and *O*(*n*) worst-case. This function
2091 /// is also known as "kth element" in other libraries. It returns a triplet of the following
2092 /// values: all elements less than the one at the given index, the value at the given index,
2093 /// and all elements greater than the one at the given index, using the provided comparator
2096 /// # Current implementation
2098 /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
2099 /// used for [`sort_unstable`].
2101 /// [`sort_unstable`]: #method.sort_unstable
2105 /// Panics when `index >= len()`, meaning it always panics on empty slices.
2110 /// #![feature(slice_partition_at_index)]
2112 /// let mut v = [-5i32, 4, 1, -3, 2];
2114 /// // Find the median as if the slice were sorted in descending order.
2115 /// v.partition_at_index_by(2, |a, b| b.cmp(a));
2117 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
2118 /// // about the specified index.
2119 /// assert!(v == [2, 4, 1, -5, -3] ||
2120 /// v == [2, 4, 1, -3, -5] ||
2121 /// v == [4, 2, 1, -5, -3] ||
2122 /// v == [4, 2, 1, -3, -5]);
2124 #[unstable(feature = "slice_partition_at_index", issue = "55300")]
2126 pub fn partition_at_index_by
<F
>(
2130 ) -> (&mut [T
], &mut T
, &mut [T
])
2132 F
: FnMut(&T
, &T
) -> Ordering
,
2134 let mut f
= |a
: &T
, b
: &T
| compare(a
, b
) == Less
;
2135 sort
::partition_at_index(self, index
, &mut f
)
2138 /// Reorder the slice with a key extraction function such that the element at `index` is at its
2139 /// final sorted position.
2141 /// This reordering has the additional property that any value at position `i < index` will be
2142 /// less than or equal to any value at a position `j > index` using the key extraction function.
2143 /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
2144 /// position `index`), in-place (i.e. does not allocate), and *O*(*n*) worst-case. This function
2145 /// is also known as "kth element" in other libraries. It returns a triplet of the following
2146 /// values: all elements less than the one at the given index, the value at the given index, and
2147 /// all elements greater than the one at the given index, using the provided key extraction
2150 /// # Current implementation
2152 /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
2153 /// used for [`sort_unstable`].
2155 /// [`sort_unstable`]: #method.sort_unstable
2159 /// Panics when `index >= len()`, meaning it always panics on empty slices.
2164 /// #![feature(slice_partition_at_index)]
2166 /// let mut v = [-5i32, 4, 1, -3, 2];
2168 /// // Return the median as if the array were sorted according to absolute value.
2169 /// v.partition_at_index_by_key(2, |a| a.abs());
2171 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
2172 /// // about the specified index.
2173 /// assert!(v == [1, 2, -3, 4, -5] ||
2174 /// v == [1, 2, -3, -5, 4] ||
2175 /// v == [2, 1, -3, 4, -5] ||
2176 /// v == [2, 1, -3, -5, 4]);
2178 #[unstable(feature = "slice_partition_at_index", issue = "55300")]
2180 pub fn partition_at_index_by_key
<K
, F
>(
2184 ) -> (&mut [T
], &mut T
, &mut [T
])
2189 let mut g
= |a
: &T
, b
: &T
| f(a
).lt(&f(b
));
2190 sort
::partition_at_index(self, index
, &mut g
)
2193 /// Moves all consecutive repeated elements to the end of the slice according to the
2194 /// [`PartialEq`] trait implementation.
2196 /// Returns two slices. The first contains no consecutive repeated elements.
2197 /// The second contains all the duplicates in no specified order.
2199 /// If the slice is sorted, the first returned slice contains no duplicates.
2204 /// #![feature(slice_partition_dedup)]
2206 /// let mut slice = [1, 2, 2, 3, 3, 2, 1, 1];
2208 /// let (dedup, duplicates) = slice.partition_dedup();
2210 /// assert_eq!(dedup, [1, 2, 3, 2, 1]);
2211 /// assert_eq!(duplicates, [2, 3, 1]);
2213 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
2215 pub fn partition_dedup(&mut self) -> (&mut [T
], &mut [T
])
2219 self.partition_dedup_by(|a
, b
| a
== b
)
2222 /// Moves all but the first of consecutive elements to the end of the slice satisfying
2223 /// a given equality relation.
2225 /// Returns two slices. The first contains no consecutive repeated elements.
2226 /// The second contains all the duplicates in no specified order.
2228 /// The `same_bucket` function is passed references to two elements from the slice and
2229 /// must determine if the elements compare equal. The elements are passed in opposite order
2230 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is moved
2231 /// at the end of the slice.
2233 /// If the slice is sorted, the first returned slice contains no duplicates.
2238 /// #![feature(slice_partition_dedup)]
2240 /// let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];
2242 /// let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b));
2244 /// assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
2245 /// assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);
2247 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
2249 pub fn partition_dedup_by
<F
>(&mut self, mut same_bucket
: F
) -> (&mut [T
], &mut [T
])
2251 F
: FnMut(&mut T
, &mut T
) -> bool
,
2253 // Although we have a mutable reference to `self`, we cannot make
2254 // *arbitrary* changes. The `same_bucket` calls could panic, so we
2255 // must ensure that the slice is in a valid state at all times.
2257 // The way that we handle this is by using swaps; we iterate
2258 // over all the elements, swapping as we go so that at the end
2259 // the elements we wish to keep are in the front, and those we
2260 // wish to reject are at the back. We can then split the slice.
2261 // This operation is still `O(n)`.
2263 // Example: We start in this state, where `r` represents "next
2264 // read" and `w` represents "next_write`.
2267 // +---+---+---+---+---+---+
2268 // | 0 | 1 | 1 | 2 | 3 | 3 |
2269 // +---+---+---+---+---+---+
2272 // Comparing self[r] against self[w-1], this is not a duplicate, so
2273 // we swap self[r] and self[w] (no effect as r==w) and then increment both
2274 // r and w, leaving us with:
2277 // +---+---+---+---+---+---+
2278 // | 0 | 1 | 1 | 2 | 3 | 3 |
2279 // +---+---+---+---+---+---+
2282 // Comparing self[r] against self[w-1], this value is a duplicate,
2283 // so we increment `r` but leave everything else unchanged:
2286 // +---+---+---+---+---+---+
2287 // | 0 | 1 | 1 | 2 | 3 | 3 |
2288 // +---+---+---+---+---+---+
2291 // Comparing self[r] against self[w-1], this is not a duplicate,
2292 // so swap self[r] and self[w] and advance r and w:
2295 // +---+---+---+---+---+---+
2296 // | 0 | 1 | 2 | 1 | 3 | 3 |
2297 // +---+---+---+---+---+---+
2300 // Not a duplicate, repeat:
2303 // +---+---+---+---+---+---+
2304 // | 0 | 1 | 2 | 3 | 1 | 3 |
2305 // +---+---+---+---+---+---+
2308 // Duplicate, advance r. End of slice. Split at w.
2310 let len
= self.len();
2312 return (self, &mut []);
2315 let ptr
= self.as_mut_ptr();
2316 let mut next_read
: usize = 1;
2317 let mut next_write
: usize = 1;
2319 // SAFETY: the `while` condition guarantees `next_read` and `next_write`
2320 // are less than `len`, thus are inside `self`. `prev_ptr_write` points to
2321 // one element before `ptr_write`, but `next_write` starts at 1, so
2322 // `prev_ptr_write` is never less than 0 and is inside the slice.
2323 // This fulfils the requirements for dereferencing `ptr_read`, `prev_ptr_write`
2324 // and `ptr_write`, and for using `ptr.add(next_read)`, `ptr.add(next_write - 1)`
2325 // and `prev_ptr_write.offset(1)`.
2327 // `next_write` is also incremented at most once per loop at most meaning
2328 // no element is skipped when it may need to be swapped.
2330 // `ptr_read` and `prev_ptr_write` never point to the same element. This
2331 // is required for `&mut *ptr_read`, `&mut *prev_ptr_write` to be safe.
2332 // The explanation is simply that `next_read >= next_write` is always true,
2333 // thus `next_read > next_write - 1` is too.
2335 // Avoid bounds checks by using raw pointers.
2336 while next_read
< len
{
2337 let ptr_read
= ptr
.add(next_read
);
2338 let prev_ptr_write
= ptr
.add(next_write
- 1);
2339 if !same_bucket(&mut *ptr_read
, &mut *prev_ptr_write
) {
2340 if next_read
!= next_write
{
2341 let ptr_write
= prev_ptr_write
.offset(1);
2342 mem
::swap(&mut *ptr_read
, &mut *ptr_write
);
2350 self.split_at_mut(next_write
)
2353 /// Moves all but the first of consecutive elements to the end of the slice that resolve
2354 /// to the same key.
2356 /// Returns two slices. The first contains no consecutive repeated elements.
2357 /// The second contains all the duplicates in no specified order.
2359 /// If the slice is sorted, the first returned slice contains no duplicates.
2364 /// #![feature(slice_partition_dedup)]
2366 /// let mut slice = [10, 20, 21, 30, 30, 20, 11, 13];
2368 /// let (dedup, duplicates) = slice.partition_dedup_by_key(|i| *i / 10);
2370 /// assert_eq!(dedup, [10, 20, 30, 20, 11]);
2371 /// assert_eq!(duplicates, [21, 30, 13]);
2373 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
2375 pub fn partition_dedup_by_key
<K
, F
>(&mut self, mut key
: F
) -> (&mut [T
], &mut [T
])
2377 F
: FnMut(&mut T
) -> K
,
2380 self.partition_dedup_by(|a
, b
| key(a
) == key(b
))
2383 /// Rotates the slice in-place such that the first `mid` elements of the
2384 /// slice move to the end while the last `self.len() - mid` elements move to
2385 /// the front. After calling `rotate_left`, the element previously at index
2386 /// `mid` will become the first element in the slice.
2390 /// This function will panic if `mid` is greater than the length of the
2391 /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op
2396 /// Takes linear (in `self.len()`) time.
2401 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2402 /// a.rotate_left(2);
2403 /// assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
2406 /// Rotating a subslice:
2409 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2410 /// a[1..5].rotate_left(1);
2411 /// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
2413 #[stable(feature = "slice_rotate", since = "1.26.0")]
2414 pub fn rotate_left(&mut self, mid
: usize) {
2415 assert
!(mid
<= self.len());
2416 let k
= self.len() - mid
;
2417 let p
= self.as_mut_ptr();
2419 // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially
2420 // valid for reading and writing, as required by `ptr_rotate`.
2422 rotate
::ptr_rotate(mid
, p
.add(mid
), k
);
2426 /// Rotates the slice in-place such that the first `self.len() - k`
2427 /// elements of the slice move to the end while the last `k` elements move
2428 /// to the front. After calling `rotate_right`, the element previously at
2429 /// index `self.len() - k` will become the first element in the slice.
2433 /// This function will panic if `k` is greater than the length of the
2434 /// slice. Note that `k == self.len()` does _not_ panic and is a no-op
2439 /// Takes linear (in `self.len()`) time.
2444 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2445 /// a.rotate_right(2);
2446 /// assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
2449 /// Rotate a subslice:
2452 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2453 /// a[1..5].rotate_right(1);
2454 /// assert_eq!(a, ['a', 'e', 'b', 'c', 'd', 'f']);
2456 #[stable(feature = "slice_rotate", since = "1.26.0")]
2457 pub fn rotate_right(&mut self, k
: usize) {
2458 assert
!(k
<= self.len());
2459 let mid
= self.len() - k
;
2460 let p
= self.as_mut_ptr();
2462 // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially
2463 // valid for reading and writing, as required by `ptr_rotate`.
2465 rotate
::ptr_rotate(mid
, p
.add(mid
), k
);
2469 /// Fills `self` with elements by cloning `value`.
2474 /// #![feature(slice_fill)]
2476 /// let mut buf = vec![0; 10];
2478 /// assert_eq!(buf, vec![1; 10]);
2480 #[unstable(feature = "slice_fill", issue = "70758")]
2481 pub fn fill(&mut self, value
: T
)
2485 if let Some((last
, elems
)) = self.split_last_mut() {
2487 el
.clone_from(&value
);
2494 /// Copies the elements from `src` into `self`.
2496 /// The length of `src` must be the same as `self`.
2498 /// If `T` implements `Copy`, it can be more performant to use
2499 /// [`copy_from_slice`].
2503 /// This function will panic if the two slices have different lengths.
2507 /// Cloning two elements from a slice into another:
2510 /// let src = [1, 2, 3, 4];
2511 /// let mut dst = [0, 0];
2513 /// // Because the slices have to be the same length,
2514 /// // we slice the source slice from four elements
2515 /// // to two. It will panic if we don't do this.
2516 /// dst.clone_from_slice(&src[2..]);
2518 /// assert_eq!(src, [1, 2, 3, 4]);
2519 /// assert_eq!(dst, [3, 4]);
2522 /// Rust enforces that there can only be one mutable reference with no
2523 /// immutable references to a particular piece of data in a particular
2524 /// scope. Because of this, attempting to use `clone_from_slice` on a
2525 /// single slice will result in a compile failure:
2528 /// let mut slice = [1, 2, 3, 4, 5];
2530 /// slice[..2].clone_from_slice(&slice[3..]); // compile fail!
2533 /// To work around this, we can use [`split_at_mut`] to create two distinct
2534 /// sub-slices from a slice:
2537 /// let mut slice = [1, 2, 3, 4, 5];
2540 /// let (left, right) = slice.split_at_mut(2);
2541 /// left.clone_from_slice(&right[1..]);
2544 /// assert_eq!(slice, [4, 5, 3, 4, 5]);
2547 /// [`copy_from_slice`]: #method.copy_from_slice
2548 /// [`split_at_mut`]: #method.split_at_mut
2549 #[stable(feature = "clone_from_slice", since = "1.7.0")]
2550 pub fn clone_from_slice(&mut self, src
: &[T
])
2554 assert
!(self.len() == src
.len(), "destination and source slices have different lengths");
2555 // NOTE: We need to explicitly slice them to the same length
2556 // for bounds checking to be elided, and the optimizer will
2557 // generate memcpy for simple cases (for example T = u8).
2558 let len
= self.len();
2559 let src
= &src
[..len
];
2561 self[i
].clone_from(&src
[i
]);
2565 /// Copies all elements from `src` into `self`, using a memcpy.
2567 /// The length of `src` must be the same as `self`.
2569 /// If `T` does not implement `Copy`, use [`clone_from_slice`].
2573 /// This function will panic if the two slices have different lengths.
2577 /// Copying two elements from a slice into another:
2580 /// let src = [1, 2, 3, 4];
2581 /// let mut dst = [0, 0];
2583 /// // Because the slices have to be the same length,
2584 /// // we slice the source slice from four elements
2585 /// // to two. It will panic if we don't do this.
2586 /// dst.copy_from_slice(&src[2..]);
2588 /// assert_eq!(src, [1, 2, 3, 4]);
2589 /// assert_eq!(dst, [3, 4]);
2592 /// Rust enforces that there can only be one mutable reference with no
2593 /// immutable references to a particular piece of data in a particular
2594 /// scope. Because of this, attempting to use `copy_from_slice` on a
2595 /// single slice will result in a compile failure:
2598 /// let mut slice = [1, 2, 3, 4, 5];
2600 /// slice[..2].copy_from_slice(&slice[3..]); // compile fail!
2603 /// To work around this, we can use [`split_at_mut`] to create two distinct
2604 /// sub-slices from a slice:
2607 /// let mut slice = [1, 2, 3, 4, 5];
2610 /// let (left, right) = slice.split_at_mut(2);
2611 /// left.copy_from_slice(&right[1..]);
2614 /// assert_eq!(slice, [4, 5, 3, 4, 5]);
2617 /// [`clone_from_slice`]: #method.clone_from_slice
2618 /// [`split_at_mut`]: #method.split_at_mut
2619 #[stable(feature = "copy_from_slice", since = "1.9.0")]
2620 pub fn copy_from_slice(&mut self, src
: &[T
])
2624 // The panic code path was put into a cold function to not bloat the
2629 fn len_mismatch_fail(dst_len
: usize, src_len
: usize) -> ! {
2631 "source slice length ({}) does not match destination slice length ({})",
2636 if self.len() != src
.len() {
2637 len_mismatch_fail(self.len(), src
.len());
2640 // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was
2641 // checked to have the same length. The slices cannot overlap because
2642 // mutable references are exclusive.
2644 ptr
::copy_nonoverlapping(src
.as_ptr(), self.as_mut_ptr(), self.len());
2648 /// Copies elements from one part of the slice to another part of itself,
2649 /// using a memmove.
2651 /// `src` is the range within `self` to copy from. `dest` is the starting
2652 /// index of the range within `self` to copy to, which will have the same
2653 /// length as `src`. The two ranges may overlap. The ends of the two ranges
2654 /// must be less than or equal to `self.len()`.
2658 /// This function will panic if either range exceeds the end of the slice,
2659 /// or if the end of `src` is before the start.
2663 /// Copying four bytes within a slice:
2666 /// let mut bytes = *b"Hello, World!";
2668 /// bytes.copy_within(1..5, 8);
2670 /// assert_eq!(&bytes, b"Hello, Wello!");
2672 #[stable(feature = "copy_within", since = "1.37.0")]
2674 pub fn copy_within
<R
: RangeBounds
<usize>>(&mut self, src
: R
, dest
: usize)
2678 let Range { start: src_start, end: src_end }
= check_range(self.len(), src
);
2679 let count
= src_end
- src_start
;
2680 assert
!(dest
<= self.len() - count
, "dest is out of bounds");
2681 // SAFETY: the conditions for `ptr::copy` have all been checked above,
2682 // as have those for `ptr::add`.
2684 ptr
::copy(self.as_ptr().add(src_start
), self.as_mut_ptr().add(dest
), count
);
2688 /// Swaps all elements in `self` with those in `other`.
2690 /// The length of `other` must be the same as `self`.
2694 /// This function will panic if the two slices have different lengths.
2698 /// Swapping two elements across slices:
2701 /// let mut slice1 = [0, 0];
2702 /// let mut slice2 = [1, 2, 3, 4];
2704 /// slice1.swap_with_slice(&mut slice2[2..]);
2706 /// assert_eq!(slice1, [3, 4]);
2707 /// assert_eq!(slice2, [1, 2, 0, 0]);
2710 /// Rust enforces that there can only be one mutable reference to a
2711 /// particular piece of data in a particular scope. Because of this,
2712 /// attempting to use `swap_with_slice` on a single slice will result in
2713 /// a compile failure:
2716 /// let mut slice = [1, 2, 3, 4, 5];
2717 /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail!
2720 /// To work around this, we can use [`split_at_mut`] to create two distinct
2721 /// mutable sub-slices from a slice:
2724 /// let mut slice = [1, 2, 3, 4, 5];
2727 /// let (left, right) = slice.split_at_mut(2);
2728 /// left.swap_with_slice(&mut right[1..]);
2731 /// assert_eq!(slice, [4, 5, 3, 1, 2]);
2734 /// [`split_at_mut`]: #method.split_at_mut
2735 #[stable(feature = "swap_with_slice", since = "1.27.0")]
2736 pub fn swap_with_slice(&mut self, other
: &mut [T
]) {
2737 assert
!(self.len() == other
.len(), "destination and source slices have different lengths");
2738 // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was
2739 // checked to have the same length. The slices cannot overlap because
2740 // mutable references are exclusive.
2742 ptr
::swap_nonoverlapping(self.as_mut_ptr(), other
.as_mut_ptr(), self.len());
2746 /// Function to calculate lengths of the middle and trailing slice for `align_to{,_mut}`.
2747 fn align_to_offsets
<U
>(&self) -> (usize, usize) {
2748 // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
2749 // lowest number of `T`s. And how many `T`s we need for each such "multiple".
2751 // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
2752 // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
2753 // place of every 3 Ts in the `rest` slice. A bit more complicated.
2755 // Formula to calculate this is:
2757 // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
2758 // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
2760 // Expanded and simplified:
2762 // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
2763 // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
2765 // Luckily since all this is constant-evaluated... performance here matters not!
2767 fn gcd(a
: usize, b
: usize) -> usize {
2768 use crate::intrinsics
;
2769 // iterative stein’s algorithm
2770 // We should still make this `const fn` (and revert to recursive algorithm if we do)
2771 // because relying on llvm to consteval all this is… well, it makes me uncomfortable.
2773 // SAFETY: `a` and `b` are checked to be non-zero values.
2774 let (ctz_a
, mut ctz_b
) = unsafe {
2781 (intrinsics
::cttz_nonzero(a
), intrinsics
::cttz_nonzero(b
))
2783 let k
= ctz_a
.min(ctz_b
);
2784 let mut a
= a
>> ctz_a
;
2787 // remove all factors of 2 from b
2790 mem
::swap(&mut a
, &mut b
);
2793 // SAFETY: `b` is checked to be non-zero.
2798 ctz_b
= intrinsics
::cttz_nonzero(b
);
2803 let gcd
: usize = gcd(mem
::size_of
::<T
>(), mem
::size_of
::<U
>());
2804 let ts
: usize = mem
::size_of
::<U
>() / gcd
;
2805 let us
: usize = mem
::size_of
::<T
>() / gcd
;
2807 // Armed with this knowledge, we can find how many `U`s we can fit!
2808 let us_len
= self.len() / ts
* us
;
2809 // And how many `T`s will be in the trailing slice!
2810 let ts_len
= self.len() % ts
;
2814 /// Transmute the slice to a slice of another type, ensuring alignment of the types is
2817 /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
2818 /// slice of a new type, and the suffix slice. The method may make the middle slice the greatest
2819 /// length possible for a given type and input slice, but only your algorithm's performance
2820 /// should depend on that, not its correctness. It is permissible for all of the input data to
2821 /// be returned as the prefix or suffix slice.
2823 /// This method has no purpose when either input element `T` or output element `U` are
2824 /// zero-sized and will return the original slice without splitting anything.
2828 /// This method is essentially a `transmute` with respect to the elements in the returned
2829 /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
2837 /// let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
2838 /// let (prefix, shorts, suffix) = bytes.align_to::<u16>();
2839 /// // less_efficient_algorithm_for_bytes(prefix);
2840 /// // more_efficient_algorithm_for_aligned_shorts(shorts);
2841 /// // less_efficient_algorithm_for_bytes(suffix);
2844 #[stable(feature = "slice_align_to", since = "1.30.0")]
2845 pub unsafe fn align_to
<U
>(&self) -> (&[T
], &[U
], &[T
]) {
2846 // Note that most of this function will be constant-evaluated,
2847 if mem
::size_of
::<U
>() == 0 || mem
::size_of
::<T
>() == 0 {
2848 // handle ZSTs specially, which is – don't handle them at all.
2849 return (self, &[], &[]);
2852 // First, find at what point do we split between the first and 2nd slice. Easy with
2853 // ptr.align_offset.
2854 let ptr
= self.as_ptr();
2855 // SAFETY: See the `align_to_mut` method for the detailed safety comment.
2856 let offset
= unsafe { crate::ptr::align_offset(ptr, mem::align_of::<U>()) }
;
2857 if offset
> self.len() {
2860 let (left
, rest
) = self.split_at(offset
);
2861 let (us_len
, ts_len
) = rest
.align_to_offsets
::<U
>();
2862 // SAFETY: now `rest` is definitely aligned, so `from_raw_parts` below is okay,
2863 // since the caller guarantees that we can transmute `T` to `U` safely.
2867 from_raw_parts(rest
.as_ptr() as *const U
, us_len
),
2868 from_raw_parts(rest
.as_ptr().add(rest
.len() - ts_len
), ts_len
),
2874 /// Transmute the slice to a slice of another type, ensuring alignment of the types is
2877 /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
2878 /// slice of a new type, and the suffix slice. The method may make the middle slice the greatest
2879 /// length possible for a given type and input slice, but only your algorithm's performance
2880 /// should depend on that, not its correctness. It is permissible for all of the input data to
2881 /// be returned as the prefix or suffix slice.
2883 /// This method has no purpose when either input element `T` or output element `U` are
2884 /// zero-sized and will return the original slice without splitting anything.
2888 /// This method is essentially a `transmute` with respect to the elements in the returned
2889 /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
2897 /// let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
2898 /// let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
2899 /// // less_efficient_algorithm_for_bytes(prefix);
2900 /// // more_efficient_algorithm_for_aligned_shorts(shorts);
2901 /// // less_efficient_algorithm_for_bytes(suffix);
2904 #[stable(feature = "slice_align_to", since = "1.30.0")]
2905 pub unsafe fn align_to_mut
<U
>(&mut self) -> (&mut [T
], &mut [U
], &mut [T
]) {
2906 // Note that most of this function will be constant-evaluated,
2907 if mem
::size_of
::<U
>() == 0 || mem
::size_of
::<T
>() == 0 {
2908 // handle ZSTs specially, which is – don't handle them at all.
2909 return (self, &mut [], &mut []);
2912 // First, find at what point do we split between the first and 2nd slice. Easy with
2913 // ptr.align_offset.
2914 let ptr
= self.as_ptr();
2915 // SAFETY: Here we are ensuring we will use aligned pointers for U for the
2916 // rest of the method. This is done by passing a pointer to &[T] with an
2917 // alignment targeted for U.
2918 // `crate::ptr::align_offset` is called with a correctly aligned and
2919 // valid pointer `ptr` (it comes from a reference to `self`) and with
2920 // a size that is a power of two (since it comes from the alignement for U),
2921 // satisfying its safety constraints.
2922 let offset
= unsafe { crate::ptr::align_offset(ptr, mem::align_of::<U>()) }
;
2923 if offset
> self.len() {
2924 (self, &mut [], &mut [])
2926 let (left
, rest
) = self.split_at_mut(offset
);
2927 let (us_len
, ts_len
) = rest
.align_to_offsets
::<U
>();
2928 let rest_len
= rest
.len();
2929 let mut_ptr
= rest
.as_mut_ptr();
2930 // We can't use `rest` again after this, that would invalidate its alias `mut_ptr`!
2931 // SAFETY: see comments for `align_to`.
2935 from_raw_parts_mut(mut_ptr
as *mut U
, us_len
),
2936 from_raw_parts_mut(mut_ptr
.add(rest_len
- ts_len
), ts_len
),
2942 /// Checks if the elements of this slice are sorted.
2944 /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
2945 /// slice yields exactly zero or one element, `true` is returned.
2947 /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
2948 /// implies that this function returns `false` if any two consecutive items are not
2954 /// #![feature(is_sorted)]
2955 /// let empty: [i32; 0] = [];
2957 /// assert!([1, 2, 2, 9].is_sorted());
2958 /// assert!(![1, 3, 2, 4].is_sorted());
2959 /// assert!([0].is_sorted());
2960 /// assert!(empty.is_sorted());
2961 /// assert!(![0.0, 1.0, f32::NAN].is_sorted());
2964 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2965 pub fn is_sorted(&self) -> bool
2969 self.is_sorted_by(|a
, b
| a
.partial_cmp(b
))
2972 /// Checks if the elements of this slice are sorted using the given comparator function.
2974 /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
2975 /// function to determine the ordering of two elements. Apart from that, it's equivalent to
2976 /// [`is_sorted`]; see its documentation for more information.
2978 /// [`is_sorted`]: #method.is_sorted
2979 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2980 pub fn is_sorted_by
<F
>(&self, mut compare
: F
) -> bool
2982 F
: FnMut(&T
, &T
) -> Option
<Ordering
>,
2984 self.iter().is_sorted_by(|a
, b
| compare(*a
, *b
))
2987 /// Checks if the elements of this slice are sorted using the given key extraction function.
2989 /// Instead of comparing the slice's elements directly, this function compares the keys of the
2990 /// elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see its
2991 /// documentation for more information.
2993 /// [`is_sorted`]: #method.is_sorted
2998 /// #![feature(is_sorted)]
3000 /// assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
3001 /// assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
3004 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
3005 pub fn is_sorted_by_key
<F
, K
>(&self, f
: F
) -> bool
3010 self.iter().is_sorted_by_key(f
)
3013 /// Returns the index of the partition point according to the given predicate
3014 /// (the index of the first element of the second partition).
3016 /// The slice is assumed to be partitioned according to the given predicate.
3017 /// This means that all elements for which the predicate returns true are at the start of the slice
3018 /// and all elements for which the predicate returns false are at the end.
3019 /// For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0
3020 /// (all odd numbers are at the start, all even at the end).
3022 /// If this slice is not partitioned, the returned result is unspecified and meaningless,
3023 /// as this method performs a kind of binary search.
3028 /// #![feature(partition_point)]
3030 /// let v = [1, 2, 3, 3, 5, 6, 7];
3031 /// let i = v.partition_point(|&x| x < 5);
3033 /// assert_eq!(i, 4);
3034 /// assert!(v[..i].iter().all(|&x| x < 5));
3035 /// assert!(v[i..].iter().all(|&x| !(x < 5)));
3037 #[unstable(feature = "partition_point", reason = "new API", issue = "73831")]
3038 pub fn partition_point
<P
>(&self, mut pred
: P
) -> usize
3040 P
: FnMut(&T
) -> bool
,
3043 let mut right
= self.len();
3045 while left
!= right
{
3046 let mid
= left
+ (right
- left
) / 2;
3047 // SAFETY: When `left < right`, `left <= mid < right`.
3048 // Therefore `left` always increases and `right` always decreases,
3049 // and either of them is selected. In both cases `left <= right` is
3050 // satisfied. Therefore if `left < right` in a step, `left <= right`
3051 // is satisfied in the next step. Therefore as long as `left != right`,
3052 // `0 <= left < right <= len` is satisfied and if this case
3053 // `0 <= mid < len` is satisfied too.
3054 let value
= unsafe { self.get_unchecked(mid) }
;
3066 #[stable(feature = "rust1", since = "1.0.0")]
3067 impl<T
> Default
for &[T
] {
3068 /// Creates an empty slice.
3069 fn default() -> Self {
3074 #[stable(feature = "mut_slice_default", since = "1.5.0")]
3075 impl<T
> Default
for &mut [T
] {
3076 /// Creates a mutable empty slice.
3077 fn default() -> Self {