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