]> git.proxmox.com Git - rustc.git/blame - src/libcollections/vec.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / libcollections / vec.rs
CommitLineData
1a4d82fc
JJ
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
7453a54e
SL
11//! A contiguous growable array type with heap-allocated contents, written
12//! `Vec<T>` but pronounced 'vector.'
1a4d82fc 13//!
62682a34
SL
14//! Vectors have `O(1)` indexing, amortized `O(1)` push (to the end) and
15//! `O(1)` pop (from the end).
1a4d82fc
JJ
16//!
17//! # Examples
18//!
d9579d0f 19//! You can explicitly create a `Vec<T>` with `new()`:
1a4d82fc
JJ
20//!
21//! ```
d9579d0f 22//! let v: Vec<i32> = Vec::new();
1a4d82fc
JJ
23//! ```
24//!
d9579d0f 25//! ...or by using the `vec!` macro:
1a4d82fc
JJ
26//!
27//! ```
d9579d0f 28//! let v: Vec<i32> = vec![];
1a4d82fc 29//!
d9579d0f
AL
30//! let v = vec![1, 2, 3, 4, 5];
31//!
32//! let v = vec![0; 10]; // ten zeroes
1a4d82fc
JJ
33//! ```
34//!
e9174d1e
SL
35//! You can `push` values onto the end of a vector (which will grow the vector
36//! as needed):
1a4d82fc
JJ
37//!
38//! ```
d9579d0f 39//! let mut v = vec![1, 2];
1a4d82fc 40//!
d9579d0f 41//! v.push(3);
1a4d82fc
JJ
42//! ```
43//!
d9579d0f
AL
44//! Popping values works in much the same way:
45//!
46//! ```
47//! let mut v = vec![1, 2];
1a4d82fc 48//!
d9579d0f 49//! let two = v.pop();
1a4d82fc 50//! ```
1a4d82fc 51//!
d9579d0f
AL
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;
1a4d82fc
JJ
58//! ```
59
85aaf69f 60#![stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 61
1a4d82fc 62use alloc::boxed::Box;
c1a9b12d 63use alloc::heap::EMPTY;
7453a54e
SL
64use alloc::raw_vec::RawVec;
65use borrow::ToOwned;
54a0048b 66use borrow::Cow;
c34b1796 67use core::cmp::Ordering;
1a4d82fc
JJ
68use core::fmt;
69use core::hash::{self, Hash};
54a0048b 70use core::intrinsics::{arith_offset, assume};
c1a9b12d 71use core::iter::FromIterator;
1a4d82fc 72use core::mem;
9cc50fc6 73use core::ops::{Index, IndexMut};
1a4d82fc
JJ
74use core::ops;
75use core::ptr;
85aaf69f 76use core::slice;
85aaf69f 77
d9579d0f
AL
78use super::range::RangeArgument;
79
7453a54e 80/// A contiguous growable array type, written `Vec<T>` but pronounced 'vector.'
1a4d82fc
JJ
81///
82/// # Examples
83///
84/// ```
85/// let mut vec = Vec::new();
85aaf69f
SL
86/// vec.push(1);
87/// vec.push(2);
1a4d82fc
JJ
88///
89/// assert_eq!(vec.len(), 2);
90/// assert_eq!(vec[0], 1);
91///
92/// assert_eq!(vec.pop(), Some(2));
93/// assert_eq!(vec.len(), 1);
94///
85aaf69f 95/// vec[0] = 7;
1a4d82fc
JJ
96/// assert_eq!(vec[0], 7);
97///
62682a34 98/// vec.extend([1, 2, 3].iter().cloned());
1a4d82fc 99///
62682a34 100/// for x in &vec {
1a4d82fc
JJ
101/// println!("{}", x);
102/// }
c34b1796 103/// assert_eq!(vec, [7, 1, 2, 3]);
1a4d82fc
JJ
104/// ```
105///
106/// The `vec!` macro is provided to make initialization more convenient:
107///
108/// ```
85aaf69f 109/// let mut vec = vec![1, 2, 3];
1a4d82fc 110/// vec.push(4);
c34b1796 111/// assert_eq!(vec, [1, 2, 3, 4]);
1a4d82fc
JJ
112/// ```
113///
c1a9b12d
SL
114/// It can also initialize each element of a `Vec<T>` with a given value:
115///
116/// ```
117/// let vec = vec![0; 5];
118/// assert_eq!(vec, [0, 0, 0, 0, 0]);
119/// ```
120///
1a4d82fc
JJ
121/// Use a `Vec<T>` as an efficient stack:
122///
123/// ```
124/// let mut stack = Vec::new();
125///
85aaf69f
SL
126/// stack.push(1);
127/// stack.push(2);
128/// stack.push(3);
1a4d82fc 129///
bd371182 130/// while let Some(top) = stack.pop() {
1a4d82fc
JJ
131/// // Prints 3, 2, 1
132/// println!("{}", top);
133/// }
134/// ```
135///
7453a54e
SL
136/// # Indexing
137///
138/// The Vec type allows to access values by index, because it implements the
139/// `Index` trait. An example will be more explicit:
140///
141/// ```
142/// let v = vec!(0, 2, 4, 6);
143/// println!("{}", v[1]); // it will display '2'
144/// ```
145///
146/// However be careful: if you try to access an index which isn't in the Vec,
147/// your software will panic! You cannot do this:
148///
149/// ```ignore
150/// let v = vec!(0, 2, 4, 6);
151/// println!("{}", v[6]); // it will panic!
152/// ```
153///
154/// In conclusion: always check if the index you want to get really exists
155/// before doing it.
156///
157/// # Slicing
158///
159/// A Vec can be mutable. Slices, on the other hand, are read-only objects.
160/// To get a slice, use "&". Example:
161///
162/// ```
163/// fn read_slice(slice: &[usize]) {
164/// // ...
165/// }
166///
167/// let v = vec!(0, 1);
168/// read_slice(&v);
169///
170/// // ... and that's all!
171/// // you can also do it like this:
172/// let x : &[usize] = &v;
173/// ```
174///
175/// In Rust, it's more common to pass slices as arguments rather than vectors
176/// when you just want to provide a read access. The same goes for String and
177/// &str.
178///
1a4d82fc
JJ
179/// # Capacity and reallocation
180///
c34b1796
AL
181/// The capacity of a vector is the amount of space allocated for any future
182/// elements that will be added onto the vector. This is not to be confused with
183/// the *length* of a vector, which specifies the number of actual elements
184/// within the vector. If a vector's length exceeds its capacity, its capacity
185/// will automatically be increased, but its elements will have to be
1a4d82fc
JJ
186/// reallocated.
187///
c34b1796
AL
188/// For example, a vector with capacity 10 and length 0 would be an empty vector
189/// with space for 10 more elements. Pushing 10 or fewer elements onto the
190/// vector will not change its capacity or cause reallocation to occur. However,
191/// if the vector's length is increased to 11, it will have to reallocate, which
192/// can be slow. For this reason, it is recommended to use `Vec::with_capacity`
193/// whenever possible to specify how big the vector is expected to get.
b039eaaf
SL
194///
195/// # Guarantees
196///
197/// Due to its incredibly fundamental nature, Vec makes a lot of guarantees
198/// about its design. This ensures that it's as low-overhead as possible in
199/// the general case, and can be correctly manipulated in primitive ways
200/// by unsafe code. Note that these guarantees refer to an unqualified `Vec<T>`.
201/// If additional type parameters are added (e.g. to support custom allocators),
202/// overriding their defaults may change the behavior.
203///
204/// Most fundamentally, Vec is and always will be a (pointer, capacity, length)
205/// triplet. No more, no less. The order of these fields is completely
206/// unspecified, and you should use the appropriate methods to modify these.
207/// The pointer will never be null, so this type is null-pointer-optimized.
208///
209/// However, the pointer may not actually point to allocated memory. In particular,
210/// if you construct a Vec with capacity 0 via `Vec::new()`, `vec![]`,
211/// `Vec::with_capacity(0)`, or by calling `shrink_to_fit()` on an empty Vec, it
212/// will not allocate memory. Similarly, if you store zero-sized types inside
213/// a Vec, it will not allocate space for them. *Note that in this case the
214/// Vec may not report a `capacity()` of 0*. Vec will allocate if and only
215/// if `mem::size_of::<T>() * capacity() > 0`. In general, Vec's allocation
216/// details are subtle enough that it is strongly recommended that you only
217/// free memory allocated by a Vec by creating a new Vec and dropping it.
218///
219/// If a Vec *has* allocated memory, then the memory it points to is on the heap
220/// (as defined by the allocator Rust is configured to use by default), and its
221/// pointer points to `len()` initialized elements in order (what you would see
222/// if you coerced it to a slice), followed by `capacity() - len()` logically
223/// uninitialized elements.
224///
225/// Vec will never perform a "small optimization" where elements are actually
226/// stored on the stack for two reasons:
227///
228/// * It would make it more difficult for unsafe code to correctly manipulate
229/// a Vec. The contents of a Vec wouldn't have a stable address if it were
230/// only moved, and it would be more difficult to determine if a Vec had
231/// actually allocated memory.
232///
233/// * It would penalize the general case, incurring an additional branch
234/// on every access.
235///
236/// Vec will never automatically shrink itself, even if completely empty. This
237/// ensures no unnecessary allocations or deallocations occur. Emptying a Vec
238/// and then filling it back up to the same `len()` should incur no calls to
239/// the allocator. If you wish to free up unused memory, use `shrink_to_fit`.
240///
241/// `push` and `insert` will never (re)allocate if the reported capacity is
242/// sufficient. `push` and `insert` *will* (re)allocate if `len() == capacity()`.
243/// That is, the reported capacity is completely accurate, and can be relied on.
244/// It can even be used to manually free the memory allocated by a Vec if
245/// desired. Bulk insertion methods *may* reallocate, even when not necessary.
246///
247/// Vec does not guarantee any particular growth strategy when reallocating
248/// when full, nor when `reserve` is called. The current strategy is basic
249/// and it may prove desirable to use a non-constant growth factor. Whatever
250/// strategy is used will of course guarantee `O(1)` amortized `push`.
251///
252/// `vec![x; n]`, `vec![a, b, c, d]`, and `Vec::with_capacity(n)`, will all
253/// produce a Vec with exactly the requested capacity. If `len() == capacity()`,
254/// (as is the case for the `vec!` macro), then a `Vec<T>` can be converted
255/// to and from a `Box<[T]>` without reallocating or moving the elements.
256///
257/// Vec will not specifically overwrite any data that is removed from it,
258/// but also won't specifically preserve it. Its uninitialized memory is
259/// scratch space that it may use however it wants. It will generally just do
260/// whatever is most efficient or otherwise easy to implement. Do not rely on
261/// removed data to be erased for security purposes. Even if you drop a Vec, its
262/// buffer may simply be reused by another Vec. Even if you zero a Vec's memory
263/// first, that may not actually happen because the optimizer does not consider
264/// this a side-effect that must be preserved.
265///
266/// Vec does not currently guarantee the order in which elements are dropped
267/// (the order has changed in the past, and may change again).
268///
1a4d82fc 269#[unsafe_no_drop_flag]
85aaf69f 270#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 271pub struct Vec<T> {
c1a9b12d 272 buf: RawVec<T>,
85aaf69f 273 len: usize,
1a4d82fc
JJ
274}
275
1a4d82fc
JJ
276////////////////////////////////////////////////////////////////////////////////
277// Inherent methods
278////////////////////////////////////////////////////////////////////////////////
279
280impl<T> Vec<T> {
281 /// Constructs a new, empty `Vec<T>`.
282 ///
283 /// The vector will not allocate until elements are pushed onto it.
284 ///
285 /// # Examples
286 ///
287 /// ```
92a42be0 288 /// # #![allow(unused_mut)]
85aaf69f 289 /// let mut vec: Vec<i32> = Vec::new();
1a4d82fc
JJ
290 /// ```
291 #[inline]
85aaf69f 292 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 293 pub fn new() -> Vec<T> {
92a42be0
SL
294 Vec {
295 buf: RawVec::new(),
296 len: 0,
297 }
1a4d82fc
JJ
298 }
299
300 /// Constructs a new, empty `Vec<T>` with the specified capacity.
301 ///
e9174d1e
SL
302 /// The vector will be able to hold exactly `capacity` elements without
303 /// reallocating. If `capacity` is 0, the vector will not allocate.
1a4d82fc 304 ///
e9174d1e
SL
305 /// It is important to note that this function does not specify the *length*
306 /// of the returned vector, but only the *capacity*. (For an explanation of
307 /// the difference between length and capacity, see the main `Vec<T>` docs
308 /// above, 'Capacity and reallocation'.)
1a4d82fc
JJ
309 ///
310 /// # Examples
311 ///
312 /// ```
9346a6ac 313 /// let mut vec = Vec::with_capacity(10);
1a4d82fc
JJ
314 ///
315 /// // The vector contains no items, even though it has capacity for more
316 /// assert_eq!(vec.len(), 0);
317 ///
318 /// // These are all done without reallocating...
85aaf69f 319 /// for i in 0..10 {
1a4d82fc
JJ
320 /// vec.push(i);
321 /// }
322 ///
323 /// // ...but this may make the vector reallocate
324 /// vec.push(11);
325 /// ```
326 #[inline]
85aaf69f
SL
327 #[stable(feature = "rust1", since = "1.0.0")]
328 pub fn with_capacity(capacity: usize) -> Vec<T> {
92a42be0
SL
329 Vec {
330 buf: RawVec::with_capacity(capacity),
331 len: 0,
332 }
1a4d82fc
JJ
333 }
334
335 /// Creates a `Vec<T>` directly from the raw components of another vector.
336 ///
b039eaaf 337 /// # Safety
c1a9b12d
SL
338 ///
339 /// This is highly unsafe, due to the number of invariants that aren't
340 /// checked:
341 ///
342 /// * `ptr` needs to have been previously allocated via `String`/`Vec<T>`
343 /// (at least, it's highly likely to be incorrect if it wasn't).
344 /// * `length` needs to be the length that less than or equal to `capacity`.
345 /// * `capacity` needs to be the capacity that the pointer was allocated with.
346 ///
347 /// Violating these may cause problems like corrupting the allocator's
348 /// internal datastructures.
1a4d82fc
JJ
349 ///
350 /// # Examples
351 ///
352 /// ```
353 /// use std::ptr;
354 /// use std::mem;
355 ///
356 /// fn main() {
85aaf69f 357 /// let mut v = vec![1, 2, 3];
1a4d82fc
JJ
358 ///
359 /// // Pull out the various important pieces of information about `v`
360 /// let p = v.as_mut_ptr();
361 /// let len = v.len();
362 /// let cap = v.capacity();
363 ///
364 /// unsafe {
365 /// // Cast `v` into the void: no destructor run, so we are in
366 /// // complete control of the allocation to which `p` points.
367 /// mem::forget(v);
368 ///
369 /// // Overwrite memory with 4, 5, 6
85aaf69f 370 /// for i in 0..len as isize {
1a4d82fc
JJ
371 /// ptr::write(p.offset(i), 4 + i);
372 /// }
373 ///
374 /// // Put everything back together into a Vec
375 /// let rebuilt = Vec::from_raw_parts(p, len, cap);
c34b1796 376 /// assert_eq!(rebuilt, [4, 5, 6]);
1a4d82fc
JJ
377 /// }
378 /// }
379 /// ```
85aaf69f 380 #[stable(feature = "rust1", since = "1.0.0")]
92a42be0 381 pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Vec<T> {
85aaf69f 382 Vec {
c1a9b12d 383 buf: RawVec::from_raw_parts(ptr, capacity),
85aaf69f 384 len: length,
85aaf69f 385 }
1a4d82fc
JJ
386 }
387
1a4d82fc
JJ
388 /// Returns the number of elements the vector can hold without
389 /// reallocating.
390 ///
391 /// # Examples
392 ///
393 /// ```
85aaf69f 394 /// let vec: Vec<i32> = Vec::with_capacity(10);
1a4d82fc
JJ
395 /// assert_eq!(vec.capacity(), 10);
396 /// ```
397 #[inline]
85aaf69f
SL
398 #[stable(feature = "rust1", since = "1.0.0")]
399 pub fn capacity(&self) -> usize {
c1a9b12d 400 self.buf.cap()
1a4d82fc
JJ
401 }
402
c34b1796
AL
403 /// Reserves capacity for at least `additional` more elements to be inserted
404 /// in the given `Vec<T>`. The collection may reserve more space to avoid
405 /// frequent reallocations.
1a4d82fc
JJ
406 ///
407 /// # Panics
408 ///
85aaf69f 409 /// Panics if the new capacity overflows `usize`.
1a4d82fc
JJ
410 ///
411 /// # Examples
412 ///
413 /// ```
85aaf69f 414 /// let mut vec = vec![1];
1a4d82fc
JJ
415 /// vec.reserve(10);
416 /// assert!(vec.capacity() >= 11);
417 /// ```
85aaf69f
SL
418 #[stable(feature = "rust1", since = "1.0.0")]
419 pub fn reserve(&mut self, additional: usize) {
c1a9b12d 420 self.buf.reserve(self.len, additional);
1a4d82fc
JJ
421 }
422
423 /// Reserves the minimum capacity for exactly `additional` more elements to
424 /// be inserted in the given `Vec<T>`. Does nothing if the capacity is already
425 /// sufficient.
426 ///
427 /// Note that the allocator may give the collection more space than it
428 /// requests. Therefore capacity can not be relied upon to be precisely
429 /// minimal. Prefer `reserve` if future insertions are expected.
430 ///
431 /// # Panics
432 ///
85aaf69f 433 /// Panics if the new capacity overflows `usize`.
1a4d82fc
JJ
434 ///
435 /// # Examples
436 ///
437 /// ```
85aaf69f 438 /// let mut vec = vec![1];
1a4d82fc
JJ
439 /// vec.reserve_exact(10);
440 /// assert!(vec.capacity() >= 11);
441 /// ```
85aaf69f
SL
442 #[stable(feature = "rust1", since = "1.0.0")]
443 pub fn reserve_exact(&mut self, additional: usize) {
c1a9b12d 444 self.buf.reserve_exact(self.len, additional);
1a4d82fc
JJ
445 }
446
447 /// Shrinks the capacity of the vector as much as possible.
448 ///
449 /// It will drop down as close as possible to the length but the allocator
450 /// may still inform the vector that there is space for a few more elements.
451 ///
452 /// # Examples
453 ///
454 /// ```
85aaf69f 455 /// let mut vec = Vec::with_capacity(10);
62682a34 456 /// vec.extend([1, 2, 3].iter().cloned());
1a4d82fc
JJ
457 /// assert_eq!(vec.capacity(), 10);
458 /// vec.shrink_to_fit();
459 /// assert!(vec.capacity() >= 3);
460 /// ```
85aaf69f 461 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 462 pub fn shrink_to_fit(&mut self) {
c1a9b12d 463 self.buf.shrink_to_fit(self.len);
1a4d82fc
JJ
464 }
465
9346a6ac 466 /// Converts the vector into Box<[T]>.
1a4d82fc
JJ
467 ///
468 /// Note that this will drop any excess capacity. Calling this and
469 /// converting back to a vector with `into_vec()` is equivalent to calling
470 /// `shrink_to_fit()`.
c34b1796 471 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 472 pub fn into_boxed_slice(mut self) -> Box<[T]> {
1a4d82fc 473 unsafe {
c1a9b12d
SL
474 self.shrink_to_fit();
475 let buf = ptr::read(&self.buf);
1a4d82fc 476 mem::forget(self);
c1a9b12d 477 buf.into_box()
1a4d82fc
JJ
478 }
479 }
480
92a42be0 481 /// Shorten a vector to be `len` elements long, dropping excess elements.
1a4d82fc
JJ
482 ///
483 /// If `len` is greater than the vector's current length, this has no
484 /// effect.
485 ///
486 /// # Examples
487 ///
488 /// ```
92a42be0 489 /// let mut vec = vec![1, 2, 3, 4, 5];
1a4d82fc 490 /// vec.truncate(2);
c34b1796 491 /// assert_eq!(vec, [1, 2]);
1a4d82fc 492 /// ```
85aaf69f
SL
493 #[stable(feature = "rust1", since = "1.0.0")]
494 pub fn truncate(&mut self, len: usize) {
1a4d82fc
JJ
495 unsafe {
496 // drop any extra elements
497 while len < self.len {
54a0048b
SL
498 // decrement len before the drop_in_place(), so a panic on Drop
499 // doesn't re-drop the just-failed value.
1a4d82fc 500 self.len -= 1;
54a0048b
SL
501 let len = self.len;
502 ptr::drop_in_place(self.get_unchecked_mut(len));
1a4d82fc
JJ
503 }
504 }
505 }
506
9346a6ac 507 /// Extracts a slice containing the entire vector.
62682a34
SL
508 ///
509 /// Equivalent to `&s[..]`.
1a4d82fc 510 #[inline]
9cc50fc6 511 #[stable(feature = "vec_as_slice", since = "1.7.0")]
c34b1796
AL
512 pub fn as_slice(&self) -> &[T] {
513 self
514 }
515
62682a34
SL
516 /// Extracts a mutable slice of the entire vector.
517 ///
518 /// Equivalent to `&mut s[..]`.
c34b1796 519 #[inline]
9cc50fc6 520 #[stable(feature = "vec_as_slice", since = "1.7.0")]
85aaf69f 521 pub fn as_mut_slice(&mut self) -> &mut [T] {
c34b1796 522 &mut self[..]
1a4d82fc
JJ
523 }
524
1a4d82fc
JJ
525 /// Sets the length of a vector.
526 ///
527 /// This will explicitly set the size of the vector, without actually
528 /// modifying its buffers, so it is up to the caller to ensure that the
529 /// vector is actually the specified size.
530 ///
531 /// # Examples
532 ///
533 /// ```
85aaf69f 534 /// let mut v = vec![1, 2, 3, 4];
1a4d82fc
JJ
535 /// unsafe {
536 /// v.set_len(1);
537 /// }
538 /// ```
539 #[inline]
85aaf69f
SL
540 #[stable(feature = "rust1", since = "1.0.0")]
541 pub unsafe fn set_len(&mut self, len: usize) {
1a4d82fc
JJ
542 self.len = len;
543 }
544
545 /// Removes an element from anywhere in the vector and return it, replacing
546 /// it with the last element.
547 ///
548 /// This does not preserve ordering, but is O(1).
549 ///
550 /// # Panics
551 ///
552 /// Panics if `index` is out of bounds.
553 ///
554 /// # Examples
555 ///
556 /// ```
557 /// let mut v = vec!["foo", "bar", "baz", "qux"];
558 ///
559 /// assert_eq!(v.swap_remove(1), "bar");
c34b1796 560 /// assert_eq!(v, ["foo", "qux", "baz"]);
1a4d82fc
JJ
561 ///
562 /// assert_eq!(v.swap_remove(0), "foo");
c34b1796 563 /// assert_eq!(v, ["baz", "qux"]);
1a4d82fc
JJ
564 /// ```
565 #[inline]
85aaf69f
SL
566 #[stable(feature = "rust1", since = "1.0.0")]
567 pub fn swap_remove(&mut self, index: usize) -> T {
1a4d82fc
JJ
568 let length = self.len();
569 self.swap(index, length - 1);
570 self.pop().unwrap()
571 }
572
573 /// Inserts an element at position `index` within the vector, shifting all
7453a54e 574 /// elements after it to the right.
1a4d82fc
JJ
575 ///
576 /// # Panics
577 ///
9346a6ac 578 /// Panics if `index` is greater than the vector's length.
1a4d82fc
JJ
579 ///
580 /// # Examples
581 ///
582 /// ```
85aaf69f 583 /// let mut vec = vec![1, 2, 3];
1a4d82fc 584 /// vec.insert(1, 4);
c34b1796 585 /// assert_eq!(vec, [1, 4, 2, 3]);
1a4d82fc 586 /// vec.insert(4, 5);
c34b1796 587 /// assert_eq!(vec, [1, 4, 2, 3, 5]);
1a4d82fc 588 /// ```
85aaf69f
SL
589 #[stable(feature = "rust1", since = "1.0.0")]
590 pub fn insert(&mut self, index: usize, element: T) {
1a4d82fc
JJ
591 let len = self.len();
592 assert!(index <= len);
c1a9b12d 593
1a4d82fc 594 // space for the new element
92a42be0
SL
595 if len == self.buf.cap() {
596 self.buf.double();
597 }
1a4d82fc 598
92a42be0
SL
599 unsafe {
600 // infallible
1a4d82fc
JJ
601 // The spot to put the new value
602 {
85aaf69f 603 let p = self.as_mut_ptr().offset(index as isize);
1a4d82fc
JJ
604 // Shift everything over to make space. (Duplicating the
605 // `index`th element into two consecutive places.)
c1a9b12d 606 ptr::copy(p, p.offset(1), len - index);
1a4d82fc
JJ
607 // Write it in, overwriting the first copy of the `index`th
608 // element.
c1a9b12d 609 ptr::write(p, element);
1a4d82fc
JJ
610 }
611 self.set_len(len + 1);
612 }
613 }
614
615 /// Removes and returns the element at position `index` within the vector,
7453a54e 616 /// shifting all elements after it to the left.
1a4d82fc
JJ
617 ///
618 /// # Panics
619 ///
bd371182 620 /// Panics if `index` is out of bounds.
1a4d82fc
JJ
621 ///
622 /// # Examples
623 ///
624 /// ```
85aaf69f 625 /// let mut v = vec![1, 2, 3];
1a4d82fc 626 /// assert_eq!(v.remove(1), 2);
c34b1796 627 /// assert_eq!(v, [1, 3]);
1a4d82fc 628 /// ```
85aaf69f
SL
629 #[stable(feature = "rust1", since = "1.0.0")]
630 pub fn remove(&mut self, index: usize) -> T {
1a4d82fc
JJ
631 let len = self.len();
632 assert!(index < len);
92a42be0
SL
633 unsafe {
634 // infallible
1a4d82fc
JJ
635 let ret;
636 {
637 // the place we are taking from.
85aaf69f 638 let ptr = self.as_mut_ptr().offset(index as isize);
1a4d82fc
JJ
639 // copy it out, unsafely having a copy of the value on
640 // the stack and in the vector at the same time.
85aaf69f 641 ret = ptr::read(ptr);
1a4d82fc
JJ
642
643 // Shift everything down to fill in that spot.
c1a9b12d 644 ptr::copy(ptr.offset(1), ptr, len - index - 1);
1a4d82fc
JJ
645 }
646 self.set_len(len - 1);
647 ret
648 }
649 }
650
651 /// Retains only the elements specified by the predicate.
652 ///
653 /// In other words, remove all elements `e` such that `f(&e)` returns false.
654 /// This method operates in place and preserves the order of the retained
655 /// elements.
656 ///
657 /// # Examples
658 ///
659 /// ```
85aaf69f 660 /// let mut vec = vec![1, 2, 3, 4];
1a4d82fc 661 /// vec.retain(|&x| x%2 == 0);
c34b1796 662 /// assert_eq!(vec, [2, 4]);
1a4d82fc 663 /// ```
85aaf69f 664 #[stable(feature = "rust1", since = "1.0.0")]
92a42be0
SL
665 pub fn retain<F>(&mut self, mut f: F)
666 where F: FnMut(&T) -> bool
667 {
1a4d82fc 668 let len = self.len();
85aaf69f 669 let mut del = 0;
1a4d82fc 670 {
85aaf69f 671 let v = &mut **self;
1a4d82fc 672
85aaf69f 673 for i in 0..len {
1a4d82fc
JJ
674 if !f(&v[i]) {
675 del += 1;
676 } else if del > 0 {
92a42be0 677 v.swap(i - del, i);
1a4d82fc
JJ
678 }
679 }
680 }
681 if del > 0 {
682 self.truncate(len - del);
683 }
684 }
685
686 /// Appends an element to the back of a collection.
687 ///
688 /// # Panics
689 ///
85aaf69f 690 /// Panics if the number of elements in the vector overflows a `usize`.
1a4d82fc
JJ
691 ///
692 /// # Examples
693 ///
c34b1796 694 /// ```
c1a9b12d 695 /// let mut vec = vec![1, 2];
1a4d82fc 696 /// vec.push(3);
c34b1796 697 /// assert_eq!(vec, [1, 2, 3]);
1a4d82fc
JJ
698 /// ```
699 #[inline]
85aaf69f 700 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 701 pub fn push(&mut self, value: T) {
c1a9b12d
SL
702 // This will panic or abort if we would allocate > isize::MAX bytes
703 // or if the length increment would overflow for zero-sized types.
92a42be0
SL
704 if self.len == self.buf.cap() {
705 self.buf.double();
706 }
1a4d82fc 707 unsafe {
c1a9b12d
SL
708 let end = self.as_mut_ptr().offset(self.len as isize);
709 ptr::write(end, value);
1a4d82fc
JJ
710 self.len += 1;
711 }
712 }
713
e9174d1e
SL
714 /// Removes the last element from a vector and returns it, or `None` if it
715 /// is empty.
1a4d82fc
JJ
716 ///
717 /// # Examples
718 ///
c34b1796 719 /// ```
85aaf69f 720 /// let mut vec = vec![1, 2, 3];
1a4d82fc 721 /// assert_eq!(vec.pop(), Some(3));
c34b1796 722 /// assert_eq!(vec, [1, 2]);
1a4d82fc
JJ
723 /// ```
724 #[inline]
85aaf69f 725 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
726 pub fn pop(&mut self) -> Option<T> {
727 if self.len == 0 {
728 None
729 } else {
730 unsafe {
731 self.len -= 1;
732 Some(ptr::read(self.get_unchecked(self.len())))
733 }
734 }
735 }
736
85aaf69f
SL
737 /// Moves all the elements of `other` into `Self`, leaving `other` empty.
738 ///
739 /// # Panics
740 ///
741 /// Panics if the number of elements in the vector overflows a `usize`.
742 ///
743 /// # Examples
744 ///
745 /// ```
746 /// let mut vec = vec![1, 2, 3];
747 /// let mut vec2 = vec![4, 5, 6];
748 /// vec.append(&mut vec2);
c34b1796
AL
749 /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
750 /// assert_eq!(vec2, []);
85aaf69f
SL
751 /// ```
752 #[inline]
e9174d1e 753 #[stable(feature = "append", since = "1.4.0")]
85aaf69f 754 pub fn append(&mut self, other: &mut Self) {
85aaf69f
SL
755 self.reserve(other.len());
756 let len = self.len();
757 unsafe {
92a42be0 758 ptr::copy_nonoverlapping(other.as_ptr(), self.get_unchecked_mut(len), other.len());
85aaf69f
SL
759 }
760
761 self.len += other.len();
92a42be0
SL
762 unsafe {
763 other.set_len(0);
764 }
85aaf69f
SL
765 }
766
d9579d0f 767 /// Create a draining iterator that removes the specified range in the vector
9cc50fc6 768 /// and yields the removed items.
d9579d0f 769 ///
9cc50fc6
SL
770 /// Note 1: The element range is removed even if the iterator is not
771 /// consumed until the end.
772 ///
773 /// Note 2: It is unspecified how many elements are removed from the vector,
d9579d0f
AL
774 /// if the `Drain` value is leaked.
775 ///
776 /// # Panics
777 ///
778 /// Panics if the starting point is greater than the end point or if
779 /// the end point is greater than the length of the vector.
1a4d82fc
JJ
780 ///
781 /// # Examples
782 ///
783 /// ```
d9579d0f 784 /// let mut v = vec![1, 2, 3];
9cc50fc6
SL
785 /// let u: Vec<_> = v.drain(1..).collect();
786 /// assert_eq!(v, &[1]);
787 /// assert_eq!(u, &[2, 3]);
788 ///
789 /// // A full range clears the vector
790 /// v.drain(..);
d9579d0f 791 /// assert_eq!(v, &[]);
1a4d82fc 792 /// ```
92a42be0
SL
793 #[stable(feature = "drain", since = "1.6.0")]
794 pub fn drain<R>(&mut self, range: R) -> Drain<T>
795 where R: RangeArgument<usize>
796 {
d9579d0f
AL
797 // Memory safety
798 //
799 // When the Drain is first created, it shortens the length of
800 // the source vector to make sure no uninitalized or moved-from elements
801 // are accessible at all if the Drain's destructor never gets to run.
802 //
803 // Drain will ptr::read out the values to remove.
804 // When finished, remaining tail of the vec is copied back to cover
805 // the hole, and the vector length is restored to the new length.
806 //
807 let len = self.len();
808 let start = *range.start().unwrap_or(&0);
809 let end = *range.end().unwrap_or(&len);
810 assert!(start <= end);
811 assert!(end <= len);
812
1a4d82fc 813 unsafe {
d9579d0f
AL
814 // set self.vec length's to start, to be safe in case Drain is leaked
815 self.set_len(start);
816 // Use the borrow in the IterMut to indicate borrowing behavior of the
817 // whole Drain iterator (like &mut T).
92a42be0
SL
818 let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().offset(start as isize),
819 end - start);
1a4d82fc 820 Drain {
d9579d0f
AL
821 tail_start: end,
822 tail_len: len - end,
823 iter: range_slice.iter_mut(),
824 vec: self as *mut _,
1a4d82fc
JJ
825 }
826 }
827 }
828
829 /// Clears the vector, removing all values.
830 ///
831 /// # Examples
832 ///
833 /// ```
85aaf69f 834 /// let mut v = vec![1, 2, 3];
1a4d82fc
JJ
835 ///
836 /// v.clear();
837 ///
838 /// assert!(v.is_empty());
839 /// ```
840 #[inline]
85aaf69f 841 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
842 pub fn clear(&mut self) {
843 self.truncate(0)
844 }
845
846 /// Returns the number of elements in the vector.
847 ///
848 /// # Examples
849 ///
850 /// ```
85aaf69f 851 /// let a = vec![1, 2, 3];
1a4d82fc
JJ
852 /// assert_eq!(a.len(), 3);
853 /// ```
854 #[inline]
85aaf69f 855 #[stable(feature = "rust1", since = "1.0.0")]
92a42be0
SL
856 pub fn len(&self) -> usize {
857 self.len
858 }
1a4d82fc
JJ
859
860 /// Returns `true` if the vector contains no elements.
861 ///
862 /// # Examples
863 ///
864 /// ```
865 /// let mut v = Vec::new();
866 /// assert!(v.is_empty());
867 ///
85aaf69f 868 /// v.push(1);
1a4d82fc
JJ
869 /// assert!(!v.is_empty());
870 /// ```
85aaf69f 871 #[stable(feature = "rust1", since = "1.0.0")]
92a42be0
SL
872 pub fn is_empty(&self) -> bool {
873 self.len() == 0
874 }
1a4d82fc 875
85aaf69f
SL
876 /// Splits the collection into two at the given index.
877 ///
878 /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
879 /// and the returned `Self` contains elements `[at, len)`.
880 ///
881 /// Note that the capacity of `self` does not change.
882 ///
883 /// # Panics
884 ///
885 /// Panics if `at > len`.
886 ///
887 /// # Examples
888 ///
889 /// ```
890 /// let mut vec = vec![1,2,3];
891 /// let vec2 = vec.split_off(1);
c34b1796
AL
892 /// assert_eq!(vec, [1]);
893 /// assert_eq!(vec2, [2, 3]);
85aaf69f
SL
894 /// ```
895 #[inline]
e9174d1e 896 #[stable(feature = "split_off", since = "1.4.0")]
85aaf69f
SL
897 pub fn split_off(&mut self, at: usize) -> Self {
898 assert!(at <= self.len(), "`at` out of bounds");
899
900 let other_len = self.len - at;
901 let mut other = Vec::with_capacity(other_len);
902
903 // Unsafely `set_len` and copy items to `other`.
904 unsafe {
905 self.set_len(at);
906 other.set_len(other_len);
907
92a42be0
SL
908 ptr::copy_nonoverlapping(self.as_ptr().offset(at as isize),
909 other.as_mut_ptr(),
910 other.len());
85aaf69f
SL
911 }
912 other
913 }
1a4d82fc
JJ
914}
915
916impl<T: Clone> Vec<T> {
917 /// Resizes the `Vec` in-place so that `len()` is equal to `new_len`.
918 ///
92a42be0
SL
919 /// If `new_len` is greater than `len()`, the `Vec` is extended by the
920 /// difference, with each additional slot filled with `value`.
921 /// If `new_len` is less than `len()`, the `Vec` is simply truncated.
1a4d82fc
JJ
922 ///
923 /// # Examples
924 ///
925 /// ```
926 /// let mut vec = vec!["hello"];
927 /// vec.resize(3, "world");
c34b1796 928 /// assert_eq!(vec, ["hello", "world", "world"]);
1a4d82fc 929 ///
85aaf69f 930 /// let mut vec = vec![1, 2, 3, 4];
1a4d82fc 931 /// vec.resize(2, 0);
c34b1796 932 /// assert_eq!(vec, [1, 2]);
1a4d82fc 933 /// ```
b039eaaf 934 #[stable(feature = "vec_resize", since = "1.5.0")]
85aaf69f 935 pub fn resize(&mut self, new_len: usize, value: T) {
1a4d82fc
JJ
936 let len = self.len();
937
938 if new_len > len {
c1a9b12d 939 self.extend_with_element(new_len - len, value);
1a4d82fc
JJ
940 } else {
941 self.truncate(new_len);
942 }
943 }
944
c1a9b12d
SL
945 /// Extend the vector by `n` additional clones of `value`.
946 fn extend_with_element(&mut self, n: usize, value: T) {
947 self.reserve(n);
948
949 unsafe {
950 let len = self.len();
951 let mut ptr = self.as_mut_ptr().offset(len as isize);
952 // Write all elements except the last one
953 for i in 1..n {
954 ptr::write(ptr, value.clone());
955 ptr = ptr.offset(1);
956 // Increment the length in every step in case clone() panics
957 self.set_len(len + i);
958 }
959
960 if n > 0 {
961 // We can write the last element directly without cloning needlessly
962 ptr::write(ptr, value);
963 self.set_len(len + n);
964 }
965 }
966 }
967
1a4d82fc
JJ
968 /// Appends all elements in a slice to the `Vec`.
969 ///
970 /// Iterates over the slice `other`, clones each element, and then appends
971 /// it to this `Vec`. The `other` vector is traversed in-order.
972 ///
92a42be0
SL
973 /// Note that this function is same as `extend` except that it is
974 /// specialized to work with slices instead. If and when Rust gets
975 /// specialization this function will likely be deprecated (but still
976 /// available).
977 ///
1a4d82fc
JJ
978 /// # Examples
979 ///
980 /// ```
85aaf69f 981 /// let mut vec = vec![1];
92a42be0 982 /// vec.extend_from_slice(&[2, 3, 4]);
c34b1796 983 /// assert_eq!(vec, [1, 2, 3, 4]);
1a4d82fc 984 /// ```
92a42be0
SL
985 #[stable(feature = "vec_extend_from_slice", since = "1.6.0")]
986 pub fn extend_from_slice(&mut self, other: &[T]) {
1a4d82fc
JJ
987 self.reserve(other.len());
988
85aaf69f 989 for i in 0..other.len() {
1a4d82fc
JJ
990 let len = self.len();
991
e9174d1e
SL
992 // Unsafe code so this can be optimised to a memcpy (or something
993 // similarly fast) when T is Copy. LLVM is easily confused, so any
994 // extra operations during the loop can prevent this optimisation.
1a4d82fc 995 unsafe {
92a42be0 996 ptr::write(self.get_unchecked_mut(len), other.get_unchecked(i).clone());
1a4d82fc
JJ
997 self.set_len(len + 1);
998 }
999 }
1000 }
1001}
1002
1003impl<T: PartialEq> Vec<T> {
1004 /// Removes consecutive repeated elements in the vector.
1005 ///
1006 /// If the vector is sorted, this removes all duplicates.
1007 ///
1008 /// # Examples
1009 ///
1010 /// ```
85aaf69f 1011 /// let mut vec = vec![1, 2, 2, 3, 2];
1a4d82fc
JJ
1012 ///
1013 /// vec.dedup();
1014 ///
c34b1796 1015 /// assert_eq!(vec, [1, 2, 3, 2]);
1a4d82fc 1016 /// ```
85aaf69f 1017 #[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1018 pub fn dedup(&mut self) {
1019 unsafe {
1020 // Although we have a mutable reference to `self`, we cannot make
1021 // *arbitrary* changes. The `PartialEq` comparisons could panic, so we
1022 // must ensure that the vector is in a valid state at all time.
1023 //
1024 // The way that we handle this is by using swaps; we iterate
1025 // over all the elements, swapping as we go so that at the end
1026 // the elements we wish to keep are in the front, and those we
1027 // wish to reject are at the back. We can then truncate the
1028 // vector. This operation is still O(n).
1029 //
1030 // Example: We start in this state, where `r` represents "next
1031 // read" and `w` represents "next_write`.
1032 //
1033 // r
1034 // +---+---+---+---+---+---+
1035 // | 0 | 1 | 1 | 2 | 3 | 3 |
1036 // +---+---+---+---+---+---+
1037 // w
1038 //
1039 // Comparing self[r] against self[w-1], this is not a duplicate, so
1040 // we swap self[r] and self[w] (no effect as r==w) and then increment both
1041 // r and w, leaving us with:
1042 //
1043 // r
1044 // +---+---+---+---+---+---+
1045 // | 0 | 1 | 1 | 2 | 3 | 3 |
1046 // +---+---+---+---+---+---+
1047 // w
1048 //
1049 // Comparing self[r] against self[w-1], this value is a duplicate,
1050 // so we increment `r` but leave everything else unchanged:
1051 //
1052 // r
1053 // +---+---+---+---+---+---+
1054 // | 0 | 1 | 1 | 2 | 3 | 3 |
1055 // +---+---+---+---+---+---+
1056 // w
1057 //
1058 // Comparing self[r] against self[w-1], this is not a duplicate,
1059 // so swap self[r] and self[w] and advance r and w:
1060 //
1061 // r
1062 // +---+---+---+---+---+---+
1063 // | 0 | 1 | 2 | 1 | 3 | 3 |
1064 // +---+---+---+---+---+---+
1065 // w
1066 //
1067 // Not a duplicate, repeat:
1068 //
1069 // r
1070 // +---+---+---+---+---+---+
1071 // | 0 | 1 | 2 | 3 | 1 | 3 |
1072 // +---+---+---+---+---+---+
1073 // w
1074 //
1075 // Duplicate, advance r. End of vec. Truncate to w.
1076
1077 let ln = self.len();
92a42be0
SL
1078 if ln <= 1 {
1079 return;
1080 }
1a4d82fc 1081
62682a34 1082 // Avoid bounds checks by using raw pointers.
1a4d82fc 1083 let p = self.as_mut_ptr();
c34b1796
AL
1084 let mut r: usize = 1;
1085 let mut w: usize = 1;
1a4d82fc
JJ
1086
1087 while r < ln {
85aaf69f
SL
1088 let p_r = p.offset(r as isize);
1089 let p_wm1 = p.offset((w - 1) as isize);
1a4d82fc
JJ
1090 if *p_r != *p_wm1 {
1091 if r != w {
1092 let p_w = p_wm1.offset(1);
1093 mem::swap(&mut *p_r, &mut *p_w);
1094 }
1095 w += 1;
1096 }
1097 r += 1;
1098 }
1099
1100 self.truncate(w);
1101 }
1102 }
1103}
1104
1105////////////////////////////////////////////////////////////////////////////////
1106// Internal methods and functions
1107////////////////////////////////////////////////////////////////////////////////
1108
85aaf69f
SL
1109#[doc(hidden)]
1110#[stable(feature = "rust1", since = "1.0.0")]
1111pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
c1a9b12d
SL
1112 let mut v = Vec::with_capacity(n);
1113 v.extend_with_element(n, elem);
1114 v
85aaf69f
SL
1115}
1116
1a4d82fc
JJ
1117////////////////////////////////////////////////////////////////////////////////
1118// Common trait implementations for Vec
1119////////////////////////////////////////////////////////////////////////////////
1120
bd371182 1121#[stable(feature = "rust1", since = "1.0.0")]
92a42be0 1122impl<T: Clone> Clone for Vec<T> {
c34b1796 1123 #[cfg(not(test))]
92a42be0
SL
1124 fn clone(&self) -> Vec<T> {
1125 <[T]>::to_vec(&**self)
1126 }
c34b1796
AL
1127
1128 // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
1129 // required for this method definition, is not available. Instead use the
1130 // `slice::to_vec` function which is only available with cfg(test)
1131 // NB see the slice::hack module in slice.rs for more information
1132 #[cfg(test)]
1133 fn clone(&self) -> Vec<T> {
1134 ::slice::to_vec(&**self)
1135 }
1a4d82fc
JJ
1136
1137 fn clone_from(&mut self, other: &Vec<T>) {
1138 // drop anything in self that will not be overwritten
b039eaaf
SL
1139 self.truncate(other.len());
1140 let len = self.len();
1a4d82fc
JJ
1141
1142 // reuse the contained values' allocations/resources.
b039eaaf 1143 self.clone_from_slice(&other[..len]);
1a4d82fc
JJ
1144
1145 // self.len <= other.len due to the truncate above, so the
1146 // slice here is always in-bounds.
92a42be0 1147 self.extend_from_slice(&other[len..]);
1a4d82fc
JJ
1148 }
1149}
1150
85aaf69f 1151#[stable(feature = "rust1", since = "1.0.0")]
85aaf69f 1152impl<T: Hash> Hash for Vec<T> {
1a4d82fc 1153 #[inline]
85aaf69f
SL
1154 fn hash<H: hash::Hasher>(&self, state: &mut H) {
1155 Hash::hash(&**self, state)
1a4d82fc
JJ
1156 }
1157}
1158
85aaf69f
SL
1159#[stable(feature = "rust1", since = "1.0.0")]
1160impl<T> Index<usize> for Vec<T> {
1a4d82fc
JJ
1161 type Output = T;
1162
1163 #[inline]
c34b1796 1164 fn index(&self, index: usize) -> &T {
85aaf69f 1165 // NB built-in indexing via `&[T]`
c34b1796 1166 &(**self)[index]
1a4d82fc
JJ
1167 }
1168}
1169
85aaf69f
SL
1170#[stable(feature = "rust1", since = "1.0.0")]
1171impl<T> IndexMut<usize> for Vec<T> {
1a4d82fc 1172 #[inline]
c34b1796 1173 fn index_mut(&mut self, index: usize) -> &mut T {
85aaf69f 1174 // NB built-in indexing via `&mut [T]`
c34b1796 1175 &mut (**self)[index]
1a4d82fc
JJ
1176 }
1177}
1178
1179
85aaf69f
SL
1180#[stable(feature = "rust1", since = "1.0.0")]
1181impl<T> ops::Index<ops::Range<usize>> for Vec<T> {
1a4d82fc 1182 type Output = [T];
c34b1796 1183
1a4d82fc 1184 #[inline]
c34b1796 1185 fn index(&self, index: ops::Range<usize>) -> &[T] {
85aaf69f 1186 Index::index(&**self, index)
1a4d82fc
JJ
1187 }
1188}
85aaf69f
SL
1189#[stable(feature = "rust1", since = "1.0.0")]
1190impl<T> ops::Index<ops::RangeTo<usize>> for Vec<T> {
1a4d82fc 1191 type Output = [T];
c34b1796 1192
1a4d82fc 1193 #[inline]
c34b1796 1194 fn index(&self, index: ops::RangeTo<usize>) -> &[T] {
85aaf69f 1195 Index::index(&**self, index)
1a4d82fc
JJ
1196 }
1197}
85aaf69f
SL
1198#[stable(feature = "rust1", since = "1.0.0")]
1199impl<T> ops::Index<ops::RangeFrom<usize>> for Vec<T> {
1a4d82fc 1200 type Output = [T];
c34b1796 1201
1a4d82fc 1202 #[inline]
c34b1796 1203 fn index(&self, index: ops::RangeFrom<usize>) -> &[T] {
85aaf69f 1204 Index::index(&**self, index)
1a4d82fc
JJ
1205 }
1206}
85aaf69f
SL
1207#[stable(feature = "rust1", since = "1.0.0")]
1208impl<T> ops::Index<ops::RangeFull> for Vec<T> {
1a4d82fc 1209 type Output = [T];
c34b1796 1210
1a4d82fc 1211 #[inline]
c34b1796
AL
1212 fn index(&self, _index: ops::RangeFull) -> &[T] {
1213 self
1a4d82fc
JJ
1214 }
1215}
54a0048b
SL
1216#[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1217impl<T> ops::Index<ops::RangeInclusive<usize>> for Vec<T> {
1218 type Output = [T];
1219
1220 #[inline]
1221 fn index(&self, index: ops::RangeInclusive<usize>) -> &[T] {
1222 Index::index(&**self, index)
1223 }
1224}
1225#[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1226impl<T> ops::Index<ops::RangeToInclusive<usize>> for Vec<T> {
1227 type Output = [T];
1228
1229 #[inline]
1230 fn index(&self, index: ops::RangeToInclusive<usize>) -> &[T] {
1231 Index::index(&**self, index)
1232 }
1233}
1a4d82fc 1234
85aaf69f
SL
1235#[stable(feature = "rust1", since = "1.0.0")]
1236impl<T> ops::IndexMut<ops::Range<usize>> for Vec<T> {
1a4d82fc 1237 #[inline]
c34b1796 1238 fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] {
85aaf69f 1239 IndexMut::index_mut(&mut **self, index)
1a4d82fc
JJ
1240 }
1241}
85aaf69f
SL
1242#[stable(feature = "rust1", since = "1.0.0")]
1243impl<T> ops::IndexMut<ops::RangeTo<usize>> for Vec<T> {
1a4d82fc 1244 #[inline]
c34b1796 1245 fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] {
85aaf69f 1246 IndexMut::index_mut(&mut **self, index)
1a4d82fc
JJ
1247 }
1248}
85aaf69f
SL
1249#[stable(feature = "rust1", since = "1.0.0")]
1250impl<T> ops::IndexMut<ops::RangeFrom<usize>> for Vec<T> {
1a4d82fc 1251 #[inline]
c34b1796 1252 fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] {
85aaf69f 1253 IndexMut::index_mut(&mut **self, index)
1a4d82fc
JJ
1254 }
1255}
85aaf69f
SL
1256#[stable(feature = "rust1", since = "1.0.0")]
1257impl<T> ops::IndexMut<ops::RangeFull> for Vec<T> {
1a4d82fc 1258 #[inline]
c34b1796
AL
1259 fn index_mut(&mut self, _index: ops::RangeFull) -> &mut [T] {
1260 self
1a4d82fc
JJ
1261 }
1262}
54a0048b
SL
1263#[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1264impl<T> ops::IndexMut<ops::RangeInclusive<usize>> for Vec<T> {
1265 #[inline]
1266 fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut [T] {
1267 IndexMut::index_mut(&mut **self, index)
1268 }
1269}
1270#[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
1271impl<T> ops::IndexMut<ops::RangeToInclusive<usize>> for Vec<T> {
1272 #[inline]
1273 fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut [T] {
1274 IndexMut::index_mut(&mut **self, index)
1275 }
1276}
1a4d82fc 1277
85aaf69f 1278#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1279impl<T> ops::Deref for Vec<T> {
1280 type Target = [T];
1281
c34b1796
AL
1282 fn deref(&self) -> &[T] {
1283 unsafe {
c1a9b12d 1284 let p = self.buf.ptr();
e9174d1e 1285 assume(!p.is_null());
c34b1796
AL
1286 slice::from_raw_parts(p, self.len)
1287 }
1288 }
1a4d82fc
JJ
1289}
1290
85aaf69f 1291#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 1292impl<T> ops::DerefMut for Vec<T> {
c34b1796
AL
1293 fn deref_mut(&mut self) -> &mut [T] {
1294 unsafe {
c1a9b12d 1295 let ptr = self.buf.ptr();
c34b1796
AL
1296 assume(!ptr.is_null());
1297 slice::from_raw_parts_mut(ptr, self.len)
1298 }
1299 }
1a4d82fc
JJ
1300}
1301
85aaf69f 1302#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1303impl<T> FromIterator<T> for Vec<T> {
1304 #[inline]
54a0048b 1305 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
62682a34
SL
1306 // Unroll the first iteration, as the vector is going to be
1307 // expanded on this iteration in every case when the iterable is not
1308 // empty, but the loop in extend_desugared() is not going to see the
1309 // vector being full in the few subsequent loop iterations.
92a42be0 1310 // So we get better branch prediction.
54a0048b 1311 let mut iterator = iter.into_iter();
62682a34
SL
1312 let mut vector = match iterator.next() {
1313 None => return Vec::new(),
1314 Some(element) => {
1315 let (lower, _) = iterator.size_hint();
1316 let mut vector = Vec::with_capacity(lower.saturating_add(1));
1317 unsafe {
1318 ptr::write(vector.get_unchecked_mut(0), element);
1319 vector.set_len(1);
1320 }
1321 vector
85aaf69f 1322 }
62682a34
SL
1323 };
1324 vector.extend_desugared(iterator);
1a4d82fc
JJ
1325 vector
1326 }
1327}
1328
85aaf69f
SL
1329#[stable(feature = "rust1", since = "1.0.0")]
1330impl<T> IntoIterator for Vec<T> {
1331 type Item = T;
1332 type IntoIter = IntoIter<T>;
1333
9346a6ac
AL
1334 /// Creates a consuming iterator, that is, one that moves each value out of
1335 /// the vector (from start to end). The vector cannot be used after calling
1336 /// this.
1337 ///
1338 /// # Examples
1339 ///
1340 /// ```
1341 /// let v = vec!["a".to_string(), "b".to_string()];
1342 /// for s in v.into_iter() {
1343 /// // s has type String, not &String
1344 /// println!("{}", s);
1345 /// }
1346 /// ```
1347 #[inline]
c1a9b12d 1348 fn into_iter(mut self) -> IntoIter<T> {
9346a6ac 1349 unsafe {
c1a9b12d 1350 let ptr = self.as_mut_ptr();
9346a6ac 1351 assume(!ptr.is_null());
9346a6ac
AL
1352 let begin = ptr as *const T;
1353 let end = if mem::size_of::<T>() == 0 {
62682a34 1354 arith_offset(ptr as *const i8, self.len() as isize) as *const T
9346a6ac
AL
1355 } else {
1356 ptr.offset(self.len() as isize) as *const T
1357 };
c1a9b12d 1358 let buf = ptr::read(&self.buf);
9346a6ac 1359 mem::forget(self);
92a42be0
SL
1360 IntoIter {
1361 _buf: buf,
1362 ptr: begin,
1363 end: end,
1364 }
9346a6ac 1365 }
85aaf69f
SL
1366 }
1367}
1368
1369#[stable(feature = "rust1", since = "1.0.0")]
1370impl<'a, T> IntoIterator for &'a Vec<T> {
1371 type Item = &'a T;
1372 type IntoIter = slice::Iter<'a, T>;
1373
1374 fn into_iter(self) -> slice::Iter<'a, T> {
1375 self.iter()
1376 }
1377}
1378
1379#[stable(feature = "rust1", since = "1.0.0")]
1380impl<'a, T> IntoIterator for &'a mut Vec<T> {
1381 type Item = &'a mut T;
1382 type IntoIter = slice::IterMut<'a, T>;
1383
1384 fn into_iter(mut self) -> slice::IterMut<'a, T> {
1385 self.iter_mut()
1386 }
1387}
1388
bd371182 1389#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1390impl<T> Extend<T> for Vec<T> {
1391 #[inline]
54a0048b
SL
1392 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1393 self.extend_desugared(iter.into_iter())
62682a34
SL
1394 }
1395}
1396
1397impl<T> Vec<T> {
92a42be0 1398 fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
62682a34
SL
1399 // This function should be the moral equivalent of:
1400 //
1401 // for item in iterator {
1402 // self.push(item);
1403 // }
1404 while let Some(element) = iterator.next() {
1405 let len = self.len();
1406 if len == self.capacity() {
1407 let (lower, _) = iterator.size_hint();
1408 self.reserve(lower.saturating_add(1));
1409 }
1410 unsafe {
1411 ptr::write(self.get_unchecked_mut(len), element);
1412 // NB can't overflow since we would have had to alloc the address space
1413 self.set_len(len + 1);
1414 }
1a4d82fc
JJ
1415 }
1416 }
1417}
1418
62682a34
SL
1419#[stable(feature = "extend_ref", since = "1.2.0")]
1420impl<'a, T: 'a + Copy> Extend<&'a T> for Vec<T> {
92a42be0 1421 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
62682a34
SL
1422 self.extend(iter.into_iter().cloned());
1423 }
1424}
1425
92a42be0
SL
1426macro_rules! __impl_slice_eq1 {
1427 ($Lhs: ty, $Rhs: ty) => {
1428 __impl_slice_eq1! { $Lhs, $Rhs, Sized }
1429 };
1430 ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
1431 #[stable(feature = "rust1", since = "1.0.0")]
1432 impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
1433 #[inline]
1434 fn eq(&self, other: &$Rhs) -> bool { self[..] == other[..] }
1435 #[inline]
1436 fn ne(&self, other: &$Rhs) -> bool { self[..] != other[..] }
1437 }
1438 }
1439}
1440
c34b1796
AL
1441__impl_slice_eq1! { Vec<A>, Vec<B> }
1442__impl_slice_eq1! { Vec<A>, &'b [B] }
1443__impl_slice_eq1! { Vec<A>, &'b mut [B] }
1444__impl_slice_eq1! { Cow<'a, [A]>, &'b [B], Clone }
1445__impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B], Clone }
1446__impl_slice_eq1! { Cow<'a, [A]>, Vec<B>, Clone }
1447
1448macro_rules! array_impls {
1449 ($($N: expr)+) => {
1450 $(
1451 // NOTE: some less important impls are omitted to reduce code bloat
1452 __impl_slice_eq1! { Vec<A>, [B; $N] }
1453 __impl_slice_eq1! { Vec<A>, &'b [B; $N] }
1454 // __impl_slice_eq1! { Vec<A>, &'b mut [B; $N] }
1455 // __impl_slice_eq1! { Cow<'a, [A]>, [B; $N], Clone }
1456 // __impl_slice_eq1! { Cow<'a, [A]>, &'b [B; $N], Clone }
1457 // __impl_slice_eq1! { Cow<'a, [A]>, &'b mut [B; $N], Clone }
1458 )+
1a4d82fc
JJ
1459 }
1460}
1461
c34b1796
AL
1462array_impls! {
1463 0 1 2 3 4 5 6 7 8 9
1464 10 11 12 13 14 15 16 17 18 19
1465 20 21 22 23 24 25 26 27 28 29
1466 30 31 32
1a4d82fc
JJ
1467}
1468
85aaf69f 1469#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1470impl<T: PartialOrd> PartialOrd for Vec<T> {
1471 #[inline]
1472 fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> {
85aaf69f 1473 PartialOrd::partial_cmp(&**self, &**other)
1a4d82fc
JJ
1474 }
1475}
1476
85aaf69f 1477#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1478impl<T: Eq> Eq for Vec<T> {}
1479
85aaf69f 1480#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1481impl<T: Ord> Ord for Vec<T> {
1482 #[inline]
1483 fn cmp(&self, other: &Vec<T>) -> Ordering {
85aaf69f 1484 Ord::cmp(&**self, &**other)
1a4d82fc
JJ
1485 }
1486}
1487
85aaf69f 1488#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 1489impl<T> Drop for Vec<T> {
b039eaaf 1490 #[unsafe_destructor_blind_to_params]
1a4d82fc 1491 fn drop(&mut self) {
c1a9b12d 1492 if self.buf.unsafe_no_drop_flag_needs_drop() {
b039eaaf 1493 unsafe {
54a0048b
SL
1494 // use drop for [T]
1495 ptr::drop_in_place(&mut self[..]);
1a4d82fc
JJ
1496 }
1497 }
c1a9b12d 1498 // RawVec handles deallocation
1a4d82fc
JJ
1499 }
1500}
1501
85aaf69f 1502#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 1503impl<T> Default for Vec<T> {
1a4d82fc
JJ
1504 fn default() -> Vec<T> {
1505 Vec::new()
1506 }
1507}
1508
85aaf69f
SL
1509#[stable(feature = "rust1", since = "1.0.0")]
1510impl<T: fmt::Debug> fmt::Debug for Vec<T> {
1a4d82fc 1511 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
85aaf69f 1512 fmt::Debug::fmt(&**self, f)
1a4d82fc
JJ
1513 }
1514}
1515
c34b1796
AL
1516#[stable(feature = "rust1", since = "1.0.0")]
1517impl<T> AsRef<Vec<T>> for Vec<T> {
1518 fn as_ref(&self) -> &Vec<T> {
1519 self
1520 }
1521}
1522
b039eaaf
SL
1523#[stable(feature = "vec_as_mut", since = "1.5.0")]
1524impl<T> AsMut<Vec<T>> for Vec<T> {
1525 fn as_mut(&mut self) -> &mut Vec<T> {
1526 self
1527 }
1528}
1529
c34b1796
AL
1530#[stable(feature = "rust1", since = "1.0.0")]
1531impl<T> AsRef<[T]> for Vec<T> {
1532 fn as_ref(&self) -> &[T] {
1533 self
1534 }
1535}
1536
b039eaaf
SL
1537#[stable(feature = "vec_as_mut", since = "1.5.0")]
1538impl<T> AsMut<[T]> for Vec<T> {
1539 fn as_mut(&mut self) -> &mut [T] {
1540 self
1541 }
1542}
1543
c34b1796
AL
1544#[stable(feature = "rust1", since = "1.0.0")]
1545impl<'a, T: Clone> From<&'a [T]> for Vec<T> {
1546 #[cfg(not(test))]
1547 fn from(s: &'a [T]) -> Vec<T> {
1548 s.to_vec()
1549 }
1550 #[cfg(test)]
1551 fn from(s: &'a [T]) -> Vec<T> {
1552 ::slice::to_vec(s)
1553 }
1554}
1555
1556#[stable(feature = "rust1", since = "1.0.0")]
1557impl<'a> From<&'a str> for Vec<u8> {
1558 fn from(s: &'a str) -> Vec<u8> {
1559 From::from(s.as_bytes())
1560 }
1561}
1562
1a4d82fc
JJ
1563////////////////////////////////////////////////////////////////////////////////
1564// Clone-on-write
1565////////////////////////////////////////////////////////////////////////////////
1566
7453a54e
SL
1567#[stable(feature = "cow_from_vec", since = "1.7.0")]
1568impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> {
1569 fn from(s: &'a [T]) -> Cow<'a, [T]> {
1570 Cow::Borrowed(s)
1571 }
1572}
1573
1574#[stable(feature = "cow_from_vec", since = "1.7.0")]
1575impl<'a, T: Clone> From<Vec<T>> for Cow<'a, [T]> {
1576 fn from(v: Vec<T>) -> Cow<'a, [T]> {
1577 Cow::Owned(v)
1578 }
1579}
1580
bd371182 1581#[stable(feature = "rust1", since = "1.0.0")]
85aaf69f 1582impl<'a, T> FromIterator<T> for Cow<'a, [T]> where T: Clone {
92a42be0 1583 fn from_iter<I: IntoIterator<Item = T>>(it: I) -> Cow<'a, [T]> {
1a4d82fc
JJ
1584 Cow::Owned(FromIterator::from_iter(it))
1585 }
1586}
1587
1a4d82fc
JJ
1588////////////////////////////////////////////////////////////////////////////////
1589// Iterators
1590////////////////////////////////////////////////////////////////////////////////
1591
1592/// An iterator that moves out of a vector.
85aaf69f 1593#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 1594pub struct IntoIter<T> {
e9174d1e 1595 _buf: RawVec<T>,
1a4d82fc 1596 ptr: *const T,
92a42be0 1597 end: *const T,
1a4d82fc
JJ
1598}
1599
92a42be0
SL
1600#[stable(feature = "rust1", since = "1.0.0")]
1601unsafe impl<T: Send> Send for IntoIter<T> {}
1602#[stable(feature = "rust1", since = "1.0.0")]
1603unsafe impl<T: Sync> Sync for IntoIter<T> {}
85aaf69f 1604
85aaf69f 1605#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1606impl<T> Iterator for IntoIter<T> {
1607 type Item = T;
1608
1609 #[inline]
85aaf69f 1610 fn next(&mut self) -> Option<T> {
1a4d82fc
JJ
1611 unsafe {
1612 if self.ptr == self.end {
1613 None
1614 } else {
1615 if mem::size_of::<T>() == 0 {
1616 // purposefully don't use 'ptr.offset' because for
1617 // vectors with 0-size elements this would return the
1618 // same pointer.
62682a34 1619 self.ptr = arith_offset(self.ptr as *const i8, 1) as *const T;
1a4d82fc
JJ
1620
1621 // Use a non-null pointer value
85aaf69f 1622 Some(ptr::read(EMPTY as *mut T))
1a4d82fc
JJ
1623 } else {
1624 let old = self.ptr;
1625 self.ptr = self.ptr.offset(1);
1626
1627 Some(ptr::read(old))
1628 }
1629 }
1630 }
1631 }
1632
1633 #[inline]
85aaf69f
SL
1634 fn size_hint(&self) -> (usize, Option<usize>) {
1635 let diff = (self.end as usize) - (self.ptr as usize);
1a4d82fc 1636 let size = mem::size_of::<T>();
92a42be0
SL
1637 let exact = diff /
1638 (if size == 0 {
1639 1
1640 } else {
1641 size
1642 });
1a4d82fc
JJ
1643 (exact, Some(exact))
1644 }
d9579d0f
AL
1645
1646 #[inline]
1647 fn count(self) -> usize {
1648 self.size_hint().0
1649 }
1a4d82fc
JJ
1650}
1651
85aaf69f 1652#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1653impl<T> DoubleEndedIterator for IntoIter<T> {
1654 #[inline]
85aaf69f 1655 fn next_back(&mut self) -> Option<T> {
1a4d82fc
JJ
1656 unsafe {
1657 if self.end == self.ptr {
1658 None
1659 } else {
1660 if mem::size_of::<T>() == 0 {
1661 // See above for why 'ptr.offset' isn't used
62682a34 1662 self.end = arith_offset(self.end as *const i8, -1) as *const T;
1a4d82fc
JJ
1663
1664 // Use a non-null pointer value
85aaf69f 1665 Some(ptr::read(EMPTY as *mut T))
1a4d82fc
JJ
1666 } else {
1667 self.end = self.end.offset(-1);
1668
e9174d1e 1669 Some(ptr::read(self.end))
1a4d82fc
JJ
1670 }
1671 }
1672 }
1673 }
1674}
1675
85aaf69f 1676#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1677impl<T> ExactSizeIterator for IntoIter<T> {}
1678
7453a54e
SL
1679#[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
1680impl<T: Clone> Clone for IntoIter<T> {
1681 fn clone(&self) -> IntoIter<T> {
1682 unsafe {
1683 slice::from_raw_parts(self.ptr, self.len()).to_owned().into_iter()
1684 }
1685 }
1686}
1687
85aaf69f 1688#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 1689impl<T> Drop for IntoIter<T> {
b039eaaf 1690 #[unsafe_destructor_blind_to_params]
1a4d82fc
JJ
1691 fn drop(&mut self) {
1692 // destroy the remaining elements
b039eaaf 1693 for _x in self {}
c1a9b12d
SL
1694
1695 // RawVec handles deallocation
1a4d82fc
JJ
1696 }
1697}
1698
d9579d0f 1699/// A draining iterator for `Vec<T>`.
92a42be0 1700#[stable(feature = "drain", since = "1.6.0")]
d9579d0f
AL
1701pub struct Drain<'a, T: 'a> {
1702 /// Index of tail to preserve
1703 tail_start: usize,
1704 /// Length of tail
1705 tail_len: usize,
1706 /// Current remaining range to remove
1707 iter: slice::IterMut<'a, T>,
1708 vec: *mut Vec<T>,
1a4d82fc
JJ
1709}
1710
92a42be0 1711#[stable(feature = "drain", since = "1.6.0")]
c34b1796 1712unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
92a42be0 1713#[stable(feature = "drain", since = "1.6.0")]
c34b1796
AL
1714unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
1715
85aaf69f 1716#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1717impl<'a, T> Iterator for Drain<'a, T> {
1718 type Item = T;
1719
1720 #[inline]
1721 fn next(&mut self) -> Option<T> {
92a42be0 1722 self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
1a4d82fc
JJ
1723 }
1724
85aaf69f 1725 fn size_hint(&self) -> (usize, Option<usize>) {
d9579d0f 1726 self.iter.size_hint()
1a4d82fc
JJ
1727 }
1728}
1729
85aaf69f 1730#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1731impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
1732 #[inline]
1733 fn next_back(&mut self) -> Option<T> {
92a42be0 1734 self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
1a4d82fc
JJ
1735 }
1736}
1737
85aaf69f 1738#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc
JJ
1739impl<'a, T> Drop for Drain<'a, T> {
1740 fn drop(&mut self) {
d9579d0f 1741 // exhaust self first
92a42be0 1742 while let Some(_) = self.next() {}
1a4d82fc 1743
d9579d0f
AL
1744 if self.tail_len > 0 {
1745 unsafe {
1746 let source_vec = &mut *self.vec;
1747 // memmove back untouched tail, update to new length
1748 let start = source_vec.len();
1749 let tail = self.tail_start;
1750 let src = source_vec.as_ptr().offset(tail as isize);
1751 let dst = source_vec.as_mut_ptr().offset(start as isize);
1752 ptr::copy(src, dst, self.tail_len);
1753 source_vec.set_len(start + self.tail_len);
1754 }
1755 }
1a4d82fc
JJ
1756 }
1757}
1758
d9579d0f
AL
1759
1760#[stable(feature = "rust1", since = "1.0.0")]
1761impl<'a, T> ExactSizeIterator for Drain<'a, T> {}