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 #[allow(deprecated)] // allow use of get
457 fn index<'a>(&'a self, index: &uint) -> &'a T {
462 // FIXME(#12825) Indexing will always try IndexMut first and that causes issues.
463 /*impl<T> IndexMut<uint,T> for Vec<T> {
465 fn index_mut<'a>(&'a mut self, index: &uint) -> &'a mut T {
470 impl<T> FromIterator<T> for Vec<T> {
472 fn from_iter<I:Iterator<T>>(mut iterator: I) -> Vec<T> {
473 let (lower, _) = iterator.size_hint();
474 let mut vector = Vec::with_capacity(lower);
475 for element in iterator {
482 impl<T> Extendable<T> for Vec<T> {
484 fn extend<I: Iterator<T>>(&mut self, mut iterator: I) {
485 let (lower, _) = iterator.size_hint();
486 self.reserve_additional(lower);
487 for element in iterator {
493 impl<T: PartialEq> PartialEq for Vec<T> {
495 fn eq(&self, other: &Vec<T>) -> bool {
496 self.as_slice() == other.as_slice()
500 impl<T: PartialOrd> PartialOrd for Vec<T> {
502 fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
503 self.as_slice().partial_cmp(&other.as_slice())
507 impl<T: Eq> Eq for Vec<T> {}
509 impl<T: PartialEq, V: Vector<T>> Equiv<V> for Vec<T> {
511 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
514 impl<T: Ord> Ord for Vec<T> {
516 fn cmp(&self, other: &Vec<T>) -> Ordering {
517 self.as_slice().cmp(&other.as_slice())
521 impl<T> Collection for Vec<T> {
523 fn len(&self) -> uint {
528 impl<T: Clone> CloneableVector<T> for Vec<T> {
529 fn to_vec(&self) -> Vec<T> { self.clone() }
530 fn into_vec(self) -> Vec<T> { self }
533 // FIXME: #13996: need a way to mark the return value as `noalias`
535 unsafe fn alloc_or_realloc<T>(ptr: *mut T, size: uint, old_size: uint) -> *mut T {
537 allocate(size, mem::min_align_of::<T>()) as *mut T
539 reallocate(ptr as *mut u8, size,
540 mem::min_align_of::<T>(), old_size) as *mut T
545 unsafe fn dealloc<T>(ptr: *mut T, len: uint) {
546 if mem::size_of::<T>() != 0 {
547 deallocate(ptr as *mut u8,
548 len * mem::size_of::<T>(),
549 mem::min_align_of::<T>())
554 /// Returns the number of elements the vector can hold without
560 /// let vec: Vec<int> = Vec::with_capacity(10);
561 /// assert_eq!(vec.capacity(), 10);
564 pub fn capacity(&self) -> uint {
568 /// Reserves capacity for at least `n` additional elements in the given
573 /// Fails if the new capacity overflows `uint`.
578 /// let mut vec: Vec<int> = vec![1i];
579 /// vec.reserve_additional(10);
580 /// assert!(vec.capacity() >= 11);
582 pub fn reserve_additional(&mut self, extra: uint) {
583 if self.cap - self.len < extra {
584 match self.len.checked_add(&extra) {
585 None => fail!("Vec::reserve_additional: `uint` overflow"),
586 Some(new_cap) => self.reserve(new_cap)
591 /// Reserves capacity for at least `n` elements in the given vector.
593 /// This function will over-allocate in order to amortize the allocation
594 /// costs in scenarios where the caller may need to repeatedly reserve
595 /// additional space.
597 /// If the capacity for `self` is already equal to or greater than the
598 /// requested capacity, then no action is taken.
603 /// let mut vec = vec![1i, 2, 3];
605 /// assert!(vec.capacity() >= 10);
607 pub fn reserve(&mut self, capacity: uint) {
608 if capacity > self.cap {
609 self.reserve_exact(num::next_power_of_two(capacity))
613 /// Reserves capacity for exactly `capacity` elements in the given vector.
615 /// If the capacity for `self` is already equal to or greater than the
616 /// requested capacity, then no action is taken.
621 /// let mut vec: Vec<int> = Vec::with_capacity(10);
622 /// vec.reserve_exact(11);
623 /// assert_eq!(vec.capacity(), 11);
625 pub fn reserve_exact(&mut self, capacity: uint) {
626 if mem::size_of::<T>() == 0 { return }
628 if capacity > self.cap {
629 let size = capacity.checked_mul(&mem::size_of::<T>())
630 .expect("capacity overflow");
632 self.ptr = alloc_or_realloc(self.ptr, size,
633 self.cap * mem::size_of::<T>());
639 /// Shrink the capacity of the vector as much as possible
644 /// let mut vec = vec![1i, 2, 3];
645 /// vec.shrink_to_fit();
647 pub fn shrink_to_fit(&mut self) {
648 if mem::size_of::<T>() == 0 { return }
653 dealloc(self.ptr, self.cap)
659 // Overflow check is unnecessary as the vector is already at
661 self.ptr = reallocate(self.ptr as *mut u8,
662 self.len * mem::size_of::<T>(),
663 mem::min_align_of::<T>(),
664 self.cap * mem::size_of::<T>()) as *mut T;
670 /// Appends one element to the vector provided. The vector itself is then
671 /// returned for use again.
676 /// let vec = vec![1i, 2];
677 /// let vec = vec.append_one(3);
678 /// assert_eq!(vec, vec![1, 2, 3]);
681 pub fn append_one(mut self, x: T) -> Vec<T> {
686 /// Shorten a vector, dropping excess elements.
688 /// If `len` is greater than the vector's current length, this has no
694 /// let mut vec = vec![1i, 2, 3, 4];
696 /// assert_eq!(vec, vec![1, 2]);
698 pub fn truncate(&mut self, len: uint) {
700 // drop any extra elements
701 while len < self.len {
702 // decrement len before the read(), so a failure on Drop doesn't
703 // re-drop the just-failed value.
705 ptr::read(self.as_slice().unsafe_ref(self.len));
710 /// Work with `self` as a mutable slice.
715 /// fn foo(slice: &mut [int]) {}
717 /// let mut vec = vec![1i, 2];
718 /// foo(vec.as_mut_slice());
721 pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
723 mem::transmute(Slice {
724 data: self.as_mut_ptr() as *const T,
730 /// Creates a consuming iterator, that is, one that moves each
731 /// value out of the vector (from start to end). The vector cannot
732 /// be used after calling this.
737 /// let v = vec!["a".to_string(), "b".to_string()];
738 /// for s in v.move_iter() {
739 /// // s has type String, not &String
740 /// println!("{}", s);
744 pub fn move_iter(self) -> MoveItems<T> {
746 let iter = mem::transmute(self.as_slice().iter());
750 MoveItems { allocation: ptr, cap: cap, iter: iter }
755 /// Sets the length of a vector.
757 /// This will explicitly set the size of the vector, without actually
758 /// modifying its buffers, so it is up to the caller to ensure that the
759 /// vector is actually the specified size.
764 /// let mut v = vec![1u, 2, 3, 4];
770 pub unsafe fn set_len(&mut self, len: uint) {
774 /// Returns a reference to the value at index `index`.
778 /// Fails if `index` is out of bounds
783 /// #![allow(deprecated)]
785 /// let vec = vec![1i, 2, 3];
786 /// assert!(vec.get(1) == &2);
788 #[deprecated="prefer using indexing, e.g., vec[0]"]
790 pub fn get<'a>(&'a self, index: uint) -> &'a T {
791 &self.as_slice()[index]
794 /// Returns a mutable reference to the value at index `index`.
798 /// Fails if `index` is out of bounds
803 /// let mut vec = vec![1i, 2, 3];
804 /// *vec.get_mut(1) = 4;
805 /// assert_eq!(vec, vec![1i, 4, 3]);
808 pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
809 &mut self.as_mut_slice()[index]
812 /// Returns an iterator over references to the elements of the vector in
818 /// let vec = vec![1i, 2, 3];
819 /// for num in vec.iter() {
820 /// println!("{}", *num);
824 pub fn iter<'a>(&'a self) -> Items<'a,T> {
825 self.as_slice().iter()
829 /// Returns an iterator over mutable references to the elements of the
835 /// let mut vec = vec![1i, 2, 3];
836 /// for num in vec.mut_iter() {
841 pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a,T> {
842 self.as_mut_slice().mut_iter()
845 /// Sort the vector, in place, using `compare` to compare elements.
847 /// This sort is `O(n log n)` worst-case and stable, but allocates
848 /// approximately `2 * n`, where `n` is the length of `self`.
853 /// let mut v = vec![5i, 4, 1, 3, 2];
854 /// v.sort_by(|a, b| a.cmp(b));
855 /// assert_eq!(v, vec![1i, 2, 3, 4, 5]);
857 /// // reverse sorting
858 /// v.sort_by(|a, b| b.cmp(a));
859 /// assert_eq!(v, vec![5i, 4, 3, 2, 1]);
862 pub fn sort_by(&mut self, compare: |&T, &T| -> Ordering) {
863 self.as_mut_slice().sort_by(compare)
866 /// Returns a slice of self spanning the interval [`start`, `end`).
870 /// Fails when the slice (or part of it) is outside the bounds of self, or when
876 /// let vec = vec![1i, 2, 3, 4];
877 /// assert!(vec.slice(0, 2) == [1, 2]);
880 pub fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
881 self.as_slice().slice(start, end)
884 /// Returns a slice containing all but the first element of the vector.
888 /// Fails when the vector is empty.
893 /// let vec = vec![1i, 2, 3];
894 /// assert!(vec.tail() == [2, 3]);
897 pub fn tail<'a>(&'a self) -> &'a [T] {
898 self.as_slice().tail()
901 /// Returns all but the first `n' elements of a vector.
905 /// Fails when there are fewer than `n` elements in the vector.
910 /// let vec = vec![1i, 2, 3, 4];
911 /// assert!(vec.tailn(2) == [3, 4]);
914 pub fn tailn<'a>(&'a self, n: uint) -> &'a [T] {
915 self.as_slice().tailn(n)
918 /// Returns a reference to the last element of a vector, or `None` if it is
924 /// let vec = vec![1i, 2, 3];
925 /// assert!(vec.last() == Some(&3));
928 pub fn last<'a>(&'a self) -> Option<&'a T> {
929 self.as_slice().last()
932 /// Returns a mutable reference to the last element of a vector, or `None`
938 /// let mut vec = vec![1i, 2, 3];
939 /// *vec.mut_last().unwrap() = 4;
940 /// assert_eq!(vec, vec![1i, 2, 4]);
943 pub fn mut_last<'a>(&'a mut self) -> Option<&'a mut T> {
944 self.as_mut_slice().mut_last()
947 /// Remove an element from anywhere in the vector and return it, replacing
948 /// it with the last element. This does not preserve ordering, but is O(1).
950 /// Returns `None` if `index` is out of bounds.
954 /// let mut v = vec!["foo".to_string(), "bar".to_string(),
955 /// "baz".to_string(), "qux".to_string()];
957 /// assert_eq!(v.swap_remove(1), Some("bar".to_string()));
958 /// assert_eq!(v, vec!["foo".to_string(), "qux".to_string(), "baz".to_string()]);
960 /// assert_eq!(v.swap_remove(0), Some("foo".to_string()));
961 /// assert_eq!(v, vec!["baz".to_string(), "qux".to_string()]);
963 /// assert_eq!(v.swap_remove(2), None);
966 pub fn swap_remove(&mut self, index: uint) -> Option<T> {
967 let length = self.len();
968 if length > 0 && index < length - 1 {
969 self.as_mut_slice().swap(index, length - 1);
970 } else if index >= length {
976 /// Prepend an element to the vector.
980 /// This is an O(n) operation as it requires copying every element in the
986 /// let mut vec = vec![1i, 2, 3];
988 /// assert_eq!(vec, vec![4, 1, 2, 3]);
991 #[deprecated = "use insert(0, ...)"]
992 pub fn unshift(&mut self, element: T) {
993 self.insert(0, element)
996 /// Removes the first element from a vector and returns it, or `None` if
997 /// the vector is empty.
1001 /// This is an O(n) operation as it requires copying every element in the
1007 /// let mut vec = vec![1i, 2, 3];
1008 /// assert!(vec.shift() == Some(1));
1009 /// assert_eq!(vec, vec![2, 3]);
1012 #[deprecated = "use remove(0)"]
1013 pub fn shift(&mut self) -> Option<T> {
1017 /// Insert an element at position `index` within the vector, shifting all
1018 /// elements after position i one position to the right.
1022 /// Fails if `index` is not between `0` and the vector's length (both
1023 /// bounds inclusive).
1028 /// let mut vec = vec![1i, 2, 3];
1029 /// vec.insert(1, 4);
1030 /// assert_eq!(vec, vec![1, 4, 2, 3]);
1031 /// vec.insert(4, 5);
1032 /// assert_eq!(vec, vec![1, 4, 2, 3, 5]);
1034 pub fn insert(&mut self, index: uint, element: T) {
1035 let len = self.len();
1036 assert!(index <= len);
1037 // space for the new element
1038 self.reserve(len + 1);
1040 unsafe { // infallible
1041 // The spot to put the new value
1043 let p = self.as_mut_ptr().offset(index as int);
1044 // Shift everything over to make space. (Duplicating the
1045 // `index`th element into two consecutive places.)
1046 ptr::copy_memory(p.offset(1), &*p, len - index);
1047 // Write it in, overwriting the first copy of the `index`th
1049 ptr::write(&mut *p, element);
1051 self.set_len(len + 1);
1055 /// Remove and return the element at position `index` within the vector,
1056 /// shifting all elements after position `index` one position to the left.
1057 /// Returns `None` if `i` is out of bounds.
1062 /// let mut v = vec![1i, 2, 3];
1063 /// assert_eq!(v.remove(1), Some(2));
1064 /// assert_eq!(v, vec![1, 3]);
1066 /// assert_eq!(v.remove(4), None);
1067 /// // v is unchanged:
1068 /// assert_eq!(v, vec![1, 3]);
1070 pub fn remove(&mut self, index: uint) -> Option<T> {
1071 let len = self.len();
1073 unsafe { // infallible
1076 // the place we are taking from.
1077 let ptr = self.as_mut_ptr().offset(index as int);
1078 // copy it out, unsafely having a copy of the value on
1079 // the stack and in the vector at the same time.
1080 ret = Some(ptr::read(ptr as *const T));
1082 // Shift everything down to fill in that spot.
1083 ptr::copy_memory(ptr, &*ptr.offset(1), len - index - 1);
1085 self.set_len(len - 1);
1093 /// Takes ownership of the vector `other`, moving all elements into
1094 /// the current vector. This does not copy any elements, and it is
1095 /// illegal to use the `other` vector after calling this method
1096 /// (because it is moved here).
1101 /// let mut vec = vec![box 1i];
1102 /// vec.push_all_move(vec![box 2, box 3, box 4]);
1103 /// assert_eq!(vec, vec![box 1, box 2, box 3, box 4]);
1106 pub fn push_all_move(&mut self, other: Vec<T>) {
1107 self.extend(other.move_iter());
1110 /// Returns a mutable slice of `self` between `start` and `end`.
1114 /// Fails when `start` or `end` point outside the bounds of `self`, or when
1115 /// `start` > `end`.
1120 /// let mut vec = vec![1i, 2, 3, 4];
1121 /// assert!(vec.mut_slice(0, 2) == [1, 2]);
1124 pub fn mut_slice<'a>(&'a mut self, start: uint, end: uint)
1126 self.as_mut_slice().mut_slice(start, end)
1129 /// Returns a mutable slice of self from `start` to the end of the vec.
1133 /// Fails when `start` points outside the bounds of self.
1138 /// let mut vec = vec![1i, 2, 3, 4];
1139 /// assert!(vec.mut_slice_from(2) == [3, 4]);
1142 pub fn mut_slice_from<'a>(&'a mut self, start: uint) -> &'a mut [T] {
1143 self.as_mut_slice().mut_slice_from(start)
1146 /// Returns a mutable slice of self from the start of the vec to `end`.
1150 /// Fails when `end` points outside the bounds of self.
1155 /// let mut vec = vec![1i, 2, 3, 4];
1156 /// assert!(vec.mut_slice_to(2) == [1, 2]);
1159 pub fn mut_slice_to<'a>(&'a mut self, end: uint) -> &'a mut [T] {
1160 self.as_mut_slice().mut_slice_to(end)
1163 /// Returns a pair of mutable slices that divides the vec at an index.
1165 /// The first will contain all indices from `[0, mid)` (excluding
1166 /// the index `mid` itself) and the second will contain all
1167 /// indices from `[mid, len)` (excluding the index `len` itself).
1171 /// Fails if `mid > len`.
1176 /// let mut vec = vec![1i, 2, 3, 4, 5, 6];
1178 /// // scoped to restrict the lifetime of the borrows
1180 /// let (left, right) = vec.mut_split_at(0);
1181 /// assert!(left == &mut []);
1182 /// assert!(right == &mut [1, 2, 3, 4, 5, 6]);
1186 /// let (left, right) = vec.mut_split_at(2);
1187 /// assert!(left == &mut [1, 2]);
1188 /// assert!(right == &mut [3, 4, 5, 6]);
1192 /// let (left, right) = vec.mut_split_at(6);
1193 /// assert!(left == &mut [1, 2, 3, 4, 5, 6]);
1194 /// assert!(right == &mut []);
1198 pub fn mut_split_at<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
1199 self.as_mut_slice().mut_split_at(mid)
1202 /// Reverse the order of elements in a vector, in place.
1207 /// let mut v = vec![1i, 2, 3];
1209 /// assert_eq!(v, vec![3i, 2, 1]);
1212 pub fn reverse(&mut self) {
1213 self.as_mut_slice().reverse()
1216 /// Returns a slice of `self` from `start` to the end of the vec.
1220 /// Fails when `start` points outside the bounds of self.
1225 /// let vec = vec![1i, 2, 3];
1226 /// assert!(vec.slice_from(1) == [2, 3]);
1229 pub fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
1230 self.as_slice().slice_from(start)
1233 /// Returns a slice of self from the start of the vec to `end`.
1237 /// Fails when `end` points outside the bounds of self.
1242 /// let vec = vec![1i, 2, 3, 4];
1243 /// assert!(vec.slice_to(2) == [1, 2]);
1246 pub fn slice_to<'a>(&'a self, end: uint) -> &'a [T] {
1247 self.as_slice().slice_to(end)
1250 /// Returns a slice containing all but the last element of the vector.
1254 /// Fails if the vector is empty
1259 /// let vec = vec![1i, 2, 3];
1260 /// assert!(vec.init() == [1, 2]);
1263 pub fn init<'a>(&'a self) -> &'a [T] {
1264 self.slice(0, self.len() - 1)
1268 /// Returns an unsafe pointer to the vector's buffer.
1270 /// The caller must ensure that the vector outlives the pointer this
1271 /// function returns, or else it will end up pointing to garbage.
1273 /// Modifying the vector may cause its buffer to be reallocated, which
1274 /// would also make any pointers to it invalid.
1279 /// let v = vec![1i, 2, 3];
1280 /// let p = v.as_ptr();
1282 /// // Examine each element manually
1283 /// assert_eq!(*p, 1i);
1284 /// assert_eq!(*p.offset(1), 2i);
1285 /// assert_eq!(*p.offset(2), 3i);
1289 pub fn as_ptr(&self) -> *const T {
1290 self.ptr as *const T
1293 /// Returns a mutable unsafe pointer to the vector's buffer.
1295 /// The caller must ensure that the vector outlives the pointer this
1296 /// function returns, or else it will end up pointing to garbage.
1298 /// Modifying the vector may cause its buffer to be reallocated, which
1299 /// would also make any pointers to it invalid.
1306 /// let mut v = vec![1i, 2, 3];
1307 /// let p = v.as_mut_ptr();
1309 /// ptr::write(p, 9i);
1310 /// ptr::write(p.offset(2), 5i);
1312 /// assert_eq!(v, vec![9i, 2, 5]);
1315 pub fn as_mut_ptr(&mut self) -> *mut T {
1319 /// Retains only the elements specified by the predicate.
1321 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1322 /// This method operates in place and preserves the order of the retained elements.
1327 /// let mut vec = vec![1i, 2, 3, 4];
1328 /// vec.retain(|x| x%2 == 0);
1329 /// assert_eq!(vec, vec![2, 4]);
1331 pub fn retain(&mut self, f: |&T| -> bool) {
1332 let len = self.len();
1335 let v = self.as_mut_slice();
1337 for i in range(0u, len) {
1346 self.truncate(len - del);
1350 /// Expands a vector in place, initializing the new elements to the result of a function.
1352 /// The vector is grown by `n` elements. The i-th new element are initialized to the value
1353 /// returned by `f(i)` where `i` is in the range [0, n).
1358 /// let mut vec = vec![0u, 1];
1359 /// vec.grow_fn(3, |i| i);
1360 /// assert_eq!(vec, vec![0, 1, 0, 1, 2]);
1362 pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) {
1363 self.reserve_additional(n);
1364 for i in range(0u, n) {
1370 impl<T:Ord> Vec<T> {
1371 /// Sorts the vector in place.
1373 /// This sort is `O(n log n)` worst-case and stable, but allocates
1374 /// approximately `2 * n`, where `n` is the length of `self`.
1379 /// let mut vec = vec![3i, 1, 2];
1381 /// assert_eq!(vec, vec![1, 2, 3]);
1383 pub fn sort(&mut self) {
1384 self.as_mut_slice().sort()
1388 impl<T> Mutable for Vec<T> {
1390 fn clear(&mut self) {
1395 impl<T:PartialEq> Vec<T> {
1396 /// Return true if a vector contains an element with the given value
1401 /// let vec = vec![1i, 2, 3];
1402 /// assert!(vec.contains(&1));
1405 pub fn contains(&self, x: &T) -> bool {
1406 self.as_slice().contains(x)
1409 /// Remove consecutive repeated elements in the vector.
1411 /// If the vector is sorted, this removes all duplicates.
1416 /// let mut vec = vec![1i, 2, 2, 3, 2];
1418 /// assert_eq!(vec, vec![1i, 2, 3, 2]);
1420 pub fn dedup(&mut self) {
1422 // Although we have a mutable reference to `self`, we cannot make
1423 // *arbitrary* changes. The `PartialEq` comparisons could fail, so we
1424 // must ensure that the vector is in a valid state at all time.
1426 // The way that we handle this is by using swaps; we iterate
1427 // over all the elements, swapping as we go so that at the end
1428 // the elements we wish to keep are in the front, and those we
1429 // wish to reject are at the back. We can then truncate the
1430 // vector. This operation is still O(n).
1432 // Example: We start in this state, where `r` represents "next
1433 // read" and `w` represents "next_write`.
1436 // +---+---+---+---+---+---+
1437 // | 0 | 1 | 1 | 2 | 3 | 3 |
1438 // +---+---+---+---+---+---+
1441 // Comparing self[r] against self[w-1], this is not a duplicate, so
1442 // we swap self[r] and self[w] (no effect as r==w) and then increment both
1443 // r and w, leaving us with:
1446 // +---+---+---+---+---+---+
1447 // | 0 | 1 | 1 | 2 | 3 | 3 |
1448 // +---+---+---+---+---+---+
1451 // Comparing self[r] against self[w-1], this value is a duplicate,
1452 // so we increment `r` but leave everything else unchanged:
1455 // +---+---+---+---+---+---+
1456 // | 0 | 1 | 1 | 2 | 3 | 3 |
1457 // +---+---+---+---+---+---+
1460 // Comparing self[r] against self[w-1], this is not a duplicate,
1461 // so swap self[r] and self[w] and advance r and w:
1464 // +---+---+---+---+---+---+
1465 // | 0 | 1 | 2 | 1 | 3 | 3 |
1466 // +---+---+---+---+---+---+
1469 // Not a duplicate, repeat:
1472 // +---+---+---+---+---+---+
1473 // | 0 | 1 | 2 | 3 | 1 | 3 |
1474 // +---+---+---+---+---+---+
1477 // Duplicate, advance r. End of vec. Truncate to w.
1479 let ln = self.len();
1480 if ln < 1 { return; }
1482 // Avoid bounds checks by using unsafe pointers.
1483 let p = self.as_mut_slice().as_mut_ptr();
1488 let p_r = p.offset(r as int);
1489 let p_wm1 = p.offset((w - 1) as int);
1492 let p_w = p_wm1.offset(1);
1493 mem::swap(&mut *p_r, &mut *p_w);
1505 impl<T> Vector<T> for Vec<T> {
1506 /// Work with `self` as a slice.
1511 /// fn foo(slice: &[int]) {}
1513 /// let vec = vec![1i, 2];
1514 /// foo(vec.as_slice());
1517 fn as_slice<'a>(&'a self) -> &'a [T] {
1518 unsafe { mem::transmute(Slice { data: self.as_ptr(), len: self.len }) }
1522 impl<T: Clone, V: Vector<T>> Add<V, Vec<T>> for Vec<T> {
1524 fn add(&self, rhs: &V) -> Vec<T> {
1525 let mut res = Vec::with_capacity(self.len() + rhs.as_slice().len());
1526 res.push_all(self.as_slice());
1527 res.push_all(rhs.as_slice());
1532 #[unsafe_destructor]
1533 impl<T> Drop for Vec<T> {
1534 fn drop(&mut self) {
1535 // This is (and should always remain) a no-op if the fields are
1536 // zeroed (when moving out, because of #[unsafe_no_drop_flag]).
1539 for x in self.as_mut_slice().iter() {
1542 dealloc(self.ptr, self.cap)
1548 impl<T> Default for Vec<T> {
1549 fn default() -> Vec<T> {
1554 impl<T:fmt::Show> fmt::Show for Vec<T> {
1555 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1556 self.as_slice().fmt(f)
1560 impl<T> MutableSeq<T> for Vec<T> {
1561 /// Append an element to the back of a collection.
1565 /// Fails if the number of elements in the vector overflows a `uint`.
1570 /// let mut vec = vec!(1i, 2);
1572 /// assert_eq!(vec, vec!(1, 2, 3));
1575 fn push(&mut self, value: T) {
1576 if mem::size_of::<T>() == 0 {
1577 // zero-size types consume no memory, so we can't rely on the address space running out
1578 self.len = self.len.checked_add(&1).expect("length overflow");
1579 unsafe { mem::forget(value); }
1582 if self.len == self.cap {
1583 let old_size = self.cap * mem::size_of::<T>();
1584 let size = max(old_size, 2 * mem::size_of::<T>()) * 2;
1585 if old_size > size { fail!("capacity overflow") }
1587 self.ptr = alloc_or_realloc(self.ptr, size,
1588 self.cap * mem::size_of::<T>());
1590 self.cap = max(self.cap, 2) * 2;
1594 let end = (self.ptr as *const T).offset(self.len as int) as *mut T;
1595 ptr::write(&mut *end, value);
1601 fn pop(&mut self) -> Option<T> {
1607 Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
1614 /// An iterator that moves out of a vector.
1615 pub struct MoveItems<T> {
1616 allocation: *mut T, // the block of memory allocated for the vector
1617 cap: uint, // the capacity of the vector
1618 iter: Items<'static, T>
1621 impl<T> Iterator<T> for MoveItems<T> {
1623 fn next(&mut self) -> Option<T> {
1625 self.iter.next().map(|x| ptr::read(x))
1630 fn size_hint(&self) -> (uint, Option<uint>) {
1631 self.iter.size_hint()
1635 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
1637 fn next_back(&mut self) -> Option<T> {
1639 self.iter.next_back().map(|x| ptr::read(x))
1644 #[unsafe_destructor]
1645 impl<T> Drop for MoveItems<T> {
1646 fn drop(&mut self) {
1647 // destroy the remaining elements
1651 dealloc(self.allocation, self.cap);
1658 * Convert an iterator of pairs into a pair of vectors.
1660 * Returns a tuple containing two vectors where the i-th element of the first
1661 * vector contains the first element of the i-th tuple of the input iterator,
1662 * and the i-th element of the second vector contains the second element
1663 * of the i-th tuple of the input iterator.
1665 pub fn unzip<T, U, V: Iterator<(T, U)>>(mut iter: V) -> (Vec<T>, Vec<U>) {
1666 let (lo, _) = iter.size_hint();
1667 let mut ts = Vec::with_capacity(lo);
1668 let mut us = Vec::with_capacity(lo);
1669 for (t, u) in iter {
1676 /// Unsafe operations
1681 /// Constructs a vector from an unsafe pointer to a buffer.
1683 /// The elements of the buffer are copied into the vector without cloning,
1684 /// as if `ptr::read()` were called on them.
1686 pub unsafe fn from_buf<T>(ptr: *const T, elts: uint) -> Vec<T> {
1687 let mut dst = Vec::with_capacity(elts);
1689 ptr::copy_nonoverlapping_memory(dst.as_mut_ptr(), ptr, elts);
1698 use std::prelude::*;
1699 use std::mem::size_of;
1701 use super::{unzip, raw, Vec};
1706 fn test_small_vec_struct() {
1707 assert!(size_of::<Vec<u8>>() == size_of::<uint>() * 3);
1711 fn test_double_drop() {
1717 struct DropCounter<'a> {
1721 #[unsafe_destructor]
1722 impl<'a> Drop for DropCounter<'a> {
1723 fn drop(&mut self) {
1728 let (mut count_x, mut count_y) = (0, 0);
1730 let mut tv = TwoVec {
1734 tv.x.push(DropCounter {count: &mut count_x});
1735 tv.y.push(DropCounter {count: &mut count_y});
1737 // If Vec had a drop flag, here is where it would be zeroed.
1738 // Instead, it should rely on its internal state to prevent
1739 // doing anything significant when dropped multiple times.
1742 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
1745 assert_eq!(count_x, 1);
1746 assert_eq!(count_y, 1);
1750 fn test_reserve_additional() {
1751 let mut v = Vec::new();
1752 assert_eq!(v.capacity(), 0);
1754 v.reserve_additional(2);
1755 assert!(v.capacity() >= 2);
1757 for i in range(0i, 16) {
1761 assert!(v.capacity() >= 16);
1762 v.reserve_additional(16);
1763 assert!(v.capacity() >= 32);
1767 v.reserve_additional(16);
1768 assert!(v.capacity() >= 33)
1773 let mut v = Vec::new();
1774 let mut w = Vec::new();
1776 v.extend(range(0i, 3));
1777 for i in range(0i, 3) { w.push(i) }
1781 v.extend(range(3i, 10));
1782 for i in range(3i, 10) { w.push(i) }
1788 fn test_mut_slice_from() {
1789 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1791 let slice = values.mut_slice_from(2);
1792 assert!(slice == [3, 4, 5]);
1793 for p in slice.mut_iter() {
1798 assert!(values.as_slice() == [1, 2, 5, 6, 7]);
1802 fn test_mut_slice_to() {
1803 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1805 let slice = values.mut_slice_to(2);
1806 assert!(slice == [1, 2]);
1807 for p in slice.mut_iter() {
1812 assert!(values.as_slice() == [2, 3, 3, 4, 5]);
1816 fn test_mut_split_at() {
1817 let mut values = Vec::from_slice([1u8,2,3,4,5]);
1819 let (left, right) = values.mut_split_at(2);
1820 assert!(left.slice(0, left.len()) == [1, 2]);
1821 for p in left.mut_iter() {
1825 assert!(right.slice(0, right.len()) == [3, 4, 5]);
1826 for p in right.mut_iter() {
1831 assert!(values == Vec::from_slice([2u8, 3, 5, 6, 7]));
1836 let v: Vec<int> = vec!();
1837 let w = vec!(1i, 2, 3);
1839 assert_eq!(v, v.clone());
1843 // they should be disjoint in memory.
1844 assert!(w.as_ptr() != z.as_ptr())
1848 fn test_clone_from() {
1850 let three = vec!(box 1i, box 2, box 3);
1851 let two = vec!(box 4i, box 5);
1853 v.clone_from(&three);
1854 assert_eq!(v, three);
1857 v.clone_from(&three);
1858 assert_eq!(v, three);
1865 v.clone_from(&three);
1866 assert_eq!(v, three)
1871 let mut v = Vec::from_slice([0u, 1]);
1872 v.grow_fn(3, |i| i);
1873 assert!(v == Vec::from_slice([0u, 1, 0, 1, 2]));
1878 let mut vec = Vec::from_slice([1u, 2, 3, 4]);
1879 vec.retain(|x| x%2 == 0);
1880 assert!(vec == Vec::from_slice([2u, 4]));
1884 fn zero_sized_values() {
1885 let mut v = Vec::new();
1886 assert_eq!(v.len(), 0);
1888 assert_eq!(v.len(), 1);
1890 assert_eq!(v.len(), 2);
1891 assert_eq!(v.pop(), Some(()));
1892 assert_eq!(v.pop(), Some(()));
1893 assert_eq!(v.pop(), None);
1895 assert_eq!(v.iter().count(), 0);
1897 assert_eq!(v.iter().count(), 1);
1899 assert_eq!(v.iter().count(), 2);
1901 for &() in v.iter() {}
1903 assert_eq!(v.mut_iter().count(), 2);
1905 assert_eq!(v.mut_iter().count(), 3);
1907 assert_eq!(v.mut_iter().count(), 4);
1909 for &() in v.mut_iter() {}
1910 unsafe { v.set_len(0); }
1911 assert_eq!(v.mut_iter().count(), 0);
1915 fn test_partition() {
1916 assert_eq!(vec![].partition(|x: &int| *x < 3), (vec![], vec![]));
1917 assert_eq!(vec![1i, 2, 3].partition(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1918 assert_eq!(vec![1i, 2, 3].partition(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1919 assert_eq!(vec![1i, 2, 3].partition(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1923 fn test_partitioned() {
1924 assert_eq!(vec![].partitioned(|x: &int| *x < 3), (vec![], vec![]))
1925 assert_eq!(vec![1i, 2, 3].partitioned(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1926 assert_eq!(vec![1i, 2, 3].partitioned(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1927 assert_eq!(vec![1i, 2, 3].partitioned(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1931 fn test_zip_unzip() {
1932 let z1 = vec![(1i, 4i), (2, 5), (3, 6)];
1934 let (left, right) = unzip(z1.iter().map(|&x| x));
1936 let (left, right) = (left.as_slice(), right.as_slice());
1937 assert_eq!((1, 4), (left[0], right[0]));
1938 assert_eq!((2, 5), (left[1], right[1]));
1939 assert_eq!((3, 6), (left[2], right[2]));
1943 fn test_unsafe_ptrs() {
1945 // Test on-stack copy-from-buf.
1947 let ptr = a.as_ptr();
1948 let b = raw::from_buf(ptr, 3u);
1949 assert_eq!(b, vec![1, 2, 3]);
1951 // Test on-heap copy-from-buf.
1952 let c = vec![1i, 2, 3, 4, 5];
1953 let ptr = c.as_ptr();
1954 let d = raw::from_buf(ptr, 5u);
1955 assert_eq!(d, vec![1, 2, 3, 4, 5]);
1960 fn test_vec_truncate_drop() {
1961 static mut drops: uint = 0;
1963 impl Drop for Elem {
1964 fn drop(&mut self) {
1965 unsafe { drops += 1; }
1969 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
1970 assert_eq!(unsafe { drops }, 0);
1972 assert_eq!(unsafe { drops }, 2);
1974 assert_eq!(unsafe { drops }, 5);
1979 fn test_vec_truncate_fail() {
1980 struct BadElem(int);
1981 impl Drop for BadElem {
1982 fn drop(&mut self) {
1983 let BadElem(ref mut x) = *self;
1984 if *x == 0xbadbeef {
1985 fail!("BadElem failure: 0xbadbeef")
1990 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
1996 let vec = vec!(1i, 2, 3);
1997 assert!(vec[1] == 2);
2002 fn test_index_out_of_bounds() {
2003 let vec = vec!(1i, 2, 3);
2008 fn test_swap_remove_empty() {
2009 let mut vec: Vec<uint> = vec!();
2010 assert_eq!(vec.swap_remove(0), None);
2014 fn bench_new(b: &mut Bencher) {
2016 let v: Vec<uint> = Vec::new();
2017 assert_eq!(v.len(), 0);
2018 assert_eq!(v.capacity(), 0);
2022 fn do_bench_with_capacity(b: &mut Bencher, src_len: uint) {
2023 b.bytes = src_len as u64;
2026 let v: Vec<uint> = Vec::with_capacity(src_len);
2027 assert_eq!(v.len(), 0);
2028 assert_eq!(v.capacity(), src_len);
2033 fn bench_with_capacity_0000(b: &mut Bencher) {
2034 do_bench_with_capacity(b, 0)
2038 fn bench_with_capacity_0010(b: &mut Bencher) {
2039 do_bench_with_capacity(b, 10)
2043 fn bench_with_capacity_0100(b: &mut Bencher) {
2044 do_bench_with_capacity(b, 100)
2048 fn bench_with_capacity_1000(b: &mut Bencher) {
2049 do_bench_with_capacity(b, 1000)
2052 fn do_bench_from_fn(b: &mut Bencher, src_len: uint) {
2053 b.bytes = src_len as u64;
2056 let dst = Vec::from_fn(src_len, |i| i);
2057 assert_eq!(dst.len(), src_len);
2058 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2063 fn bench_from_fn_0000(b: &mut Bencher) {
2064 do_bench_from_fn(b, 0)
2068 fn bench_from_fn_0010(b: &mut Bencher) {
2069 do_bench_from_fn(b, 10)
2073 fn bench_from_fn_0100(b: &mut Bencher) {
2074 do_bench_from_fn(b, 100)
2078 fn bench_from_fn_1000(b: &mut Bencher) {
2079 do_bench_from_fn(b, 1000)
2082 fn do_bench_from_elem(b: &mut Bencher, src_len: uint) {
2083 b.bytes = src_len as u64;
2086 let dst: Vec<uint> = Vec::from_elem(src_len, 5);
2087 assert_eq!(dst.len(), src_len);
2088 assert!(dst.iter().all(|x| *x == 5));
2093 fn bench_from_elem_0000(b: &mut Bencher) {
2094 do_bench_from_elem(b, 0)
2098 fn bench_from_elem_0010(b: &mut Bencher) {
2099 do_bench_from_elem(b, 10)
2103 fn bench_from_elem_0100(b: &mut Bencher) {
2104 do_bench_from_elem(b, 100)
2108 fn bench_from_elem_1000(b: &mut Bencher) {
2109 do_bench_from_elem(b, 1000)
2112 fn do_bench_from_slice(b: &mut Bencher, src_len: uint) {
2113 let src: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2115 b.bytes = src_len as u64;
2118 let dst = Vec::from_slice(src.clone().as_slice());
2119 assert_eq!(dst.len(), src_len);
2120 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2125 fn bench_from_slice_0000(b: &mut Bencher) {
2126 do_bench_from_slice(b, 0)
2130 fn bench_from_slice_0010(b: &mut Bencher) {
2131 do_bench_from_slice(b, 10)
2135 fn bench_from_slice_0100(b: &mut Bencher) {
2136 do_bench_from_slice(b, 100)
2140 fn bench_from_slice_1000(b: &mut Bencher) {
2141 do_bench_from_slice(b, 1000)
2144 fn do_bench_from_iter(b: &mut Bencher, src_len: uint) {
2145 let src: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2147 b.bytes = src_len as u64;
2150 let dst: Vec<uint> = FromIterator::from_iter(src.clone().move_iter());
2151 assert_eq!(dst.len(), src_len);
2152 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2157 fn bench_from_iter_0000(b: &mut Bencher) {
2158 do_bench_from_iter(b, 0)
2162 fn bench_from_iter_0010(b: &mut Bencher) {
2163 do_bench_from_iter(b, 10)
2167 fn bench_from_iter_0100(b: &mut Bencher) {
2168 do_bench_from_iter(b, 100)
2172 fn bench_from_iter_1000(b: &mut Bencher) {
2173 do_bench_from_iter(b, 1000)
2176 fn do_bench_extend(b: &mut Bencher, dst_len: uint, src_len: uint) {
2177 let dst: Vec<uint> = FromIterator::from_iter(range(0, dst_len));
2178 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2180 b.bytes = src_len as u64;
2183 let mut dst = dst.clone();
2184 dst.extend(src.clone().move_iter());
2185 assert_eq!(dst.len(), dst_len + src_len);
2186 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2191 fn bench_extend_0000_0000(b: &mut Bencher) {
2192 do_bench_extend(b, 0, 0)
2196 fn bench_extend_0000_0010(b: &mut Bencher) {
2197 do_bench_extend(b, 0, 10)
2201 fn bench_extend_0000_0100(b: &mut Bencher) {
2202 do_bench_extend(b, 0, 100)
2206 fn bench_extend_0000_1000(b: &mut Bencher) {
2207 do_bench_extend(b, 0, 1000)
2211 fn bench_extend_0010_0010(b: &mut Bencher) {
2212 do_bench_extend(b, 10, 10)
2216 fn bench_extend_0100_0100(b: &mut Bencher) {
2217 do_bench_extend(b, 100, 100)
2221 fn bench_extend_1000_1000(b: &mut Bencher) {
2222 do_bench_extend(b, 1000, 1000)
2225 fn do_bench_push_all(b: &mut Bencher, dst_len: uint, src_len: uint) {
2226 let dst: Vec<uint> = FromIterator::from_iter(range(0, dst_len));
2227 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2229 b.bytes = src_len as u64;
2232 let mut dst = dst.clone();
2233 dst.push_all(src.as_slice());
2234 assert_eq!(dst.len(), dst_len + src_len);
2235 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2240 fn bench_push_all_0000_0000(b: &mut Bencher) {
2241 do_bench_push_all(b, 0, 0)
2245 fn bench_push_all_0000_0010(b: &mut Bencher) {
2246 do_bench_push_all(b, 0, 10)
2250 fn bench_push_all_0000_0100(b: &mut Bencher) {
2251 do_bench_push_all(b, 0, 100)
2255 fn bench_push_all_0000_1000(b: &mut Bencher) {
2256 do_bench_push_all(b, 0, 1000)
2260 fn bench_push_all_0010_0010(b: &mut Bencher) {
2261 do_bench_push_all(b, 10, 10)
2265 fn bench_push_all_0100_0100(b: &mut Bencher) {
2266 do_bench_push_all(b, 100, 100)
2270 fn bench_push_all_1000_1000(b: &mut Bencher) {
2271 do_bench_push_all(b, 1000, 1000)
2274 fn do_bench_push_all_move(b: &mut Bencher, dst_len: uint, src_len: uint) {
2275 let dst: Vec<uint> = FromIterator::from_iter(range(0u, dst_len));
2276 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2278 b.bytes = src_len as u64;
2281 let mut dst = dst.clone();
2282 dst.push_all_move(src.clone());
2283 assert_eq!(dst.len(), dst_len + src_len);
2284 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2289 fn bench_push_all_move_0000_0000(b: &mut Bencher) {
2290 do_bench_push_all_move(b, 0, 0)
2294 fn bench_push_all_move_0000_0010(b: &mut Bencher) {
2295 do_bench_push_all_move(b, 0, 10)
2299 fn bench_push_all_move_0000_0100(b: &mut Bencher) {
2300 do_bench_push_all_move(b, 0, 100)
2304 fn bench_push_all_move_0000_1000(b: &mut Bencher) {
2305 do_bench_push_all_move(b, 0, 1000)
2309 fn bench_push_all_move_0010_0010(b: &mut Bencher) {
2310 do_bench_push_all_move(b, 10, 10)
2314 fn bench_push_all_move_0100_0100(b: &mut Bencher) {
2315 do_bench_push_all_move(b, 100, 100)
2319 fn bench_push_all_move_1000_1000(b: &mut Bencher) {
2320 do_bench_push_all_move(b, 1000, 1000)
2323 fn do_bench_clone(b: &mut Bencher, src_len: uint) {
2324 let src: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2326 b.bytes = src_len as u64;
2329 let dst = src.clone();
2330 assert_eq!(dst.len(), src_len);
2331 assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
2336 fn bench_clone_0000(b: &mut Bencher) {
2337 do_bench_clone(b, 0)
2341 fn bench_clone_0010(b: &mut Bencher) {
2342 do_bench_clone(b, 10)
2346 fn bench_clone_0100(b: &mut Bencher) {
2347 do_bench_clone(b, 100)
2351 fn bench_clone_1000(b: &mut Bencher) {
2352 do_bench_clone(b, 1000)
2355 fn do_bench_clone_from(b: &mut Bencher, times: uint, dst_len: uint, src_len: uint) {
2356 let dst: Vec<uint> = FromIterator::from_iter(range(0, src_len));
2357 let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len));
2359 b.bytes = (times * src_len) as u64;
2362 let mut dst = dst.clone();
2364 for _ in range(0, times) {
2365 dst.clone_from(&src);
2367 assert_eq!(dst.len(), src_len);
2368 assert!(dst.iter().enumerate().all(|(i, x)| dst_len + i == *x));
2374 fn bench_clone_from_01_0000_0000(b: &mut Bencher) {
2375 do_bench_clone_from(b, 1, 0, 0)
2379 fn bench_clone_from_01_0000_0010(b: &mut Bencher) {
2380 do_bench_clone_from(b, 1, 0, 10)
2384 fn bench_clone_from_01_0000_0100(b: &mut Bencher) {
2385 do_bench_clone_from(b, 1, 0, 100)
2389 fn bench_clone_from_01_0000_1000(b: &mut Bencher) {
2390 do_bench_clone_from(b, 1, 0, 1000)
2394 fn bench_clone_from_01_0010_0010(b: &mut Bencher) {
2395 do_bench_clone_from(b, 1, 10, 10)
2399 fn bench_clone_from_01_0100_0100(b: &mut Bencher) {
2400 do_bench_clone_from(b, 1, 100, 100)
2404 fn bench_clone_from_01_1000_1000(b: &mut Bencher) {
2405 do_bench_clone_from(b, 1, 1000, 1000)
2409 fn bench_clone_from_01_0010_0100(b: &mut Bencher) {
2410 do_bench_clone_from(b, 1, 10, 100)
2414 fn bench_clone_from_01_0100_1000(b: &mut Bencher) {
2415 do_bench_clone_from(b, 1, 100, 1000)
2419 fn bench_clone_from_01_0010_0000(b: &mut Bencher) {
2420 do_bench_clone_from(b, 1, 10, 0)
2424 fn bench_clone_from_01_0100_0010(b: &mut Bencher) {
2425 do_bench_clone_from(b, 1, 100, 10)
2429 fn bench_clone_from_01_1000_0100(b: &mut Bencher) {
2430 do_bench_clone_from(b, 1, 1000, 100)
2434 fn bench_clone_from_10_0000_0000(b: &mut Bencher) {
2435 do_bench_clone_from(b, 10, 0, 0)
2439 fn bench_clone_from_10_0000_0010(b: &mut Bencher) {
2440 do_bench_clone_from(b, 10, 0, 10)
2444 fn bench_clone_from_10_0000_0100(b: &mut Bencher) {
2445 do_bench_clone_from(b, 10, 0, 100)
2449 fn bench_clone_from_10_0000_1000(b: &mut Bencher) {
2450 do_bench_clone_from(b, 10, 0, 1000)
2454 fn bench_clone_from_10_0010_0010(b: &mut Bencher) {
2455 do_bench_clone_from(b, 10, 10, 10)
2459 fn bench_clone_from_10_0100_0100(b: &mut Bencher) {
2460 do_bench_clone_from(b, 10, 100, 100)
2464 fn bench_clone_from_10_1000_1000(b: &mut Bencher) {
2465 do_bench_clone_from(b, 10, 1000, 1000)
2469 fn bench_clone_from_10_0010_0100(b: &mut Bencher) {
2470 do_bench_clone_from(b, 10, 10, 100)
2474 fn bench_clone_from_10_0100_1000(b: &mut Bencher) {
2475 do_bench_clone_from(b, 10, 100, 1000)
2479 fn bench_clone_from_10_0010_0000(b: &mut Bencher) {
2480 do_bench_clone_from(b, 10, 10, 0)
2484 fn bench_clone_from_10_0100_0010(b: &mut Bencher) {
2485 do_bench_clone_from(b, 10, 100, 10)
2489 fn bench_clone_from_10_1000_0100(b: &mut Bencher) {
2490 do_bench_clone_from(b, 10, 1000, 100)