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