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 contiguous growable array type with heap-allocated contents, written
  12 //! `Vec<T>` but pronounced 'vector.'
  13 //!
  14 //! Vectors have `O(1)` indexing, amortized `O(1)` push (to the end) and
  15 //! `O(1)` pop (from the end).
  16 //!
  17 //! # Examples
  18 //!
  19 //! You can explicitly create a [`Vec<T>`] with [`new`]:
  20 //!
  21 //! ```
  22 //! let v: Vec<i32> = Vec::new();
  23 //! ```
  24 //!
  25 //! ...or by using the [`vec!`] macro:
  26 //!
  27 //! ```
  28 //! let v: Vec<i32> = vec![];
  29 //!
  30 //! let v = vec![1, 2, 3, 4, 5];
  31 //!
  32 //! let v = vec![0; 10]; // ten zeroes
  33 //! ```
  34 //!
  35 //! You can [`push`] values onto the end of a vector (which will grow the vector
  36 //! as needed):
  37 //!
  38 //! ```
  39 //! let mut v = vec![1, 2];
  40 //!
  41 //! v.push(3);
  42 //! ```
  43 //!
  44 //! Popping values works in much the same way:
  45 //!
  46 //! ```
  47 //! let mut v = vec![1, 2];
  48 //!
  49 //! let two = v.pop();
  50 //! ```
  51 //!
  52 //! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits):
  53 //!
  54 //! ```
  55 //! let mut v = vec![1, 2, 3];
  56 //! let three = v[2];
  57 //! v[1] = v[1] + 5;
  58 //! ```
  59 //!
  60 //! [`Vec<T>`]: ../../std/vec/struct.Vec.html
  61 //! [`new`]: ../../std/vec/struct.Vec.html#method.new
  62 //! [`push`]: ../../std/vec/struct.Vec.html#method.push
  63 //! [`Index`]: ../../std/ops/trait.Index.html
  64 //! [`IndexMut`]: ../../std/ops/trait.IndexMut.html
  65 //! [`vec!`]: ../../std/macro.vec.html
  66
  67 #![stable(feature = "rust1", since = "1.0.0")]
  68
  69 use alloc::boxed::Box;
  70 use alloc::heap::EMPTY;
  71 use alloc::raw_vec::RawVec;
  72 use borrow::ToOwned;
  73 use borrow::Cow;
  74 use core::cmp::Ordering;
  75 use core::fmt;
  76 use core::hash::{self, Hash};
  77 use core::intrinsics::{arith_offset, assume};
  78 use core::iter::{FromIterator, FusedIterator, TrustedLen};
  79 use core::mem;
  80 use core::ops::{InPlace, Index, IndexMut, Place, Placer};
  81 use core::ops;
  82 use core::ptr;
  83 use core::ptr::Shared;
  84 use core::slice;
  85
  86 use super::range::RangeArgument;
  87 use Bound::{Excluded, Included, Unbounded};
  88
  89 /// A contiguous growable array type, written `Vec<T>` but pronounced 'vector'.
  90 ///
  91 /// # Examples
  92 ///
  93 /// ```
  94 /// let mut vec = Vec::new();
  95 /// vec.push(1);
  96 /// vec.push(2);
  97 ///
  98 /// assert_eq!(vec.len(), 2);
  99 /// assert_eq!(vec[0], 1);
 100 ///
 101 /// assert_eq!(vec.pop(), Some(2));
 102 /// assert_eq!(vec.len(), 1);
 103 ///
 104 /// vec[0] = 7;
 105 /// assert_eq!(vec[0], 7);
 106 ///
 107 /// vec.extend([1, 2, 3].iter().cloned());
 108 ///
 109 /// for x in &vec {
 110 ///     println!("{}", x);
 111 /// }
 112 /// assert_eq!(vec, [7, 1, 2, 3]);
 113 /// ```
 114 ///
 115 /// The [`vec!`] macro is provided to make initialization more convenient:
 116 ///
 117 /// ```
 118 /// let mut vec = vec![1, 2, 3];
 119 /// vec.push(4);
 120 /// assert_eq!(vec, [1, 2, 3, 4]);
 121 /// ```
 122 ///
 123 /// It can also initialize each element of a `Vec<T>` with a given value:
 124 ///
 125 /// ```
 126 /// let vec = vec![0; 5];
 127 /// assert_eq!(vec, [0, 0, 0, 0, 0]);
 128 /// ```
 129 ///
 130 /// Use a `Vec<T>` as an efficient stack:
 131 ///
 132 /// ```
 133 /// let mut stack = Vec::new();
 134 ///
 135 /// stack.push(1);
 136 /// stack.push(2);
 137 /// stack.push(3);
 138 ///
 139 /// while let Some(top) = stack.pop() {
 140 ///     // Prints 3, 2, 1
 141 ///     println!("{}", top);
 142 /// }
 143 /// ```
 144 ///
 145 /// # Indexing
 146 ///
 147 /// The `Vec` type allows to access values by index, because it implements the
 148 /// [`Index`] trait. An example will be more explicit:
 149 ///
 150 /// ```
 151 /// let v = vec![0, 2, 4, 6];
 152 /// println!("{}", v[1]); // it will display '2'
 153 /// ```
 154 ///
 155 /// However be careful: if you try to access an index which isn't in the `Vec`,
 156 /// your software will panic! You cannot do this:
 157 ///
 158 /// ```ignore
 159 /// let v = vec![0, 2, 4, 6];
 160 /// println!("{}", v[6]); // it will panic!
 161 /// ```
 162 ///
 163 /// In conclusion: always check if the index you want to get really exists
 164 /// before doing it.
 165 ///
 166 /// # Slicing
 167 ///
 168 /// A `Vec` can be mutable. Slices, on the other hand, are read-only objects.
 169 /// To get a slice, use `&`. Example:
 170 ///
 171 /// ```
 172 /// fn read_slice(slice: &[usize]) {
 173 ///     // ...
 174 /// }
 175 ///
 176 /// let v = vec![0, 1];
 177 /// read_slice(&v);
 178 ///
 179 /// // ... and that's all!
 180 /// // you can also do it like this:
 181 /// let x : &[usize] = &v;
 182 /// ```
 183 ///
 184 /// In Rust, it's more common to pass slices as arguments rather than vectors
 185 /// when you just want to provide a read access. The same goes for [`String`] and
 186 /// [`&str`].
 187 ///
 188 /// # Capacity and reallocation
 189 ///
 190 /// The capacity of a vector is the amount of space allocated for any future
 191 /// elements that will be added onto the vector. This is not to be confused with
 192 /// the *length* of a vector, which specifies the number of actual elements
 193 /// within the vector. If a vector's length exceeds its capacity, its capacity
 194 /// will automatically be increased, but its elements will have to be
 195 /// reallocated.
 196 ///
 197 /// For example, a vector with capacity 10 and length 0 would be an empty vector
 198 /// with space for 10 more elements. Pushing 10 or fewer elements onto the
 199 /// vector will not change its capacity or cause reallocation to occur. However,
 200 /// if the vector's length is increased to 11, it will have to reallocate, which
 201 /// can be slow. For this reason, it is recommended to use [`Vec::with_capacity`]
 202 /// whenever possible to specify how big the vector is expected to get.
 203 ///
 204 /// # Guarantees
 205 ///
 206 /// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees
 207 /// about its design. This ensures that it's as low-overhead as possible in
 208 /// the general case, and can be correctly manipulated in primitive ways
 209 /// by unsafe code. Note that these guarantees refer to an unqualified `Vec<T>`.
 210 /// If additional type parameters are added (e.g. to support custom allocators),
 211 /// overriding their defaults may change the behavior.
 212 ///
 213 /// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length)
 214 /// triplet. No more, no less. The order of these fields is completely
 215 /// unspecified, and you should use the appropriate methods to modify these.
 216 /// The pointer will never be null, so this type is null-pointer-optimized.
 217 ///
 218 /// However, the pointer may not actually point to allocated memory. In particular,
 219 /// if you construct a `Vec` with capacity 0 via [`Vec::new`], [`vec![]`][`vec!`],
 220 /// [`Vec::with_capacity(0)`][`Vec::with_capacity`], or by calling [`shrink_to_fit`]
 221 /// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized
 222 /// types inside a `Vec`, it will not allocate space for them. *Note that in this case
 223 /// the `Vec` may not report a [`capacity`] of 0*. `Vec` will allocate if and only
 224 /// if [`mem::size_of::<T>`]` * capacity() > 0`. In general, `Vec`'s allocation
 225 /// details are subtle enough that it is strongly recommended that you only
 226 /// free memory allocated by a `Vec` by creating a new `Vec` and dropping it.
 227 ///
 228 /// If a `Vec` *has* allocated memory, then the memory it points to is on the heap
 229 /// (as defined by the allocator Rust is configured to use by default), and its
 230 /// pointer points to [`len`] initialized elements in order (what you would see
 231 /// if you coerced it to a slice), followed by [`capacity`]` - `[`len`]
 232 /// logically uninitialized elements.
 233 ///
 234 /// `Vec` will never perform a "small optimization" where elements are actually
 235 /// stored on the stack for two reasons:
 236 ///
 237 /// * It would make it more difficult for unsafe code to correctly manipulate
 238 ///   a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were
 239 ///   only moved, and it would be more difficult to determine if a `Vec` had
 240 ///   actually allocated memory.
 241 ///
 242 /// * It would penalize the general case, incurring an additional branch
 243 ///   on every access.
 244 ///
 245 /// `Vec` will never automatically shrink itself, even if completely empty. This
 246 /// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec`
 247 /// and then filling it back up to the same [`len`] should incur no calls to
 248 /// the allocator. If you wish to free up unused memory, use
 249 /// [`shrink_to_fit`][`shrink_to_fit`].
 250 ///
 251 /// [`push`] and [`insert`] will never (re)allocate if the reported capacity is
 252 /// sufficient. [`push`] and [`insert`] *will* (re)allocate if
 253 /// [`len`]` == `[`capacity`]. That is, the reported capacity is completely
 254 /// accurate, and can be relied on. It can even be used to manually free the memory
 255 /// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even
 256 /// when not necessary.
 257 ///
 258 /// `Vec` does not guarantee any particular growth strategy when reallocating
 259 /// when full, nor when [`reserve`] is called. The current strategy is basic
 260 /// and it may prove desirable to use a non-constant growth factor. Whatever
 261 /// strategy is used will of course guarantee `O(1)` amortized [`push`].
 262 ///
 263 /// `vec![x; n]`, `vec![a, b, c, d]`, and
 264 /// [`Vec::with_capacity(n)`][`Vec::with_capacity`], will all produce a `Vec`
 265 /// with exactly the requested capacity. If [`len`]` == `[`capacity`],
 266 /// (as is the case for the [`vec!`] macro), then a `Vec<T>` can be converted to
 267 /// and from a [`Box<[T]>`][owned slice] without reallocating or moving the elements.
 268 ///
 269 /// `Vec` will not specifically overwrite any data that is removed from it,
 270 /// but also won't specifically preserve it. Its uninitialized memory is
 271 /// scratch space that it may use however it wants. It will generally just do
 272 /// whatever is most efficient or otherwise easy to implement. Do not rely on
 273 /// removed data to be erased for security purposes. Even if you drop a `Vec`, its
 274 /// buffer may simply be reused by another `Vec`. Even if you zero a `Vec`'s memory
 275 /// first, that may not actually happen because the optimizer does not consider
 276 /// this a side-effect that must be preserved.
 277 ///
 278 /// `Vec` does not currently guarantee the order in which elements are dropped
 279 /// (the order has changed in the past, and may change again).
 280 ///
 281 /// [`vec!`]: ../../std/macro.vec.html
 282 /// [`Index`]: ../../std/ops/trait.Index.html
 283 /// [`String`]: ../../std/string/struct.String.html
 284 /// [`&str`]: ../../std/primitive.str.html
 285 /// [`Vec::with_capacity`]: ../../std/vec/struct.Vec.html#method.with_capacity
 286 /// [`Vec::new`]: ../../std/vec/struct.Vec.html#method.new
 287 /// [`shrink_to_fit`]: ../../std/vec/struct.Vec.html#method.shrink_to_fit
 288 /// [`capacity`]: ../../std/vec/struct.Vec.html#method.capacity
 289 /// [`mem::size_of::<T>`]: ../../std/mem/fn.size_of.html
 290 /// [`len`]: ../../std/vec/struct.Vec.html#method.len
 291 /// [`push`]: ../../std/vec/struct.Vec.html#method.push
 292 /// [`insert`]: ../../std/vec/struct.Vec.html#method.insert
 293 /// [`reserve`]: ../../std/vec/struct.Vec.html#method.reserve
 294 /// [owned slice]: ../../std/boxed/struct.Box.html
 295 #[stable(feature = "rust1", since = "1.0.0")]
 296 pub struct Vec<T> {
 297     buf: RawVec<T>,
 298     len: usize,
 299 }
 300
 301 ////////////////////////////////////////////////////////////////////////////////
 302 // Inherent methods
 303 ////////////////////////////////////////////////////////////////////////////////
 304
 305 impl<T> Vec<T> {
 306     /// Constructs a new, empty `Vec<T>`.
 307     ///
 308     /// The vector will not allocate until elements are pushed onto it.
 309     ///
 310     /// # Examples
 311     ///
 312     /// ```
 313     /// # #![allow(unused_mut)]
 314     /// let mut vec: Vec<i32> = Vec::new();
 315     /// ```
 316     #[inline]
 317     #[stable(feature = "rust1", since = "1.0.0")]
 318     pub fn new() -> Vec<T> {
 319         Vec {
 320             buf: RawVec::new(),
 321             len: 0,
 322         }
 323     }
 324
 325     /// Constructs a new, empty `Vec<T>` with the specified capacity.
 326     ///
 327     /// The vector will be able to hold exactly `capacity` elements without
 328     /// reallocating. If `capacity` is 0, the vector will not allocate.
 329     ///
 330     /// It is important to note that this function does not specify the *length*
 331     /// of the returned vector, but only the *capacity*. For an explanation of
 332     /// the difference between length and capacity, see *[Capacity and reallocation]*.
 333     ///
 334     /// [Capacity and reallocation]: #capacity-and-reallocation
 335     ///
 336     /// # Examples
 337     ///
 338     /// ```
 339     /// let mut vec = Vec::with_capacity(10);
 340     ///
 341     /// // The vector contains no items, even though it has capacity for more
 342     /// assert_eq!(vec.len(), 0);
 343     ///
 344     /// // These are all done without reallocating...
 345     /// for i in 0..10 {
 346     ///     vec.push(i);
 347     /// }
 348     ///
 349     /// // ...but this may make the vector reallocate
 350     /// vec.push(11);
 351     /// ```
 352     #[inline]
 353     #[stable(feature = "rust1", since = "1.0.0")]
 354     pub fn with_capacity(capacity: usize) -> Vec<T> {
 355         Vec {
 356             buf: RawVec::with_capacity(capacity),
 357             len: 0,
 358         }
 359     }
 360
 361     /// Creates a `Vec<T>` directly from the raw components of another vector.
 362     ///
 363     /// # Safety
 364     ///
 365     /// This is highly unsafe, due to the number of invariants that aren't
 366     /// checked:
 367     ///
 368     /// * `ptr` needs to have been previously allocated via [`String`]/`Vec<T>`
 369     ///   (at least, it's highly likely to be incorrect if it wasn't).
 370     /// * `length` needs to be less than or equal to `capacity`.
 371     /// * `capacity` needs to be the capacity that the pointer was allocated with.
 372     ///
 373     /// Violating these may cause problems like corrupting the allocator's
 374     /// internal datastructures. For example it is **not** safe
 375     /// to build a `Vec<u8>` from a pointer to a C `char` array and a `size_t`.
 376     ///
 377     /// The ownership of `ptr` is effectively transferred to the
 378     /// `Vec<T>` which may then deallocate, reallocate or change the
 379     /// contents of memory pointed to by the pointer at will. Ensure
 380     /// that nothing else uses the pointer after calling this
 381     /// function.
 382     ///
 383     /// [`String`]: ../../std/string/struct.String.html
 384     ///
 385     /// # Examples
 386     ///
 387     /// ```
 388     /// use std::ptr;
 389     /// use std::mem;
 390     ///
 391     /// fn main() {
 392     ///     let mut v = vec![1, 2, 3];
 393     ///
 394     ///     // Pull out the various important pieces of information about `v`
 395     ///     let p = v.as_mut_ptr();
 396     ///     let len = v.len();
 397     ///     let cap = v.capacity();
 398     ///
 399     ///     unsafe {
 400     ///         // Cast `v` into the void: no destructor run, so we are in
 401     ///         // complete control of the allocation to which `p` points.
 402     ///         mem::forget(v);
 403     ///
 404     ///         // Overwrite memory with 4, 5, 6
 405     ///         for i in 0..len as isize {
 406     ///             ptr::write(p.offset(i), 4 + i);
 407     ///         }
 408     ///
 409     ///         // Put everything back together into a Vec
 410     ///         let rebuilt = Vec::from_raw_parts(p, len, cap);
 411     ///         assert_eq!(rebuilt, [4, 5, 6]);
 412     ///     }
 413     /// }
 414     /// ```
 415     #[stable(feature = "rust1", since = "1.0.0")]
 416     pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Vec<T> {
 417         Vec {
 418             buf: RawVec::from_raw_parts(ptr, capacity),
 419             len: length,
 420         }
 421     }
 422
 423     /// Returns the number of elements the vector can hold without
 424     /// reallocating.
 425     ///
 426     /// # Examples
 427     ///
 428     /// ```
 429     /// let vec: Vec<i32> = Vec::with_capacity(10);
 430     /// assert_eq!(vec.capacity(), 10);
 431     /// ```
 432     #[inline]
 433     #[stable(feature = "rust1", since = "1.0.0")]
 434     pub fn capacity(&self) -> usize {
 435         self.buf.cap()
 436     }
 437
 438     /// Reserves capacity for at least `additional` more elements to be inserted
 439     /// in the given `Vec<T>`. The collection may reserve more space to avoid
 440     /// frequent reallocations. After calling `reserve`, capacity will be
 441     /// greater than or equal to `self.len() + additional`. Does nothing if
 442     /// capacity is already sufficient.
 443     ///
 444     /// # Panics
 445     ///
 446     /// Panics if the new capacity overflows `usize`.
 447     ///
 448     /// # Examples
 449     ///
 450     /// ```
 451     /// let mut vec = vec![1];
 452     /// vec.reserve(10);
 453     /// assert!(vec.capacity() >= 11);
 454     /// ```
 455     #[stable(feature = "rust1", since = "1.0.0")]
 456     pub fn reserve(&mut self, additional: usize) {
 457         self.buf.reserve(self.len, additional);
 458     }
 459
 460     /// Reserves the minimum capacity for exactly `additional` more elements to
 461     /// be inserted in the given `Vec<T>`. After calling `reserve_exact`,
 462     /// capacity will be greater than or equal to `self.len() + additional`.
 463     /// Does nothing if the capacity is already sufficient.
 464     ///
 465     /// Note that the allocator may give the collection more space than it
 466     /// requests. Therefore capacity can not be relied upon to be precisely
 467     /// minimal. Prefer `reserve` if future insertions are expected.
 468     ///
 469     /// # Panics
 470     ///
 471     /// Panics if the new capacity overflows `usize`.
 472     ///
 473     /// # Examples
 474     ///
 475     /// ```
 476     /// let mut vec = vec![1];
 477     /// vec.reserve_exact(10);
 478     /// assert!(vec.capacity() >= 11);
 479     /// ```
 480     #[stable(feature = "rust1", since = "1.0.0")]
 481     pub fn reserve_exact(&mut self, additional: usize) {
 482         self.buf.reserve_exact(self.len, additional);
 483     }
 484
 485     /// Shrinks the capacity of the vector as much as possible.
 486     ///
 487     /// It will drop down as close as possible to the length but the allocator
 488     /// may still inform the vector that there is space for a few more elements.
 489     ///
 490     /// # Examples
 491     ///
 492     /// ```
 493     /// let mut vec = Vec::with_capacity(10);
 494     /// vec.extend([1, 2, 3].iter().cloned());
 495     /// assert_eq!(vec.capacity(), 10);
 496     /// vec.shrink_to_fit();
 497     /// assert!(vec.capacity() >= 3);
 498     /// ```
 499     #[stable(feature = "rust1", since = "1.0.0")]
 500     pub fn shrink_to_fit(&mut self) {
 501         self.buf.shrink_to_fit(self.len);
 502     }
 503
 504     /// Converts the vector into [`Box<[T]>`][owned slice].
 505     ///
 506     /// Note that this will drop any excess capacity. Calling this and
 507     /// converting back to a vector with [`into_vec`] is equivalent to calling
 508     /// [`shrink_to_fit`].
 509     ///
 510     /// [owned slice]: ../../std/boxed/struct.Box.html
 511     /// [`into_vec`]: ../../std/primitive.slice.html#method.into_vec
 512     /// [`shrink_to_fit`]: #method.shrink_to_fit
 513     ///
 514     /// # Examples
 515     ///
 516     /// ```
 517     /// let v = vec![1, 2, 3];
 518     ///
 519     /// let slice = v.into_boxed_slice();
 520     /// ```
 521     ///
 522     /// Any excess capacity is removed:
 523     ///
 524     /// ```
 525     /// let mut vec = Vec::with_capacity(10);
 526     /// vec.extend([1, 2, 3].iter().cloned());
 527     ///
 528     /// assert_eq!(vec.capacity(), 10);
 529     /// let slice = vec.into_boxed_slice();
 530     /// assert_eq!(slice.into_vec().capacity(), 3);
 531     /// ```
 532     #[stable(feature = "rust1", since = "1.0.0")]
 533     pub fn into_boxed_slice(mut self) -> Box<[T]> {
 534         unsafe {
 535             self.shrink_to_fit();
 536             let buf = ptr::read(&self.buf);
 537             mem::forget(self);
 538             buf.into_box()
 539         }
 540     }
 541
 542     /// Shortens the vector, keeping the first `len` elements and dropping
 543     /// the rest.
 544     ///
 545     /// If `len` is greater than the vector's current length, this has no
 546     /// effect.
 547     ///
 548     /// The [`drain`] method can emulate `truncate`, but causes the excess
 549     /// elements to be returned instead of dropped.
 550     ///
 551     /// Note that this method has no effect on the allocated capacity
 552     /// of the vector.
 553     ///
 554     /// # Examples
 555     ///
 556     /// Truncating a five element vector to two elements:
 557     ///
 558     /// ```
 559     /// let mut vec = vec![1, 2, 3, 4, 5];
 560     /// vec.truncate(2);
 561     /// assert_eq!(vec, [1, 2]);
 562     /// ```
 563     ///
 564     /// No truncation occurs when `len` is greater than the vector's current
 565     /// length:
 566     ///
 567     /// ```
 568     /// let mut vec = vec![1, 2, 3];
 569     /// vec.truncate(8);
 570     /// assert_eq!(vec, [1, 2, 3]);
 571     /// ```
 572     ///
 573     /// Truncating when `len == 0` is equivalent to calling the [`clear`]
 574     /// method.
 575     ///
 576     /// ```
 577     /// let mut vec = vec![1, 2, 3];
 578     /// vec.truncate(0);
 579     /// assert_eq!(vec, []);
 580     /// ```
 581     ///
 582     /// [`clear`]: #method.clear
 583     /// [`drain`]: #method.drain
 584     #[stable(feature = "rust1", since = "1.0.0")]
 585     pub fn truncate(&mut self, len: usize) {
 586         unsafe {
 587             // drop any extra elements
 588             while len < self.len {
 589                 // decrement len before the drop_in_place(), so a panic on Drop
 590                 // doesn't re-drop the just-failed value.
 591                 self.len -= 1;
 592                 let len = self.len;
 593                 ptr::drop_in_place(self.get_unchecked_mut(len));
 594             }
 595         }
 596     }
 597
 598     /// Extracts a slice containing the entire vector.
 599     ///
 600     /// Equivalent to `&s[..]`.
 601     ///
 602     /// # Examples
 603     ///
 604     /// ```
 605     /// use std::io::{self, Write};
 606     /// let buffer = vec![1, 2, 3, 5, 8];
 607     /// io::sink().write(buffer.as_slice()).unwrap();
 608     /// ```
 609     #[inline]
 610     #[stable(feature = "vec_as_slice", since = "1.7.0")]
 611     pub fn as_slice(&self) -> &[T] {
 612         self
 613     }
 614
 615     /// Extracts a mutable slice of the entire vector.
 616     ///
 617     /// Equivalent to `&mut s[..]`.
 618     ///
 619     /// # Examples
 620     ///
 621     /// ```
 622     /// use std::io::{self, Read};
 623     /// let mut buffer = vec![0; 3];
 624     /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
 625     /// ```
 626     #[inline]
 627     #[stable(feature = "vec_as_slice", since = "1.7.0")]
 628     pub fn as_mut_slice(&mut self) -> &mut [T] {
 629         self
 630     }
 631
 632     /// Sets the length of a vector.
 633     ///
 634     /// This will explicitly set the size of the vector, without actually
 635     /// modifying its buffers, so it is up to the caller to ensure that the
 636     /// vector is actually the specified size.
 637     ///
 638     /// # Examples
 639     ///
 640     /// ```
 641     /// use std::ptr;
 642     ///
 643     /// let mut vec = vec!['r', 'u', 's', 't'];
 644     ///
 645     /// unsafe {
 646     ///     ptr::drop_in_place(&mut vec[3]);
 647     ///     vec.set_len(3);
 648     /// }
 649     /// assert_eq!(vec, ['r', 'u', 's']);
 650     /// ```
 651     ///
 652     /// In this example, there is a memory leak since the memory locations
 653     /// owned by the inner vectors were not freed prior to the `set_len` call:
 654     ///
 655     /// ```
 656     /// let mut vec = vec![vec![1, 0, 0],
 657     ///                    vec![0, 1, 0],
 658     ///                    vec![0, 0, 1]];
 659     /// unsafe {
 660     ///     vec.set_len(0);
 661     /// }
 662     /// ```
 663     ///
 664     /// In this example, the vector gets expanded from zero to four items
 665     /// without any memory allocations occurring, resulting in vector
 666     /// values of unallocated memory:
 667     ///
 668     /// ```
 669     /// let mut vec: Vec<char> = Vec::new();
 670     ///
 671     /// unsafe {
 672     ///     vec.set_len(4);
 673     /// }
 674     /// ```
 675     #[inline]
 676     #[stable(feature = "rust1", since = "1.0.0")]
 677     pub unsafe fn set_len(&mut self, len: usize) {
 678         self.len = len;
 679     }
 680
 681     /// Removes an element from anywhere in the vector and return it, replacing
 682     /// it with the last element.
 683     ///
 684     /// This does not preserve ordering, but is O(1).
 685     ///
 686     /// # Panics
 687     ///
 688     /// Panics if `index` is out of bounds.
 689     ///
 690     /// # Examples
 691     ///
 692     /// ```
 693     /// let mut v = vec!["foo", "bar", "baz", "qux"];
 694     ///
 695     /// assert_eq!(v.swap_remove(1), "bar");
 696     /// assert_eq!(v, ["foo", "qux", "baz"]);
 697     ///
 698     /// assert_eq!(v.swap_remove(0), "foo");
 699     /// assert_eq!(v, ["baz", "qux"]);
 700     /// ```
 701     #[inline]
 702     #[stable(feature = "rust1", since = "1.0.0")]
 703     pub fn swap_remove(&mut self, index: usize) -> T {
 704         let length = self.len();
 705         self.swap(index, length - 1);
 706         self.pop().unwrap()
 707     }
 708
 709     /// Inserts an element at position `index` within the vector, shifting all
 710     /// elements after it to the right.
 711     ///
 712     /// # Panics
 713     ///
 714     /// Panics if `index` is out of bounds.
 715     ///
 716     /// # Examples
 717     ///
 718     /// ```
 719     /// let mut vec = vec![1, 2, 3];
 720     /// vec.insert(1, 4);
 721     /// assert_eq!(vec, [1, 4, 2, 3]);
 722     /// vec.insert(4, 5);
 723     /// assert_eq!(vec, [1, 4, 2, 3, 5]);
 724     /// ```
 725     #[stable(feature = "rust1", since = "1.0.0")]
 726     pub fn insert(&mut self, index: usize, element: T) {
 727         let len = self.len();
 728         assert!(index <= len);
 729
 730         // space for the new element
 731         if len == self.buf.cap() {
 732             self.buf.double();
 733         }
 734
 735         unsafe {
 736             // infallible
 737             // The spot to put the new value
 738             {
 739                 let p = self.as_mut_ptr().offset(index as isize);
 740                 // Shift everything over to make space. (Duplicating the
 741                 // `index`th element into two consecutive places.)
 742                 ptr::copy(p, p.offset(1), len - index);
 743                 // Write it in, overwriting the first copy of the `index`th
 744                 // element.
 745                 ptr::write(p, element);
 746             }
 747             self.set_len(len + 1);
 748         }
 749     }
 750
 751     /// Removes and returns the element at position `index` within the vector,
 752     /// shifting all elements after it to the left.
 753     ///
 754     /// # Panics
 755     ///
 756     /// Panics if `index` is out of bounds.
 757     ///
 758     /// # Examples
 759     ///
 760     /// ```
 761     /// let mut v = vec![1, 2, 3];
 762     /// assert_eq!(v.remove(1), 2);
 763     /// assert_eq!(v, [1, 3]);
 764     /// ```
 765     #[stable(feature = "rust1", since = "1.0.0")]
 766     pub fn remove(&mut self, index: usize) -> T {
 767         let len = self.len();
 768         assert!(index < len);
 769         unsafe {
 770             // infallible
 771             let ret;
 772             {
 773                 // the place we are taking from.
 774                 let ptr = self.as_mut_ptr().offset(index as isize);
 775                 // copy it out, unsafely having a copy of the value on
 776                 // the stack and in the vector at the same time.
 777                 ret = ptr::read(ptr);
 778
 779                 // Shift everything down to fill in that spot.
 780                 ptr::copy(ptr.offset(1), ptr, len - index - 1);
 781             }
 782             self.set_len(len - 1);
 783             ret
 784         }
 785     }
 786
 787     /// Retains only the elements specified by the predicate.
 788     ///
 789     /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
 790     /// This method operates in place and preserves the order of the retained
 791     /// elements.
 792     ///
 793     /// # Examples
 794     ///
 795     /// ```
 796     /// let mut vec = vec![1, 2, 3, 4];
 797     /// vec.retain(|&x| x%2 == 0);
 798     /// assert_eq!(vec, [2, 4]);
 799     /// ```
 800     #[stable(feature = "rust1", since = "1.0.0")]
 801     pub fn retain<F>(&mut self, mut f: F)
 802         where F: FnMut(&T) -> bool
 803     {
 804         let len = self.len();
 805         let mut del = 0;
 806         {
 807             let v = &mut **self;
 808
 809             for i in 0..len {
 810                 if !f(&v[i]) {
 811                     del += 1;
 812                 } else if del > 0 {
 813                     v.swap(i - del, i);
 814                 }
 815             }
 816         }
 817         if del > 0 {
 818             self.truncate(len - del);
 819         }
 820     }
 821
 822     /// Removes consecutive elements in the vector that resolve to the same key.
 823     ///
 824     /// If the vector is sorted, this removes all duplicates.
 825     ///
 826     /// # Examples
 827     ///
 828     /// ```
 829     /// let mut vec = vec![10, 20, 21, 30, 20];
 830     ///
 831     /// vec.dedup_by_key(|i| *i / 10);
 832     ///
 833     /// assert_eq!(vec, [10, 20, 30, 20]);
 834     /// ```
 835     #[stable(feature = "dedup_by", since = "1.16.0")]
 836     #[inline]
 837     pub fn dedup_by_key<F, K>(&mut self, mut key: F) where F: FnMut(&mut T) -> K, K: PartialEq {
 838         self.dedup_by(|a, b| key(a) == key(b))
 839     }
 840
 841     /// Removes consecutive elements in the vector that resolve to the same key.
 842     ///
 843     /// If the vector is sorted, this removes all duplicates.
 844     ///
 845     /// # Examples
 846     ///
 847     /// ```
 848     /// use std::ascii::AsciiExt;
 849     ///
 850     /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
 851     ///
 852     /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
 853     ///
 854     /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
 855     /// ```
 856     #[stable(feature = "dedup_by", since = "1.16.0")]
 857     pub fn dedup_by<F>(&mut self, mut same_bucket: F) where F: FnMut(&mut T, &mut T) -> bool {
 858         unsafe {
 859             // Although we have a mutable reference to `self`, we cannot make
 860             // *arbitrary* changes. The `same_bucket` calls could panic, so we
 861             // must ensure that the vector is in a valid state at all time.
 862             //
 863             // The way that we handle this is by using swaps; we iterate
 864             // over all the elements, swapping as we go so that at the end
 865             // the elements we wish to keep are in the front, and those we
 866             // wish to reject are at the back. We can then truncate the
 867             // vector. This operation is still O(n).
 868             //
 869             // Example: We start in this state, where `r` represents "next
 870             // read" and `w` represents "next_write`.
 871             //
 872             //           r
 873             //     +---+---+---+---+---+---+
 874             //     | 0 | 1 | 1 | 2 | 3 | 3 |
 875             //     +---+---+---+---+---+---+
 876             //           w
 877             //
 878             // Comparing self[r] against self[w-1], this is not a duplicate, so
 879             // we swap self[r] and self[w] (no effect as r==w) and then increment both
 880             // r and w, leaving us with:
 881             //
 882             //               r
 883             //     +---+---+---+---+---+---+
 884             //     | 0 | 1 | 1 | 2 | 3 | 3 |
 885             //     +---+---+---+---+---+---+
 886             //               w
 887             //
 888             // Comparing self[r] against self[w-1], this value is a duplicate,
 889             // so we increment `r` but leave everything else unchanged:
 890             //
 891             //                   r
 892             //     +---+---+---+---+---+---+
 893             //     | 0 | 1 | 1 | 2 | 3 | 3 |
 894             //     +---+---+---+---+---+---+
 895             //               w
 896             //
 897             // Comparing self[r] against self[w-1], this is not a duplicate,
 898             // so swap self[r] and self[w] and advance r and w:
 899             //
 900             //                       r
 901             //     +---+---+---+---+---+---+
 902             //     | 0 | 1 | 2 | 1 | 3 | 3 |
 903             //     +---+---+---+---+---+---+
 904             //                   w
 905             //
 906             // Not a duplicate, repeat:
 907             //
 908             //                           r
 909             //     +---+---+---+---+---+---+
 910             //     | 0 | 1 | 2 | 3 | 1 | 3 |
 911             //     +---+---+---+---+---+---+
 912             //                       w
 913             //
 914             // Duplicate, advance r. End of vec. Truncate to w.
 915
 916             let ln = self.len();
 917             if ln <= 1 {
 918                 return;
 919             }
 920
 921             // Avoid bounds checks by using raw pointers.
 922             let p = self.as_mut_ptr();
 923             let mut r: usize = 1;
 924             let mut w: usize = 1;
 925
 926             while r < ln {
 927                 let p_r = p.offset(r as isize);
 928                 let p_wm1 = p.offset((w - 1) as isize);
 929                 if !same_bucket(&mut *p_r, &mut *p_wm1) {
 930                     if r != w {
 931                         let p_w = p_wm1.offset(1);
 932                         mem::swap(&mut *p_r, &mut *p_w);
 933                     }
 934                     w += 1;
 935                 }
 936                 r += 1;
 937             }
 938
 939             self.truncate(w);
 940         }
 941     }
 942
 943     /// Appends an element to the back of a collection.
 944     ///
 945     /// # Panics
 946     ///
 947     /// Panics if the number of elements in the vector overflows a `usize`.
 948     ///
 949     /// # Examples
 950     ///
 951     /// ```
 952     /// let mut vec = vec![1, 2];
 953     /// vec.push(3);
 954     /// assert_eq!(vec, [1, 2, 3]);
 955     /// ```
 956     #[inline]
 957     #[stable(feature = "rust1", since = "1.0.0")]
 958     pub fn push(&mut self, value: T) {
 959         // This will panic or abort if we would allocate > isize::MAX bytes
 960         // or if the length increment would overflow for zero-sized types.
 961         if self.len == self.buf.cap() {
 962             self.buf.double();
 963         }
 964         unsafe {
 965             let end = self.as_mut_ptr().offset(self.len as isize);
 966             ptr::write(end, value);
 967             self.len += 1;
 968         }
 969     }
 970
 971     /// Removes the last element from a vector and returns it, or [`None`] if it
 972     /// is empty.
 973     ///
 974     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 975     ///
 976     /// # Examples
 977     ///
 978     /// ```
 979     /// let mut vec = vec![1, 2, 3];
 980     /// assert_eq!(vec.pop(), Some(3));
 981     /// assert_eq!(vec, [1, 2]);
 982     /// ```
 983     #[inline]
 984     #[stable(feature = "rust1", since = "1.0.0")]
 985     pub fn pop(&mut self) -> Option<T> {
 986         if self.len == 0 {
 987             None
 988         } else {
 989             unsafe {
 990                 self.len -= 1;
 991                 Some(ptr::read(self.get_unchecked(self.len())))
 992             }
 993         }
 994     }
 995
 996     /// Moves all the elements of `other` into `Self`, leaving `other` empty.
 997     ///
 998     /// # Panics
 999     ///
1000     /// Panics if the number of elements in the vector overflows a `usize`.
1001     ///
1002     /// # Examples
1003     ///
1004     /// ```
1005     /// let mut vec = vec![1, 2, 3];
1006     /// let mut vec2 = vec![4, 5, 6];
1007     /// vec.append(&mut vec2);
1008     /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
1009     /// assert_eq!(vec2, []);
1010     /// ```
1011     #[inline]
1012     #[stable(feature = "append", since = "1.4.0")]
1013     pub fn append(&mut self, other: &mut Self) {
1014         self.reserve(other.len());
1015         let len = self.len();
1016         unsafe {
1017             ptr::copy_nonoverlapping(other.as_ptr(), self.get_unchecked_mut(len), other.len());
1018         }
1019
1020         self.len += other.len();
1021         unsafe {
1022             other.set_len(0);
1023         }
1024     }
1025
1026     /// Create a draining iterator that removes the specified range in the vector
1027     /// and yields the removed items.
1028     ///
1029     /// Note 1: The element range is removed even if the iterator is only
1030     /// partially consumed or not consumed at all.
1031     ///
1032     /// Note 2: It is unspecified how many elements are removed from the vector,
1033     /// if the `Drain` value is leaked.
1034     ///
1035     /// # Panics
1036     ///
1037     /// Panics if the starting point is greater than the end point or if
1038     /// the end point is greater than the length of the vector.
1039     ///
1040     /// # Examples
1041     ///
1042     /// ```
1043     /// let mut v = vec![1, 2, 3];
1044     /// let u: Vec<_> = v.drain(1..).collect();
1045     /// assert_eq!(v, &[1]);
1046     /// assert_eq!(u, &[2, 3]);
1047     ///
1048     /// // A full range clears the vector
1049     /// v.drain(..);
1050     /// assert_eq!(v, &[]);
1051     /// ```
1052     #[stable(feature = "drain", since = "1.6.0")]
1053     pub fn drain<R>(&mut self, range: R) -> Drain<T>
1054         where R: RangeArgument<usize>
1055     {
1056         // Memory safety
1057         //
1058         // When the Drain is first created, it shortens the length of
1059         // the source vector to make sure no uninitalized or moved-from elements
1060         // are accessible at all if the Drain's destructor never gets to run.
1061         //
1062         // Drain will ptr::read out the values to remove.
1063         // When finished, remaining tail of the vec is copied back to cover
1064         // the hole, and the vector length is restored to the new length.
1065         //
1066         let len = self.len();
1067         let start = match range.start() {
1068             Included(&n) => n,
1069             Excluded(&n) => n + 1,
1070             Unbounded    => 0,
1071         };
1072         let end = match range.end() {
1073             Included(&n) => n + 1,
1074             Excluded(&n) => n,
1075             Unbounded    => len,
1076         };
1077         assert!(start <= end);
1078         assert!(end <= len);
1079
1080         unsafe {
1081             // set self.vec length's to start, to be safe in case Drain is leaked
1082             self.set_len(start);
1083             // Use the borrow in the IterMut to indicate borrowing behavior of the
1084             // whole Drain iterator (like &mut T).
1085             let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().offset(start as isize),
1086                                                         end - start);
1087             Drain {
1088                 tail_start: end,
1089                 tail_len: len - end,
1090                 iter: range_slice.iter(),
1091                 vec: Shared::new(self as *mut _),
1092             }
1093         }
1094     }
1095
1096     /// Clears the vector, removing all values.
1097     ///
1098     /// Note that this method has no effect on the allocated capacity
1099     /// of the vector.
1100     ///
1101     /// # Examples
1102     ///
1103     /// ```
1104     /// let mut v = vec![1, 2, 3];
1105     ///
1106     /// v.clear();
1107     ///
1108     /// assert!(v.is_empty());
1109     /// ```
1110     #[inline]
1111     #[stable(feature = "rust1", since = "1.0.0")]
1112     pub fn clear(&mut self) {
1113         self.truncate(0)
1114     }
1115
1116     /// Returns the number of elements in the vector.
1117     ///
1118     /// # Examples
1119     ///
1120     /// ```
1121     /// let a = vec![1, 2, 3];
1122     /// assert_eq!(a.len(), 3);
1123     /// ```
1124     #[inline]
1125     #[stable(feature = "rust1", since = "1.0.0")]
1126     pub fn len(&self) -> usize {
1127         self.len
1128     }
1129
1130     /// Returns `true` if the vector contains no elements.
1131     ///
1132     /// # Examples
1133     ///
1134     /// ```
1135     /// let mut v = Vec::new();
1136     /// assert!(v.is_empty());
1137     ///
1138     /// v.push(1);
1139     /// assert!(!v.is_empty());
1140     /// ```
1141     #[stable(feature = "rust1", since = "1.0.0")]
1142     pub fn is_empty(&self) -> bool {
1143         self.len() == 0
1144     }
1145
1146     /// Splits the collection into two at the given index.
1147     ///
1148     /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
1149     /// and the returned `Self` contains elements `[at, len)`.
1150     ///
1151     /// Note that the capacity of `self` does not change.
1152     ///
1153     /// # Panics
1154     ///
1155     /// Panics if `at > len`.
1156     ///
1157     /// # Examples
1158     ///
1159     /// ```
1160     /// let mut vec = vec![1,2,3];
1161     /// let vec2 = vec.split_off(1);
1162     /// assert_eq!(vec, [1]);
1163     /// assert_eq!(vec2, [2, 3]);
1164     /// ```
1165     #[inline]
1166     #[stable(feature = "split_off", since = "1.4.0")]
1167     pub fn split_off(&mut self, at: usize) -> Self {
1168         assert!(at <= self.len(), "`at` out of bounds");
1169
1170         let other_len = self.len - at;
1171         let mut other = Vec::with_capacity(other_len);
1172
1173         // Unsafely `set_len` and copy items to `other`.
1174         unsafe {
1175             self.set_len(at);
1176             other.set_len(other_len);
1177
1178             ptr::copy_nonoverlapping(self.as_ptr().offset(at as isize),
1179                                      other.as_mut_ptr(),
1180                                      other.len());
1181         }
1182         other
1183     }
1184 }
1185
1186 impl<T: Clone> Vec<T> {
1187     /// Resizes the `Vec` in-place so that `len()` is equal to `new_len`.
1188     ///
1189     /// If `new_len` is greater than `len()`, the `Vec` is extended by the
1190     /// difference, with each additional slot filled with `value`.
1191     /// If `new_len` is less than `len()`, the `Vec` is simply truncated.
1192     ///
1193     /// # Examples
1194     ///
1195     /// ```
1196     /// let mut vec = vec!["hello"];
1197     /// vec.resize(3, "world");
1198     /// assert_eq!(vec, ["hello", "world", "world"]);
1199     ///
1200     /// let mut vec = vec![1, 2, 3, 4];
1201     /// vec.resize(2, 0);
1202     /// assert_eq!(vec, [1, 2]);
1203     /// ```
1204     #[stable(feature = "vec_resize", since = "1.5.0")]
1205     pub fn resize(&mut self, new_len: usize, value: T) {
1206         let len = self.len();
1207
1208         if new_len > len {
1209             self.extend_with_element(new_len - len, value);
1210         } else {
1211             self.truncate(new_len);
1212         }
1213     }
1214
1215     /// Extend the vector by `n` additional clones of `value`.
1216     fn extend_with_element(&mut self, n: usize, value: T) {
1217         self.reserve(n);
1218
1219         unsafe {
1220             let mut ptr = self.as_mut_ptr().offset(self.len() as isize);
1221             // Use SetLenOnDrop to work around bug where compiler
1222             // may not realize the store through `ptr` through self.set_len()
1223             // don't alias.
1224             let mut local_len = SetLenOnDrop::new(&mut self.len);
1225
1226             // Write all elements except the last one
1227             for _ in 1..n {
1228                 ptr::write(ptr, value.clone());
1229                 ptr = ptr.offset(1);
1230                 // Increment the length in every step in case clone() panics
1231                 local_len.increment_len(1);
1232             }
1233
1234             if n > 0 {
1235                 // We can write the last element directly without cloning needlessly
1236                 ptr::write(ptr, value);
1237                 local_len.increment_len(1);
1238             }
1239
1240             // len set by scope guard
1241         }
1242     }
1243
1244     /// Clones and appends all elements in a slice to the `Vec`.
1245     ///
1246     /// Iterates over the slice `other`, clones each element, and then appends
1247     /// it to this `Vec`. The `other` vector is traversed in-order.
1248     ///
1249     /// Note that this function is same as `extend` except that it is
1250     /// specialized to work with slices instead. If and when Rust gets
1251     /// specialization this function will likely be deprecated (but still
1252     /// available).
1253     ///
1254     /// # Examples
1255     ///
1256     /// ```
1257     /// let mut vec = vec![1];
1258     /// vec.extend_from_slice(&[2, 3, 4]);
1259     /// assert_eq!(vec, [1, 2, 3, 4]);
1260     /// ```
1261     #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
1262     pub fn extend_from_slice(&mut self, other: &[T]) {
1263         self.spec_extend(other.iter())
1264     }
1265
1266     /// Returns a place for insertion at the back of the `Vec`.
1267     ///
1268     /// Using this method with placement syntax is equivalent to [`push`](#method.push),
1269     /// but may be more efficient.
1270     ///
1271     /// # Examples
1272     ///
1273     /// ```
1274     /// #![feature(collection_placement)]
1275     /// #![feature(placement_in_syntax)]
1276     ///
1277     /// let mut vec = vec![1, 2];
1278     /// vec.place_back() <- 3;
1279     /// vec.place_back() <- 4;
1280     /// assert_eq!(&vec, &[1, 2, 3, 4]);
1281     /// ```
1282     #[unstable(feature = "collection_placement",
1283                reason = "placement protocol is subject to change",
1284                issue = "30172")]
1285     pub fn place_back(&mut self) -> PlaceBack<T> {
1286         PlaceBack { vec: self }
1287     }
1288 }
1289
1290 // Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
1291 //
1292 // The idea is: The length field in SetLenOnDrop is a local variable
1293 // that the optimizer will see does not alias with any stores through the Vec's data
1294 // pointer. This is a workaround for alias analysis issue #32155
1295 struct SetLenOnDrop<'a> {
1296     len: &'a mut usize,
1297     local_len: usize,
1298 }
1299
1300 impl<'a> SetLenOnDrop<'a> {
1301     #[inline]
1302     fn new(len: &'a mut usize) -> Self {
1303         SetLenOnDrop { local_len: *len, len: len }
1304     }
1305
1306     #[inline]
1307     fn increment_len(&mut self, increment: usize) {
1308         self.local_len += increment;
1309     }
1310 }
1311
1312 impl<'a> Drop for SetLenOnDrop<'a> {
1313     #[inline]
1314     fn drop(&mut self) {
1315         *self.len = self.local_len;
1316     }
1317 }
1318
1319 impl<T: PartialEq> Vec<T> {
1320     /// Removes consecutive repeated elements in the vector.
1321     ///
1322     /// If the vector is sorted, this removes all duplicates.
1323     ///
1324     /// # Examples
1325     ///
1326     /// ```
1327     /// let mut vec = vec![1, 2, 2, 3, 2];
1328     ///
1329     /// vec.dedup();
1330     ///
1331     /// assert_eq!(vec, [1, 2, 3, 2]);
1332     /// ```
1333     #[stable(feature = "rust1", since = "1.0.0")]
1334     #[inline]
1335     pub fn dedup(&mut self) {
1336         self.dedup_by(|a, b| a == b)
1337     }
1338
1339     /// Removes the first instance of `item` from the vector if the item exists.
1340     ///
1341     /// # Examples
1342     ///
1343     /// ```
1344     ///# #![feature(vec_remove_item)]
1345     /// let mut vec = vec![1, 2, 3, 1];
1346     ///
1347     /// vec.remove_item(&1);
1348     ///
1349     /// assert_eq!(vec, vec![2, 3, 1]);
1350     /// ```
1351     #[unstable(feature = "vec_remove_item", reason = "recently added", issue = "40062")]
1352     pub fn remove_item(&mut self, item: &T) -> Option<T> {
1353         let pos = match self.iter().position(|x| *x == *item) {
1354             Some(x) => x,
1355             None => return None,
1356         };
1357         Some(self.remove(pos))
1358     }
1359 }
1360
1361 ////////////////////////////////////////////////////////////////////////////////
1362 // Internal methods and functions
1363 ////////////////////////////////////////////////////////////////////////////////
1364
1365 #[doc(hidden)]
1366 #[stable(feature = "rust1", since = "1.0.0")]
1367 pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
1368     let mut v = Vec::with_capacity(n);
1369     v.extend_with_element(n, elem);
1370     v
1371 }
1372
1373 ////////////////////////////////////////////////////////////////////////////////
1374 // Common trait implementations for Vec
1375 ////////////////////////////////////////////////////////////////////////////////
1376
1377 #[stable(feature = "rust1", since = "1.0.0")]
1378 impl<T: Clone> Clone for Vec<T> {
1379     #[cfg(not(test))]
1380     fn clone(&self) -> Vec<T> {
1381         <[T]>::to_vec(&**self)
1382     }
1383
1384     // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
1385     // required for this method definition, is not available. Instead use the
1386     // `slice::to_vec`  function which is only available with cfg(test)
1387     // NB see the slice::hack module in slice.rs for more information
1388     #[cfg(test)]
1389     fn clone(&self) -> Vec<T> {
1390         ::slice::to_vec(&**self)
1391     }
1392
1393     fn clone_from(&mut self, other: &Vec<T>) {
1394         // drop anything in self that will not be overwritten
1395         self.truncate(other.len());
1396         let len = self.len();
1397
1398         // reuse the contained values' allocations/resources.
1399         self.clone_from_slice(&other[..len]);
1400
1401         // self.len <= other.len due to the truncate above, so the
1402         // slice here is always in-bounds.
1403         self.extend_from_slice(&other[len..]);
1404     }
1405 }
1406
1407 #[stable(feature = "rust1", since = "1.0.0")]
1408 impl<T: Hash> Hash for Vec<T> {
1409     #[inline]
1410     fn hash<H: hash::Hasher>(&self, state: &mut H) {
1411         Hash::hash(&**self, state)
1412     }
1413 }
1414
1415 #[stable(feature = "rust1", since = "1.0.0")]
1416 impl<T> Index<usize> for Vec<T> {
1417     type Output = T;
1418
1419     #[inline]
1420     fn index(&self, index: usize) -> &T {
1421         // NB built-in indexing via `&[T]`
1422         &(**self)[index]
1423     }
1424 }
1425
1426 #[stable(feature = "rust1", since = "1.0.0")]
1427 impl<T> IndexMut<usize> for Vec<T> {
1428     #[inline]
1429     fn index_mut(&mut self, index: usize) -> &mut T {
1430         // NB built-in indexing via `&mut [T]`
1431         &mut (**self)[index]
1432     }
1433 }
1434
1435
1436 #[stable(feature = "rust1", since = "1.0.0")]
1437 impl<T> ops::Index<ops::Range<usize>> for Vec<T> {
1438     type Output = [T];
1439
1440     #[inline]
1441     fn index(&self, index: ops::Range<usize>) -> &[T] {
1442         Index::index(&**self, index)
1443     }
1444 }
1445 #[stable(feature = "rust1", since = "1.0.0")]
1446 impl<T> ops::Index<ops::RangeTo<usize>> for Vec<T> {
1447     type Output = [T];
1448
1449     #[inline]
1450     fn index(&self, index: ops::RangeTo<usize>) -> &[T] {
1451         Index::index(&**self, index)
1452     }
1453 }
1454 #[stable(feature = "rust1", since = "1.0.0")]
1455 impl<T> ops::Index<ops::RangeFrom<usize>> for Vec<T> {
1456     type Output = [T];
1457
1458     #[inline]
1459     fn index(&self, index: ops::RangeFrom<usize>) -> &[T] {
1460         Index::index(&**self, index)
1461     }
1462 }
1463 #[stable(feature = "rust1", since = "1.0.0")]
1464 impl<T> ops::Index<ops::RangeFull> for Vec<T> {
1465     type Output = [T];
1466
1467     #[inline]
1468     fn index(&self, _index: ops::RangeFull) -> &[T] {
1469         self
1470     }
1471 }
1472 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1473 impl<T> ops::Index<ops::RangeInclusive<usize>> for Vec<T> {
1474     type Output = [T];
1475
1476     #[inline]
1477     fn index(&self, index: ops::RangeInclusive<usize>) -> &[T] {
1478         Index::index(&**self, index)
1479     }
1480 }
1481 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1482 impl<T> ops::Index<ops::RangeToInclusive<usize>> for Vec<T> {
1483     type Output = [T];
1484
1485     #[inline]
1486     fn index(&self, index: ops::RangeToInclusive<usize>) -> &[T] {
1487         Index::index(&**self, index)
1488     }
1489 }
1490
1491 #[stable(feature = "rust1", since = "1.0.0")]
1492 impl<T> ops::IndexMut<ops::Range<usize>> for Vec<T> {
1493     #[inline]
1494     fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] {
1495         IndexMut::index_mut(&mut **self, index)
1496     }
1497 }
1498 #[stable(feature = "rust1", since = "1.0.0")]
1499 impl<T> ops::IndexMut<ops::RangeTo<usize>> for Vec<T> {
1500     #[inline]
1501     fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] {
1502         IndexMut::index_mut(&mut **self, index)
1503     }
1504 }
1505 #[stable(feature = "rust1", since = "1.0.0")]
1506 impl<T> ops::IndexMut<ops::RangeFrom<usize>> for Vec<T> {
1507     #[inline]
1508     fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] {
1509         IndexMut::index_mut(&mut **self, index)
1510     }
1511 }
1512 #[stable(feature = "rust1", since = "1.0.0")]
1513 impl<T> ops::IndexMut<ops::RangeFull> for Vec<T> {
1514     #[inline]
1515     fn index_mut(&mut self, _index: ops::RangeFull) -> &mut [T] {
1516         self
1517     }
1518 }
1519 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1520 impl<T> ops::IndexMut<ops::RangeInclusive<usize>> for Vec<T> {
1521     #[inline]
1522     fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut [T] {
1523         IndexMut::index_mut(&mut **self, index)
1524     }
1525 }
1526 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1527 impl<T> ops::IndexMut<ops::RangeToInclusive<usize>> for Vec<T> {
1528     #[inline]
1529     fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut [T] {
1530         IndexMut::index_mut(&mut **self, index)
1531     }
1532 }
1533
1534 #[stable(feature = "rust1", since = "1.0.0")]
1535 impl<T> ops::Deref for Vec<T> {
1536     type Target = [T];
1537
1538     fn deref(&self) -> &[T] {
1539         unsafe {
1540             let p = self.buf.ptr();
1541             assume(!p.is_null());
1542             slice::from_raw_parts(p, self.len)
1543         }
1544     }
1545 }
1546
1547 #[stable(feature = "rust1", since = "1.0.0")]
1548 impl<T> ops::DerefMut for Vec<T> {
1549     fn deref_mut(&mut self) -> &mut [T] {
1550         unsafe {
1551             let ptr = self.buf.ptr();
1552             assume(!ptr.is_null());
1553             slice::from_raw_parts_mut(ptr, self.len)
1554         }
1555     }
1556 }
1557
1558 #[stable(feature = "rust1", since = "1.0.0")]
1559 impl<T> FromIterator<T> for Vec<T> {
1560     #[inline]
1561     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
1562         <Self as SpecExtend<_, _>>::from_iter(iter.into_iter())
1563     }
1564 }
1565
1566 #[stable(feature = "rust1", since = "1.0.0")]
1567 impl<T> IntoIterator for Vec<T> {
1568     type Item = T;
1569     type IntoIter = IntoIter<T>;
1570
1571     /// Creates a consuming iterator, that is, one that moves each value out of
1572     /// the vector (from start to end). The vector cannot be used after calling
1573     /// this.
1574     ///
1575     /// # Examples
1576     ///
1577     /// ```
1578     /// let v = vec!["a".to_string(), "b".to_string()];
1579     /// for s in v.into_iter() {
1580     ///     // s has type String, not &String
1581     ///     println!("{}", s);
1582     /// }
1583     /// ```
1584     #[inline]
1585     fn into_iter(mut self) -> IntoIter<T> {
1586         unsafe {
1587             let begin = self.as_mut_ptr();
1588             assume(!begin.is_null());
1589             let end = if mem::size_of::<T>() == 0 {
1590                 arith_offset(begin as *const i8, self.len() as isize) as *const T
1591             } else {
1592                 begin.offset(self.len() as isize) as *const T
1593             };
1594             let cap = self.buf.cap();
1595             mem::forget(self);
1596             IntoIter {
1597                 buf: Shared::new(begin),
1598                 cap: cap,
1599                 ptr: begin,
1600                 end: end,
1601             }
1602         }
1603     }
1604 }
1605
1606 #[stable(feature = "rust1", since = "1.0.0")]
1607 impl<'a, T> IntoIterator for &'a Vec<T> {
1608     type Item = &'a T;
1609     type IntoIter = slice::Iter<'a, T>;
1610
1611     fn into_iter(self) -> slice::Iter<'a, T> {
1612         self.iter()
1613     }
1614 }
1615
1616 #[stable(feature = "rust1", since = "1.0.0")]
1617 impl<'a, T> IntoIterator for &'a mut Vec<T> {
1618     type Item = &'a mut T;
1619     type IntoIter = slice::IterMut<'a, T>;
1620
1621     fn into_iter(mut self) -> slice::IterMut<'a, T> {
1622         self.iter_mut()
1623     }
1624 }
1625
1626 #[stable(feature = "rust1", since = "1.0.0")]
1627 impl<T> Extend<T> for Vec<T> {
1628     #[inline]
1629     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1630         self.spec_extend(iter.into_iter())
1631     }
1632 }
1633
1634 // Specialization trait used for Vec::from_iter and Vec::extend
1635 trait SpecExtend<T, I> {
1636     fn from_iter(iter: I) -> Self;
1637     fn spec_extend(&mut self, iter: I);
1638 }
1639
1640 impl<T, I> SpecExtend<T, I> for Vec<T>
1641     where I: Iterator<Item=T>,
1642 {
1643     default fn from_iter(mut iterator: I) -> Self {
1644         // Unroll the first iteration, as the vector is going to be
1645         // expanded on this iteration in every case when the iterable is not
1646         // empty, but the loop in extend_desugared() is not going to see the
1647         // vector being full in the few subsequent loop iterations.
1648         // So we get better branch prediction.
1649         let mut vector = match iterator.next() {
1650             None => return Vec::new(),
1651             Some(element) => {
1652                 let (lower, _) = iterator.size_hint();
1653                 let mut vector = Vec::with_capacity(lower.saturating_add(1));
1654                 unsafe {
1655                     ptr::write(vector.get_unchecked_mut(0), element);
1656                     vector.set_len(1);
1657                 }
1658                 vector
1659             }
1660         };
1661         vector.spec_extend(iterator);
1662         vector
1663     }
1664
1665     default fn spec_extend(&mut self, iter: I) {
1666         self.extend_desugared(iter)
1667     }
1668 }
1669
1670 impl<T, I> SpecExtend<T, I> for Vec<T>
1671     where I: TrustedLen<Item=T>,
1672 {
1673     fn from_iter(iterator: I) -> Self {
1674         let mut vector = Vec::new();
1675         vector.spec_extend(iterator);
1676         vector
1677     }
1678
1679     fn spec_extend(&mut self, iterator: I) {
1680         // This is the case for a TrustedLen iterator.
1681         let (low, high) = iterator.size_hint();
1682         if let Some(high_value) = high {
1683             debug_assert_eq!(low, high_value,
1684                              "TrustedLen iterator's size hint is not exact: {:?}",
1685                              (low, high));
1686         }
1687         if let Some(additional) = high {
1688             self.reserve(additional);
1689             unsafe {
1690                 let mut ptr = self.as_mut_ptr().offset(self.len() as isize);
1691                 let mut local_len = SetLenOnDrop::new(&mut self.len);
1692                 for element in iterator {
1693                     ptr::write(ptr, element);
1694                     ptr = ptr.offset(1);
1695                     // NB can't overflow since we would have had to alloc the address space
1696                     local_len.increment_len(1);
1697                 }
1698             }
1699         } else {
1700             self.extend_desugared(iterator)
1701         }
1702     }
1703 }
1704
1705 impl<'a, T: 'a, I> SpecExtend<&'a T, I> for Vec<T>
1706     where I: Iterator<Item=&'a T>,
1707           T: Clone,
1708 {
1709     default fn from_iter(iterator: I) -> Self {
1710         SpecExtend::from_iter(iterator.cloned())
1711     }
1712
1713     default fn spec_extend(&mut self, iterator: I) {
1714         self.spec_extend(iterator.cloned())
1715     }
1716 }
1717
1718 impl<'a, T: 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T>
1719     where T: Copy,
1720 {
1721     fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
1722         let slice = iterator.as_slice();
1723         self.reserve(slice.len());
1724         unsafe {
1725             let len = self.len();
1726             self.set_len(len + slice.len());
1727             self.get_unchecked_mut(len..).copy_from_slice(slice);
1728         }
1729     }
1730 }
1731
1732 impl<T> Vec<T> {
1733     fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
1734         // This is the case for a general iterator.
1735         //
1736         // This function should be the moral equivalent of:
1737         //
1738         //      for item in iterator {
1739         //          self.push(item);
1740         //      }
1741         while let Some(element) = iterator.next() {
1742             let len = self.len();
1743             if len == self.capacity() {
1744                 let (lower, _) = iterator.size_hint();
1745                 self.reserve(lower.saturating_add(1));
1746             }
1747             unsafe {
1748                 ptr::write(self.get_unchecked_mut(len), element);
1749                 // NB can't overflow since we would have had to alloc the address space
1750                 self.set_len(len + 1);
1751             }
1752         }
1753     }
1754 }
1755
1756 #[stable(feature = "extend_ref", since = "1.2.0")]
1757 impl<'a, T: 'a + Copy> Extend<&'a T> for Vec<T> {
1758     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1759         self.spec_extend(iter.into_iter())
1760     }
1761 }
1762
1763 macro_rules! __impl_slice_eq1 {
1764     ($Lhs: ty, $Rhs: ty) => {
1765         __impl_slice_eq1! { $Lhs, $Rhs, Sized }
1766     };
1767     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
1768         #[stable(feature = "rust1", since = "1.0.0")]
1769         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
1770             #[inline]
1771             fn eq(&self, other: &$Rhs) -> bool { self[..] == other[..] }
1772             #[inline]
1773             fn ne(&self, other: &$Rhs) -> bool { self[..] != other[..] }
1774         }
1775     }
1776 }
1777
1778 __impl_slice_eq1! { Vec<A>, Vec<B> }
1779 __impl_slice_eq1! { Vec<A>, &'b [B] }
1780 __impl_slice_eq1! { Vec<A>, &'b mut [B] }
1781 __impl_slice_eq1! { Cow<'a, [A]>, &'b [B], Clone }
1782 __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B], Clone }
1783 __impl_slice_eq1! { Cow<'a, [A]>, Vec<B>, Clone }
1784
1785 macro_rules! array_impls {
1786     ($($N: expr)+) => {
1787         $(
1788             // NOTE: some less important impls are omitted to reduce code bloat
1789             __impl_slice_eq1! { Vec<A>, [B; $N] }
1790             __impl_slice_eq1! { Vec<A>, &'b [B; $N] }
1791             // __impl_slice_eq1! { Vec<A>, &'b mut [B; $N] }
1792             // __impl_slice_eq1! { Cow<'a, [A]>, [B; $N], Clone }
1793             // __impl_slice_eq1! { Cow<'a, [A]>, &'b [B; $N], Clone }
1794             // __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B; $N], Clone }
1795         )+
1796     }
1797 }
1798
1799 array_impls! {
1800      0  1  2  3  4  5  6  7  8  9
1801     10 11 12 13 14 15 16 17 18 19
1802     20 21 22 23 24 25 26 27 28 29
1803     30 31 32
1804 }
1805
1806 /// Implements comparison of vectors, lexicographically.
1807 #[stable(feature = "rust1", since = "1.0.0")]
1808 impl<T: PartialOrd> PartialOrd for Vec<T> {
1809     #[inline]
1810     fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
1811         PartialOrd::partial_cmp(&**self, &**other)
1812     }
1813 }
1814
1815 #[stable(feature = "rust1", since = "1.0.0")]
1816 impl<T: Eq> Eq for Vec<T> {}
1817
1818 /// Implements ordering of vectors, lexicographically.
1819 #[stable(feature = "rust1", since = "1.0.0")]
1820 impl<T: Ord> Ord for Vec<T> {
1821     #[inline]
1822     fn cmp(&self, other: &Vec<T>) -> Ordering {
1823         Ord::cmp(&**self, &**other)
1824     }
1825 }
1826
1827 #[stable(feature = "rust1", since = "1.0.0")]
1828 unsafe impl<#[may_dangle] T> Drop for Vec<T> {
1829     fn drop(&mut self) {
1830         unsafe {
1831             // use drop for [T]
1832             ptr::drop_in_place(&mut self[..]);
1833         }
1834         // RawVec handles deallocation
1835     }
1836 }
1837
1838 #[stable(feature = "rust1", since = "1.0.0")]
1839 impl<T> Default for Vec<T> {
1840     /// Creates an empty `Vec<T>`.
1841     fn default() -> Vec<T> {
1842         Vec::new()
1843     }
1844 }
1845
1846 #[stable(feature = "rust1", since = "1.0.0")]
1847 impl<T: fmt::Debug> fmt::Debug for Vec<T> {
1848     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1849         fmt::Debug::fmt(&**self, f)
1850     }
1851 }
1852
1853 #[stable(feature = "rust1", since = "1.0.0")]
1854 impl<T> AsRef<Vec<T>> for Vec<T> {
1855     fn as_ref(&self) -> &Vec<T> {
1856         self
1857     }
1858 }
1859
1860 #[stable(feature = "vec_as_mut", since = "1.5.0")]
1861 impl<T> AsMut<Vec<T>> for Vec<T> {
1862     fn as_mut(&mut self) -> &mut Vec<T> {
1863         self
1864     }
1865 }
1866
1867 #[stable(feature = "rust1", since = "1.0.0")]
1868 impl<T> AsRef<[T]> for Vec<T> {
1869     fn as_ref(&self) -> &[T] {
1870         self
1871     }
1872 }
1873
1874 #[stable(feature = "vec_as_mut", since = "1.5.0")]
1875 impl<T> AsMut<[T]> for Vec<T> {
1876     fn as_mut(&mut self) -> &mut [T] {
1877         self
1878     }
1879 }
1880
1881 #[stable(feature = "rust1", since = "1.0.0")]
1882 impl<'a, T: Clone> From<&'a [T]> for Vec<T> {
1883     #[cfg(not(test))]
1884     fn from(s: &'a [T]) -> Vec<T> {
1885         s.to_vec()
1886     }
1887     #[cfg(test)]
1888     fn from(s: &'a [T]) -> Vec<T> {
1889         ::slice::to_vec(s)
1890     }
1891 }
1892
1893 #[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
1894 impl<'a, T> From<Cow<'a, [T]>> for Vec<T> where [T]: ToOwned<Owned=Vec<T>> {
1895     fn from(s: Cow<'a, [T]>) -> Vec<T> {
1896         s.into_owned()
1897     }
1898 }
1899
1900 // note: test pulls in libstd, which causes errors here
1901 #[cfg(not(test))]
1902 #[stable(feature = "vec_from_box", since = "1.17.0")]
1903 impl<T> From<Box<[T]>> for Vec<T> {
1904     fn from(s: Box<[T]>) -> Vec<T> {
1905         s.into_vec()
1906     }
1907 }
1908
1909 #[stable(feature = "box_from_vec", since = "1.17.0")]
1910 impl<T> Into<Box<[T]>> for Vec<T> {
1911     fn into(self) -> Box<[T]> {
1912         self.into_boxed_slice()
1913     }
1914 }
1915
1916 #[stable(feature = "rust1", since = "1.0.0")]
1917 impl<'a> From<&'a str> for Vec<u8> {
1918     fn from(s: &'a str) -> Vec<u8> {
1919         From::from(s.as_bytes())
1920     }
1921 }
1922
1923 ////////////////////////////////////////////////////////////////////////////////
1924 // Clone-on-write
1925 ////////////////////////////////////////////////////////////////////////////////
1926
1927 #[stable(feature = "cow_from_vec", since = "1.7.0")]
1928 impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> {
1929     fn from(s: &'a [T]) -> Cow<'a, [T]> {
1930         Cow::Borrowed(s)
1931     }
1932 }
1933
1934 #[stable(feature = "cow_from_vec", since = "1.7.0")]
1935 impl<'a, T: Clone> From<Vec<T>> for Cow<'a, [T]> {
1936     fn from(v: Vec<T>) -> Cow<'a, [T]> {
1937         Cow::Owned(v)
1938     }
1939 }
1940
1941 #[stable(feature = "rust1", since = "1.0.0")]
1942 impl<'a, T> FromIterator<T> for Cow<'a, [T]> where T: Clone {
1943     fn from_iter<I: IntoIterator<Item = T>>(it: I) -> Cow<'a, [T]> {
1944         Cow::Owned(FromIterator::from_iter(it))
1945     }
1946 }
1947
1948 ////////////////////////////////////////////////////////////////////////////////
1949 // Iterators
1950 ////////////////////////////////////////////////////////////////////////////////
1951
1952 /// An iterator that moves out of a vector.
1953 ///
1954 /// This `struct` is created by the `into_iter` method on [`Vec`][`Vec`] (provided
1955 /// by the [`IntoIterator`] trait).
1956 ///
1957 /// [`Vec`]: struct.Vec.html
1958 /// [`IntoIterator`]: ../../std/iter/trait.IntoIterator.html
1959 #[stable(feature = "rust1", since = "1.0.0")]
1960 pub struct IntoIter<T> {
1961     buf: Shared<T>,
1962     cap: usize,
1963     ptr: *const T,
1964     end: *const T,
1965 }
1966
1967 #[stable(feature = "vec_intoiter_debug", since = "1.13.0")]
1968 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
1969     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1970         f.debug_tuple("IntoIter")
1971             .field(&self.as_slice())
1972             .finish()
1973     }
1974 }
1975
1976 impl<T> IntoIter<T> {
1977     /// Returns the remaining items of this iterator as a slice.
1978     ///
1979     /// # Examples
1980     ///
1981     /// ```
1982     /// let vec = vec!['a', 'b', 'c'];
1983     /// let mut into_iter = vec.into_iter();
1984     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
1985     /// let _ = into_iter.next().unwrap();
1986     /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
1987     /// ```
1988     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
1989     pub fn as_slice(&self) -> &[T] {
1990         unsafe {
1991             slice::from_raw_parts(self.ptr, self.len())
1992         }
1993     }
1994
1995     /// Returns the remaining items of this iterator as a mutable slice.
1996     ///
1997     /// # Examples
1998     ///
1999     /// ```
2000     /// let vec = vec!['a', 'b', 'c'];
2001     /// let mut into_iter = vec.into_iter();
2002     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2003     /// into_iter.as_mut_slice()[2] = 'z';
2004     /// assert_eq!(into_iter.next().unwrap(), 'a');
2005     /// assert_eq!(into_iter.next().unwrap(), 'b');
2006     /// assert_eq!(into_iter.next().unwrap(), 'z');
2007     /// ```
2008     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
2009     pub fn as_mut_slice(&mut self) -> &mut [T] {
2010         unsafe {
2011             slice::from_raw_parts_mut(self.ptr as *mut T, self.len())
2012         }
2013     }
2014 }
2015
2016 #[stable(feature = "rust1", since = "1.0.0")]
2017 unsafe impl<T: Send> Send for IntoIter<T> {}
2018 #[stable(feature = "rust1", since = "1.0.0")]
2019 unsafe impl<T: Sync> Sync for IntoIter<T> {}
2020
2021 #[stable(feature = "rust1", since = "1.0.0")]
2022 impl<T> Iterator for IntoIter<T> {
2023     type Item = T;
2024
2025     #[inline]
2026     fn next(&mut self) -> Option<T> {
2027         unsafe {
2028             if self.ptr as *const _ == self.end {
2029                 None
2030             } else {
2031                 if mem::size_of::<T>() == 0 {
2032                     // purposefully don't use 'ptr.offset' because for
2033                     // vectors with 0-size elements this would return the
2034                     // same pointer.
2035                     self.ptr = arith_offset(self.ptr as *const i8, 1) as *mut T;
2036
2037                     // Use a non-null pointer value
2038                     Some(ptr::read(EMPTY as *mut T))
2039                 } else {
2040                     let old = self.ptr;
2041                     self.ptr = self.ptr.offset(1);
2042
2043                     Some(ptr::read(old))
2044                 }
2045             }
2046         }
2047     }
2048
2049     #[inline]
2050     fn size_hint(&self) -> (usize, Option<usize>) {
2051         let diff = (self.end as usize) - (self.ptr as usize);
2052         let size = mem::size_of::<T>();
2053         let exact = diff /
2054                     (if size == 0 {
2055                          1
2056                      } else {
2057                          size
2058                      });
2059         (exact, Some(exact))
2060     }
2061
2062     #[inline]
2063     fn count(self) -> usize {
2064         self.len()
2065     }
2066 }
2067
2068 #[stable(feature = "rust1", since = "1.0.0")]
2069 impl<T> DoubleEndedIterator for IntoIter<T> {
2070     #[inline]
2071     fn next_back(&mut self) -> Option<T> {
2072         unsafe {
2073             if self.end == self.ptr {
2074                 None
2075             } else {
2076                 if mem::size_of::<T>() == 0 {
2077                     // See above for why 'ptr.offset' isn't used
2078                     self.end = arith_offset(self.end as *const i8, -1) as *mut T;
2079
2080                     // Use a non-null pointer value
2081                     Some(ptr::read(EMPTY as *mut T))
2082                 } else {
2083                     self.end = self.end.offset(-1);
2084
2085                     Some(ptr::read(self.end))
2086                 }
2087             }
2088         }
2089     }
2090 }
2091
2092 #[stable(feature = "rust1", since = "1.0.0")]
2093 impl<T> ExactSizeIterator for IntoIter<T> {
2094     fn is_empty(&self) -> bool {
2095         self.ptr == self.end
2096     }
2097 }
2098
2099 #[unstable(feature = "fused", issue = "35602")]
2100 impl<T> FusedIterator for IntoIter<T> {}
2101
2102 #[unstable(feature = "trusted_len", issue = "37572")]
2103 unsafe impl<T> TrustedLen for IntoIter<T> {}
2104
2105 #[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
2106 impl<T: Clone> Clone for IntoIter<T> {
2107     fn clone(&self) -> IntoIter<T> {
2108         self.as_slice().to_owned().into_iter()
2109     }
2110 }
2111
2112 #[stable(feature = "rust1", since = "1.0.0")]
2113 unsafe impl<#[may_dangle] T> Drop for IntoIter<T> {
2114     fn drop(&mut self) {
2115         // destroy the remaining elements
2116         for _x in self.by_ref() {}
2117
2118         // RawVec handles deallocation
2119         let _ = unsafe { RawVec::from_raw_parts(*self.buf, self.cap) };
2120     }
2121 }
2122
2123 /// A draining iterator for `Vec<T>`.
2124 ///
2125 /// This `struct` is created by the [`drain`] method on [`Vec`].
2126 ///
2127 /// [`drain`]: struct.Vec.html#method.drain
2128 /// [`Vec`]: struct.Vec.html
2129 #[stable(feature = "drain", since = "1.6.0")]
2130 pub struct Drain<'a, T: 'a> {
2131     /// Index of tail to preserve
2132     tail_start: usize,
2133     /// Length of tail
2134     tail_len: usize,
2135     /// Current remaining range to remove
2136     iter: slice::Iter<'a, T>,
2137     vec: Shared<Vec<T>>,
2138 }
2139
2140 #[stable(feature = "collection_debug", since = "1.17.0")]
2141 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Drain<'a, T> {
2142     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2143         f.debug_tuple("Drain")
2144          .field(&self.iter.as_slice())
2145          .finish()
2146     }
2147 }
2148
2149 #[stable(feature = "drain", since = "1.6.0")]
2150 unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
2151 #[stable(feature = "drain", since = "1.6.0")]
2152 unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
2153
2154 #[stable(feature = "drain", since = "1.6.0")]
2155 impl<'a, T> Iterator for Drain<'a, T> {
2156     type Item = T;
2157
2158     #[inline]
2159     fn next(&mut self) -> Option<T> {
2160         self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
2161     }
2162
2163     fn size_hint(&self) -> (usize, Option<usize>) {
2164         self.iter.size_hint()
2165     }
2166 }
2167
2168 #[stable(feature = "drain", since = "1.6.0")]
2169 impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
2170     #[inline]
2171     fn next_back(&mut self) -> Option<T> {
2172         self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
2173     }
2174 }
2175
2176 #[stable(feature = "drain", since = "1.6.0")]
2177 impl<'a, T> Drop for Drain<'a, T> {
2178     fn drop(&mut self) {
2179         // exhaust self first
2180         while let Some(_) = self.next() {}
2181
2182         if self.tail_len > 0 {
2183             unsafe {
2184                 let source_vec = &mut **self.vec;
2185                 // memmove back untouched tail, update to new length
2186                 let start = source_vec.len();
2187                 let tail = self.tail_start;
2188                 let src = source_vec.as_ptr().offset(tail as isize);
2189                 let dst = source_vec.as_mut_ptr().offset(start as isize);
2190                 ptr::copy(src, dst, self.tail_len);
2191                 source_vec.set_len(start + self.tail_len);
2192             }
2193         }
2194     }
2195 }
2196
2197
2198 #[stable(feature = "drain", since = "1.6.0")]
2199 impl<'a, T> ExactSizeIterator for Drain<'a, T> {
2200     fn is_empty(&self) -> bool {
2201         self.iter.is_empty()
2202     }
2203 }
2204
2205 #[unstable(feature = "fused", issue = "35602")]
2206 impl<'a, T> FusedIterator for Drain<'a, T> {}
2207
2208 /// A place for insertion at the back of a `Vec`.
2209 ///
2210 /// See [`Vec::place_back`](struct.Vec.html#method.place_back) for details.
2211 #[must_use = "places do nothing unless written to with `<-` syntax"]
2212 #[unstable(feature = "collection_placement",
2213            reason = "struct name and placement protocol are subject to change",
2214            issue = "30172")]
2215 #[derive(Debug)]
2216 pub struct PlaceBack<'a, T: 'a> {
2217     vec: &'a mut Vec<T>,
2218 }
2219
2220 #[unstable(feature = "collection_placement",
2221            reason = "placement protocol is subject to change",
2222            issue = "30172")]
2223 impl<'a, T> Placer<T> for PlaceBack<'a, T> {
2224     type Place = PlaceBack<'a, T>;
2225
2226     fn make_place(self) -> Self {
2227         // This will panic or abort if we would allocate > isize::MAX bytes
2228         // or if the length increment would overflow for zero-sized types.
2229         if self.vec.len == self.vec.buf.cap() {
2230             self.vec.buf.double();
2231         }
2232         self
2233     }
2234 }
2235
2236 #[unstable(feature = "collection_placement",
2237            reason = "placement protocol is subject to change",
2238            issue = "30172")]
2239 impl<'a, T> Place<T> for PlaceBack<'a, T> {
2240     fn pointer(&mut self) -> *mut T {
2241         unsafe { self.vec.as_mut_ptr().offset(self.vec.len as isize) }
2242     }
2243 }
2244
2245 #[unstable(feature = "collection_placement",
2246            reason = "placement protocol is subject to change",
2247            issue = "30172")]
2248 impl<'a, T> InPlace<T> for PlaceBack<'a, T> {
2249     type Owner = &'a mut T;
2250
2251     unsafe fn finalize(mut self) -> &'a mut T {
2252         let ptr = self.pointer();
2253         self.vec.len += 1;
2254         &mut *ptr
2255     }
2256 }