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 according to a predicate.
 842     ///
 843     /// The `same_bucket` function is passed references to two elements from the vector, and
 844     /// returns `true` if the elements compare equal, or `false` if they do not. Only the first
 845     /// of adjacent equal items is kept.
 846     ///
 847     /// If the vector is sorted, this removes all duplicates.
 848     ///
 849     /// # Examples
 850     ///
 851     /// ```
 852     /// use std::ascii::AsciiExt;
 853     ///
 854     /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
 855     ///
 856     /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
 857     ///
 858     /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
 859     /// ```
 860     #[stable(feature = "dedup_by", since = "1.16.0")]
 861     pub fn dedup_by<F>(&mut self, mut same_bucket: F) where F: FnMut(&mut T, &mut T) -> bool {
 862         unsafe {
 863             // Although we have a mutable reference to `self`, we cannot make
 864             // *arbitrary* changes. The `same_bucket` calls could panic, so we
 865             // must ensure that the vector is in a valid state at all time.
 866             //
 867             // The way that we handle this is by using swaps; we iterate
 868             // over all the elements, swapping as we go so that at the end
 869             // the elements we wish to keep are in the front, and those we
 870             // wish to reject are at the back. We can then truncate the
 871             // vector. This operation is still O(n).
 872             //
 873             // Example: We start in this state, where `r` represents "next
 874             // read" and `w` represents "next_write`.
 875             //
 876             //           r
 877             //     +---+---+---+---+---+---+
 878             //     | 0 | 1 | 1 | 2 | 3 | 3 |
 879             //     +---+---+---+---+---+---+
 880             //           w
 881             //
 882             // Comparing self[r] against self[w-1], this is not a duplicate, so
 883             // we swap self[r] and self[w] (no effect as r==w) and then increment both
 884             // r and w, leaving us with:
 885             //
 886             //               r
 887             //     +---+---+---+---+---+---+
 888             //     | 0 | 1 | 1 | 2 | 3 | 3 |
 889             //     +---+---+---+---+---+---+
 890             //               w
 891             //
 892             // Comparing self[r] against self[w-1], this value is a duplicate,
 893             // so we increment `r` but leave everything else unchanged:
 894             //
 895             //                   r
 896             //     +---+---+---+---+---+---+
 897             //     | 0 | 1 | 1 | 2 | 3 | 3 |
 898             //     +---+---+---+---+---+---+
 899             //               w
 900             //
 901             // Comparing self[r] against self[w-1], this is not a duplicate,
 902             // so swap self[r] and self[w] and advance r and w:
 903             //
 904             //                       r
 905             //     +---+---+---+---+---+---+
 906             //     | 0 | 1 | 2 | 1 | 3 | 3 |
 907             //     +---+---+---+---+---+---+
 908             //                   w
 909             //
 910             // Not a duplicate, repeat:
 911             //
 912             //                           r
 913             //     +---+---+---+---+---+---+
 914             //     | 0 | 1 | 2 | 3 | 1 | 3 |
 915             //     +---+---+---+---+---+---+
 916             //                       w
 917             //
 918             // Duplicate, advance r. End of vec. Truncate to w.
 919
 920             let ln = self.len();
 921             if ln <= 1 {
 922                 return;
 923             }
 924
 925             // Avoid bounds checks by using raw pointers.
 926             let p = self.as_mut_ptr();
 927             let mut r: usize = 1;
 928             let mut w: usize = 1;
 929
 930             while r < ln {
 931                 let p_r = p.offset(r as isize);
 932                 let p_wm1 = p.offset((w - 1) as isize);
 933                 if !same_bucket(&mut *p_r, &mut *p_wm1) {
 934                     if r != w {
 935                         let p_w = p_wm1.offset(1);
 936                         mem::swap(&mut *p_r, &mut *p_w);
 937                     }
 938                     w += 1;
 939                 }
 940                 r += 1;
 941             }
 942
 943             self.truncate(w);
 944         }
 945     }
 946
 947     /// Appends an element to the back of a collection.
 948     ///
 949     /// # Panics
 950     ///
 951     /// Panics if the number of elements in the vector overflows a `usize`.
 952     ///
 953     /// # Examples
 954     ///
 955     /// ```
 956     /// let mut vec = vec![1, 2];
 957     /// vec.push(3);
 958     /// assert_eq!(vec, [1, 2, 3]);
 959     /// ```
 960     #[inline]
 961     #[stable(feature = "rust1", since = "1.0.0")]
 962     pub fn push(&mut self, value: T) {
 963         // This will panic or abort if we would allocate > isize::MAX bytes
 964         // or if the length increment would overflow for zero-sized types.
 965         if self.len == self.buf.cap() {
 966             self.buf.double();
 967         }
 968         unsafe {
 969             let end = self.as_mut_ptr().offset(self.len as isize);
 970             ptr::write(end, value);
 971             self.len += 1;
 972         }
 973     }
 974
 975     /// Removes the last element from a vector and returns it, or [`None`] if it
 976     /// is empty.
 977     ///
 978     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 979     ///
 980     /// # Examples
 981     ///
 982     /// ```
 983     /// let mut vec = vec![1, 2, 3];
 984     /// assert_eq!(vec.pop(), Some(3));
 985     /// assert_eq!(vec, [1, 2]);
 986     /// ```
 987     #[inline]
 988     #[stable(feature = "rust1", since = "1.0.0")]
 989     pub fn pop(&mut self) -> Option<T> {
 990         if self.len == 0 {
 991             None
 992         } else {
 993             unsafe {
 994                 self.len -= 1;
 995                 Some(ptr::read(self.get_unchecked(self.len())))
 996             }
 997         }
 998     }
 999
1000     /// Moves all the elements of `other` into `Self`, leaving `other` empty.
1001     ///
1002     /// # Panics
1003     ///
1004     /// Panics if the number of elements in the vector overflows a `usize`.
1005     ///
1006     /// # Examples
1007     ///
1008     /// ```
1009     /// let mut vec = vec![1, 2, 3];
1010     /// let mut vec2 = vec![4, 5, 6];
1011     /// vec.append(&mut vec2);
1012     /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
1013     /// assert_eq!(vec2, []);
1014     /// ```
1015     #[inline]
1016     #[stable(feature = "append", since = "1.4.0")]
1017     pub fn append(&mut self, other: &mut Self) {
1018         self.reserve(other.len());
1019         let len = self.len();
1020         unsafe {
1021             ptr::copy_nonoverlapping(other.as_ptr(), self.get_unchecked_mut(len), other.len());
1022         }
1023
1024         self.len += other.len();
1025         unsafe {
1026             other.set_len(0);
1027         }
1028     }
1029
1030     /// Create a draining iterator that removes the specified range in the vector
1031     /// and yields the removed items.
1032     ///
1033     /// Note 1: The element range is removed even if the iterator is only
1034     /// partially consumed or not consumed at all.
1035     ///
1036     /// Note 2: It is unspecified how many elements are removed from the vector,
1037     /// if the `Drain` value is leaked.
1038     ///
1039     /// # Panics
1040     ///
1041     /// Panics if the starting point is greater than the end point or if
1042     /// the end point is greater than the length of the vector.
1043     ///
1044     /// # Examples
1045     ///
1046     /// ```
1047     /// let mut v = vec![1, 2, 3];
1048     /// let u: Vec<_> = v.drain(1..).collect();
1049     /// assert_eq!(v, &[1]);
1050     /// assert_eq!(u, &[2, 3]);
1051     ///
1052     /// // A full range clears the vector
1053     /// v.drain(..);
1054     /// assert_eq!(v, &[]);
1055     /// ```
1056     #[stable(feature = "drain", since = "1.6.0")]
1057     pub fn drain<R>(&mut self, range: R) -> Drain<T>
1058         where R: RangeArgument<usize>
1059     {
1060         // Memory safety
1061         //
1062         // When the Drain is first created, it shortens the length of
1063         // the source vector to make sure no uninitalized or moved-from elements
1064         // are accessible at all if the Drain's destructor never gets to run.
1065         //
1066         // Drain will ptr::read out the values to remove.
1067         // When finished, remaining tail of the vec is copied back to cover
1068         // the hole, and the vector length is restored to the new length.
1069         //
1070         let len = self.len();
1071         let start = match range.start() {
1072             Included(&n) => n,
1073             Excluded(&n) => n + 1,
1074             Unbounded    => 0,
1075         };
1076         let end = match range.end() {
1077             Included(&n) => n + 1,
1078             Excluded(&n) => n,
1079             Unbounded    => len,
1080         };
1081         assert!(start <= end);
1082         assert!(end <= len);
1083
1084         unsafe {
1085             // set self.vec length's to start, to be safe in case Drain is leaked
1086             self.set_len(start);
1087             // Use the borrow in the IterMut to indicate borrowing behavior of the
1088             // whole Drain iterator (like &mut T).
1089             let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().offset(start as isize),
1090                                                         end - start);
1091             Drain {
1092                 tail_start: end,
1093                 tail_len: len - end,
1094                 iter: range_slice.iter(),
1095                 vec: Shared::new(self as *mut _),
1096             }
1097         }
1098     }
1099
1100     /// Clears the vector, removing all values.
1101     ///
1102     /// Note that this method has no effect on the allocated capacity
1103     /// of the vector.
1104     ///
1105     /// # Examples
1106     ///
1107     /// ```
1108     /// let mut v = vec![1, 2, 3];
1109     ///
1110     /// v.clear();
1111     ///
1112     /// assert!(v.is_empty());
1113     /// ```
1114     #[inline]
1115     #[stable(feature = "rust1", since = "1.0.0")]
1116     pub fn clear(&mut self) {
1117         self.truncate(0)
1118     }
1119
1120     /// Returns the number of elements in the vector.
1121     ///
1122     /// # Examples
1123     ///
1124     /// ```
1125     /// let a = vec![1, 2, 3];
1126     /// assert_eq!(a.len(), 3);
1127     /// ```
1128     #[inline]
1129     #[stable(feature = "rust1", since = "1.0.0")]
1130     pub fn len(&self) -> usize {
1131         self.len
1132     }
1133
1134     /// Returns `true` if the vector contains no elements.
1135     ///
1136     /// # Examples
1137     ///
1138     /// ```
1139     /// let mut v = Vec::new();
1140     /// assert!(v.is_empty());
1141     ///
1142     /// v.push(1);
1143     /// assert!(!v.is_empty());
1144     /// ```
1145     #[stable(feature = "rust1", since = "1.0.0")]
1146     pub fn is_empty(&self) -> bool {
1147         self.len() == 0
1148     }
1149
1150     /// Splits the collection into two at the given index.
1151     ///
1152     /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
1153     /// and the returned `Self` contains elements `[at, len)`.
1154     ///
1155     /// Note that the capacity of `self` does not change.
1156     ///
1157     /// # Panics
1158     ///
1159     /// Panics if `at > len`.
1160     ///
1161     /// # Examples
1162     ///
1163     /// ```
1164     /// let mut vec = vec![1,2,3];
1165     /// let vec2 = vec.split_off(1);
1166     /// assert_eq!(vec, [1]);
1167     /// assert_eq!(vec2, [2, 3]);
1168     /// ```
1169     #[inline]
1170     #[stable(feature = "split_off", since = "1.4.0")]
1171     pub fn split_off(&mut self, at: usize) -> Self {
1172         assert!(at <= self.len(), "`at` out of bounds");
1173
1174         let other_len = self.len - at;
1175         let mut other = Vec::with_capacity(other_len);
1176
1177         // Unsafely `set_len` and copy items to `other`.
1178         unsafe {
1179             self.set_len(at);
1180             other.set_len(other_len);
1181
1182             ptr::copy_nonoverlapping(self.as_ptr().offset(at as isize),
1183                                      other.as_mut_ptr(),
1184                                      other.len());
1185         }
1186         other
1187     }
1188 }
1189
1190 impl<T: Clone> Vec<T> {
1191     /// Resizes the `Vec` in-place so that `len()` is equal to `new_len`.
1192     ///
1193     /// If `new_len` is greater than `len()`, the `Vec` is extended by the
1194     /// difference, with each additional slot filled with `value`.
1195     /// If `new_len` is less than `len()`, the `Vec` is simply truncated.
1196     ///
1197     /// # Examples
1198     ///
1199     /// ```
1200     /// let mut vec = vec!["hello"];
1201     /// vec.resize(3, "world");
1202     /// assert_eq!(vec, ["hello", "world", "world"]);
1203     ///
1204     /// let mut vec = vec![1, 2, 3, 4];
1205     /// vec.resize(2, 0);
1206     /// assert_eq!(vec, [1, 2]);
1207     /// ```
1208     #[stable(feature = "vec_resize", since = "1.5.0")]
1209     pub fn resize(&mut self, new_len: usize, value: T) {
1210         let len = self.len();
1211
1212         if new_len > len {
1213             self.extend_with_element(new_len - len, value);
1214         } else {
1215             self.truncate(new_len);
1216         }
1217     }
1218
1219     /// Extend the vector by `n` additional clones of `value`.
1220     fn extend_with_element(&mut self, n: usize, value: T) {
1221         self.reserve(n);
1222
1223         unsafe {
1224             let mut ptr = self.as_mut_ptr().offset(self.len() as isize);
1225             // Use SetLenOnDrop to work around bug where compiler
1226             // may not realize the store through `ptr` through self.set_len()
1227             // don't alias.
1228             let mut local_len = SetLenOnDrop::new(&mut self.len);
1229
1230             // Write all elements except the last one
1231             for _ in 1..n {
1232                 ptr::write(ptr, value.clone());
1233                 ptr = ptr.offset(1);
1234                 // Increment the length in every step in case clone() panics
1235                 local_len.increment_len(1);
1236             }
1237
1238             if n > 0 {
1239                 // We can write the last element directly without cloning needlessly
1240                 ptr::write(ptr, value);
1241                 local_len.increment_len(1);
1242             }
1243
1244             // len set by scope guard
1245         }
1246     }
1247
1248     /// Clones and appends all elements in a slice to the `Vec`.
1249     ///
1250     /// Iterates over the slice `other`, clones each element, and then appends
1251     /// it to this `Vec`. The `other` vector is traversed in-order.
1252     ///
1253     /// Note that this function is same as `extend` except that it is
1254     /// specialized to work with slices instead. If and when Rust gets
1255     /// specialization this function will likely be deprecated (but still
1256     /// available).
1257     ///
1258     /// # Examples
1259     ///
1260     /// ```
1261     /// let mut vec = vec![1];
1262     /// vec.extend_from_slice(&[2, 3, 4]);
1263     /// assert_eq!(vec, [1, 2, 3, 4]);
1264     /// ```
1265     #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
1266     pub fn extend_from_slice(&mut self, other: &[T]) {
1267         self.spec_extend(other.iter())
1268     }
1269
1270     /// Returns a place for insertion at the back of the `Vec`.
1271     ///
1272     /// Using this method with placement syntax is equivalent to [`push`](#method.push),
1273     /// but may be more efficient.
1274     ///
1275     /// # Examples
1276     ///
1277     /// ```
1278     /// #![feature(collection_placement)]
1279     /// #![feature(placement_in_syntax)]
1280     ///
1281     /// let mut vec = vec![1, 2];
1282     /// vec.place_back() <- 3;
1283     /// vec.place_back() <- 4;
1284     /// assert_eq!(&vec, &[1, 2, 3, 4]);
1285     /// ```
1286     #[unstable(feature = "collection_placement",
1287                reason = "placement protocol is subject to change",
1288                issue = "30172")]
1289     pub fn place_back(&mut self) -> PlaceBack<T> {
1290         PlaceBack { vec: self }
1291     }
1292 }
1293
1294 // Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
1295 //
1296 // The idea is: The length field in SetLenOnDrop is a local variable
1297 // that the optimizer will see does not alias with any stores through the Vec's data
1298 // pointer. This is a workaround for alias analysis issue #32155
1299 struct SetLenOnDrop<'a> {
1300     len: &'a mut usize,
1301     local_len: usize,
1302 }
1303
1304 impl<'a> SetLenOnDrop<'a> {
1305     #[inline]
1306     fn new(len: &'a mut usize) -> Self {
1307         SetLenOnDrop { local_len: *len, len: len }
1308     }
1309
1310     #[inline]
1311     fn increment_len(&mut self, increment: usize) {
1312         self.local_len += increment;
1313     }
1314 }
1315
1316 impl<'a> Drop for SetLenOnDrop<'a> {
1317     #[inline]
1318     fn drop(&mut self) {
1319         *self.len = self.local_len;
1320     }
1321 }
1322
1323 impl<T: PartialEq> Vec<T> {
1324     /// Removes consecutive repeated elements in the vector.
1325     ///
1326     /// If the vector is sorted, this removes all duplicates.
1327     ///
1328     /// # Examples
1329     ///
1330     /// ```
1331     /// let mut vec = vec![1, 2, 2, 3, 2];
1332     ///
1333     /// vec.dedup();
1334     ///
1335     /// assert_eq!(vec, [1, 2, 3, 2]);
1336     /// ```
1337     #[stable(feature = "rust1", since = "1.0.0")]
1338     #[inline]
1339     pub fn dedup(&mut self) {
1340         self.dedup_by(|a, b| a == b)
1341     }
1342
1343     /// Removes the first instance of `item` from the vector if the item exists.
1344     ///
1345     /// # Examples
1346     ///
1347     /// ```
1348     ///# #![feature(vec_remove_item)]
1349     /// let mut vec = vec![1, 2, 3, 1];
1350     ///
1351     /// vec.remove_item(&1);
1352     ///
1353     /// assert_eq!(vec, vec![2, 3, 1]);
1354     /// ```
1355     #[unstable(feature = "vec_remove_item", reason = "recently added", issue = "40062")]
1356     pub fn remove_item(&mut self, item: &T) -> Option<T> {
1357         let pos = match self.iter().position(|x| *x == *item) {
1358             Some(x) => x,
1359             None => return None,
1360         };
1361         Some(self.remove(pos))
1362     }
1363 }
1364
1365 ////////////////////////////////////////////////////////////////////////////////
1366 // Internal methods and functions
1367 ////////////////////////////////////////////////////////////////////////////////
1368
1369 #[doc(hidden)]
1370 #[stable(feature = "rust1", since = "1.0.0")]
1371 pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
1372     let mut v = Vec::with_capacity(n);
1373     v.extend_with_element(n, elem);
1374     v
1375 }
1376
1377 ////////////////////////////////////////////////////////////////////////////////
1378 // Common trait implementations for Vec
1379 ////////////////////////////////////////////////////////////////////////////////
1380
1381 #[stable(feature = "rust1", since = "1.0.0")]
1382 impl<T: Clone> Clone for Vec<T> {
1383     #[cfg(not(test))]
1384     fn clone(&self) -> Vec<T> {
1385         <[T]>::to_vec(&**self)
1386     }
1387
1388     // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
1389     // required for this method definition, is not available. Instead use the
1390     // `slice::to_vec`  function which is only available with cfg(test)
1391     // NB see the slice::hack module in slice.rs for more information
1392     #[cfg(test)]
1393     fn clone(&self) -> Vec<T> {
1394         ::slice::to_vec(&**self)
1395     }
1396
1397     fn clone_from(&mut self, other: &Vec<T>) {
1398         // drop anything in self that will not be overwritten
1399         self.truncate(other.len());
1400         let len = self.len();
1401
1402         // reuse the contained values' allocations/resources.
1403         self.clone_from_slice(&other[..len]);
1404
1405         // self.len <= other.len due to the truncate above, so the
1406         // slice here is always in-bounds.
1407         self.extend_from_slice(&other[len..]);
1408     }
1409 }
1410
1411 #[stable(feature = "rust1", since = "1.0.0")]
1412 impl<T: Hash> Hash for Vec<T> {
1413     #[inline]
1414     fn hash<H: hash::Hasher>(&self, state: &mut H) {
1415         Hash::hash(&**self, state)
1416     }
1417 }
1418
1419 #[stable(feature = "rust1", since = "1.0.0")]
1420 impl<T> Index<usize> for Vec<T> {
1421     type Output = T;
1422
1423     #[inline]
1424     fn index(&self, index: usize) -> &T {
1425         // NB built-in indexing via `&[T]`
1426         &(**self)[index]
1427     }
1428 }
1429
1430 #[stable(feature = "rust1", since = "1.0.0")]
1431 impl<T> IndexMut<usize> for Vec<T> {
1432     #[inline]
1433     fn index_mut(&mut self, index: usize) -> &mut T {
1434         // NB built-in indexing via `&mut [T]`
1435         &mut (**self)[index]
1436     }
1437 }
1438
1439
1440 #[stable(feature = "rust1", since = "1.0.0")]
1441 impl<T> ops::Index<ops::Range<usize>> for Vec<T> {
1442     type Output = [T];
1443
1444     #[inline]
1445     fn index(&self, index: ops::Range<usize>) -> &[T] {
1446         Index::index(&**self, index)
1447     }
1448 }
1449 #[stable(feature = "rust1", since = "1.0.0")]
1450 impl<T> ops::Index<ops::RangeTo<usize>> for Vec<T> {
1451     type Output = [T];
1452
1453     #[inline]
1454     fn index(&self, index: ops::RangeTo<usize>) -> &[T] {
1455         Index::index(&**self, index)
1456     }
1457 }
1458 #[stable(feature = "rust1", since = "1.0.0")]
1459 impl<T> ops::Index<ops::RangeFrom<usize>> for Vec<T> {
1460     type Output = [T];
1461
1462     #[inline]
1463     fn index(&self, index: ops::RangeFrom<usize>) -> &[T] {
1464         Index::index(&**self, index)
1465     }
1466 }
1467 #[stable(feature = "rust1", since = "1.0.0")]
1468 impl<T> ops::Index<ops::RangeFull> for Vec<T> {
1469     type Output = [T];
1470
1471     #[inline]
1472     fn index(&self, _index: ops::RangeFull) -> &[T] {
1473         self
1474     }
1475 }
1476 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1477 impl<T> ops::Index<ops::RangeInclusive<usize>> for Vec<T> {
1478     type Output = [T];
1479
1480     #[inline]
1481     fn index(&self, index: ops::RangeInclusive<usize>) -> &[T] {
1482         Index::index(&**self, index)
1483     }
1484 }
1485 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1486 impl<T> ops::Index<ops::RangeToInclusive<usize>> for Vec<T> {
1487     type Output = [T];
1488
1489     #[inline]
1490     fn index(&self, index: ops::RangeToInclusive<usize>) -> &[T] {
1491         Index::index(&**self, index)
1492     }
1493 }
1494
1495 #[stable(feature = "rust1", since = "1.0.0")]
1496 impl<T> ops::IndexMut<ops::Range<usize>> for Vec<T> {
1497     #[inline]
1498     fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] {
1499         IndexMut::index_mut(&mut **self, index)
1500     }
1501 }
1502 #[stable(feature = "rust1", since = "1.0.0")]
1503 impl<T> ops::IndexMut<ops::RangeTo<usize>> for Vec<T> {
1504     #[inline]
1505     fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] {
1506         IndexMut::index_mut(&mut **self, index)
1507     }
1508 }
1509 #[stable(feature = "rust1", since = "1.0.0")]
1510 impl<T> ops::IndexMut<ops::RangeFrom<usize>> for Vec<T> {
1511     #[inline]
1512     fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] {
1513         IndexMut::index_mut(&mut **self, index)
1514     }
1515 }
1516 #[stable(feature = "rust1", since = "1.0.0")]
1517 impl<T> ops::IndexMut<ops::RangeFull> for Vec<T> {
1518     #[inline]
1519     fn index_mut(&mut self, _index: ops::RangeFull) -> &mut [T] {
1520         self
1521     }
1522 }
1523 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1524 impl<T> ops::IndexMut<ops::RangeInclusive<usize>> for Vec<T> {
1525     #[inline]
1526     fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut [T] {
1527         IndexMut::index_mut(&mut **self, index)
1528     }
1529 }
1530 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1531 impl<T> ops::IndexMut<ops::RangeToInclusive<usize>> for Vec<T> {
1532     #[inline]
1533     fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut [T] {
1534         IndexMut::index_mut(&mut **self, index)
1535     }
1536 }
1537
1538 #[stable(feature = "rust1", since = "1.0.0")]
1539 impl<T> ops::Deref for Vec<T> {
1540     type Target = [T];
1541
1542     fn deref(&self) -> &[T] {
1543         unsafe {
1544             let p = self.buf.ptr();
1545             assume(!p.is_null());
1546             slice::from_raw_parts(p, self.len)
1547         }
1548     }
1549 }
1550
1551 #[stable(feature = "rust1", since = "1.0.0")]
1552 impl<T> ops::DerefMut for Vec<T> {
1553     fn deref_mut(&mut self) -> &mut [T] {
1554         unsafe {
1555             let ptr = self.buf.ptr();
1556             assume(!ptr.is_null());
1557             slice::from_raw_parts_mut(ptr, self.len)
1558         }
1559     }
1560 }
1561
1562 #[stable(feature = "rust1", since = "1.0.0")]
1563 impl<T> FromIterator<T> for Vec<T> {
1564     #[inline]
1565     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
1566         <Self as SpecExtend<T, I::IntoIter>>::from_iter(iter.into_iter())
1567     }
1568 }
1569
1570 #[stable(feature = "rust1", since = "1.0.0")]
1571 impl<T> IntoIterator for Vec<T> {
1572     type Item = T;
1573     type IntoIter = IntoIter<T>;
1574
1575     /// Creates a consuming iterator, that is, one that moves each value out of
1576     /// the vector (from start to end). The vector cannot be used after calling
1577     /// this.
1578     ///
1579     /// # Examples
1580     ///
1581     /// ```
1582     /// let v = vec!["a".to_string(), "b".to_string()];
1583     /// for s in v.into_iter() {
1584     ///     // s has type String, not &String
1585     ///     println!("{}", s);
1586     /// }
1587     /// ```
1588     #[inline]
1589     fn into_iter(mut self) -> IntoIter<T> {
1590         unsafe {
1591             let begin = self.as_mut_ptr();
1592             assume(!begin.is_null());
1593             let end = if mem::size_of::<T>() == 0 {
1594                 arith_offset(begin as *const i8, self.len() as isize) as *const T
1595             } else {
1596                 begin.offset(self.len() as isize) as *const T
1597             };
1598             let cap = self.buf.cap();
1599             mem::forget(self);
1600             IntoIter {
1601                 buf: Shared::new(begin),
1602                 cap: cap,
1603                 ptr: begin,
1604                 end: end,
1605             }
1606         }
1607     }
1608 }
1609
1610 #[stable(feature = "rust1", since = "1.0.0")]
1611 impl<'a, T> IntoIterator for &'a Vec<T> {
1612     type Item = &'a T;
1613     type IntoIter = slice::Iter<'a, T>;
1614
1615     fn into_iter(self) -> slice::Iter<'a, T> {
1616         self.iter()
1617     }
1618 }
1619
1620 #[stable(feature = "rust1", since = "1.0.0")]
1621 impl<'a, T> IntoIterator for &'a mut Vec<T> {
1622     type Item = &'a mut T;
1623     type IntoIter = slice::IterMut<'a, T>;
1624
1625     fn into_iter(mut self) -> slice::IterMut<'a, T> {
1626         self.iter_mut()
1627     }
1628 }
1629
1630 #[stable(feature = "rust1", since = "1.0.0")]
1631 impl<T> Extend<T> for Vec<T> {
1632     #[inline]
1633     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1634         <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
1635     }
1636 }
1637
1638 // Specialization trait used for Vec::from_iter and Vec::extend
1639 trait SpecExtend<T, I> {
1640     fn from_iter(iter: I) -> Self;
1641     fn spec_extend(&mut self, iter: I);
1642 }
1643
1644 impl<T, I> SpecExtend<T, I> for Vec<T>
1645     where I: Iterator<Item=T>,
1646 {
1647     default fn from_iter(mut iterator: I) -> Self {
1648         // Unroll the first iteration, as the vector is going to be
1649         // expanded on this iteration in every case when the iterable is not
1650         // empty, but the loop in extend_desugared() is not going to see the
1651         // vector being full in the few subsequent loop iterations.
1652         // So we get better branch prediction.
1653         let mut vector = match iterator.next() {
1654             None => return Vec::new(),
1655             Some(element) => {
1656                 let (lower, _) = iterator.size_hint();
1657                 let mut vector = Vec::with_capacity(lower.saturating_add(1));
1658                 unsafe {
1659                     ptr::write(vector.get_unchecked_mut(0), element);
1660                     vector.set_len(1);
1661                 }
1662                 vector
1663             }
1664         };
1665         <Vec<T> as SpecExtend<T, I>>::spec_extend(&mut vector, iterator);
1666         vector
1667     }
1668
1669     default fn spec_extend(&mut self, iter: I) {
1670         self.extend_desugared(iter)
1671     }
1672 }
1673
1674 impl<T, I> SpecExtend<T, I> for Vec<T>
1675     where I: TrustedLen<Item=T>,
1676 {
1677     default fn from_iter(iterator: I) -> Self {
1678         let mut vector = Vec::new();
1679         vector.spec_extend(iterator);
1680         vector
1681     }
1682
1683     fn spec_extend(&mut self, iterator: I) {
1684         // This is the case for a TrustedLen iterator.
1685         let (low, high) = iterator.size_hint();
1686         if let Some(high_value) = high {
1687             debug_assert_eq!(low, high_value,
1688                              "TrustedLen iterator's size hint is not exact: {:?}",
1689                              (low, high));
1690         }
1691         if let Some(additional) = high {
1692             self.reserve(additional);
1693             unsafe {
1694                 let mut ptr = self.as_mut_ptr().offset(self.len() as isize);
1695                 let mut local_len = SetLenOnDrop::new(&mut self.len);
1696                 for element in iterator {
1697                     ptr::write(ptr, element);
1698                     ptr = ptr.offset(1);
1699                     // NB can't overflow since we would have had to alloc the address space
1700                     local_len.increment_len(1);
1701                 }
1702             }
1703         } else {
1704             self.extend_desugared(iterator)
1705         }
1706     }
1707 }
1708
1709 impl<T> SpecExtend<T, IntoIter<T>> for Vec<T> {
1710     fn from_iter(iterator: IntoIter<T>) -> Self {
1711         // A common case is passing a vector into a function which immediately
1712         // re-collects into a vector. We can short circuit this if the IntoIter
1713         // has not been advanced at all.
1714         if *iterator.buf == iterator.ptr as *mut T {
1715             unsafe {
1716                 let vec = Vec::from_raw_parts(*iterator.buf as *mut T,
1717                                               iterator.len(),
1718                                               iterator.cap);
1719                 mem::forget(iterator);
1720                 vec
1721             }
1722         } else {
1723             let mut vector = Vec::new();
1724             vector.spec_extend(iterator);
1725             vector
1726         }
1727     }
1728 }
1729
1730 impl<'a, T: 'a, I> SpecExtend<&'a T, I> for Vec<T>
1731     where I: Iterator<Item=&'a T>,
1732           T: Clone,
1733 {
1734     default fn from_iter(iterator: I) -> Self {
1735         SpecExtend::from_iter(iterator.cloned())
1736     }
1737
1738     default fn spec_extend(&mut self, iterator: I) {
1739         self.spec_extend(iterator.cloned())
1740     }
1741 }
1742
1743 impl<'a, T: 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T>
1744     where T: Copy,
1745 {
1746     fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
1747         let slice = iterator.as_slice();
1748         self.reserve(slice.len());
1749         unsafe {
1750             let len = self.len();
1751             self.set_len(len + slice.len());
1752             self.get_unchecked_mut(len..).copy_from_slice(slice);
1753         }
1754     }
1755 }
1756
1757 impl<T> Vec<T> {
1758     fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
1759         // This is the case for a general iterator.
1760         //
1761         // This function should be the moral equivalent of:
1762         //
1763         //      for item in iterator {
1764         //          self.push(item);
1765         //      }
1766         while let Some(element) = iterator.next() {
1767             let len = self.len();
1768             if len == self.capacity() {
1769                 let (lower, _) = iterator.size_hint();
1770                 self.reserve(lower.saturating_add(1));
1771             }
1772             unsafe {
1773                 ptr::write(self.get_unchecked_mut(len), element);
1774                 // NB can't overflow since we would have had to alloc the address space
1775                 self.set_len(len + 1);
1776             }
1777         }
1778     }
1779 }
1780
1781 #[stable(feature = "extend_ref", since = "1.2.0")]
1782 impl<'a, T: 'a + Copy> Extend<&'a T> for Vec<T> {
1783     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1784         self.spec_extend(iter.into_iter())
1785     }
1786 }
1787
1788 macro_rules! __impl_slice_eq1 {
1789     ($Lhs: ty, $Rhs: ty) => {
1790         __impl_slice_eq1! { $Lhs, $Rhs, Sized }
1791     };
1792     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
1793         #[stable(feature = "rust1", since = "1.0.0")]
1794         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
1795             #[inline]
1796             fn eq(&self, other: &$Rhs) -> bool { self[..] == other[..] }
1797             #[inline]
1798             fn ne(&self, other: &$Rhs) -> bool { self[..] != other[..] }
1799         }
1800     }
1801 }
1802
1803 __impl_slice_eq1! { Vec<A>, Vec<B> }
1804 __impl_slice_eq1! { Vec<A>, &'b [B] }
1805 __impl_slice_eq1! { Vec<A>, &'b mut [B] }
1806 __impl_slice_eq1! { Cow<'a, [A]>, &'b [B], Clone }
1807 __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B], Clone }
1808 __impl_slice_eq1! { Cow<'a, [A]>, Vec<B>, Clone }
1809
1810 macro_rules! array_impls {
1811     ($($N: expr)+) => {
1812         $(
1813             // NOTE: some less important impls are omitted to reduce code bloat
1814             __impl_slice_eq1! { Vec<A>, [B; $N] }
1815             __impl_slice_eq1! { Vec<A>, &'b [B; $N] }
1816             // __impl_slice_eq1! { Vec<A>, &'b mut [B; $N] }
1817             // __impl_slice_eq1! { Cow<'a, [A]>, [B; $N], Clone }
1818             // __impl_slice_eq1! { Cow<'a, [A]>, &'b [B; $N], Clone }
1819             // __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B; $N], Clone }
1820         )+
1821     }
1822 }
1823
1824 array_impls! {
1825      0  1  2  3  4  5  6  7  8  9
1826     10 11 12 13 14 15 16 17 18 19
1827     20 21 22 23 24 25 26 27 28 29
1828     30 31 32
1829 }
1830
1831 /// Implements comparison of vectors, lexicographically.
1832 #[stable(feature = "rust1", since = "1.0.0")]
1833 impl<T: PartialOrd> PartialOrd for Vec<T> {
1834     #[inline]
1835     fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
1836         PartialOrd::partial_cmp(&**self, &**other)
1837     }
1838 }
1839
1840 #[stable(feature = "rust1", since = "1.0.0")]
1841 impl<T: Eq> Eq for Vec<T> {}
1842
1843 /// Implements ordering of vectors, lexicographically.
1844 #[stable(feature = "rust1", since = "1.0.0")]
1845 impl<T: Ord> Ord for Vec<T> {
1846     #[inline]
1847     fn cmp(&self, other: &Vec<T>) -> Ordering {
1848         Ord::cmp(&**self, &**other)
1849     }
1850 }
1851
1852 #[stable(feature = "rust1", since = "1.0.0")]
1853 unsafe impl<#[may_dangle] T> Drop for Vec<T> {
1854     fn drop(&mut self) {
1855         unsafe {
1856             // use drop for [T]
1857             ptr::drop_in_place(&mut self[..]);
1858         }
1859         // RawVec handles deallocation
1860     }
1861 }
1862
1863 #[stable(feature = "rust1", since = "1.0.0")]
1864 impl<T> Default for Vec<T> {
1865     /// Creates an empty `Vec<T>`.
1866     fn default() -> Vec<T> {
1867         Vec::new()
1868     }
1869 }
1870
1871 #[stable(feature = "rust1", since = "1.0.0")]
1872 impl<T: fmt::Debug> fmt::Debug for Vec<T> {
1873     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1874         fmt::Debug::fmt(&**self, f)
1875     }
1876 }
1877
1878 #[stable(feature = "rust1", since = "1.0.0")]
1879 impl<T> AsRef<Vec<T>> for Vec<T> {
1880     fn as_ref(&self) -> &Vec<T> {
1881         self
1882     }
1883 }
1884
1885 #[stable(feature = "vec_as_mut", since = "1.5.0")]
1886 impl<T> AsMut<Vec<T>> for Vec<T> {
1887     fn as_mut(&mut self) -> &mut Vec<T> {
1888         self
1889     }
1890 }
1891
1892 #[stable(feature = "rust1", since = "1.0.0")]
1893 impl<T> AsRef<[T]> for Vec<T> {
1894     fn as_ref(&self) -> &[T] {
1895         self
1896     }
1897 }
1898
1899 #[stable(feature = "vec_as_mut", since = "1.5.0")]
1900 impl<T> AsMut<[T]> for Vec<T> {
1901     fn as_mut(&mut self) -> &mut [T] {
1902         self
1903     }
1904 }
1905
1906 #[stable(feature = "rust1", since = "1.0.0")]
1907 impl<'a, T: Clone> From<&'a [T]> for Vec<T> {
1908     #[cfg(not(test))]
1909     fn from(s: &'a [T]) -> Vec<T> {
1910         s.to_vec()
1911     }
1912     #[cfg(test)]
1913     fn from(s: &'a [T]) -> Vec<T> {
1914         ::slice::to_vec(s)
1915     }
1916 }
1917
1918 #[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
1919 impl<'a, T> From<Cow<'a, [T]>> for Vec<T> where [T]: ToOwned<Owned=Vec<T>> {
1920     fn from(s: Cow<'a, [T]>) -> Vec<T> {
1921         s.into_owned()
1922     }
1923 }
1924
1925 // note: test pulls in libstd, which causes errors here
1926 #[cfg(not(test))]
1927 #[stable(feature = "vec_from_box", since = "1.17.0")]
1928 impl<T> From<Box<[T]>> for Vec<T> {
1929     fn from(s: Box<[T]>) -> Vec<T> {
1930         s.into_vec()
1931     }
1932 }
1933
1934 #[stable(feature = "box_from_vec", since = "1.17.0")]
1935 impl<T> Into<Box<[T]>> for Vec<T> {
1936     fn into(self) -> Box<[T]> {
1937         self.into_boxed_slice()
1938     }
1939 }
1940
1941 #[stable(feature = "rust1", since = "1.0.0")]
1942 impl<'a> From<&'a str> for Vec<u8> {
1943     fn from(s: &'a str) -> Vec<u8> {
1944         From::from(s.as_bytes())
1945     }
1946 }
1947
1948 ////////////////////////////////////////////////////////////////////////////////
1949 // Clone-on-write
1950 ////////////////////////////////////////////////////////////////////////////////
1951
1952 #[stable(feature = "cow_from_vec", since = "1.7.0")]
1953 impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> {
1954     fn from(s: &'a [T]) -> Cow<'a, [T]> {
1955         Cow::Borrowed(s)
1956     }
1957 }
1958
1959 #[stable(feature = "cow_from_vec", since = "1.7.0")]
1960 impl<'a, T: Clone> From<Vec<T>> for Cow<'a, [T]> {
1961     fn from(v: Vec<T>) -> Cow<'a, [T]> {
1962         Cow::Owned(v)
1963     }
1964 }
1965
1966 #[stable(feature = "rust1", since = "1.0.0")]
1967 impl<'a, T> FromIterator<T> for Cow<'a, [T]> where T: Clone {
1968     fn from_iter<I: IntoIterator<Item = T>>(it: I) -> Cow<'a, [T]> {
1969         Cow::Owned(FromIterator::from_iter(it))
1970     }
1971 }
1972
1973 ////////////////////////////////////////////////////////////////////////////////
1974 // Iterators
1975 ////////////////////////////////////////////////////////////////////////////////
1976
1977 /// An iterator that moves out of a vector.
1978 ///
1979 /// This `struct` is created by the `into_iter` method on [`Vec`][`Vec`] (provided
1980 /// by the [`IntoIterator`] trait).
1981 ///
1982 /// [`Vec`]: struct.Vec.html
1983 /// [`IntoIterator`]: ../../std/iter/trait.IntoIterator.html
1984 #[stable(feature = "rust1", since = "1.0.0")]
1985 pub struct IntoIter<T> {
1986     buf: Shared<T>,
1987     cap: usize,
1988     ptr: *const T,
1989     end: *const T,
1990 }
1991
1992 #[stable(feature = "vec_intoiter_debug", since = "1.13.0")]
1993 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
1994     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1995         f.debug_tuple("IntoIter")
1996             .field(&self.as_slice())
1997             .finish()
1998     }
1999 }
2000
2001 impl<T> IntoIter<T> {
2002     /// Returns the remaining items of this iterator as a slice.
2003     ///
2004     /// # Examples
2005     ///
2006     /// ```
2007     /// let vec = vec!['a', 'b', 'c'];
2008     /// let mut into_iter = vec.into_iter();
2009     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2010     /// let _ = into_iter.next().unwrap();
2011     /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
2012     /// ```
2013     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
2014     pub fn as_slice(&self) -> &[T] {
2015         unsafe {
2016             slice::from_raw_parts(self.ptr, self.len())
2017         }
2018     }
2019
2020     /// Returns the remaining items of this iterator as a mutable slice.
2021     ///
2022     /// # Examples
2023     ///
2024     /// ```
2025     /// let vec = vec!['a', 'b', 'c'];
2026     /// let mut into_iter = vec.into_iter();
2027     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2028     /// into_iter.as_mut_slice()[2] = 'z';
2029     /// assert_eq!(into_iter.next().unwrap(), 'a');
2030     /// assert_eq!(into_iter.next().unwrap(), 'b');
2031     /// assert_eq!(into_iter.next().unwrap(), 'z');
2032     /// ```
2033     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
2034     pub fn as_mut_slice(&mut self) -> &mut [T] {
2035         unsafe {
2036             slice::from_raw_parts_mut(self.ptr as *mut T, self.len())
2037         }
2038     }
2039 }
2040
2041 #[stable(feature = "rust1", since = "1.0.0")]
2042 unsafe impl<T: Send> Send for IntoIter<T> {}
2043 #[stable(feature = "rust1", since = "1.0.0")]
2044 unsafe impl<T: Sync> Sync for IntoIter<T> {}
2045
2046 #[stable(feature = "rust1", since = "1.0.0")]
2047 impl<T> Iterator for IntoIter<T> {
2048     type Item = T;
2049
2050     #[inline]
2051     fn next(&mut self) -> Option<T> {
2052         unsafe {
2053             if self.ptr as *const _ == self.end {
2054                 None
2055             } else {
2056                 if mem::size_of::<T>() == 0 {
2057                     // purposefully don't use 'ptr.offset' because for
2058                     // vectors with 0-size elements this would return the
2059                     // same pointer.
2060                     self.ptr = arith_offset(self.ptr as *const i8, 1) as *mut T;
2061
2062                     // Use a non-null pointer value
2063                     Some(ptr::read(EMPTY as *mut T))
2064                 } else {
2065                     let old = self.ptr;
2066                     self.ptr = self.ptr.offset(1);
2067
2068                     Some(ptr::read(old))
2069                 }
2070             }
2071         }
2072     }
2073
2074     #[inline]
2075     fn size_hint(&self) -> (usize, Option<usize>) {
2076         let diff = (self.end as usize) - (self.ptr as usize);
2077         let size = mem::size_of::<T>();
2078         let exact = diff /
2079                     (if size == 0 {
2080                          1
2081                      } else {
2082                          size
2083                      });
2084         (exact, Some(exact))
2085     }
2086
2087     #[inline]
2088     fn count(self) -> usize {
2089         self.len()
2090     }
2091 }
2092
2093 #[stable(feature = "rust1", since = "1.0.0")]
2094 impl<T> DoubleEndedIterator for IntoIter<T> {
2095     #[inline]
2096     fn next_back(&mut self) -> Option<T> {
2097         unsafe {
2098             if self.end == self.ptr {
2099                 None
2100             } else {
2101                 if mem::size_of::<T>() == 0 {
2102                     // See above for why 'ptr.offset' isn't used
2103                     self.end = arith_offset(self.end as *const i8, -1) as *mut T;
2104
2105                     // Use a non-null pointer value
2106                     Some(ptr::read(EMPTY as *mut T))
2107                 } else {
2108                     self.end = self.end.offset(-1);
2109
2110                     Some(ptr::read(self.end))
2111                 }
2112             }
2113         }
2114     }
2115 }
2116
2117 #[stable(feature = "rust1", since = "1.0.0")]
2118 impl<T> ExactSizeIterator for IntoIter<T> {
2119     fn is_empty(&self) -> bool {
2120         self.ptr == self.end
2121     }
2122 }
2123
2124 #[unstable(feature = "fused", issue = "35602")]
2125 impl<T> FusedIterator for IntoIter<T> {}
2126
2127 #[unstable(feature = "trusted_len", issue = "37572")]
2128 unsafe impl<T> TrustedLen for IntoIter<T> {}
2129
2130 #[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
2131 impl<T: Clone> Clone for IntoIter<T> {
2132     fn clone(&self) -> IntoIter<T> {
2133         self.as_slice().to_owned().into_iter()
2134     }
2135 }
2136
2137 #[stable(feature = "rust1", since = "1.0.0")]
2138 unsafe impl<#[may_dangle] T> Drop for IntoIter<T> {
2139     fn drop(&mut self) {
2140         // destroy the remaining elements
2141         for _x in self.by_ref() {}
2142
2143         // RawVec handles deallocation
2144         let _ = unsafe { RawVec::from_raw_parts(self.buf.as_mut_ptr(), self.cap) };
2145     }
2146 }
2147
2148 /// A draining iterator for `Vec<T>`.
2149 ///
2150 /// This `struct` is created by the [`drain`] method on [`Vec`].
2151 ///
2152 /// [`drain`]: struct.Vec.html#method.drain
2153 /// [`Vec`]: struct.Vec.html
2154 #[stable(feature = "drain", since = "1.6.0")]
2155 pub struct Drain<'a, T: 'a> {
2156     /// Index of tail to preserve
2157     tail_start: usize,
2158     /// Length of tail
2159     tail_len: usize,
2160     /// Current remaining range to remove
2161     iter: slice::Iter<'a, T>,
2162     vec: Shared<Vec<T>>,
2163 }
2164
2165 #[stable(feature = "collection_debug", since = "1.17.0")]
2166 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Drain<'a, T> {
2167     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2168         f.debug_tuple("Drain")
2169          .field(&self.iter.as_slice())
2170          .finish()
2171     }
2172 }
2173
2174 #[stable(feature = "drain", since = "1.6.0")]
2175 unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
2176 #[stable(feature = "drain", since = "1.6.0")]
2177 unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
2178
2179 #[stable(feature = "drain", since = "1.6.0")]
2180 impl<'a, T> Iterator for Drain<'a, T> {
2181     type Item = T;
2182
2183     #[inline]
2184     fn next(&mut self) -> Option<T> {
2185         self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
2186     }
2187
2188     fn size_hint(&self) -> (usize, Option<usize>) {
2189         self.iter.size_hint()
2190     }
2191 }
2192
2193 #[stable(feature = "drain", since = "1.6.0")]
2194 impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
2195     #[inline]
2196     fn next_back(&mut self) -> Option<T> {
2197         self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
2198     }
2199 }
2200
2201 #[stable(feature = "drain", since = "1.6.0")]
2202 impl<'a, T> Drop for Drain<'a, T> {
2203     fn drop(&mut self) {
2204         // exhaust self first
2205         while let Some(_) = self.next() {}
2206
2207         if self.tail_len > 0 {
2208             unsafe {
2209                 let source_vec = &mut *self.vec.as_mut_ptr();
2210                 // memmove back untouched tail, update to new length
2211                 let start = source_vec.len();
2212                 let tail = self.tail_start;
2213                 let src = source_vec.as_ptr().offset(tail as isize);
2214                 let dst = source_vec.as_mut_ptr().offset(start as isize);
2215                 ptr::copy(src, dst, self.tail_len);
2216                 source_vec.set_len(start + self.tail_len);
2217             }
2218         }
2219     }
2220 }
2221
2222
2223 #[stable(feature = "drain", since = "1.6.0")]
2224 impl<'a, T> ExactSizeIterator for Drain<'a, T> {
2225     fn is_empty(&self) -> bool {
2226         self.iter.is_empty()
2227     }
2228 }
2229
2230 #[unstable(feature = "fused", issue = "35602")]
2231 impl<'a, T> FusedIterator for Drain<'a, T> {}
2232
2233 /// A place for insertion at the back of a `Vec`.
2234 ///
2235 /// See [`Vec::place_back`](struct.Vec.html#method.place_back) for details.
2236 #[must_use = "places do nothing unless written to with `<-` syntax"]
2237 #[unstable(feature = "collection_placement",
2238            reason = "struct name and placement protocol are subject to change",
2239            issue = "30172")]
2240 #[derive(Debug)]
2241 pub struct PlaceBack<'a, T: 'a> {
2242     vec: &'a mut Vec<T>,
2243 }
2244
2245 #[unstable(feature = "collection_placement",
2246            reason = "placement protocol is subject to change",
2247            issue = "30172")]
2248 impl<'a, T> Placer<T> for PlaceBack<'a, T> {
2249     type Place = PlaceBack<'a, T>;
2250
2251     fn make_place(self) -> Self {
2252         // This will panic or abort if we would allocate > isize::MAX bytes
2253         // or if the length increment would overflow for zero-sized types.
2254         if self.vec.len == self.vec.buf.cap() {
2255             self.vec.buf.double();
2256         }
2257         self
2258     }
2259 }
2260
2261 #[unstable(feature = "collection_placement",
2262            reason = "placement protocol is subject to change",
2263            issue = "30172")]
2264 impl<'a, T> Place<T> for PlaceBack<'a, T> {
2265     fn pointer(&mut self) -> *mut T {
2266         unsafe { self.vec.as_mut_ptr().offset(self.vec.len as isize) }
2267     }
2268 }
2269
2270 #[unstable(feature = "collection_placement",
2271            reason = "placement protocol is subject to change",
2272            issue = "30172")]
2273 impl<'a, T> InPlace<T> for PlaceBack<'a, T> {
2274     type Owner = &'a mut T;
2275
2276     unsafe fn finalize(mut self) -> &'a mut T {
2277         let ptr = self.pointer();
2278         self.vec.len += 1;
2279         &mut *ptr
2280     }
2281 }