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 /// let mut dst = [0, 0, 0];
849 /// let src = [1, 2, 3];
851 /// dst.copy_from_slice(&src);
852 /// assert_eq!(src, dst);
854 #[stable(feature = "copy_from_slice", since = "1.9.0")]
855 pub fn copy_from_slice(&mut self, src
: &[T
]) where T
: Copy
{
856 core_slice
::SliceExt
::copy_from_slice(self, src
)
860 /// Copies `self` into a new `Vec`.
861 #[stable(feature = "rust1", since = "1.0.0")]
863 pub fn to_vec(&self) -> Vec
<T
>
866 // NB see hack module in this file
870 /// Converts `self` into a vector without clones or allocation.
871 #[stable(feature = "rust1", since = "1.0.0")]
873 pub fn into_vec(self: Box
<Self>) -> Vec
<T
> {
874 // NB see hack module in this file
879 ////////////////////////////////////////////////////////////////////////////////
880 // Extension traits for slices over specific kinds of data
881 ////////////////////////////////////////////////////////////////////////////////
882 #[unstable(feature = "slice_concat_ext",
883 reason
= "trait should not have to exist",
885 /// An extension trait for concatenating slices
886 pub trait SliceConcatExt
<T
: ?Sized
> {
887 #[unstable(feature = "slice_concat_ext",
888 reason
= "trait should not have to exist",
890 /// The resulting type after concatenation
893 /// Flattens a slice of `T` into a single value `Self::Output`.
898 /// assert_eq!(["hello", "world"].concat(), "helloworld");
900 #[stable(feature = "rust1", since = "1.0.0")]
901 fn concat(&self) -> Self::Output
;
903 /// Flattens a slice of `T` into a single value `Self::Output`, placing a
904 /// given separator between each.
909 /// assert_eq!(["hello", "world"].join(" "), "hello world");
911 #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
912 fn join(&self, sep
: &T
) -> Self::Output
;
914 #[stable(feature = "rust1", since = "1.0.0")]
915 #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
916 fn connect(&self, sep
: &T
) -> Self::Output
;
919 #[unstable(feature = "slice_concat_ext",
920 reason
= "trait should not have to exist",
922 impl<T
: Clone
, V
: Borrow
<[T
]>> SliceConcatExt
<T
> for [V
] {
923 type Output
= Vec
<T
>;
925 fn concat(&self) -> Vec
<T
> {
926 let size
= self.iter().fold(0, |acc
, v
| acc
+ v
.borrow().len());
927 let mut result
= Vec
::with_capacity(size
);
929 result
.extend_from_slice(v
.borrow())
934 fn join(&self, sep
: &T
) -> Vec
<T
> {
935 let size
= self.iter().fold(0, |acc
, v
| acc
+ v
.borrow().len());
936 let mut result
= Vec
::with_capacity(size
+ self.len());
937 let mut first
= true;
942 result
.push(sep
.clone())
944 result
.extend_from_slice(v
.borrow())
949 fn connect(&self, sep
: &T
) -> Vec
<T
> {
954 ////////////////////////////////////////////////////////////////////////////////
955 // Standard trait implementations for slices
956 ////////////////////////////////////////////////////////////////////////////////
958 #[stable(feature = "rust1", since = "1.0.0")]
959 impl<T
> Borrow
<[T
]> for Vec
<T
> {
960 fn borrow(&self) -> &[T
] {
965 #[stable(feature = "rust1", since = "1.0.0")]
966 impl<T
> BorrowMut
<[T
]> for Vec
<T
> {
967 fn borrow_mut(&mut self) -> &mut [T
] {
972 #[stable(feature = "rust1", since = "1.0.0")]
973 impl<T
: Clone
> ToOwned
for [T
] {
976 fn to_owned(&self) -> Vec
<T
> {
980 // HACK(japaric): with cfg(test) the inherent `[T]::to_vec`, which is required for this method
981 // definition, is not available. Since we don't require this method for testing purposes, I'll
983 // NB see the slice::hack module in slice.rs for more information
985 fn to_owned(&self) -> Vec
<T
> {
986 panic
!("not available with cfg(test)")
990 ////////////////////////////////////////////////////////////////////////////////
992 ////////////////////////////////////////////////////////////////////////////////
994 fn insertion_sort
<T
, F
>(v
: &mut [T
], mut compare
: F
)
995 where F
: FnMut(&T
, &T
) -> Ordering
997 let len
= v
.len() as isize;
998 let buf_v
= v
.as_mut_ptr();
1002 // j satisfies: 0 <= j <= i;
1005 // `i` is in bounds.
1006 let read_ptr
= buf_v
.offset(i
) as *const T
;
1008 // find where to insert, we need to do strict <,
1009 // rather than <=, to maintain stability.
1011 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1012 while j
> 0 && compare(&*read_ptr
, &*buf_v
.offset(j
- 1)) == Less
{
1016 // shift everything to the right, to make space to
1017 // insert this value.
1019 // j + 1 could be `len` (for the last `i`), but in
1020 // that case, `i == j` so we don't copy. The
1021 // `.offset(j)` is always in bounds.
1024 let tmp
= ptr
::read(read_ptr
);
1025 ptr
::copy(&*buf_v
.offset(j
), buf_v
.offset(j
+ 1), (i
- j
) as usize);
1026 ptr
::copy_nonoverlapping(&tmp
, buf_v
.offset(j
), 1);
1033 fn merge_sort
<T
, F
>(v
: &mut [T
], mut compare
: F
)
1034 where F
: FnMut(&T
, &T
) -> Ordering
1036 // warning: this wildly uses unsafe.
1037 const BASE_INSERTION
: usize = 32;
1038 const LARGE_INSERTION
: usize = 16;
1040 // FIXME #12092: smaller insertion runs seems to make sorting
1041 // vectors of large elements a little faster on some platforms,
1042 // but hasn't been tested/tuned extensively
1043 let insertion
= if size_of
::<T
>() <= 16 {
1051 // short vectors get sorted in-place via insertion sort to avoid allocations
1052 if len
<= insertion
{
1053 insertion_sort(v
, compare
);
1057 // allocate some memory to use as scratch memory, we keep the
1058 // length 0 so we can keep shallow copies of the contents of `v`
1059 // without risking the dtors running on an object twice if
1060 // `compare` panics.
1061 let mut working_space
= Vec
::with_capacity(2 * len
);
1062 // these both are buffers of length `len`.
1063 let mut buf_dat
= working_space
.as_mut_ptr();
1064 let mut buf_tmp
= unsafe { buf_dat.offset(len as isize) }
;
1067 let buf_v
= v
.as_ptr();
1069 // step 1. sort short runs with insertion sort. This takes the
1070 // values from `v` and sorts them into `buf_dat`, leaving that
1071 // with sorted runs of length INSERTION.
1073 // We could hardcode the sorting comparisons here, and we could
1074 // manipulate/step the pointers themselves, rather than repeatedly
1076 for start
in (0..len
).step_by(insertion
) {
1077 // start <= i < len;
1078 for i
in start
..cmp
::min(start
+ insertion
, len
) {
1079 // j satisfies: start <= j <= i;
1080 let mut j
= i
as isize;
1082 // `i` is in bounds.
1083 let read_ptr
= buf_v
.offset(i
as isize);
1085 // find where to insert, we need to do strict <,
1086 // rather than <=, to maintain stability.
1088 // start <= j - 1 < len, so .offset(j - 1) is in
1090 while j
> start
as isize && compare(&*read_ptr
, &*buf_dat
.offset(j
- 1)) == Less
{
1094 // shift everything to the right, to make space to
1095 // insert this value.
1097 // j + 1 could be `len` (for the last `i`), but in
1098 // that case, `i == j` so we don't copy. The
1099 // `.offset(j)` is always in bounds.
1100 ptr
::copy(&*buf_dat
.offset(j
), buf_dat
.offset(j
+ 1), i
- j
as usize);
1101 ptr
::copy_nonoverlapping(read_ptr
, buf_dat
.offset(j
), 1);
1106 // step 2. merge the sorted runs.
1107 let mut width
= insertion
;
1109 // merge the sorted runs of length `width` in `buf_dat` two at
1110 // a time, placing the result in `buf_tmp`.
1112 // 0 <= start <= len.
1113 for start
in (0..len
).step_by(2 * width
) {
1114 // manipulate pointers directly for speed (rather than
1115 // using a `for` loop with `range` and `.offset` inside
1118 // the end of the first run & start of the
1119 // second. Offset of `len` is defined, since this is
1120 // precisely one byte past the end of the object.
1121 let right_start
= buf_dat
.offset(cmp
::min(start
+ width
, len
) as isize);
1122 // end of the second. Similar reasoning to the above re safety.
1123 let right_end_idx
= cmp
::min(start
+ 2 * width
, len
);
1124 let right_end
= buf_dat
.offset(right_end_idx
as isize);
1126 // the pointers to the elements under consideration
1127 // from the two runs.
1129 // both of these are in bounds.
1130 let mut left
= buf_dat
.offset(start
as isize);
1131 let mut right
= right_start
;
1133 // where we're putting the results, it is a run of
1134 // length `2*width`, so we step it once for each step
1135 // of either `left` or `right`. `buf_tmp` has length
1136 // `len`, so these are in bounds.
1137 let mut out
= buf_tmp
.offset(start
as isize);
1138 let out_end
= buf_tmp
.offset(right_end_idx
as isize);
1140 // If left[last] <= right[0], they are already in order:
1141 // fast-forward the left side (the right side is handled
1143 // If `right` is not empty then left is not empty, and
1144 // the offsets are in bounds.
1145 if right
!= right_end
&& compare(&*right
.offset(-1), &*right
) != Greater
{
1146 let elems
= (right_start
as usize - left
as usize) / mem
::size_of
::<T
>();
1147 ptr
::copy_nonoverlapping(&*left
, out
, elems
);
1148 out
= out
.offset(elems
as isize);
1152 while out
< out_end
{
1153 // Either the left or the right run are exhausted,
1154 // so just copy the remainder from the other run
1155 // and move on; this gives a huge speed-up (order
1156 // of 25%) for mostly sorted vectors (the best
1158 if left
== right_start
{
1159 // the number remaining in this run.
1160 let elems
= (right_end
as usize - right
as usize) / mem
::size_of
::<T
>();
1161 ptr
::copy_nonoverlapping(&*right
, out
, elems
);
1163 } else if right
== right_end
{
1164 let elems
= (right_start
as usize - left
as usize) / mem
::size_of
::<T
>();
1165 ptr
::copy_nonoverlapping(&*left
, out
, elems
);
1169 // check which side is smaller, and that's the
1170 // next element for the new run.
1172 // `left < right_start` and `right < right_end`,
1173 // so these are valid.
1174 let to_copy
= if compare(&*left
, &*right
) == Greater
{
1179 ptr
::copy_nonoverlapping(&*to_copy
, out
, 1);
1185 mem
::swap(&mut buf_dat
, &mut buf_tmp
);
1190 // write the result to `v` in one go, so that there are never two copies
1191 // of the same object in `v`.
1193 ptr
::copy_nonoverlapping(&*buf_dat
, v
.as_mut_ptr(), len
);
1196 // increment the pointer, returning the old pointer.
1198 unsafe fn step
<T
>(ptr
: &mut *mut T
) -> *mut T
{
1200 *ptr
= ptr
.offset(1);