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