src/libcollections/vec.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A growable list type with heap-allocated contents, written `Vec<T>` but
  12 //! pronounced 'vector.'
  13 //!
  14 //! Vectors have `O(1)` indexing, push (to the end) and pop (from the end).
  15 //!
  16 //! # Examples
  17 //!
  18 //! Explicitly creating a `Vec<T>` with `new()`:
  19 //!
  20 //! ```
  21 //! let xs: Vec<i32> = Vec::new();
  22 //! ```
  23 //!
  24 //! Using the `vec!` macro:
  25 //!
  26 //! ```
  27 //! let ys: Vec<i32> = vec![];
  28 //!
  29 //! let zs = vec![1i32, 2, 3, 4, 5];
  30 //! ```
  31 //!
  32 //! Push:
  33 //!
  34 //! ```
  35 //! let mut xs = vec![1i32, 2];
  36 //!
  37 //! xs.push(3);
  38 //! ```
  39 //!
  40 //! And pop:
  41 //!
  42 //! ```
  43 //! let mut xs = vec![1i32, 2];
  44 //!
  45 //! let two = xs.pop();
  46 //! ```
  47
  48 #![stable(feature = "rust1", since = "1.0.0")]
  49
  50 use core::prelude::*;
  51
  52 use alloc::boxed::Box;
  53 use alloc::heap::{EMPTY, allocate, reallocate, deallocate};
  54 use core::cmp::max;
  55 use core::cmp::Ordering;
  56 use core::fmt;
  57 use core::hash::{self, Hash};
  58 use core::intrinsics::assume;
  59 use core::iter::{repeat, FromIterator};
  60 use core::marker::PhantomData;
  61 use core::mem;
  62 use core::ops::{Index, IndexMut, Deref, Add};
  63 use core::ops;
  64 use core::ptr;
  65 use core::ptr::Unique;
  66 use core::slice;
  67 use core::isize;
  68 use core::usize;
  69
  70 use borrow::{Cow, IntoCow};
  71
  72 // FIXME- fix places which assume the max vector allowed has memory usize::MAX.
  73 static MAX_MEMORY_SIZE: usize = isize::MAX as usize;
  74
  75 /// A growable list type, written `Vec<T>` but pronounced 'vector.'
  76 ///
  77 /// # Examples
  78 ///
  79 /// ```
  80 /// # #![feature(collections)]
  81 /// let mut vec = Vec::new();
  82 /// vec.push(1);
  83 /// vec.push(2);
  84 ///
  85 /// assert_eq!(vec.len(), 2);
  86 /// assert_eq!(vec[0], 1);
  87 ///
  88 /// assert_eq!(vec.pop(), Some(2));
  89 /// assert_eq!(vec.len(), 1);
  90 ///
  91 /// vec[0] = 7;
  92 /// assert_eq!(vec[0], 7);
  93 ///
  94 /// vec.push_all(&[1, 2, 3]);
  95 ///
  96 /// for x in vec.iter() {
  97 ///     println!("{}", x);
  98 /// }
  99 /// assert_eq!(vec, [7, 1, 2, 3]);
 100 /// ```
 101 ///
 102 /// The `vec!` macro is provided to make initialization more convenient:
 103 ///
 104 /// ```
 105 /// let mut vec = vec![1, 2, 3];
 106 /// vec.push(4);
 107 /// assert_eq!(vec, [1, 2, 3, 4]);
 108 /// ```
 109 ///
 110 /// Use a `Vec<T>` as an efficient stack:
 111 ///
 112 /// ```
 113 /// let mut stack = Vec::new();
 114 ///
 115 /// stack.push(1);
 116 /// stack.push(2);
 117 /// stack.push(3);
 118 ///
 119 /// loop {
 120 ///     let top = match stack.pop() {
 121 ///         None => break, // empty
 122 ///         Some(x) => x,
 123 ///     };
 124 ///     // Prints 3, 2, 1
 125 ///     println!("{}", top);
 126 /// }
 127 /// ```
 128 ///
 129 /// # Capacity and reallocation
 130 ///
 131 /// The capacity of a vector is the amount of space allocated for any future
 132 /// elements that will be added onto the vector. This is not to be confused with
 133 /// the *length* of a vector, which specifies the number of actual elements
 134 /// within the vector. If a vector's length exceeds its capacity, its capacity
 135 /// will automatically be increased, but its elements will have to be
 136 /// reallocated.
 137 ///
 138 /// For example, a vector with capacity 10 and length 0 would be an empty vector
 139 /// with space for 10 more elements. Pushing 10 or fewer elements onto the
 140 /// vector will not change its capacity or cause reallocation to occur. However,
 141 /// if the vector's length is increased to 11, it will have to reallocate, which
 142 /// can be slow. For this reason, it is recommended to use `Vec::with_capacity`
 143 /// whenever possible to specify how big the vector is expected to get.
 144 #[unsafe_no_drop_flag]
 145 #[stable(feature = "rust1", since = "1.0.0")]
 146 pub struct Vec<T> {
 147     ptr: Unique<T>,
 148     len: usize,
 149     cap: usize,
 150 }
 151
 152 unsafe impl<T: Send> Send for Vec<T> { }
 153 unsafe impl<T: Sync> Sync for Vec<T> { }
 154
 155 ////////////////////////////////////////////////////////////////////////////////
 156 // Inherent methods
 157 ////////////////////////////////////////////////////////////////////////////////
 158
 159 impl<T> Vec<T> {
 160     /// Constructs a new, empty `Vec<T>`.
 161     ///
 162     /// The vector will not allocate until elements are pushed onto it.
 163     ///
 164     /// # Examples
 165     ///
 166     /// ```
 167     /// let mut vec: Vec<i32> = Vec::new();
 168     /// ```
 169     #[inline]
 170     #[stable(feature = "rust1", since = "1.0.0")]
 171     pub fn new() -> Vec<T> {
 172         // We want ptr to never be NULL so instead we set it to some arbitrary
 173         // non-null value which is fine since we never call deallocate on the ptr
 174         // if cap is 0. The reason for this is because the pointer of a slice
 175         // being NULL would break the null pointer optimization for enums.
 176         unsafe { Vec::from_raw_parts(EMPTY as *mut T, 0, 0) }
 177     }
 178
 179     /// Constructs a new, empty `Vec<T>` with the specified capacity.
 180     ///
 181     /// The vector will be able to hold exactly `capacity` elements without reallocating. If
 182     /// `capacity` is 0, the vector will not allocate.
 183     ///
 184     /// It is important to note that this function does not specify the *length* of the returned
 185     /// vector, but only the *capacity*. (For an explanation of the difference between length and
 186     /// capacity, see the main `Vec<T>` docs above, 'Capacity and reallocation'.)
 187     ///
 188     /// # Examples
 189     ///
 190     /// ```
 191     /// let mut vec = Vec::with_capacity(10);
 192     ///
 193     /// // The vector contains no items, even though it has capacity for more
 194     /// assert_eq!(vec.len(), 0);
 195     ///
 196     /// // These are all done without reallocating...
 197     /// for i in 0..10 {
 198     ///     vec.push(i);
 199     /// }
 200     ///
 201     /// // ...but this may make the vector reallocate
 202     /// vec.push(11);
 203     /// ```
 204     #[inline]
 205     #[stable(feature = "rust1", since = "1.0.0")]
 206     pub fn with_capacity(capacity: usize) -> Vec<T> {
 207         if mem::size_of::<T>() == 0 {
 208             unsafe { Vec::from_raw_parts(EMPTY as *mut T, 0, usize::MAX) }
 209         } else if capacity == 0 {
 210             Vec::new()
 211         } else {
 212             let size = capacity.checked_mul(mem::size_of::<T>())
 213                                .expect("capacity overflow");
 214             let ptr = unsafe { allocate(size, mem::min_align_of::<T>()) };
 215             if ptr.is_null() { ::alloc::oom() }
 216             unsafe { Vec::from_raw_parts(ptr as *mut T, 0, capacity) }
 217         }
 218     }
 219
 220     /// Creates a `Vec<T>` directly from the raw components of another vector.
 221     ///
 222     /// This is highly unsafe, due to the number of invariants that aren't checked.
 223     ///
 224     /// # Examples
 225     ///
 226     /// ```
 227     /// use std::ptr;
 228     /// use std::mem;
 229     ///
 230     /// fn main() {
 231     ///     let mut v = vec![1, 2, 3];
 232     ///
 233     ///     // Pull out the various important pieces of information about `v`
 234     ///     let p = v.as_mut_ptr();
 235     ///     let len = v.len();
 236     ///     let cap = v.capacity();
 237     ///
 238     ///     unsafe {
 239     ///         // Cast `v` into the void: no destructor run, so we are in
 240     ///         // complete control of the allocation to which `p` points.
 241     ///         mem::forget(v);
 242     ///
 243     ///         // Overwrite memory with 4, 5, 6
 244     ///         for i in 0..len as isize {
 245     ///             ptr::write(p.offset(i), 4 + i);
 246     ///         }
 247     ///
 248     ///         // Put everything back together into a Vec
 249     ///         let rebuilt = Vec::from_raw_parts(p, len, cap);
 250     ///         assert_eq!(rebuilt, [4, 5, 6]);
 251     ///     }
 252     /// }
 253     /// ```
 254     #[stable(feature = "rust1", since = "1.0.0")]
 255     pub unsafe fn from_raw_parts(ptr: *mut T, length: usize,
 256                                  capacity: usize) -> Vec<T> {
 257         Vec {
 258             ptr: Unique::new(ptr),
 259             len: length,
 260             cap: capacity,
 261         }
 262     }
 263
 264     /// Creates a vector by copying the elements from a raw pointer.
 265     ///
 266     /// This function will copy `elts` contiguous elements starting at `ptr`
 267     /// into a new allocation owned by the returned `Vec<T>`. The elements of
 268     /// the buffer are copied into the vector without cloning, as if
 269     /// `ptr::read()` were called on them.
 270     #[inline]
 271     #[unstable(feature = "collections",
 272                reason = "may be better expressed via composition")]
 273     pub unsafe fn from_raw_buf(ptr: *const T, elts: usize) -> Vec<T> {
 274         let mut dst = Vec::with_capacity(elts);
 275         dst.set_len(elts);
 276         ptr::copy_nonoverlapping(ptr, dst.as_mut_ptr(), elts);
 277         dst
 278     }
 279
 280     /// Returns the number of elements the vector can hold without
 281     /// reallocating.
 282     ///
 283     /// # Examples
 284     ///
 285     /// ```
 286     /// let vec: Vec<i32> = Vec::with_capacity(10);
 287     /// assert_eq!(vec.capacity(), 10);
 288     /// ```
 289     #[inline]
 290     #[stable(feature = "rust1", since = "1.0.0")]
 291     pub fn capacity(&self) -> usize {
 292         self.cap
 293     }
 294
 295     /// Reserves capacity for at least `additional` more elements to be inserted
 296     /// in the given `Vec<T>`. The collection may reserve more space to avoid
 297     /// frequent reallocations.
 298     ///
 299     /// # Panics
 300     ///
 301     /// Panics if the new capacity overflows `usize`.
 302     ///
 303     /// # Examples
 304     ///
 305     /// ```
 306     /// let mut vec = vec![1];
 307     /// vec.reserve(10);
 308     /// assert!(vec.capacity() >= 11);
 309     /// ```
 310     #[stable(feature = "rust1", since = "1.0.0")]
 311     pub fn reserve(&mut self, additional: usize) {
 312         if self.cap - self.len < additional {
 313             const ERR_MSG: &'static str  = "Vec::reserve: `isize` overflow";
 314
 315             let new_min_cap = self.len.checked_add(additional).expect(ERR_MSG);
 316             if new_min_cap > MAX_MEMORY_SIZE { panic!(ERR_MSG) }
 317             self.grow_capacity(match new_min_cap.checked_next_power_of_two() {
 318                 Some(x) if x > MAX_MEMORY_SIZE => MAX_MEMORY_SIZE,
 319                 None => MAX_MEMORY_SIZE,
 320                 Some(x) => x,
 321             });
 322         }
 323     }
 324
 325     /// Reserves the minimum capacity for exactly `additional` more elements to
 326     /// be inserted in the given `Vec<T>`. Does nothing if the capacity is already
 327     /// sufficient.
 328     ///
 329     /// Note that the allocator may give the collection more space than it
 330     /// requests. Therefore capacity can not be relied upon to be precisely
 331     /// minimal. Prefer `reserve` if future insertions are expected.
 332     ///
 333     /// # Panics
 334     ///
 335     /// Panics if the new capacity overflows `usize`.
 336     ///
 337     /// # Examples
 338     ///
 339     /// ```
 340     /// let mut vec = vec![1];
 341     /// vec.reserve_exact(10);
 342     /// assert!(vec.capacity() >= 11);
 343     /// ```
 344     #[stable(feature = "rust1", since = "1.0.0")]
 345     pub fn reserve_exact(&mut self, additional: usize) {
 346         if self.cap - self.len < additional {
 347             match self.len.checked_add(additional) {
 348                 None => panic!("Vec::reserve: `usize` overflow"),
 349                 Some(new_cap) => self.grow_capacity(new_cap)
 350             }
 351         }
 352     }
 353
 354     /// Shrinks the capacity of the vector as much as possible.
 355     ///
 356     /// It will drop down as close as possible to the length but the allocator
 357     /// may still inform the vector that there is space for a few more elements.
 358     ///
 359     /// # Examples
 360     ///
 361     /// ```
 362     /// # #![feature(collections)]
 363     /// let mut vec = Vec::with_capacity(10);
 364     /// vec.push_all(&[1, 2, 3]);
 365     /// assert_eq!(vec.capacity(), 10);
 366     /// vec.shrink_to_fit();
 367     /// assert!(vec.capacity() >= 3);
 368     /// ```
 369     #[stable(feature = "rust1", since = "1.0.0")]
 370     pub fn shrink_to_fit(&mut self) {
 371         if mem::size_of::<T>() == 0 { return }
 372
 373         if self.len == 0 {
 374             if self.cap != 0 {
 375                 unsafe {
 376                     dealloc(*self.ptr, self.cap)
 377                 }
 378                 self.cap = 0;
 379             }
 380         } else if self.cap != self.len {
 381             unsafe {
 382                 // Overflow check is unnecessary as the vector is already at
 383                 // least this large.
 384                 let ptr = reallocate(*self.ptr as *mut u8,
 385                                      self.cap * mem::size_of::<T>(),
 386                                      self.len * mem::size_of::<T>(),
 387                                      mem::min_align_of::<T>()) as *mut T;
 388                 if ptr.is_null() { ::alloc::oom() }
 389                 self.ptr = Unique::new(ptr);
 390             }
 391             self.cap = self.len;
 392         }
 393     }
 394
 395     /// Converts the vector into Box<[T]>.
 396     ///
 397     /// Note that this will drop any excess capacity. Calling this and
 398     /// converting back to a vector with `into_vec()` is equivalent to calling
 399     /// `shrink_to_fit()`.
 400     #[stable(feature = "rust1", since = "1.0.0")]
 401     pub fn into_boxed_slice(mut self) -> Box<[T]> {
 402         self.shrink_to_fit();
 403         unsafe {
 404             let xs: Box<[T]> = Box::from_raw(&mut *self);
 405             mem::forget(self);
 406             xs
 407         }
 408     }
 409
 410     /// Shorten a vector, dropping excess elements.
 411     ///
 412     /// If `len` is greater than the vector's current length, this has no
 413     /// effect.
 414     ///
 415     /// # Examples
 416     ///
 417     /// ```
 418     /// # #![feature(collections)]
 419     /// let mut vec = vec![1, 2, 3, 4];
 420     /// vec.truncate(2);
 421     /// assert_eq!(vec, [1, 2]);
 422     /// ```
 423     #[stable(feature = "rust1", since = "1.0.0")]
 424     pub fn truncate(&mut self, len: usize) {
 425         unsafe {
 426             // drop any extra elements
 427             while len < self.len {
 428                 // decrement len before the read(), so a panic on Drop doesn't
 429                 // re-drop the just-failed value.
 430                 self.len -= 1;
 431                 ptr::read(self.get_unchecked(self.len));
 432             }
 433         }
 434     }
 435
 436     /// Extracts a slice containing the entire vector.
 437     #[inline]
 438     #[unstable(feature = "convert",
 439                reason = "waiting on RFC revision")]
 440     pub fn as_slice(&self) -> &[T] {
 441         self
 442     }
 443
 444     /// Deprecated: use `&mut s[..]` instead.
 445     #[inline]
 446     #[unstable(feature = "convert",
 447                reason = "waiting on RFC revision")]
 448     pub fn as_mut_slice(&mut self) -> &mut [T] {
 449         &mut self[..]
 450     }
 451
 452     /// Sets the length of a vector.
 453     ///
 454     /// This will explicitly set the size of the vector, without actually
 455     /// modifying its buffers, so it is up to the caller to ensure that the
 456     /// vector is actually the specified size.
 457     ///
 458     /// # Examples
 459     ///
 460     /// ```
 461     /// let mut v = vec![1, 2, 3, 4];
 462     /// unsafe {
 463     ///     v.set_len(1);
 464     /// }
 465     /// ```
 466     #[inline]
 467     #[stable(feature = "rust1", since = "1.0.0")]
 468     pub unsafe fn set_len(&mut self, len: usize) {
 469         self.len = len;
 470     }
 471
 472     /// Removes an element from anywhere in the vector and return it, replacing
 473     /// it with the last element.
 474     ///
 475     /// This does not preserve ordering, but is O(1).
 476     ///
 477     /// # Panics
 478     ///
 479     /// Panics if `index` is out of bounds.
 480     ///
 481     /// # Examples
 482     ///
 483     /// ```
 484     /// let mut v = vec!["foo", "bar", "baz", "qux"];
 485     ///
 486     /// assert_eq!(v.swap_remove(1), "bar");
 487     /// assert_eq!(v, ["foo", "qux", "baz"]);
 488     ///
 489     /// assert_eq!(v.swap_remove(0), "foo");
 490     /// assert_eq!(v, ["baz", "qux"]);
 491     /// ```
 492     #[inline]
 493     #[stable(feature = "rust1", since = "1.0.0")]
 494     pub fn swap_remove(&mut self, index: usize) -> T {
 495         let length = self.len();
 496         self.swap(index, length - 1);
 497         self.pop().unwrap()
 498     }
 499
 500     /// Inserts an element at position `index` within the vector, shifting all
 501     /// elements after position `i` one position to the right.
 502     ///
 503     /// # Panics
 504     ///
 505     /// Panics if `index` is greater than the vector's length.
 506     ///
 507     /// # Examples
 508     ///
 509     /// ```
 510     /// let mut vec = vec![1, 2, 3];
 511     /// vec.insert(1, 4);
 512     /// assert_eq!(vec, [1, 4, 2, 3]);
 513     /// vec.insert(4, 5);
 514     /// assert_eq!(vec, [1, 4, 2, 3, 5]);
 515     /// ```
 516     #[stable(feature = "rust1", since = "1.0.0")]
 517     pub fn insert(&mut self, index: usize, element: T) {
 518         let len = self.len();
 519         assert!(index <= len);
 520         // space for the new element
 521         self.reserve(1);
 522
 523         unsafe { // infallible
 524             // The spot to put the new value
 525             {
 526                 let p = self.as_mut_ptr().offset(index as isize);
 527                 // Shift everything over to make space. (Duplicating the
 528                 // `index`th element into two consecutive places.)
 529                 ptr::copy(&*p, p.offset(1), len - index);
 530                 // Write it in, overwriting the first copy of the `index`th
 531                 // element.
 532                 ptr::write(&mut *p, element);
 533             }
 534             self.set_len(len + 1);
 535         }
 536     }
 537
 538     /// Removes and returns the element at position `index` within the vector,
 539     /// shifting all elements after position `index` one position to the left.
 540     ///
 541     /// # Panics
 542     ///
 543     /// Panics if `i` is out of bounds.
 544     ///
 545     /// # Examples
 546     ///
 547     /// ```
 548     /// # #![feature(collections)]
 549     /// let mut v = vec![1, 2, 3];
 550     /// assert_eq!(v.remove(1), 2);
 551     /// assert_eq!(v, [1, 3]);
 552     /// ```
 553     #[stable(feature = "rust1", since = "1.0.0")]
 554     pub fn remove(&mut self, index: usize) -> T {
 555         let len = self.len();
 556         assert!(index < len);
 557         unsafe { // infallible
 558             let ret;
 559             {
 560                 // the place we are taking from.
 561                 let ptr = self.as_mut_ptr().offset(index as isize);
 562                 // copy it out, unsafely having a copy of the value on
 563                 // the stack and in the vector at the same time.
 564                 ret = ptr::read(ptr);
 565
 566                 // Shift everything down to fill in that spot.
 567                 ptr::copy(&*ptr.offset(1), ptr, len - index - 1);
 568             }
 569             self.set_len(len - 1);
 570             ret
 571         }
 572     }
 573
 574     /// Retains only the elements specified by the predicate.
 575     ///
 576     /// In other words, remove all elements `e` such that `f(&e)` returns false.
 577     /// This method operates in place and preserves the order of the retained
 578     /// elements.
 579     ///
 580     /// # Examples
 581     ///
 582     /// ```
 583     /// let mut vec = vec![1, 2, 3, 4];
 584     /// vec.retain(|&x| x%2 == 0);
 585     /// assert_eq!(vec, [2, 4]);
 586     /// ```
 587     #[stable(feature = "rust1", since = "1.0.0")]
 588     pub fn retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool {
 589         let len = self.len();
 590         let mut del = 0;
 591         {
 592             let v = &mut **self;
 593
 594             for i in 0..len {
 595                 if !f(&v[i]) {
 596                     del += 1;
 597                 } else if del > 0 {
 598                     v.swap(i-del, i);
 599                 }
 600             }
 601         }
 602         if del > 0 {
 603             self.truncate(len - del);
 604         }
 605     }
 606
 607     /// Appends an element to the back of a collection.
 608     ///
 609     /// # Panics
 610     ///
 611     /// Panics if the number of elements in the vector overflows a `usize`.
 612     ///
 613     /// # Examples
 614     ///
 615     /// ```
 616     /// let mut vec = vec!(1, 2);
 617     /// vec.push(3);
 618     /// assert_eq!(vec, [1, 2, 3]);
 619     /// ```
 620     #[inline]
 621     #[stable(feature = "rust1", since = "1.0.0")]
 622     pub fn push(&mut self, value: T) {
 623         #[cold]
 624         #[inline(never)]
 625         fn resize<T>(vec: &mut Vec<T>) {
 626             let old_size = vec.cap * mem::size_of::<T>();
 627             if old_size >= MAX_MEMORY_SIZE { panic!("capacity overflow") }
 628             let mut size = max(old_size, 2 * mem::size_of::<T>()) * 2;
 629             if old_size > size || size > MAX_MEMORY_SIZE {
 630                 size = MAX_MEMORY_SIZE;
 631             }
 632             unsafe {
 633                 let ptr = alloc_or_realloc(*vec.ptr, old_size, size);
 634                 if ptr.is_null() { ::alloc::oom() }
 635                 vec.ptr = Unique::new(ptr);
 636             }
 637             vec.cap = max(vec.cap, 2) * 2;
 638         }
 639
 640         if mem::size_of::<T>() == 0 {
 641             // zero-size types consume no memory, so we can't rely on the
 642             // address space running out
 643             self.len = self.len.checked_add(1).expect("length overflow");
 644             unsafe { mem::forget(value); }
 645             return
 646         }
 647
 648         if self.len == self.cap {
 649             resize(self);
 650         }
 651
 652         unsafe {
 653             let end = (*self.ptr).offset(self.len as isize);
 654             ptr::write(&mut *end, value);
 655             self.len += 1;
 656         }
 657     }
 658
 659     /// Removes the last element from a vector and returns it, or `None` if it is empty.
 660     ///
 661     /// # Examples
 662     ///
 663     /// ```
 664     /// let mut vec = vec![1, 2, 3];
 665     /// assert_eq!(vec.pop(), Some(3));
 666     /// assert_eq!(vec, [1, 2]);
 667     /// ```
 668     #[inline]
 669     #[stable(feature = "rust1", since = "1.0.0")]
 670     pub fn pop(&mut self) -> Option<T> {
 671         if self.len == 0 {
 672             None
 673         } else {
 674             unsafe {
 675                 self.len -= 1;
 676                 Some(ptr::read(self.get_unchecked(self.len())))
 677             }
 678         }
 679     }
 680
 681     /// Moves all the elements of `other` into `Self`, leaving `other` empty.
 682     ///
 683     /// # Panics
 684     ///
 685     /// Panics if the number of elements in the vector overflows a `usize`.
 686     ///
 687     /// # Examples
 688     ///
 689     /// ```
 690     /// # #![feature(collections)]
 691     /// let mut vec = vec![1, 2, 3];
 692     /// let mut vec2 = vec![4, 5, 6];
 693     /// vec.append(&mut vec2);
 694     /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
 695     /// assert_eq!(vec2, []);
 696     /// ```
 697     #[inline]
 698     #[unstable(feature = "collections",
 699                reason = "new API, waiting for dust to settle")]
 700     pub fn append(&mut self, other: &mut Self) {
 701         if mem::size_of::<T>() == 0 {
 702             // zero-size types consume no memory, so we can't rely on the
 703             // address space running out
 704             self.len = self.len.checked_add(other.len()).expect("length overflow");
 705             unsafe { other.set_len(0) }
 706             return;
 707         }
 708         self.reserve(other.len());
 709         let len = self.len();
 710         unsafe {
 711             ptr::copy_nonoverlapping(
 712                 other.as_ptr(),
 713                 self.get_unchecked_mut(len),
 714                 other.len());
 715         }
 716
 717         self.len += other.len();
 718         unsafe { other.set_len(0); }
 719     }
 720
 721     /// Creates a draining iterator that clears the `Vec` and iterates over
 722     /// the removed items from start to end.
 723     ///
 724     /// # Examples
 725     ///
 726     /// ```
 727     /// # #![feature(collections)]
 728     /// let mut v = vec!["a".to_string(), "b".to_string()];
 729     /// for s in v.drain() {
 730     ///     // s has type String, not &String
 731     ///     println!("{}", s);
 732     /// }
 733     /// assert!(v.is_empty());
 734     /// ```
 735     #[inline]
 736     #[unstable(feature = "collections",
 737                reason = "matches collection reform specification, waiting for dust to settle")]
 738     pub fn drain(&mut self) -> Drain<T> {
 739         unsafe {
 740             let begin = *self.ptr as *const T;
 741             let end = if mem::size_of::<T>() == 0 {
 742                 (*self.ptr as usize + self.len()) as *const T
 743             } else {
 744                 (*self.ptr).offset(self.len() as isize) as *const T
 745             };
 746             self.set_len(0);
 747             Drain {
 748                 ptr: begin,
 749                 end: end,
 750                 marker: PhantomData,
 751             }
 752         }
 753     }
 754
 755     /// Clears the vector, removing all values.
 756     ///
 757     /// # Examples
 758     ///
 759     /// ```
 760     /// let mut v = vec![1, 2, 3];
 761     ///
 762     /// v.clear();
 763     ///
 764     /// assert!(v.is_empty());
 765     /// ```
 766     #[inline]
 767     #[stable(feature = "rust1", since = "1.0.0")]
 768     pub fn clear(&mut self) {
 769         self.truncate(0)
 770     }
 771
 772     /// Returns the number of elements in the vector.
 773     ///
 774     /// # Examples
 775     ///
 776     /// ```
 777     /// let a = vec![1, 2, 3];
 778     /// assert_eq!(a.len(), 3);
 779     /// ```
 780     #[inline]
 781     #[stable(feature = "rust1", since = "1.0.0")]
 782     pub fn len(&self) -> usize { self.len }
 783
 784     /// Returns `true` if the vector contains no elements.
 785     ///
 786     /// # Examples
 787     ///
 788     /// ```
 789     /// let mut v = Vec::new();
 790     /// assert!(v.is_empty());
 791     ///
 792     /// v.push(1);
 793     /// assert!(!v.is_empty());
 794     /// ```
 795     #[stable(feature = "rust1", since = "1.0.0")]
 796     pub fn is_empty(&self) -> bool { self.len() == 0 }
 797
 798     /// Converts a `Vec<T>` to a `Vec<U>` where `T` and `U` have the same
 799     /// size and in case they are not zero-sized the same minimal alignment.
 800     ///
 801     /// # Panics
 802     ///
 803     /// Panics if `T` and `U` have differing sizes or are not zero-sized and
 804     /// have differing minimal alignments.
 805     ///
 806     /// # Examples
 807     ///
 808     /// ```
 809     /// # #![feature(collections, core)]
 810     /// let v = vec![0, 1, 2];
 811     /// let w = v.map_in_place(|i| i + 3);
 812     /// assert_eq!(&w[..], &[3, 4, 5]);
 813     ///
 814     /// #[derive(PartialEq, Debug)]
 815     /// struct Newtype(u8);
 816     /// let bytes = vec![0x11, 0x22];
 817     /// let newtyped_bytes = bytes.map_in_place(|x| Newtype(x));
 818     /// assert_eq!(&newtyped_bytes[..], &[Newtype(0x11), Newtype(0x22)]);
 819     /// ```
 820     #[unstable(feature = "collections",
 821                reason = "API may change to provide stronger guarantees")]
 822     pub fn map_in_place<U, F>(self, mut f: F) -> Vec<U> where F: FnMut(T) -> U {
 823         // FIXME: Assert statically that the types `T` and `U` have the same
 824         // size.
 825         assert!(mem::size_of::<T>() == mem::size_of::<U>());
 826
 827         let mut vec = self;
 828
 829         if mem::size_of::<T>() != 0 {
 830             // FIXME: Assert statically that the types `T` and `U` have the
 831             // same minimal alignment in case they are not zero-sized.
 832
 833             // These asserts are necessary because the `min_align_of` of the
 834             // types are passed to the allocator by `Vec`.
 835             assert!(mem::min_align_of::<T>() == mem::min_align_of::<U>());
 836
 837             // This `as isize` cast is safe, because the size of the elements of the
 838             // vector is not 0, and:
 839             //
 840             // 1) If the size of the elements in the vector is 1, the `isize` may
 841             //    overflow, but it has the correct bit pattern so that the
 842             //    `.offset()` function will work.
 843             //
 844             //    Example:
 845             //        Address space 0x0-0xF.
 846             //        `u8` array at: 0x1.
 847             //        Size of `u8` array: 0x8.
 848             //        Calculated `offset`: -0x8.
 849             //        After `array.offset(offset)`: 0x9.
 850             //        (0x1 + 0x8 = 0x1 - 0x8)
 851             //
 852             // 2) If the size of the elements in the vector is >1, the `usize` ->
 853             //    `isize` conversion can't overflow.
 854             let offset = vec.len() as isize;
 855             let start = vec.as_mut_ptr();
 856
 857             let mut pv = PartialVecNonZeroSized {
 858                 vec: vec,
 859
 860                 start_t: start,
 861                 // This points inside the vector, as the vector has length
 862                 // `offset`.
 863                 end_t: unsafe { start.offset(offset) },
 864                 start_u: start as *mut U,
 865                 end_u: start as *mut U,
 866
 867                 _marker: PhantomData,
 868             };
 869             //  start_t
 870             //  start_u
 871             //  |
 872             // +-+-+-+-+-+-+
 873             // |T|T|T|...|T|
 874             // +-+-+-+-+-+-+
 875             //  |           |
 876             //  end_u       end_t
 877
 878             while pv.end_u as *mut T != pv.end_t {
 879                 unsafe {
 880                     //  start_u start_t
 881                     //  |       |
 882                     // +-+-+-+-+-+-+-+-+-+
 883                     // |U|...|U|T|T|...|T|
 884                     // +-+-+-+-+-+-+-+-+-+
 885                     //          |         |
 886                     //          end_u     end_t
 887
 888                     let t = ptr::read(pv.start_t);
 889                     //  start_u start_t
 890                     //  |       |
 891                     // +-+-+-+-+-+-+-+-+-+
 892                     // |U|...|U|X|T|...|T|
 893                     // +-+-+-+-+-+-+-+-+-+
 894                     //          |         |
 895                     //          end_u     end_t
 896                     // We must not panic here, one cell is marked as `T`
 897                     // although it is not `T`.
 898
 899                     pv.start_t = pv.start_t.offset(1);
 900                     //  start_u   start_t
 901                     //  |         |
 902                     // +-+-+-+-+-+-+-+-+-+
 903                     // |U|...|U|X|T|...|T|
 904                     // +-+-+-+-+-+-+-+-+-+
 905                     //          |         |
 906                     //          end_u     end_t
 907                     // We may panic again.
 908
 909                     // The function given by the user might panic.
 910                     let u = f(t);
 911
 912                     ptr::write(pv.end_u, u);
 913                     //  start_u   start_t
 914                     //  |         |
 915                     // +-+-+-+-+-+-+-+-+-+
 916                     // |U|...|U|U|T|...|T|
 917                     // +-+-+-+-+-+-+-+-+-+
 918                     //          |         |
 919                     //          end_u     end_t
 920                     // We should not panic here, because that would leak the `U`
 921                     // pointed to by `end_u`.
 922
 923                     pv.end_u = pv.end_u.offset(1);
 924                     //  start_u   start_t
 925                     //  |         |
 926                     // +-+-+-+-+-+-+-+-+-+
 927                     // |U|...|U|U|T|...|T|
 928                     // +-+-+-+-+-+-+-+-+-+
 929                     //            |       |
 930                     //            end_u   end_t
 931                     // We may panic again.
 932                 }
 933             }
 934
 935             //  start_u     start_t
 936             //  |           |
 937             // +-+-+-+-+-+-+
 938             // |U|...|U|U|U|
 939             // +-+-+-+-+-+-+
 940             //              |
 941             //              end_t
 942             //              end_u
 943             // Extract `vec` and prevent the destructor of
 944             // `PartialVecNonZeroSized` from running. Note that none of the
 945             // function calls can panic, thus no resources can be leaked (as the
 946             // `vec` member of `PartialVec` is the only one which holds
 947             // allocations -- and it is returned from this function. None of
 948             // this can panic.
 949             unsafe {
 950                 let vec_len = pv.vec.len();
 951                 let vec_cap = pv.vec.capacity();
 952                 let vec_ptr = pv.vec.as_mut_ptr() as *mut U;
 953                 mem::forget(pv);
 954                 Vec::from_raw_parts(vec_ptr, vec_len, vec_cap)
 955             }
 956         } else {
 957             // Put the `Vec` into the `PartialVecZeroSized` structure and
 958             // prevent the destructor of the `Vec` from running. Since the
 959             // `Vec` contained zero-sized objects, it did not allocate, so we
 960             // are not leaking memory here.
 961             let mut pv = PartialVecZeroSized::<T,U> {
 962                 num_t: vec.len(),
 963                 num_u: 0,
 964                 marker: PhantomData,
 965             };
 966             unsafe { mem::forget(vec); }
 967
 968             while pv.num_t != 0 {
 969                 unsafe {
 970                     // Create a `T` out of thin air and decrement `num_t`. This
 971                     // must not panic between these steps, as otherwise a
 972                     // destructor of `T` which doesn't exist runs.
 973                     let t = mem::uninitialized();
 974                     pv.num_t -= 1;
 975
 976                     // The function given by the user might panic.
 977                     let u = f(t);
 978
 979                     // Forget the `U` and increment `num_u`. This increment
 980                     // cannot overflow the `usize` as we only do this for a
 981                     // number of times that fits into a `usize` (and start with
 982                     // `0`). Again, we should not panic between these steps.
 983                     mem::forget(u);
 984                     pv.num_u += 1;
 985                 }
 986             }
 987             // Create a `Vec` from our `PartialVecZeroSized` and make sure the
 988             // destructor of the latter will not run. None of this can panic.
 989             let mut result = Vec::new();
 990             unsafe {
 991                 result.set_len(pv.num_u);
 992                 mem::forget(pv);
 993             }
 994             result
 995         }
 996     }
 997
 998     /// Splits the collection into two at the given index.
 999     ///
1000     /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
1001     /// and the returned `Self` contains elements `[at, len)`.
1002     ///
1003     /// Note that the capacity of `self` does not change.
1004     ///
1005     /// # Panics
1006     ///
1007     /// Panics if `at > len`.
1008     ///
1009     /// # Examples
1010     ///
1011     /// ```
1012     /// # #![feature(collections)]
1013     /// let mut vec = vec![1,2,3];
1014     /// let vec2 = vec.split_off(1);
1015     /// assert_eq!(vec, [1]);
1016     /// assert_eq!(vec2, [2, 3]);
1017     /// ```
1018     #[inline]
1019     #[unstable(feature = "collections",
1020                reason = "new API, waiting for dust to settle")]
1021     pub fn split_off(&mut self, at: usize) -> Self {
1022         assert!(at <= self.len(), "`at` out of bounds");
1023
1024         let other_len = self.len - at;
1025         let mut other = Vec::with_capacity(other_len);
1026
1027         // Unsafely `set_len` and copy items to `other`.
1028         unsafe {
1029             self.set_len(at);
1030             other.set_len(other_len);
1031
1032             ptr::copy_nonoverlapping(
1033                 self.as_ptr().offset(at as isize),
1034                 other.as_mut_ptr(),
1035                 other.len());
1036         }
1037         other
1038     }
1039
1040 }
1041
1042 impl<T: Clone> Vec<T> {
1043     /// Resizes the `Vec` in-place so that `len()` is equal to `new_len`.
1044     ///
1045     /// Calls either `extend()` or `truncate()` depending on whether `new_len`
1046     /// is larger than the current value of `len()` or not.
1047     ///
1048     /// # Examples
1049     ///
1050     /// ```
1051     /// # #![feature(collections)]
1052     /// let mut vec = vec!["hello"];
1053     /// vec.resize(3, "world");
1054     /// assert_eq!(vec, ["hello", "world", "world"]);
1055     ///
1056     /// let mut vec = vec![1, 2, 3, 4];
1057     /// vec.resize(2, 0);
1058     /// assert_eq!(vec, [1, 2]);
1059     /// ```
1060     #[unstable(feature = "collections",
1061                reason = "matches collection reform specification; waiting for dust to settle")]
1062     pub fn resize(&mut self, new_len: usize, value: T) {
1063         let len = self.len();
1064
1065         if new_len > len {
1066             self.extend(repeat(value).take(new_len - len));
1067         } else {
1068             self.truncate(new_len);
1069         }
1070     }
1071
1072     /// Appends all elements in a slice to the `Vec`.
1073     ///
1074     /// Iterates over the slice `other`, clones each element, and then appends
1075     /// it to this `Vec`. The `other` vector is traversed in-order.
1076     ///
1077     /// # Examples
1078     ///
1079     /// ```
1080     /// # #![feature(collections)]
1081     /// let mut vec = vec![1];
1082     /// vec.push_all(&[2, 3, 4]);
1083     /// assert_eq!(vec, [1, 2, 3, 4]);
1084     /// ```
1085     #[inline]
1086     #[unstable(feature = "collections",
1087                reason = "likely to be replaced by a more optimized extend")]
1088     pub fn push_all(&mut self, other: &[T]) {
1089         self.reserve(other.len());
1090
1091         for i in 0..other.len() {
1092             let len = self.len();
1093
1094             // Unsafe code so this can be optimised to a memcpy (or something similarly
1095             // fast) when T is Copy. LLVM is easily confused, so any extra operations
1096             // during the loop can prevent this optimisation.
1097             unsafe {
1098                 ptr::write(
1099                     self.get_unchecked_mut(len),
1100                     other.get_unchecked(i).clone());
1101                 self.set_len(len + 1);
1102             }
1103         }
1104     }
1105 }
1106
1107 impl<T: PartialEq> Vec<T> {
1108     /// Removes consecutive repeated elements in the vector.
1109     ///
1110     /// If the vector is sorted, this removes all duplicates.
1111     ///
1112     /// # Examples
1113     ///
1114     /// ```
1115     /// let mut vec = vec![1, 2, 2, 3, 2];
1116     ///
1117     /// vec.dedup();
1118     ///
1119     /// assert_eq!(vec, [1, 2, 3, 2]);
1120     /// ```
1121     #[stable(feature = "rust1", since = "1.0.0")]
1122     pub fn dedup(&mut self) {
1123         unsafe {
1124             // Although we have a mutable reference to `self`, we cannot make
1125             // *arbitrary* changes. The `PartialEq` comparisons could panic, so we
1126             // must ensure that the vector is in a valid state at all time.
1127             //
1128             // The way that we handle this is by using swaps; we iterate
1129             // over all the elements, swapping as we go so that at the end
1130             // the elements we wish to keep are in the front, and those we
1131             // wish to reject are at the back. We can then truncate the
1132             // vector. This operation is still O(n).
1133             //
1134             // Example: We start in this state, where `r` represents "next
1135             // read" and `w` represents "next_write`.
1136             //
1137             //           r
1138             //     +---+---+---+---+---+---+
1139             //     | 0 | 1 | 1 | 2 | 3 | 3 |
1140             //     +---+---+---+---+---+---+
1141             //           w
1142             //
1143             // Comparing self[r] against self[w-1], this is not a duplicate, so
1144             // we swap self[r] and self[w] (no effect as r==w) and then increment both
1145             // r and w, leaving us with:
1146             //
1147             //               r
1148             //     +---+---+---+---+---+---+
1149             //     | 0 | 1 | 1 | 2 | 3 | 3 |
1150             //     +---+---+---+---+---+---+
1151             //               w
1152             //
1153             // Comparing self[r] against self[w-1], this value is a duplicate,
1154             // so we increment `r` but leave everything else unchanged:
1155             //
1156             //                   r
1157             //     +---+---+---+---+---+---+
1158             //     | 0 | 1 | 1 | 2 | 3 | 3 |
1159             //     +---+---+---+---+---+---+
1160             //               w
1161             //
1162             // Comparing self[r] against self[w-1], this is not a duplicate,
1163             // so swap self[r] and self[w] and advance r and w:
1164             //
1165             //                       r
1166             //     +---+---+---+---+---+---+
1167             //     | 0 | 1 | 2 | 1 | 3 | 3 |
1168             //     +---+---+---+---+---+---+
1169             //                   w
1170             //
1171             // Not a duplicate, repeat:
1172             //
1173             //                           r
1174             //     +---+---+---+---+---+---+
1175             //     | 0 | 1 | 2 | 3 | 1 | 3 |
1176             //     +---+---+---+---+---+---+
1177             //                       w
1178             //
1179             // Duplicate, advance r. End of vec. Truncate to w.
1180
1181             let ln = self.len();
1182             if ln < 1 { return; }
1183
1184             // Avoid bounds checks by using unsafe pointers.
1185             let p = self.as_mut_ptr();
1186             let mut r: usize = 1;
1187             let mut w: usize = 1;
1188
1189             while r < ln {
1190                 let p_r = p.offset(r as isize);
1191                 let p_wm1 = p.offset((w - 1) as isize);
1192                 if *p_r != *p_wm1 {
1193                     if r != w {
1194                         let p_w = p_wm1.offset(1);
1195                         mem::swap(&mut *p_r, &mut *p_w);
1196                     }
1197                     w += 1;
1198                 }
1199                 r += 1;
1200             }
1201
1202             self.truncate(w);
1203         }
1204     }
1205 }
1206
1207 ////////////////////////////////////////////////////////////////////////////////
1208 // Internal methods and functions
1209 ////////////////////////////////////////////////////////////////////////////////
1210
1211 impl<T> Vec<T> {
1212     /// Reserves capacity for exactly `capacity` elements in the given vector.
1213     ///
1214     /// If the capacity for `self` is already equal to or greater than the
1215     /// requested capacity, then no action is taken.
1216     fn grow_capacity(&mut self, capacity: usize) {
1217         if mem::size_of::<T>() == 0 { return }
1218
1219         if capacity > self.cap {
1220             let size = capacity.checked_mul(mem::size_of::<T>())
1221                                .expect("capacity overflow");
1222             unsafe {
1223                 let ptr = alloc_or_realloc(*self.ptr, self.cap * mem::size_of::<T>(), size);
1224                 if ptr.is_null() { ::alloc::oom() }
1225                 self.ptr = Unique::new(ptr);
1226             }
1227             self.cap = capacity;
1228         }
1229     }
1230 }
1231
1232 // FIXME: #13996: need a way to mark the return value as `noalias`
1233 #[inline(never)]
1234 unsafe fn alloc_or_realloc<T>(ptr: *mut T, old_size: usize, size: usize) -> *mut T {
1235     if old_size == 0 {
1236         allocate(size, mem::min_align_of::<T>()) as *mut T
1237     } else {
1238         reallocate(ptr as *mut u8, old_size, size, mem::min_align_of::<T>()) as *mut T
1239     }
1240 }
1241
1242 #[inline]
1243 unsafe fn dealloc<T>(ptr: *mut T, len: usize) {
1244     if mem::size_of::<T>() != 0 {
1245         deallocate(ptr as *mut u8,
1246                    len * mem::size_of::<T>(),
1247                    mem::min_align_of::<T>())
1248     }
1249 }
1250
1251 #[doc(hidden)]
1252 #[stable(feature = "rust1", since = "1.0.0")]
1253 pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
1254     unsafe {
1255         let mut v = Vec::with_capacity(n);
1256         let mut ptr = v.as_mut_ptr();
1257
1258         // Write all elements except the last one
1259         for i in 1..n {
1260             ptr::write(ptr, Clone::clone(&elem));
1261             ptr = ptr.offset(1);
1262             v.set_len(i); // Increment the length in every step in case Clone::clone() panics
1263         }
1264
1265         if n > 0 {
1266             // We can write the last element directly without cloning needlessly
1267             ptr::write(ptr, elem);
1268             v.set_len(n);
1269         }
1270
1271         v
1272     }
1273 }
1274
1275 ////////////////////////////////////////////////////////////////////////////////
1276 // Common trait implementations for Vec
1277 ////////////////////////////////////////////////////////////////////////////////
1278
1279 #[unstable(feature = "collections")]
1280 impl<T:Clone> Clone for Vec<T> {
1281     #[cfg(not(test))]
1282     fn clone(&self) -> Vec<T> { <[T]>::to_vec(&**self) }
1283
1284     // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
1285     // required for this method definition, is not available. Instead use the
1286     // `slice::to_vec`  function which is only available with cfg(test)
1287     // NB see the slice::hack module in slice.rs for more information
1288     #[cfg(test)]
1289     fn clone(&self) -> Vec<T> {
1290         ::slice::to_vec(&**self)
1291     }
1292
1293     fn clone_from(&mut self, other: &Vec<T>) {
1294         // drop anything in self that will not be overwritten
1295         if self.len() > other.len() {
1296             self.truncate(other.len())
1297         }
1298
1299         // reuse the contained values' allocations/resources.
1300         for (place, thing) in self.iter_mut().zip(other.iter()) {
1301             place.clone_from(thing)
1302         }
1303
1304         // self.len <= other.len due to the truncate above, so the
1305         // slice here is always in-bounds.
1306         let slice = &other[self.len()..];
1307         self.push_all(slice);
1308     }
1309 }
1310
1311 #[stable(feature = "rust1", since = "1.0.0")]
1312 impl<T: Hash> Hash for Vec<T> {
1313     #[inline]
1314     fn hash<H: hash::Hasher>(&self, state: &mut H) {
1315         Hash::hash(&**self, state)
1316     }
1317 }
1318
1319 #[stable(feature = "rust1", since = "1.0.0")]
1320 impl<T> Index<usize> for Vec<T> {
1321     type Output = T;
1322
1323     #[inline]
1324     fn index(&self, index: usize) -> &T {
1325         // NB built-in indexing via `&[T]`
1326         &(**self)[index]
1327     }
1328 }
1329
1330 #[stable(feature = "rust1", since = "1.0.0")]
1331 impl<T> IndexMut<usize> for Vec<T> {
1332     #[inline]
1333     fn index_mut(&mut self, index: usize) -> &mut T {
1334         // NB built-in indexing via `&mut [T]`
1335         &mut (**self)[index]
1336     }
1337 }
1338
1339
1340 #[stable(feature = "rust1", since = "1.0.0")]
1341 impl<T> ops::Index<ops::Range<usize>> for Vec<T> {
1342     type Output = [T];
1343
1344     #[inline]
1345     fn index(&self, index: ops::Range<usize>) -> &[T] {
1346         Index::index(&**self, index)
1347     }
1348 }
1349 #[stable(feature = "rust1", since = "1.0.0")]
1350 impl<T> ops::Index<ops::RangeTo<usize>> for Vec<T> {
1351     type Output = [T];
1352
1353     #[inline]
1354     fn index(&self, index: ops::RangeTo<usize>) -> &[T] {
1355         Index::index(&**self, index)
1356     }
1357 }
1358 #[stable(feature = "rust1", since = "1.0.0")]
1359 impl<T> ops::Index<ops::RangeFrom<usize>> for Vec<T> {
1360     type Output = [T];
1361
1362     #[inline]
1363     fn index(&self, index: ops::RangeFrom<usize>) -> &[T] {
1364         Index::index(&**self, index)
1365     }
1366 }
1367 #[stable(feature = "rust1", since = "1.0.0")]
1368 impl<T> ops::Index<ops::RangeFull> for Vec<T> {
1369     type Output = [T];
1370
1371     #[inline]
1372     fn index(&self, _index: ops::RangeFull) -> &[T] {
1373         self
1374     }
1375 }
1376
1377 #[stable(feature = "rust1", since = "1.0.0")]
1378 impl<T> ops::IndexMut<ops::Range<usize>> for Vec<T> {
1379
1380     #[inline]
1381     fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] {
1382         IndexMut::index_mut(&mut **self, index)
1383     }
1384 }
1385 #[stable(feature = "rust1", since = "1.0.0")]
1386 impl<T> ops::IndexMut<ops::RangeTo<usize>> for Vec<T> {
1387
1388     #[inline]
1389     fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] {
1390         IndexMut::index_mut(&mut **self, index)
1391     }
1392 }
1393 #[stable(feature = "rust1", since = "1.0.0")]
1394 impl<T> ops::IndexMut<ops::RangeFrom<usize>> for Vec<T> {
1395
1396     #[inline]
1397     fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] {
1398         IndexMut::index_mut(&mut **self, index)
1399     }
1400 }
1401 #[stable(feature = "rust1", since = "1.0.0")]
1402 impl<T> ops::IndexMut<ops::RangeFull> for Vec<T> {
1403
1404     #[inline]
1405     fn index_mut(&mut self, _index: ops::RangeFull) -> &mut [T] {
1406         self
1407     }
1408 }
1409
1410 #[stable(feature = "rust1", since = "1.0.0")]
1411 impl<T> ops::Deref for Vec<T> {
1412     type Target = [T];
1413
1414     fn deref(&self) -> &[T] {
1415         unsafe {
1416             let p = *self.ptr;
1417             assume(p != 0 as *mut T);
1418             slice::from_raw_parts(p, self.len)
1419         }
1420     }
1421 }
1422
1423 #[stable(feature = "rust1", since = "1.0.0")]
1424 impl<T> ops::DerefMut for Vec<T> {
1425     fn deref_mut(&mut self) -> &mut [T] {
1426         unsafe {
1427             let ptr = *self.ptr;
1428             assume(!ptr.is_null());
1429             slice::from_raw_parts_mut(ptr, self.len)
1430         }
1431     }
1432 }
1433
1434 #[stable(feature = "rust1", since = "1.0.0")]
1435 impl<T> FromIterator<T> for Vec<T> {
1436     #[inline]
1437     fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> Vec<T> {
1438         let mut iterator = iterable.into_iter();
1439         let (lower, _) = iterator.size_hint();
1440         let mut vector = Vec::with_capacity(lower);
1441
1442         // This function should be the moral equivalent of:
1443         //
1444         //      for item in iterator {
1445         //          vector.push(item);
1446         //      }
1447         //
1448         // This equivalent crucially runs the iterator precisely once. Below we
1449         // actually in theory run the iterator twice (one without bounds checks
1450         // and one with). To achieve the "moral equivalent", we use the `if`
1451         // statement below to break out early.
1452         //
1453         // If the first loop has terminated, then we have one of two conditions.
1454         //
1455         // 1. The underlying iterator returned `None`. In this case we are
1456         //    guaranteed that less than `vector.capacity()` elements have been
1457         //    returned, so we break out early.
1458         // 2. The underlying iterator yielded `vector.capacity()` elements and
1459         //    has not yielded `None` yet. In this case we run the iterator to
1460         //    its end below.
1461         for element in iterator.by_ref().take(vector.capacity()) {
1462             let len = vector.len();
1463             unsafe {
1464                 ptr::write(vector.get_unchecked_mut(len), element);
1465                 vector.set_len(len + 1);
1466             }
1467         }
1468
1469         if vector.len() == vector.capacity() {
1470             for element in iterator {
1471                 vector.push(element);
1472             }
1473         }
1474         vector
1475     }
1476 }
1477
1478 #[stable(feature = "rust1", since = "1.0.0")]
1479 impl<T> IntoIterator for Vec<T> {
1480     type Item = T;
1481     type IntoIter = IntoIter<T>;
1482
1483     /// Creates a consuming iterator, that is, one that moves each value out of
1484     /// the vector (from start to end). The vector cannot be used after calling
1485     /// this.
1486     ///
1487     /// # Examples
1488     ///
1489     /// ```
1490     /// let v = vec!["a".to_string(), "b".to_string()];
1491     /// for s in v.into_iter() {
1492     ///     // s has type String, not &String
1493     ///     println!("{}", s);
1494     /// }
1495     /// ```
1496     #[inline]
1497     fn into_iter(self) -> IntoIter<T> {
1498         unsafe {
1499             let ptr = *self.ptr;
1500             assume(!ptr.is_null());
1501             let cap = self.cap;
1502             let begin = ptr as *const T;
1503             let end = if mem::size_of::<T>() == 0 {
1504                 (ptr as usize + self.len()) as *const T
1505             } else {
1506                 ptr.offset(self.len() as isize) as *const T
1507             };
1508             mem::forget(self);
1509             IntoIter { allocation: ptr, cap: cap, ptr: begin, end: end }
1510         }
1511     }
1512 }
1513
1514 #[stable(feature = "rust1", since = "1.0.0")]
1515 impl<'a, T> IntoIterator for &'a Vec<T> {
1516     type Item = &'a T;
1517     type IntoIter = slice::Iter<'a, T>;
1518
1519     fn into_iter(self) -> slice::Iter<'a, T> {
1520         self.iter()
1521     }
1522 }
1523
1524 #[stable(feature = "rust1", since = "1.0.0")]
1525 impl<'a, T> IntoIterator for &'a mut Vec<T> {
1526     type Item = &'a mut T;
1527     type IntoIter = slice::IterMut<'a, T>;
1528
1529     fn into_iter(mut self) -> slice::IterMut<'a, T> {
1530         self.iter_mut()
1531     }
1532 }
1533
1534 #[unstable(feature = "collections", reason = "waiting on Extend stability")]
1535 impl<T> Extend<T> for Vec<T> {
1536     #[inline]
1537     fn extend<I: IntoIterator<Item=T>>(&mut self, iterable: I) {
1538         let iterator = iterable.into_iter();
1539         let (lower, _) = iterator.size_hint();
1540         self.reserve(lower);
1541         for element in iterator {
1542             self.push(element)
1543         }
1544     }
1545 }
1546
1547 __impl_slice_eq1! { Vec<A>, Vec<B> }
1548 __impl_slice_eq1! { Vec<A>, &'b [B] }
1549 __impl_slice_eq1! { Vec<A>, &'b mut [B] }
1550 __impl_slice_eq1! { Cow<'a, [A]>, &'b [B], Clone }
1551 __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B], Clone }
1552 __impl_slice_eq1! { Cow<'a, [A]>, Vec<B>, Clone }
1553
1554 macro_rules! array_impls {
1555     ($($N: expr)+) => {
1556         $(
1557             // NOTE: some less important impls are omitted to reduce code bloat
1558             __impl_slice_eq1! { Vec<A>, [B; $N] }
1559             __impl_slice_eq1! { Vec<A>, &'b [B; $N] }
1560             // __impl_slice_eq1! { Vec<A>, &'b mut [B; $N] }
1561             // __impl_slice_eq1! { Cow<'a, [A]>, [B; $N], Clone }
1562             // __impl_slice_eq1! { Cow<'a, [A]>, &'b [B; $N], Clone }
1563             // __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B; $N], Clone }
1564         )+
1565     }
1566 }
1567
1568 array_impls! {
1569      0  1  2  3  4  5  6  7  8  9
1570     10 11 12 13 14 15 16 17 18 19
1571     20 21 22 23 24 25 26 27 28 29
1572     30 31 32
1573 }
1574
1575 #[stable(feature = "rust1", since = "1.0.0")]
1576 impl<T: PartialOrd> PartialOrd for Vec<T> {
1577     #[inline]
1578     fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
1579         PartialOrd::partial_cmp(&**self, &**other)
1580     }
1581 }
1582
1583 #[stable(feature = "rust1", since = "1.0.0")]
1584 impl<T: Eq> Eq for Vec<T> {}
1585
1586 #[stable(feature = "rust1", since = "1.0.0")]
1587 impl<T: Ord> Ord for Vec<T> {
1588     #[inline]
1589     fn cmp(&self, other: &Vec<T>) -> Ordering {
1590         Ord::cmp(&**self, &**other)
1591     }
1592 }
1593
1594 #[unstable(feature = "collections",
1595            reason = "recent addition, needs more experience")]
1596 impl<'a, T: Clone> Add<&'a [T]> for Vec<T> {
1597     type Output = Vec<T>;
1598
1599     #[inline]
1600     fn add(mut self, rhs: &[T]) -> Vec<T> {
1601         self.push_all(rhs);
1602         self
1603     }
1604 }
1605
1606 #[unsafe_destructor]
1607 #[stable(feature = "rust1", since = "1.0.0")]
1608 impl<T> Drop for Vec<T> {
1609     fn drop(&mut self) {
1610         // This is (and should always remain) a no-op if the fields are
1611         // zeroed (when moving out, because of #[unsafe_no_drop_flag]).
1612         if self.cap != 0 && self.cap != mem::POST_DROP_USIZE {
1613             unsafe {
1614                 for x in &*self {
1615                     ptr::read(x);
1616                 }
1617                 dealloc(*self.ptr, self.cap)
1618             }
1619         }
1620     }
1621 }
1622
1623 #[stable(feature = "rust1", since = "1.0.0")]
1624 impl<T> Default for Vec<T> {
1625     #[stable(feature = "rust1", since = "1.0.0")]
1626     fn default() -> Vec<T> {
1627         Vec::new()
1628     }
1629 }
1630
1631 #[stable(feature = "rust1", since = "1.0.0")]
1632 impl<T: fmt::Debug> fmt::Debug for Vec<T> {
1633     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1634         fmt::Debug::fmt(&**self, f)
1635     }
1636 }
1637
1638 #[stable(feature = "rust1", since = "1.0.0")]
1639 impl<T> AsRef<Vec<T>> for Vec<T> {
1640     fn as_ref(&self) -> &Vec<T> {
1641         self
1642     }
1643 }
1644
1645 #[stable(feature = "rust1", since = "1.0.0")]
1646 impl<T> AsRef<[T]> for Vec<T> {
1647     fn as_ref(&self) -> &[T] {
1648         self
1649     }
1650 }
1651
1652 #[stable(feature = "rust1", since = "1.0.0")]
1653 impl<'a, T: Clone> From<&'a [T]> for Vec<T> {
1654     #[cfg(not(test))]
1655     fn from(s: &'a [T]) -> Vec<T> {
1656         s.to_vec()
1657     }
1658     #[cfg(test)]
1659     fn from(s: &'a [T]) -> Vec<T> {
1660         ::slice::to_vec(s)
1661     }
1662 }
1663
1664 #[stable(feature = "rust1", since = "1.0.0")]
1665 impl<'a> From<&'a str> for Vec<u8> {
1666     fn from(s: &'a str) -> Vec<u8> {
1667         From::from(s.as_bytes())
1668     }
1669 }
1670
1671 ////////////////////////////////////////////////////////////////////////////////
1672 // Clone-on-write
1673 ////////////////////////////////////////////////////////////////////////////////
1674
1675 #[unstable(feature = "collections")]
1676 impl<'a, T> FromIterator<T> for Cow<'a, [T]> where T: Clone {
1677     fn from_iter<I: IntoIterator<Item=T>>(it: I) -> Cow<'a, [T]> {
1678         Cow::Owned(FromIterator::from_iter(it))
1679     }
1680 }
1681
1682 impl<'a, T: 'a> IntoCow<'a, [T]> for Vec<T> where T: Clone {
1683     fn into_cow(self) -> Cow<'a, [T]> {
1684         Cow::Owned(self)
1685     }
1686 }
1687
1688 impl<'a, T> IntoCow<'a, [T]> for &'a [T] where T: Clone {
1689     fn into_cow(self) -> Cow<'a, [T]> {
1690         Cow::Borrowed(self)
1691     }
1692 }
1693
1694 ////////////////////////////////////////////////////////////////////////////////
1695 // Iterators
1696 ////////////////////////////////////////////////////////////////////////////////
1697
1698 /// An iterator that moves out of a vector.
1699 #[stable(feature = "rust1", since = "1.0.0")]
1700 pub struct IntoIter<T> {
1701     allocation: *mut T, // the block of memory allocated for the vector
1702     cap: usize, // the capacity of the vector
1703     ptr: *const T,
1704     end: *const T
1705 }
1706
1707 unsafe impl<T: Send> Send for IntoIter<T> { }
1708 unsafe impl<T: Sync> Sync for IntoIter<T> { }
1709
1710 impl<T> IntoIter<T> {
1711     #[inline]
1712     /// Drops all items that have not yet been moved and returns the empty vector.
1713     #[unstable(feature = "collections")]
1714     pub fn into_inner(mut self) -> Vec<T> {
1715         unsafe {
1716             for _x in self.by_ref() { }
1717             let IntoIter { allocation, cap, ptr: _ptr, end: _end } = self;
1718             mem::forget(self);
1719             Vec::from_raw_parts(allocation, 0, cap)
1720         }
1721     }
1722 }
1723
1724 #[stable(feature = "rust1", since = "1.0.0")]
1725 impl<T> Iterator for IntoIter<T> {
1726     type Item = T;
1727
1728     #[inline]
1729     fn next(&mut self) -> Option<T> {
1730         unsafe {
1731             if self.ptr == self.end {
1732                 None
1733             } else {
1734                 if mem::size_of::<T>() == 0 {
1735                     // purposefully don't use 'ptr.offset' because for
1736                     // vectors with 0-size elements this would return the
1737                     // same pointer.
1738                     self.ptr = mem::transmute(self.ptr as usize + 1);
1739
1740                     // Use a non-null pointer value
1741                     Some(ptr::read(EMPTY as *mut T))
1742                 } else {
1743                     let old = self.ptr;
1744                     self.ptr = self.ptr.offset(1);
1745
1746                     Some(ptr::read(old))
1747                 }
1748             }
1749         }
1750     }
1751
1752     #[inline]
1753     fn size_hint(&self) -> (usize, Option<usize>) {
1754         let diff = (self.end as usize) - (self.ptr as usize);
1755         let size = mem::size_of::<T>();
1756         let exact = diff / (if size == 0 {1} else {size});
1757         (exact, Some(exact))
1758     }
1759 }
1760
1761 #[stable(feature = "rust1", since = "1.0.0")]
1762 impl<T> DoubleEndedIterator for IntoIter<T> {
1763     #[inline]
1764     fn next_back(&mut self) -> Option<T> {
1765         unsafe {
1766             if self.end == self.ptr {
1767                 None
1768             } else {
1769                 if mem::size_of::<T>() == 0 {
1770                     // See above for why 'ptr.offset' isn't used
1771                     self.end = mem::transmute(self.end as usize - 1);
1772
1773                     // Use a non-null pointer value
1774                     Some(ptr::read(EMPTY as *mut T))
1775                 } else {
1776                     self.end = self.end.offset(-1);
1777
1778                     Some(ptr::read(mem::transmute(self.end)))
1779                 }
1780             }
1781         }
1782     }
1783 }
1784
1785 #[stable(feature = "rust1", since = "1.0.0")]
1786 impl<T> ExactSizeIterator for IntoIter<T> {}
1787
1788 #[unsafe_destructor]
1789 #[stable(feature = "rust1", since = "1.0.0")]
1790 impl<T> Drop for IntoIter<T> {
1791     fn drop(&mut self) {
1792         // destroy the remaining elements
1793         if self.cap != 0 {
1794             for _x in self.by_ref() {}
1795             unsafe {
1796                 dealloc(self.allocation, self.cap);
1797             }
1798         }
1799     }
1800 }
1801
1802 /// An iterator that drains a vector.
1803 #[unsafe_no_drop_flag]
1804 #[unstable(feature = "collections",
1805            reason = "recently added as part of collections reform 2")]
1806 pub struct Drain<'a, T:'a> {
1807     ptr: *const T,
1808     end: *const T,
1809     marker: PhantomData<&'a T>,
1810 }
1811
1812 unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
1813 unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
1814
1815 #[stable(feature = "rust1", since = "1.0.0")]
1816 impl<'a, T> Iterator for Drain<'a, T> {
1817     type Item = T;
1818
1819     #[inline]
1820     fn next(&mut self) -> Option<T> {
1821         unsafe {
1822             if self.ptr == self.end {
1823                 None
1824             } else {
1825                 if mem::size_of::<T>() == 0 {
1826                     // purposefully don't use 'ptr.offset' because for
1827                     // vectors with 0-size elements this would return the
1828                     // same pointer.
1829                     self.ptr = mem::transmute(self.ptr as usize + 1);
1830
1831                     // Use a non-null pointer value
1832                     Some(ptr::read(EMPTY as *mut T))
1833                 } else {
1834                     let old = self.ptr;
1835                     self.ptr = self.ptr.offset(1);
1836
1837                     Some(ptr::read(old))
1838                 }
1839             }
1840         }
1841     }
1842
1843     #[inline]
1844     fn size_hint(&self) -> (usize, Option<usize>) {
1845         let diff = (self.end as usize) - (self.ptr as usize);
1846         let size = mem::size_of::<T>();
1847         let exact = diff / (if size == 0 {1} else {size});
1848         (exact, Some(exact))
1849     }
1850 }
1851
1852 #[stable(feature = "rust1", since = "1.0.0")]
1853 impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
1854     #[inline]
1855     fn next_back(&mut self) -> Option<T> {
1856         unsafe {
1857             if self.end == self.ptr {
1858                 None
1859             } else {
1860                 if mem::size_of::<T>() == 0 {
1861                     // See above for why 'ptr.offset' isn't used
1862                     self.end = mem::transmute(self.end as usize - 1);
1863
1864                     // Use a non-null pointer value
1865                     Some(ptr::read(EMPTY as *mut T))
1866                 } else {
1867                     self.end = self.end.offset(-1);
1868
1869                     Some(ptr::read(self.end))
1870                 }
1871             }
1872         }
1873     }
1874 }
1875
1876 #[stable(feature = "rust1", since = "1.0.0")]
1877 impl<'a, T> ExactSizeIterator for Drain<'a, T> {}
1878
1879 #[unsafe_destructor]
1880 #[stable(feature = "rust1", since = "1.0.0")]
1881 impl<'a, T> Drop for Drain<'a, T> {
1882     fn drop(&mut self) {
1883         // self.ptr == self.end == mem::POST_DROP_USIZE if drop has already been called,
1884         // so we can use #[unsafe_no_drop_flag].
1885
1886         // destroy the remaining elements
1887         for _x in self.by_ref() {}
1888     }
1889 }
1890
1891 ////////////////////////////////////////////////////////////////////////////////
1892 // Conversion from &[T] to &Vec<T>
1893 ////////////////////////////////////////////////////////////////////////////////
1894
1895 /// Wrapper type providing a `&Vec<T>` reference via `Deref`.
1896 #[unstable(feature = "collections")]
1897 pub struct DerefVec<'a, T:'a> {
1898     x: Vec<T>,
1899     l: PhantomData<&'a T>,
1900 }
1901
1902 #[unstable(feature = "collections")]
1903 impl<'a, T> Deref for DerefVec<'a, T> {
1904     type Target = Vec<T>;
1905
1906     fn deref<'b>(&'b self) -> &'b Vec<T> {
1907         &self.x
1908     }
1909 }
1910
1911 // Prevent the inner `Vec<T>` from attempting to deallocate memory.
1912 #[unsafe_destructor]
1913 #[stable(feature = "rust1", since = "1.0.0")]
1914 impl<'a, T> Drop for DerefVec<'a, T> {
1915     fn drop(&mut self) {
1916         self.x.len = 0;
1917         self.x.cap = 0;
1918     }
1919 }
1920
1921 /// Converts a slice to a wrapper type providing a `&Vec<T>` reference.
1922 #[unstable(feature = "collections")]
1923 pub fn as_vec<'a, T>(x: &'a [T]) -> DerefVec<'a, T> {
1924     unsafe {
1925         DerefVec {
1926             x: Vec::from_raw_parts(x.as_ptr() as *mut T, x.len(), x.len()),
1927             l: PhantomData,
1928         }
1929     }
1930 }
1931
1932 ////////////////////////////////////////////////////////////////////////////////
1933 // Partial vec, used for map_in_place
1934 ////////////////////////////////////////////////////////////////////////////////
1935
1936 /// An owned, partially type-converted vector of elements with non-zero size.
1937 ///
1938 /// `T` and `U` must have the same, non-zero size. They must also have the same
1939 /// alignment.
1940 ///
1941 /// When the destructor of this struct runs, all `U`s from `start_u` (incl.) to
1942 /// `end_u` (excl.) and all `T`s from `start_t` (incl.) to `end_t` (excl.) are
1943 /// destructed. Additionally the underlying storage of `vec` will be freed.
1944 struct PartialVecNonZeroSized<T,U> {
1945     vec: Vec<T>,
1946
1947     start_u: *mut U,
1948     end_u: *mut U,
1949     start_t: *mut T,
1950     end_t: *mut T,
1951
1952     _marker: PhantomData<U>,
1953 }
1954
1955 /// An owned, partially type-converted vector of zero-sized elements.
1956 ///
1957 /// When the destructor of this struct runs, all `num_t` `T`s and `num_u` `U`s
1958 /// are destructed.
1959 struct PartialVecZeroSized<T,U> {
1960     num_t: usize,
1961     num_u: usize,
1962     marker: PhantomData<::core::cell::Cell<(T,U)>>,
1963 }
1964
1965 #[unsafe_destructor]
1966 impl<T,U> Drop for PartialVecNonZeroSized<T,U> {
1967     fn drop(&mut self) {
1968         unsafe {
1969             // `vec` hasn't been modified until now. As it has a length
1970             // currently, this would run destructors of `T`s which might not be
1971             // there. So at first, set `vec`s length to `0`. This must be done
1972             // at first to remain memory-safe as the destructors of `U` or `T`
1973             // might cause unwinding where `vec`s destructor would be executed.
1974             self.vec.set_len(0);
1975
1976             // We have instances of `U`s and `T`s in `vec`. Destruct them.
1977             while self.start_u != self.end_u {
1978                 let _ = ptr::read(self.start_u); // Run a `U` destructor.
1979                 self.start_u = self.start_u.offset(1);
1980             }
1981             while self.start_t != self.end_t {
1982                 let _ = ptr::read(self.start_t); // Run a `T` destructor.
1983                 self.start_t = self.start_t.offset(1);
1984             }
1985             // After this destructor ran, the destructor of `vec` will run,
1986             // deallocating the underlying memory.
1987         }
1988     }
1989 }
1990
1991 #[unsafe_destructor]
1992 impl<T,U> Drop for PartialVecZeroSized<T,U> {
1993     fn drop(&mut self) {
1994         unsafe {
1995             // Destruct the instances of `T` and `U` this struct owns.
1996             while self.num_t != 0 {
1997                 let _: T = mem::uninitialized(); // Run a `T` destructor.
1998                 self.num_t -= 1;
1999             }
2000             while self.num_u != 0 {
2001                 let _: U = mem::uninitialized(); // Run a `U` destructor.
2002                 self.num_u -= 1;
2003             }
2004         }
2005     }
2006 }