1 // Copyright 2014 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 //! An owned, growable vector.
13 use cast::{forget, transmute};
15 use cmp::{Ord, Eq, Ordering, TotalEq, TotalOrd};
16 use container::{Container, Mutable};
19 use iter::{DoubleEndedIterator, FromIterator, Extendable, Iterator, range};
20 use libc::{free, c_void};
21 use mem::{size_of, move_val_init};
24 use num::{CheckedMul, CheckedAdd};
26 use option::{None, Option, Some};
29 use rt::global_heap::{malloc_raw, realloc_raw};
31 use slice::{ImmutableEqVector, ImmutableVector, Items, MutItems, MutableVector};
32 use slice::{MutableTotalOrdVector, OwnedVector, Vector};
34 /// An owned, growable vector.
39 /// # use std::vec::Vec;
40 /// let mut vec = Vec::new();
44 /// assert_eq!(vec.len(), 2);
45 /// assert_eq!(vec.get(0), &1);
47 /// assert_eq!(vec.pop(), Some(2));
48 /// assert_eq!(vec.len(), 1);
51 /// The `vec!` macro is provided to make initialization more convenient:
54 /// let mut vec = vec!(1, 2, 3);
56 /// assert_eq!(vec, vec!(1, 2, 3, 4));
58 #[unsafe_no_drop_flag]
66 /// Constructs a new, empty `Vec`.
68 /// The vector will not allocate until elements are pushed onto it.
73 /// # use std::vec::Vec;
74 /// let mut vec: Vec<int> = Vec::new();
77 pub fn new() -> Vec<T> {
78 Vec { len: 0, cap: 0, ptr: 0 as *mut T }
81 /// Constructs a new, empty `Vec` with the specified capacity.
83 /// The vector will be able to hold exactly `capacity` elements without
84 /// reallocating. If `capacity` is 0, the vector will not allocate.
89 /// # use std::vec::Vec;
90 /// let vec: Vec<int> = Vec::with_capacity(10);
92 pub fn with_capacity(capacity: uint) -> Vec<T> {
96 let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
97 let ptr = unsafe { malloc_raw(size) };
98 Vec { len: 0, cap: capacity, ptr: ptr as *mut T }
102 /// Creates and initializes a `Vec`.
104 /// Creates a `Vec` of size `length` and initializes the elements to the
105 /// value returned by the closure `op`.
110 /// # use std::vec::Vec;
111 /// let vec = Vec::from_fn(3, |idx| idx * 2);
112 /// assert_eq!(vec, vec!(0, 2, 4));
114 pub fn from_fn(length: uint, op: |uint| -> T) -> Vec<T> {
116 let mut xs = Vec::with_capacity(length);
117 while xs.len < length {
118 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), op(xs.len));
125 /// Create a `Vec<T>` directly from the raw constituents.
127 /// This is highly unsafe:
129 /// - if `ptr` is null, then `length` and `capacity` should be 0
130 /// - `ptr` must point to an allocation of size `capacity`
131 /// - there must be `length` valid instances of type `T` at the
132 /// beginning of that allocation
133 /// - `ptr` must be allocated by the default `Vec` allocator
134 pub unsafe fn from_raw_parts(length: uint, capacity: uint, ptr: *mut T) -> Vec<T> {
135 Vec { len: length, cap: capacity, ptr: ptr }
138 /// Consumes the `Vec`, partitioning it based on a predcate.
140 /// Partitions the `Vec` into two `Vec`s `(A,B)`, where all elements of `A`
141 /// satisfy `f` and all elements of `B` do not. The order of elements is
147 /// let vec = vec!(1, 2, 3, 4);
148 /// let (even, odd) = vec.partition(|&n| n % 2 == 0);
149 /// assert_eq!(even, vec!(2, 4));
150 /// assert_eq!(odd, vec!(1, 3));
153 pub fn partition(self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
154 let mut lefts = Vec::new();
155 let mut rights = Vec::new();
157 for elt in self.move_iter() {
169 impl<T: Clone> Vec<T> {
170 /// Iterates over the `second` vector, copying each element and appending it to
171 /// the `first`. Afterwards, the `first` is then returned for use again.
176 /// let vec = vec!(1, 2);
177 /// let vec = vec.append([3, 4]);
178 /// assert_eq!(vec, vec!(1, 2, 3, 4));
181 pub fn append(mut self, second: &[T]) -> Vec<T> {
182 self.push_all(second);
186 /// Constructs a `Vec` by cloning elements of a slice.
191 /// # use std::vec::Vec;
192 /// let slice = [1, 2, 3];
193 /// let vec = Vec::from_slice(slice);
195 pub fn from_slice(values: &[T]) -> Vec<T> {
196 values.iter().map(|x| x.clone()).collect()
199 /// Constructs a `Vec` with copies of a value.
201 /// Creates a `Vec` with `length` copies of `value`.
205 /// # use std::vec::Vec;
206 /// let vec = Vec::from_elem(3, "hi");
207 /// println!("{}", vec); // prints [hi, hi, hi]
209 pub fn from_elem(length: uint, value: T) -> Vec<T> {
211 let mut xs = Vec::with_capacity(length);
212 while xs.len < length {
213 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), value.clone());
220 /// Appends all elements in a slice to the `Vec`.
222 /// Iterates over the slice `other`, clones each element, and then appends
223 /// it to this `Vec`. The `other` vector is traversed in-order.
228 /// let mut vec = vec!(1);
229 /// vec.push_all([2, 3, 4]);
230 /// assert_eq!(vec, vec!(1, 2, 3, 4));
233 pub fn push_all(&mut self, other: &[T]) {
234 self.extend(other.iter().map(|e| e.clone()));
237 /// Grows the `Vec` in-place.
239 /// Adds `n` copies of `value` to the `Vec`.
244 /// let mut vec = vec!("hello");
245 /// vec.grow(2, & &"world");
246 /// assert_eq!(vec, vec!("hello", "world", "world"));
248 pub fn grow(&mut self, n: uint, value: &T) {
249 let new_len = self.len() + n;
250 self.reserve(new_len);
251 let mut i: uint = 0u;
254 self.push((*value).clone());
259 /// Sets the value of a vector element at a given index, growing the vector
262 /// Sets the element at position `index` to `value`. If `index` is past the
263 /// end of the vector, expands the vector by replicating `initval` to fill
264 /// the intervening space.
269 /// let mut vec = vec!("a", "b", "c");
270 /// vec.grow_set(1, & &"fill", "d");
271 /// vec.grow_set(4, & &"fill", "e");
272 /// assert_eq!(vec, vec!("a", "d", "c", "fill", "e"));
274 pub fn grow_set(&mut self, index: uint, initval: &T, value: T) {
277 self.grow(index - l + 1u, initval);
279 *self.get_mut(index) = value;
282 /// Partitions a vector based on a predcate.
284 /// Clones the elements of the vector, partitioning them into two `Vec`s
285 /// `(A,B)`, where all elements of `A` satisfy `f` and all elements of `B`
286 /// do not. The order of elements is preserved.
291 /// let vec = vec!(1, 2, 3, 4);
292 /// let (even, odd) = vec.partitioned(|&n| n % 2 == 0);
293 /// assert_eq!(even, vec!(2, 4));
294 /// assert_eq!(odd, vec!(1, 3));
296 pub fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
297 let mut lefts = Vec::new();
298 let mut rights = Vec::new();
300 for elt in self.iter() {
302 lefts.push(elt.clone());
304 rights.push(elt.clone());
312 impl<T:Clone> Clone for Vec<T> {
313 fn clone(&self) -> Vec<T> {
315 let mut vector = Vec::with_capacity(len);
316 // Unsafe code so this can be optimised to a memcpy (or something
317 // similarly fast) when T is Copy. LLVM is easily confused, so any
318 // extra operations during the loop can prevent this optimisation
320 let this_slice = self.as_slice();
321 while vector.len < len {
324 vector.as_mut_slice().unsafe_mut_ref(vector.len),
325 this_slice.unsafe_ref(vector.len).clone());
333 fn clone_from(&mut self, other: &Vec<T>) {
334 // drop anything in self that will not be overwritten
335 if self.len() > other.len() {
336 self.truncate(other.len())
339 // reuse the contained values' allocations/resources.
340 for (place, thing) in self.mut_iter().zip(other.iter()) {
341 place.clone_from(thing)
344 // self.len <= other.len due to the truncate above, so the
345 // slice here is always in-bounds.
346 let len = self.len();
347 self.extend(other.slice_from(len).iter().map(|x| x.clone()));
351 impl<T> FromIterator<T> for Vec<T> {
352 fn from_iter<I:Iterator<T>>(mut iterator: I) -> Vec<T> {
353 let (lower, _) = iterator.size_hint();
354 let mut vector = Vec::with_capacity(lower);
355 for element in iterator {
362 impl<T> Extendable<T> for Vec<T> {
363 fn extend<I: Iterator<T>>(&mut self, mut iterator: I) {
364 let (lower, _) = iterator.size_hint();
365 self.reserve_additional(lower);
366 for element in iterator {
372 impl<T: Eq> Eq for Vec<T> {
374 fn eq(&self, other: &Vec<T>) -> bool {
375 self.as_slice() == other.as_slice()
379 impl<T: Ord> Ord for Vec<T> {
381 fn lt(&self, other: &Vec<T>) -> bool {
382 self.as_slice() < other.as_slice()
386 impl<T: TotalEq> TotalEq for Vec<T> {}
388 impl<T: TotalOrd> TotalOrd for Vec<T> {
390 fn cmp(&self, other: &Vec<T>) -> Ordering {
391 self.as_slice().cmp(&other.as_slice())
395 impl<T> Container for Vec<T> {
397 fn len(&self) -> uint {
403 /// Returns the number of elements the vector can hold without
409 /// # use std::vec::Vec;
410 /// let vec: Vec<int> = Vec::with_capacity(10);
411 /// assert_eq!(vec.capacity(), 10);
414 pub fn capacity(&self) -> uint {
418 /// Reserves capacity for at least `n` additional elements in the given
423 /// Fails if the new capacity overflows `uint`.
428 /// # use std::vec::Vec;
429 /// let mut vec: Vec<int> = vec!(1);
430 /// vec.reserve_additional(10);
431 /// assert!(vec.capacity() >= 11);
433 pub fn reserve_additional(&mut self, extra: uint) {
434 if self.cap - self.len < extra {
435 match self.len.checked_add(&extra) {
436 None => fail!("Vec::reserve_additional: `uint` overflow"),
437 Some(new_cap) => self.reserve(new_cap)
442 /// Reserves capacity for at least `n` elements in the given vector.
444 /// This function will over-allocate in order to amortize the allocation
445 /// costs in scenarios where the caller may need to repeatedly reserve
446 /// additional space.
448 /// If the capacity for `self` is already equal to or greater than the
449 /// requested capacity, then no action is taken.
454 /// let mut vec = vec!(1, 2, 3);
456 /// assert!(vec.capacity() >= 10);
458 pub fn reserve(&mut self, capacity: uint) {
459 if capacity >= self.len {
460 self.reserve_exact(num::next_power_of_two(capacity))
464 /// Reserves capacity for exactly `capacity` elements in the given vector.
466 /// If the capacity for `self` is already equal to or greater than the
467 /// requested capacity, then no action is taken.
472 /// # use std::vec::Vec;
473 /// let mut vec: Vec<int> = Vec::with_capacity(10);
474 /// vec.reserve_exact(11);
475 /// assert_eq!(vec.capacity(), 11);
477 pub fn reserve_exact(&mut self, capacity: uint) {
478 if capacity > self.cap {
479 let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
482 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
487 /// Shrink the capacity of the vector to match the length
492 /// let mut vec = vec!(1, 2, 3);
493 /// vec.shrink_to_fit();
494 /// assert_eq!(vec.capacity(), vec.len());
496 pub fn shrink_to_fit(&mut self) {
498 unsafe { free(self.ptr as *mut c_void) };
500 self.ptr = 0 as *mut T;
503 // Overflow check is unnecessary as the vector is already at least this large.
504 self.ptr = realloc_raw(self.ptr as *mut u8, self.len * size_of::<T>()) as *mut T;
510 /// Remove the last element from a vector and return it, or `None` if it is
516 /// let mut vec = vec!(1, 2, 3);
517 /// assert_eq!(vec.pop(), Some(3));
518 /// assert_eq!(vec, vec!(1, 2));
521 pub fn pop(&mut self) -> Option<T> {
527 Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
532 /// Append an element to a vector.
536 /// Fails if the number of elements in the vector overflows a `uint`.
541 /// let mut vec = vec!(1, 2);
543 /// assert_eq!(vec, vec!(1, 2, 3));
546 pub fn push(&mut self, value: T) {
547 if self.len == self.cap {
548 if self.cap == 0 { self.cap += 2 }
549 let old_size = self.cap * size_of::<T>();
550 self.cap = self.cap * 2;
551 let size = old_size * 2;
552 if old_size > size { fail!("capacity overflow") }
554 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
559 let end = (self.ptr as *T).offset(self.len as int) as *mut T;
560 move_val_init(&mut *end, value);
565 /// Appends one element to the vector provided. The vector itself is then
566 /// returned for use again.
571 /// let vec = vec!(1, 2);
572 /// let vec = vec.append_one(3);
573 /// assert_eq!(vec, vec!(1, 2, 3));
576 pub fn append_one(mut self, x: T) -> Vec<T> {
581 /// Shorten a vector, dropping excess elements.
583 /// If `len` is greater than the vector's current length, this has no
589 /// let mut vec = vec!(1, 2, 3, 4);
591 /// assert_eq!(vec, vec!(1, 2));
593 pub fn truncate(&mut self, len: uint) {
596 // drop any extra elements
598 ptr::read(self.as_slice().unsafe_ref(i));
605 /// Work with `self` as a mutable slice.
610 /// fn foo(slice: &mut [int]) {}
612 /// let mut vec = vec!(1, 2);
613 /// foo(vec.as_mut_slice());
616 pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
618 transmute(Slice { data: self.as_mut_ptr() as *T, len: self.len })
622 /// Creates a consuming iterator, that is, one that moves each
623 /// value out of the vector (from start to end). The vector cannot
624 /// be used after calling this.
629 /// let v = vec!("a".to_owned(), "b".to_owned());
630 /// for s in v.move_iter() {
631 /// // s has type ~str, not &~str
632 /// println!("{}", s);
636 pub fn move_iter(self) -> MoveItems<T> {
638 let iter = transmute(self.as_slice().iter());
639 let ptr = self.ptr as *mut c_void;
641 MoveItems { allocation: ptr, iter: iter }
646 /// Sets the length of a vector.
648 /// This will explicitly set the size of the vector, without actually
649 /// modifying its buffers, so it is up to the caller to ensure that the
650 /// vector is actually the specified size.
652 pub unsafe fn set_len(&mut self, len: uint) {
656 /// Returns a reference to the value at index `index`.
660 /// Fails if `index` is out of bounds
665 /// let vec = vec!(1, 2, 3);
666 /// assert!(vec.get(1) == &2);
669 pub fn get<'a>(&'a self, index: uint) -> &'a T {
670 &self.as_slice()[index]
673 /// Returns a mutable reference to the value at index `index`.
677 /// Fails if `index` is out of bounds
682 /// let mut vec = vec!(1, 2, 3);
683 /// *vec.get_mut(1) = 4;
684 /// assert_eq!(vec, vec!(1, 4, 3));
687 pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
688 &mut self.as_mut_slice()[index]
691 /// Returns an iterator over references to the elements of the vector in
697 /// let vec = vec!(1, 2, 3);
698 /// for num in vec.iter() {
699 /// println!("{}", *num);
703 pub fn iter<'a>(&'a self) -> Items<'a,T> {
704 self.as_slice().iter()
708 /// Returns an iterator over mutable references to the elements of the
714 /// let mut vec = vec!(1, 2, 3);
715 /// for num in vec.mut_iter() {
720 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a,T> {
721 self.as_mut_slice().mut_iter()
724 /// Sort the vector, in place, using `compare` to compare elements.
726 /// This sort is `O(n log n)` worst-case and stable, but allocates
727 /// approximately `2 * n`, where `n` is the length of `self`.
732 /// let mut v = vec!(5i, 4, 1, 3, 2);
733 /// v.sort_by(|a, b| a.cmp(b));
734 /// assert_eq!(v, vec!(1, 2, 3, 4, 5));
736 /// // reverse sorting
737 /// v.sort_by(|a, b| b.cmp(a));
738 /// assert_eq!(v, vec!(5, 4, 3, 2, 1));
741 pub fn sort_by(&mut self, compare: |&T, &T| -> Ordering) {
742 self.as_mut_slice().sort_by(compare)
745 /// Returns a slice of `self` between `start` and `end`.
749 /// Fails when `start` or `end` point outside the bounds of `self`, or when
755 /// let vec = vec!(1, 2, 3, 4);
756 /// assert!(vec.slice(0, 2) == [1, 2]);
759 pub fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
760 self.as_slice().slice(start, end)
763 /// Returns a slice containing all but the first element of the vector.
767 /// Fails when the vector is empty.
772 /// let vec = vec!(1, 2, 3);
773 /// assert!(vec.tail() == [2, 3]);
776 pub fn tail<'a>(&'a self) -> &'a [T] {
777 self.as_slice().tail()
780 /// Returns all but the first `n' elements of a vector.
784 /// Fails when there are fewer than `n` elements in the vector.
789 /// let vec = vec!(1, 2, 3, 4);
790 /// assert!(vec.tailn(2) == [3, 4]);
793 pub fn tailn<'a>(&'a self, n: uint) -> &'a [T] {
794 self.as_slice().tailn(n)
797 /// Returns a reference to the last element of a vector, or `None` if it is
803 /// let vec = vec!(1, 2, 3);
804 /// assert!(vec.last() == Some(&3));
807 pub fn last<'a>(&'a self) -> Option<&'a T> {
808 self.as_slice().last()
811 /// Returns a mutable reference to the last element of a vector, or `None`
817 /// let mut vec = vec!(1, 2, 3);
818 /// *vec.mut_last().unwrap() = 4;
819 /// assert_eq!(vec, vec!(1, 2, 4));
822 pub fn mut_last<'a>(&'a mut self) -> Option<&'a mut T> {
823 self.as_mut_slice().mut_last()
826 /// Remove an element from anywhere in the vector and return it, replacing
827 /// it with the last element. This does not preserve ordering, but is O(1).
829 /// Returns `None` if `index` is out of bounds.
833 /// let mut v = vec!("foo".to_owned(), "bar".to_owned(), "baz".to_owned(), "qux".to_owned());
835 /// assert_eq!(v.swap_remove(1), Some("bar".to_owned()));
836 /// assert_eq!(v, vec!("foo".to_owned(), "qux".to_owned(), "baz".to_owned()));
838 /// assert_eq!(v.swap_remove(0), Some("foo".to_owned()));
839 /// assert_eq!(v, vec!("baz".to_owned(), "qux".to_owned()));
841 /// assert_eq!(v.swap_remove(2), None);
844 pub fn swap_remove(&mut self, index: uint) -> Option<T> {
845 let length = self.len();
846 if index < length - 1 {
847 self.as_mut_slice().swap(index, length - 1);
848 } else if index >= length {
854 /// Prepend an element to the vector.
858 /// This is an O(n) operation as it requires copying every element in the
864 /// let mut vec = vec!(1, 2, 3);
866 /// assert_eq!(vec, vec!(4, 1, 2, 3));
869 pub fn unshift(&mut self, element: T) {
870 self.insert(0, element)
873 /// Removes the first element from a vector and returns it, or `None` if
874 /// the vector is empty.
878 /// This is an O(n) operation as it requires copying every element in the
884 /// let mut vec = vec!(1, 2, 3);
885 /// assert!(vec.shift() == Some(1));
886 /// assert_eq!(vec, vec!(2, 3));
889 pub fn shift(&mut self) -> Option<T> {
893 /// Insert an element at position `index` within the vector, shifting all
894 /// elements after position i one position to the right.
898 /// Fails if `index` is out of bounds of the vector.
903 /// let mut vec = vec!(1, 2, 3);
904 /// vec.insert(1, 4);
905 /// assert_eq!(vec, vec!(1, 4, 2, 3));
907 pub fn insert(&mut self, index: uint, element: T) {
908 let len = self.len();
909 assert!(index <= len);
910 // space for the new element
911 self.reserve(len + 1);
913 unsafe { // infallible
914 // The spot to put the new value
916 let p = self.as_mut_ptr().offset(index as int);
917 // Shift everything over to make space. (Duplicating the
918 // `index`th element into two consecutive places.)
919 ptr::copy_memory(p.offset(1), &*p, len - index);
920 // Write it in, overwriting the first copy of the `index`th
922 move_val_init(&mut *p, element);
924 self.set_len(len + 1);
928 /// Remove and return the element at position `index` within the vector,
929 /// shifting all elements after position `index` one position to the left.
930 /// Returns `None` if `i` is out of bounds.
935 /// let mut v = vec!(1, 2, 3);
936 /// assert_eq!(v.remove(1), Some(2));
937 /// assert_eq!(v, vec!(1, 3));
939 /// assert_eq!(v.remove(4), None);
940 /// // v is unchanged:
941 /// assert_eq!(v, vec!(1, 3));
943 pub fn remove(&mut self, index: uint) -> Option<T> {
944 let len = self.len();
946 unsafe { // infallible
949 // the place we are taking from.
950 let ptr = self.as_mut_ptr().offset(index as int);
951 // copy it out, unsafely having a copy of the value on
952 // the stack and in the vector at the same time.
953 ret = Some(ptr::read(ptr as *T));
955 // Shift everything down to fill in that spot.
956 ptr::copy_memory(ptr, &*ptr.offset(1), len - index - 1);
958 self.set_len(len - 1);
966 /// Takes ownership of the vector `other`, moving all elements into
967 /// the current vector. This does not copy any elements, and it is
968 /// illegal to use the `other` vector after calling this method
969 /// (because it is moved here).
974 /// let mut vec = vec!(~1);
975 /// vec.push_all_move(vec!(~2, ~3, ~4));
976 /// assert_eq!(vec, vec!(~1, ~2, ~3, ~4));
978 pub fn push_all_move(&mut self, other: Vec<T>) {
979 self.extend(other.move_iter());
982 /// Returns a mutable slice of `self` between `start` and `end`.
986 /// Fails when `start` or `end` point outside the bounds of `self`, or when
992 /// let mut vec = vec!(1, 2, 3, 4);
993 /// assert!(vec.mut_slice(0, 2) == [1, 2]);
996 pub fn mut_slice<'a>(&'a mut self, start: uint, end: uint)
998 self.as_mut_slice().mut_slice(start, end)
1001 /// Returns a mutable slice of self from `start` to the end of the vec.
1005 /// Fails when `start` points outside the bounds of self.
1010 /// let mut vec = vec!(1, 2, 3, 4);
1011 /// assert!(vec.mut_slice_from(2) == [3, 4]);
1014 pub fn mut_slice_from<'a>(&'a mut self, start: uint) -> &'a mut [T] {
1015 self.as_mut_slice().mut_slice_from(start)
1018 /// Returns a mutable slice of self from the start of the vec to `end`.
1022 /// Fails when `end` points outside the bounds of self.
1027 /// let mut vec = vec!(1, 2, 3, 4);
1028 /// assert!(vec.mut_slice_to(2) == [1, 2]);
1031 pub fn mut_slice_to<'a>(&'a mut self, end: uint) -> &'a mut [T] {
1032 self.as_mut_slice().mut_slice_to(end)
1035 /// Returns a pair of mutable slices that divides the vec at an index.
1037 /// The first will contain all indices from `[0, mid)` (excluding
1038 /// the index `mid` itself) and the second will contain all
1039 /// indices from `[mid, len)` (excluding the index `len` itself).
1043 /// Fails if `mid > len`.
1048 /// let mut vec = vec!(1, 2, 3, 4, 5, 6);
1050 /// // scoped to restrict the lifetime of the borrows
1052 /// let (left, right) = vec.mut_split_at(0);
1053 /// assert!(left == &mut []);
1054 /// assert!(right == &mut [1, 2, 3, 4, 5, 6]);
1058 /// let (left, right) = vec.mut_split_at(2);
1059 /// assert!(left == &mut [1, 2]);
1060 /// assert!(right == &mut [3, 4, 5, 6]);
1064 /// let (left, right) = vec.mut_split_at(6);
1065 /// assert!(left == &mut [1, 2, 3, 4, 5, 6]);
1066 /// assert!(right == &mut []);
1070 pub fn mut_split_at<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
1071 self.as_mut_slice().mut_split_at(mid)
1074 /// Reverse the order of elements in a vector, in place.
1079 /// let mut v = vec!(1, 2, 3);
1081 /// assert_eq!(v, vec!(3, 2, 1));
1084 pub fn reverse(&mut self) {
1085 self.as_mut_slice().reverse()
1088 /// Returns a slice of `self` from `start` to the end of the vec.
1092 /// Fails when `start` points outside the bounds of self.
1097 /// let vec = vec!(1, 2, 3);
1098 /// assert!(vec.slice_from(1) == [2, 3]);
1101 pub fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
1102 self.as_slice().slice_from(start)
1105 /// Returns a slice of self from the start of the vec to `end`.
1109 /// Fails when `end` points outside the bounds of self.
1114 /// let vec = vec!(1, 2, 3);
1115 /// assert!(vec.slice_to(2) == [1, 2]);
1118 pub fn slice_to<'a>(&'a self, end: uint) -> &'a [T] {
1119 self.as_slice().slice_to(end)
1122 /// Returns a slice containing all but the last element of the vector.
1126 /// Fails if the vector is empty
1128 pub fn init<'a>(&'a self) -> &'a [T] {
1129 self.slice(0, self.len() - 1)
1133 /// Returns an unsafe pointer to the vector's buffer.
1135 /// The caller must ensure that the vector outlives the pointer this
1136 /// function returns, or else it will end up pointing to garbage.
1138 /// Modifying the vector may cause its buffer to be reallocated, which
1139 /// would also make any pointers to it invalid.
1141 pub fn as_ptr(&self) -> *T {
1142 // If we have a 0-sized vector, then the base pointer should not be NULL
1143 // because an iterator over the slice will attempt to yield the base
1144 // pointer as the first element in the vector, but this will end up
1145 // being Some(NULL) which is optimized to None.
1146 if mem::size_of::<T>() == 0 {
1153 /// Returns a mutable unsafe pointer to the vector's buffer.
1155 /// The caller must ensure that the vector outlives the pointer this
1156 /// function returns, or else it will end up pointing to garbage.
1158 /// Modifying the vector may cause its buffer to be reallocated, which
1159 /// would also make any pointers to it invalid.
1161 pub fn as_mut_ptr(&mut self) -> *mut T {
1162 // see above for the 0-size check
1163 if mem::size_of::<T>() == 0 {
1170 /// Retains only the elements specified by the predicate.
1172 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1173 /// This method operates in place and preserves the order the retained elements.
1178 /// let mut vec = vec!(1i, 2, 3, 4);
1179 /// vec.retain(|x| x%2 == 0);
1180 /// assert_eq!(vec, vec!(2, 4));
1182 pub fn retain(&mut self, f: |&T| -> bool) {
1183 let len = self.len();
1186 let v = self.as_mut_slice();
1188 for i in range(0u, len) {
1197 self.truncate(len - del);
1201 /// Expands a vector in place, initializing the new elements to the result of a function.
1203 /// The vector is grown by `n` elements. The i-th new element are initialized to the value
1204 /// returned by `f(i)` where `i` is in the range [0, n).
1209 /// let mut vec = vec!(0u, 1);
1210 /// vec.grow_fn(3, |i| i);
1211 /// assert_eq!(vec, vec!(0, 1, 0, 1, 2));
1213 pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) {
1214 self.reserve_additional(n);
1215 for i in range(0u, n) {
1221 impl<T:TotalOrd> Vec<T> {
1222 /// Sorts the vector in place.
1224 /// This sort is `O(n log n)` worst-case and stable, but allocates
1225 /// approximately `2 * n`, where `n` is the length of `self`.
1230 /// let mut vec = vec!(3i, 1, 2);
1232 /// assert_eq!(vec, vec!(1, 2, 3));
1234 pub fn sort(&mut self) {
1235 self.as_mut_slice().sort()
1239 impl<T> Mutable for Vec<T> {
1241 fn clear(&mut self) {
1247 /// Return true if a vector contains an element with the given value
1252 /// let vec = vec!(1, 2, 3);
1253 /// assert!(vec.contains(&1));
1255 pub fn contains(&self, x: &T) -> bool {
1256 self.as_slice().contains(x)
1259 /// Remove consecutive repeated elements in the vector.
1261 /// If the vector is sorted, this removes all duplicates.
1266 /// let mut vec = vec!(1, 2, 2, 3, 2);
1268 /// assert_eq!(vec, vec!(1, 2, 3, 2));
1270 pub fn dedup(&mut self) {
1272 // Although we have a mutable reference to `self`, we cannot make
1273 // *arbitrary* changes. The `Eq` comparisons could fail, so we
1274 // must ensure that the vector is in a valid state at all time.
1276 // The way that we handle this is by using swaps; we iterate
1277 // over all the elements, swapping as we go so that at the end
1278 // the elements we wish to keep are in the front, and those we
1279 // wish to reject are at the back. We can then truncate the
1280 // vector. This operation is still O(n).
1282 // Example: We start in this state, where `r` represents "next
1283 // read" and `w` represents "next_write`.
1286 // +---+---+---+---+---+---+
1287 // | 0 | 1 | 1 | 2 | 3 | 3 |
1288 // +---+---+---+---+---+---+
1291 // Comparing self[r] against self[w-1], tis is not a duplicate, so
1292 // we swap self[r] and self[w] (no effect as r==w) and then increment both
1293 // r and w, leaving us with:
1296 // +---+---+---+---+---+---+
1297 // | 0 | 1 | 1 | 2 | 3 | 3 |
1298 // +---+---+---+---+---+---+
1301 // Comparing self[r] against self[w-1], this value is a duplicate,
1302 // so we increment `r` but leave everything else unchanged:
1305 // +---+---+---+---+---+---+
1306 // | 0 | 1 | 1 | 2 | 3 | 3 |
1307 // +---+---+---+---+---+---+
1310 // Comparing self[r] against self[w-1], this is not a duplicate,
1311 // so swap self[r] and self[w] and advance r and w:
1314 // +---+---+---+---+---+---+
1315 // | 0 | 1 | 2 | 1 | 3 | 3 |
1316 // +---+---+---+---+---+---+
1319 // Not a duplicate, repeat:
1322 // +---+---+---+---+---+---+
1323 // | 0 | 1 | 2 | 3 | 1 | 3 |
1324 // +---+---+---+---+---+---+
1327 // Duplicate, advance r. End of vec. Truncate to w.
1329 let ln = self.len();
1330 if ln < 1 { return; }
1332 // Avoid bounds checks by using unsafe pointers.
1333 let p = self.as_mut_slice().as_mut_ptr();
1338 let p_r = p.offset(r as int);
1339 let p_wm1 = p.offset((w - 1) as int);
1342 let p_w = p_wm1.offset(1);
1343 mem::swap(&mut *p_r, &mut *p_w);
1355 impl<T> Vector<T> for Vec<T> {
1356 /// Work with `self` as a slice.
1361 /// fn foo(slice: &[int]) {}
1363 /// let vec = vec!(1, 2);
1364 /// foo(vec.as_slice());
1367 fn as_slice<'a>(&'a self) -> &'a [T] {
1368 unsafe { transmute(Slice { data: self.as_ptr(), len: self.len }) }
1372 #[unsafe_destructor]
1373 impl<T> Drop for Vec<T> {
1374 fn drop(&mut self) {
1375 // This is (and should always remain) a no-op if the fields are
1376 // zeroed (when moving out, because of #[unsafe_no_drop_flag]).
1378 for x in self.as_mut_slice().iter() {
1381 free(self.ptr as *mut c_void)
1386 impl<T> Default for Vec<T> {
1387 fn default() -> Vec<T> {
1392 impl<T:fmt::Show> fmt::Show for Vec<T> {
1393 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1394 self.as_slice().fmt(f)
1398 /// An iterator that moves out of a vector.
1399 pub struct MoveItems<T> {
1400 allocation: *mut c_void, // the block of memory allocated for the vector
1401 iter: Items<'static, T>
1404 impl<T> Iterator<T> for MoveItems<T> {
1406 fn next(&mut self) -> Option<T> {
1408 self.iter.next().map(|x| ptr::read(x))
1413 fn size_hint(&self) -> (uint, Option<uint>) {
1414 self.iter.size_hint()
1418 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
1420 fn next_back(&mut self) -> Option<T> {
1422 self.iter.next_back().map(|x| ptr::read(x))
1427 #[unsafe_destructor]
1428 impl<T> Drop for MoveItems<T> {
1429 fn drop(&mut self) {
1430 // destroy the remaining elements
1433 free(self.allocation)
1444 fn test_small_vec_struct() {
1445 assert!(size_of::<Vec<u8>>() == size_of::<uint>() * 3);
1449 fn test_double_drop() {
1455 struct DropCounter<'a> {
1459 #[unsafe_destructor]
1460 impl<'a> Drop for DropCounter<'a> {
1461 fn drop(&mut self) {
1466 let mut count_x @ mut count_y = 0;
1468 let mut tv = TwoVec {
1472 tv.x.push(DropCounter {count: &mut count_x});
1473 tv.y.push(DropCounter {count: &mut count_y});
1475 // If Vec had a drop flag, here is where it would be zeroed.
1476 // Instead, it should rely on its internal state to prevent
1477 // doing anything significant when dropped multiple times.
1480 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
1483 assert_eq!(count_x, 1);
1484 assert_eq!(count_y, 1);
1488 fn test_reserve_additional() {
1489 let mut v = Vec::new();
1490 assert_eq!(v.capacity(), 0);
1492 v.reserve_additional(2);
1493 assert!(v.capacity() >= 2);
1495 for i in range(0, 16) {
1499 assert!(v.capacity() >= 16);
1500 v.reserve_additional(16);
1501 assert!(v.capacity() >= 32);
1505 v.reserve_additional(16);
1506 assert!(v.capacity() >= 33)
1511 let mut v = Vec::new();
1512 let mut w = Vec::new();
1514 v.extend(range(0, 3));
1515 for i in range(0, 3) { w.push(i) }
1519 v.extend(range(3, 10));
1520 for i in range(3, 10) { w.push(i) }
1526 fn test_mut_slice_from() {
1527 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1529 let slice = values.mut_slice_from(2);
1530 assert!(slice == [3, 4, 5]);
1531 for p in slice.mut_iter() {
1536 assert!(values.as_slice() == [1, 2, 5, 6, 7]);
1540 fn test_mut_slice_to() {
1541 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1543 let slice = values.mut_slice_to(2);
1544 assert!(slice == [1, 2]);
1545 for p in slice.mut_iter() {
1550 assert!(values.as_slice() == [2, 3, 3, 4, 5]);
1554 fn test_mut_split_at() {
1555 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1557 let (left, right) = values.mut_split_at(2);
1558 assert!(left.slice(0, left.len()) == [1, 2]);
1559 for p in left.mut_iter() {
1563 assert!(right.slice(0, right.len()) == [3, 4, 5]);
1564 for p in right.mut_iter() {
1569 assert!(values == Vec::from_slice([2u8, 3, 5, 6, 7]));
1574 let v: Vec<int> = vec!();
1575 let w = vec!(1, 2, 3);
1577 assert_eq!(v, v.clone());
1581 // they should be disjoint in memory.
1582 assert!(w.as_ptr() != z.as_ptr())
1586 fn test_clone_from() {
1588 let three = vec!(~1, ~2, ~3);
1589 let two = vec!(~4, ~5);
1591 v.clone_from(&three);
1592 assert_eq!(v, three);
1595 v.clone_from(&three);
1596 assert_eq!(v, three);
1603 v.clone_from(&three);
1604 assert_eq!(v, three)
1609 let mut v = Vec::from_slice([0u, 1]);
1610 v.grow_fn(3, |i| i);
1611 assert!(v == Vec::from_slice([0u, 1, 0, 1, 2]));
1616 let mut vec = Vec::from_slice([1u, 2, 3, 4]);
1617 vec.retain(|x| x%2 == 0);
1618 assert!(vec == Vec::from_slice([2u, 4]));
1622 fn zero_sized_values() {
1623 let mut v = Vec::new();
1624 assert_eq!(v.len(), 0);
1626 assert_eq!(v.len(), 1);
1628 assert_eq!(v.len(), 2);
1629 assert_eq!(v.pop(), Some(()));
1630 assert_eq!(v.pop(), Some(()));
1631 assert_eq!(v.pop(), None);
1633 assert_eq!(v.iter().len(), 0);
1635 assert_eq!(v.iter().len(), 1);
1637 assert_eq!(v.iter().len(), 2);
1639 for &() in v.iter() {}
1641 assert_eq!(v.mut_iter().len(), 2);
1643 assert_eq!(v.mut_iter().len(), 3);
1645 assert_eq!(v.mut_iter().len(), 4);
1647 for &() in v.mut_iter() {}
1648 unsafe { v.set_len(0); }
1649 assert_eq!(v.mut_iter().len(), 0);