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