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 // How this module is organized.
13 // The library infrastructure for slices is fairly messy. There's
14 // a lot of stuff defined here. Let's keep it clean.
16 // The layout of this file is thus:
18 // * Inherent methods. This is where most of the slice API resides.
19 // * Implementations of a few common traits with important slice ops.
20 // * Definitions of a bunch of iterators.
22 // * The `raw` and `bytes` submodules.
23 // * Boilerplate trait implementations.
25 use crate::cmp::Ordering::{self, Less, Equal, Greater};
28 use crate::intrinsics::assume;
31 use crate::ops::{FnMut, Try, self};
32 use crate::option::Option;
33 use crate::option::Option::{None, Some};
34 use crate::result::Result;
35 use crate::result::Result::{Ok, Err};
38 use crate::marker::{Copy, Send, Sync, Sized, self};
40 #[unstable(feature = "slice_internals", issue = "0",
41 reason = "exposed from core to be reused in std; use the memchr crate")]
42 /// Pure rust memchr implementation, taken from rust-memchr
49 union Repr<'a, T: 'a> {
51 rust_mut: &'a mut [T],
68 /// Returns the number of elements in the slice.
73 /// let a = [1, 2, 3];
74 /// assert_eq!(a.len(), 3);
76 #[stable(feature = "rust1", since = "1.0.0")]
78 #[rustc_const_unstable(feature = "const_slice_len")]
79 pub const fn len(&self) -> usize {
81 Repr { rust: self }.raw.len
85 /// Returns `true` if the slice has a length of 0.
90 /// let a = [1, 2, 3];
91 /// assert!(!a.is_empty());
93 #[stable(feature = "rust1", since = "1.0.0")]
95 #[rustc_const_unstable(feature = "const_slice_len")]
96 pub const fn is_empty(&self) -> bool {
100 /// Returns the first element of the slice, or `None` if it is empty.
105 /// let v = [10, 40, 30];
106 /// assert_eq!(Some(&10), v.first());
108 /// let w: &[i32] = &[];
109 /// assert_eq!(None, w.first());
111 #[stable(feature = "rust1", since = "1.0.0")]
113 pub fn first(&self) -> Option<&T> {
117 /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty.
122 /// let x = &mut [0, 1, 2];
124 /// if let Some(first) = x.first_mut() {
127 /// assert_eq!(x, &[5, 1, 2]);
129 #[stable(feature = "rust1", since = "1.0.0")]
131 pub fn first_mut(&mut self) -> Option<&mut T> {
135 /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
140 /// let x = &[0, 1, 2];
142 /// if let Some((first, elements)) = x.split_first() {
143 /// assert_eq!(first, &0);
144 /// assert_eq!(elements, &[1, 2]);
147 #[stable(feature = "slice_splits", since = "1.5.0")]
149 pub fn split_first(&self) -> Option<(&T, &[T])> {
150 if self.is_empty() { None } else { Some((&self[0], &self[1..])) }
153 /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
158 /// let x = &mut [0, 1, 2];
160 /// if let Some((first, elements)) = x.split_first_mut() {
165 /// assert_eq!(x, &[3, 4, 5]);
167 #[stable(feature = "slice_splits", since = "1.5.0")]
169 pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
170 if self.is_empty() { None } else {
171 let split = self.split_at_mut(1);
172 Some((&mut split.0[0], split.1))
176 /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
181 /// let x = &[0, 1, 2];
183 /// if let Some((last, elements)) = x.split_last() {
184 /// assert_eq!(last, &2);
185 /// assert_eq!(elements, &[0, 1]);
188 #[stable(feature = "slice_splits", since = "1.5.0")]
190 pub fn split_last(&self) -> Option<(&T, &[T])> {
191 let len = self.len();
192 if len == 0 { None } else { Some((&self[len - 1], &self[..(len - 1)])) }
195 /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
200 /// let x = &mut [0, 1, 2];
202 /// if let Some((last, elements)) = x.split_last_mut() {
207 /// assert_eq!(x, &[4, 5, 3]);
209 #[stable(feature = "slice_splits", since = "1.5.0")]
211 pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
212 let len = self.len();
213 if len == 0 { None } else {
214 let split = self.split_at_mut(len - 1);
215 Some((&mut split.1[0], split.0))
220 /// Returns the last element of the slice, or `None` if it is empty.
225 /// let v = [10, 40, 30];
226 /// assert_eq!(Some(&30), v.last());
228 /// let w: &[i32] = &[];
229 /// assert_eq!(None, w.last());
231 #[stable(feature = "rust1", since = "1.0.0")]
233 pub fn last(&self) -> Option<&T> {
234 let last_idx = self.len().checked_sub(1)?;
238 /// Returns a mutable pointer to the last item in the slice.
243 /// let x = &mut [0, 1, 2];
245 /// if let Some(last) = x.last_mut() {
248 /// assert_eq!(x, &[0, 1, 10]);
250 #[stable(feature = "rust1", since = "1.0.0")]
252 pub fn last_mut(&mut self) -> Option<&mut T> {
253 let last_idx = self.len().checked_sub(1)?;
254 self.get_mut(last_idx)
257 /// Returns a reference to an element or subslice depending on the type of
260 /// - If given a position, returns a reference to the element at that
261 /// position or `None` if out of bounds.
262 /// - If given a range, returns the subslice corresponding to that range,
263 /// or `None` if out of bounds.
268 /// let v = [10, 40, 30];
269 /// assert_eq!(Some(&40), v.get(1));
270 /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
271 /// assert_eq!(None, v.get(3));
272 /// assert_eq!(None, v.get(0..4));
274 #[stable(feature = "rust1", since = "1.0.0")]
276 pub fn get<I>(&self, index: I) -> Option<&I::Output>
277 where I: SliceIndex<Self>
282 /// Returns a mutable reference to an element or subslice depending on the
283 /// type of index (see [`get`]) or `None` if the index is out of bounds.
285 /// [`get`]: #method.get
290 /// let x = &mut [0, 1, 2];
292 /// if let Some(elem) = x.get_mut(1) {
295 /// assert_eq!(x, &[0, 42, 2]);
297 #[stable(feature = "rust1", since = "1.0.0")]
299 pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
300 where I: SliceIndex<Self>
305 /// Returns a reference to an element or subslice, without doing bounds
308 /// This is generally not recommended, use with caution! For a safe
309 /// alternative see [`get`].
311 /// [`get`]: #method.get
316 /// let x = &[1, 2, 4];
319 /// assert_eq!(x.get_unchecked(1), &2);
322 #[stable(feature = "rust1", since = "1.0.0")]
324 pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
325 where I: SliceIndex<Self>
327 index.get_unchecked(self)
330 /// Returns a mutable reference to an element or subslice, without doing
333 /// This is generally not recommended, use with caution! For a safe
334 /// alternative see [`get_mut`].
336 /// [`get_mut`]: #method.get_mut
341 /// let x = &mut [1, 2, 4];
344 /// let elem = x.get_unchecked_mut(1);
347 /// assert_eq!(x, &[1, 13, 4]);
349 #[stable(feature = "rust1", since = "1.0.0")]
351 pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
352 where I: SliceIndex<Self>
354 index.get_unchecked_mut(self)
357 /// Returns a raw pointer to the slice's buffer.
359 /// The caller must ensure that the slice outlives the pointer this
360 /// function returns, or else it will end up pointing to garbage.
362 /// Modifying the container referenced by this slice may cause its buffer
363 /// to be reallocated, which would also make any pointers to it invalid.
368 /// let x = &[1, 2, 4];
369 /// let x_ptr = x.as_ptr();
372 /// for i in 0..x.len() {
373 /// assert_eq!(x.get_unchecked(i), &*x_ptr.add(i));
377 #[stable(feature = "rust1", since = "1.0.0")]
379 pub const fn as_ptr(&self) -> *const T {
380 self as *const [T] as *const T
383 /// Returns an unsafe mutable pointer to the slice's buffer.
385 /// The caller must ensure that the slice outlives the pointer this
386 /// function returns, or else it will end up pointing to garbage.
388 /// Modifying the container referenced by this slice may cause its buffer
389 /// to be reallocated, which would also make any pointers to it invalid.
394 /// let x = &mut [1, 2, 4];
395 /// let x_ptr = x.as_mut_ptr();
398 /// for i in 0..x.len() {
399 /// *x_ptr.add(i) += 2;
402 /// assert_eq!(x, &[3, 4, 6]);
404 #[stable(feature = "rust1", since = "1.0.0")]
406 pub fn as_mut_ptr(&mut self) -> *mut T {
407 self as *mut [T] as *mut T
410 /// Swaps two elements in the slice.
414 /// * a - The index of the first element
415 /// * b - The index of the second element
419 /// Panics if `a` or `b` are out of bounds.
424 /// let mut v = ["a", "b", "c", "d"];
426 /// assert!(v == ["a", "d", "c", "b"]);
428 #[stable(feature = "rust1", since = "1.0.0")]
430 pub fn swap(&mut self, a: usize, b: usize) {
432 // Can't take two mutable loans from one vector, so instead just cast
433 // them to their raw pointers to do the swap
434 let pa: *mut T = &mut self[a];
435 let pb: *mut T = &mut self[b];
440 /// Reverses the order of elements in the slice, in place.
445 /// let mut v = [1, 2, 3];
447 /// assert!(v == [3, 2, 1]);
449 #[stable(feature = "rust1", since = "1.0.0")]
451 pub fn reverse(&mut self) {
452 let mut i: usize = 0;
455 // For very small types, all the individual reads in the normal
456 // path perform poorly. We can do better, given efficient unaligned
457 // load/store, by loading a larger chunk and reversing a register.
459 // Ideally LLVM would do this for us, as it knows better than we do
460 // whether unaligned reads are efficient (since that changes between
461 // different ARM versions, for example) and what the best chunk size
462 // would be. Unfortunately, as of LLVM 4.0 (2017-05) it only unrolls
463 // the loop, so we need to do this ourselves. (Hypothesis: reverse
464 // is troublesome because the sides can be aligned differently --
465 // will be, when the length is odd -- so there's no way of emitting
466 // pre- and postludes to use fully-aligned SIMD in the middle.)
469 cfg!(any(target_arch = "x86", target_arch = "x86_64"));
471 if fast_unaligned && mem::size_of::<T>() == 1 {
472 // Use the llvm.bswap intrinsic to reverse u8s in a usize
473 let chunk = mem::size_of::<usize>();
474 while i + chunk - 1 < ln / 2 {
476 let pa: *mut T = self.get_unchecked_mut(i);
477 let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
478 let va = ptr::read_unaligned(pa as *mut usize);
479 let vb = ptr::read_unaligned(pb as *mut usize);
480 ptr::write_unaligned(pa as *mut usize, vb.swap_bytes());
481 ptr::write_unaligned(pb as *mut usize, va.swap_bytes());
487 if fast_unaligned && mem::size_of::<T>() == 2 {
488 // Use rotate-by-16 to reverse u16s in a u32
489 let chunk = mem::size_of::<u32>() / 2;
490 while i + chunk - 1 < ln / 2 {
492 let pa: *mut T = self.get_unchecked_mut(i);
493 let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
494 let va = ptr::read_unaligned(pa as *mut u32);
495 let vb = ptr::read_unaligned(pb as *mut u32);
496 ptr::write_unaligned(pa as *mut u32, vb.rotate_left(16));
497 ptr::write_unaligned(pb as *mut u32, va.rotate_left(16));
504 // Unsafe swap to avoid the bounds check in safe swap.
506 let pa: *mut T = self.get_unchecked_mut(i);
507 let pb: *mut T = self.get_unchecked_mut(ln - i - 1);
514 /// Returns an iterator over the slice.
519 /// let x = &[1, 2, 4];
520 /// let mut iterator = x.iter();
522 /// assert_eq!(iterator.next(), Some(&1));
523 /// assert_eq!(iterator.next(), Some(&2));
524 /// assert_eq!(iterator.next(), Some(&4));
525 /// assert_eq!(iterator.next(), None);
527 #[stable(feature = "rust1", since = "1.0.0")]
529 pub fn iter(&self) -> Iter<'_, T> {
531 let ptr = self.as_ptr();
532 assume(!ptr.is_null());
534 let end = if mem::size_of::<T>() == 0 {
535 (ptr as *const u8).wrapping_add(self.len()) as *const T
543 _marker: marker::PhantomData
548 /// Returns an iterator that allows modifying each value.
553 /// let x = &mut [1, 2, 4];
554 /// for elem in x.iter_mut() {
557 /// assert_eq!(x, &[3, 4, 6]);
559 #[stable(feature = "rust1", since = "1.0.0")]
561 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
563 let ptr = self.as_mut_ptr();
564 assume(!ptr.is_null());
566 let end = if mem::size_of::<T>() == 0 {
567 (ptr as *mut u8).wrapping_add(self.len()) as *mut T
575 _marker: marker::PhantomData
580 /// Returns an iterator over all contiguous windows of length
581 /// `size`. The windows overlap. If the slice is shorter than
582 /// `size`, the iterator returns no values.
586 /// Panics if `size` is 0.
591 /// let slice = ['r', 'u', 's', 't'];
592 /// let mut iter = slice.windows(2);
593 /// assert_eq!(iter.next().unwrap(), &['r', 'u']);
594 /// assert_eq!(iter.next().unwrap(), &['u', 's']);
595 /// assert_eq!(iter.next().unwrap(), &['s', 't']);
596 /// assert!(iter.next().is_none());
599 /// If the slice is shorter than `size`:
602 /// let slice = ['f', 'o', 'o'];
603 /// let mut iter = slice.windows(4);
604 /// assert!(iter.next().is_none());
606 #[stable(feature = "rust1", since = "1.0.0")]
608 pub fn windows(&self, size: usize) -> Windows<'_, T> {
610 Windows { v: self, size }
613 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
614 /// beginning of the slice.
616 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
617 /// slice, then the last chunk will not have length `chunk_size`.
619 /// See [`chunks_exact`] for a variant of this iterator that returns chunks of always exactly
620 /// `chunk_size` elements, and [`rchunks`] for the same iterator but starting at the end of the
621 /// slice of the slice.
625 /// Panics if `chunk_size` is 0.
630 /// let slice = ['l', 'o', 'r', 'e', 'm'];
631 /// let mut iter = slice.chunks(2);
632 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
633 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
634 /// assert_eq!(iter.next().unwrap(), &['m']);
635 /// assert!(iter.next().is_none());
638 /// [`chunks_exact`]: #method.chunks_exact
639 /// [`rchunks`]: #method.rchunks
640 #[stable(feature = "rust1", since = "1.0.0")]
642 pub fn chunks(&self, chunk_size: usize) -> Chunks<'_, T> {
643 assert!(chunk_size != 0);
644 Chunks { v: self, chunk_size }
647 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
648 /// beginning of the slice.
650 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
651 /// length of the slice, then the last chunk will not have length `chunk_size`.
653 /// See [`chunks_exact_mut`] for a variant of this iterator that returns chunks of always
654 /// exactly `chunk_size` elements, and [`rchunks_mut`] for the same iterator but starting at
655 /// the end of the slice of the slice.
659 /// Panics if `chunk_size` is 0.
664 /// let v = &mut [0, 0, 0, 0, 0];
665 /// let mut count = 1;
667 /// for chunk in v.chunks_mut(2) {
668 /// for elem in chunk.iter_mut() {
673 /// assert_eq!(v, &[1, 1, 2, 2, 3]);
676 /// [`chunks_exact_mut`]: #method.chunks_exact_mut
677 /// [`rchunks_mut`]: #method.rchunks_mut
678 #[stable(feature = "rust1", since = "1.0.0")]
680 pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T> {
681 assert!(chunk_size != 0);
682 ChunksMut { v: self, chunk_size }
685 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
686 /// beginning of the slice.
688 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
689 /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
690 /// from the `remainder` function of the iterator.
692 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
693 /// resulting code better than in the case of [`chunks`].
695 /// See [`chunks`] for a variant of this iterator that also returns the remainder as a smaller
696 /// chunk, and [`rchunks_exact`] for the same iterator but starting at the end of the slice.
700 /// Panics if `chunk_size` is 0.
705 /// let slice = ['l', 'o', 'r', 'e', 'm'];
706 /// let mut iter = slice.chunks_exact(2);
707 /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
708 /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
709 /// assert!(iter.next().is_none());
710 /// assert_eq!(iter.remainder(), &['m']);
713 /// [`chunks`]: #method.chunks
714 /// [`rchunks_exact`]: #method.rchunks_exact
715 #[stable(feature = "chunks_exact", since = "1.31.0")]
717 pub fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T> {
718 assert!(chunk_size != 0);
719 let rem = self.len() % chunk_size;
720 let len = self.len() - rem;
721 let (fst, snd) = self.split_at(len);
722 ChunksExact { v: fst, rem: snd, chunk_size }
725 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
726 /// beginning of the slice.
728 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
729 /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
730 /// retrieved from the `into_remainder` function of the iterator.
732 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
733 /// resulting code better than in the case of [`chunks_mut`].
735 /// See [`chunks_mut`] for a variant of this iterator that also returns the remainder as a
736 /// smaller chunk, and [`rchunks_exact_mut`] for the same iterator but starting at the end of
737 /// the slice of the slice.
741 /// Panics if `chunk_size` is 0.
746 /// let v = &mut [0, 0, 0, 0, 0];
747 /// let mut count = 1;
749 /// for chunk in v.chunks_exact_mut(2) {
750 /// for elem in chunk.iter_mut() {
755 /// assert_eq!(v, &[1, 1, 2, 2, 0]);
758 /// [`chunks_mut`]: #method.chunks_mut
759 /// [`rchunks_exact_mut`]: #method.rchunks_exact_mut
760 #[stable(feature = "chunks_exact", since = "1.31.0")]
762 pub fn chunks_exact_mut(&mut self, chunk_size: usize) -> ChunksExactMut<'_, T> {
763 assert!(chunk_size != 0);
764 let rem = self.len() % chunk_size;
765 let len = self.len() - rem;
766 let (fst, snd) = self.split_at_mut(len);
767 ChunksExactMut { v: fst, rem: snd, chunk_size }
770 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
773 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
774 /// slice, then the last chunk will not have length `chunk_size`.
776 /// See [`rchunks_exact`] for a variant of this iterator that returns chunks of always exactly
777 /// `chunk_size` elements, and [`chunks`] for the same iterator but starting at the beginning
782 /// Panics if `chunk_size` is 0.
787 /// let slice = ['l', 'o', 'r', 'e', 'm'];
788 /// let mut iter = slice.rchunks(2);
789 /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
790 /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
791 /// assert_eq!(iter.next().unwrap(), &['l']);
792 /// assert!(iter.next().is_none());
795 /// [`rchunks_exact`]: #method.rchunks_exact
796 /// [`chunks`]: #method.chunks
797 #[stable(feature = "rchunks", since = "1.31.0")]
799 pub fn rchunks(&self, chunk_size: usize) -> RChunks<'_, T> {
800 assert!(chunk_size != 0);
801 RChunks { v: self, chunk_size }
804 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
807 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
808 /// length of the slice, then the last chunk will not have length `chunk_size`.
810 /// See [`rchunks_exact_mut`] for a variant of this iterator that returns chunks of always
811 /// exactly `chunk_size` elements, and [`chunks_mut`] for the same iterator but starting at the
812 /// beginning of the slice.
816 /// Panics if `chunk_size` is 0.
821 /// let v = &mut [0, 0, 0, 0, 0];
822 /// let mut count = 1;
824 /// for chunk in v.rchunks_mut(2) {
825 /// for elem in chunk.iter_mut() {
830 /// assert_eq!(v, &[3, 2, 2, 1, 1]);
833 /// [`rchunks_exact_mut`]: #method.rchunks_exact_mut
834 /// [`chunks_mut`]: #method.chunks_mut
835 #[stable(feature = "rchunks", since = "1.31.0")]
837 pub fn rchunks_mut(&mut self, chunk_size: usize) -> RChunksMut<'_, T> {
838 assert!(chunk_size != 0);
839 RChunksMut { v: self, chunk_size }
842 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
843 /// end of the slice.
845 /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
846 /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
847 /// from the `remainder` function of the iterator.
849 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
850 /// resulting code better than in the case of [`chunks`].
852 /// See [`rchunks`] for a variant of this iterator that also returns the remainder as a smaller
853 /// chunk, and [`chunks_exact`] for the same iterator but starting at the beginning of the
858 /// Panics if `chunk_size` is 0.
863 /// let slice = ['l', 'o', 'r', 'e', 'm'];
864 /// let mut iter = slice.rchunks_exact(2);
865 /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
866 /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
867 /// assert!(iter.next().is_none());
868 /// assert_eq!(iter.remainder(), &['l']);
871 /// [`chunks`]: #method.chunks
872 /// [`rchunks`]: #method.rchunks
873 /// [`chunks_exact`]: #method.chunks_exact
874 #[stable(feature = "rchunks", since = "1.31.0")]
876 pub fn rchunks_exact(&self, chunk_size: usize) -> RChunksExact<'_, T> {
877 assert!(chunk_size != 0);
878 let rem = self.len() % chunk_size;
879 let (fst, snd) = self.split_at(rem);
880 RChunksExact { v: snd, rem: fst, chunk_size }
883 /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
886 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
887 /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
888 /// retrieved from the `into_remainder` function of the iterator.
890 /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
891 /// resulting code better than in the case of [`chunks_mut`].
893 /// See [`rchunks_mut`] for a variant of this iterator that also returns the remainder as a
894 /// smaller chunk, and [`chunks_exact_mut`] for the same iterator but starting at the beginning
899 /// Panics if `chunk_size` is 0.
904 /// let v = &mut [0, 0, 0, 0, 0];
905 /// let mut count = 1;
907 /// for chunk in v.rchunks_exact_mut(2) {
908 /// for elem in chunk.iter_mut() {
913 /// assert_eq!(v, &[0, 2, 2, 1, 1]);
916 /// [`chunks_mut`]: #method.chunks_mut
917 /// [`rchunks_mut`]: #method.rchunks_mut
918 /// [`chunks_exact_mut`]: #method.chunks_exact_mut
919 #[stable(feature = "rchunks", since = "1.31.0")]
921 pub fn rchunks_exact_mut(&mut self, chunk_size: usize) -> RChunksExactMut<'_, T> {
922 assert!(chunk_size != 0);
923 let rem = self.len() % chunk_size;
924 let (fst, snd) = self.split_at_mut(rem);
925 RChunksExactMut { v: snd, rem: fst, chunk_size }
928 /// Divides one slice into two at an index.
930 /// The first will contain all indices from `[0, mid)` (excluding
931 /// the index `mid` itself) and the second will contain all
932 /// indices from `[mid, len)` (excluding the index `len` itself).
936 /// Panics if `mid > len`.
941 /// let v = [1, 2, 3, 4, 5, 6];
944 /// let (left, right) = v.split_at(0);
945 /// assert!(left == []);
946 /// assert!(right == [1, 2, 3, 4, 5, 6]);
950 /// let (left, right) = v.split_at(2);
951 /// assert!(left == [1, 2]);
952 /// assert!(right == [3, 4, 5, 6]);
956 /// let (left, right) = v.split_at(6);
957 /// assert!(left == [1, 2, 3, 4, 5, 6]);
958 /// assert!(right == []);
961 #[stable(feature = "rust1", since = "1.0.0")]
963 pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
964 (&self[..mid], &self[mid..])
967 /// Divides one mutable slice into two at an index.
969 /// The first will contain all indices from `[0, mid)` (excluding
970 /// the index `mid` itself) and the second will contain all
971 /// indices from `[mid, len)` (excluding the index `len` itself).
975 /// Panics if `mid > len`.
980 /// let mut v = [1, 0, 3, 0, 5, 6];
981 /// // scoped to restrict the lifetime of the borrows
983 /// let (left, right) = v.split_at_mut(2);
984 /// assert!(left == [1, 0]);
985 /// assert!(right == [3, 0, 5, 6]);
989 /// assert!(v == [1, 2, 3, 4, 5, 6]);
991 #[stable(feature = "rust1", since = "1.0.0")]
993 pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
994 let len = self.len();
995 let ptr = self.as_mut_ptr();
1000 (from_raw_parts_mut(ptr, mid),
1001 from_raw_parts_mut(ptr.add(mid), len - mid))
1005 /// Returns an iterator over subslices separated by elements that match
1006 /// `pred`. The matched element is not contained in the subslices.
1011 /// let slice = [10, 40, 33, 20];
1012 /// let mut iter = slice.split(|num| num % 3 == 0);
1014 /// assert_eq!(iter.next().unwrap(), &[10, 40]);
1015 /// assert_eq!(iter.next().unwrap(), &[20]);
1016 /// assert!(iter.next().is_none());
1019 /// If the first element is matched, an empty slice will be the first item
1020 /// returned by the iterator. Similarly, if the last element in the slice
1021 /// is matched, an empty slice will be the last item returned by the
1025 /// let slice = [10, 40, 33];
1026 /// let mut iter = slice.split(|num| num % 3 == 0);
1028 /// assert_eq!(iter.next().unwrap(), &[10, 40]);
1029 /// assert_eq!(iter.next().unwrap(), &[]);
1030 /// assert!(iter.next().is_none());
1033 /// If two matched elements are directly adjacent, an empty slice will be
1034 /// present between them:
1037 /// let slice = [10, 6, 33, 20];
1038 /// let mut iter = slice.split(|num| num % 3 == 0);
1040 /// assert_eq!(iter.next().unwrap(), &[10]);
1041 /// assert_eq!(iter.next().unwrap(), &[]);
1042 /// assert_eq!(iter.next().unwrap(), &[20]);
1043 /// assert!(iter.next().is_none());
1045 #[stable(feature = "rust1", since = "1.0.0")]
1047 pub fn split<F>(&self, pred: F) -> Split<'_, T, F>
1048 where F: FnMut(&T) -> bool
1057 /// Returns an iterator over mutable subslices separated by elements that
1058 /// match `pred`. The matched element is not contained in the subslices.
1063 /// let mut v = [10, 40, 30, 20, 60, 50];
1065 /// for group in v.split_mut(|num| *num % 3 == 0) {
1068 /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
1070 #[stable(feature = "rust1", since = "1.0.0")]
1072 pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<'_, T, F>
1073 where F: FnMut(&T) -> bool
1075 SplitMut { v: self, pred, finished: false }
1078 /// Returns an iterator over subslices separated by elements that match
1079 /// `pred`, starting at the end of the slice and working backwards.
1080 /// The matched element is not contained in the subslices.
1085 /// let slice = [11, 22, 33, 0, 44, 55];
1086 /// let mut iter = slice.rsplit(|num| *num == 0);
1088 /// assert_eq!(iter.next().unwrap(), &[44, 55]);
1089 /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
1090 /// assert_eq!(iter.next(), None);
1093 /// As with `split()`, if the first or last element is matched, an empty
1094 /// slice will be the first (or last) item returned by the iterator.
1097 /// let v = &[0, 1, 1, 2, 3, 5, 8];
1098 /// let mut it = v.rsplit(|n| *n % 2 == 0);
1099 /// assert_eq!(it.next().unwrap(), &[]);
1100 /// assert_eq!(it.next().unwrap(), &[3, 5]);
1101 /// assert_eq!(it.next().unwrap(), &[1, 1]);
1102 /// assert_eq!(it.next().unwrap(), &[]);
1103 /// assert_eq!(it.next(), None);
1105 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1107 pub fn rsplit<F>(&self, pred: F) -> RSplit<'_, T, F>
1108 where F: FnMut(&T) -> bool
1110 RSplit { inner: self.split(pred) }
1113 /// Returns an iterator over mutable subslices separated by elements that
1114 /// match `pred`, starting at the end of the slice and working
1115 /// backwards. The matched element is not contained in the subslices.
1120 /// let mut v = [100, 400, 300, 200, 600, 500];
1122 /// let mut count = 0;
1123 /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
1125 /// group[0] = count;
1127 /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
1130 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1132 pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<'_, T, F>
1133 where F: FnMut(&T) -> bool
1135 RSplitMut { inner: self.split_mut(pred) }
1138 /// Returns an iterator over subslices separated by elements that match
1139 /// `pred`, limited to returning at most `n` items. The matched element is
1140 /// not contained in the subslices.
1142 /// The last element returned, if any, will contain the remainder of the
1147 /// Print the slice split once by numbers divisible by 3 (i.e., `[10, 40]`,
1148 /// `[20, 60, 50]`):
1151 /// let v = [10, 40, 30, 20, 60, 50];
1153 /// for group in v.splitn(2, |num| *num % 3 == 0) {
1154 /// println!("{:?}", group);
1157 #[stable(feature = "rust1", since = "1.0.0")]
1159 pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<'_, T, F>
1160 where F: FnMut(&T) -> bool
1163 inner: GenericSplitN {
1164 iter: self.split(pred),
1170 /// Returns an iterator over subslices separated by elements that match
1171 /// `pred`, limited to returning at most `n` items. The matched element is
1172 /// not contained in the subslices.
1174 /// The last element returned, if any, will contain the remainder of the
1180 /// let mut v = [10, 40, 30, 20, 60, 50];
1182 /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
1185 /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
1187 #[stable(feature = "rust1", since = "1.0.0")]
1189 pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<'_, T, F>
1190 where F: FnMut(&T) -> bool
1193 inner: GenericSplitN {
1194 iter: self.split_mut(pred),
1200 /// Returns an iterator over subslices separated by elements that match
1201 /// `pred` limited to returning at most `n` items. This starts at the end of
1202 /// the slice and works backwards. The matched element is not contained in
1205 /// The last element returned, if any, will contain the remainder of the
1210 /// Print the slice split once, starting from the end, by numbers divisible
1211 /// by 3 (i.e., `[50]`, `[10, 40, 30, 20]`):
1214 /// let v = [10, 40, 30, 20, 60, 50];
1216 /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
1217 /// println!("{:?}", group);
1220 #[stable(feature = "rust1", since = "1.0.0")]
1222 pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<'_, T, F>
1223 where F: FnMut(&T) -> bool
1226 inner: GenericSplitN {
1227 iter: self.rsplit(pred),
1233 /// Returns an iterator over subslices separated by elements that match
1234 /// `pred` limited to returning at most `n` items. This starts at the end of
1235 /// the slice and works backwards. The matched element is not contained in
1238 /// The last element returned, if any, will contain the remainder of the
1244 /// let mut s = [10, 40, 30, 20, 60, 50];
1246 /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
1249 /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
1251 #[stable(feature = "rust1", since = "1.0.0")]
1253 pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<'_, T, F>
1254 where F: FnMut(&T) -> bool
1257 inner: GenericSplitN {
1258 iter: self.rsplit_mut(pred),
1264 /// Returns `true` if the slice contains an element with the given value.
1269 /// let v = [10, 40, 30];
1270 /// assert!(v.contains(&30));
1271 /// assert!(!v.contains(&50));
1273 #[stable(feature = "rust1", since = "1.0.0")]
1274 pub fn contains(&self, x: &T) -> bool
1277 x.slice_contains(self)
1280 /// Returns `true` if `needle` is a prefix of the slice.
1285 /// let v = [10, 40, 30];
1286 /// assert!(v.starts_with(&[10]));
1287 /// assert!(v.starts_with(&[10, 40]));
1288 /// assert!(!v.starts_with(&[50]));
1289 /// assert!(!v.starts_with(&[10, 50]));
1292 /// Always returns `true` if `needle` is an empty slice:
1295 /// let v = &[10, 40, 30];
1296 /// assert!(v.starts_with(&[]));
1297 /// let v: &[u8] = &[];
1298 /// assert!(v.starts_with(&[]));
1300 #[stable(feature = "rust1", since = "1.0.0")]
1301 pub fn starts_with(&self, needle: &[T]) -> bool
1304 let n = needle.len();
1305 self.len() >= n && needle == &self[..n]
1308 /// Returns `true` if `needle` is a suffix of the slice.
1313 /// let v = [10, 40, 30];
1314 /// assert!(v.ends_with(&[30]));
1315 /// assert!(v.ends_with(&[40, 30]));
1316 /// assert!(!v.ends_with(&[50]));
1317 /// assert!(!v.ends_with(&[50, 30]));
1320 /// Always returns `true` if `needle` is an empty slice:
1323 /// let v = &[10, 40, 30];
1324 /// assert!(v.ends_with(&[]));
1325 /// let v: &[u8] = &[];
1326 /// assert!(v.ends_with(&[]));
1328 #[stable(feature = "rust1", since = "1.0.0")]
1329 pub fn ends_with(&self, needle: &[T]) -> bool
1332 let (m, n) = (self.len(), needle.len());
1333 m >= n && needle == &self[m-n..]
1336 /// Binary searches this sorted slice for a given element.
1338 /// If the value is found then [`Result::Ok`] is returned, containing the
1339 /// index of the matching element. If there are multiple matches, then any
1340 /// one of the matches could be returned. If the value is not found then
1341 /// [`Result::Err`] is returned, containing the index where a matching
1342 /// element could be inserted while maintaining sorted order.
1346 /// Looks up a series of four elements. The first is found, with a
1347 /// uniquely determined position; the second and third are not
1348 /// found; the fourth could match any position in `[1, 4]`.
1351 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1353 /// assert_eq!(s.binary_search(&13), Ok(9));
1354 /// assert_eq!(s.binary_search(&4), Err(7));
1355 /// assert_eq!(s.binary_search(&100), Err(13));
1356 /// let r = s.binary_search(&1);
1357 /// assert!(match r { Ok(1..=4) => true, _ => false, });
1359 #[stable(feature = "rust1", since = "1.0.0")]
1360 pub fn binary_search(&self, x: &T) -> Result<usize, usize>
1363 self.binary_search_by(|p| p.cmp(x))
1366 /// Binary searches this sorted slice with a comparator function.
1368 /// The comparator function should implement an order consistent
1369 /// with the sort order of the underlying slice, returning an
1370 /// order code that indicates whether its argument is `Less`,
1371 /// `Equal` or `Greater` the desired target.
1373 /// If the value is found then [`Result::Ok`] is returned, containing the
1374 /// index of the matching element. If there are multiple matches, then any
1375 /// one of the matches could be returned. If the value is not found then
1376 /// [`Result::Err`] is returned, containing the index where a matching
1377 /// element could be inserted while maintaining sorted order.
1381 /// Looks up a series of four elements. The first is found, with a
1382 /// uniquely determined position; the second and third are not
1383 /// found; the fourth could match any position in `[1, 4]`.
1386 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1389 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
1391 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
1393 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
1395 /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
1396 /// assert!(match r { Ok(1..=4) => true, _ => false, });
1398 #[stable(feature = "rust1", since = "1.0.0")]
1400 pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
1401 where F: FnMut(&'a T) -> Ordering
1404 let mut size = s.len();
1408 let mut base = 0usize;
1410 let half = size / 2;
1411 let mid = base + half;
1412 // mid is always in [0, size), that means mid is >= 0 and < size.
1413 // mid >= 0: by definition
1414 // mid < size: mid = size / 2 + size / 4 + size / 8 ...
1415 let cmp = f(unsafe { s.get_unchecked(mid) });
1416 base = if cmp == Greater { base } else { mid };
1419 // base is always in [0, size) because base <= mid.
1420 let cmp = f(unsafe { s.get_unchecked(base) });
1421 if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) }
1425 /// Binary searches this sorted slice with a key extraction function.
1427 /// Assumes that the slice is sorted by the key, for instance with
1428 /// [`sort_by_key`] using the same key extraction function.
1430 /// If the value is found then [`Result::Ok`] is returned, containing the
1431 /// index of the matching element. If there are multiple matches, then any
1432 /// one of the matches could be returned. If the value is not found then
1433 /// [`Result::Err`] is returned, containing the index where a matching
1434 /// element could be inserted while maintaining sorted order.
1436 /// [`sort_by_key`]: #method.sort_by_key
1440 /// Looks up a series of four elements in a slice of pairs sorted by
1441 /// their second elements. The first is found, with a uniquely
1442 /// determined position; the second and third are not found; the
1443 /// fourth could match any position in `[1, 4]`.
1446 /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
1447 /// (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
1448 /// (1, 21), (2, 34), (4, 55)];
1450 /// assert_eq!(s.binary_search_by_key(&13, |&(a,b)| b), Ok(9));
1451 /// assert_eq!(s.binary_search_by_key(&4, |&(a,b)| b), Err(7));
1452 /// assert_eq!(s.binary_search_by_key(&100, |&(a,b)| b), Err(13));
1453 /// let r = s.binary_search_by_key(&1, |&(a,b)| b);
1454 /// assert!(match r { Ok(1..=4) => true, _ => false, });
1456 #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
1458 pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
1459 where F: FnMut(&'a T) -> B,
1462 self.binary_search_by(|k| f(k).cmp(b))
1465 /// Sorts the slice, but may not preserve the order of equal elements.
1467 /// This sort is unstable (i.e., may reorder equal elements), in-place
1468 /// (i.e., does not allocate), and `O(n log n)` worst-case.
1470 /// # Current implementation
1472 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1473 /// which combines the fast average case of randomized quicksort with the fast worst case of
1474 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1475 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1476 /// deterministic behavior.
1478 /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
1479 /// slice consists of several concatenated sorted sequences.
1484 /// let mut v = [-5, 4, 1, -3, 2];
1486 /// v.sort_unstable();
1487 /// assert!(v == [-5, -3, 1, 2, 4]);
1490 /// [pdqsort]: https://github.com/orlp/pdqsort
1491 #[stable(feature = "sort_unstable", since = "1.20.0")]
1493 pub fn sort_unstable(&mut self)
1496 sort::quicksort(self, |a, b| a.lt(b));
1499 /// Sorts the slice with a comparator function, but may not preserve the order of equal
1502 /// This sort is unstable (i.e., may reorder equal elements), in-place
1503 /// (i.e., does not allocate), and `O(n log n)` worst-case.
1505 /// The comparator function must define a total ordering for the elements in the slice. If
1506 /// the ordering is not total, the order of the elements is unspecified. An order is a
1507 /// total order if it is (for all a, b and c):
1509 /// * total and antisymmetric: exactly one of a < b, a == b or a > b is true; and
1510 /// * transitive, a < b and b < c implies a < c. The same must hold for both == and >.
1512 /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use
1513 /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`.
1516 /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
1517 /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
1518 /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
1521 /// # Current implementation
1523 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1524 /// which combines the fast average case of randomized quicksort with the fast worst case of
1525 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1526 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1527 /// deterministic behavior.
1529 /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
1530 /// slice consists of several concatenated sorted sequences.
1535 /// let mut v = [5, 4, 1, 3, 2];
1536 /// v.sort_unstable_by(|a, b| a.cmp(b));
1537 /// assert!(v == [1, 2, 3, 4, 5]);
1539 /// // reverse sorting
1540 /// v.sort_unstable_by(|a, b| b.cmp(a));
1541 /// assert!(v == [5, 4, 3, 2, 1]);
1544 /// [pdqsort]: https://github.com/orlp/pdqsort
1545 #[stable(feature = "sort_unstable", since = "1.20.0")]
1547 pub fn sort_unstable_by<F>(&mut self, mut compare: F)
1548 where F: FnMut(&T, &T) -> Ordering
1550 sort::quicksort(self, |a, b| compare(a, b) == Ordering::Less);
1553 /// Sorts the slice with a key extraction function, but may not preserve the order of equal
1556 /// This sort is unstable (i.e., may reorder equal elements), in-place
1557 /// (i.e., does not allocate), and `O(m n log(m n))` worst-case, where the key function is
1560 /// # Current implementation
1562 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1563 /// which combines the fast average case of randomized quicksort with the fast worst case of
1564 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1565 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1566 /// deterministic behavior.
1568 /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key)
1569 /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_cached_key) in
1570 /// cases where the key function is expensive.
1575 /// let mut v = [-5i32, 4, 1, -3, 2];
1577 /// v.sort_unstable_by_key(|k| k.abs());
1578 /// assert!(v == [1, 2, -3, 4, -5]);
1581 /// [pdqsort]: https://github.com/orlp/pdqsort
1582 #[stable(feature = "sort_unstable", since = "1.20.0")]
1584 pub fn sort_unstable_by_key<K, F>(&mut self, mut f: F)
1585 where F: FnMut(&T) -> K, K: Ord
1587 sort::quicksort(self, |a, b| f(a).lt(&f(b)));
1590 /// Reorder the slice such that the element at `index` is at its final sorted position.
1592 /// This reordering has the additional property that any value at position `i < index` will be
1593 /// less than or equal to any value at a position `j > index`. Additionally, this reordering is
1594 /// unstable (i.e. any number of equal elements may end up at position `index`), in-place
1595 /// (i.e. does not allocate), and `O(n)` worst-case. This function is also/ known as "kth
1596 /// element" in other libraries. It returns a triplet of the following values: all elements less
1597 /// than the one at the given index, the value at the given index, and all elements greater than
1598 /// the one at the given index.
1600 /// # Current implementation
1602 /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
1603 /// used for [`sort_unstable`].
1605 /// [`sort_unstable`]: #method.sort_unstable
1609 /// Panics when `index >= len()`, meaning it always panics on empty slices.
1614 /// #![feature(slice_partition_at_index)]
1616 /// let mut v = [-5i32, 4, 1, -3, 2];
1618 /// // Find the median
1619 /// v.partition_at_index(2);
1621 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
1622 /// // about the specified index.
1623 /// assert!(v == [-3, -5, 1, 2, 4] ||
1624 /// v == [-5, -3, 1, 2, 4] ||
1625 /// v == [-3, -5, 1, 4, 2] ||
1626 /// v == [-5, -3, 1, 4, 2]);
1628 #[unstable(feature = "slice_partition_at_index", issue = "55300")]
1630 pub fn partition_at_index(&mut self, index: usize) -> (&mut [T], &mut T, &mut [T])
1633 let mut f = |a: &T, b: &T| a.lt(b);
1634 sort::partition_at_index(self, index, &mut f)
1637 /// Reorder the slice with a comparator function such that the element at `index` is at its
1638 /// final sorted position.
1640 /// This reordering has the additional property that any value at position `i < index` will be
1641 /// less than or equal to any value at a position `j > index` using the comparator function.
1642 /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
1643 /// position `index`), in-place (i.e. does not allocate), and `O(n)` worst-case. This function
1644 /// is also known as "kth element" in other libraries. It returns a triplet of the following
1645 /// values: all elements less than the one at the given index, the value at the given index,
1646 /// and all elements greater than the one at the given index, using the provided comparator
1649 /// # Current implementation
1651 /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
1652 /// used for [`sort_unstable`].
1654 /// [`sort_unstable`]: #method.sort_unstable
1658 /// Panics when `index >= len()`, meaning it always panics on empty slices.
1663 /// #![feature(slice_partition_at_index)]
1665 /// let mut v = [-5i32, 4, 1, -3, 2];
1667 /// // Find the median as if the slice were sorted in descending order.
1668 /// v.partition_at_index_by(2, |a, b| b.cmp(a));
1670 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
1671 /// // about the specified index.
1672 /// assert!(v == [2, 4, 1, -5, -3] ||
1673 /// v == [2, 4, 1, -3, -5] ||
1674 /// v == [4, 2, 1, -5, -3] ||
1675 /// v == [4, 2, 1, -3, -5]);
1677 #[unstable(feature = "slice_partition_at_index", issue = "55300")]
1679 pub fn partition_at_index_by<F>(&mut self, index: usize, mut compare: F)
1680 -> (&mut [T], &mut T, &mut [T])
1681 where F: FnMut(&T, &T) -> Ordering
1683 let mut f = |a: &T, b: &T| compare(a, b) == Less;
1684 sort::partition_at_index(self, index, &mut f)
1687 /// Reorder the slice with a key extraction function such that the element at `index` is at its
1688 /// final sorted position.
1690 /// This reordering has the additional property that any value at position `i < index` will be
1691 /// less than or equal to any value at a position `j > index` using the key extraction function.
1692 /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
1693 /// position `index`), in-place (i.e. does not allocate), and `O(n)` worst-case. This function
1694 /// is also known as "kth element" in other libraries. It returns a triplet of the following
1695 /// values: all elements less than the one at the given index, the value at the given index, and
1696 /// all elements greater than the one at the given index, using the provided key extraction
1699 /// # Current implementation
1701 /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
1702 /// used for [`sort_unstable`].
1704 /// [`sort_unstable`]: #method.sort_unstable
1708 /// Panics when `index >= len()`, meaning it always panics on empty slices.
1713 /// #![feature(slice_partition_at_index)]
1715 /// let mut v = [-5i32, 4, 1, -3, 2];
1717 /// // Return the median as if the array were sorted according to absolute value.
1718 /// v.partition_at_index_by_key(2, |a| a.abs());
1720 /// // We are only guaranteed the slice will be one of the following, based on the way we sort
1721 /// // about the specified index.
1722 /// assert!(v == [1, 2, -3, 4, -5] ||
1723 /// v == [1, 2, -3, -5, 4] ||
1724 /// v == [2, 1, -3, 4, -5] ||
1725 /// v == [2, 1, -3, -5, 4]);
1727 #[unstable(feature = "slice_partition_at_index", issue = "55300")]
1729 pub fn partition_at_index_by_key<K, F>(&mut self, index: usize, mut f: F)
1730 -> (&mut [T], &mut T, &mut [T])
1731 where F: FnMut(&T) -> K, K: Ord
1733 let mut g = |a: &T, b: &T| f(a).lt(&f(b));
1734 sort::partition_at_index(self, index, &mut g)
1737 /// Moves all consecutive repeated elements to the end of the slice according to the
1738 /// [`PartialEq`] trait implementation.
1740 /// Returns two slices. The first contains no consecutive repeated elements.
1741 /// The second contains all the duplicates in no specified order.
1743 /// If the slice is sorted, the first returned slice contains no duplicates.
1748 /// #![feature(slice_partition_dedup)]
1750 /// let mut slice = [1, 2, 2, 3, 3, 2, 1, 1];
1752 /// let (dedup, duplicates) = slice.partition_dedup();
1754 /// assert_eq!(dedup, [1, 2, 3, 2, 1]);
1755 /// assert_eq!(duplicates, [2, 3, 1]);
1757 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
1759 pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T])
1762 self.partition_dedup_by(|a, b| a == b)
1765 /// Moves all but the first of consecutive elements to the end of the slice satisfying
1766 /// a given equality relation.
1768 /// Returns two slices. The first contains no consecutive repeated elements.
1769 /// The second contains all the duplicates in no specified order.
1771 /// The `same_bucket` function is passed references to two elements from the slice and
1772 /// must determine if the elements compare equal. The elements are passed in opposite order
1773 /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is moved
1774 /// at the end of the slice.
1776 /// If the slice is sorted, the first returned slice contains no duplicates.
1781 /// #![feature(slice_partition_dedup)]
1783 /// let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];
1785 /// let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b));
1787 /// assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
1788 /// assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);
1790 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
1792 pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T])
1793 where F: FnMut(&mut T, &mut T) -> bool
1795 // Although we have a mutable reference to `self`, we cannot make
1796 // *arbitrary* changes. The `same_bucket` calls could panic, so we
1797 // must ensure that the slice is in a valid state at all times.
1799 // The way that we handle this is by using swaps; we iterate
1800 // over all the elements, swapping as we go so that at the end
1801 // the elements we wish to keep are in the front, and those we
1802 // wish to reject are at the back. We can then split the slice.
1803 // This operation is still O(n).
1805 // Example: We start in this state, where `r` represents "next
1806 // read" and `w` represents "next_write`.
1809 // +---+---+---+---+---+---+
1810 // | 0 | 1 | 1 | 2 | 3 | 3 |
1811 // +---+---+---+---+---+---+
1814 // Comparing self[r] against self[w-1], this is not a duplicate, so
1815 // we swap self[r] and self[w] (no effect as r==w) and then increment both
1816 // r and w, leaving us with:
1819 // +---+---+---+---+---+---+
1820 // | 0 | 1 | 1 | 2 | 3 | 3 |
1821 // +---+---+---+---+---+---+
1824 // Comparing self[r] against self[w-1], this value is a duplicate,
1825 // so we increment `r` but leave everything else unchanged:
1828 // +---+---+---+---+---+---+
1829 // | 0 | 1 | 1 | 2 | 3 | 3 |
1830 // +---+---+---+---+---+---+
1833 // Comparing self[r] against self[w-1], this is not a duplicate,
1834 // so swap self[r] and self[w] and advance r and w:
1837 // +---+---+---+---+---+---+
1838 // | 0 | 1 | 2 | 1 | 3 | 3 |
1839 // +---+---+---+---+---+---+
1842 // Not a duplicate, repeat:
1845 // +---+---+---+---+---+---+
1846 // | 0 | 1 | 2 | 3 | 1 | 3 |
1847 // +---+---+---+---+---+---+
1850 // Duplicate, advance r. End of slice. Split at w.
1852 let len = self.len();
1854 return (self, &mut [])
1857 let ptr = self.as_mut_ptr();
1858 let mut next_read: usize = 1;
1859 let mut next_write: usize = 1;
1862 // Avoid bounds checks by using raw pointers.
1863 while next_read < len {
1864 let ptr_read = ptr.add(next_read);
1865 let prev_ptr_write = ptr.add(next_write - 1);
1866 if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) {
1867 if next_read != next_write {
1868 let ptr_write = prev_ptr_write.offset(1);
1869 mem::swap(&mut *ptr_read, &mut *ptr_write);
1877 self.split_at_mut(next_write)
1880 /// Moves all but the first of consecutive elements to the end of the slice that resolve
1881 /// to the same key.
1883 /// Returns two slices. The first contains no consecutive repeated elements.
1884 /// The second contains all the duplicates in no specified order.
1886 /// If the slice is sorted, the first returned slice contains no duplicates.
1891 /// #![feature(slice_partition_dedup)]
1893 /// let mut slice = [10, 20, 21, 30, 30, 20, 11, 13];
1895 /// let (dedup, duplicates) = slice.partition_dedup_by_key(|i| *i / 10);
1897 /// assert_eq!(dedup, [10, 20, 30, 20, 11]);
1898 /// assert_eq!(duplicates, [21, 30, 13]);
1900 #[unstable(feature = "slice_partition_dedup", issue = "54279")]
1902 pub fn partition_dedup_by_key<K, F>(&mut self, mut key: F) -> (&mut [T], &mut [T])
1903 where F: FnMut(&mut T) -> K,
1906 self.partition_dedup_by(|a, b| key(a) == key(b))
1909 /// Rotates the slice in-place such that the first `mid` elements of the
1910 /// slice move to the end while the last `self.len() - mid` elements move to
1911 /// the front. After calling `rotate_left`, the element previously at index
1912 /// `mid` will become the first element in the slice.
1916 /// This function will panic if `mid` is greater than the length of the
1917 /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op
1922 /// Takes linear (in `self.len()`) time.
1927 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1928 /// a.rotate_left(2);
1929 /// assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
1932 /// Rotating a subslice:
1935 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1936 /// a[1..5].rotate_left(1);
1937 /// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
1939 #[stable(feature = "slice_rotate", since = "1.26.0")]
1940 pub fn rotate_left(&mut self, mid: usize) {
1941 assert!(mid <= self.len());
1942 let k = self.len() - mid;
1945 let p = self.as_mut_ptr();
1946 rotate::ptr_rotate(mid, p.add(mid), k);
1950 /// Rotates the slice in-place such that the first `self.len() - k`
1951 /// elements of the slice move to the end while the last `k` elements move
1952 /// to the front. After calling `rotate_right`, the element previously at
1953 /// index `self.len() - k` will become the first element in the slice.
1957 /// This function will panic if `k` is greater than the length of the
1958 /// slice. Note that `k == self.len()` does _not_ panic and is a no-op
1963 /// Takes linear (in `self.len()`) time.
1968 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1969 /// a.rotate_right(2);
1970 /// assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
1973 /// Rotate a subslice:
1976 /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1977 /// a[1..5].rotate_right(1);
1978 /// assert_eq!(a, ['a', 'e', 'b', 'c', 'd', 'f']);
1980 #[stable(feature = "slice_rotate", since = "1.26.0")]
1981 pub fn rotate_right(&mut self, k: usize) {
1982 assert!(k <= self.len());
1983 let mid = self.len() - k;
1986 let p = self.as_mut_ptr();
1987 rotate::ptr_rotate(mid, p.add(mid), k);
1991 /// Copies the elements from `src` into `self`.
1993 /// The length of `src` must be the same as `self`.
1995 /// If `src` implements `Copy`, it can be more performant to use
1996 /// [`copy_from_slice`].
2000 /// This function will panic if the two slices have different lengths.
2004 /// Cloning two elements from a slice into another:
2007 /// let src = [1, 2, 3, 4];
2008 /// let mut dst = [0, 0];
2010 /// // Because the slices have to be the same length,
2011 /// // we slice the source slice from four elements
2012 /// // to two. It will panic if we don't do this.
2013 /// dst.clone_from_slice(&src[2..]);
2015 /// assert_eq!(src, [1, 2, 3, 4]);
2016 /// assert_eq!(dst, [3, 4]);
2019 /// Rust enforces that there can only be one mutable reference with no
2020 /// immutable references to a particular piece of data in a particular
2021 /// scope. Because of this, attempting to use `clone_from_slice` on a
2022 /// single slice will result in a compile failure:
2025 /// let mut slice = [1, 2, 3, 4, 5];
2027 /// slice[..2].clone_from_slice(&slice[3..]); // compile fail!
2030 /// To work around this, we can use [`split_at_mut`] to create two distinct
2031 /// sub-slices from a slice:
2034 /// let mut slice = [1, 2, 3, 4, 5];
2037 /// let (left, right) = slice.split_at_mut(2);
2038 /// left.clone_from_slice(&right[1..]);
2041 /// assert_eq!(slice, [4, 5, 3, 4, 5]);
2044 /// [`copy_from_slice`]: #method.copy_from_slice
2045 /// [`split_at_mut`]: #method.split_at_mut
2046 #[stable(feature = "clone_from_slice", since = "1.7.0")]
2047 pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
2048 assert!(self.len() == src.len(),
2049 "destination and source slices have different lengths");
2050 // NOTE: We need to explicitly slice them to the same length
2051 // for bounds checking to be elided, and the optimizer will
2052 // generate memcpy for simple cases (for example T = u8).
2053 let len = self.len();
2054 let src = &src[..len];
2056 self[i].clone_from(&src[i]);
2061 /// Copies all elements from `src` into `self`, using a memcpy.
2063 /// The length of `src` must be the same as `self`.
2065 /// If `src` does not implement `Copy`, use [`clone_from_slice`].
2069 /// This function will panic if the two slices have different lengths.
2073 /// Copying two elements from a slice into another:
2076 /// let src = [1, 2, 3, 4];
2077 /// let mut dst = [0, 0];
2079 /// // Because the slices have to be the same length,
2080 /// // we slice the source slice from four elements
2081 /// // to two. It will panic if we don't do this.
2082 /// dst.copy_from_slice(&src[2..]);
2084 /// assert_eq!(src, [1, 2, 3, 4]);
2085 /// assert_eq!(dst, [3, 4]);
2088 /// Rust enforces that there can only be one mutable reference with no
2089 /// immutable references to a particular piece of data in a particular
2090 /// scope. Because of this, attempting to use `copy_from_slice` on a
2091 /// single slice will result in a compile failure:
2094 /// let mut slice = [1, 2, 3, 4, 5];
2096 /// slice[..2].copy_from_slice(&slice[3..]); // compile fail!
2099 /// To work around this, we can use [`split_at_mut`] to create two distinct
2100 /// sub-slices from a slice:
2103 /// let mut slice = [1, 2, 3, 4, 5];
2106 /// let (left, right) = slice.split_at_mut(2);
2107 /// left.copy_from_slice(&right[1..]);
2110 /// assert_eq!(slice, [4, 5, 3, 4, 5]);
2113 /// [`clone_from_slice`]: #method.clone_from_slice
2114 /// [`split_at_mut`]: #method.split_at_mut
2115 #[stable(feature = "copy_from_slice", since = "1.9.0")]
2116 pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
2117 assert_eq!(self.len(), src.len(),
2118 "destination and source slices have different lengths");
2120 ptr::copy_nonoverlapping(
2121 src.as_ptr(), self.as_mut_ptr(), self.len());
2125 /// Copies elements from one part of the slice to another part of itself,
2126 /// using a memmove.
2128 /// `src` is the range within `self` to copy from. `dest` is the starting
2129 /// index of the range within `self` to copy to, which will have the same
2130 /// length as `src`. The two ranges may overlap. The ends of the two ranges
2131 /// must be less than or equal to `self.len()`.
2135 /// This function will panic if either range exceeds the end of the slice,
2136 /// or if the end of `src` is before the start.
2140 /// Copying four bytes within a slice:
2143 /// # #![feature(copy_within)]
2144 /// let mut bytes = *b"Hello, World!";
2146 /// bytes.copy_within(1..5, 8);
2148 /// assert_eq!(&bytes, b"Hello, Wello!");
2150 #[unstable(feature = "copy_within", issue = "54236")]
2151 pub fn copy_within<R: ops::RangeBounds<usize>>(&mut self, src: R, dest: usize)
2155 let src_start = match src.start_bound() {
2156 ops::Bound::Included(&n) => n,
2157 ops::Bound::Excluded(&n) => n
2159 .unwrap_or_else(|| slice_index_overflow_fail()),
2160 ops::Bound::Unbounded => 0,
2162 let src_end = match src.end_bound() {
2163 ops::Bound::Included(&n) => n
2165 .unwrap_or_else(|| slice_index_overflow_fail()),
2166 ops::Bound::Excluded(&n) => n,
2167 ops::Bound::Unbounded => self.len(),
2169 assert!(src_start <= src_end, "src end is before src start");
2170 assert!(src_end <= self.len(), "src is out of bounds");
2171 let count = src_end - src_start;
2172 assert!(dest <= self.len() - count, "dest is out of bounds");
2175 self.get_unchecked(src_start),
2176 self.get_unchecked_mut(dest),
2182 /// Swaps all elements in `self` with those in `other`.
2184 /// The length of `other` must be the same as `self`.
2188 /// This function will panic if the two slices have different lengths.
2192 /// Swapping two elements across slices:
2195 /// let mut slice1 = [0, 0];
2196 /// let mut slice2 = [1, 2, 3, 4];
2198 /// slice1.swap_with_slice(&mut slice2[2..]);
2200 /// assert_eq!(slice1, [3, 4]);
2201 /// assert_eq!(slice2, [1, 2, 0, 0]);
2204 /// Rust enforces that there can only be one mutable reference to a
2205 /// particular piece of data in a particular scope. Because of this,
2206 /// attempting to use `swap_with_slice` on a single slice will result in
2207 /// a compile failure:
2210 /// let mut slice = [1, 2, 3, 4, 5];
2211 /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail!
2214 /// To work around this, we can use [`split_at_mut`] to create two distinct
2215 /// mutable sub-slices from a slice:
2218 /// let mut slice = [1, 2, 3, 4, 5];
2221 /// let (left, right) = slice.split_at_mut(2);
2222 /// left.swap_with_slice(&mut right[1..]);
2225 /// assert_eq!(slice, [4, 5, 3, 1, 2]);
2228 /// [`split_at_mut`]: #method.split_at_mut
2229 #[stable(feature = "swap_with_slice", since = "1.27.0")]
2230 pub fn swap_with_slice(&mut self, other: &mut [T]) {
2231 assert!(self.len() == other.len(),
2232 "destination and source slices have different lengths");
2234 ptr::swap_nonoverlapping(
2235 self.as_mut_ptr(), other.as_mut_ptr(), self.len());
2239 /// Function to calculate lengths of the middle and trailing slice for `align_to{,_mut}`.
2240 fn align_to_offsets<U>(&self) -> (usize, usize) {
2241 // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
2242 // lowest number of `T`s. And how many `T`s we need for each such "multiple".
2244 // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
2245 // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
2246 // place of every 3 Ts in the `rest` slice. A bit more complicated.
2248 // Formula to calculate this is:
2250 // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
2251 // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
2253 // Expanded and simplified:
2255 // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
2256 // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
2258 // Luckily since all this is constant-evaluated... performance here matters not!
2260 fn gcd(a: usize, b: usize) -> usize {
2261 use crate::intrinsics;
2262 // iterative stein’s algorithm
2263 // We should still make this `const fn` (and revert to recursive algorithm if we do)
2264 // because relying on llvm to consteval all this is… well, it makes me uncomfortable.
2265 let (ctz_a, mut ctz_b) = unsafe {
2266 if a == 0 { return b; }
2267 if b == 0 { return a; }
2268 (intrinsics::cttz_nonzero(a), intrinsics::cttz_nonzero(b))
2270 let k = ctz_a.min(ctz_b);
2271 let mut a = a >> ctz_a;
2274 // remove all factors of 2 from b
2277 mem::swap(&mut a, &mut b);
2284 ctz_b = intrinsics::cttz_nonzero(b);
2289 let gcd: usize = gcd(mem::size_of::<T>(), mem::size_of::<U>());
2290 let ts: usize = mem::size_of::<U>() / gcd;
2291 let us: usize = mem::size_of::<T>() / gcd;
2293 // Armed with this knowledge, we can find how many `U`s we can fit!
2294 let us_len = self.len() / ts * us;
2295 // And how many `T`s will be in the trailing slice!
2296 let ts_len = self.len() % ts;
2300 /// Transmute the slice to a slice of another type, ensuring alignment of the types is
2303 /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
2304 /// slice of a new type, and the suffix slice. The method does a best effort to make the
2305 /// middle slice the greatest length possible for a given type and input slice, but only
2306 /// your algorithm's performance should depend on that, not its correctness.
2308 /// This method has no purpose when either input element `T` or output element `U` are
2309 /// zero-sized and will return the original slice without splitting anything.
2313 /// This method is essentially a `transmute` with respect to the elements in the returned
2314 /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
2322 /// let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
2323 /// let (prefix, shorts, suffix) = bytes.align_to::<u16>();
2324 /// // less_efficient_algorithm_for_bytes(prefix);
2325 /// // more_efficient_algorithm_for_aligned_shorts(shorts);
2326 /// // less_efficient_algorithm_for_bytes(suffix);
2329 #[stable(feature = "slice_align_to", since = "1.30.0")]
2330 pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) {
2331 // Note that most of this function will be constant-evaluated,
2332 if mem::size_of::<U>() == 0 || mem::size_of::<T>() == 0 {
2333 // handle ZSTs specially, which is – don't handle them at all.
2334 return (self, &[], &[]);
2337 // First, find at what point do we split between the first and 2nd slice. Easy with
2338 // ptr.align_offset.
2339 let ptr = self.as_ptr();
2340 let offset = crate::ptr::align_offset(ptr, mem::align_of::<U>());
2341 if offset > self.len() {
2344 let (left, rest) = self.split_at(offset);
2345 // now `rest` is definitely aligned, so `from_raw_parts_mut` below is okay
2346 let (us_len, ts_len) = rest.align_to_offsets::<U>();
2348 from_raw_parts(rest.as_ptr() as *const U, us_len),
2349 from_raw_parts(rest.as_ptr().add(rest.len() - ts_len), ts_len))
2353 /// Transmute the slice to a slice of another type, ensuring alignment of the types is
2356 /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
2357 /// slice of a new type, and the suffix slice. The method does a best effort to make the
2358 /// middle slice the greatest length possible for a given type and input slice, but only
2359 /// your algorithm's performance should depend on that, not its correctness.
2361 /// This method has no purpose when either input element `T` or output element `U` are
2362 /// zero-sized and will return the original slice without splitting anything.
2366 /// This method is essentially a `transmute` with respect to the elements in the returned
2367 /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
2375 /// let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
2376 /// let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
2377 /// // less_efficient_algorithm_for_bytes(prefix);
2378 /// // more_efficient_algorithm_for_aligned_shorts(shorts);
2379 /// // less_efficient_algorithm_for_bytes(suffix);
2382 #[stable(feature = "slice_align_to", since = "1.30.0")]
2383 pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) {
2384 // Note that most of this function will be constant-evaluated,
2385 if mem::size_of::<U>() == 0 || mem::size_of::<T>() == 0 {
2386 // handle ZSTs specially, which is – don't handle them at all.
2387 return (self, &mut [], &mut []);
2390 // First, find at what point do we split between the first and 2nd slice. Easy with
2391 // ptr.align_offset.
2392 let ptr = self.as_ptr();
2393 let offset = crate::ptr::align_offset(ptr, mem::align_of::<U>());
2394 if offset > self.len() {
2395 (self, &mut [], &mut [])
2397 let (left, rest) = self.split_at_mut(offset);
2398 // now `rest` is definitely aligned, so `from_raw_parts_mut` below is okay
2399 let (us_len, ts_len) = rest.align_to_offsets::<U>();
2400 let mut_ptr = rest.as_mut_ptr();
2402 from_raw_parts_mut(mut_ptr as *mut U, us_len),
2403 from_raw_parts_mut(mut_ptr.add(rest.len() - ts_len), ts_len))
2407 /// Checks if the elements of this slice are sorted.
2409 /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
2410 /// slice yields exactly zero or one element, `true` is returned.
2412 /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
2413 /// implies that this function returns `false` if any two consecutive items are not
2419 /// #![feature(is_sorted)]
2420 /// let empty: [i32; 0] = [];
2422 /// assert!([1, 2, 2, 9].is_sorted());
2423 /// assert!(![1, 3, 2, 4].is_sorted());
2424 /// assert!([0].is_sorted());
2425 /// assert!(empty.is_sorted());
2426 /// assert!(![0.0, 1.0, std::f32::NAN].is_sorted());
2429 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2430 pub fn is_sorted(&self) -> bool
2434 self.is_sorted_by(|a, b| a.partial_cmp(b))
2437 /// Checks if the elements of this slice are sorted using the given comparator function.
2439 /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
2440 /// function to determine the ordering of two elements. Apart from that, it's equivalent to
2441 /// [`is_sorted`]; see its documentation for more information.
2443 /// [`is_sorted`]: #method.is_sorted
2444 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2445 pub fn is_sorted_by<F>(&self, mut compare: F) -> bool
2447 F: FnMut(&T, &T) -> Option<Ordering>
2449 self.iter().is_sorted_by(|a, b| compare(*a, *b))
2452 /// Checks if the elements of this slice are sorted using the given key extraction function.
2454 /// Instead of comparing the slice's elements directly, this function compares the keys of the
2455 /// elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see its
2456 /// documentation for more information.
2458 /// [`is_sorted`]: #method.is_sorted
2463 /// #![feature(is_sorted)]
2465 /// assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
2466 /// assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
2469 #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2470 pub fn is_sorted_by_key<F, K>(&self, mut f: F) -> bool
2475 self.is_sorted_by(|a, b| f(a).partial_cmp(&f(b)))
2479 #[lang = "slice_u8"]
2482 /// Checks if all bytes in this slice are within the ASCII range.
2483 #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2485 pub fn is_ascii(&self) -> bool {
2486 self.iter().all(|b| b.is_ascii())
2489 /// Checks that two slices are an ASCII case-insensitive match.
2491 /// Same as `to_ascii_lowercase(a) == to_ascii_lowercase(b)`,
2492 /// but without allocating and copying temporaries.
2493 #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2495 pub fn eq_ignore_ascii_case(&self, other: &[u8]) -> bool {
2496 self.len() == other.len() &&
2497 self.iter().zip(other).all(|(a, b)| {
2498 a.eq_ignore_ascii_case(b)
2502 /// Converts this slice to its ASCII upper case equivalent in-place.
2504 /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
2505 /// but non-ASCII letters are unchanged.
2507 /// To return a new uppercased value without modifying the existing one, use
2508 /// [`to_ascii_uppercase`].
2510 /// [`to_ascii_uppercase`]: #method.to_ascii_uppercase
2511 #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2513 pub fn make_ascii_uppercase(&mut self) {
2515 byte.make_ascii_uppercase();
2519 /// Converts this slice to its ASCII lower case equivalent in-place.
2521 /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
2522 /// but non-ASCII letters are unchanged.
2524 /// To return a new lowercased value without modifying the existing one, use
2525 /// [`to_ascii_lowercase`].
2527 /// [`to_ascii_lowercase`]: #method.to_ascii_lowercase
2528 #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2530 pub fn make_ascii_lowercase(&mut self) {
2532 byte.make_ascii_lowercase();
2538 #[stable(feature = "rust1", since = "1.0.0")]
2539 impl<T, I> ops::Index<I> for [T]
2540 where I: SliceIndex<[T]>
2542 type Output = I::Output;
2545 fn index(&self, index: I) -> &I::Output {
2550 #[stable(feature = "rust1", since = "1.0.0")]
2551 impl<T, I> ops::IndexMut<I> for [T]
2552 where I: SliceIndex<[T]>
2555 fn index_mut(&mut self, index: I) -> &mut I::Output {
2556 index.index_mut(self)
2562 fn slice_index_len_fail(index: usize, len: usize) -> ! {
2563 panic!("index {} out of range for slice of length {}", index, len);
2568 fn slice_index_order_fail(index: usize, end: usize) -> ! {
2569 panic!("slice index starts at {} but ends at {}", index, end);
2574 fn slice_index_overflow_fail() -> ! {
2575 panic!("attempted to index slice up to maximum usize");
2578 mod private_slice_index {
2580 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2583 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2584 impl Sealed for usize {}
2585 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2586 impl Sealed for ops::Range<usize> {}
2587 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2588 impl Sealed for ops::RangeTo<usize> {}
2589 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2590 impl Sealed for ops::RangeFrom<usize> {}
2591 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2592 impl Sealed for ops::RangeFull {}
2593 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2594 impl Sealed for ops::RangeInclusive<usize> {}
2595 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2596 impl Sealed for ops::RangeToInclusive<usize> {}
2599 /// A helper trait used for indexing operations.
2600 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2601 #[rustc_on_unimplemented(
2604 label = "string indices are ranges of `usize`",
2607 all(any(T = "str", T = "&str", T = "std::string::String"), _Self="{integer}"),
2608 note="you can use `.chars().nth()` or `.bytes().nth()`
2609 see chapter in The Book <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>"
2611 message = "the type `{T}` cannot be indexed by `{Self}`",
2612 label = "slice indices are of type `usize` or ranges of `usize`",
2614 pub trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
2615 /// The output type returned by methods.
2616 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2617 type Output: ?Sized;
2619 /// Returns a shared reference to the output at this location, if in
2621 #[unstable(feature = "slice_index_methods", issue = "0")]
2622 fn get(self, slice: &T) -> Option<&Self::Output>;
2624 /// Returns a mutable reference to the output at this location, if in
2626 #[unstable(feature = "slice_index_methods", issue = "0")]
2627 fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
2629 /// Returns a shared reference to the output at this location, without
2630 /// performing any bounds checking.
2631 #[unstable(feature = "slice_index_methods", issue = "0")]
2632 unsafe fn get_unchecked(self, slice: &T) -> &Self::Output;
2634 /// Returns a mutable reference to the output at this location, without
2635 /// performing any bounds checking.
2636 #[unstable(feature = "slice_index_methods", issue = "0")]
2637 unsafe fn get_unchecked_mut(self, slice: &mut T) -> &mut Self::Output;
2639 /// Returns a shared reference to the output at this location, panicking
2640 /// if out of bounds.
2641 #[unstable(feature = "slice_index_methods", issue = "0")]
2642 fn index(self, slice: &T) -> &Self::Output;
2644 /// Returns a mutable reference to the output at this location, panicking
2645 /// if out of bounds.
2646 #[unstable(feature = "slice_index_methods", issue = "0")]
2647 fn index_mut(self, slice: &mut T) -> &mut Self::Output;
2650 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2651 impl<T> SliceIndex<[T]> for usize {
2655 fn get(self, slice: &[T]) -> Option<&T> {
2656 if self < slice.len() {
2658 Some(self.get_unchecked(slice))
2666 fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
2667 if self < slice.len() {
2669 Some(self.get_unchecked_mut(slice))
2677 unsafe fn get_unchecked(self, slice: &[T]) -> &T {
2678 &*slice.as_ptr().add(self)
2682 unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut T {
2683 &mut *slice.as_mut_ptr().add(self)
2687 fn index(self, slice: &[T]) -> &T {
2688 // N.B., use intrinsic indexing
2693 fn index_mut(self, slice: &mut [T]) -> &mut T {
2694 // N.B., use intrinsic indexing
2699 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2700 impl<T> SliceIndex<[T]> for ops::Range<usize> {
2704 fn get(self, slice: &[T]) -> Option<&[T]> {
2705 if self.start > self.end || self.end > slice.len() {
2709 Some(self.get_unchecked(slice))
2715 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2716 if self.start > self.end || self.end > slice.len() {
2720 Some(self.get_unchecked_mut(slice))
2726 unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2727 from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start)
2731 unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2732 from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start)
2736 fn index(self, slice: &[T]) -> &[T] {
2737 if self.start > self.end {
2738 slice_index_order_fail(self.start, self.end);
2739 } else if self.end > slice.len() {
2740 slice_index_len_fail(self.end, slice.len());
2743 self.get_unchecked(slice)
2748 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2749 if self.start > self.end {
2750 slice_index_order_fail(self.start, self.end);
2751 } else if self.end > slice.len() {
2752 slice_index_len_fail(self.end, slice.len());
2755 self.get_unchecked_mut(slice)
2760 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2761 impl<T> SliceIndex<[T]> for ops::RangeTo<usize> {
2765 fn get(self, slice: &[T]) -> Option<&[T]> {
2766 (0..self.end).get(slice)
2770 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2771 (0..self.end).get_mut(slice)
2775 unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2776 (0..self.end).get_unchecked(slice)
2780 unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2781 (0..self.end).get_unchecked_mut(slice)
2785 fn index(self, slice: &[T]) -> &[T] {
2786 (0..self.end).index(slice)
2790 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2791 (0..self.end).index_mut(slice)
2795 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2796 impl<T> SliceIndex<[T]> for ops::RangeFrom<usize> {
2800 fn get(self, slice: &[T]) -> Option<&[T]> {
2801 (self.start..slice.len()).get(slice)
2805 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2806 (self.start..slice.len()).get_mut(slice)
2810 unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2811 (self.start..slice.len()).get_unchecked(slice)
2815 unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2816 (self.start..slice.len()).get_unchecked_mut(slice)
2820 fn index(self, slice: &[T]) -> &[T] {
2821 (self.start..slice.len()).index(slice)
2825 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2826 (self.start..slice.len()).index_mut(slice)
2830 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2831 impl<T> SliceIndex<[T]> for ops::RangeFull {
2835 fn get(self, slice: &[T]) -> Option<&[T]> {
2840 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2845 unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2850 unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2855 fn index(self, slice: &[T]) -> &[T] {
2860 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2866 #[stable(feature = "inclusive_range", since = "1.26.0")]
2867 impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
2871 fn get(self, slice: &[T]) -> Option<&[T]> {
2872 if *self.end() == usize::max_value() { None }
2873 else { (*self.start()..self.end() + 1).get(slice) }
2877 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2878 if *self.end() == usize::max_value() { None }
2879 else { (*self.start()..self.end() + 1).get_mut(slice) }
2883 unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2884 (*self.start()..self.end() + 1).get_unchecked(slice)
2888 unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2889 (*self.start()..self.end() + 1).get_unchecked_mut(slice)
2893 fn index(self, slice: &[T]) -> &[T] {
2894 if *self.end() == usize::max_value() { slice_index_overflow_fail(); }
2895 (*self.start()..self.end() + 1).index(slice)
2899 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2900 if *self.end() == usize::max_value() { slice_index_overflow_fail(); }
2901 (*self.start()..self.end() + 1).index_mut(slice)
2905 #[stable(feature = "inclusive_range", since = "1.26.0")]
2906 impl<T> SliceIndex<[T]> for ops::RangeToInclusive<usize> {
2910 fn get(self, slice: &[T]) -> Option<&[T]> {
2911 (0..=self.end).get(slice)
2915 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2916 (0..=self.end).get_mut(slice)
2920 unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2921 (0..=self.end).get_unchecked(slice)
2925 unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2926 (0..=self.end).get_unchecked_mut(slice)
2930 fn index(self, slice: &[T]) -> &[T] {
2931 (0..=self.end).index(slice)
2935 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2936 (0..=self.end).index_mut(slice)
2940 ////////////////////////////////////////////////////////////////////////////////
2942 ////////////////////////////////////////////////////////////////////////////////
2944 #[stable(feature = "rust1", since = "1.0.0")]
2945 impl<T> Default for &[T] {
2946 /// Creates an empty slice.
2947 fn default() -> Self { &[] }
2950 #[stable(feature = "mut_slice_default", since = "1.5.0")]
2951 impl<T> Default for &mut [T] {
2952 /// Creates a mutable empty slice.
2953 fn default() -> Self { &mut [] }
2960 #[stable(feature = "rust1", since = "1.0.0")]
2961 impl<'a, T> IntoIterator for &'a [T] {
2963 type IntoIter = Iter<'a, T>;
2965 fn into_iter(self) -> Iter<'a, T> {
2970 #[stable(feature = "rust1", since = "1.0.0")]
2971 impl<'a, T> IntoIterator for &'a mut [T] {
2972 type Item = &'a mut T;
2973 type IntoIter = IterMut<'a, T>;
2975 fn into_iter(self) -> IterMut<'a, T> {
2980 // Macro helper functions
2982 fn size_from_ptr<T>(_: *const T) -> usize {
2986 // Inlining is_empty and len makes a huge performance difference
2987 macro_rules! is_empty {
2988 // The way we encode the length of a ZST iterator, this works both for ZST
2990 ($self: ident) => {$self.ptr == $self.end}
2992 // To get rid of some bounds checks (see `position`), we compute the length in a somewhat
2993 // unexpected way. (Tested by `codegen/slice-position-bounds-check`.)
2995 ($self: ident) => {{
2996 let start = $self.ptr;
2997 let diff = ($self.end as usize).wrapping_sub(start as usize);
2998 let size = size_from_ptr(start);
3002 // Using division instead of `offset_from` helps LLVM remove bounds checks
3008 // The shared definition of the `Iter` and `IterMut` iterators
3009 macro_rules! iterator {
3011 struct $name:ident -> $ptr:ty,
3017 impl<'a, T> $name<'a, T> {
3018 // Helper function for creating a slice from the iterator.
3020 fn make_slice(&self) -> &'a [T] {
3021 unsafe { from_raw_parts(self.ptr, len!(self)) }
3024 // Helper function for moving the start of the iterator forwards by `offset` elements,
3025 // returning the old start.
3026 // Unsafe because the offset must be in-bounds or one-past-the-end.
3028 unsafe fn post_inc_start(&mut self, offset: isize) -> * $raw_mut T {
3029 if mem::size_of::<T>() == 0 {
3030 // This is *reducing* the length. `ptr` never changes with ZST.
3031 self.end = (self.end as * $raw_mut u8).wrapping_offset(-offset) as * $raw_mut T;
3035 self.ptr = self.ptr.offset(offset);
3040 // Helper function for moving the end of the iterator backwards by `offset` elements,
3041 // returning the new end.
3042 // Unsafe because the offset must be in-bounds or one-past-the-end.
3044 unsafe fn pre_dec_end(&mut self, offset: isize) -> * $raw_mut T {
3045 if mem::size_of::<T>() == 0 {
3046 self.end = (self.end as * $raw_mut u8).wrapping_offset(-offset) as * $raw_mut T;
3049 self.end = self.end.offset(-offset);
3055 #[stable(feature = "rust1", since = "1.0.0")]
3056 impl<T> ExactSizeIterator for $name<'_, T> {
3058 fn len(&self) -> usize {
3063 fn is_empty(&self) -> bool {
3068 #[stable(feature = "rust1", since = "1.0.0")]
3069 impl<'a, T> Iterator for $name<'a, T> {
3073 fn next(&mut self) -> Option<$elem> {
3074 // could be implemented with slices, but this avoids bounds checks
3076 assume(!self.ptr.is_null());
3077 if mem::size_of::<T>() != 0 {
3078 assume(!self.end.is_null());
3080 if is_empty!(self) {
3083 Some(& $( $mut_ )* *self.post_inc_start(1))
3089 fn size_hint(&self) -> (usize, Option<usize>) {
3090 let exact = len!(self);
3091 (exact, Some(exact))
3095 fn count(self) -> usize {
3100 fn nth(&mut self, n: usize) -> Option<$elem> {
3101 if n >= len!(self) {
3102 // This iterator is now empty.
3103 if mem::size_of::<T>() == 0 {
3104 // We have to do it this way as `ptr` may never be 0, but `end`
3105 // could be (due to wrapping).
3106 self.end = self.ptr;
3108 self.ptr = self.end;
3112 // We are in bounds. `offset` does the right thing even for ZSTs.
3114 let elem = Some(& $( $mut_ )* *self.ptr.add(n));
3115 self.post_inc_start((n as isize).wrapping_add(1));
3121 fn last(mut self) -> Option<$elem> {
3126 fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
3127 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
3129 // manual unrolling is needed when there are conditional exits from the loop
3130 let mut accum = init;
3132 while len!(self) >= 4 {
3133 accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
3134 accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
3135 accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
3136 accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
3138 while !is_empty!(self) {
3139 accum = f(accum, & $( $mut_ )* *self.post_inc_start(1))?;
3146 fn fold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
3147 where Fold: FnMut(Acc, Self::Item) -> Acc,
3149 // Let LLVM unroll this, rather than using the default
3150 // impl that would force the manual unrolling above
3151 let mut accum = init;
3152 while let Some(x) = self.next() {
3153 accum = f(accum, x);
3159 #[rustc_inherit_overflow_checks]
3160 fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
3162 P: FnMut(Self::Item) -> bool,
3164 // The addition might panic on overflow.
3166 self.try_fold(0, move |i, x| {
3167 if predicate(x) { Err(i) }
3171 unsafe { assume(i < n) };
3177 fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
3178 P: FnMut(Self::Item) -> bool,
3179 Self: Sized + ExactSizeIterator + DoubleEndedIterator
3181 // No need for an overflow check here, because `ExactSizeIterator`
3183 self.try_rfold(n, move |i, x| {
3185 if predicate(x) { Err(i) }
3189 unsafe { assume(i < n) };
3197 #[stable(feature = "rust1", since = "1.0.0")]
3198 impl<'a, T> DoubleEndedIterator for $name<'a, T> {
3200 fn next_back(&mut self) -> Option<$elem> {
3201 // could be implemented with slices, but this avoids bounds checks
3203 assume(!self.ptr.is_null());
3204 if mem::size_of::<T>() != 0 {
3205 assume(!self.end.is_null());
3207 if is_empty!(self) {
3210 Some(& $( $mut_ )* *self.pre_dec_end(1))
3216 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
3217 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
3219 // manual unrolling is needed when there are conditional exits from the loop
3220 let mut accum = init;
3222 while len!(self) >= 4 {
3223 accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
3224 accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
3225 accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
3226 accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
3228 // inlining is_empty everywhere makes a huge performance difference
3229 while !is_empty!(self) {
3230 accum = f(accum, & $( $mut_ )* *self.pre_dec_end(1))?;
3237 fn rfold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
3238 where Fold: FnMut(Acc, Self::Item) -> Acc,
3240 // Let LLVM unroll this, rather than using the default
3241 // impl that would force the manual unrolling above
3242 let mut accum = init;
3243 while let Some(x) = self.next_back() {
3244 accum = f(accum, x);
3250 #[stable(feature = "fused", since = "1.26.0")]
3251 impl<T> FusedIterator for $name<'_, T> {}
3253 #[unstable(feature = "trusted_len", issue = "37572")]
3254 unsafe impl<T> TrustedLen for $name<'_, T> {}
3258 /// Immutable slice iterator
3260 /// This struct is created by the [`iter`] method on [slices].
3267 /// // First, we declare a type which has `iter` method to get the `Iter` struct (&[usize here]):
3268 /// let slice = &[1, 2, 3];
3270 /// // Then, we iterate over it:
3271 /// for element in slice.iter() {
3272 /// println!("{}", element);
3276 /// [`iter`]: ../../std/primitive.slice.html#method.iter
3277 /// [slices]: ../../std/primitive.slice.html
3278 #[stable(feature = "rust1", since = "1.0.0")]
3279 pub struct Iter<'a, T: 'a> {
3281 end: *const T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that
3282 // ptr == end is a quick test for the Iterator being empty, that works
3283 // for both ZST and non-ZST.
3284 _marker: marker::PhantomData<&'a T>,
3287 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3288 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
3289 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3290 f.debug_tuple("Iter")
3291 .field(&self.as_slice())
3296 #[stable(feature = "rust1", since = "1.0.0")]
3297 unsafe impl<T: Sync> Sync for Iter<'_, T> {}
3298 #[stable(feature = "rust1", since = "1.0.0")]
3299 unsafe impl<T: Sync> Send for Iter<'_, T> {}
3301 impl<'a, T> Iter<'a, T> {
3302 /// Views the underlying data as a subslice of the original data.
3304 /// This has the same lifetime as the original slice, and so the
3305 /// iterator can continue to be used while this exists.
3312 /// // First, we declare a type which has the `iter` method to get the `Iter`
3313 /// // struct (&[usize here]):
3314 /// let slice = &[1, 2, 3];
3316 /// // Then, we get the iterator:
3317 /// let mut iter = slice.iter();
3318 /// // So if we print what `as_slice` method returns here, we have "[1, 2, 3]":
3319 /// println!("{:?}", iter.as_slice());
3321 /// // Next, we move to the second element of the slice:
3323 /// // Now `as_slice` returns "[2, 3]":
3324 /// println!("{:?}", iter.as_slice());
3326 #[stable(feature = "iter_to_slice", since = "1.4.0")]
3327 pub fn as_slice(&self) -> &'a [T] {
3332 iterator!{struct Iter -> *const T, &'a T, const, {/* no mut */}, {
3333 fn is_sorted_by<F>(self, mut compare: F) -> bool
3336 F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>,
3338 self.as_slice().windows(2).all(|w| {
3339 compare(&&w[0], &&w[1]).map(|o| o != Ordering::Greater).unwrap_or(false)
3344 #[stable(feature = "rust1", since = "1.0.0")]
3345 impl<T> Clone for Iter<'_, T> {
3346 fn clone(&self) -> Self { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } }
3349 #[stable(feature = "slice_iter_as_ref", since = "1.13.0")]
3350 impl<T> AsRef<[T]> for Iter<'_, T> {
3351 fn as_ref(&self) -> &[T] {
3356 /// Mutable slice iterator.
3358 /// This struct is created by the [`iter_mut`] method on [slices].
3365 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
3366 /// // struct (&[usize here]):
3367 /// let mut slice = &mut [1, 2, 3];
3369 /// // Then, we iterate over it and increment each element value:
3370 /// for element in slice.iter_mut() {
3374 /// // We now have "[2, 3, 4]":
3375 /// println!("{:?}", slice);
3378 /// [`iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
3379 /// [slices]: ../../std/primitive.slice.html
3380 #[stable(feature = "rust1", since = "1.0.0")]
3381 pub struct IterMut<'a, T: 'a> {
3383 end: *mut T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that
3384 // ptr == end is a quick test for the Iterator being empty, that works
3385 // for both ZST and non-ZST.
3386 _marker: marker::PhantomData<&'a mut T>,
3389 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3390 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
3391 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3392 f.debug_tuple("IterMut")
3393 .field(&self.make_slice())
3398 #[stable(feature = "rust1", since = "1.0.0")]
3399 unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
3400 #[stable(feature = "rust1", since = "1.0.0")]
3401 unsafe impl<T: Send> Send for IterMut<'_, T> {}
3403 impl<'a, T> IterMut<'a, T> {
3404 /// Views the underlying data as a subslice of the original data.
3406 /// To avoid creating `&mut` references that alias, this is forced
3407 /// to consume the iterator.
3414 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
3415 /// // struct (&[usize here]):
3416 /// let mut slice = &mut [1, 2, 3];
3419 /// // Then, we get the iterator:
3420 /// let mut iter = slice.iter_mut();
3421 /// // We move to next element:
3423 /// // So if we print what `into_slice` method returns here, we have "[2, 3]":
3424 /// println!("{:?}", iter.into_slice());
3427 /// // Now let's modify a value of the slice:
3429 /// // First we get back the iterator:
3430 /// let mut iter = slice.iter_mut();
3431 /// // We change the value of the first element of the slice returned by the `next` method:
3432 /// *iter.next().unwrap() += 1;
3434 /// // Now slice is "[2, 2, 3]":
3435 /// println!("{:?}", slice);
3437 #[stable(feature = "iter_to_slice", since = "1.4.0")]
3438 pub fn into_slice(self) -> &'a mut [T] {
3439 unsafe { from_raw_parts_mut(self.ptr, len!(self)) }
3442 /// Views the underlying data as a subslice of the original data.
3444 /// To avoid creating `&mut [T]` references that alias, the returned slice
3445 /// borrows its lifetime from the iterator the method is applied on.
3452 /// # #![feature(slice_iter_mut_as_slice)]
3453 /// let mut slice: &mut [usize] = &mut [1, 2, 3];
3455 /// // First, we get the iterator:
3456 /// let mut iter = slice.iter_mut();
3457 /// // So if we check what the `as_slice` method returns here, we have "[1, 2, 3]":
3458 /// assert_eq!(iter.as_slice(), &[1, 2, 3]);
3460 /// // Next, we move to the second element of the slice:
3462 /// // Now `as_slice` returns "[2, 3]":
3463 /// assert_eq!(iter.as_slice(), &[2, 3]);
3465 #[unstable(feature = "slice_iter_mut_as_slice", reason = "recently added", issue = "58957")]
3466 pub fn as_slice(&self) -> &[T] {
3471 iterator!{struct IterMut -> *mut T, &'a mut T, mut, {mut}, {}}
3473 /// An internal abstraction over the splitting iterators, so that
3474 /// splitn, splitn_mut etc can be implemented once.
3476 trait SplitIter: DoubleEndedIterator {
3477 /// Marks the underlying iterator as complete, extracting the remaining
3478 /// portion of the slice.
3479 fn finish(&mut self) -> Option<Self::Item>;
3482 /// An iterator over subslices separated by elements that match a predicate
3485 /// This struct is created by the [`split`] method on [slices].
3487 /// [`split`]: ../../std/primitive.slice.html#method.split
3488 /// [slices]: ../../std/primitive.slice.html
3489 #[stable(feature = "rust1", since = "1.0.0")]
3490 pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool {
3496 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3497 impl<T: fmt::Debug, P> fmt::Debug for Split<'_, T, P> where P: FnMut(&T) -> bool {
3498 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3499 f.debug_struct("Split")
3500 .field("v", &self.v)
3501 .field("finished", &self.finished)
3506 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3507 #[stable(feature = "rust1", since = "1.0.0")]
3508 impl<T, P> Clone for Split<'_, T, P> where P: Clone + FnMut(&T) -> bool {
3509 fn clone(&self) -> Self {
3512 pred: self.pred.clone(),
3513 finished: self.finished,
3518 #[stable(feature = "rust1", since = "1.0.0")]
3519 impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
3520 type Item = &'a [T];
3523 fn next(&mut self) -> Option<&'a [T]> {
3524 if self.finished { return None; }
3526 match self.v.iter().position(|x| (self.pred)(x)) {
3527 None => self.finish(),
3529 let ret = Some(&self.v[..idx]);
3530 self.v = &self.v[idx + 1..];
3537 fn size_hint(&self) -> (usize, Option<usize>) {
3541 (1, Some(self.v.len() + 1))
3546 #[stable(feature = "rust1", since = "1.0.0")]
3547 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
3549 fn next_back(&mut self) -> Option<&'a [T]> {
3550 if self.finished { return None; }
3552 match self.v.iter().rposition(|x| (self.pred)(x)) {
3553 None => self.finish(),
3555 let ret = Some(&self.v[idx + 1..]);
3556 self.v = &self.v[..idx];
3563 impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool {
3565 fn finish(&mut self) -> Option<&'a [T]> {
3566 if self.finished { None } else { self.finished = true; Some(self.v) }
3570 #[stable(feature = "fused", since = "1.26.0")]
3571 impl<T, P> FusedIterator for Split<'_, T, P> where P: FnMut(&T) -> bool {}
3573 /// An iterator over the subslices of the vector which are separated
3574 /// by elements that match `pred`.
3576 /// This struct is created by the [`split_mut`] method on [slices].
3578 /// [`split_mut`]: ../../std/primitive.slice.html#method.split_mut
3579 /// [slices]: ../../std/primitive.slice.html
3580 #[stable(feature = "rust1", since = "1.0.0")]
3581 pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
3587 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3588 impl<T: fmt::Debug, P> fmt::Debug for SplitMut<'_, T, P> where P: FnMut(&T) -> bool {
3589 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3590 f.debug_struct("SplitMut")
3591 .field("v", &self.v)
3592 .field("finished", &self.finished)
3597 impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3599 fn finish(&mut self) -> Option<&'a mut [T]> {
3603 self.finished = true;
3604 Some(mem::replace(&mut self.v, &mut []))
3609 #[stable(feature = "rust1", since = "1.0.0")]
3610 impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3611 type Item = &'a mut [T];
3614 fn next(&mut self) -> Option<&'a mut [T]> {
3615 if self.finished { return None; }
3617 let idx_opt = { // work around borrowck limitations
3618 let pred = &mut self.pred;
3619 self.v.iter().position(|x| (*pred)(x))
3622 None => self.finish(),
3624 let tmp = mem::replace(&mut self.v, &mut []);
3625 let (head, tail) = tmp.split_at_mut(idx);
3626 self.v = &mut tail[1..];
3633 fn size_hint(&self) -> (usize, Option<usize>) {
3637 // if the predicate doesn't match anything, we yield one slice
3638 // if it matches every element, we yield len+1 empty slices.
3639 (1, Some(self.v.len() + 1))
3644 #[stable(feature = "rust1", since = "1.0.0")]
3645 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where
3646 P: FnMut(&T) -> bool,
3649 fn next_back(&mut self) -> Option<&'a mut [T]> {
3650 if self.finished { return None; }
3652 let idx_opt = { // work around borrowck limitations
3653 let pred = &mut self.pred;
3654 self.v.iter().rposition(|x| (*pred)(x))
3657 None => self.finish(),
3659 let tmp = mem::replace(&mut self.v, &mut []);
3660 let (head, tail) = tmp.split_at_mut(idx);
3662 Some(&mut tail[1..])
3668 #[stable(feature = "fused", since = "1.26.0")]
3669 impl<T, P> FusedIterator for SplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
3671 /// An iterator over subslices separated by elements that match a predicate
3672 /// function, starting from the end of the slice.
3674 /// This struct is created by the [`rsplit`] method on [slices].
3676 /// [`rsplit`]: ../../std/primitive.slice.html#method.rsplit
3677 /// [slices]: ../../std/primitive.slice.html
3678 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3679 #[derive(Clone)] // Is this correct, or does it incorrectly require `T: Clone`?
3680 pub struct RSplit<'a, T:'a, P> where P: FnMut(&T) -> bool {
3681 inner: Split<'a, T, P>
3684 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3685 impl<T: fmt::Debug, P> fmt::Debug for RSplit<'_, T, P> where P: FnMut(&T) -> bool {
3686 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3687 f.debug_struct("RSplit")
3688 .field("v", &self.inner.v)
3689 .field("finished", &self.inner.finished)
3694 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3695 impl<'a, T, P> Iterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3696 type Item = &'a [T];
3699 fn next(&mut self) -> Option<&'a [T]> {
3700 self.inner.next_back()
3704 fn size_hint(&self) -> (usize, Option<usize>) {
3705 self.inner.size_hint()
3709 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3710 impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3712 fn next_back(&mut self) -> Option<&'a [T]> {
3717 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3718 impl<'a, T, P> SplitIter for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3720 fn finish(&mut self) -> Option<&'a [T]> {
3725 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3726 impl<T, P> FusedIterator for RSplit<'_, T, P> where P: FnMut(&T) -> bool {}
3728 /// An iterator over the subslices of the vector which are separated
3729 /// by elements that match `pred`, starting from the end of the slice.
3731 /// This struct is created by the [`rsplit_mut`] method on [slices].
3733 /// [`rsplit_mut`]: ../../std/primitive.slice.html#method.rsplit_mut
3734 /// [slices]: ../../std/primitive.slice.html
3735 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3736 pub struct RSplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
3737 inner: SplitMut<'a, T, P>
3740 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3741 impl<T: fmt::Debug, P> fmt::Debug for RSplitMut<'_, T, P> where P: FnMut(&T) -> bool {
3742 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3743 f.debug_struct("RSplitMut")
3744 .field("v", &self.inner.v)
3745 .field("finished", &self.inner.finished)
3750 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3751 impl<'a, T, P> SplitIter for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3753 fn finish(&mut self) -> Option<&'a mut [T]> {
3758 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3759 impl<'a, T, P> Iterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3760 type Item = &'a mut [T];
3763 fn next(&mut self) -> Option<&'a mut [T]> {
3764 self.inner.next_back()
3768 fn size_hint(&self) -> (usize, Option<usize>) {
3769 self.inner.size_hint()
3773 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3774 impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P> where
3775 P: FnMut(&T) -> bool,
3778 fn next_back(&mut self) -> Option<&'a mut [T]> {
3783 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3784 impl<T, P> FusedIterator for RSplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
3786 /// An private iterator over subslices separated by elements that
3787 /// match a predicate function, splitting at most a fixed number of
3790 struct GenericSplitN<I> {
3795 impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> {
3799 fn next(&mut self) -> Option<T> {
3802 1 => { self.count -= 1; self.iter.finish() }
3803 _ => { self.count -= 1; self.iter.next() }
3808 fn size_hint(&self) -> (usize, Option<usize>) {
3809 let (lower, upper_opt) = self.iter.size_hint();
3810 (lower, upper_opt.map(|upper| cmp::min(self.count, upper)))
3814 /// An iterator over subslices separated by elements that match a predicate
3815 /// function, limited to a given number of splits.
3817 /// This struct is created by the [`splitn`] method on [slices].
3819 /// [`splitn`]: ../../std/primitive.slice.html#method.splitn
3820 /// [slices]: ../../std/primitive.slice.html
3821 #[stable(feature = "rust1", since = "1.0.0")]
3822 pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3823 inner: GenericSplitN<Split<'a, T, P>>
3826 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3827 impl<T: fmt::Debug, P> fmt::Debug for SplitN<'_, T, P> where P: FnMut(&T) -> bool {
3828 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3829 f.debug_struct("SplitN")
3830 .field("inner", &self.inner)
3835 /// An iterator over subslices separated by elements that match a
3836 /// predicate function, limited to a given number of splits, starting
3837 /// from the end of the slice.
3839 /// This struct is created by the [`rsplitn`] method on [slices].
3841 /// [`rsplitn`]: ../../std/primitive.slice.html#method.rsplitn
3842 /// [slices]: ../../std/primitive.slice.html
3843 #[stable(feature = "rust1", since = "1.0.0")]
3844 pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3845 inner: GenericSplitN<RSplit<'a, T, P>>
3848 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3849 impl<T: fmt::Debug, P> fmt::Debug for RSplitN<'_, T, P> where P: FnMut(&T) -> bool {
3850 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3851 f.debug_struct("RSplitN")
3852 .field("inner", &self.inner)
3857 /// An iterator over subslices separated by elements that match a predicate
3858 /// function, limited to a given number of splits.
3860 /// This struct is created by the [`splitn_mut`] method on [slices].
3862 /// [`splitn_mut`]: ../../std/primitive.slice.html#method.splitn_mut
3863 /// [slices]: ../../std/primitive.slice.html
3864 #[stable(feature = "rust1", since = "1.0.0")]
3865 pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3866 inner: GenericSplitN<SplitMut<'a, T, P>>
3869 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3870 impl<T: fmt::Debug, P> fmt::Debug for SplitNMut<'_, T, P> where P: FnMut(&T) -> bool {
3871 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3872 f.debug_struct("SplitNMut")
3873 .field("inner", &self.inner)
3878 /// An iterator over subslices separated by elements that match a
3879 /// predicate function, limited to a given number of splits, starting
3880 /// from the end of the slice.
3882 /// This struct is created by the [`rsplitn_mut`] method on [slices].
3884 /// [`rsplitn_mut`]: ../../std/primitive.slice.html#method.rsplitn_mut
3885 /// [slices]: ../../std/primitive.slice.html
3886 #[stable(feature = "rust1", since = "1.0.0")]
3887 pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3888 inner: GenericSplitN<RSplitMut<'a, T, P>>
3891 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3892 impl<T: fmt::Debug, P> fmt::Debug for RSplitNMut<'_, T, P> where P: FnMut(&T) -> bool {
3893 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3894 f.debug_struct("RSplitNMut")
3895 .field("inner", &self.inner)
3900 macro_rules! forward_iterator {
3901 ($name:ident: $elem:ident, $iter_of:ty) => {
3902 #[stable(feature = "rust1", since = "1.0.0")]
3903 impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where
3904 P: FnMut(&T) -> bool
3906 type Item = $iter_of;
3909 fn next(&mut self) -> Option<$iter_of> {
3914 fn size_hint(&self) -> (usize, Option<usize>) {
3915 self.inner.size_hint()
3919 #[stable(feature = "fused", since = "1.26.0")]
3920 impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P>
3921 where P: FnMut(&T) -> bool {}
3925 forward_iterator! { SplitN: T, &'a [T] }
3926 forward_iterator! { RSplitN: T, &'a [T] }
3927 forward_iterator! { SplitNMut: T, &'a mut [T] }
3928 forward_iterator! { RSplitNMut: T, &'a mut [T] }
3930 /// An iterator over overlapping subslices of length `size`.
3932 /// This struct is created by the [`windows`] method on [slices].
3934 /// [`windows`]: ../../std/primitive.slice.html#method.windows
3935 /// [slices]: ../../std/primitive.slice.html
3937 #[stable(feature = "rust1", since = "1.0.0")]
3938 pub struct Windows<'a, T:'a> {
3943 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3944 #[stable(feature = "rust1", since = "1.0.0")]
3945 impl<T> Clone for Windows<'_, T> {
3946 fn clone(&self) -> Self {
3954 #[stable(feature = "rust1", since = "1.0.0")]
3955 impl<'a, T> Iterator for Windows<'a, T> {
3956 type Item = &'a [T];
3959 fn next(&mut self) -> Option<&'a [T]> {
3960 if self.size > self.v.len() {
3963 let ret = Some(&self.v[..self.size]);
3964 self.v = &self.v[1..];
3970 fn size_hint(&self) -> (usize, Option<usize>) {
3971 if self.size > self.v.len() {
3974 let size = self.v.len() - self.size + 1;
3980 fn count(self) -> usize {
3985 fn nth(&mut self, n: usize) -> Option<Self::Item> {
3986 let (end, overflow) = self.size.overflowing_add(n);
3987 if end > self.v.len() || overflow {
3991 let nth = &self.v[n..end];
3992 self.v = &self.v[n+1..];
3998 fn last(self) -> Option<Self::Item> {
3999 if self.size > self.v.len() {
4002 let start = self.v.len() - self.size;
4003 Some(&self.v[start..])
4008 #[stable(feature = "rust1", since = "1.0.0")]
4009 impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
4011 fn next_back(&mut self) -> Option<&'a [T]> {
4012 if self.size > self.v.len() {
4015 let ret = Some(&self.v[self.v.len()-self.size..]);
4016 self.v = &self.v[..self.v.len()-1];
4022 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
4023 let (end, overflow) = self.v.len().overflowing_sub(n);
4024 if end < self.size || overflow {
4028 let ret = &self.v[end-self.size..end];
4029 self.v = &self.v[..end-1];
4035 #[stable(feature = "rust1", since = "1.0.0")]
4036 impl<T> ExactSizeIterator for Windows<'_, T> {}
4038 #[unstable(feature = "trusted_len", issue = "37572")]
4039 unsafe impl<T> TrustedLen for Windows<'_, T> {}
4041 #[stable(feature = "fused", since = "1.26.0")]
4042 impl<T> FusedIterator for Windows<'_, T> {}
4045 unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {
4046 unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
4047 from_raw_parts(self.v.as_ptr().add(i), self.size)
4049 fn may_have_side_effect() -> bool { false }
4052 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
4053 /// time), starting at the beginning of the slice.
4055 /// When the slice len is not evenly divided by the chunk size, the last slice
4056 /// of the iteration will be the remainder.
4058 /// This struct is created by the [`chunks`] method on [slices].
4060 /// [`chunks`]: ../../std/primitive.slice.html#method.chunks
4061 /// [slices]: ../../std/primitive.slice.html
4063 #[stable(feature = "rust1", since = "1.0.0")]
4064 pub struct Chunks<'a, T:'a> {
4069 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
4070 #[stable(feature = "rust1", since = "1.0.0")]
4071 impl<T> Clone for Chunks<'_, T> {
4072 fn clone(&self) -> Self {
4075 chunk_size: self.chunk_size,
4080 #[stable(feature = "rust1", since = "1.0.0")]
4081 impl<'a, T> Iterator for Chunks<'a, T> {
4082 type Item = &'a [T];
4085 fn next(&mut self) -> Option<&'a [T]> {
4086 if self.v.is_empty() {
4089 let chunksz = cmp::min(self.v.len(), self.chunk_size);
4090 let (fst, snd) = self.v.split_at(chunksz);
4097 fn size_hint(&self) -> (usize, Option<usize>) {
4098 if self.v.is_empty() {
4101 let n = self.v.len() / self.chunk_size;
4102 let rem = self.v.len() % self.chunk_size;
4103 let n = if rem > 0 { n+1 } else { n };
4109 fn count(self) -> usize {
4114 fn nth(&mut self, n: usize) -> Option<Self::Item> {
4115 let (start, overflow) = n.overflowing_mul(self.chunk_size);
4116 if start >= self.v.len() || overflow {
4120 let end = match start.checked_add(self.chunk_size) {
4121 Some(sum) => cmp::min(self.v.len(), sum),
4122 None => self.v.len(),
4124 let nth = &self.v[start..end];
4125 self.v = &self.v[end..];
4131 fn last(self) -> Option<Self::Item> {
4132 if self.v.is_empty() {
4135 let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
4136 Some(&self.v[start..])
4141 #[stable(feature = "rust1", since = "1.0.0")]
4142 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
4144 fn next_back(&mut self) -> Option<&'a [T]> {
4145 if self.v.is_empty() {
4148 let remainder = self.v.len() % self.chunk_size;
4149 let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
4150 let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
4157 #[stable(feature = "rust1", since = "1.0.0")]
4158 impl<T> ExactSizeIterator for Chunks<'_, T> {}
4160 #[unstable(feature = "trusted_len", issue = "37572")]
4161 unsafe impl<T> TrustedLen for Chunks<'_, T> {}
4163 #[stable(feature = "fused", since = "1.26.0")]
4164 impl<T> FusedIterator for Chunks<'_, T> {}
4167 unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {
4168 unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
4169 let start = i * self.chunk_size;
4170 let end = match start.checked_add(self.chunk_size) {
4171 None => self.v.len(),
4172 Some(end) => cmp::min(end, self.v.len()),
4174 from_raw_parts(self.v.as_ptr().add(start), end - start)
4176 fn may_have_side_effect() -> bool { false }
4179 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
4180 /// elements at a time), starting at the beginning of the slice.
4182 /// When the slice len is not evenly divided by the chunk size, the last slice
4183 /// of the iteration will be the remainder.
4185 /// This struct is created by the [`chunks_mut`] method on [slices].
4187 /// [`chunks_mut`]: ../../std/primitive.slice.html#method.chunks_mut
4188 /// [slices]: ../../std/primitive.slice.html
4190 #[stable(feature = "rust1", since = "1.0.0")]
4191 pub struct ChunksMut<'a, T:'a> {
4196 #[stable(feature = "rust1", since = "1.0.0")]
4197 impl<'a, T> Iterator for ChunksMut<'a, T> {
4198 type Item = &'a mut [T];
4201 fn next(&mut self) -> Option<&'a mut [T]> {
4202 if self.v.is_empty() {
4205 let sz = cmp::min(self.v.len(), self.chunk_size);
4206 let tmp = mem::replace(&mut self.v, &mut []);
4207 let (head, tail) = tmp.split_at_mut(sz);
4214 fn size_hint(&self) -> (usize, Option<usize>) {
4215 if self.v.is_empty() {
4218 let n = self.v.len() / self.chunk_size;
4219 let rem = self.v.len() % self.chunk_size;
4220 let n = if rem > 0 { n + 1 } else { n };
4226 fn count(self) -> usize {
4231 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
4232 let (start, overflow) = n.overflowing_mul(self.chunk_size);
4233 if start >= self.v.len() || overflow {
4237 let end = match start.checked_add(self.chunk_size) {
4238 Some(sum) => cmp::min(self.v.len(), sum),
4239 None => self.v.len(),
4241 let tmp = mem::replace(&mut self.v, &mut []);
4242 let (head, tail) = tmp.split_at_mut(end);
4243 let (_, nth) = head.split_at_mut(start);
4250 fn last(self) -> Option<Self::Item> {
4251 if self.v.is_empty() {
4254 let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
4255 Some(&mut self.v[start..])
4260 #[stable(feature = "rust1", since = "1.0.0")]
4261 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
4263 fn next_back(&mut self) -> Option<&'a mut [T]> {
4264 if self.v.is_empty() {
4267 let remainder = self.v.len() % self.chunk_size;
4268 let sz = if remainder != 0 { remainder } else { self.chunk_size };
4269 let tmp = mem::replace(&mut self.v, &mut []);
4270 let tmp_len = tmp.len();
4271 let (head, tail) = tmp.split_at_mut(tmp_len - sz);
4278 #[stable(feature = "rust1", since = "1.0.0")]
4279 impl<T> ExactSizeIterator for ChunksMut<'_, T> {}
4281 #[unstable(feature = "trusted_len", issue = "37572")]
4282 unsafe impl<T> TrustedLen for ChunksMut<'_, T> {}
4284 #[stable(feature = "fused", since = "1.26.0")]
4285 impl<T> FusedIterator for ChunksMut<'_, T> {}
4288 unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {
4289 unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
4290 let start = i * self.chunk_size;
4291 let end = match start.checked_add(self.chunk_size) {
4292 None => self.v.len(),
4293 Some(end) => cmp::min(end, self.v.len()),
4295 from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start)
4297 fn may_have_side_effect() -> bool { false }
4300 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
4301 /// time), starting at the beginning of the slice.
4303 /// When the slice len is not evenly divided by the chunk size, the last
4304 /// up to `chunk_size-1` elements will be omitted but can be retrieved from
4305 /// the [`remainder`] function from the iterator.
4307 /// This struct is created by the [`chunks_exact`] method on [slices].
4309 /// [`chunks_exact`]: ../../std/primitive.slice.html#method.chunks_exact
4310 /// [`remainder`]: ../../std/slice/struct.ChunksExact.html#method.remainder
4311 /// [slices]: ../../std/primitive.slice.html
4313 #[stable(feature = "chunks_exact", since = "1.31.0")]
4314 pub struct ChunksExact<'a, T:'a> {
4320 impl<'a, T> ChunksExact<'a, T> {
4321 /// Returns the remainder of the original slice that is not going to be
4322 /// returned by the iterator. The returned slice has at most `chunk_size-1`
4324 #[stable(feature = "chunks_exact", since = "1.31.0")]
4325 pub fn remainder(&self) -> &'a [T] {
4330 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
4331 #[stable(feature = "chunks_exact", since = "1.31.0")]
4332 impl<T> Clone for ChunksExact<'_, T> {
4333 fn clone(&self) -> Self {
4337 chunk_size: self.chunk_size,
4342 #[stable(feature = "chunks_exact", since = "1.31.0")]
4343 impl<'a, T> Iterator for ChunksExact<'a, T> {
4344 type Item = &'a [T];
4347 fn next(&mut self) -> Option<&'a [T]> {
4348 if self.v.len() < self.chunk_size {
4351 let (fst, snd) = self.v.split_at(self.chunk_size);
4358 fn size_hint(&self) -> (usize, Option<usize>) {
4359 let n = self.v.len() / self.chunk_size;
4364 fn count(self) -> usize {
4369 fn nth(&mut self, n: usize) -> Option<Self::Item> {
4370 let (start, overflow) = n.overflowing_mul(self.chunk_size);
4371 if start >= self.v.len() || overflow {
4375 let (_, snd) = self.v.split_at(start);
4382 fn last(mut self) -> Option<Self::Item> {
4387 #[stable(feature = "chunks_exact", since = "1.31.0")]
4388 impl<'a, T> DoubleEndedIterator for ChunksExact<'a, T> {
4390 fn next_back(&mut self) -> Option<&'a [T]> {
4391 if self.v.len() < self.chunk_size {
4394 let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
4401 #[stable(feature = "chunks_exact", since = "1.31.0")]
4402 impl<T> ExactSizeIterator for ChunksExact<'_, T> {
4403 fn is_empty(&self) -> bool {
4408 #[unstable(feature = "trusted_len", issue = "37572")]
4409 unsafe impl<T> TrustedLen for ChunksExact<'_, T> {}
4411 #[stable(feature = "chunks_exact", since = "1.31.0")]
4412 impl<T> FusedIterator for ChunksExact<'_, T> {}
4415 #[stable(feature = "chunks_exact", since = "1.31.0")]
4416 unsafe impl<'a, T> TrustedRandomAccess for ChunksExact<'a, T> {
4417 unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
4418 let start = i * self.chunk_size;
4419 from_raw_parts(self.v.as_ptr().add(start), self.chunk_size)
4421 fn may_have_side_effect() -> bool { false }
4424 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
4425 /// elements at a time), starting at the beginning of the slice.
4427 /// When the slice len is not evenly divided by the chunk size, the last up to
4428 /// `chunk_size-1` elements will be omitted but can be retrieved from the
4429 /// [`into_remainder`] function from the iterator.
4431 /// This struct is created by the [`chunks_exact_mut`] method on [slices].
4433 /// [`chunks_exact_mut`]: ../../std/primitive.slice.html#method.chunks_exact_mut
4434 /// [`into_remainder`]: ../../std/slice/struct.ChunksExactMut.html#method.into_remainder
4435 /// [slices]: ../../std/primitive.slice.html
4437 #[stable(feature = "chunks_exact", since = "1.31.0")]
4438 pub struct ChunksExactMut<'a, T:'a> {
4444 impl<'a, T> ChunksExactMut<'a, T> {
4445 /// Returns the remainder of the original slice that is not going to be
4446 /// returned by the iterator. The returned slice has at most `chunk_size-1`
4448 #[stable(feature = "chunks_exact", since = "1.31.0")]
4449 pub fn into_remainder(self) -> &'a mut [T] {
4454 #[stable(feature = "chunks_exact", since = "1.31.0")]
4455 impl<'a, T> Iterator for ChunksExactMut<'a, T> {
4456 type Item = &'a mut [T];
4459 fn next(&mut self) -> Option<&'a mut [T]> {
4460 if self.v.len() < self.chunk_size {
4463 let tmp = mem::replace(&mut self.v, &mut []);
4464 let (head, tail) = tmp.split_at_mut(self.chunk_size);
4471 fn size_hint(&self) -> (usize, Option<usize>) {
4472 let n = self.v.len() / self.chunk_size;
4477 fn count(self) -> usize {
4482 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
4483 let (start, overflow) = n.overflowing_mul(self.chunk_size);
4484 if start >= self.v.len() || overflow {
4488 let tmp = mem::replace(&mut self.v, &mut []);
4489 let (_, snd) = tmp.split_at_mut(start);
4496 fn last(mut self) -> Option<Self::Item> {
4501 #[stable(feature = "chunks_exact", since = "1.31.0")]
4502 impl<'a, T> DoubleEndedIterator for ChunksExactMut<'a, T> {
4504 fn next_back(&mut self) -> Option<&'a mut [T]> {
4505 if self.v.len() < self.chunk_size {
4508 let tmp = mem::replace(&mut self.v, &mut []);
4509 let tmp_len = tmp.len();
4510 let (head, tail) = tmp.split_at_mut(tmp_len - self.chunk_size);
4517 #[stable(feature = "chunks_exact", since = "1.31.0")]
4518 impl<T> ExactSizeIterator for ChunksExactMut<'_, T> {
4519 fn is_empty(&self) -> bool {
4524 #[unstable(feature = "trusted_len", issue = "37572")]
4525 unsafe impl<T> TrustedLen for ChunksExactMut<'_, T> {}
4527 #[stable(feature = "chunks_exact", since = "1.31.0")]
4528 impl<T> FusedIterator for ChunksExactMut<'_, T> {}
4531 #[stable(feature = "chunks_exact", since = "1.31.0")]
4532 unsafe impl<'a, T> TrustedRandomAccess for ChunksExactMut<'a, T> {
4533 unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
4534 let start = i * self.chunk_size;
4535 from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size)
4537 fn may_have_side_effect() -> bool { false }
4540 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
4541 /// time), starting at the end of the slice.
4543 /// When the slice len is not evenly divided by the chunk size, the last slice
4544 /// of the iteration will be the remainder.
4546 /// This struct is created by the [`rchunks`] method on [slices].
4548 /// [`rchunks`]: ../../std/primitive.slice.html#method.rchunks
4549 /// [slices]: ../../std/primitive.slice.html
4551 #[stable(feature = "rchunks", since = "1.31.0")]
4552 pub struct RChunks<'a, T:'a> {
4557 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
4558 #[stable(feature = "rchunks", since = "1.31.0")]
4559 impl<T> Clone for RChunks<'_, T> {
4560 fn clone(&self) -> Self {
4563 chunk_size: self.chunk_size,
4568 #[stable(feature = "rchunks", since = "1.31.0")]
4569 impl<'a, T> Iterator for RChunks<'a, T> {
4570 type Item = &'a [T];
4573 fn next(&mut self) -> Option<&'a [T]> {
4574 if self.v.is_empty() {
4577 let chunksz = cmp::min(self.v.len(), self.chunk_size);
4578 let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
4585 fn size_hint(&self) -> (usize, Option<usize>) {
4586 if self.v.is_empty() {
4589 let n = self.v.len() / self.chunk_size;
4590 let rem = self.v.len() % self.chunk_size;
4591 let n = if rem > 0 { n+1 } else { n };
4597 fn count(self) -> usize {
4602 fn nth(&mut self, n: usize) -> Option<Self::Item> {
4603 let (end, overflow) = n.overflowing_mul(self.chunk_size);
4604 if end >= self.v.len() || overflow {
4608 // Can't underflow because of the check above
4609 let end = self.v.len() - end;
4610 let start = match end.checked_sub(self.chunk_size) {
4614 let nth = &self.v[start..end];
4615 self.v = &self.v[0..start];
4621 fn last(self) -> Option<Self::Item> {
4622 if self.v.is_empty() {
4625 let rem = self.v.len() % self.chunk_size;
4626 let end = if rem == 0 { self.chunk_size } else { rem };
4627 Some(&self.v[0..end])
4632 #[stable(feature = "rchunks", since = "1.31.0")]
4633 impl<'a, T> DoubleEndedIterator for RChunks<'a, T> {
4635 fn next_back(&mut self) -> Option<&'a [T]> {
4636 if self.v.is_empty() {
4639 let remainder = self.v.len() % self.chunk_size;
4640 let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
4641 let (fst, snd) = self.v.split_at(chunksz);
4648 #[stable(feature = "rchunks", since = "1.31.0")]
4649 impl<T> ExactSizeIterator for RChunks<'_, T> {}
4651 #[unstable(feature = "trusted_len", issue = "37572")]
4652 unsafe impl<T> TrustedLen for RChunks<'_, T> {}
4654 #[stable(feature = "rchunks", since = "1.31.0")]
4655 impl<T> FusedIterator for RChunks<'_, T> {}
4658 #[stable(feature = "rchunks", since = "1.31.0")]
4659 unsafe impl<'a, T> TrustedRandomAccess for RChunks<'a, T> {
4660 unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
4661 let end = self.v.len() - i * self.chunk_size;
4662 let start = match end.checked_sub(self.chunk_size) {
4664 Some(start) => start,
4666 from_raw_parts(self.v.as_ptr().add(start), end - start)
4668 fn may_have_side_effect() -> bool { false }
4671 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
4672 /// elements at a time), starting at the end of the slice.
4674 /// When the slice len is not evenly divided by the chunk size, the last slice
4675 /// of the iteration will be the remainder.
4677 /// This struct is created by the [`rchunks_mut`] method on [slices].
4679 /// [`rchunks_mut`]: ../../std/primitive.slice.html#method.rchunks_mut
4680 /// [slices]: ../../std/primitive.slice.html
4682 #[stable(feature = "rchunks", since = "1.31.0")]
4683 pub struct RChunksMut<'a, T:'a> {
4688 #[stable(feature = "rchunks", since = "1.31.0")]
4689 impl<'a, T> Iterator for RChunksMut<'a, T> {
4690 type Item = &'a mut [T];
4693 fn next(&mut self) -> Option<&'a mut [T]> {
4694 if self.v.is_empty() {
4697 let sz = cmp::min(self.v.len(), self.chunk_size);
4698 let tmp = mem::replace(&mut self.v, &mut []);
4699 let tmp_len = tmp.len();
4700 let (head, tail) = tmp.split_at_mut(tmp_len - sz);
4707 fn size_hint(&self) -> (usize, Option<usize>) {
4708 if self.v.is_empty() {
4711 let n = self.v.len() / self.chunk_size;
4712 let rem = self.v.len() % self.chunk_size;
4713 let n = if rem > 0 { n + 1 } else { n };
4719 fn count(self) -> usize {
4724 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
4725 let (end, overflow) = n.overflowing_mul(self.chunk_size);
4726 if end >= self.v.len() || overflow {
4730 // Can't underflow because of the check above
4731 let end = self.v.len() - end;
4732 let start = match end.checked_sub(self.chunk_size) {
4736 let tmp = mem::replace(&mut self.v, &mut []);
4737 let (head, tail) = tmp.split_at_mut(start);
4738 let (nth, _) = tail.split_at_mut(end - start);
4745 fn last(self) -> Option<Self::Item> {
4746 if self.v.is_empty() {
4749 let rem = self.v.len() % self.chunk_size;
4750 let end = if rem == 0 { self.chunk_size } else { rem };
4751 Some(&mut self.v[0..end])
4756 #[stable(feature = "rchunks", since = "1.31.0")]
4757 impl<'a, T> DoubleEndedIterator for RChunksMut<'a, T> {
4759 fn next_back(&mut self) -> Option<&'a mut [T]> {
4760 if self.v.is_empty() {
4763 let remainder = self.v.len() % self.chunk_size;
4764 let sz = if remainder != 0 { remainder } else { self.chunk_size };
4765 let tmp = mem::replace(&mut self.v, &mut []);
4766 let (head, tail) = tmp.split_at_mut(sz);
4773 #[stable(feature = "rchunks", since = "1.31.0")]
4774 impl<T> ExactSizeIterator for RChunksMut<'_, T> {}
4776 #[unstable(feature = "trusted_len", issue = "37572")]
4777 unsafe impl<T> TrustedLen for RChunksMut<'_, T> {}
4779 #[stable(feature = "rchunks", since = "1.31.0")]
4780 impl<T> FusedIterator for RChunksMut<'_, T> {}
4783 #[stable(feature = "rchunks", since = "1.31.0")]
4784 unsafe impl<'a, T> TrustedRandomAccess for RChunksMut<'a, T> {
4785 unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
4786 let end = self.v.len() - i * self.chunk_size;
4787 let start = match end.checked_sub(self.chunk_size) {
4789 Some(start) => start,
4791 from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start)
4793 fn may_have_side_effect() -> bool { false }
4796 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
4797 /// time), starting at the end of the slice.
4799 /// When the slice len is not evenly divided by the chunk size, the last
4800 /// up to `chunk_size-1` elements will be omitted but can be retrieved from
4801 /// the [`remainder`] function from the iterator.
4803 /// This struct is created by the [`rchunks_exact`] method on [slices].
4805 /// [`rchunks_exact`]: ../../std/primitive.slice.html#method.rchunks_exact
4806 /// [`remainder`]: ../../std/slice/struct.ChunksExact.html#method.remainder
4807 /// [slices]: ../../std/primitive.slice.html
4809 #[stable(feature = "rchunks", since = "1.31.0")]
4810 pub struct RChunksExact<'a, T:'a> {
4816 impl<'a, T> RChunksExact<'a, T> {
4817 /// Returns the remainder of the original slice that is not going to be
4818 /// returned by the iterator. The returned slice has at most `chunk_size-1`
4820 #[stable(feature = "rchunks", since = "1.31.0")]
4821 pub fn remainder(&self) -> &'a [T] {
4826 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
4827 #[stable(feature = "rchunks", since = "1.31.0")]
4828 impl<'a, T> Clone for RChunksExact<'a, T> {
4829 fn clone(&self) -> RChunksExact<'a, T> {
4833 chunk_size: self.chunk_size,
4838 #[stable(feature = "rchunks", since = "1.31.0")]
4839 impl<'a, T> Iterator for RChunksExact<'a, T> {
4840 type Item = &'a [T];
4843 fn next(&mut self) -> Option<&'a [T]> {
4844 if self.v.len() < self.chunk_size {
4847 let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
4854 fn size_hint(&self) -> (usize, Option<usize>) {
4855 let n = self.v.len() / self.chunk_size;
4860 fn count(self) -> usize {
4865 fn nth(&mut self, n: usize) -> Option<Self::Item> {
4866 let (end, overflow) = n.overflowing_mul(self.chunk_size);
4867 if end >= self.v.len() || overflow {
4871 let (fst, _) = self.v.split_at(self.v.len() - end);
4878 fn last(mut self) -> Option<Self::Item> {
4883 #[stable(feature = "rchunks", since = "1.31.0")]
4884 impl<'a, T> DoubleEndedIterator for RChunksExact<'a, T> {
4886 fn next_back(&mut self) -> Option<&'a [T]> {
4887 if self.v.len() < self.chunk_size {
4890 let (fst, snd) = self.v.split_at(self.chunk_size);
4897 #[stable(feature = "rchunks", since = "1.31.0")]
4898 impl<'a, T> ExactSizeIterator for RChunksExact<'a, T> {
4899 fn is_empty(&self) -> bool {
4904 #[unstable(feature = "trusted_len", issue = "37572")]
4905 unsafe impl<T> TrustedLen for RChunksExact<'_, T> {}
4907 #[stable(feature = "rchunks", since = "1.31.0")]
4908 impl<T> FusedIterator for RChunksExact<'_, T> {}
4911 #[stable(feature = "rchunks", since = "1.31.0")]
4912 unsafe impl<'a, T> TrustedRandomAccess for RChunksExact<'a, T> {
4913 unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
4914 let end = self.v.len() - i * self.chunk_size;
4915 let start = end - self.chunk_size;
4916 from_raw_parts(self.v.as_ptr().add(start), self.chunk_size)
4918 fn may_have_side_effect() -> bool { false }
4921 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
4922 /// elements at a time), starting at the end of the slice.
4924 /// When the slice len is not evenly divided by the chunk size, the last up to
4925 /// `chunk_size-1` elements will be omitted but can be retrieved from the
4926 /// [`into_remainder`] function from the iterator.
4928 /// This struct is created by the [`rchunks_exact_mut`] method on [slices].
4930 /// [`rchunks_exact_mut`]: ../../std/primitive.slice.html#method.rchunks_exact_mut
4931 /// [`into_remainder`]: ../../std/slice/struct.ChunksExactMut.html#method.into_remainder
4932 /// [slices]: ../../std/primitive.slice.html
4934 #[stable(feature = "rchunks", since = "1.31.0")]
4935 pub struct RChunksExactMut<'a, T:'a> {
4941 impl<'a, T> RChunksExactMut<'a, T> {
4942 /// Returns the remainder of the original slice that is not going to be
4943 /// returned by the iterator. The returned slice has at most `chunk_size-1`
4945 #[stable(feature = "rchunks", since = "1.31.0")]
4946 pub fn into_remainder(self) -> &'a mut [T] {
4951 #[stable(feature = "rchunks", since = "1.31.0")]
4952 impl<'a, T> Iterator for RChunksExactMut<'a, T> {
4953 type Item = &'a mut [T];
4956 fn next(&mut self) -> Option<&'a mut [T]> {
4957 if self.v.len() < self.chunk_size {
4960 let tmp = mem::replace(&mut self.v, &mut []);
4961 let tmp_len = tmp.len();
4962 let (head, tail) = tmp.split_at_mut(tmp_len - self.chunk_size);
4969 fn size_hint(&self) -> (usize, Option<usize>) {
4970 let n = self.v.len() / self.chunk_size;
4975 fn count(self) -> usize {
4980 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
4981 let (end, overflow) = n.overflowing_mul(self.chunk_size);
4982 if end >= self.v.len() || overflow {
4986 let tmp = mem::replace(&mut self.v, &mut []);
4987 let tmp_len = tmp.len();
4988 let (fst, _) = tmp.split_at_mut(tmp_len - end);
4995 fn last(mut self) -> Option<Self::Item> {
5000 #[stable(feature = "rchunks", since = "1.31.0")]
5001 impl<'a, T> DoubleEndedIterator for RChunksExactMut<'a, T> {
5003 fn next_back(&mut self) -> Option<&'a mut [T]> {
5004 if self.v.len() < self.chunk_size {
5007 let tmp = mem::replace(&mut self.v, &mut []);
5008 let (head, tail) = tmp.split_at_mut(self.chunk_size);
5015 #[stable(feature = "rchunks", since = "1.31.0")]
5016 impl<T> ExactSizeIterator for RChunksExactMut<'_, T> {
5017 fn is_empty(&self) -> bool {
5022 #[unstable(feature = "trusted_len", issue = "37572")]
5023 unsafe impl<T> TrustedLen for RChunksExactMut<'_, T> {}
5025 #[stable(feature = "rchunks", since = "1.31.0")]
5026 impl<T> FusedIterator for RChunksExactMut<'_, T> {}
5029 #[stable(feature = "rchunks", since = "1.31.0")]
5030 unsafe impl<'a, T> TrustedRandomAccess for RChunksExactMut<'a, T> {
5031 unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
5032 let end = self.v.len() - i * self.chunk_size;
5033 let start = end - self.chunk_size;
5034 from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size)
5036 fn may_have_side_effect() -> bool { false }
5043 /// Forms a slice from a pointer and a length.
5045 /// The `len` argument is the number of **elements**, not the number of bytes.
5049 /// This function is unsafe as there is no guarantee that the given pointer is
5050 /// valid for `len` elements, nor whether the lifetime inferred is a suitable
5051 /// lifetime for the returned slice.
5053 /// `data` must be non-null and aligned, even for zero-length slices. One
5054 /// reason for this is that enum layout optimizations may rely on references
5055 /// (including slices of any length) being aligned and non-null to distinguish
5056 /// them from other data. You can obtain a pointer that is usable as `data`
5057 /// for zero-length slices using [`NonNull::dangling()`].
5059 /// The total size of the slice must be no larger than `isize::MAX` **bytes**
5060 /// in memory. See the safety documentation of [`pointer::offset`].
5064 /// The lifetime for the returned slice is inferred from its usage. To
5065 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
5066 /// source lifetime is safe in the context, such as by providing a helper
5067 /// function taking the lifetime of a host value for the slice, or by explicit
5075 /// // manifest a slice for a single element
5077 /// let ptr = &x as *const _;
5078 /// let slice = unsafe { slice::from_raw_parts(ptr, 1) };
5079 /// assert_eq!(slice[0], 42);
5082 /// [`NonNull::dangling()`]: ../../std/ptr/struct.NonNull.html#method.dangling
5083 /// [`pointer::offset`]: ../../std/primitive.pointer.html#method.offset
5085 #[stable(feature = "rust1", since = "1.0.0")]
5086 pub unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] {
5087 debug_assert!(data as usize % mem::align_of::<T>() == 0, "attempt to create unaligned slice");
5088 debug_assert!(mem::size_of::<T>().saturating_mul(len) <= isize::MAX as usize,
5089 "attempt to create slice covering half the address space");
5090 Repr { raw: FatPtr { data, len } }.rust
5093 /// Performs the same functionality as [`from_raw_parts`], except that a
5094 /// mutable slice is returned.
5096 /// This function is unsafe for the same reasons as [`from_raw_parts`], as well
5097 /// as not being able to provide a non-aliasing guarantee of the returned
5098 /// mutable slice. `data` must be non-null and aligned even for zero-length
5099 /// slices as with [`from_raw_parts`]. The total size of the slice must be no
5100 /// larger than `isize::MAX` **bytes** in memory.
5102 /// See the documentation of [`from_raw_parts`] for more details.
5104 /// [`from_raw_parts`]: ../../std/slice/fn.from_raw_parts.html
5106 #[stable(feature = "rust1", since = "1.0.0")]
5107 pub unsafe fn from_raw_parts_mut<'a, T>(data: *mut T, len: usize) -> &'a mut [T] {
5108 debug_assert!(data as usize % mem::align_of::<T>() == 0, "attempt to create unaligned slice");
5109 debug_assert!(mem::size_of::<T>().saturating_mul(len) <= isize::MAX as usize,
5110 "attempt to create slice covering half the address space");
5111 Repr { raw: FatPtr { data, len } }.rust_mut
5114 /// Converts a reference to T into a slice of length 1 (without copying).
5115 #[stable(feature = "from_ref", since = "1.28.0")]
5116 pub fn from_ref<T>(s: &T) -> &[T] {
5118 from_raw_parts(s, 1)
5122 /// Converts a reference to T into a slice of length 1 (without copying).
5123 #[stable(feature = "from_ref", since = "1.28.0")]
5124 pub fn from_mut<T>(s: &mut T) -> &mut [T] {
5126 from_raw_parts_mut(s, 1)
5130 // This function is public only because there is no other way to unit test heapsort.
5131 #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "0")]
5133 pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
5134 where F: FnMut(&T, &T) -> bool
5136 sort::heapsort(v, &mut is_less);
5140 // Comparison traits
5144 /// Calls implementation provided memcmp.
5146 /// Interprets the data as u8.
5148 /// Returns 0 for equal, < 0 for less than and > 0 for greater
5150 // FIXME(#32610): Return type should be c_int
5151 fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
5154 #[stable(feature = "rust1", since = "1.0.0")]
5155 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
5156 fn eq(&self, other: &[B]) -> bool {
5157 SlicePartialEq::equal(self, other)
5160 fn ne(&self, other: &[B]) -> bool {
5161 SlicePartialEq::not_equal(self, other)
5165 #[stable(feature = "rust1", since = "1.0.0")]
5166 impl<T: Eq> Eq for [T] {}
5168 /// Implements comparison of vectors lexicographically.
5169 #[stable(feature = "rust1", since = "1.0.0")]
5170 impl<T: Ord> Ord for [T] {
5171 fn cmp(&self, other: &[T]) -> Ordering {
5172 SliceOrd::compare(self, other)
5176 /// Implements comparison of vectors lexicographically.
5177 #[stable(feature = "rust1", since = "1.0.0")]
5178 impl<T: PartialOrd> PartialOrd for [T] {
5179 fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
5180 SlicePartialOrd::partial_compare(self, other)
5185 // intermediate trait for specialization of slice's PartialEq
5186 trait SlicePartialEq<B> {
5187 fn equal(&self, other: &[B]) -> bool;
5189 fn not_equal(&self, other: &[B]) -> bool { !self.equal(other) }
5192 // Generic slice equality
5193 impl<A, B> SlicePartialEq<B> for [A]
5194 where A: PartialEq<B>
5196 default fn equal(&self, other: &[B]) -> bool {
5197 if self.len() != other.len() {
5201 for i in 0..self.len() {
5202 if !self[i].eq(&other[i]) {
5211 // Use memcmp for bytewise equality when the types allow
5212 impl<A> SlicePartialEq<A> for [A]
5213 where A: PartialEq<A> + BytewiseEquality
5215 fn equal(&self, other: &[A]) -> bool {
5216 if self.len() != other.len() {
5219 if self.as_ptr() == other.as_ptr() {
5223 let size = mem::size_of_val(self);
5224 memcmp(self.as_ptr() as *const u8,
5225 other.as_ptr() as *const u8, size) == 0
5231 // intermediate trait for specialization of slice's PartialOrd
5232 trait SlicePartialOrd<B> {
5233 fn partial_compare(&self, other: &[B]) -> Option<Ordering>;
5236 impl<A> SlicePartialOrd<A> for [A]
5239 default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
5240 let l = cmp::min(self.len(), other.len());
5242 // Slice to the loop iteration range to enable bound check
5243 // elimination in the compiler
5244 let lhs = &self[..l];
5245 let rhs = &other[..l];
5248 match lhs[i].partial_cmp(&rhs[i]) {
5249 Some(Ordering::Equal) => (),
5250 non_eq => return non_eq,
5254 self.len().partial_cmp(&other.len())
5258 impl<A> SlicePartialOrd<A> for [A]
5261 default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
5262 Some(SliceOrd::compare(self, other))
5267 // intermediate trait for specialization of slice's Ord
5269 fn compare(&self, other: &[B]) -> Ordering;
5272 impl<A> SliceOrd<A> for [A]
5275 default fn compare(&self, other: &[A]) -> Ordering {
5276 let l = cmp::min(self.len(), other.len());
5278 // Slice to the loop iteration range to enable bound check
5279 // elimination in the compiler
5280 let lhs = &self[..l];
5281 let rhs = &other[..l];
5284 match lhs[i].cmp(&rhs[i]) {
5285 Ordering::Equal => (),
5286 non_eq => return non_eq,
5290 self.len().cmp(&other.len())
5294 // memcmp compares a sequence of unsigned bytes lexicographically.
5295 // this matches the order we want for [u8], but no others (not even [i8]).
5296 impl SliceOrd<u8> for [u8] {
5298 fn compare(&self, other: &[u8]) -> Ordering {
5299 let order = unsafe {
5300 memcmp(self.as_ptr(), other.as_ptr(),
5301 cmp::min(self.len(), other.len()))
5304 self.len().cmp(&other.len())
5305 } else if order < 0 {
5314 /// Trait implemented for types that can be compared for equality using
5315 /// their bytewise representation
5316 trait BytewiseEquality { }
5318 macro_rules! impl_marker_for {
5319 ($traitname:ident, $($ty:ty)*) => {
5321 impl $traitname for $ty { }
5326 impl_marker_for!(BytewiseEquality,
5327 u8 i8 u16 i16 u32 i32 u64 i64 usize isize char bool);
5330 unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {
5331 unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
5334 fn may_have_side_effect() -> bool { false }
5338 unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {
5339 unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
5340 &mut *self.ptr.add(i)
5342 fn may_have_side_effect() -> bool { false }
5345 trait SliceContains: Sized {
5346 fn slice_contains(&self, x: &[Self]) -> bool;
5349 impl<T> SliceContains for T where T: PartialEq {
5350 default fn slice_contains(&self, x: &[Self]) -> bool {
5351 x.iter().any(|y| *y == *self)
5355 impl SliceContains for u8 {
5356 fn slice_contains(&self, x: &[Self]) -> bool {
5357 memchr::memchr(*self, x).is_some()
5361 impl SliceContains for i8 {
5362 fn slice_contains(&self, x: &[Self]) -> bool {
5363 let byte = *self as u8;
5364 let bytes: &[u8] = unsafe { from_raw_parts(x.as_ptr() as *const u8, x.len()) };
5365 memchr::memchr(byte, bytes).is_some()