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.
15 use alloc::heap::{allocate, reallocate, deallocate};
18 use core::default::Default;
21 use core::num::{CheckedMul, CheckedAdd};
26 use {Collection, Mutable, MutableSeq};
27 use slice::{MutableOrdVector, MutableVectorAllocating, CloneableVector};
28 use slice::{Items, MutItems};
32 pub static PTR_MARKER: u8 = 0;
34 /// An owned, growable vector.
39 /// let mut vec = Vec::new();
43 /// assert_eq!(vec.len(), 2);
44 /// assert_eq!(vec[0], 1);
46 /// assert_eq!(vec.pop(), Some(2));
47 /// assert_eq!(vec.len(), 1);
49 /// *vec.get_mut(0) = 7i;
50 /// assert_eq!(vec[0], 7);
52 /// vec.push_all([1, 2, 3]);
54 /// for x in vec.iter() {
55 /// println!("{}", x);
57 /// assert_eq!(vec, vec![7i, 1, 2, 3]);
60 /// The `vec!` macro is provided to make initialization more convenient:
63 /// let mut vec = vec![1i, 2i, 3i];
65 /// assert_eq!(vec, vec![1, 2, 3, 4]);
68 /// Use a `Vec` as an efficient stack:
71 /// let mut stack = Vec::new();
78 /// let top = match stack.pop() {
79 /// None => break, // empty
83 /// println!("{}", top);
87 /// # Capacity and reallocation
89 /// The capacity of a vector is the amount of space allocated for any future
90 /// elements that will be added onto the vector. This is not to be confused
91 /// with the *length* of a vector, which specifies the number of actual
92 /// elements within the vector. If a vector's length exceeds its capacity,
93 /// its capacity will automatically be increased, but its elements will
94 /// have to be reallocated.
96 /// For example, a vector with capacity 10 and length 0 would be an empty
97 /// vector with space for 10 more elements. Pushing 10 or fewer elements onto
98 /// the vector will not change its capacity or cause reallocation to occur.
99 /// However, if the vector's length is increased to 11, it will have to
100 /// reallocate, which can be slow. For this reason, it is recommended
101 /// to use `Vec::with_capacity` whenever possible to specify how big the vector
102 /// is expected to get.
103 #[unsafe_no_drop_flag]
111 /// Constructs a new, empty `Vec`.
113 /// The vector will not allocate until elements are pushed onto it.
118 /// let mut vec: Vec<int> = Vec::new();
121 pub fn new() -> Vec<T> {
122 // We want ptr to never be NULL so instead we set it to some arbitrary
123 // non-null value which is fine since we never call deallocate on the ptr
124 // if cap is 0. The reason for this is because the pointer of a slice
125 // being NULL would break the null pointer optimization for enums.
126 Vec { len: 0, cap: 0, ptr: &PTR_MARKER as *const _ as *mut T }
129 /// Constructs a new, empty `Vec` with the specified capacity.
131 /// The vector will be able to hold exactly `capacity` elements without
132 /// reallocating. If `capacity` is 0, the vector will not allocate.
134 /// It is important to note that this function does not specify the
135 /// *length* of the returned vector, but only the *capacity*. (For an
136 /// explanation of the difference between length and capacity, see
137 /// the main `Vec` docs above, 'Capacity and reallocation'.) To create
138 /// a vector of a given length, use `Vec::from_elem` or `Vec::from_fn`.
143 /// let mut vec: Vec<int> = Vec::with_capacity(10);
145 /// // The vector contains no items, even though it has capacity for more
146 /// assert_eq!(vec.len(), 0);
148 /// // These are all done without reallocating...
149 /// for i in range(0i, 10) {
153 /// // ...but this may make the vector reallocate
157 pub fn with_capacity(capacity: uint) -> Vec<T> {
158 if mem::size_of::<T>() == 0 {
159 Vec { len: 0, cap: uint::MAX, ptr: &PTR_MARKER as *const _ as *mut T }
160 } else if capacity == 0 {
163 let size = capacity.checked_mul(&mem::size_of::<T>())
164 .expect("capacity overflow");
165 let ptr = unsafe { allocate(size, mem::min_align_of::<T>()) };
166 Vec { len: 0, cap: capacity, ptr: ptr as *mut T }
170 /// Creates and initializes a `Vec`.
172 /// Creates a `Vec` of size `length` and initializes the elements to the
173 /// value returned by the closure `op`.
178 /// let vec = Vec::from_fn(3, |idx| idx * 2);
179 /// assert_eq!(vec, vec![0, 2, 4]);
182 pub fn from_fn(length: uint, op: |uint| -> T) -> Vec<T> {
184 let mut xs = Vec::with_capacity(length);
185 while xs.len < length {
187 ptr::write(xs.as_mut_slice().unsafe_mut_ref(len), op(len));
194 /// Create a `Vec<T>` directly from the raw constituents.
196 /// This is highly unsafe:
198 /// - if `ptr` is null, then `length` and `capacity` should be 0
199 /// - `ptr` must point to an allocation of size `capacity`
200 /// - there must be `length` valid instances of type `T` at the
201 /// beginning of that allocation
202 /// - `ptr` must be allocated by the default `Vec` allocator
211 /// let mut v = vec![1i, 2, 3];
213 /// // Pull out the various important pieces of information about `v`
214 /// let p = v.as_mut_ptr();
215 /// let len = v.len();
216 /// let cap = v.capacity();
219 /// // Cast `v` into the void: no destructor run, so we are in
220 /// // complete control of the allocation to which `p` points.
223 /// // Overwrite memory with 4, 5, 6
224 /// for i in range(0, len as int) {
225 /// ptr::write(p.offset(i), 4 + i);
228 /// // Put everything back together into a Vec
229 /// let rebuilt = Vec::from_raw_parts(len, cap, p);
230 /// assert_eq!(rebuilt, vec![4i, 5i, 6i]);
234 pub unsafe fn from_raw_parts(length: uint, capacity: uint,
235 ptr: *mut T) -> Vec<T> {
236 Vec { len: length, cap: capacity, ptr: ptr }
239 /// Consumes the `Vec`, partitioning it based on a predicate.
241 /// Partitions the `Vec` into two `Vec`s `(A,B)`, where all elements of `A`
242 /// satisfy `f` and all elements of `B` do not. The order of elements is
248 /// let vec = vec![1i, 2i, 3i, 4i];
249 /// let (even, odd) = vec.partition(|&n| n % 2 == 0);
250 /// assert_eq!(even, vec![2, 4]);
251 /// assert_eq!(odd, vec![1, 3]);
254 pub fn partition(self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
255 let mut lefts = Vec::new();
256 let mut rights = Vec::new();
258 for elt in self.move_iter() {
270 impl<T: Clone> Vec<T> {
271 /// Iterates over the `second` vector, copying each element and appending it to
272 /// the `first`. Afterwards, the `first` is then returned for use again.
277 /// let vec = vec![1i, 2i];
278 /// let vec = vec.append([3i, 4i]);
279 /// assert_eq!(vec, vec![1, 2, 3, 4]);
282 pub fn append(mut self, second: &[T]) -> Vec<T> {
283 self.push_all(second);
287 /// Constructs a `Vec` by cloning elements of a slice.
292 /// let slice = [1i, 2, 3];
293 /// let vec = Vec::from_slice(slice);
296 pub fn from_slice(values: &[T]) -> Vec<T> {
297 let mut vector = Vec::new();
298 vector.push_all(values);
302 /// Constructs a `Vec` with copies of a value.
304 /// Creates a `Vec` with `length` copies of `value`.
308 /// let vec = Vec::from_elem(3, "hi");
309 /// println!("{}", vec); // prints [hi, hi, hi]
312 pub fn from_elem(length: uint, value: T) -> Vec<T> {
314 let mut xs = Vec::with_capacity(length);
315 while xs.len < length {
317 ptr::write(xs.as_mut_slice().unsafe_mut_ref(len),
325 /// Appends all elements in a slice to the `Vec`.
327 /// Iterates over the slice `other`, clones each element, and then appends
328 /// it to this `Vec`. The `other` vector is traversed in-order.
333 /// let mut vec = vec![1i];
334 /// vec.push_all([2i, 3, 4]);
335 /// assert_eq!(vec, vec![1, 2, 3, 4]);
338 pub fn push_all(&mut self, other: &[T]) {
339 self.reserve_additional(other.len());
341 for i in range(0, other.len()) {
342 let len = self.len();
344 // Unsafe code so this can be optimised to a memcpy (or something similarly
345 // fast) when T is Copy. LLVM is easily confused, so any extra operations
346 // during the loop can prevent this optimisation.
349 self.as_mut_slice().unsafe_mut_ref(len),
350 other.unsafe_ref(i).clone());
351 self.set_len(len + 1);
356 /// Grows the `Vec` in-place.
358 /// Adds `n` copies of `value` to the `Vec`.
363 /// let mut vec = vec!["hello"];
364 /// vec.grow(2, &("world"));
365 /// assert_eq!(vec, vec!["hello", "world", "world"]);
367 pub fn grow(&mut self, n: uint, value: &T) {
368 self.reserve_additional(n);
369 let mut i: uint = 0u;
372 self.push((*value).clone());
377 /// Sets the value of a vector element at a given index, growing the vector
380 /// Sets the element at position `index` to `value`. If `index` is past the
381 /// end of the vector, expands the vector by replicating `initval` to fill
382 /// the intervening space.
387 /// let mut vec = vec!["a", "b", "c"];
388 /// vec.grow_set(1, &("fill"), "d");
389 /// vec.grow_set(4, &("fill"), "e");
390 /// assert_eq!(vec, vec!["a", "d", "c", "fill", "e"]);
392 pub fn grow_set(&mut self, index: uint, initval: &T, value: T) {
395 self.grow(index - l + 1u, initval);
397 *self.get_mut(index) = value;
400 /// Partitions a vector based on a predicate.
402 /// Clones the elements of the vector, partitioning them into two `Vec`s
403 /// `(A,B)`, where all elements of `A` satisfy `f` and all elements of `B`
404 /// do not. The order of elements is preserved.
409 /// let vec = vec![1i, 2, 3, 4];
410 /// let (even, odd) = vec.partitioned(|&n| n % 2 == 0);
411 /// assert_eq!(even, vec![2i, 4]);
412 /// assert_eq!(odd, vec![1i, 3]);
414 pub fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
415 let mut lefts = Vec::new();
416 let mut rights = Vec::new();
418 for elt in self.iter() {
420 lefts.push(elt.clone());
422 rights.push(elt.clone());
431 impl<T:Clone> Clone for Vec<T> {
432 fn clone(&self) -> Vec<T> {
433 Vec::from_slice(self.as_slice())
436 fn clone_from(&mut self, other: &Vec<T>) {
437 // drop anything in self that will not be overwritten
438 if self.len() > other.len() {
439 self.truncate(other.len())
442 // reuse the contained values' allocations/resources.
443 for (place, thing) in self.mut_iter().zip(other.iter()) {
444 place.clone_from(thing)
447 // self.len <= other.len due to the truncate above, so the
448 // slice here is always in-bounds.
449 let slice = other.slice_from(self.len());
450 self.push_all(slice);
454 impl<T> Index<uint,T> for Vec<T> {
456 fn index<'a>(&'a self, index: &uint) -> &'a T {
461 // FIXME(#12825) Indexing will always try IndexMut first and that causes issues.
462 /*impl<T> IndexMut<uint,T> for Vec<T> {
464 fn index_mut<'a>(&'a mut self, index: &uint) -> &'a mut T {
469 impl<T> FromIterator<T> for Vec<T> {
471 fn from_iter<I:Iterator<T>>(mut iterator: I) -> Vec<T> {
472 let (lower, _) = iterator.size_hint();
473 let mut vector = Vec::with_capacity(lower);
474 for element in iterator {
481 impl<T> Extendable<T> for Vec<T> {
483 fn extend<I: Iterator<T>>(&mut self, mut iterator: I) {
484 let (lower, _) = iterator.size_hint();
485 self.reserve_additional(lower);
486 for element in iterator {
492 impl<T: PartialEq> PartialEq for Vec<T> {
494 fn eq(&self, other: &Vec<T>) -> bool {
495 self.as_slice() == other.as_slice()
499 impl<T: PartialOrd> PartialOrd for Vec<T> {
501 fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
502 self.as_slice().partial_cmp(&other.as_slice())
506 impl<T: Eq> Eq for Vec<T> {}
508 impl<T: PartialEq, V: Vector<T>> Equiv<V> for Vec<T> {
510 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
513 impl<T: Ord> Ord for Vec<T> {
515 fn cmp(&self, other: &Vec<T>) -> Ordering {
516 self.as_slice().cmp(&other.as_slice())
520 impl<T> Collection for Vec<T> {
522 fn len(&self) -> uint {
527 impl<T: Clone> CloneableVector<T> for Vec<T> {
528 fn to_vec(&self) -> Vec<T> { self.clone() }
529 fn into_vec(self) -> Vec<T> { self }
532 // FIXME: #13996: need a way to mark the return value as `noalias`
534 unsafe fn alloc_or_realloc<T>(ptr: *mut T, size: uint, old_size: uint) -> *mut T {
536 allocate(size, mem::min_align_of::<T>()) as *mut T
538 reallocate(ptr as *mut u8, size,
539 mem::min_align_of::<T>(), old_size) as *mut T
544 unsafe fn dealloc<T>(ptr: *mut T, len: uint) {
545 if mem::size_of::<T>() != 0 {
546 deallocate(ptr as *mut u8,
547 len * mem::size_of::<T>(),
548 mem::min_align_of::<T>())
553 /// Returns the number of elements the vector can hold without
559 /// let vec: Vec<int> = Vec::with_capacity(10);
560 /// assert_eq!(vec.capacity(), 10);
563 pub fn capacity(&self) -> uint {
567 /// Reserves capacity for at least `n` additional elements in the given
572 /// Fails if the new capacity overflows `uint`.
577 /// let mut vec: Vec<int> = vec![1i];
578 /// vec.reserve_additional(10);
579 /// assert!(vec.capacity() >= 11);
581 pub fn reserve_additional(&mut self, extra: uint) {
582 if self.cap - self.len < extra {
583 match self.len.checked_add(&extra) {
584 None => fail!("Vec::reserve_additional: `uint` overflow"),
585 Some(new_cap) => self.reserve(new_cap)
590 /// Reserves capacity for at least `n` elements in the given vector.
592 /// This function will over-allocate in order to amortize the allocation
593 /// costs in scenarios where the caller may need to repeatedly reserve
594 /// additional space.
596 /// If the capacity for `self` is already equal to or greater than the
597 /// requested capacity, then no action is taken.
602 /// let mut vec = vec![1i, 2, 3];
604 /// assert!(vec.capacity() >= 10);
606 pub fn reserve(&mut self, capacity: uint) {
607 if capacity > self.cap {
608 self.reserve_exact(num::next_power_of_two(capacity))
612 /// Reserves capacity for exactly `capacity` elements in the given vector.
614 /// If the capacity for `self` is already equal to or greater than the
615 /// requested capacity, then no action is taken.
620 /// let mut vec: Vec<int> = Vec::with_capacity(10);
621 /// vec.reserve_exact(11);
622 /// assert_eq!(vec.capacity(), 11);
624 pub fn reserve_exact(&mut self, capacity: uint) {
625 if mem::size_of::<T>() == 0 { return }
627 if capacity > self.cap {
628 let size = capacity.checked_mul(&mem::size_of::<T>())
629 .expect("capacity overflow");
631 self.ptr = alloc_or_realloc(self.ptr, size,
632 self.cap * mem::size_of::<T>());
638 /// Shrink the capacity of the vector as much as possible
643 /// let mut vec = vec![1i, 2, 3];
644 /// vec.shrink_to_fit();
646 pub fn shrink_to_fit(&mut self) {
647 if mem::size_of::<T>() == 0 { return }
652 dealloc(self.ptr, self.cap)
658 // Overflow check is unnecessary as the vector is already at
660 self.ptr = reallocate(self.ptr as *mut u8,
661 self.len * mem::size_of::<T>(),
662 mem::min_align_of::<T>(),
663 self.cap * mem::size_of::<T>()) as *mut T;
669 /// Appends one element to the vector provided. The vector itself is then
670 /// returned for use again.
675 /// let vec = vec![1i, 2];
676 /// let vec = vec.append_one(3);
677 /// assert_eq!(vec, vec![1, 2, 3]);
680 pub fn append_one(mut self, x: T) -> Vec<T> {
685 /// Shorten a vector, dropping excess elements.
687 /// If `len` is greater than the vector's current length, this has no
693 /// let mut vec = vec![1i, 2, 3, 4];
695 /// assert_eq!(vec, vec![1, 2]);
697 pub fn truncate(&mut self, len: uint) {
699 // drop any extra elements
700 while len < self.len {
701 // decrement len before the read(), so a failure on Drop doesn't
702 // re-drop the just-failed value.
704 ptr::read(self.as_slice().unsafe_ref(self.len));
709 /// Work with `self` as a mutable slice.
714 /// fn foo(slice: &mut [int]) {}
716 /// let mut vec = vec![1i, 2];
717 /// foo(vec.as_mut_slice());
720 pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
722 mem::transmute(Slice {
723 data: self.as_mut_ptr() as *const T,
729 /// Creates a consuming iterator, that is, one that moves each
730 /// value out of the vector (from start to end). The vector cannot
731 /// be used after calling this.
736 /// let v = vec!["a".to_string(), "b".to_string()];
737 /// for s in v.move_iter() {
738 /// // s has type String, not &String
739 /// println!("{}", s);
743 pub fn move_iter(self) -> MoveItems<T> {
745 let iter = mem::transmute(self.as_slice().iter());
749 MoveItems { allocation: ptr, cap: cap, iter: iter }
754 /// Sets the length of a vector.
756 /// This will explicitly set the size of the vector, without actually
757 /// modifying its buffers, so it is up to the caller to ensure that the
758 /// vector is actually the specified size.
763 /// let mut v = vec![1u, 2, 3, 4];
769 pub unsafe fn set_len(&mut self, len: uint) {
773 /// Returns a reference to the value at index `index`.
777 /// Fails if `index` is out of bounds
782 /// #![allow(deprecated)]
784 /// let vec = vec![1i, 2, 3];
785 /// assert!(vec.get(1) == &2);
787 #[deprecated="prefer using indexing, e.g., vec[0]"]
789 pub fn get<'a>(&'a self, index: uint) -> &'a T {
790 &self.as_slice()[index]
793 /// Returns a mutable reference to the value at index `index`.
797 /// Fails if `index` is out of bounds
802 /// let mut vec = vec![1i, 2, 3];
803 /// *vec.get_mut(1) = 4;
804 /// assert_eq!(vec, vec![1i, 4, 3]);
807 pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
808 &mut self.as_mut_slice()[index]
811 /// Returns an iterator over references to the elements of the vector in
817 /// let vec = vec![1i, 2, 3];
818 /// for num in vec.iter() {
819 /// println!("{}", *num);
823 pub fn iter<'a>(&'a self) -> Items<'a,T> {
824 self.as_slice().iter()
828 /// Returns an iterator over mutable references to the elements of the
834 /// let mut vec = vec![1i, 2, 3];
835 /// for num in vec.mut_iter() {
840 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a,T> {
841 self.as_mut_slice().mut_iter()
844 /// Sort the vector, in place, using `compare` to compare elements.
846 /// This sort is `O(n log n)` worst-case and stable, but allocates
847 /// approximately `2 * n`, where `n` is the length of `self`.
852 /// let mut v = vec![5i, 4, 1, 3, 2];
853 /// v.sort_by(|a, b| a.cmp(b));
854 /// assert_eq!(v, vec![1i, 2, 3, 4, 5]);
856 /// // reverse sorting
857 /// v.sort_by(|a, b| b.cmp(a));
858 /// assert_eq!(v, vec![5i, 4, 3, 2, 1]);
861 pub fn sort_by(&mut self, compare: |&T, &T| -> Ordering) {
862 self.as_mut_slice().sort_by(compare)
865 /// Returns a slice of self spanning the interval [`start`, `end`).
869 /// Fails when the slice (or part of it) is outside the bounds of self, or when
875 /// let vec = vec![1i, 2, 3, 4];
876 /// assert!(vec.slice(0, 2) == [1, 2]);
879 pub fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
880 self.as_slice().slice(start, end)
883 /// Returns a slice containing all but the first element of the vector.
887 /// Fails when the vector is empty.
892 /// let vec = vec![1i, 2, 3];
893 /// assert!(vec.tail() == [2, 3]);
896 pub fn tail<'a>(&'a self) -> &'a [T] {
897 self.as_slice().tail()
900 /// Returns all but the first `n' elements of a vector.
904 /// Fails when there are fewer than `n` elements in the vector.
909 /// let vec = vec![1i, 2, 3, 4];
910 /// assert!(vec.tailn(2) == [3, 4]);
913 pub fn tailn<'a>(&'a self, n: uint) -> &'a [T] {
914 self.as_slice().tailn(n)
917 /// Returns a reference to the last element of a vector, or `None` if it is
923 /// let vec = vec![1i, 2, 3];
924 /// assert!(vec.last() == Some(&3));
927 pub fn last<'a>(&'a self) -> Option<&'a T> {
928 self.as_slice().last()
931 /// Returns a mutable reference to the last element of a vector, or `None`
937 /// let mut vec = vec![1i, 2, 3];
938 /// *vec.mut_last().unwrap() = 4;
939 /// assert_eq!(vec, vec![1i, 2, 4]);
942 pub fn mut_last<'a>(&'a mut self) -> Option<&'a mut T> {
943 self.as_mut_slice().mut_last()
946 /// Remove an element from anywhere in the vector and return it, replacing
947 /// it with the last element. This does not preserve ordering, but is O(1).
949 /// Returns `None` if `index` is out of bounds.
953 /// let mut v = vec!["foo".to_string(), "bar".to_string(),
954 /// "baz".to_string(), "qux".to_string()];
956 /// assert_eq!(v.swap_remove(1), Some("bar".to_string()));
957 /// assert_eq!(v, vec!["foo".to_string(), "qux".to_string(), "baz".to_string()]);
959 /// assert_eq!(v.swap_remove(0), Some("foo".to_string()));
960 /// assert_eq!(v, vec!["baz".to_string(), "qux".to_string()]);
962 /// assert_eq!(v.swap_remove(2), None);
965 pub fn swap_remove(&mut self, index: uint) -> Option<T> {
966 let length = self.len();
967 if index < length - 1 {
968 self.as_mut_slice().swap(index, length - 1);
969 } else if index >= length {
975 /// Prepend an element to the vector.
979 /// This is an O(n) operation as it requires copying every element in the
985 /// let mut vec = vec![1i, 2, 3];
987 /// assert_eq!(vec, vec![4, 1, 2, 3]);
990 pub fn unshift(&mut self, element: T) {
991 self.insert(0, element)
994 /// Removes the first element from a vector and returns it, or `None` if
995 /// the vector is empty.
999 /// This is an O(n) operation as it requires copying every element in the
1005 /// let mut vec = vec![1i, 2, 3];
1006 /// assert!(vec.shift() == Some(1));
1007 /// assert_eq!(vec, vec![2, 3]);
1010 pub fn shift(&mut self) -> Option<T> {
1014 /// Insert an element at position `index` within the vector, shifting all
1015 /// elements after position i one position to the right.
1019 /// Fails if `index` is not between `0` and the vector's length (both
1020 /// bounds inclusive).
1025 /// let mut vec = vec![1i, 2, 3];
1026 /// vec.insert(1, 4);
1027 /// assert_eq!(vec, vec![1, 4, 2, 3]);
1028 /// vec.insert(4, 5);
1029 /// assert_eq!(vec, vec![1, 4, 2, 3, 5]);
1031 pub fn insert(&mut self, index: uint, element: T) {
1032 let len = self.len();
1033 assert!(index <= len);
1034 // space for the new element
1035 self.reserve(len + 1);
1037 unsafe { // infallible
1038 // The spot to put the new value
1040 let p = self.as_mut_ptr().offset(index as int);
1041 // Shift everything over to make space. (Duplicating the
1042 // `index`th element into two consecutive places.)
1043 ptr::copy_memory(p.offset(1), &*p, len - index);
1044 // Write it in, overwriting the first copy of the `index`th
1046 ptr::write(&mut *p, element);
1048 self.set_len(len + 1);
1052 /// Remove and return the element at position `index` within the vector,
1053 /// shifting all elements after position `index` one position to the left.
1054 /// Returns `None` if `i` is out of bounds.
1059 /// let mut v = vec![1i, 2, 3];
1060 /// assert_eq!(v.remove(1), Some(2));
1061 /// assert_eq!(v, vec![1, 3]);
1063 /// assert_eq!(v.remove(4), None);
1064 /// // v is unchanged:
1065 /// assert_eq!(v, vec![1, 3]);
1067 pub fn remove(&mut self, index: uint) -> Option<T> {
1068 let len = self.len();
1070 unsafe { // infallible
1073 // the place we are taking from.
1074 let ptr = self.as_mut_ptr().offset(index as int);
1075 // copy it out, unsafely having a copy of the value on
1076 // the stack and in the vector at the same time.
1077 ret = Some(ptr::read(ptr as *const T));
1079 // Shift everything down to fill in that spot.
1080 ptr::copy_memory(ptr, &*ptr.offset(1), len - index - 1);
1082 self.set_len(len - 1);
1090 /// Takes ownership of the vector `other`, moving all elements into
1091 /// the current vector. This does not copy any elements, and it is
1092 /// illegal to use the `other` vector after calling this method
1093 /// (because it is moved here).
1098 /// let mut vec = vec![box 1i];
1099 /// vec.push_all_move(vec![box 2, box 3, box 4]);
1100 /// assert_eq!(vec, vec![box 1, box 2, box 3, box 4]);
1103 pub fn push_all_move(&mut self, other: Vec<T>) {
1104 self.extend(other.move_iter());
1107 /// Returns a mutable slice of `self` between `start` and `end`.
1111 /// Fails when `start` or `end` point outside the bounds of `self`, or when
1112 /// `start` > `end`.
1117 /// let mut vec = vec![1i, 2, 3, 4];
1118 /// assert!(vec.mut_slice(0, 2) == [1, 2]);
1121 pub fn mut_slice<'a>(&'a mut self, start: uint, end: uint)
1123 self.as_mut_slice().mut_slice(start, end)
1126 /// Returns a mutable slice of self from `start` to the end of the vec.
1130 /// Fails when `start` points outside the bounds of self.
1135 /// let mut vec = vec![1i, 2, 3, 4];
1136 /// assert!(vec.mut_slice_from(2) == [3, 4]);
1139 pub fn mut_slice_from<'a>(&'a mut self, start: uint) -> &'a mut [T] {
1140 self.as_mut_slice().mut_slice_from(start)
1143 /// Returns a mutable slice of self from the start of the vec to `end`.
1147 /// Fails when `end` points outside the bounds of self.
1152 /// let mut vec = vec![1i, 2, 3, 4];
1153 /// assert!(vec.mut_slice_to(2) == [1, 2]);
1156 pub fn mut_slice_to<'a>(&'a mut self, end: uint) -> &'a mut [T] {
1157 self.as_mut_slice().mut_slice_to(end)
1160 /// Returns a pair of mutable slices that divides the vec at an index.
1162 /// The first will contain all indices from `[0, mid)` (excluding
1163 /// the index `mid` itself) and the second will contain all
1164 /// indices from `[mid, len)` (excluding the index `len` itself).
1168 /// Fails if `mid > len`.
1173 /// let mut vec = vec![1i, 2, 3, 4, 5, 6];
1175 /// // scoped to restrict the lifetime of the borrows
1177 /// let (left, right) = vec.mut_split_at(0);
1178 /// assert!(left == &mut []);
1179 /// assert!(right == &mut [1, 2, 3, 4, 5, 6]);
1183 /// let (left, right) = vec.mut_split_at(2);
1184 /// assert!(left == &mut [1, 2]);
1185 /// assert!(right == &mut [3, 4, 5, 6]);
1189 /// let (left, right) = vec.mut_split_at(6);
1190 /// assert!(left == &mut [1, 2, 3, 4, 5, 6]);
1191 /// assert!(right == &mut []);
1195 pub fn mut_split_at<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
1196 self.as_mut_slice().mut_split_at(mid)
1199 /// Reverse the order of elements in a vector, in place.
1204 /// let mut v = vec![1i, 2, 3];
1206 /// assert_eq!(v, vec![3i, 2, 1]);
1209 pub fn reverse(&mut self) {
1210 self.as_mut_slice().reverse()
1213 /// Returns a slice of `self` from `start` to the end of the vec.
1217 /// Fails when `start` points outside the bounds of self.
1222 /// let vec = vec![1i, 2, 3];
1223 /// assert!(vec.slice_from(1) == [2, 3]);
1226 pub fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
1227 self.as_slice().slice_from(start)
1230 /// Returns a slice of self from the start of the vec to `end`.
1234 /// Fails when `end` points outside the bounds of self.
1239 /// let vec = vec![1i, 2, 3, 4];
1240 /// assert!(vec.slice_to(2) == [1, 2]);
1243 pub fn slice_to<'a>(&'a self, end: uint) -> &'a [T] {
1244 self.as_slice().slice_to(end)
1247 /// Returns a slice containing all but the last element of the vector.
1251 /// Fails if the vector is empty
1256 /// let vec = vec![1i, 2, 3];
1257 /// assert!(vec.init() == [1, 2]);
1260 pub fn init<'a>(&'a self) -> &'a [T] {
1261 self.slice(0, self.len() - 1)
1265 /// Returns an unsafe pointer to the vector's buffer.
1267 /// The caller must ensure that the vector outlives the pointer this
1268 /// function returns, or else it will end up pointing to garbage.
1270 /// Modifying the vector may cause its buffer to be reallocated, which
1271 /// would also make any pointers to it invalid.
1276 /// let v = vec![1i, 2, 3];
1277 /// let p = v.as_ptr();
1279 /// // Examine each element manually
1280 /// assert_eq!(*p, 1i);
1281 /// assert_eq!(*p.offset(1), 2i);
1282 /// assert_eq!(*p.offset(2), 3i);
1286 pub fn as_ptr(&self) -> *const T {
1287 self.ptr as *const T
1290 /// Returns a mutable unsafe pointer to the vector's buffer.
1292 /// The caller must ensure that the vector outlives the pointer this
1293 /// function returns, or else it will end up pointing to garbage.
1295 /// Modifying the vector may cause its buffer to be reallocated, which
1296 /// would also make any pointers to it invalid.
1303 /// let mut v = vec![1i, 2, 3];
1304 /// let p = v.as_mut_ptr();
1306 /// ptr::write(p, 9i);
1307 /// ptr::write(p.offset(2), 5i);
1309 /// assert_eq!(v, vec![9i, 2, 5]);
1312 pub fn as_mut_ptr(&mut self) -> *mut T {
1316 /// Retains only the elements specified by the predicate.
1318 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1319 /// This method operates in place and preserves the order the retained elements.
1324 /// let mut vec = vec![1i, 2, 3, 4];
1325 /// vec.retain(|x| x%2 == 0);
1326 /// assert_eq!(vec, vec![2, 4]);
1328 pub fn retain(&mut self, f: |&T| -> bool) {
1329 let len = self.len();
1332 let v = self.as_mut_slice();
1334 for i in range(0u, len) {
1343 self.truncate(len - del);
1347 /// Expands a vector in place, initializing the new elements to the result of a function.
1349 /// The vector is grown by `n` elements. The i-th new element are initialized to the value
1350 /// returned by `f(i)` where `i` is in the range [0, n).
1355 /// let mut vec = vec![0u, 1];
1356 /// vec.grow_fn(3, |i| i);
1357 /// assert_eq!(vec, vec![0, 1, 0, 1, 2]);
1359 pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) {
1360 self.reserve_additional(n);
1361 for i in range(0u, n) {
1367 impl<T:Ord> Vec<T> {
1368 /// Sorts the vector in place.
1370 /// This sort is `O(n log n)` worst-case and stable, but allocates
1371 /// approximately `2 * n`, where `n` is the length of `self`.
1376 /// let mut vec = vec![3i, 1, 2];
1378 /// assert_eq!(vec, vec![1, 2, 3]);
1380 pub fn sort(&mut self) {
1381 self.as_mut_slice().sort()
1385 impl<T> Mutable for Vec<T> {
1387 fn clear(&mut self) {
1392 impl<T:PartialEq> Vec<T> {
1393 /// Return true if a vector contains an element with the given value
1398 /// let vec = vec![1i, 2, 3];
1399 /// assert!(vec.contains(&1));
1402 pub fn contains(&self, x: &T) -> bool {
1403 self.as_slice().contains(x)
1406 /// Remove consecutive repeated elements in the vector.
1408 /// If the vector is sorted, this removes all duplicates.
1413 /// let mut vec = vec![1i, 2, 2, 3, 2];
1415 /// assert_eq!(vec, vec![1i, 2, 3, 2]);
1417 pub fn dedup(&mut self) {
1419 // Although we have a mutable reference to `self`, we cannot make
1420 // *arbitrary* changes. The `PartialEq` comparisons could fail, so we
1421 // must ensure that the vector is in a valid state at all time.
1423 // The way that we handle this is by using swaps; we iterate
1424 // over all the elements, swapping as we go so that at the end
1425 // the elements we wish to keep are in the front, and those we
1426 // wish to reject are at the back. We can then truncate the
1427 // vector. This operation is still O(n).
1429 // Example: We start in this state, where `r` represents "next
1430 // read" and `w` represents "next_write`.
1433 // +---+---+---+---+---+---+
1434 // | 0 | 1 | 1 | 2 | 3 | 3 |
1435 // +---+---+---+---+---+---+
1438 // Comparing self[r] against self[w-1], this is not a duplicate, so
1439 // we swap self[r] and self[w] (no effect as r==w) and then increment both
1440 // r and w, leaving us with:
1443 // +---+---+---+---+---+---+
1444 // | 0 | 1 | 1 | 2 | 3 | 3 |
1445 // +---+---+---+---+---+---+
1448 // Comparing self[r] against self[w-1], this value is a duplicate,
1449 // so we increment `r` but leave everything else unchanged:
1452 // +---+---+---+---+---+---+
1453 // | 0 | 1 | 1 | 2 | 3 | 3 |
1454 // +---+---+---+---+---+---+
1457 // Comparing self[r] against self[w-1], this is not a duplicate,
1458 // so swap self[r] and self[w] and advance r and w:
1461 // +---+---+---+---+---+---+
1462 // | 0 | 1 | 2 | 1 | 3 | 3 |
1463 // +---+---+---+---+---+---+
1466 // Not a duplicate, repeat:
1469 // +---+---+---+---+---+---+
1470 // | 0 | 1 | 2 | 3 | 1 | 3 |
1471 // +---+---+---+---+---+---+
1474 // Duplicate, advance r. End of vec. Truncate to w.
1476 let ln = self.len();
1477 if ln < 1 { return; }
1479 // Avoid bounds checks by using unsafe pointers.
1480 let p = self.as_mut_slice().as_mut_ptr();
1485 let p_r = p.offset(r as int);
1486 let p_wm1 = p.offset((w - 1) as int);
1489 let p_w = p_wm1.offset(1);
1490 mem::swap(&mut *p_r, &mut *p_w);
1502 impl<T> Vector<T> for Vec<T> {
1503 /// Work with `self` as a slice.
1508 /// fn foo(slice: &[int]) {}
1510 /// let vec = vec![1i, 2];
1511 /// foo(vec.as_slice());
1514 fn as_slice<'a>(&'a self) -> &'a [T] {
1515 unsafe { mem::transmute(Slice { data: self.as_ptr(), len: self.len }) }
1519 impl<T: Clone, V: Vector<T>> Add<V, Vec<T>> for Vec<T> {
1521 fn add(&self, rhs: &V) -> Vec<T> {
1522 let mut res = Vec::with_capacity(self.len() + rhs.as_slice().len());
1523 res.push_all(self.as_slice());
1524 res.push_all(rhs.as_slice());
1529 #[unsafe_destructor]
1530 impl<T> Drop for Vec<T> {
1531 fn drop(&mut self) {
1532 // This is (and should always remain) a no-op if the fields are
1533 // zeroed (when moving out, because of #[unsafe_no_drop_flag]).
1536 for x in self.as_mut_slice().iter() {
1539 dealloc(self.ptr, self.cap)
1545 impl<T> Default for Vec<T> {
1546 fn default() -> Vec<T> {
1551 impl<T:fmt::Show> fmt::Show for Vec<T> {
1552 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1553 self.as_slice().fmt(f)
1557 impl<T> MutableSeq<T> for Vec<T> {
1558 /// Append an element to a vector.
1562 /// Fails if the number of elements in the vector overflows a `uint`.
1567 /// let mut vec = vec!(1i, 2);
1569 /// assert_eq!(vec, vec!(1, 2, 3));
1572 fn push(&mut self, value: T) {
1573 if mem::size_of::<T>() == 0 {
1574 // zero-size types consume no memory, so we can't rely on the address space running out
1575 self.len = self.len.checked_add(&1).expect("length overflow");
1576 unsafe { mem::forget(value); }
1579 if self.len == self.cap {
1580 let old_size = self.cap * mem::size_of::<T>();
1581 let size = max(old_size, 2 * mem::size_of::<T>()) * 2;
1582 if old_size > size { fail!("capacity overflow") }
1584 self.ptr = alloc_or_realloc(self.ptr, size,
1585 self.cap * mem::size_of::<T>());
1587 self.cap = max(self.cap, 2) * 2;
1591 let end = (self.ptr as *const T).offset(self.len as int) as *mut T;
1592 ptr::write(&mut *end, value);
1597 /// Remove the last element from a vector and return it, or `None` if it is
1603 /// let mut vec = vec!(1i, 2, 3);
1604 /// assert_eq!(vec.pop(), Some(3));
1605 /// assert_eq!(vec, vec!(1, 2));
1608 fn pop(&mut self) -> Option<T> {
1614 Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
1621 /// An iterator that moves out of a vector.
1622 pub struct MoveItems<T> {
1623 allocation: *mut T, // the block of memory allocated for the vector
1624 cap: uint, // the capacity of the vector
1625 iter: Items<'static, T>
1628 impl<T> Iterator<T> for MoveItems<T> {
1630 fn next(&mut self) -> Option<T> {
1632 self.iter.next().map(|x| ptr::read(x))
1637 fn size_hint(&self) -> (uint, Option<uint>) {
1638 self.iter.size_hint()
1642 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
1644 fn next_back(&mut self) -> Option<T> {
1646 self.iter.next_back().map(|x| ptr::read(x))
1651 #[unsafe_destructor]
1652 impl<T> Drop for MoveItems<T> {
1653 fn drop(&mut self) {
1654 // destroy the remaining elements
1658 dealloc(self.allocation, self.cap);
1665 * Convert an iterator of pairs into a pair of vectors.
1667 * Returns a tuple containing two vectors where the i-th element of the first
1668 * vector contains the first element of the i-th tuple of the input iterator,
1669 * and the i-th element of the second vector contains the second element
1670 * of the i-th tuple of the input iterator.
1672 pub fn unzip<T, U, V: Iterator<(T, U)>>(mut iter: V) -> (Vec<T>, Vec<U>) {
1673 let (lo, _) = iter.size_hint();
1674 let mut ts = Vec::with_capacity(lo);
1675 let mut us = Vec::with_capacity(lo);
1676 for (t, u) in iter {
1683 /// Unsafe operations
1688 /// Constructs a vector from an unsafe pointer to a buffer.
1690 /// The elements of the buffer are copied into the vector without cloning,
1691 /// as if `ptr::read()` were called on them.
1693 pub unsafe fn from_buf<T>(ptr: *const T, elts: uint) -> Vec<T> {
1694 let mut dst = Vec::with_capacity(elts);
1696 ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(), ptr, elts);
1705 use std::prelude::*;
1706 use std::mem::size_of;
1708 use super::{unzip, raw, Vec};
1713 fn test_small_vec_struct() {
1714 assert!(size_of::<Vec<u8>>() == size_of::<uint>() * 3);
1718 fn test_double_drop() {
1724 struct DropCounter<'a> {
1728 #[unsafe_destructor]
1729 impl<'a> Drop for DropCounter<'a> {
1730 fn drop(&mut self) {
1735 let mut count_x @ mut count_y = 0;
1737 let mut tv = TwoVec {
1741 tv.x.push(DropCounter {count: &mut count_x});
1742 tv.y.push(DropCounter {count: &mut count_y});
1744 // If Vec had a drop flag, here is where it would be zeroed.
1745 // Instead, it should rely on its internal state to prevent
1746 // doing anything significant when dropped multiple times.
1749 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
1752 assert_eq!(count_x, 1);
1753 assert_eq!(count_y, 1);
1757 fn test_reserve_additional() {
1758 let mut v = Vec::new();
1759 assert_eq!(v.capacity(), 0);
1761 v.reserve_additional(2);
1762 assert!(v.capacity() >= 2);
1764 for i in range(0i, 16) {
1768 assert!(v.capacity() >= 16);
1769 v.reserve_additional(16);
1770 assert!(v.capacity() >= 32);
1774 v.reserve_additional(16);
1775 assert!(v.capacity() >= 33)
1780 let mut v = Vec::new();
1781 let mut w = Vec::new();
1783 v.extend(range(0i, 3));
1784 for i in range(0i, 3) { w.push(i) }
1788 v.extend(range(3i, 10));
1789 for i in range(3i, 10) { w.push(i) }
1795 fn test_mut_slice_from() {
1796 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1798 let slice = values.mut_slice_from(2);
1799 assert!(slice == [3, 4, 5]);
1800 for p in slice.mut_iter() {
1805 assert!(values.as_slice() == [1, 2, 5, 6, 7]);
1809 fn test_mut_slice_to() {
1810 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1812 let slice = values.mut_slice_to(2);
1813 assert!(slice == [1, 2]);
1814 for p in slice.mut_iter() {
1819 assert!(values.as_slice() == [2, 3, 3, 4, 5]);
1823 fn test_mut_split_at() {
1824 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1826 let (left, right) = values.mut_split_at(2);
1827 assert!(left.slice(0, left.len()) == [1, 2]);
1828 for p in left.mut_iter() {
1832 assert!(right.slice(0, right.len()) == [3, 4, 5]);
1833 for p in right.mut_iter() {
1838 assert!(values == Vec::from_slice([2u8, 3, 5, 6, 7]));
1843 let v: Vec<int> = vec!();
1844 let w = vec!(1i, 2, 3);
1846 assert_eq!(v, v.clone());
1850 // they should be disjoint in memory.
1851 assert!(w.as_ptr() != z.as_ptr())
1855 fn test_clone_from() {
1857 let three = vec!(box 1i, box 2, box 3);
1858 let two = vec!(box 4i, box 5);
1860 v.clone_from(&three);
1861 assert_eq!(v, three);
1864 v.clone_from(&three);
1865 assert_eq!(v, three);
1872 v.clone_from(&three);
1873 assert_eq!(v, three)
1878 let mut v = Vec::from_slice([0u, 1]);
1879 v.grow_fn(3, |i| i);
1880 assert!(v == Vec::from_slice([0u, 1, 0, 1, 2]));
1885 let mut vec = Vec::from_slice([1u, 2, 3, 4]);
1886 vec.retain(|x| x%2 == 0);
1887 assert!(vec == Vec::from_slice([2u, 4]));
1891 fn zero_sized_values() {
1892 let mut v = Vec::new();
1893 assert_eq!(v.len(), 0);
1895 assert_eq!(v.len(), 1);
1897 assert_eq!(v.len(), 2);
1898 assert_eq!(v.pop(), Some(()));
1899 assert_eq!(v.pop(), Some(()));
1900 assert_eq!(v.pop(), None);
1902 assert_eq!(v.iter().count(), 0);
1904 assert_eq!(v.iter().count(), 1);
1906 assert_eq!(v.iter().count(), 2);
1908 for &() in v.iter() {}
1910 assert_eq!(v.mut_iter().count(), 2);
1912 assert_eq!(v.mut_iter().count(), 3);
1914 assert_eq!(v.mut_iter().count(), 4);
1916 for &() in v.mut_iter() {}
1917 unsafe { v.set_len(0); }
1918 assert_eq!(v.mut_iter().count(), 0);
1922 fn test_partition() {
1923 assert_eq!(vec![].partition(|x: &int| *x < 3), (vec![], vec![]));
1924 assert_eq!(vec![1i, 2, 3].partition(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1925 assert_eq!(vec![1i, 2, 3].partition(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1926 assert_eq!(vec![1i, 2, 3].partition(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1930 fn test_partitioned() {
1931 assert_eq!(vec![].partitioned(|x: &int| *x < 3), (vec![], vec![]))
1932 assert_eq!(vec![1i, 2, 3].partitioned(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1933 assert_eq!(vec![1i, 2, 3].partitioned(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1934 assert_eq!(vec![1i, 2, 3].partitioned(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1938 fn test_zip_unzip() {
1939 let z1 = vec![(1i, 4i), (2, 5), (3, 6)];
1941 let (left, right) = unzip(z1.iter().map(|&x| x));
1943 let (left, right) = (left.as_slice(), right.as_slice());
1944 assert_eq!((1, 4), (left[0], right[0]));
1945 assert_eq!((2, 5), (left[1], right[1]));
1946 assert_eq!((3, 6), (left[2], right[2]));
1950 fn test_unsafe_ptrs() {
1952 // Test on-stack copy-from-buf.
1954 let ptr = a.as_ptr();
1955 let b = raw::from_buf(ptr, 3u);
1956 assert_eq!(b, vec![1, 2, 3]);
1958 // Test on-heap copy-from-buf.
1959 let c = vec![1i, 2, 3, 4, 5];
1960 let ptr = c.as_ptr();
1961 let d = raw::from_buf(ptr, 5u);
1962 assert_eq!(d, vec![1, 2, 3, 4, 5]);
1967 fn test_vec_truncate_drop() {
1968 static mut drops: uint = 0;
1970 impl Drop for Elem {
1971 fn drop(&mut self) {
1972 unsafe { drops += 1; }
1976 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
1977 assert_eq!(unsafe { drops }, 0);
1979 assert_eq!(unsafe { drops }, 2);
1981 assert_eq!(unsafe { drops }, 5);
1986 fn test_vec_truncate_fail() {
1987 struct BadElem(int);
1988 impl Drop for BadElem {
1989 fn drop(&mut self) {
1990 let BadElem(ref mut x) = *self;
1991 if *x == 0xbadbeef {
1992 fail!("BadElem failure: 0xbadbeef")
1997 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
2003 let vec = vec!(1i, 2, 3);
2004 assert!(vec[1] == 2);
2009 fn test_index_out_of_bounds() {
2010 let vec = vec!(1i, 2, 3);
2015 fn bench_new(b: &mut Bencher) {
2017 let v: Vec<uint> = Vec::new();
2018 assert_eq!(v.len(), 0);
2019 assert_eq!(v.capacity(), 0);
2023 fn do_bench_with_capacity(b: &mut Bencher, src_len: uint) {
2024 b.bytes = src_len as u64;
2027 let v: Vec<uint> = Vec::with_capacity(src_len);
2028 assert_eq!(v.len(), 0);
2029 assert_eq!(v.capacity(), src_len);
2034 fn bench_with_capacity_0000(b: &mut Bencher) {
2035 do_bench_with_capacity(b, 0)
2039 fn bench_with_capacity_0010(b: &mut Bencher) {
2040 do_bench_with_capacity(b, 10)
2044 fn bench_with_capacity_0100(b: &mut Bencher) {
2045 do_bench_with_capacity(b, 100)
2049 fn bench_with_capacity_1000(b: &mut Bencher) {
2050 do_bench_with_capacity(b, 1000)
2053 fn do_bench_from_fn(b: &mut Bencher, src_len: uint) {
2054 b.bytes = src_len as u64;
2057 let dst = Vec::from_fn(src_len, |i| i);
2058 assert_eq!(dst.len(), src_len);
2059 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2064 fn bench_from_fn_0000(b: &mut Bencher) {
2065 do_bench_from_fn(b, 0)
2069 fn bench_from_fn_0010(b: &mut Bencher) {
2070 do_bench_from_fn(b, 10)
2074 fn bench_from_fn_0100(b: &mut Bencher) {
2075 do_bench_from_fn(b, 100)
2079 fn bench_from_fn_1000(b: &mut Bencher) {
2080 do_bench_from_fn(b, 1000)
2083 fn do_bench_from_elem(b: &mut Bencher, src_len: uint) {
2084 b.bytes = src_len as u64;
2087 let dst: Vec<uint> = Vec::from_elem(src_len, 5);
2088 assert_eq!(dst.len(), src_len);
2089 assert!(dst.iter().all(|x| *x == 5));
2094 fn bench_from_elem_0000(b: &mut Bencher) {
2095 do_bench_from_elem(b, 0)
2099 fn bench_from_elem_0010(b: &mut Bencher) {
2100 do_bench_from_elem(b, 10)
2104 fn bench_from_elem_0100(b: &mut Bencher) {
2105 do_bench_from_elem(b, 100)
2109 fn bench_from_elem_1000(b: &mut Bencher) {
2110 do_bench_from_elem(b, 1000)
2113 fn do_bench_from_slice(b: &mut Bencher, src_len: uint) {
2114 let src: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2116 b.bytes = src_len as u64;
2119 let dst = Vec::from_slice(src.clone().as_slice());
2120 assert_eq!(dst.len(), src_len);
2121 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2126 fn bench_from_slice_0000(b: &mut Bencher) {
2127 do_bench_from_slice(b, 0)
2131 fn bench_from_slice_0010(b: &mut Bencher) {
2132 do_bench_from_slice(b, 10)
2136 fn bench_from_slice_0100(b: &mut Bencher) {
2137 do_bench_from_slice(b, 100)
2141 fn bench_from_slice_1000(b: &mut Bencher) {
2142 do_bench_from_slice(b, 1000)
2145 fn do_bench_from_iter(b: &mut Bencher, src_len: uint) {
2146 let src: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2148 b.bytes = src_len as u64;
2151 let dst: Vec<uint> = FromIterator::from_iter(src.clone().move_iter());
2152 assert_eq!(dst.len(), src_len);
2153 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2158 fn bench_from_iter_0000(b: &mut Bencher) {
2159 do_bench_from_iter(b, 0)
2163 fn bench_from_iter_0010(b: &mut Bencher) {
2164 do_bench_from_iter(b, 10)
2168 fn bench_from_iter_0100(b: &mut Bencher) {
2169 do_bench_from_iter(b, 100)
2173 fn bench_from_iter_1000(b: &mut Bencher) {
2174 do_bench_from_iter(b, 1000)
2177 fn do_bench_extend(b: &mut Bencher, dst_len: uint, src_len: uint) {
2178 let dst: Vec<uint> = FromIterator::from_iter(range(0, dst_len));
2179 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2181 b.bytes = src_len as u64;
2184 let mut dst = dst.clone();
2185 dst.extend(src.clone().move_iter());
2186 assert_eq!(dst.len(), dst_len + src_len);
2187 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2192 fn bench_extend_0000_0000(b: &mut Bencher) {
2193 do_bench_extend(b, 0, 0)
2197 fn bench_extend_0000_0010(b: &mut Bencher) {
2198 do_bench_extend(b, 0, 10)
2202 fn bench_extend_0000_0100(b: &mut Bencher) {
2203 do_bench_extend(b, 0, 100)
2207 fn bench_extend_0000_1000(b: &mut Bencher) {
2208 do_bench_extend(b, 0, 1000)
2212 fn bench_extend_0010_0010(b: &mut Bencher) {
2213 do_bench_extend(b, 10, 10)
2217 fn bench_extend_0100_0100(b: &mut Bencher) {
2218 do_bench_extend(b, 100, 100)
2222 fn bench_extend_1000_1000(b: &mut Bencher) {
2223 do_bench_extend(b, 1000, 1000)
2226 fn do_bench_push_all(b: &mut Bencher, dst_len: uint, src_len: uint) {
2227 let dst: Vec<uint> = FromIterator::from_iter(range(0, dst_len));
2228 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2230 b.bytes = src_len as u64;
2233 let mut dst = dst.clone();
2234 dst.push_all(src.as_slice());
2235 assert_eq!(dst.len(), dst_len + src_len);
2236 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2241 fn bench_push_all_0000_0000(b: &mut Bencher) {
2242 do_bench_push_all(b, 0, 0)
2246 fn bench_push_all_0000_0010(b: &mut Bencher) {
2247 do_bench_push_all(b, 0, 10)
2251 fn bench_push_all_0000_0100(b: &mut Bencher) {
2252 do_bench_push_all(b, 0, 100)
2256 fn bench_push_all_0000_1000(b: &mut Bencher) {
2257 do_bench_push_all(b, 0, 1000)
2261 fn bench_push_all_0010_0010(b: &mut Bencher) {
2262 do_bench_push_all(b, 10, 10)
2266 fn bench_push_all_0100_0100(b: &mut Bencher) {
2267 do_bench_push_all(b, 100, 100)
2271 fn bench_push_all_1000_1000(b: &mut Bencher) {
2272 do_bench_push_all(b, 1000, 1000)
2275 fn do_bench_push_all_move(b: &mut Bencher, dst_len: uint, src_len: uint) {
2276 let dst: Vec<uint> = FromIterator::from_iter(range(0u, dst_len));
2277 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2279 b.bytes = src_len as u64;
2282 let mut dst = dst.clone();
2283 dst.push_all_move(src.clone());
2284 assert_eq!(dst.len(), dst_len + src_len);
2285 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2290 fn bench_push_all_move_0000_0000(b: &mut Bencher) {
2291 do_bench_push_all_move(b, 0, 0)
2295 fn bench_push_all_move_0000_0010(b: &mut Bencher) {
2296 do_bench_push_all_move(b, 0, 10)
2300 fn bench_push_all_move_0000_0100(b: &mut Bencher) {
2301 do_bench_push_all_move(b, 0, 100)
2305 fn bench_push_all_move_0000_1000(b: &mut Bencher) {
2306 do_bench_push_all_move(b, 0, 1000)
2310 fn bench_push_all_move_0010_0010(b: &mut Bencher) {
2311 do_bench_push_all_move(b, 10, 10)
2315 fn bench_push_all_move_0100_0100(b: &mut Bencher) {
2316 do_bench_push_all_move(b, 100, 100)
2320 fn bench_push_all_move_1000_1000(b: &mut Bencher) {
2321 do_bench_push_all_move(b, 1000, 1000)
2324 fn do_bench_clone(b: &mut Bencher, src_len: uint) {
2325 let src: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2327 b.bytes = src_len as u64;
2330 let dst = src.clone();
2331 assert_eq!(dst.len(), src_len);
2332 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2337 fn bench_clone_0000(b: &mut Bencher) {
2338 do_bench_clone(b, 0)
2342 fn bench_clone_0010(b: &mut Bencher) {
2343 do_bench_clone(b, 10)
2347 fn bench_clone_0100(b: &mut Bencher) {
2348 do_bench_clone(b, 100)
2352 fn bench_clone_1000(b: &mut Bencher) {
2353 do_bench_clone(b, 1000)
2356 fn do_bench_clone_from(b: &mut Bencher, times: uint, dst_len: uint, src_len: uint) {
2357 let dst: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2358 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2360 b.bytes = (times * src_len) as u64;
2363 let mut dst = dst.clone();
2365 for _ in range(0, times) {
2366 dst.clone_from(&src);
2368 assert_eq!(dst.len(), src_len);
2369 assert!(dst.iter().enumerate().all(|(i, x)| dst_len + i == *x));
2375 fn bench_clone_from_01_0000_0000(b: &mut Bencher) {
2376 do_bench_clone_from(b, 1, 0, 0)
2380 fn bench_clone_from_01_0000_0010(b: &mut Bencher) {
2381 do_bench_clone_from(b, 1, 0, 10)
2385 fn bench_clone_from_01_0000_0100(b: &mut Bencher) {
2386 do_bench_clone_from(b, 1, 0, 100)
2390 fn bench_clone_from_01_0000_1000(b: &mut Bencher) {
2391 do_bench_clone_from(b, 1, 0, 1000)
2395 fn bench_clone_from_01_0010_0010(b: &mut Bencher) {
2396 do_bench_clone_from(b, 1, 10, 10)
2400 fn bench_clone_from_01_0100_0100(b: &mut Bencher) {
2401 do_bench_clone_from(b, 1, 100, 100)
2405 fn bench_clone_from_01_1000_1000(b: &mut Bencher) {
2406 do_bench_clone_from(b, 1, 1000, 1000)
2410 fn bench_clone_from_01_0010_0100(b: &mut Bencher) {
2411 do_bench_clone_from(b, 1, 10, 100)
2415 fn bench_clone_from_01_0100_1000(b: &mut Bencher) {
2416 do_bench_clone_from(b, 1, 100, 1000)
2420 fn bench_clone_from_01_0010_0000(b: &mut Bencher) {
2421 do_bench_clone_from(b, 1, 10, 0)
2425 fn bench_clone_from_01_0100_0010(b: &mut Bencher) {
2426 do_bench_clone_from(b, 1, 100, 10)
2430 fn bench_clone_from_01_1000_0100(b: &mut Bencher) {
2431 do_bench_clone_from(b, 1, 1000, 100)
2435 fn bench_clone_from_10_0000_0000(b: &mut Bencher) {
2436 do_bench_clone_from(b, 10, 0, 0)
2440 fn bench_clone_from_10_0000_0010(b: &mut Bencher) {
2441 do_bench_clone_from(b, 10, 0, 10)
2445 fn bench_clone_from_10_0000_0100(b: &mut Bencher) {
2446 do_bench_clone_from(b, 10, 0, 100)
2450 fn bench_clone_from_10_0000_1000(b: &mut Bencher) {
2451 do_bench_clone_from(b, 10, 0, 1000)
2455 fn bench_clone_from_10_0010_0010(b: &mut Bencher) {
2456 do_bench_clone_from(b, 10, 10, 10)
2460 fn bench_clone_from_10_0100_0100(b: &mut Bencher) {
2461 do_bench_clone_from(b, 10, 100, 100)
2465 fn bench_clone_from_10_1000_1000(b: &mut Bencher) {
2466 do_bench_clone_from(b, 10, 1000, 1000)
2470 fn bench_clone_from_10_0010_0100(b: &mut Bencher) {
2471 do_bench_clone_from(b, 10, 10, 100)
2475 fn bench_clone_from_10_0100_1000(b: &mut Bencher) {
2476 do_bench_clone_from(b, 10, 100, 1000)
2480 fn bench_clone_from_10_0010_0000(b: &mut Bencher) {
2481 do_bench_clone_from(b, 10, 10, 0)
2485 fn bench_clone_from_10_0100_0010(b: &mut Bencher) {
2486 do_bench_clone_from(b, 10, 100, 10)
2490 fn bench_clone_from_10_1000_0100(b: &mut Bencher) {
2491 do_bench_clone_from(b, 10, 1000, 100)