1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! A dynamically-sized view into a contiguous sequence, `[T]`.
13 //! Slices are a view into a block of memory represented as a pointer and a
18 //! let vec = vec![1, 2, 3];
19 //! let int_slice = &vec[..];
20 //! // coercing an array to a slice
21 //! let str_slice: &[&str] = &["one", "two", "three"];
24 //! Slices are either mutable or shared. The shared slice type is `&[T]`,
25 //! while the mutable slice type is `&mut [T]`, where `T` represents the element
26 //! type. For example, you can mutate the block of memory that a mutable slice
30 //! let x = &mut [1, 2, 3];
32 //! assert_eq!(x, &[1, 7, 3]);
35 //! Here are some of the things this module contains:
39 //! There are several structs that are useful for slices, such as `Iter`, which
40 //! represents iteration over a slice.
42 //! ## Trait Implementations
44 //! There are several implementations of common traits for slices. Some examples
48 //! * `Eq`, `Ord` - for slices whose element type are `Eq` or `Ord`.
49 //! * `Hash` - for slices whose element type is `Hash`
53 //! The slices implement `IntoIterator`. The iterator yields references to the
57 //! let numbers = &[0, 1, 2];
58 //! for n in numbers {
59 //! println!("{} is a number!", n);
63 //! The mutable slice yields mutable references to the elements:
66 //! let mut scores = [7, 8, 9];
67 //! for score in &mut scores[..] {
72 //! This iterator yields mutable references to the slice's elements, so while
73 //! the element type of the slice is `i32`, the element type of the iterator is
76 //! * `.iter()` and `.iter_mut()` are the explicit methods to return the default
78 //! * Further methods that return iterators are `.split()`, `.splitn()`,
79 //! `.chunks()`, `.windows()` and more.
81 //! *[See also the slice primitive type](../../std/primitive.slice.html).*
82 #![stable(feature = "rust1", since = "1.0.0")]
84 // Many of the usings in this module are only used in the test configuration.
85 // It's cleaner to just turn off the unused_imports warning than to fix them.
86 #![cfg_attr(test, allow(unused_imports, dead_code))]
88 use alloc::boxed::Box;
89 use core::cmp::Ordering::{self, Greater, Less};
91 use core::mem::size_of;
94 use core::slice as core_slice;
96 use borrow::{Borrow, BorrowMut, ToOwned};
99 #[stable(feature = "rust1", since = "1.0.0")]
100 pub use core::slice::{Chunks, Windows};
101 #[stable(feature = "rust1", since = "1.0.0")]
102 pub use core::slice::{Iter, IterMut};
103 #[stable(feature = "rust1", since = "1.0.0")]
104 pub use core::slice::{SplitMut, ChunksMut, Split};
105 #[stable(feature = "rust1", since = "1.0.0")]
106 pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut};
107 #[stable(feature = "rust1", since = "1.0.0")]
108 pub use core::slice::{from_raw_parts, from_raw_parts_mut};
110 ////////////////////////////////////////////////////////////////////////////////
111 // Basic slice extension methods
112 ////////////////////////////////////////////////////////////////////////////////
114 // HACK(japaric) needed for the implementation of `vec!` macro during testing
115 // NB see the hack module in this file for more details
117 pub use self::hack::into_vec;
119 // HACK(japaric) needed for the implementation of `Vec::clone` during testing
120 // NB see the hack module in this file for more details
122 pub use self::hack::to_vec;
124 // HACK(japaric): With cfg(test) `impl [T]` is not available, these three
125 // functions are actually methods that are in `impl [T]` but not in
126 // `core::slice::SliceExt` - we need to supply these functions for the
127 // `test_permutations` test
129 use alloc::boxed::Box;
133 use string::ToString;
136 pub fn into_vec<T>(mut b: Box<[T]>) -> Vec<T> {
138 let xs = Vec::from_raw_parts(b.as_mut_ptr(), b.len(), b.len());
145 pub fn to_vec<T>(s: &[T]) -> Vec<T>
148 let mut vector = Vec::with_capacity(s.len());
149 vector.extend_from_slice(s);
154 /// Allocating extension methods for slices.
158 /// Returns the number of elements in the slice.
163 /// let a = [1, 2, 3];
164 /// assert_eq!(a.len(), 3);
166 #[stable(feature = "rust1", since = "1.0.0")]
168 pub fn len(&self) -> usize {
169 core_slice::SliceExt::len(self)
172 /// Returns true if the slice has a length of 0
177 /// let a = [1, 2, 3];
178 /// assert!(!a.is_empty());
180 #[stable(feature = "rust1", since = "1.0.0")]
182 pub fn is_empty(&self) -> bool {
183 core_slice::SliceExt::is_empty(self)
186 /// Returns the first element of a slice, or `None` if it is empty.
191 /// let v = [10, 40, 30];
192 /// assert_eq!(Some(&10), v.first());
194 /// let w: &[i32] = &[];
195 /// assert_eq!(None, w.first());
197 #[stable(feature = "rust1", since = "1.0.0")]
199 pub fn first(&self) -> Option<&T> {
200 core_slice::SliceExt::first(self)
203 /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty
204 #[stable(feature = "rust1", since = "1.0.0")]
206 pub fn first_mut(&mut self) -> Option<&mut T> {
207 core_slice::SliceExt::first_mut(self)
210 /// Returns the first and all the rest of the elements of a slice.
211 #[stable(feature = "slice_splits", since = "1.5.0")]
213 pub fn split_first(&self) -> Option<(&T, &[T])> {
214 core_slice::SliceExt::split_first(self)
217 /// Returns the first and all the rest of the elements of a slice.
218 #[stable(feature = "slice_splits", since = "1.5.0")]
220 pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
221 core_slice::SliceExt::split_first_mut(self)
224 /// Returns the last and all the rest of the elements of a slice.
225 #[stable(feature = "slice_splits", since = "1.5.0")]
227 pub fn split_last(&self) -> Option<(&T, &[T])> {
228 core_slice::SliceExt::split_last(self)
232 /// Returns the last and all the rest of the elements of a slice.
233 #[stable(feature = "slice_splits", since = "1.5.0")]
235 pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
236 core_slice::SliceExt::split_last_mut(self)
239 /// Returns the last element of a slice, or `None` if it is empty.
244 /// let v = [10, 40, 30];
245 /// assert_eq!(Some(&30), v.last());
247 /// let w: &[i32] = &[];
248 /// assert_eq!(None, w.last());
250 #[stable(feature = "rust1", since = "1.0.0")]
252 pub fn last(&self) -> Option<&T> {
253 core_slice::SliceExt::last(self)
256 /// Returns a mutable pointer to the last item in the slice.
257 #[stable(feature = "rust1", since = "1.0.0")]
259 pub fn last_mut(&mut self) -> Option<&mut T> {
260 core_slice::SliceExt::last_mut(self)
263 /// Returns the element of a slice at the given index, or `None` if the
264 /// index is out of bounds.
269 /// let v = [10, 40, 30];
270 /// assert_eq!(Some(&40), v.get(1));
271 /// assert_eq!(None, v.get(3));
273 #[stable(feature = "rust1", since = "1.0.0")]
275 pub fn get(&self, index: usize) -> Option<&T> {
276 core_slice::SliceExt::get(self, index)
279 /// Returns a mutable reference to the element at the given index,
280 /// or `None` if the index is out of bounds
281 #[stable(feature = "rust1", since = "1.0.0")]
283 pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
284 core_slice::SliceExt::get_mut(self, index)
287 /// Returns a pointer to the element at the given index, without doing
289 #[stable(feature = "rust1", since = "1.0.0")]
291 pub unsafe fn get_unchecked(&self, index: usize) -> &T {
292 core_slice::SliceExt::get_unchecked(self, index)
295 /// Returns an unsafe mutable pointer to the element in index
296 #[stable(feature = "rust1", since = "1.0.0")]
298 pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
299 core_slice::SliceExt::get_unchecked_mut(self, index)
302 /// Returns an raw pointer to the slice's buffer
304 /// The caller must ensure that the slice outlives the pointer this
305 /// function returns, or else it will end up pointing to garbage.
307 /// Modifying the slice may cause its buffer to be reallocated, which
308 /// would also make any pointers to it invalid.
309 #[stable(feature = "rust1", since = "1.0.0")]
311 pub fn as_ptr(&self) -> *const T {
312 core_slice::SliceExt::as_ptr(self)
315 /// Returns an unsafe mutable pointer to the slice's buffer.
317 /// The caller must ensure that the slice outlives the pointer this
318 /// function returns, or else it will end up pointing to garbage.
320 /// Modifying the slice may cause its buffer to be reallocated, which
321 /// would also make any pointers to it invalid.
322 #[stable(feature = "rust1", since = "1.0.0")]
324 pub fn as_mut_ptr(&mut self) -> *mut T {
325 core_slice::SliceExt::as_mut_ptr(self)
328 /// Swaps two elements in a slice.
332 /// * a - The index of the first element
333 /// * b - The index of the second element
337 /// Panics if `a` or `b` are out of bounds.
342 /// let mut v = ["a", "b", "c", "d"];
344 /// assert!(v == ["a", "d", "c", "b"]);
346 #[stable(feature = "rust1", since = "1.0.0")]
348 pub fn swap(&mut self, a: usize, b: usize) {
349 core_slice::SliceExt::swap(self, a, b)
352 /// Reverse the order of elements in a slice, in place.
357 /// let mut v = [1, 2, 3];
359 /// assert!(v == [3, 2, 1]);
361 #[stable(feature = "rust1", since = "1.0.0")]
363 pub fn reverse(&mut self) {
364 core_slice::SliceExt::reverse(self)
367 /// Returns an iterator over the slice.
368 #[stable(feature = "rust1", since = "1.0.0")]
370 pub fn iter(&self) -> Iter<T> {
371 core_slice::SliceExt::iter(self)
374 /// Returns an iterator that allows modifying each value
375 #[stable(feature = "rust1", since = "1.0.0")]
377 pub fn iter_mut(&mut self) -> IterMut<T> {
378 core_slice::SliceExt::iter_mut(self)
381 /// Returns an iterator over all contiguous windows of length
382 /// `size`. The windows overlap. If the slice is shorter than
383 /// `size`, the iterator returns no values.
387 /// Panics if `size` is 0.
391 /// Print the adjacent pairs of a slice (i.e. `[1,2]`, `[2,3]`,
395 /// let v = &[1, 2, 3, 4];
396 /// for win in v.windows(2) {
397 /// println!("{:?}", win);
400 #[stable(feature = "rust1", since = "1.0.0")]
402 pub fn windows(&self, size: usize) -> Windows<T> {
403 core_slice::SliceExt::windows(self, size)
406 /// Returns an iterator over `size` elements of the slice at a
407 /// time. The chunks are slices and do not overlap. If `size` does not divide the
408 /// length of the slice, then the last chunk will not have length
413 /// Panics if `size` is 0.
417 /// Print the slice two elements at a time (i.e. `[1,2]`,
421 /// let v = &[1, 2, 3, 4, 5];
422 /// for win in v.chunks(2) {
423 /// println!("{:?}", win);
426 #[stable(feature = "rust1", since = "1.0.0")]
428 pub fn chunks(&self, size: usize) -> Chunks<T> {
429 core_slice::SliceExt::chunks(self, size)
432 /// Returns an iterator over `chunk_size` elements of the slice at a time.
433 /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
434 /// not divide the length of the slice, then the last chunk will not
435 /// have length `chunk_size`.
439 /// Panics if `chunk_size` is 0.
440 #[stable(feature = "rust1", since = "1.0.0")]
442 pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
443 core_slice::SliceExt::chunks_mut(self, chunk_size)
446 /// Divides one slice into two at an index.
448 /// The first will contain all indices from `[0, mid)` (excluding
449 /// the index `mid` itself) and the second will contain all
450 /// indices from `[mid, len)` (excluding the index `len` itself).
454 /// Panics if `mid > len`.
459 /// let v = [10, 40, 30, 20, 50];
460 /// let (v1, v2) = v.split_at(2);
461 /// assert_eq!([10, 40], v1);
462 /// assert_eq!([30, 20, 50], v2);
464 #[stable(feature = "rust1", since = "1.0.0")]
466 pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
467 core_slice::SliceExt::split_at(self, mid)
470 /// Divides one `&mut` into two at an index.
472 /// The first will contain all indices from `[0, mid)` (excluding
473 /// the index `mid` itself) and the second will contain all
474 /// indices from `[mid, len)` (excluding the index `len` itself).
478 /// Panics if `mid > len`.
483 /// let mut v = [1, 2, 3, 4, 5, 6];
485 /// // scoped to restrict the lifetime of the borrows
487 /// let (left, right) = v.split_at_mut(0);
488 /// assert!(left == []);
489 /// assert!(right == [1, 2, 3, 4, 5, 6]);
493 /// let (left, right) = v.split_at_mut(2);
494 /// assert!(left == [1, 2]);
495 /// assert!(right == [3, 4, 5, 6]);
499 /// let (left, right) = v.split_at_mut(6);
500 /// assert!(left == [1, 2, 3, 4, 5, 6]);
501 /// assert!(right == []);
504 #[stable(feature = "rust1", since = "1.0.0")]
506 pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
507 core_slice::SliceExt::split_at_mut(self, mid)
510 /// Returns an iterator over subslices separated by elements that match
511 /// `pred`. The matched element is not contained in the subslices.
515 /// Print the slice split by numbers divisible by 3 (i.e. `[10, 40]`,
519 /// let v = [10, 40, 30, 20, 60, 50];
520 /// for group in v.split(|num| *num % 3 == 0) {
521 /// println!("{:?}", group);
524 #[stable(feature = "rust1", since = "1.0.0")]
526 pub fn split<F>(&self, pred: F) -> Split<T, F>
527 where F: FnMut(&T) -> bool
529 core_slice::SliceExt::split(self, pred)
532 /// Returns an iterator over mutable subslices separated by elements that
533 /// match `pred`. The matched element is not contained in the subslices.
534 #[stable(feature = "rust1", since = "1.0.0")]
536 pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
537 where F: FnMut(&T) -> bool
539 core_slice::SliceExt::split_mut(self, pred)
542 /// Returns an iterator over subslices separated by elements that match
543 /// `pred`, limited to returning at most `n` items. The matched element is
544 /// not contained in the subslices.
546 /// The last element returned, if any, will contain the remainder of the
551 /// Print the slice split once by numbers divisible by 3 (i.e. `[10, 40]`,
555 /// let v = [10, 40, 30, 20, 60, 50];
556 /// for group in v.splitn(2, |num| *num % 3 == 0) {
557 /// println!("{:?}", group);
560 #[stable(feature = "rust1", since = "1.0.0")]
562 pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<T, F>
563 where F: FnMut(&T) -> bool
565 core_slice::SliceExt::splitn(self, n, pred)
568 /// Returns an iterator over subslices separated by elements that match
569 /// `pred`, limited to returning at most `n` items. The matched element is
570 /// not contained in the subslices.
572 /// The last element returned, if any, will contain the remainder of the
574 #[stable(feature = "rust1", since = "1.0.0")]
576 pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<T, F>
577 where F: FnMut(&T) -> bool
579 core_slice::SliceExt::splitn_mut(self, n, pred)
582 /// Returns an iterator over subslices separated by elements that match
583 /// `pred` limited to returning at most `n` items. This starts at the end of
584 /// the slice and works backwards. The matched element is not contained in
587 /// The last element returned, if any, will contain the remainder of the
592 /// Print the slice split once, starting from the end, by numbers divisible
593 /// by 3 (i.e. `[50]`, `[10, 40, 30, 20]`):
596 /// let v = [10, 40, 30, 20, 60, 50];
597 /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
598 /// println!("{:?}", group);
601 #[stable(feature = "rust1", since = "1.0.0")]
603 pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<T, F>
604 where F: FnMut(&T) -> bool
606 core_slice::SliceExt::rsplitn(self, n, pred)
609 /// Returns an iterator over subslices separated by elements that match
610 /// `pred` limited to returning at most `n` items. This starts at the end of
611 /// the slice and works backwards. The matched element is not contained in
614 /// The last element returned, if any, will contain the remainder of the
616 #[stable(feature = "rust1", since = "1.0.0")]
618 pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<T, F>
619 where F: FnMut(&T) -> bool
621 core_slice::SliceExt::rsplitn_mut(self, n, pred)
624 /// Returns true if the slice contains an element with the given value.
629 /// let v = [10, 40, 30];
630 /// assert!(v.contains(&30));
631 /// assert!(!v.contains(&50));
633 #[stable(feature = "rust1", since = "1.0.0")]
634 pub fn contains(&self, x: &T) -> bool
637 core_slice::SliceExt::contains(self, x)
640 /// Returns true if `needle` is a prefix of the slice.
645 /// let v = [10, 40, 30];
646 /// assert!(v.starts_with(&[10]));
647 /// assert!(v.starts_with(&[10, 40]));
648 /// assert!(!v.starts_with(&[50]));
649 /// assert!(!v.starts_with(&[10, 50]));
651 #[stable(feature = "rust1", since = "1.0.0")]
652 pub fn starts_with(&self, needle: &[T]) -> bool
655 core_slice::SliceExt::starts_with(self, needle)
658 /// Returns true if `needle` is a suffix of the slice.
663 /// let v = [10, 40, 30];
664 /// assert!(v.ends_with(&[30]));
665 /// assert!(v.ends_with(&[40, 30]));
666 /// assert!(!v.ends_with(&[50]));
667 /// assert!(!v.ends_with(&[50, 30]));
669 #[stable(feature = "rust1", since = "1.0.0")]
670 pub fn ends_with(&self, needle: &[T]) -> bool
673 core_slice::SliceExt::ends_with(self, needle)
676 /// Binary search a sorted slice for a given element.
678 /// If the value is found then `Ok` is returned, containing the
679 /// index of the matching element; if the value is not found then
680 /// `Err` is returned, containing the index where a matching
681 /// element could be inserted while maintaining sorted order.
685 /// Looks up a series of four elements. The first is found, with a
686 /// uniquely determined position; the second and third are not
687 /// found; the fourth could match any position in `[1,4]`.
690 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
692 /// assert_eq!(s.binary_search(&13), Ok(9));
693 /// assert_eq!(s.binary_search(&4), Err(7));
694 /// assert_eq!(s.binary_search(&100), Err(13));
695 /// let r = s.binary_search(&1);
696 /// assert!(match r { Ok(1...4) => true, _ => false, });
698 #[stable(feature = "rust1", since = "1.0.0")]
699 pub fn binary_search(&self, x: &T) -> Result<usize, usize>
702 core_slice::SliceExt::binary_search(self, x)
705 /// Binary search a sorted slice with a comparator function.
707 /// The comparator function should implement an order consistent
708 /// with the sort order of the underlying slice, returning an
709 /// order code that indicates whether its argument is `Less`,
710 /// `Equal` or `Greater` the desired target.
712 /// If a matching value is found then returns `Ok`, containing
713 /// the index for the matched element; if no match is found then
714 /// `Err` is returned, containing the index where a matching
715 /// element could be inserted while maintaining sorted order.
719 /// Looks up a series of four elements. The first is found, with a
720 /// uniquely determined position; the second and third are not
721 /// found; the fourth could match any position in `[1,4]`.
724 /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
727 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
729 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
731 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
733 /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
734 /// assert!(match r { Ok(1...4) => true, _ => false, });
736 #[stable(feature = "rust1", since = "1.0.0")]
738 pub fn binary_search_by<F>(&self, f: F) -> Result<usize, usize>
739 where F: FnMut(&T) -> Ordering
741 core_slice::SliceExt::binary_search_by(self, f)
744 /// Sorts the slice, in place.
746 /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
748 /// This is a stable sort.
753 /// let mut v = [-5, 4, 1, -3, 2];
756 /// assert!(v == [-5, -3, 1, 2, 4]);
758 #[stable(feature = "rust1", since = "1.0.0")]
760 pub fn sort(&mut self)
763 self.sort_by(|a, b| a.cmp(b))
766 /// Sorts the slice, in place, using `key` to extract a key by which to
767 /// order the sort by.
769 /// This sort is `O(n log n)` worst-case and stable, but allocates
770 /// approximately `2 * n`, where `n` is the length of `self`.
772 /// This is a stable sort.
777 /// let mut v = [-5i32, 4, 1, -3, 2];
779 /// v.sort_by_key(|k| k.abs());
780 /// assert!(v == [1, 2, -3, 4, -5]);
782 #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
784 pub fn sort_by_key<B, F>(&mut self, mut f: F)
785 where F: FnMut(&T) -> B, B: Ord
787 self.sort_by(|a, b| f(a).cmp(&f(b)))
790 /// Sorts the slice, in place, using `compare` to compare
793 /// This sort is `O(n log n)` worst-case and stable, but allocates
794 /// approximately `2 * n`, where `n` is the length of `self`.
799 /// let mut v = [5, 4, 1, 3, 2];
800 /// v.sort_by(|a, b| a.cmp(b));
801 /// assert!(v == [1, 2, 3, 4, 5]);
803 /// // reverse sorting
804 /// v.sort_by(|a, b| b.cmp(a));
805 /// assert!(v == [5, 4, 3, 2, 1]);
807 #[stable(feature = "rust1", since = "1.0.0")]
809 pub fn sort_by<F>(&mut self, compare: F)
810 where F: FnMut(&T, &T) -> Ordering
812 merge_sort(self, compare)
815 /// Copies the elements from `src` into `self`.
817 /// The length of this slice must be the same as the slice passed in.
821 /// This function will panic if the two slices have different lengths.
826 /// let mut dst = [0, 0, 0];
827 /// let src = [1, 2, 3];
829 /// dst.clone_from_slice(&src);
830 /// assert!(dst == [1, 2, 3]);
832 #[stable(feature = "clone_from_slice", since = "1.7.0")]
833 pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
834 core_slice::SliceExt::clone_from_slice(self, src)
837 /// Copies all elements from `src` into `self`, using a memcpy.
839 /// The length of `src` must be the same as `self`.
843 /// This function will panic if the two slices have different lengths.
848 /// #![feature(copy_from_slice)]
849 /// let mut dst = [0, 0, 0];
850 /// let src = [1, 2, 3];
852 /// dst.copy_from_slice(&src);
853 /// assert_eq!(src, dst);
855 #[unstable(feature = "copy_from_slice", issue = "31755")]
856 pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
857 core_slice::SliceExt::copy_from_slice(self, src)
861 /// Copies `self` into a new `Vec`.
862 #[stable(feature = "rust1", since = "1.0.0")]
864 pub fn to_vec(&self) -> Vec<T>
867 // NB see hack module in this file
871 /// Converts `self` into a vector without clones or allocation.
872 #[stable(feature = "rust1", since = "1.0.0")]
874 pub fn into_vec(self: Box<Self>) -> Vec<T> {
875 // NB see hack module in this file
880 ////////////////////////////////////////////////////////////////////////////////
881 // Extension traits for slices over specific kinds of data
882 ////////////////////////////////////////////////////////////////////////////////
883 #[unstable(feature = "slice_concat_ext",
884 reason = "trait should not have to exist",
886 /// An extension trait for concatenating slices
887 pub trait SliceConcatExt<T: ?Sized> {
888 #[unstable(feature = "slice_concat_ext",
889 reason = "trait should not have to exist",
891 /// The resulting type after concatenation
894 /// Flattens a slice of `T` into a single value `Self::Output`.
899 /// assert_eq!(["hello", "world"].concat(), "helloworld");
901 #[stable(feature = "rust1", since = "1.0.0")]
902 fn concat(&self) -> Self::Output;
904 /// Flattens a slice of `T` into a single value `Self::Output`, placing a
905 /// given separator between each.
910 /// assert_eq!(["hello", "world"].join(" "), "hello world");
912 #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
913 fn join(&self, sep: &T) -> Self::Output;
915 #[stable(feature = "rust1", since = "1.0.0")]
916 #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
917 fn connect(&self, sep: &T) -> Self::Output;
920 #[unstable(feature = "slice_concat_ext",
921 reason = "trait should not have to exist",
923 impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] {
924 type Output = Vec<T>;
926 fn concat(&self) -> Vec<T> {
927 let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
928 let mut result = Vec::with_capacity(size);
930 result.extend_from_slice(v.borrow())
935 fn join(&self, sep: &T) -> Vec<T> {
936 let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
937 let mut result = Vec::with_capacity(size + self.len());
938 let mut first = true;
943 result.push(sep.clone())
945 result.extend_from_slice(v.borrow())
950 fn connect(&self, sep: &T) -> Vec<T> {
955 ////////////////////////////////////////////////////////////////////////////////
956 // Standard trait implementations for slices
957 ////////////////////////////////////////////////////////////////////////////////
959 #[stable(feature = "rust1", since = "1.0.0")]
960 impl<T> Borrow<[T]> for Vec<T> {
961 fn borrow(&self) -> &[T] {
966 #[stable(feature = "rust1", since = "1.0.0")]
967 impl<T> BorrowMut<[T]> for Vec<T> {
968 fn borrow_mut(&mut self) -> &mut [T] {
973 #[stable(feature = "rust1", since = "1.0.0")]
974 impl<T: Clone> ToOwned for [T] {
977 fn to_owned(&self) -> Vec<T> {
981 // HACK(japaric): with cfg(test) the inherent `[T]::to_vec`, which is required for this method
982 // definition, is not available. Since we don't require this method for testing purposes, I'll
984 // NB see the slice::hack module in slice.rs for more information
986 fn to_owned(&self) -> Vec<T> {
987 panic!("not available with cfg(test)")
991 ////////////////////////////////////////////////////////////////////////////////
993 ////////////////////////////////////////////////////////////////////////////////
995 fn insertion_sort<T, F>(v: &mut [T], mut compare: F)
996 where F: FnMut(&T, &T) -> Ordering
998 let len = v.len() as isize;
999 let buf_v = v.as_mut_ptr();
1003 // j satisfies: 0 <= j <= i;
1006 // `i` is in bounds.
1007 let read_ptr = buf_v.offset(i) as *const T;
1009 // find where to insert, we need to do strict <,
1010 // rather than <=, to maintain stability.
1012 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1013 while j > 0 && compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
1017 // shift everything to the right, to make space to
1018 // insert this value.
1020 // j + 1 could be `len` (for the last `i`), but in
1021 // that case, `i == j` so we don't copy. The
1022 // `.offset(j)` is always in bounds.
1025 let tmp = ptr::read(read_ptr);
1026 ptr::copy(&*buf_v.offset(j), buf_v.offset(j + 1), (i - j) as usize);
1027 ptr::copy_nonoverlapping(&tmp, buf_v.offset(j), 1);
1034 fn merge_sort<T, F>(v: &mut [T], mut compare: F)
1035 where F: FnMut(&T, &T) -> Ordering
1037 // warning: this wildly uses unsafe.
1038 const BASE_INSERTION: usize = 32;
1039 const LARGE_INSERTION: usize = 16;
1041 // FIXME #12092: smaller insertion runs seems to make sorting
1042 // vectors of large elements a little faster on some platforms,
1043 // but hasn't been tested/tuned extensively
1044 let insertion = if size_of::<T>() <= 16 {
1052 // short vectors get sorted in-place via insertion sort to avoid allocations
1053 if len <= insertion {
1054 insertion_sort(v, compare);
1058 // allocate some memory to use as scratch memory, we keep the
1059 // length 0 so we can keep shallow copies of the contents of `v`
1060 // without risking the dtors running on an object twice if
1061 // `compare` panics.
1062 let mut working_space = Vec::with_capacity(2 * len);
1063 // these both are buffers of length `len`.
1064 let mut buf_dat = working_space.as_mut_ptr();
1065 let mut buf_tmp = unsafe { buf_dat.offset(len as isize) };
1068 let buf_v = v.as_ptr();
1070 // step 1. sort short runs with insertion sort. This takes the
1071 // values from `v` and sorts them into `buf_dat`, leaving that
1072 // with sorted runs of length INSERTION.
1074 // We could hardcode the sorting comparisons here, and we could
1075 // manipulate/step the pointers themselves, rather than repeatedly
1077 for start in (0..len).step_by(insertion) {
1078 // start <= i < len;
1079 for i in start..cmp::min(start + insertion, len) {
1080 // j satisfies: start <= j <= i;
1081 let mut j = i as isize;
1083 // `i` is in bounds.
1084 let read_ptr = buf_v.offset(i as isize);
1086 // find where to insert, we need to do strict <,
1087 // rather than <=, to maintain stability.
1089 // start <= j - 1 < len, so .offset(j - 1) is in
1091 while j > start as isize && compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
1095 // shift everything to the right, to make space to
1096 // insert this value.
1098 // j + 1 could be `len` (for the last `i`), but in
1099 // that case, `i == j` so we don't copy. The
1100 // `.offset(j)` is always in bounds.
1101 ptr::copy(&*buf_dat.offset(j), buf_dat.offset(j + 1), i - j as usize);
1102 ptr::copy_nonoverlapping(read_ptr, buf_dat.offset(j), 1);
1107 // step 2. merge the sorted runs.
1108 let mut width = insertion;
1110 // merge the sorted runs of length `width` in `buf_dat` two at
1111 // a time, placing the result in `buf_tmp`.
1113 // 0 <= start <= len.
1114 for start in (0..len).step_by(2 * width) {
1115 // manipulate pointers directly for speed (rather than
1116 // using a `for` loop with `range` and `.offset` inside
1119 // the end of the first run & start of the
1120 // second. Offset of `len` is defined, since this is
1121 // precisely one byte past the end of the object.
1122 let right_start = buf_dat.offset(cmp::min(start + width, len) as isize);
1123 // end of the second. Similar reasoning to the above re safety.
1124 let right_end_idx = cmp::min(start + 2 * width, len);
1125 let right_end = buf_dat.offset(right_end_idx as isize);
1127 // the pointers to the elements under consideration
1128 // from the two runs.
1130 // both of these are in bounds.
1131 let mut left = buf_dat.offset(start as isize);
1132 let mut right = right_start;
1134 // where we're putting the results, it is a run of
1135 // length `2*width`, so we step it once for each step
1136 // of either `left` or `right`. `buf_tmp` has length
1137 // `len`, so these are in bounds.
1138 let mut out = buf_tmp.offset(start as isize);
1139 let out_end = buf_tmp.offset(right_end_idx as isize);
1141 // If left[last] <= right[0], they are already in order:
1142 // fast-forward the left side (the right side is handled
1144 // If `right` is not empty then left is not empty, and
1145 // the offsets are in bounds.
1146 if right != right_end && compare(&*right.offset(-1), &*right) != Greater {
1147 let elems = (right_start as usize - left as usize) / mem::size_of::<T>();
1148 ptr::copy_nonoverlapping(&*left, out, elems);
1149 out = out.offset(elems as isize);
1153 while out < out_end {
1154 // Either the left or the right run are exhausted,
1155 // so just copy the remainder from the other run
1156 // and move on; this gives a huge speed-up (order
1157 // of 25%) for mostly sorted vectors (the best
1159 if left == right_start {
1160 // the number remaining in this run.
1161 let elems = (right_end as usize - right as usize) / mem::size_of::<T>();
1162 ptr::copy_nonoverlapping(&*right, out, elems);
1164 } else if right == right_end {
1165 let elems = (right_start as usize - left as usize) / mem::size_of::<T>();
1166 ptr::copy_nonoverlapping(&*left, out, elems);
1170 // check which side is smaller, and that's the
1171 // next element for the new run.
1173 // `left < right_start` and `right < right_end`,
1174 // so these are valid.
1175 let to_copy = if compare(&*left, &*right) == Greater {
1180 ptr::copy_nonoverlapping(&*to_copy, out, 1);
1186 mem::swap(&mut buf_dat, &mut buf_tmp);
1191 // write the result to `v` in one go, so that there are never two copies
1192 // of the same object in `v`.
1194 ptr::copy_nonoverlapping(&*buf_dat, v.as_mut_ptr(), len);
1197 // increment the pointer, returning the old pointer.
1199 unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
1201 *ptr = ptr.offset(1);