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         other.as_slice().clone_into(self);
1400     }
1401 }
1402
1403 #[stable(feature = "rust1", since = "1.0.0")]
1404 impl<T: Hash> Hash for Vec<T> {
1405     #[inline]
1406     fn hash<H: hash::Hasher>(&self, state: &mut H) {
1407         Hash::hash(&**self, state)
1408     }
1409 }
1410
1411 #[stable(feature = "rust1", since = "1.0.0")]
1412 impl<T> Index<usize> for Vec<T> {
1413     type Output = T;
1414
1415     #[inline]
1416     fn index(&self, index: usize) -> &T {
1417         // NB built-in indexing via `&[T]`
1418         &(**self)[index]
1419     }
1420 }
1421
1422 #[stable(feature = "rust1", since = "1.0.0")]
1423 impl<T> IndexMut<usize> for Vec<T> {
1424     #[inline]
1425     fn index_mut(&mut self, index: usize) -> &mut T {
1426         // NB built-in indexing via `&mut [T]`
1427         &mut (**self)[index]
1428     }
1429 }
1430
1431
1432 #[stable(feature = "rust1", since = "1.0.0")]
1433 impl<T> ops::Index<ops::Range<usize>> for Vec<T> {
1434     type Output = [T];
1435
1436     #[inline]
1437     fn index(&self, index: ops::Range<usize>) -> &[T] {
1438         Index::index(&**self, index)
1439     }
1440 }
1441 #[stable(feature = "rust1", since = "1.0.0")]
1442 impl<T> ops::Index<ops::RangeTo<usize>> for Vec<T> {
1443     type Output = [T];
1444
1445     #[inline]
1446     fn index(&self, index: ops::RangeTo<usize>) -> &[T] {
1447         Index::index(&**self, index)
1448     }
1449 }
1450 #[stable(feature = "rust1", since = "1.0.0")]
1451 impl<T> ops::Index<ops::RangeFrom<usize>> for Vec<T> {
1452     type Output = [T];
1453
1454     #[inline]
1455     fn index(&self, index: ops::RangeFrom<usize>) -> &[T] {
1456         Index::index(&**self, index)
1457     }
1458 }
1459 #[stable(feature = "rust1", since = "1.0.0")]
1460 impl<T> ops::Index<ops::RangeFull> for Vec<T> {
1461     type Output = [T];
1462
1463     #[inline]
1464     fn index(&self, _index: ops::RangeFull) -> &[T] {
1465         self
1466     }
1467 }
1468 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1469 impl<T> ops::Index<ops::RangeInclusive<usize>> for Vec<T> {
1470     type Output = [T];
1471
1472     #[inline]
1473     fn index(&self, index: ops::RangeInclusive<usize>) -> &[T] {
1474         Index::index(&**self, index)
1475     }
1476 }
1477 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1478 impl<T> ops::Index<ops::RangeToInclusive<usize>> for Vec<T> {
1479     type Output = [T];
1480
1481     #[inline]
1482     fn index(&self, index: ops::RangeToInclusive<usize>) -> &[T] {
1483         Index::index(&**self, index)
1484     }
1485 }
1486
1487 #[stable(feature = "rust1", since = "1.0.0")]
1488 impl<T> ops::IndexMut<ops::Range<usize>> for Vec<T> {
1489     #[inline]
1490     fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] {
1491         IndexMut::index_mut(&mut **self, index)
1492     }
1493 }
1494 #[stable(feature = "rust1", since = "1.0.0")]
1495 impl<T> ops::IndexMut<ops::RangeTo<usize>> for Vec<T> {
1496     #[inline]
1497     fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] {
1498         IndexMut::index_mut(&mut **self, index)
1499     }
1500 }
1501 #[stable(feature = "rust1", since = "1.0.0")]
1502 impl<T> ops::IndexMut<ops::RangeFrom<usize>> for Vec<T> {
1503     #[inline]
1504     fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] {
1505         IndexMut::index_mut(&mut **self, index)
1506     }
1507 }
1508 #[stable(feature = "rust1", since = "1.0.0")]
1509 impl<T> ops::IndexMut<ops::RangeFull> for Vec<T> {
1510     #[inline]
1511     fn index_mut(&mut self, _index: ops::RangeFull) -> &mut [T] {
1512         self
1513     }
1514 }
1515 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1516 impl<T> ops::IndexMut<ops::RangeInclusive<usize>> for Vec<T> {
1517     #[inline]
1518     fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut [T] {
1519         IndexMut::index_mut(&mut **self, index)
1520     }
1521 }
1522 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1523 impl<T> ops::IndexMut<ops::RangeToInclusive<usize>> for Vec<T> {
1524     #[inline]
1525     fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut [T] {
1526         IndexMut::index_mut(&mut **self, index)
1527     }
1528 }
1529
1530 #[stable(feature = "rust1", since = "1.0.0")]
1531 impl<T> ops::Deref for Vec<T> {
1532     type Target = [T];
1533
1534     fn deref(&self) -> &[T] {
1535         unsafe {
1536             let p = self.buf.ptr();
1537             assume(!p.is_null());
1538             slice::from_raw_parts(p, self.len)
1539         }
1540     }
1541 }
1542
1543 #[stable(feature = "rust1", since = "1.0.0")]
1544 impl<T> ops::DerefMut for Vec<T> {
1545     fn deref_mut(&mut self) -> &mut [T] {
1546         unsafe {
1547             let ptr = self.buf.ptr();
1548             assume(!ptr.is_null());
1549             slice::from_raw_parts_mut(ptr, self.len)
1550         }
1551     }
1552 }
1553
1554 #[stable(feature = "rust1", since = "1.0.0")]
1555 impl<T> FromIterator<T> for Vec<T> {
1556     #[inline]
1557     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
1558         <Self as SpecExtend<T, I::IntoIter>>::from_iter(iter.into_iter())
1559     }
1560 }
1561
1562 #[stable(feature = "rust1", since = "1.0.0")]
1563 impl<T> IntoIterator for Vec<T> {
1564     type Item = T;
1565     type IntoIter = IntoIter<T>;
1566
1567     /// Creates a consuming iterator, that is, one that moves each value out of
1568     /// the vector (from start to end). The vector cannot be used after calling
1569     /// this.
1570     ///
1571     /// # Examples
1572     ///
1573     /// ```
1574     /// let v = vec!["a".to_string(), "b".to_string()];
1575     /// for s in v.into_iter() {
1576     ///     // s has type String, not &String
1577     ///     println!("{}", s);
1578     /// }
1579     /// ```
1580     #[inline]
1581     fn into_iter(mut self) -> IntoIter<T> {
1582         unsafe {
1583             let begin = self.as_mut_ptr();
1584             assume(!begin.is_null());
1585             let end = if mem::size_of::<T>() == 0 {
1586                 arith_offset(begin as *const i8, self.len() as isize) as *const T
1587             } else {
1588                 begin.offset(self.len() as isize) as *const T
1589             };
1590             let cap = self.buf.cap();
1591             mem::forget(self);
1592             IntoIter {
1593                 buf: Shared::new(begin),
1594                 cap: cap,
1595                 ptr: begin,
1596                 end: end,
1597             }
1598         }
1599     }
1600 }
1601
1602 #[stable(feature = "rust1", since = "1.0.0")]
1603 impl<'a, T> IntoIterator for &'a Vec<T> {
1604     type Item = &'a T;
1605     type IntoIter = slice::Iter<'a, T>;
1606
1607     fn into_iter(self) -> slice::Iter<'a, T> {
1608         self.iter()
1609     }
1610 }
1611
1612 #[stable(feature = "rust1", since = "1.0.0")]
1613 impl<'a, T> IntoIterator for &'a mut Vec<T> {
1614     type Item = &'a mut T;
1615     type IntoIter = slice::IterMut<'a, T>;
1616
1617     fn into_iter(mut self) -> slice::IterMut<'a, T> {
1618         self.iter_mut()
1619     }
1620 }
1621
1622 #[stable(feature = "rust1", since = "1.0.0")]
1623 impl<T> Extend<T> for Vec<T> {
1624     #[inline]
1625     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1626         <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter())
1627     }
1628 }
1629
1630 // Specialization trait used for Vec::from_iter and Vec::extend
1631 trait SpecExtend<T, I> {
1632     fn from_iter(iter: I) -> Self;
1633     fn spec_extend(&mut self, iter: I);
1634 }
1635
1636 impl<T, I> SpecExtend<T, I> for Vec<T>
1637     where I: Iterator<Item=T>,
1638 {
1639     default fn from_iter(mut iterator: I) -> Self {
1640         // Unroll the first iteration, as the vector is going to be
1641         // expanded on this iteration in every case when the iterable is not
1642         // empty, but the loop in extend_desugared() is not going to see the
1643         // vector being full in the few subsequent loop iterations.
1644         // So we get better branch prediction.
1645         let mut vector = match iterator.next() {
1646             None => return Vec::new(),
1647             Some(element) => {
1648                 let (lower, _) = iterator.size_hint();
1649                 let mut vector = Vec::with_capacity(lower.saturating_add(1));
1650                 unsafe {
1651                     ptr::write(vector.get_unchecked_mut(0), element);
1652                     vector.set_len(1);
1653                 }
1654                 vector
1655             }
1656         };
1657         <Vec<T> as SpecExtend<T, I>>::spec_extend(&mut vector, iterator);
1658         vector
1659     }
1660
1661     default fn spec_extend(&mut self, iter: I) {
1662         self.extend_desugared(iter)
1663     }
1664 }
1665
1666 impl<T, I> SpecExtend<T, I> for Vec<T>
1667     where I: TrustedLen<Item=T>,
1668 {
1669     default fn from_iter(iterator: I) -> Self {
1670         let mut vector = Vec::new();
1671         vector.spec_extend(iterator);
1672         vector
1673     }
1674
1675     fn spec_extend(&mut self, iterator: I) {
1676         // This is the case for a TrustedLen iterator.
1677         let (low, high) = iterator.size_hint();
1678         if let Some(high_value) = high {
1679             debug_assert_eq!(low, high_value,
1680                              "TrustedLen iterator's size hint is not exact: {:?}",
1681                              (low, high));
1682         }
1683         if let Some(additional) = high {
1684             self.reserve(additional);
1685             unsafe {
1686                 let mut ptr = self.as_mut_ptr().offset(self.len() as isize);
1687                 let mut local_len = SetLenOnDrop::new(&mut self.len);
1688                 for element in iterator {
1689                     ptr::write(ptr, element);
1690                     ptr = ptr.offset(1);
1691                     // NB can't overflow since we would have had to alloc the address space
1692                     local_len.increment_len(1);
1693                 }
1694             }
1695         } else {
1696             self.extend_desugared(iterator)
1697         }
1698     }
1699 }
1700
1701 impl<T> SpecExtend<T, IntoIter<T>> for Vec<T> {
1702     fn from_iter(iterator: IntoIter<T>) -> Self {
1703         // A common case is passing a vector into a function which immediately
1704         // re-collects into a vector. We can short circuit this if the IntoIter
1705         // has not been advanced at all.
1706         if *iterator.buf == iterator.ptr as *mut T {
1707             unsafe {
1708                 let vec = Vec::from_raw_parts(*iterator.buf as *mut T,
1709                                               iterator.len(),
1710                                               iterator.cap);
1711                 mem::forget(iterator);
1712                 vec
1713             }
1714         } else {
1715             let mut vector = Vec::new();
1716             vector.spec_extend(iterator);
1717             vector
1718         }
1719     }
1720 }
1721
1722 impl<'a, T: 'a, I> SpecExtend<&'a T, I> for Vec<T>
1723     where I: Iterator<Item=&'a T>,
1724           T: Clone,
1725 {
1726     default fn from_iter(iterator: I) -> Self {
1727         SpecExtend::from_iter(iterator.cloned())
1728     }
1729
1730     default fn spec_extend(&mut self, iterator: I) {
1731         self.spec_extend(iterator.cloned())
1732     }
1733 }
1734
1735 impl<'a, T: 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T>
1736     where T: Copy,
1737 {
1738     fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
1739         let slice = iterator.as_slice();
1740         self.reserve(slice.len());
1741         unsafe {
1742             let len = self.len();
1743             self.set_len(len + slice.len());
1744             self.get_unchecked_mut(len..).copy_from_slice(slice);
1745         }
1746     }
1747 }
1748
1749 impl<T> Vec<T> {
1750     fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
1751         // This is the case for a general iterator.
1752         //
1753         // This function should be the moral equivalent of:
1754         //
1755         //      for item in iterator {
1756         //          self.push(item);
1757         //      }
1758         while let Some(element) = iterator.next() {
1759             let len = self.len();
1760             if len == self.capacity() {
1761                 let (lower, _) = iterator.size_hint();
1762                 self.reserve(lower.saturating_add(1));
1763             }
1764             unsafe {
1765                 ptr::write(self.get_unchecked_mut(len), element);
1766                 // NB can't overflow since we would have had to alloc the address space
1767                 self.set_len(len + 1);
1768             }
1769         }
1770     }
1771 }
1772
1773 #[stable(feature = "extend_ref", since = "1.2.0")]
1774 impl<'a, T: 'a + Copy> Extend<&'a T> for Vec<T> {
1775     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1776         self.spec_extend(iter.into_iter())
1777     }
1778 }
1779
1780 macro_rules! __impl_slice_eq1 {
1781     ($Lhs: ty, $Rhs: ty) => {
1782         __impl_slice_eq1! { $Lhs, $Rhs, Sized }
1783     };
1784     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
1785         #[stable(feature = "rust1", since = "1.0.0")]
1786         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
1787             #[inline]
1788             fn eq(&self, other: &$Rhs) -> bool { self[..] == other[..] }
1789             #[inline]
1790             fn ne(&self, other: &$Rhs) -> bool { self[..] != other[..] }
1791         }
1792     }
1793 }
1794
1795 __impl_slice_eq1! { Vec<A>, Vec<B> }
1796 __impl_slice_eq1! { Vec<A>, &'b [B] }
1797 __impl_slice_eq1! { Vec<A>, &'b mut [B] }
1798 __impl_slice_eq1! { Cow<'a, [A]>, &'b [B], Clone }
1799 __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B], Clone }
1800 __impl_slice_eq1! { Cow<'a, [A]>, Vec<B>, Clone }
1801
1802 macro_rules! array_impls {
1803     ($($N: expr)+) => {
1804         $(
1805             // NOTE: some less important impls are omitted to reduce code bloat
1806             __impl_slice_eq1! { Vec<A>, [B; $N] }
1807             __impl_slice_eq1! { Vec<A>, &'b [B; $N] }
1808             // __impl_slice_eq1! { Vec<A>, &'b mut [B; $N] }
1809             // __impl_slice_eq1! { Cow<'a, [A]>, [B; $N], Clone }
1810             // __impl_slice_eq1! { Cow<'a, [A]>, &'b [B; $N], Clone }
1811             // __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B; $N], Clone }
1812         )+
1813     }
1814 }
1815
1816 array_impls! {
1817      0  1  2  3  4  5  6  7  8  9
1818     10 11 12 13 14 15 16 17 18 19
1819     20 21 22 23 24 25 26 27 28 29
1820     30 31 32
1821 }
1822
1823 /// Implements comparison of vectors, lexicographically.
1824 #[stable(feature = "rust1", since = "1.0.0")]
1825 impl<T: PartialOrd> PartialOrd for Vec<T> {
1826     #[inline]
1827     fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
1828         PartialOrd::partial_cmp(&**self, &**other)
1829     }
1830 }
1831
1832 #[stable(feature = "rust1", since = "1.0.0")]
1833 impl<T: Eq> Eq for Vec<T> {}
1834
1835 /// Implements ordering of vectors, lexicographically.
1836 #[stable(feature = "rust1", since = "1.0.0")]
1837 impl<T: Ord> Ord for Vec<T> {
1838     #[inline]
1839     fn cmp(&self, other: &Vec<T>) -> Ordering {
1840         Ord::cmp(&**self, &**other)
1841     }
1842 }
1843
1844 #[stable(feature = "rust1", since = "1.0.0")]
1845 unsafe impl<#[may_dangle] T> Drop for Vec<T> {
1846     fn drop(&mut self) {
1847         unsafe {
1848             // use drop for [T]
1849             ptr::drop_in_place(&mut self[..]);
1850         }
1851         // RawVec handles deallocation
1852     }
1853 }
1854
1855 #[stable(feature = "rust1", since = "1.0.0")]
1856 impl<T> Default for Vec<T> {
1857     /// Creates an empty `Vec<T>`.
1858     fn default() -> Vec<T> {
1859         Vec::new()
1860     }
1861 }
1862
1863 #[stable(feature = "rust1", since = "1.0.0")]
1864 impl<T: fmt::Debug> fmt::Debug for Vec<T> {
1865     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1866         fmt::Debug::fmt(&**self, f)
1867     }
1868 }
1869
1870 #[stable(feature = "rust1", since = "1.0.0")]
1871 impl<T> AsRef<Vec<T>> for Vec<T> {
1872     fn as_ref(&self) -> &Vec<T> {
1873         self
1874     }
1875 }
1876
1877 #[stable(feature = "vec_as_mut", since = "1.5.0")]
1878 impl<T> AsMut<Vec<T>> for Vec<T> {
1879     fn as_mut(&mut self) -> &mut Vec<T> {
1880         self
1881     }
1882 }
1883
1884 #[stable(feature = "rust1", since = "1.0.0")]
1885 impl<T> AsRef<[T]> for Vec<T> {
1886     fn as_ref(&self) -> &[T] {
1887         self
1888     }
1889 }
1890
1891 #[stable(feature = "vec_as_mut", since = "1.5.0")]
1892 impl<T> AsMut<[T]> for Vec<T> {
1893     fn as_mut(&mut self) -> &mut [T] {
1894         self
1895     }
1896 }
1897
1898 #[stable(feature = "rust1", since = "1.0.0")]
1899 impl<'a, T: Clone> From<&'a [T]> for Vec<T> {
1900     #[cfg(not(test))]
1901     fn from(s: &'a [T]) -> Vec<T> {
1902         s.to_vec()
1903     }
1904     #[cfg(test)]
1905     fn from(s: &'a [T]) -> Vec<T> {
1906         ::slice::to_vec(s)
1907     }
1908 }
1909
1910 #[stable(feature = "vec_from_cow_slice", since = "1.14.0")]
1911 impl<'a, T> From<Cow<'a, [T]>> for Vec<T> where [T]: ToOwned<Owned=Vec<T>> {
1912     fn from(s: Cow<'a, [T]>) -> Vec<T> {
1913         s.into_owned()
1914     }
1915 }
1916
1917 // note: test pulls in libstd, which causes errors here
1918 #[cfg(not(test))]
1919 #[stable(feature = "vec_from_box", since = "1.17.0")]
1920 impl<T> From<Box<[T]>> for Vec<T> {
1921     fn from(s: Box<[T]>) -> Vec<T> {
1922         s.into_vec()
1923     }
1924 }
1925
1926 #[stable(feature = "box_from_vec", since = "1.17.0")]
1927 impl<T> Into<Box<[T]>> for Vec<T> {
1928     fn into(self) -> Box<[T]> {
1929         self.into_boxed_slice()
1930     }
1931 }
1932
1933 #[stable(feature = "rust1", since = "1.0.0")]
1934 impl<'a> From<&'a str> for Vec<u8> {
1935     fn from(s: &'a str) -> Vec<u8> {
1936         From::from(s.as_bytes())
1937     }
1938 }
1939
1940 ////////////////////////////////////////////////////////////////////////////////
1941 // Clone-on-write
1942 ////////////////////////////////////////////////////////////////////////////////
1943
1944 #[stable(feature = "cow_from_vec", since = "1.7.0")]
1945 impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> {
1946     fn from(s: &'a [T]) -> Cow<'a, [T]> {
1947         Cow::Borrowed(s)
1948     }
1949 }
1950
1951 #[stable(feature = "cow_from_vec", since = "1.7.0")]
1952 impl<'a, T: Clone> From<Vec<T>> for Cow<'a, [T]> {
1953     fn from(v: Vec<T>) -> Cow<'a, [T]> {
1954         Cow::Owned(v)
1955     }
1956 }
1957
1958 #[stable(feature = "rust1", since = "1.0.0")]
1959 impl<'a, T> FromIterator<T> for Cow<'a, [T]> where T: Clone {
1960     fn from_iter<I: IntoIterator<Item = T>>(it: I) -> Cow<'a, [T]> {
1961         Cow::Owned(FromIterator::from_iter(it))
1962     }
1963 }
1964
1965 ////////////////////////////////////////////////////////////////////////////////
1966 // Iterators
1967 ////////////////////////////////////////////////////////////////////////////////
1968
1969 /// An iterator that moves out of a vector.
1970 ///
1971 /// This `struct` is created by the `into_iter` method on [`Vec`][`Vec`] (provided
1972 /// by the [`IntoIterator`] trait).
1973 ///
1974 /// [`Vec`]: struct.Vec.html
1975 /// [`IntoIterator`]: ../../std/iter/trait.IntoIterator.html
1976 #[stable(feature = "rust1", since = "1.0.0")]
1977 pub struct IntoIter<T> {
1978     buf: Shared<T>,
1979     cap: usize,
1980     ptr: *const T,
1981     end: *const T,
1982 }
1983
1984 #[stable(feature = "vec_intoiter_debug", since = "1.13.0")]
1985 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
1986     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1987         f.debug_tuple("IntoIter")
1988             .field(&self.as_slice())
1989             .finish()
1990     }
1991 }
1992
1993 impl<T> IntoIter<T> {
1994     /// Returns the remaining items of this iterator as a slice.
1995     ///
1996     /// # Examples
1997     ///
1998     /// ```
1999     /// let vec = vec!['a', 'b', 'c'];
2000     /// let mut into_iter = vec.into_iter();
2001     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2002     /// let _ = into_iter.next().unwrap();
2003     /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
2004     /// ```
2005     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
2006     pub fn as_slice(&self) -> &[T] {
2007         unsafe {
2008             slice::from_raw_parts(self.ptr, self.len())
2009         }
2010     }
2011
2012     /// Returns the remaining items of this iterator as a mutable slice.
2013     ///
2014     /// # Examples
2015     ///
2016     /// ```
2017     /// let vec = vec!['a', 'b', 'c'];
2018     /// let mut into_iter = vec.into_iter();
2019     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2020     /// into_iter.as_mut_slice()[2] = 'z';
2021     /// assert_eq!(into_iter.next().unwrap(), 'a');
2022     /// assert_eq!(into_iter.next().unwrap(), 'b');
2023     /// assert_eq!(into_iter.next().unwrap(), 'z');
2024     /// ```
2025     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
2026     pub fn as_mut_slice(&mut self) -> &mut [T] {
2027         unsafe {
2028             slice::from_raw_parts_mut(self.ptr as *mut T, self.len())
2029         }
2030     }
2031 }
2032
2033 #[stable(feature = "rust1", since = "1.0.0")]
2034 unsafe impl<T: Send> Send for IntoIter<T> {}
2035 #[stable(feature = "rust1", since = "1.0.0")]
2036 unsafe impl<T: Sync> Sync for IntoIter<T> {}
2037
2038 #[stable(feature = "rust1", since = "1.0.0")]
2039 impl<T> Iterator for IntoIter<T> {
2040     type Item = T;
2041
2042     #[inline]
2043     fn next(&mut self) -> Option<T> {
2044         unsafe {
2045             if self.ptr as *const _ == self.end {
2046                 None
2047             } else {
2048                 if mem::size_of::<T>() == 0 {
2049                     // purposefully don't use 'ptr.offset' because for
2050                     // vectors with 0-size elements this would return the
2051                     // same pointer.
2052                     self.ptr = arith_offset(self.ptr as *const i8, 1) as *mut T;
2053
2054                     // Use a non-null pointer value
2055                     Some(ptr::read(EMPTY as *mut T))
2056                 } else {
2057                     let old = self.ptr;
2058                     self.ptr = self.ptr.offset(1);
2059
2060                     Some(ptr::read(old))
2061                 }
2062             }
2063         }
2064     }
2065
2066     #[inline]
2067     fn size_hint(&self) -> (usize, Option<usize>) {
2068         let exact = match self.ptr.offset_to(self.end) {
2069             Some(x) => x as usize,
2070             None => (self.end as usize).wrapping_sub(self.ptr as usize),
2071         };
2072         (exact, Some(exact))
2073     }
2074
2075     #[inline]
2076     fn count(self) -> usize {
2077         self.len()
2078     }
2079 }
2080
2081 #[stable(feature = "rust1", since = "1.0.0")]
2082 impl<T> DoubleEndedIterator for IntoIter<T> {
2083     #[inline]
2084     fn next_back(&mut self) -> Option<T> {
2085         unsafe {
2086             if self.end == self.ptr {
2087                 None
2088             } else {
2089                 if mem::size_of::<T>() == 0 {
2090                     // See above for why 'ptr.offset' isn't used
2091                     self.end = arith_offset(self.end as *const i8, -1) as *mut T;
2092
2093                     // Use a non-null pointer value
2094                     Some(ptr::read(EMPTY as *mut T))
2095                 } else {
2096                     self.end = self.end.offset(-1);
2097
2098                     Some(ptr::read(self.end))
2099                 }
2100             }
2101         }
2102     }
2103 }
2104
2105 #[stable(feature = "rust1", since = "1.0.0")]
2106 impl<T> ExactSizeIterator for IntoIter<T> {
2107     fn is_empty(&self) -> bool {
2108         self.ptr == self.end
2109     }
2110 }
2111
2112 #[unstable(feature = "fused", issue = "35602")]
2113 impl<T> FusedIterator for IntoIter<T> {}
2114
2115 #[unstable(feature = "trusted_len", issue = "37572")]
2116 unsafe impl<T> TrustedLen for IntoIter<T> {}
2117
2118 #[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
2119 impl<T: Clone> Clone for IntoIter<T> {
2120     fn clone(&self) -> IntoIter<T> {
2121         self.as_slice().to_owned().into_iter()
2122     }
2123 }
2124
2125 #[stable(feature = "rust1", since = "1.0.0")]
2126 unsafe impl<#[may_dangle] T> Drop for IntoIter<T> {
2127     fn drop(&mut self) {
2128         // destroy the remaining elements
2129         for _x in self.by_ref() {}
2130
2131         // RawVec handles deallocation
2132         let _ = unsafe { RawVec::from_raw_parts(self.buf.as_mut_ptr(), self.cap) };
2133     }
2134 }
2135
2136 /// A draining iterator for `Vec<T>`.
2137 ///
2138 /// This `struct` is created by the [`drain`] method on [`Vec`].
2139 ///
2140 /// [`drain`]: struct.Vec.html#method.drain
2141 /// [`Vec`]: struct.Vec.html
2142 #[stable(feature = "drain", since = "1.6.0")]
2143 pub struct Drain<'a, T: 'a> {
2144     /// Index of tail to preserve
2145     tail_start: usize,
2146     /// Length of tail
2147     tail_len: usize,
2148     /// Current remaining range to remove
2149     iter: slice::Iter<'a, T>,
2150     vec: Shared<Vec<T>>,
2151 }
2152
2153 #[stable(feature = "collection_debug", since = "1.17.0")]
2154 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Drain<'a, T> {
2155     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2156         f.debug_tuple("Drain")
2157          .field(&self.iter.as_slice())
2158          .finish()
2159     }
2160 }
2161
2162 #[stable(feature = "drain", since = "1.6.0")]
2163 unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
2164 #[stable(feature = "drain", since = "1.6.0")]
2165 unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
2166
2167 #[stable(feature = "drain", since = "1.6.0")]
2168 impl<'a, T> Iterator for Drain<'a, T> {
2169     type Item = T;
2170
2171     #[inline]
2172     fn next(&mut self) -> Option<T> {
2173         self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
2174     }
2175
2176     fn size_hint(&self) -> (usize, Option<usize>) {
2177         self.iter.size_hint()
2178     }
2179 }
2180
2181 #[stable(feature = "drain", since = "1.6.0")]
2182 impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
2183     #[inline]
2184     fn next_back(&mut self) -> Option<T> {
2185         self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
2186     }
2187 }
2188
2189 #[stable(feature = "drain", since = "1.6.0")]
2190 impl<'a, T> Drop for Drain<'a, T> {
2191     fn drop(&mut self) {
2192         // exhaust self first
2193         while let Some(_) = self.next() {}
2194
2195         if self.tail_len > 0 {
2196             unsafe {
2197                 let source_vec = &mut *self.vec.as_mut_ptr();
2198                 // memmove back untouched tail, update to new length
2199                 let start = source_vec.len();
2200                 let tail = self.tail_start;
2201                 let src = source_vec.as_ptr().offset(tail as isize);
2202                 let dst = source_vec.as_mut_ptr().offset(start as isize);
2203                 ptr::copy(src, dst, self.tail_len);
2204                 source_vec.set_len(start + self.tail_len);
2205             }
2206         }
2207     }
2208 }
2209
2210
2211 #[stable(feature = "drain", since = "1.6.0")]
2212 impl<'a, T> ExactSizeIterator for Drain<'a, T> {
2213     fn is_empty(&self) -> bool {
2214         self.iter.is_empty()
2215     }
2216 }
2217
2218 #[unstable(feature = "fused", issue = "35602")]
2219 impl<'a, T> FusedIterator for Drain<'a, T> {}
2220
2221 /// A place for insertion at the back of a `Vec`.
2222 ///
2223 /// See [`Vec::place_back`](struct.Vec.html#method.place_back) for details.
2224 #[must_use = "places do nothing unless written to with `<-` syntax"]
2225 #[unstable(feature = "collection_placement",
2226            reason = "struct name and placement protocol are subject to change",
2227            issue = "30172")]
2228 #[derive(Debug)]
2229 pub struct PlaceBack<'a, T: 'a> {
2230     vec: &'a mut Vec<T>,
2231 }
2232
2233 #[unstable(feature = "collection_placement",
2234            reason = "placement protocol is subject to change",
2235            issue = "30172")]
2236 impl<'a, T> Placer<T> for PlaceBack<'a, T> {
2237     type Place = PlaceBack<'a, T>;
2238
2239     fn make_place(self) -> Self {
2240         // This will panic or abort if we would allocate > isize::MAX bytes
2241         // or if the length increment would overflow for zero-sized types.
2242         if self.vec.len == self.vec.buf.cap() {
2243             self.vec.buf.double();
2244         }
2245         self
2246     }
2247 }
2248
2249 #[unstable(feature = "collection_placement",
2250            reason = "placement protocol is subject to change",
2251            issue = "30172")]
2252 impl<'a, T> Place<T> for PlaceBack<'a, T> {
2253     fn pointer(&mut self) -> *mut T {
2254         unsafe { self.vec.as_mut_ptr().offset(self.vec.len as isize) }
2255     }
2256 }
2257
2258 #[unstable(feature = "collection_placement",
2259            reason = "placement protocol is subject to change",
2260            issue = "30172")]
2261 impl<'a, T> InPlace<T> for PlaceBack<'a, T> {
2262     type Owner = &'a mut T;
2263
2264     unsafe fn finalize(mut self) -> &'a mut T {
2265         let ptr = self.pointer();
2266         self.vec.len += 1;
2267         &mut *ptr
2268     }
2269 }