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