src/libstd/vec.rs

   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.
   4 //
   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.
  10
  11 //! An owned, growable vector.
  12
  13 use cast::{forget, transmute};
  14 use clone::Clone;
  15 use cmp::{Ord, Eq, Ordering, TotalEq, TotalOrd};
  16 use container::{Container, Mutable};
  17 use default::Default;
  18 use fmt;
  19 use iter::{DoubleEndedIterator, FromIterator, Extendable, Iterator, range};
  20 use libc::{free, c_void};
  21 use mem::{size_of, move_val_init};
  22 use mem;
  23 use num;
  24 use num::{CheckedMul, CheckedAdd};
  25 use ops::Drop;
  26 use option::{None, Option, Some};
  27 use ptr::RawPtr;
  28 use ptr;
  29 use rt::global_heap::{malloc_raw, realloc_raw};
  30 use raw::Slice;
  31 use slice::{ImmutableEqVector, ImmutableVector, Items, MutItems, MutableVector};
  32 use slice::{MutableTotalOrdVector, OwnedVector, Vector};
  33 use slice::{MutableVectorAllocating};
  34
  35 /// An owned, growable vector.
  36 ///
  37 /// # Examples
  38 ///
  39 /// ```rust
  40 /// # use std::vec::Vec;
  41 /// let mut vec = Vec::new();
  42 /// vec.push(1);
  43 /// vec.push(2);
  44 ///
  45 /// assert_eq!(vec.len(), 2);
  46 /// assert_eq!(vec.get(0), &1);
  47 ///
  48 /// assert_eq!(vec.pop(), Some(2));
  49 /// assert_eq!(vec.len(), 1);
  50 /// ```
  51 ///
  52 /// The `vec!` macro is provided to make initialization more convenient:
  53 ///
  54 /// ```rust
  55 /// let mut vec = vec!(1, 2, 3);
  56 /// vec.push(4);
  57 /// assert_eq!(vec, vec!(1, 2, 3, 4));
  58 /// ```
  59 #[unsafe_no_drop_flag]
  60 pub struct Vec<T> {
  61     len: uint,
  62     cap: uint,
  63     ptr: *mut T
  64 }
  65
  66 impl<T> Vec<T> {
  67     /// Constructs a new, empty `Vec`.
  68     ///
  69     /// The vector will not allocate until elements are pushed onto it.
  70     ///
  71     /// # Example
  72     ///
  73     /// ```rust
  74     /// # use std::vec::Vec;
  75     /// let mut vec: Vec<int> = Vec::new();
  76     /// ```
  77     #[inline]
  78     pub fn new() -> Vec<T> {
  79         Vec { len: 0, cap: 0, ptr: 0 as *mut T }
  80     }
  81
  82     /// Constructs a new, empty `Vec` with the specified capacity.
  83     ///
  84     /// The vector will be able to hold exactly `capacity` elements without
  85     /// reallocating. If `capacity` is 0, the vector will not allocate.
  86     ///
  87     /// # Example
  88     ///
  89     /// ```rust
  90     /// # use std::vec::Vec;
  91     /// let vec: Vec<int> = Vec::with_capacity(10);
  92     /// ```
  93     pub fn with_capacity(capacity: uint) -> Vec<T> {
  94         if capacity == 0 {
  95             Vec::new()
  96         } else {
  97             let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
  98             let ptr = unsafe { malloc_raw(size) };
  99             Vec { len: 0, cap: capacity, ptr: ptr as *mut T }
 100         }
 101     }
 102
 103     /// Creates and initializes a `Vec`.
 104     ///
 105     /// Creates a `Vec` of size `length` and initializes the elements to the
 106     /// value returned by the closure `op`.
 107     ///
 108     /// # Example
 109     ///
 110     /// ```rust
 111     /// # use std::vec::Vec;
 112     /// let vec = Vec::from_fn(3, |idx| idx * 2);
 113     /// assert_eq!(vec, vec!(0, 2, 4));
 114     /// ```
 115     pub fn from_fn(length: uint, op: |uint| -> T) -> Vec<T> {
 116         unsafe {
 117             let mut xs = Vec::with_capacity(length);
 118             while xs.len < length {
 119                 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), op(xs.len));
 120                 xs.len += 1;
 121             }
 122             xs
 123         }
 124     }
 125
 126     /// Create a `Vec<T>` directly from the raw constituents.
 127     ///
 128     /// This is highly unsafe:
 129     ///
 130     /// - if `ptr` is null, then `length` and `capacity` should be 0
 131     /// - `ptr` must point to an allocation of size `capacity`
 132     /// - there must be `length` valid instances of type `T` at the
 133     ///   beginning of that allocation
 134     /// - `ptr` must be allocated by the default `Vec` allocator
 135     pub unsafe fn from_raw_parts(length: uint, capacity: uint, ptr: *mut T) -> Vec<T> {
 136         Vec { len: length, cap: capacity, ptr: ptr }
 137     }
 138
 139     /// Consumes the `Vec`, partitioning it based on a predicate.
 140     ///
 141     /// Partitions the `Vec` into two `Vec`s `(A,B)`, where all elements of `A`
 142     /// satisfy `f` and all elements of `B` do not. The order of elements is
 143     /// preserved.
 144     ///
 145     /// # Example
 146     ///
 147     /// ```rust
 148     /// let vec = vec!(1, 2, 3, 4);
 149     /// let (even, odd) = vec.partition(|&n| n % 2 == 0);
 150     /// assert_eq!(even, vec!(2, 4));
 151     /// assert_eq!(odd, vec!(1, 3));
 152     /// ```
 153     #[inline]
 154     pub fn partition(self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
 155         let mut lefts  = Vec::new();
 156         let mut rights = Vec::new();
 157
 158         for elt in self.move_iter() {
 159             if f(&elt) {
 160                 lefts.push(elt);
 161             } else {
 162                 rights.push(elt);
 163             }
 164         }
 165
 166         (lefts, rights)
 167     }
 168 }
 169
 170 impl<T: Clone> Vec<T> {
 171     /// Iterates over the `second` vector, copying each element and appending it to
 172     /// the `first`. Afterwards, the `first` is then returned for use again.
 173     ///
 174     /// # Example
 175     ///
 176     /// ```rust
 177     /// let vec = vec!(1, 2);
 178     /// let vec = vec.append([3, 4]);
 179     /// assert_eq!(vec, vec!(1, 2, 3, 4));
 180     /// ```
 181     #[inline]
 182     pub fn append(mut self, second: &[T]) -> Vec<T> {
 183         self.push_all(second);
 184         self
 185     }
 186
 187     /// Constructs a `Vec` by cloning elements of a slice.
 188     ///
 189     /// # Example
 190     ///
 191     /// ```rust
 192     /// # use std::vec::Vec;
 193     /// let slice = [1, 2, 3];
 194     /// let vec = Vec::from_slice(slice);
 195     /// ```
 196     pub fn from_slice(values: &[T]) -> Vec<T> {
 197         values.iter().map(|x| x.clone()).collect()
 198     }
 199
 200     /// Constructs a `Vec` with copies of a value.
 201     ///
 202     /// Creates a `Vec` with `length` copies of `value`.
 203     ///
 204     /// # Example
 205     /// ```rust
 206     /// # use std::vec::Vec;
 207     /// let vec = Vec::from_elem(3, "hi");
 208     /// println!("{}", vec); // prints [hi, hi, hi]
 209     /// ```
 210     pub fn from_elem(length: uint, value: T) -> Vec<T> {
 211         unsafe {
 212             let mut xs = Vec::with_capacity(length);
 213             while xs.len < length {
 214                 move_val_init(xs.as_mut_slice().unsafe_mut_ref(xs.len), value.clone());
 215                 xs.len += 1;
 216             }
 217             xs
 218         }
 219     }
 220
 221     /// Appends all elements in a slice to the `Vec`.
 222     ///
 223     /// Iterates over the slice `other`, clones each element, and then appends
 224     /// it to this `Vec`. The `other` vector is traversed in-order.
 225     ///
 226     /// # Example
 227     ///
 228     /// ```rust
 229     /// let mut vec = vec!(1);
 230     /// vec.push_all([2, 3, 4]);
 231     /// assert_eq!(vec, vec!(1, 2, 3, 4));
 232     /// ```
 233     #[inline]
 234     pub fn push_all(&mut self, other: &[T]) {
 235         self.extend(other.iter().map(|e| e.clone()));
 236     }
 237
 238     /// Grows the `Vec` in-place.
 239     ///
 240     /// Adds `n` copies of `value` to the `Vec`.
 241     ///
 242     /// # Example
 243     ///
 244     /// ```rust
 245     /// let mut vec = vec!("hello");
 246     /// vec.grow(2, &("world"));
 247     /// assert_eq!(vec, vec!("hello", "world", "world"));
 248     /// ```
 249     pub fn grow(&mut self, n: uint, value: &T) {
 250         let new_len = self.len() + n;
 251         self.reserve(new_len);
 252         let mut i: uint = 0u;
 253
 254         while i < n {
 255             self.push((*value).clone());
 256             i += 1u;
 257         }
 258     }
 259
 260     /// Sets the value of a vector element at a given index, growing the vector
 261     /// as needed.
 262     ///
 263     /// Sets the element at position `index` to `value`. If `index` is past the
 264     /// end of the vector, expands the vector by replicating `initval` to fill
 265     /// the intervening space.
 266     ///
 267     /// # Example
 268     ///
 269     /// ```rust
 270     /// let mut vec = vec!("a", "b", "c");
 271     /// vec.grow_set(1, &("fill"), "d");
 272     /// vec.grow_set(4, &("fill"), "e");
 273     /// assert_eq!(vec, vec!("a", "d", "c", "fill", "e"));
 274     /// ```
 275     pub fn grow_set(&mut self, index: uint, initval: &T, value: T) {
 276         let l = self.len();
 277         if index >= l {
 278             self.grow(index - l + 1u, initval);
 279         }
 280         *self.get_mut(index) = value;
 281     }
 282
 283     /// Partitions a vector based on a predicate.
 284     ///
 285     /// Clones the elements of the vector, partitioning them into two `Vec`s
 286     /// `(A,B)`, where all elements of `A` satisfy `f` and all elements of `B`
 287     /// do not. The order of elements is preserved.
 288     ///
 289     /// # Example
 290     ///
 291     /// ```rust
 292     /// let vec = vec!(1, 2, 3, 4);
 293     /// let (even, odd) = vec.partitioned(|&n| n % 2 == 0);
 294     /// assert_eq!(even, vec!(2, 4));
 295     /// assert_eq!(odd, vec!(1, 3));
 296     /// ```
 297     pub fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
 298         let mut lefts = Vec::new();
 299         let mut rights = Vec::new();
 300
 301         for elt in self.iter() {
 302             if f(elt) {
 303                 lefts.push(elt.clone());
 304             } else {
 305                 rights.push(elt.clone());
 306             }
 307         }
 308
 309         (lefts, rights)
 310     }
 311 }
 312
 313 impl<T:Clone> Clone for Vec<T> {
 314     fn clone(&self) -> Vec<T> {
 315         let len = self.len;
 316         let mut vector = Vec::with_capacity(len);
 317         // Unsafe code so this can be optimised to a memcpy (or something
 318         // similarly fast) when T is Copy. LLVM is easily confused, so any
 319         // extra operations during the loop can prevent this optimisation
 320         {
 321             let this_slice = self.as_slice();
 322             while vector.len < len {
 323                 unsafe {
 324                     mem::move_val_init(
 325                         vector.as_mut_slice().unsafe_mut_ref(vector.len),
 326                         this_slice.unsafe_ref(vector.len).clone());
 327                 }
 328                 vector.len += 1;
 329             }
 330         }
 331         vector
 332     }
 333
 334     fn clone_from(&mut self, other: &Vec<T>) {
 335         // drop anything in self that will not be overwritten
 336         if self.len() > other.len() {
 337             self.truncate(other.len())
 338         }
 339
 340         // reuse the contained values' allocations/resources.
 341         for (place, thing) in self.mut_iter().zip(other.iter()) {
 342             place.clone_from(thing)
 343         }
 344
 345         // self.len <= other.len due to the truncate above, so the
 346         // slice here is always in-bounds.
 347         let len = self.len();
 348         self.extend(other.slice_from(len).iter().map(|x| x.clone()));
 349     }
 350 }
 351
 352 impl<T> FromIterator<T> for Vec<T> {
 353     fn from_iter<I:Iterator<T>>(mut iterator: I) -> Vec<T> {
 354         let (lower, _) = iterator.size_hint();
 355         let mut vector = Vec::with_capacity(lower);
 356         for element in iterator {
 357             vector.push(element)
 358         }
 359         vector
 360     }
 361 }
 362
 363 impl<T> Extendable<T> for Vec<T> {
 364     fn extend<I: Iterator<T>>(&mut self, mut iterator: I) {
 365         let (lower, _) = iterator.size_hint();
 366         self.reserve_additional(lower);
 367         for element in iterator {
 368             self.push(element)
 369         }
 370     }
 371 }
 372
 373 impl<T: Eq> Eq for Vec<T> {
 374     #[inline]
 375     fn eq(&self, other: &Vec<T>) -> bool {
 376         self.as_slice() == other.as_slice()
 377     }
 378 }
 379
 380 impl<T: Ord> Ord for Vec<T> {
 381     #[inline]
 382     fn lt(&self, other: &Vec<T>) -> bool {
 383         self.as_slice() < other.as_slice()
 384     }
 385 }
 386
 387 impl<T: TotalEq> TotalEq for Vec<T> {}
 388
 389 impl<T: TotalOrd> TotalOrd for Vec<T> {
 390     #[inline]
 391     fn cmp(&self, other: &Vec<T>) -> Ordering {
 392         self.as_slice().cmp(&other.as_slice())
 393     }
 394 }
 395
 396 impl<T> Container for Vec<T> {
 397     #[inline]
 398     fn len(&self) -> uint {
 399         self.len
 400     }
 401 }
 402
 403 impl<T> Vec<T> {
 404     /// Returns the number of elements the vector can hold without
 405     /// reallocating.
 406     ///
 407     /// # Example
 408     ///
 409     /// ```rust
 410     /// # use std::vec::Vec;
 411     /// let vec: Vec<int> = Vec::with_capacity(10);
 412     /// assert_eq!(vec.capacity(), 10);
 413     /// ```
 414     #[inline]
 415     pub fn capacity(&self) -> uint {
 416         self.cap
 417     }
 418
 419      /// Reserves capacity for at least `n` additional elements in the given
 420      /// vector.
 421      ///
 422      /// # Failure
 423      ///
 424      /// Fails if the new capacity overflows `uint`.
 425      ///
 426      /// # Example
 427      ///
 428      /// ```rust
 429      /// # use std::vec::Vec;
 430      /// let mut vec: Vec<int> = vec!(1);
 431      /// vec.reserve_additional(10);
 432      /// assert!(vec.capacity() >= 11);
 433      /// ```
 434     pub fn reserve_additional(&mut self, extra: uint) {
 435         if self.cap - self.len < extra {
 436             match self.len.checked_add(&extra) {
 437                 None => fail!("Vec::reserve_additional: `uint` overflow"),
 438                 Some(new_cap) => self.reserve(new_cap)
 439             }
 440         }
 441     }
 442
 443     /// Reserves capacity for at least `n` elements in the given vector.
 444     ///
 445     /// This function will over-allocate in order to amortize the allocation
 446     /// costs in scenarios where the caller may need to repeatedly reserve
 447     /// additional space.
 448     ///
 449     /// If the capacity for `self` is already equal to or greater than the
 450     /// requested capacity, then no action is taken.
 451     ///
 452     /// # Example
 453     ///
 454     /// ```rust
 455     /// let mut vec = vec!(1, 2, 3);
 456     /// vec.reserve(10);
 457     /// assert!(vec.capacity() >= 10);
 458     /// ```
 459     pub fn reserve(&mut self, capacity: uint) {
 460         if capacity >= self.len {
 461             self.reserve_exact(num::next_power_of_two(capacity))
 462         }
 463     }
 464
 465     /// Reserves capacity for exactly `capacity` elements in the given vector.
 466     ///
 467     /// If the capacity for `self` is already equal to or greater than the
 468     /// requested capacity, then no action is taken.
 469     ///
 470     /// # Example
 471     ///
 472     /// ```rust
 473     /// # use std::vec::Vec;
 474     /// let mut vec: Vec<int> = Vec::with_capacity(10);
 475     /// vec.reserve_exact(11);
 476     /// assert_eq!(vec.capacity(), 11);
 477     /// ```
 478     pub fn reserve_exact(&mut self, capacity: uint) {
 479         if capacity > self.cap {
 480             let size = capacity.checked_mul(&size_of::<T>()).expect("capacity overflow");
 481             self.cap = capacity;
 482             unsafe {
 483                 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
 484             }
 485         }
 486     }
 487
 488     /// Shrink the capacity of the vector to match the length
 489     ///
 490     /// # Example
 491     ///
 492     /// ```rust
 493     /// let mut vec = vec!(1, 2, 3);
 494     /// vec.shrink_to_fit();
 495     /// assert_eq!(vec.capacity(), vec.len());
 496     /// ```
 497     pub fn shrink_to_fit(&mut self) {
 498         if self.len == 0 {
 499             unsafe { free(self.ptr as *mut c_void) };
 500             self.cap = 0;
 501             self.ptr = 0 as *mut T;
 502         } else {
 503             unsafe {
 504                 // Overflow check is unnecessary as the vector is already at least this large.
 505                 self.ptr = realloc_raw(self.ptr as *mut u8, self.len * size_of::<T>()) as *mut T;
 506             }
 507             self.cap = self.len;
 508         }
 509     }
 510
 511     /// Remove the last element from a vector and return it, or `None` if it is
 512     /// empty.
 513     ///
 514     /// # Example
 515     ///
 516     /// ```rust
 517     /// let mut vec = vec!(1, 2, 3);
 518     /// assert_eq!(vec.pop(), Some(3));
 519     /// assert_eq!(vec, vec!(1, 2));
 520     /// ```
 521     #[inline]
 522     pub fn pop(&mut self) -> Option<T> {
 523         if self.len == 0 {
 524             None
 525         } else {
 526             unsafe {
 527                 self.len -= 1;
 528                 Some(ptr::read(self.as_slice().unsafe_ref(self.len())))
 529             }
 530         }
 531     }
 532
 533     /// Append an element to a vector.
 534     ///
 535     /// # Failure
 536     ///
 537     /// Fails if the number of elements in the vector overflows a `uint`.
 538     ///
 539     /// # Example
 540     ///
 541     /// ```rust
 542     /// let mut vec = vec!(1, 2);
 543     /// vec.push(3);
 544     /// assert_eq!(vec, vec!(1, 2, 3));
 545     /// ```
 546     #[inline]
 547     pub fn push(&mut self, value: T) {
 548         if self.len == self.cap {
 549             if self.cap == 0 { self.cap += 2 }
 550             let old_size = self.cap * size_of::<T>();
 551             self.cap = self.cap * 2;
 552             let size = old_size * 2;
 553             if old_size > size { fail!("capacity overflow") }
 554             unsafe {
 555                 self.ptr = realloc_raw(self.ptr as *mut u8, size) as *mut T;
 556             }
 557         }
 558
 559         unsafe {
 560             let end = (self.ptr as *T).offset(self.len as int) as *mut T;
 561             move_val_init(&mut *end, value);
 562             self.len += 1;
 563         }
 564     }
 565
 566     /// Appends one element to the vector provided. The vector itself is then
 567     /// returned for use again.
 568     ///
 569     /// # Example
 570     ///
 571     /// ```rust
 572     /// let vec = vec!(1, 2);
 573     /// let vec = vec.append_one(3);
 574     /// assert_eq!(vec, vec!(1, 2, 3));
 575     /// ```
 576     #[inline]
 577     pub fn append_one(mut self, x: T) -> Vec<T> {
 578         self.push(x);
 579         self
 580     }
 581
 582     /// Shorten a vector, dropping excess elements.
 583     ///
 584     /// If `len` is greater than the vector's current length, this has no
 585     /// effect.
 586     ///
 587     /// # Example
 588     ///
 589     /// ```rust
 590     /// let mut vec = vec!(1, 2, 3, 4);
 591     /// vec.truncate(2);
 592     /// assert_eq!(vec, vec!(1, 2));
 593     /// ```
 594     pub fn truncate(&mut self, len: uint) {
 595         unsafe {
 596             let mut i = len;
 597             // drop any extra elements
 598             while i < self.len {
 599                 ptr::read(self.as_slice().unsafe_ref(i));
 600                 i += 1;
 601             }
 602         }
 603         self.len = len;
 604     }
 605
 606     /// Work with `self` as a mutable slice.
 607     ///
 608     /// # Example
 609     ///
 610     /// ```rust
 611     /// fn foo(slice: &mut [int]) {}
 612     ///
 613     /// let mut vec = vec!(1, 2);
 614     /// foo(vec.as_mut_slice());
 615     /// ```
 616     #[inline]
 617     pub fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
 618         unsafe {
 619             transmute(Slice { data: self.as_mut_ptr() as *T, len: self.len })
 620         }
 621     }
 622
 623     /// Creates a consuming iterator, that is, one that moves each
 624     /// value out of the vector (from start to end). The vector cannot
 625     /// be used after calling this.
 626     ///
 627     /// # Example
 628     ///
 629     /// ```rust
 630     /// let v = vec!("a".to_owned(), "b".to_owned());
 631     /// for s in v.move_iter() {
 632     ///     // s has type ~str, not &~str
 633     ///     println!("{}", s);
 634     /// }
 635     /// ```
 636     #[inline]
 637     pub fn move_iter(self) -> MoveItems<T> {
 638         unsafe {
 639             let iter = transmute(self.as_slice().iter());
 640             let ptr = self.ptr as *mut c_void;
 641             forget(self);
 642             MoveItems { allocation: ptr, iter: iter }
 643         }
 644     }
 645
 646
 647     /// Sets the length of a vector.
 648     ///
 649     /// This will explicitly set the size of the vector, without actually
 650     /// modifying its buffers, so it is up to the caller to ensure that the
 651     /// vector is actually the specified size.
 652     #[inline]
 653     pub unsafe fn set_len(&mut self, len: uint) {
 654         self.len = len;
 655     }
 656
 657     /// Returns a reference to the value at index `index`.
 658     ///
 659     /// # Failure
 660     ///
 661     /// Fails if `index` is out of bounds
 662     ///
 663     /// # Example
 664     ///
 665     /// ```rust
 666     /// let vec = vec!(1, 2, 3);
 667     /// assert!(vec.get(1) == &2);
 668     /// ```
 669     #[inline]
 670     pub fn get<'a>(&'a self, index: uint) -> &'a T {
 671         &self.as_slice()[index]
 672     }
 673
 674     /// Returns a mutable reference to the value at index `index`.
 675     ///
 676     /// # Failure
 677     ///
 678     /// Fails if `index` is out of bounds
 679     ///
 680     /// # Example
 681     ///
 682     /// ```rust
 683     /// let mut vec = vec!(1, 2, 3);
 684     /// *vec.get_mut(1) = 4;
 685     /// assert_eq!(vec, vec!(1, 4, 3));
 686     /// ```
 687     #[inline]
 688     pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
 689         &mut self.as_mut_slice()[index]
 690     }
 691
 692     /// Returns an iterator over references to the elements of the vector in
 693     /// order.
 694     ///
 695     /// # Example
 696     ///
 697     /// ```rust
 698     /// let vec = vec!(1, 2, 3);
 699     /// for num in vec.iter() {
 700     ///     println!("{}", *num);
 701     /// }
 702     /// ```
 703     #[inline]
 704     pub fn iter<'a>(&'a self) -> Items<'a,T> {
 705         self.as_slice().iter()
 706     }
 707
 708
 709     /// Returns an iterator over mutable references to the elements of the
 710     /// vector in order.
 711     ///
 712     /// # Example
 713     ///
 714     /// ```rust
 715     /// let mut vec = vec!(1, 2, 3);
 716     /// for num in vec.mut_iter() {
 717     ///     *num = 0;
 718     /// }
 719     /// ```
 720     #[inline]
 721     pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a,T> {
 722         self.as_mut_slice().mut_iter()
 723     }
 724
 725     /// Sort the vector, in place, using `compare` to compare elements.
 726     ///
 727     /// This sort is `O(n log n)` worst-case and stable, but allocates
 728     /// approximately `2 * n`, where `n` is the length of `self`.
 729     ///
 730     /// # Example
 731     ///
 732     /// ```rust
 733     /// let mut v = vec!(5i, 4, 1, 3, 2);
 734     /// v.sort_by(|a, b| a.cmp(b));
 735     /// assert_eq!(v, vec!(1, 2, 3, 4, 5));
 736     ///
 737     /// // reverse sorting
 738     /// v.sort_by(|a, b| b.cmp(a));
 739     /// assert_eq!(v, vec!(5, 4, 3, 2, 1));
 740     /// ```
 741     #[inline]
 742     pub fn sort_by(&mut self, compare: |&T, &T| -> Ordering) {
 743         self.as_mut_slice().sort_by(compare)
 744     }
 745
 746     /// Returns a slice of `self` between `start` and `end`.
 747     ///
 748     /// # Failure
 749     ///
 750     /// Fails when `start` or `end` point outside the bounds of `self`, or when
 751     /// `start` > `end`.
 752     ///
 753     /// # Example
 754     ///
 755     /// ```rust
 756     /// let vec = vec!(1, 2, 3, 4);
 757     /// assert!(vec.slice(0, 2) == [1, 2]);
 758     /// ```
 759     #[inline]
 760     pub fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
 761         self.as_slice().slice(start, end)
 762     }
 763
 764     /// Returns a slice containing all but the first element of the vector.
 765     ///
 766     /// # Failure
 767     ///
 768     /// Fails when the vector is empty.
 769     ///
 770     /// # Example
 771     ///
 772     /// ```rust
 773     /// let vec = vec!(1, 2, 3);
 774     /// assert!(vec.tail() == [2, 3]);
 775     /// ```
 776     #[inline]
 777     pub fn tail<'a>(&'a self) -> &'a [T] {
 778         self.as_slice().tail()
 779     }
 780
 781     /// Returns all but the first `n' elements of a vector.
 782     ///
 783     /// # Failure
 784     ///
 785     /// Fails when there are fewer than `n` elements in the vector.
 786     ///
 787     /// # Example
 788     ///
 789     /// ```rust
 790     /// let vec = vec!(1, 2, 3, 4);
 791     /// assert!(vec.tailn(2) == [3, 4]);
 792     /// ```
 793     #[inline]
 794     pub fn tailn<'a>(&'a self, n: uint) -> &'a [T] {
 795         self.as_slice().tailn(n)
 796     }
 797
 798     /// Returns a reference to the last element of a vector, or `None` if it is
 799     /// empty.
 800     ///
 801     /// # Example
 802     ///
 803     /// ```rust
 804     /// let vec = vec!(1, 2, 3);
 805     /// assert!(vec.last() == Some(&3));
 806     /// ```
 807     #[inline]
 808     pub fn last<'a>(&'a self) -> Option<&'a T> {
 809         self.as_slice().last()
 810     }
 811
 812     /// Returns a mutable reference to the last element of a vector, or `None`
 813     /// if it is empty.
 814     ///
 815     /// # Example
 816     ///
 817     /// ```rust
 818     /// let mut vec = vec!(1, 2, 3);
 819     /// *vec.mut_last().unwrap() = 4;
 820     /// assert_eq!(vec, vec!(1, 2, 4));
 821     /// ```
 822     #[inline]
 823     pub fn mut_last<'a>(&'a mut self) -> Option<&'a mut T> {
 824         self.as_mut_slice().mut_last()
 825     }
 826
 827     /// Remove an element from anywhere in the vector and return it, replacing
 828     /// it with the last element. This does not preserve ordering, but is O(1).
 829     ///
 830     /// Returns `None` if `index` is out of bounds.
 831     ///
 832     /// # Example
 833     /// ```rust
 834     /// let mut v = vec!("foo".to_owned(), "bar".to_owned(), "baz".to_owned(), "qux".to_owned());
 835     ///
 836     /// assert_eq!(v.swap_remove(1), Some("bar".to_owned()));
 837     /// assert_eq!(v, vec!("foo".to_owned(), "qux".to_owned(), "baz".to_owned()));
 838     ///
 839     /// assert_eq!(v.swap_remove(0), Some("foo".to_owned()));
 840     /// assert_eq!(v, vec!("baz".to_owned(), "qux".to_owned()));
 841     ///
 842     /// assert_eq!(v.swap_remove(2), None);
 843     /// ```
 844     #[inline]
 845     pub fn swap_remove(&mut self, index: uint) -> Option<T> {
 846         let length = self.len();
 847         if index < length - 1 {
 848             self.as_mut_slice().swap(index, length - 1);
 849         } else if index >= length {
 850             return None
 851         }
 852         self.pop()
 853     }
 854
 855     /// Prepend an element to the vector.
 856     ///
 857     /// # Warning
 858     ///
 859     /// This is an O(n) operation as it requires copying every element in the
 860     /// vector.
 861     ///
 862     /// # Example
 863     ///
 864     /// ```rust
 865     /// let mut vec = vec!(1, 2, 3);
 866     /// vec.unshift(4);
 867     /// assert_eq!(vec, vec!(4, 1, 2, 3));
 868     /// ```
 869     #[inline]
 870     pub fn unshift(&mut self, element: T) {
 871         self.insert(0, element)
 872     }
 873
 874     /// Removes the first element from a vector and returns it, or `None` if
 875     /// the vector is empty.
 876     ///
 877     /// # Warning
 878     ///
 879     /// This is an O(n) operation as it requires copying every element in the
 880     /// vector.
 881     ///
 882     /// # Example
 883     ///
 884     /// ```rust
 885     /// let mut vec = vec!(1, 2, 3);
 886     /// assert!(vec.shift() == Some(1));
 887     /// assert_eq!(vec, vec!(2, 3));
 888     /// ```
 889     #[inline]
 890     pub fn shift(&mut self) -> Option<T> {
 891         self.remove(0)
 892     }
 893
 894     /// Insert an element at position `index` within the vector, shifting all
 895     /// elements after position i one position to the right.
 896     ///
 897     /// # Failure
 898     ///
 899     /// Fails if `index` is out of bounds of the vector.
 900     ///
 901     /// # Example
 902     ///
 903     /// ```rust
 904     /// let mut vec = vec!(1, 2, 3);
 905     /// vec.insert(1, 4);
 906     /// assert_eq!(vec, vec!(1, 4, 2, 3));
 907     /// ```
 908     pub fn insert(&mut self, index: uint, element: T) {
 909         let len = self.len();
 910         assert!(index <= len);
 911         // space for the new element
 912         self.reserve(len + 1);
 913
 914         unsafe { // infallible
 915             // The spot to put the new value
 916             {
 917                 let p = self.as_mut_ptr().offset(index as int);
 918                 // Shift everything over to make space. (Duplicating the
 919                 // `index`th element into two consecutive places.)
 920                 ptr::copy_memory(p.offset(1), &*p, len - index);
 921                 // Write it in, overwriting the first copy of the `index`th
 922                 // element.
 923                 move_val_init(&mut *p, element);
 924             }
 925             self.set_len(len + 1);
 926         }
 927     }
 928
 929     /// Remove and return the element at position `index` within the vector,
 930     /// shifting all elements after position `index` one position to the left.
 931     /// Returns `None` if `i` is out of bounds.
 932     ///
 933     /// # Example
 934     ///
 935     /// ```rust
 936     /// let mut v = vec!(1, 2, 3);
 937     /// assert_eq!(v.remove(1), Some(2));
 938     /// assert_eq!(v, vec!(1, 3));
 939     ///
 940     /// assert_eq!(v.remove(4), None);
 941     /// // v is unchanged:
 942     /// assert_eq!(v, vec!(1, 3));
 943     /// ```
 944     pub fn remove(&mut self, index: uint) -> Option<T> {
 945         let len = self.len();
 946         if index < len {
 947             unsafe { // infallible
 948                 let ret;
 949                 {
 950                     // the place we are taking from.
 951                     let ptr = self.as_mut_ptr().offset(index as int);
 952                     // copy it out, unsafely having a copy of the value on
 953                     // the stack and in the vector at the same time.
 954                     ret = Some(ptr::read(ptr as *T));
 955
 956                     // Shift everything down to fill in that spot.
 957                     ptr::copy_memory(ptr, &*ptr.offset(1), len - index - 1);
 958                 }
 959                 self.set_len(len - 1);
 960                 ret
 961             }
 962         } else {
 963             None
 964         }
 965     }
 966
 967     /// Takes ownership of the vector `other`, moving all elements into
 968     /// the current vector. This does not copy any elements, and it is
 969     /// illegal to use the `other` vector after calling this method
 970     /// (because it is moved here).
 971     ///
 972     /// # Example
 973     ///
 974     /// ```rust
 975     /// let mut vec = vec!(box 1);
 976     /// vec.push_all_move(vec!(box 2, box 3, box 4));
 977     /// assert_eq!(vec, vec!(box 1, box 2, box 3, box 4));
 978     /// ```
 979     pub fn push_all_move(&mut self, other: Vec<T>) {
 980         self.extend(other.move_iter());
 981     }
 982
 983     /// Returns a mutable slice of `self` between `start` and `end`.
 984     ///
 985     /// # Failure
 986     ///
 987     /// Fails when `start` or `end` point outside the bounds of `self`, or when
 988     /// `start` > `end`.
 989     ///
 990     /// # Example
 991     ///
 992     /// ```rust
 993     /// let mut vec = vec!(1, 2, 3, 4);
 994     /// assert!(vec.mut_slice(0, 2) == [1, 2]);
 995     /// ```
 996     #[inline]
 997     pub fn mut_slice<'a>(&'a mut self, start: uint, end: uint)
 998                          -> &'a mut [T] {
 999         self.as_mut_slice().mut_slice(start, end)
1000     }
1001
1002     /// Returns a mutable slice of self from `start` to the end of the vec.
1003     ///
1004     /// # Failure
1005     ///
1006     /// Fails when `start` points outside the bounds of self.
1007     ///
1008     /// # Example
1009     ///
1010     /// ```rust
1011     /// let mut vec = vec!(1, 2, 3, 4);
1012     /// assert!(vec.mut_slice_from(2) == [3, 4]);
1013     /// ```
1014     #[inline]
1015     pub fn mut_slice_from<'a>(&'a mut self, start: uint) -> &'a mut [T] {
1016         self.as_mut_slice().mut_slice_from(start)
1017     }
1018
1019     /// Returns a mutable slice of self from the start of the vec to `end`.
1020     ///
1021     /// # Failure
1022     ///
1023     /// Fails when `end` points outside the bounds of self.
1024     ///
1025     /// # Example
1026     ///
1027     /// ```rust
1028     /// let mut vec = vec!(1, 2, 3, 4);
1029     /// assert!(vec.mut_slice_to(2) == [1, 2]);
1030     /// ```
1031     #[inline]
1032     pub fn mut_slice_to<'a>(&'a mut self, end: uint) -> &'a mut [T] {
1033         self.as_mut_slice().mut_slice_to(end)
1034     }
1035
1036     /// Returns a pair of mutable slices that divides the vec at an index.
1037     ///
1038     /// The first will contain all indices from `[0, mid)` (excluding
1039     /// the index `mid` itself) and the second will contain all
1040     /// indices from `[mid, len)` (excluding the index `len` itself).
1041     ///
1042     /// # Failure
1043     ///
1044     /// Fails if `mid > len`.
1045     ///
1046     /// # Example
1047     ///
1048     /// ```rust
1049     /// let mut vec = vec!(1, 2, 3, 4, 5, 6);
1050     ///
1051     /// // scoped to restrict the lifetime of the borrows
1052     /// {
1053     ///    let (left, right) = vec.mut_split_at(0);
1054     ///    assert!(left == &mut []);
1055     ///    assert!(right == &mut [1, 2, 3, 4, 5, 6]);
1056     /// }
1057     ///
1058     /// {
1059     ///     let (left, right) = vec.mut_split_at(2);
1060     ///     assert!(left == &mut [1, 2]);
1061     ///     assert!(right == &mut [3, 4, 5, 6]);
1062     /// }
1063     ///
1064     /// {
1065     ///     let (left, right) = vec.mut_split_at(6);
1066     ///     assert!(left == &mut [1, 2, 3, 4, 5, 6]);
1067     ///     assert!(right == &mut []);
1068     /// }
1069     /// ```
1070     #[inline]
1071     pub fn mut_split_at<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
1072         self.as_mut_slice().mut_split_at(mid)
1073     }
1074
1075     /// Reverse the order of elements in a vector, in place.
1076     ///
1077     /// # Example
1078     ///
1079     /// ```rust
1080     /// let mut v = vec!(1, 2, 3);
1081     /// v.reverse();
1082     /// assert_eq!(v, vec!(3, 2, 1));
1083     /// ```
1084     #[inline]
1085     pub fn reverse(&mut self) {
1086         self.as_mut_slice().reverse()
1087     }
1088
1089     /// Returns a slice of `self` from `start` to the end of the vec.
1090     ///
1091     /// # Failure
1092     ///
1093     /// Fails when `start` points outside the bounds of self.
1094     ///
1095     /// # Example
1096     ///
1097     /// ```rust
1098     /// let vec = vec!(1, 2, 3);
1099     /// assert!(vec.slice_from(1) == [2, 3]);
1100     /// ```
1101     #[inline]
1102     pub fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
1103         self.as_slice().slice_from(start)
1104     }
1105
1106     /// Returns a slice of self from the start of the vec to `end`.
1107     ///
1108     /// # Failure
1109     ///
1110     /// Fails when `end` points outside the bounds of self.
1111     ///
1112     /// # Example
1113     ///
1114     /// ```rust
1115     /// let vec = vec!(1, 2, 3);
1116     /// assert!(vec.slice_to(2) == [1, 2]);
1117     /// ```
1118     #[inline]
1119     pub fn slice_to<'a>(&'a self, end: uint) -> &'a [T] {
1120         self.as_slice().slice_to(end)
1121     }
1122
1123     /// Returns a slice containing all but the last element of the vector.
1124     ///
1125     /// # Failure
1126     ///
1127     /// Fails if the vector is empty
1128     #[inline]
1129     pub fn init<'a>(&'a self) -> &'a [T] {
1130         self.slice(0, self.len() - 1)
1131     }
1132
1133
1134     /// Returns an unsafe pointer to the vector's buffer.
1135     ///
1136     /// The caller must ensure that the vector outlives the pointer this
1137     /// function returns, or else it will end up pointing to garbage.
1138     ///
1139     /// Modifying the vector may cause its buffer to be reallocated, which
1140     /// would also make any pointers to it invalid.
1141     #[inline]
1142     pub fn as_ptr(&self) -> *T {
1143         // If we have a 0-sized vector, then the base pointer should not be NULL
1144         // because an iterator over the slice will attempt to yield the base
1145         // pointer as the first element in the vector, but this will end up
1146         // being Some(NULL) which is optimized to None.
1147         if mem::size_of::<T>() == 0 {
1148             1 as *T
1149         } else {
1150             self.ptr as *T
1151         }
1152     }
1153
1154     /// Returns a mutable unsafe pointer to the vector's buffer.
1155     ///
1156     /// The caller must ensure that the vector outlives the pointer this
1157     /// function returns, or else it will end up pointing to garbage.
1158     ///
1159     /// Modifying the vector may cause its buffer to be reallocated, which
1160     /// would also make any pointers to it invalid.
1161     #[inline]
1162     pub fn as_mut_ptr(&mut self) -> *mut T {
1163         // see above for the 0-size check
1164         if mem::size_of::<T>() == 0 {
1165             1 as *mut T
1166         } else {
1167             self.ptr
1168         }
1169     }
1170
1171     /// Retains only the elements specified by the predicate.
1172     ///
1173     /// In other words, remove all elements `e` such that `f(&e)` returns false.
1174     /// This method operates in place and preserves the order the retained elements.
1175     ///
1176     /// # Example
1177     ///
1178     /// ```rust
1179     /// let mut vec = vec!(1i, 2, 3, 4);
1180     /// vec.retain(|x| x%2 == 0);
1181     /// assert_eq!(vec, vec!(2, 4));
1182     /// ```
1183     pub fn retain(&mut self, f: |&T| -> bool) {
1184         let len = self.len();
1185         let mut del = 0u;
1186         {
1187             let v = self.as_mut_slice();
1188
1189             for i in range(0u, len) {
1190                 if !f(&v[i]) {
1191                     del += 1;
1192                 } else if del > 0 {
1193                     v.swap(i-del, i);
1194                 }
1195             }
1196         }
1197         if del > 0 {
1198             self.truncate(len - del);
1199         }
1200     }
1201
1202     /// Expands a vector in place, initializing the new elements to the result of a function.
1203     ///
1204     /// The vector is grown by `n` elements. The i-th new element are initialized to the value
1205     /// returned by `f(i)` where `i` is in the range [0, n).
1206     ///
1207     /// # Example
1208     ///
1209     /// ```rust
1210     /// let mut vec = vec!(0u, 1);
1211     /// vec.grow_fn(3, |i| i);
1212     /// assert_eq!(vec, vec!(0, 1, 0, 1, 2));
1213     /// ```
1214     pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) {
1215         self.reserve_additional(n);
1216         for i in range(0u, n) {
1217             self.push(f(i));
1218         }
1219     }
1220 }
1221
1222 impl<T:TotalOrd> Vec<T> {
1223     /// Sorts the vector in place.
1224     ///
1225     /// This sort is `O(n log n)` worst-case and stable, but allocates
1226     /// approximately `2 * n`, where `n` is the length of `self`.
1227     ///
1228     /// # Example
1229     ///
1230     /// ```rust
1231     /// let mut vec = vec!(3i, 1, 2);
1232     /// vec.sort();
1233     /// assert_eq!(vec, vec!(1, 2, 3));
1234     /// ```
1235     pub fn sort(&mut self) {
1236         self.as_mut_slice().sort()
1237     }
1238 }
1239
1240 impl<T> Mutable for Vec<T> {
1241     #[inline]
1242     fn clear(&mut self) {
1243         self.truncate(0)
1244     }
1245 }
1246
1247 impl<T:Eq> Vec<T> {
1248     /// Return true if a vector contains an element with the given value
1249     ///
1250     /// # Example
1251     ///
1252     /// ```rust
1253     /// let vec = vec!(1, 2, 3);
1254     /// assert!(vec.contains(&1));
1255     /// ```
1256     pub fn contains(&self, x: &T) -> bool {
1257         self.as_slice().contains(x)
1258     }
1259
1260     /// Remove consecutive repeated elements in the vector.
1261     ///
1262     /// If the vector is sorted, this removes all duplicates.
1263     ///
1264     /// # Example
1265     ///
1266     /// ```rust
1267     /// let mut vec = vec!(1, 2, 2, 3, 2);
1268     /// vec.dedup();
1269     /// assert_eq!(vec, vec!(1, 2, 3, 2));
1270     /// ```
1271     pub fn dedup(&mut self) {
1272         unsafe {
1273             // Although we have a mutable reference to `self`, we cannot make
1274             // *arbitrary* changes. The `Eq` comparisons could fail, so we
1275             // must ensure that the vector is in a valid state at all time.
1276             //
1277             // The way that we handle this is by using swaps; we iterate
1278             // over all the elements, swapping as we go so that at the end
1279             // the elements we wish to keep are in the front, and those we
1280             // wish to reject are at the back. We can then truncate the
1281             // vector. This operation is still O(n).
1282             //
1283             // Example: We start in this state, where `r` represents "next
1284             // read" and `w` represents "next_write`.
1285             //
1286             //           r
1287             //     +---+---+---+---+---+---+
1288             //     | 0 | 1 | 1 | 2 | 3 | 3 |
1289             //     +---+---+---+---+---+---+
1290             //           w
1291             //
1292             // Comparing self[r] against self[w-1], this is not a duplicate, so
1293             // we swap self[r] and self[w] (no effect as r==w) and then increment both
1294             // r and w, leaving us with:
1295             //
1296             //               r
1297             //     +---+---+---+---+---+---+
1298             //     | 0 | 1 | 1 | 2 | 3 | 3 |
1299             //     +---+---+---+---+---+---+
1300             //               w
1301             //
1302             // Comparing self[r] against self[w-1], this value is a duplicate,
1303             // so we increment `r` but leave everything else unchanged:
1304             //
1305             //                   r
1306             //     +---+---+---+---+---+---+
1307             //     | 0 | 1 | 1 | 2 | 3 | 3 |
1308             //     +---+---+---+---+---+---+
1309             //               w
1310             //
1311             // Comparing self[r] against self[w-1], this is not a duplicate,
1312             // so swap self[r] and self[w] and advance r and w:
1313             //
1314             //                       r
1315             //     +---+---+---+---+---+---+
1316             //     | 0 | 1 | 2 | 1 | 3 | 3 |
1317             //     +---+---+---+---+---+---+
1318             //                   w
1319             //
1320             // Not a duplicate, repeat:
1321             //
1322             //                           r
1323             //     +---+---+---+---+---+---+
1324             //     | 0 | 1 | 2 | 3 | 1 | 3 |
1325             //     +---+---+---+---+---+---+
1326             //                       w
1327             //
1328             // Duplicate, advance r. End of vec. Truncate to w.
1329
1330             let ln = self.len();
1331             if ln < 1 { return; }
1332
1333             // Avoid bounds checks by using unsafe pointers.
1334             let p = self.as_mut_slice().as_mut_ptr();
1335             let mut r = 1;
1336             let mut w = 1;
1337
1338             while r < ln {
1339                 let p_r = p.offset(r as int);
1340                 let p_wm1 = p.offset((w - 1) as int);
1341                 if *p_r != *p_wm1 {
1342                     if r != w {
1343                         let p_w = p_wm1.offset(1);
1344                         mem::swap(&mut *p_r, &mut *p_w);
1345                     }
1346                     w += 1;
1347                 }
1348                 r += 1;
1349             }
1350
1351             self.truncate(w);
1352         }
1353     }
1354 }
1355
1356 impl<T> Vector<T> for Vec<T> {
1357     /// Work with `self` as a slice.
1358     ///
1359     /// # Example
1360     ///
1361     /// ```rust
1362     /// fn foo(slice: &[int]) {}
1363     ///
1364     /// let vec = vec!(1, 2);
1365     /// foo(vec.as_slice());
1366     /// ```
1367     #[inline]
1368     fn as_slice<'a>(&'a self) -> &'a [T] {
1369         unsafe { transmute(Slice { data: self.as_ptr(), len: self.len }) }
1370     }
1371 }
1372
1373 #[unsafe_destructor]
1374 impl<T> Drop for Vec<T> {
1375     fn drop(&mut self) {
1376         // This is (and should always remain) a no-op if the fields are
1377         // zeroed (when moving out, because of #[unsafe_no_drop_flag]).
1378         unsafe {
1379             for x in self.as_mut_slice().iter() {
1380                 ptr::read(x);
1381             }
1382             free(self.ptr as *mut c_void)
1383         }
1384     }
1385 }
1386
1387 impl<T> Default for Vec<T> {
1388     fn default() -> Vec<T> {
1389         Vec::new()
1390     }
1391 }
1392
1393 impl<T:fmt::Show> fmt::Show for Vec<T> {
1394     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1395         self.as_slice().fmt(f)
1396     }
1397 }
1398
1399 /// An iterator that moves out of a vector.
1400 pub struct MoveItems<T> {
1401     allocation: *mut c_void, // the block of memory allocated for the vector
1402     iter: Items<'static, T>
1403 }
1404
1405 impl<T> Iterator<T> for MoveItems<T> {
1406     #[inline]
1407     fn next(&mut self) -> Option<T> {
1408         unsafe {
1409             self.iter.next().map(|x| ptr::read(x))
1410         }
1411     }
1412
1413     #[inline]
1414     fn size_hint(&self) -> (uint, Option<uint>) {
1415         self.iter.size_hint()
1416     }
1417 }
1418
1419 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
1420     #[inline]
1421     fn next_back(&mut self) -> Option<T> {
1422         unsafe {
1423             self.iter.next_back().map(|x| ptr::read(x))
1424         }
1425     }
1426 }
1427
1428 #[unsafe_destructor]
1429 impl<T> Drop for MoveItems<T> {
1430     fn drop(&mut self) {
1431         // destroy the remaining elements
1432         for _x in *self {}
1433         unsafe {
1434             free(self.allocation)
1435         }
1436     }
1437 }
1438
1439 #[cfg(test)]
1440 mod tests {
1441     use prelude::*;
1442     use mem::size_of;
1443
1444     #[test]
1445     fn test_small_vec_struct() {
1446         assert!(size_of::<Vec<u8>>() == size_of::<uint>() * 3);
1447     }
1448
1449     #[test]
1450     fn test_double_drop() {
1451         struct TwoVec<T> {
1452             x: Vec<T>,
1453             y: Vec<T>
1454         }
1455
1456         struct DropCounter<'a> {
1457             count: &'a mut int
1458         }
1459
1460         #[unsafe_destructor]
1461         impl<'a> Drop for DropCounter<'a> {
1462             fn drop(&mut self) {
1463                 *self.count += 1;
1464             }
1465         }
1466
1467         let mut count_x @ mut count_y = 0;
1468         {
1469             let mut tv = TwoVec {
1470                 x: Vec::new(),
1471                 y: Vec::new()
1472             };
1473             tv.x.push(DropCounter {count: &mut count_x});
1474             tv.y.push(DropCounter {count: &mut count_y});
1475
1476             // If Vec had a drop flag, here is where it would be zeroed.
1477             // Instead, it should rely on its internal state to prevent
1478             // doing anything significant when dropped multiple times.
1479             drop(tv.x);
1480
1481             // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
1482         }
1483
1484         assert_eq!(count_x, 1);
1485         assert_eq!(count_y, 1);
1486     }
1487
1488     #[test]
1489     fn test_reserve_additional() {
1490         let mut v = Vec::new();
1491         assert_eq!(v.capacity(), 0);
1492
1493         v.reserve_additional(2);
1494         assert!(v.capacity() >= 2);
1495
1496         for i in range(0, 16) {
1497             v.push(i);
1498         }
1499
1500         assert!(v.capacity() >= 16);
1501         v.reserve_additional(16);
1502         assert!(v.capacity() >= 32);
1503
1504         v.push(16);
1505
1506         v.reserve_additional(16);
1507         assert!(v.capacity() >= 33)
1508     }
1509
1510     #[test]
1511     fn test_extend() {
1512         let mut v = Vec::new();
1513         let mut w = Vec::new();
1514
1515         v.extend(range(0, 3));
1516         for i in range(0, 3) { w.push(i) }
1517
1518         assert_eq!(v, w);
1519
1520         v.extend(range(3, 10));
1521         for i in range(3, 10) { w.push(i) }
1522
1523         assert_eq!(v, w);
1524     }
1525
1526     #[test]
1527     fn test_mut_slice_from() {
1528         let mut values = Vec::from_slice([1u8,2,3,4,5]);
1529         {
1530             let slice = values.mut_slice_from(2);
1531             assert!(slice == [3, 4, 5]);
1532             for p in slice.mut_iter() {
1533                 *p += 2;
1534             }
1535         }
1536
1537         assert!(values.as_slice() == [1, 2, 5, 6, 7]);
1538     }
1539
1540     #[test]
1541     fn test_mut_slice_to() {
1542         let mut values = Vec::from_slice([1u8,2,3,4,5]);
1543         {
1544             let slice = values.mut_slice_to(2);
1545             assert!(slice == [1, 2]);
1546             for p in slice.mut_iter() {
1547                 *p += 1;
1548             }
1549         }
1550
1551         assert!(values.as_slice() == [2, 3, 3, 4, 5]);
1552     }
1553
1554     #[test]
1555     fn test_mut_split_at() {
1556         let mut values = Vec::from_slice([1u8,2,3,4,5]);
1557         {
1558             let (left, right) = values.mut_split_at(2);
1559             assert!(left.slice(0, left.len()) == [1, 2]);
1560             for p in left.mut_iter() {
1561                 *p += 1;
1562             }
1563
1564             assert!(right.slice(0, right.len()) == [3, 4, 5]);
1565             for p in right.mut_iter() {
1566                 *p += 2;
1567             }
1568         }
1569
1570         assert!(values == Vec::from_slice([2u8, 3, 5, 6, 7]));
1571     }
1572
1573     #[test]
1574     fn test_clone() {
1575         let v: Vec<int> = vec!();
1576         let w = vec!(1, 2, 3);
1577
1578         assert_eq!(v, v.clone());
1579
1580         let z = w.clone();
1581         assert_eq!(w, z);
1582         // they should be disjoint in memory.
1583         assert!(w.as_ptr() != z.as_ptr())
1584     }
1585
1586     #[test]
1587     fn test_clone_from() {
1588         let mut v = vec!();
1589         let three = vec!(box 1, box 2, box 3);
1590         let two = vec!(box 4, box 5);
1591         // zero, long
1592         v.clone_from(&three);
1593         assert_eq!(v, three);
1594
1595         // equal
1596         v.clone_from(&three);
1597         assert_eq!(v, three);
1598
1599         // long, short
1600         v.clone_from(&two);
1601         assert_eq!(v, two);
1602
1603         // short, long
1604         v.clone_from(&three);
1605         assert_eq!(v, three)
1606     }
1607
1608     #[test]
1609     fn test_grow_fn() {
1610         let mut v = Vec::from_slice([0u, 1]);
1611         v.grow_fn(3, |i| i);
1612         assert!(v == Vec::from_slice([0u, 1, 0, 1, 2]));
1613     }
1614
1615     #[test]
1616     fn test_retain() {
1617         let mut vec = Vec::from_slice([1u, 2, 3, 4]);
1618         vec.retain(|x| x%2 == 0);
1619         assert!(vec == Vec::from_slice([2u, 4]));
1620     }
1621
1622     #[test]
1623     fn zero_sized_values() {
1624         let mut v = Vec::new();
1625         assert_eq!(v.len(), 0);
1626         v.push(());
1627         assert_eq!(v.len(), 1);
1628         v.push(());
1629         assert_eq!(v.len(), 2);
1630         assert_eq!(v.pop(), Some(()));
1631         assert_eq!(v.pop(), Some(()));
1632         assert_eq!(v.pop(), None);
1633
1634         assert_eq!(v.iter().len(), 0);
1635         v.push(());
1636         assert_eq!(v.iter().len(), 1);
1637         v.push(());
1638         assert_eq!(v.iter().len(), 2);
1639
1640         for &() in v.iter() {}
1641
1642         assert_eq!(v.mut_iter().len(), 2);
1643         v.push(());
1644         assert_eq!(v.mut_iter().len(), 3);
1645         v.push(());
1646         assert_eq!(v.mut_iter().len(), 4);
1647
1648         for &() in v.mut_iter() {}
1649         unsafe { v.set_len(0); }
1650         assert_eq!(v.mut_iter().len(), 0);
1651     }
1652 }