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