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