src/libcollections/vec_map.rs

   1 // Copyright 2012-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 simple map based on a vector for small integer keys. Space requirements
  12 //! are O(highest integer key).
  13
  14 #![allow(missing_docs)]
  15
  16 pub use self::Entry::*;
  17
  18 use core::prelude::*;
  19
  20 use core::cmp::Ordering;
  21 use core::default::Default;
  22 use core::fmt;
  23 use core::hash::{Hash, Writer, Hasher};
  24 use core::iter::{Enumerate, FilterMap, Map, FromIterator, IntoIterator};
  25 use core::iter;
  26 use core::mem::replace;
  27 use core::ops::{Index, IndexMut};
  28
  29 use {vec, slice};
  30 use vec::Vec;
  31
  32 /// A map optimized for small integer keys.
  33 ///
  34 /// # Examples
  35 ///
  36 /// ```
  37 /// use std::collections::VecMap;
  38 ///
  39 /// let mut months = VecMap::new();
  40 /// months.insert(1, "Jan");
  41 /// months.insert(2, "Feb");
  42 /// months.insert(3, "Mar");
  43 ///
  44 /// if !months.contains_key(&12) {
  45 ///     println!("The end is near!");
  46 /// }
  47 ///
  48 /// assert_eq!(months.get(&1), Some(&"Jan"));
  49 ///
  50 /// match months.get_mut(&3) {
  51 ///     Some(value) => *value = "Venus",
  52 ///     None => (),
  53 /// }
  54 ///
  55 /// assert_eq!(months.get(&3), Some(&"Venus"));
  56 ///
  57 /// // Print out all months
  58 /// for (key, value) in months.iter() {
  59 ///     println!("month {} is {}", key, value);
  60 /// }
  61 ///
  62 /// months.clear();
  63 /// assert!(months.is_empty());
  64 /// ```
  65 pub struct VecMap<V> {
  66     v: Vec<Option<V>>,
  67 }
  68
  69 /// A view into a single entry in a map, which may either be vacant or occupied.
  70 #[unstable(feature = "collections",
  71            reason = "precise API still under development")]
  72 pub enum Entry<'a, V:'a> {
  73     /// A vacant Entry
  74     Vacant(VacantEntry<'a, V>),
  75     /// An occupied Entry
  76     Occupied(OccupiedEntry<'a, V>),
  77 }
  78
  79 /// A vacant Entry.
  80 #[unstable(feature = "collections",
  81            reason = "precise API still under development")]
  82 pub struct VacantEntry<'a, V:'a> {
  83     map: &'a mut VecMap<V>,
  84     index: usize,
  85 }
  86
  87 /// An occupied Entry.
  88 #[unstable(feature = "collections",
  89            reason = "precise API still under development")]
  90 pub struct OccupiedEntry<'a, V:'a> {
  91     map: &'a mut VecMap<V>,
  92     index: usize,
  93 }
  94
  95 #[stable(feature = "rust1", since = "1.0.0")]
  96 impl<V> Default for VecMap<V> {
  97     #[stable(feature = "rust1", since = "1.0.0")]
  98     #[inline]
  99     fn default() -> VecMap<V> { VecMap::new() }
 100 }
 101
 102 impl<V:Clone> Clone for VecMap<V> {
 103     #[inline]
 104     fn clone(&self) -> VecMap<V> {
 105         VecMap { v: self.v.clone() }
 106     }
 107
 108     #[inline]
 109     fn clone_from(&mut self, source: &VecMap<V>) {
 110         self.v.clone_from(&source.v);
 111     }
 112 }
 113
 114 impl<S: Writer + Hasher, V: Hash<S>> Hash<S> for VecMap<V> {
 115     fn hash(&self, state: &mut S) {
 116         // In order to not traverse the `VecMap` twice, count the elements
 117         // during iteration.
 118         let mut count: usize = 0;
 119         for elt in self {
 120             elt.hash(state);
 121             count += 1;
 122         }
 123         count.hash(state);
 124     }
 125 }
 126
 127 impl<V> VecMap<V> {
 128     /// Creates an empty `VecMap`.
 129     ///
 130     /// # Examples
 131     ///
 132     /// ```
 133     /// use std::collections::VecMap;
 134     /// let mut map: VecMap<&str> = VecMap::new();
 135     /// ```
 136     #[stable(feature = "rust1", since = "1.0.0")]
 137     pub fn new() -> VecMap<V> { VecMap { v: vec![] } }
 138
 139     /// Creates an empty `VecMap` with space for at least `capacity`
 140     /// elements before resizing.
 141     ///
 142     /// # Examples
 143     ///
 144     /// ```
 145     /// use std::collections::VecMap;
 146     /// let mut map: VecMap<&str> = VecMap::with_capacity(10);
 147     /// ```
 148     #[stable(feature = "rust1", since = "1.0.0")]
 149     pub fn with_capacity(capacity: usize) -> VecMap<V> {
 150         VecMap { v: Vec::with_capacity(capacity) }
 151     }
 152
 153     /// Returns the number of elements the `VecMap` can hold without
 154     /// reallocating.
 155     ///
 156     /// # Examples
 157     ///
 158     /// ```
 159     /// use std::collections::VecMap;
 160     /// let map: VecMap<String> = VecMap::with_capacity(10);
 161     /// assert!(map.capacity() >= 10);
 162     /// ```
 163     #[inline]
 164     #[stable(feature = "rust1", since = "1.0.0")]
 165     pub fn capacity(&self) -> usize {
 166         self.v.capacity()
 167     }
 168
 169     /// Reserves capacity for the given `VecMap` to contain `len` distinct keys.
 170     /// In the case of `VecMap` this means reallocations will not occur as long
 171     /// as all inserted keys are less than `len`.
 172     ///
 173     /// The collection may reserve more space to avoid frequent reallocations.
 174     ///
 175     /// # Examples
 176     ///
 177     /// ```
 178     /// use std::collections::VecMap;
 179     /// let mut map: VecMap<&str> = VecMap::new();
 180     /// map.reserve_len(10);
 181     /// assert!(map.capacity() >= 10);
 182     /// ```
 183     #[stable(feature = "rust1", since = "1.0.0")]
 184     pub fn reserve_len(&mut self, len: usize) {
 185         let cur_len = self.v.len();
 186         if len >= cur_len {
 187             self.v.reserve(len - cur_len);
 188         }
 189     }
 190
 191     /// Reserves the minimum capacity for the given `VecMap` to contain `len` distinct keys.
 192     /// In the case of `VecMap` this means reallocations will not occur as long as all inserted
 193     /// keys are less than `len`.
 194     ///
 195     /// Note that the allocator may give the collection more space than it requests.
 196     /// Therefore capacity cannot be relied upon to be precisely minimal.  Prefer
 197     /// `reserve_len` if future insertions are expected.
 198     ///
 199     /// # Examples
 200     ///
 201     /// ```
 202     /// use std::collections::VecMap;
 203     /// let mut map: VecMap<&str> = VecMap::new();
 204     /// map.reserve_len_exact(10);
 205     /// assert!(map.capacity() >= 10);
 206     /// ```
 207     #[stable(feature = "rust1", since = "1.0.0")]
 208     pub fn reserve_len_exact(&mut self, len: usize) {
 209         let cur_len = self.v.len();
 210         if len >= cur_len {
 211             self.v.reserve_exact(len - cur_len);
 212         }
 213     }
 214
 215     /// Returns an iterator visiting all keys in ascending order of the keys.
 216     /// The iterator's element type is `usize`.
 217     #[stable(feature = "rust1", since = "1.0.0")]
 218     pub fn keys<'r>(&'r self) -> Keys<'r, V> {
 219         fn first<A, B>((a, _): (A, B)) -> A { a }
 220         let first: fn((usize, &'r V)) -> usize = first; // coerce to fn pointer
 221
 222         Keys { iter: self.iter().map(first) }
 223     }
 224
 225     /// Returns an iterator visiting all values in ascending order of the keys.
 226     /// The iterator's element type is `&'r V`.
 227     #[stable(feature = "rust1", since = "1.0.0")]
 228     pub fn values<'r>(&'r self) -> Values<'r, V> {
 229         fn second<A, B>((_, b): (A, B)) -> B { b }
 230         let second: fn((usize, &'r V)) -> &'r V = second; // coerce to fn pointer
 231
 232         Values { iter: self.iter().map(second) }
 233     }
 234
 235     /// Returns an iterator visiting all key-value pairs in ascending order of the keys.
 236     /// The iterator's element type is `(usize, &'r V)`.
 237     ///
 238     /// # Examples
 239     ///
 240     /// ```
 241     /// use std::collections::VecMap;
 242     ///
 243     /// let mut map = VecMap::new();
 244     /// map.insert(1, "a");
 245     /// map.insert(3, "c");
 246     /// map.insert(2, "b");
 247     ///
 248     /// // Print `1: a` then `2: b` then `3: c`
 249     /// for (key, value) in map.iter() {
 250     ///     println!("{}: {}", key, value);
 251     /// }
 252     /// ```
 253     #[stable(feature = "rust1", since = "1.0.0")]
 254     pub fn iter<'r>(&'r self) -> Iter<'r, V> {
 255         Iter {
 256             front: 0,
 257             back: self.v.len(),
 258             iter: self.v.iter()
 259         }
 260     }
 261
 262     /// Returns an iterator visiting all key-value pairs in ascending order of the keys,
 263     /// with mutable references to the values.
 264     /// The iterator's element type is `(usize, &'r mut V)`.
 265     ///
 266     /// # Examples
 267     ///
 268     /// ```
 269     /// use std::collections::VecMap;
 270     ///
 271     /// let mut map = VecMap::new();
 272     /// map.insert(1, "a");
 273     /// map.insert(2, "b");
 274     /// map.insert(3, "c");
 275     ///
 276     /// for (key, value) in map.iter_mut() {
 277     ///     *value = "x";
 278     /// }
 279     ///
 280     /// for (key, value) in map.iter() {
 281     ///     assert_eq!(value, &"x");
 282     /// }
 283     /// ```
 284     #[stable(feature = "rust1", since = "1.0.0")]
 285     pub fn iter_mut<'r>(&'r mut self) -> IterMut<'r, V> {
 286         IterMut {
 287             front: 0,
 288             back: self.v.len(),
 289             iter: self.v.iter_mut()
 290         }
 291     }
 292
 293     /// Returns an iterator visiting all key-value pairs in ascending order of
 294     /// the keys, consuming the original `VecMap`.
 295     /// The iterator's element type is `(usize, &'r V)`.
 296     ///
 297     /// # Examples
 298     ///
 299     /// ```
 300     /// use std::collections::VecMap;
 301     ///
 302     /// let mut map = VecMap::new();
 303     /// map.insert(1, "a");
 304     /// map.insert(3, "c");
 305     /// map.insert(2, "b");
 306     ///
 307     /// let vec: Vec<(usize, &str)> = map.into_iter().collect();
 308     ///
 309     /// assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
 310     /// ```
 311     #[stable(feature = "rust1", since = "1.0.0")]
 312     pub fn into_iter(self) -> IntoIter<V> {
 313         fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
 314             v.map(|v| (i, v))
 315         }
 316         let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr
 317
 318         IntoIter { iter: self.v.into_iter().enumerate().filter_map(filter) }
 319     }
 320
 321     /// Returns an iterator visiting all key-value pairs in ascending order of
 322     /// the keys, emptying (but not consuming) the original `VecMap`.
 323     /// The iterator's element type is `(usize, &'r V)`. Keeps the allocated memory for reuse.
 324     ///
 325     /// # Examples
 326     ///
 327     /// ```
 328     /// use std::collections::VecMap;
 329     ///
 330     /// let mut map = VecMap::new();
 331     /// map.insert(1, "a");
 332     /// map.insert(3, "c");
 333     /// map.insert(2, "b");
 334     ///
 335     /// let vec: Vec<(usize, &str)> = map.drain().collect();
 336     ///
 337     /// assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
 338     /// ```
 339     #[unstable(feature = "collections",
 340                reason = "matches collection reform specification, waiting for dust to settle")]
 341     pub fn drain<'a>(&'a mut self) -> Drain<'a, V> {
 342         fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> {
 343             v.map(|v| (i, v))
 344         }
 345         let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr
 346
 347         Drain { iter: self.v.drain().enumerate().filter_map(filter) }
 348     }
 349
 350     /// Return the number of elements in the map.
 351     ///
 352     /// # Examples
 353     ///
 354     /// ```
 355     /// use std::collections::VecMap;
 356     ///
 357     /// let mut a = VecMap::new();
 358     /// assert_eq!(a.len(), 0);
 359     /// a.insert(1, "a");
 360     /// assert_eq!(a.len(), 1);
 361     /// ```
 362     #[stable(feature = "rust1", since = "1.0.0")]
 363     pub fn len(&self) -> usize {
 364         self.v.iter().filter(|elt| elt.is_some()).count()
 365     }
 366
 367     /// Return true if the map contains no elements.
 368     ///
 369     /// # Examples
 370     ///
 371     /// ```
 372     /// use std::collections::VecMap;
 373     ///
 374     /// let mut a = VecMap::new();
 375     /// assert!(a.is_empty());
 376     /// a.insert(1, "a");
 377     /// assert!(!a.is_empty());
 378     /// ```
 379     #[stable(feature = "rust1", since = "1.0.0")]
 380     pub fn is_empty(&self) -> bool {
 381         self.v.iter().all(|elt| elt.is_none())
 382     }
 383
 384     /// Clears the map, removing all key-value pairs.
 385     ///
 386     /// # Examples
 387     ///
 388     /// ```
 389     /// use std::collections::VecMap;
 390     ///
 391     /// let mut a = VecMap::new();
 392     /// a.insert(1, "a");
 393     /// a.clear();
 394     /// assert!(a.is_empty());
 395     /// ```
 396     #[stable(feature = "rust1", since = "1.0.0")]
 397     pub fn clear(&mut self) { self.v.clear() }
 398
 399     /// Returns a reference to the value corresponding to the key.
 400     ///
 401     /// # Examples
 402     ///
 403     /// ```
 404     /// use std::collections::VecMap;
 405     ///
 406     /// let mut map = VecMap::new();
 407     /// map.insert(1, "a");
 408     /// assert_eq!(map.get(&1), Some(&"a"));
 409     /// assert_eq!(map.get(&2), None);
 410     /// ```
 411     #[stable(feature = "rust1", since = "1.0.0")]
 412     pub fn get(&self, key: &usize) -> Option<&V> {
 413         if *key < self.v.len() {
 414             match self.v[*key] {
 415               Some(ref value) => Some(value),
 416               None => None
 417             }
 418         } else {
 419             None
 420         }
 421     }
 422
 423     /// Returns true if the map contains a value for the specified key.
 424     ///
 425     /// # Examples
 426     ///
 427     /// ```
 428     /// use std::collections::VecMap;
 429     ///
 430     /// let mut map = VecMap::new();
 431     /// map.insert(1, "a");
 432     /// assert_eq!(map.contains_key(&1), true);
 433     /// assert_eq!(map.contains_key(&2), false);
 434     /// ```
 435     #[inline]
 436     #[stable(feature = "rust1", since = "1.0.0")]
 437     pub fn contains_key(&self, key: &usize) -> bool {
 438         self.get(key).is_some()
 439     }
 440
 441     /// Returns a mutable reference to the value corresponding to the key.
 442     ///
 443     /// # Examples
 444     ///
 445     /// ```
 446     /// use std::collections::VecMap;
 447     ///
 448     /// let mut map = VecMap::new();
 449     /// map.insert(1, "a");
 450     /// match map.get_mut(&1) {
 451     ///     Some(x) => *x = "b",
 452     ///     None => (),
 453     /// }
 454     /// assert_eq!(map[1], "b");
 455     /// ```
 456     #[stable(feature = "rust1", since = "1.0.0")]
 457     pub fn get_mut(&mut self, key: &usize) -> Option<&mut V> {
 458         if *key < self.v.len() {
 459             match *(&mut self.v[*key]) {
 460               Some(ref mut value) => Some(value),
 461               None => None
 462             }
 463         } else {
 464             None
 465         }
 466     }
 467
 468     /// Inserts a key-value pair from the map. If the key already had a value
 469     /// present in the map, that value is returned. Otherwise, `None` is returned.
 470     ///
 471     /// # Examples
 472     ///
 473     /// ```
 474     /// use std::collections::VecMap;
 475     ///
 476     /// let mut map = VecMap::new();
 477     /// assert_eq!(map.insert(37, "a"), None);
 478     /// assert_eq!(map.is_empty(), false);
 479     ///
 480     /// map.insert(37, "b");
 481     /// assert_eq!(map.insert(37, "c"), Some("b"));
 482     /// assert_eq!(map[37], "c");
 483     /// ```
 484     #[stable(feature = "rust1", since = "1.0.0")]
 485     pub fn insert(&mut self, key: usize, value: V) -> Option<V> {
 486         let len = self.v.len();
 487         if len <= key {
 488             self.v.extend((0..key - len + 1).map(|_| None));
 489         }
 490         replace(&mut self.v[key], Some(value))
 491     }
 492
 493     /// Removes a key from the map, returning the value at the key if the key
 494     /// was previously in the map.
 495     ///
 496     /// # Examples
 497     ///
 498     /// ```
 499     /// use std::collections::VecMap;
 500     ///
 501     /// let mut map = VecMap::new();
 502     /// map.insert(1, "a");
 503     /// assert_eq!(map.remove(&1), Some("a"));
 504     /// assert_eq!(map.remove(&1), None);
 505     /// ```
 506     #[stable(feature = "rust1", since = "1.0.0")]
 507     pub fn remove(&mut self, key: &usize) -> Option<V> {
 508         if *key >= self.v.len() {
 509             return None;
 510         }
 511         let result = &mut self.v[*key];
 512         result.take()
 513     }
 514
 515     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 516     ///
 517     /// # Examples
 518     ///
 519     /// ```
 520     /// use std::collections::VecMap;
 521     /// use std::collections::vec_map::Entry;
 522     ///
 523     /// let mut count: VecMap<u32> = VecMap::new();
 524     ///
 525     /// // count the number of occurrences of numbers in the vec
 526     /// for x in vec![1, 2, 1, 2, 3, 4, 1, 2, 4].iter() {
 527     ///     match count.entry(*x) {
 528     ///         Entry::Vacant(view) => {
 529     ///             view.insert(1);
 530     ///         },
 531     ///         Entry::Occupied(mut view) => {
 532     ///             let v = view.get_mut();
 533     ///             *v += 1;
 534     ///         },
 535     ///     }
 536     /// }
 537     ///
 538     /// assert_eq!(count[1], 3);
 539     /// ```
 540     #[unstable(feature = "collections",
 541                reason = "precise API still under development")]
 542     pub fn entry(&mut self, key: usize) -> Entry<V> {
 543         // FIXME(Gankro): this is basically the dumbest implementation of
 544         // entry possible, because weird non-lexical borrows issues make it
 545         // completely insane to do any other way. That said, Entry is a border-line
 546         // useless construct on VecMap, so it's hardly a big loss.
 547         if self.contains_key(&key) {
 548             Occupied(OccupiedEntry {
 549                 map: self,
 550                 index: key,
 551             })
 552         } else {
 553             Vacant(VacantEntry {
 554                 map: self,
 555                 index: key,
 556             })
 557         }
 558     }
 559 }
 560
 561
 562 impl<'a, V> Entry<'a, V> {
 563     #[unstable(feature = "collections",
 564                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 565     /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
 566     pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, V>> {
 567         match self {
 568             Occupied(entry) => Ok(entry.into_mut()),
 569             Vacant(entry) => Err(entry),
 570         }
 571     }
 572 }
 573
 574 impl<'a, V> VacantEntry<'a, V> {
 575     /// Sets the value of the entry with the VacantEntry's key,
 576     /// and returns a mutable reference to it.
 577     #[unstable(feature = "collections",
 578                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 579     pub fn insert(self, value: V) -> &'a mut V {
 580         let index = self.index;
 581         self.map.insert(index, value);
 582         &mut self.map[index]
 583     }
 584 }
 585
 586 impl<'a, V> OccupiedEntry<'a, V> {
 587     /// Gets a reference to the value in the entry.
 588     #[unstable(feature = "collections",
 589                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 590     pub fn get(&self) -> &V {
 591         let index = self.index;
 592         &self.map[index]
 593     }
 594
 595     /// Gets a mutable reference to the value in the entry.
 596     #[unstable(feature = "collections",
 597                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 598     pub fn get_mut(&mut self) -> &mut V {
 599         let index = self.index;
 600         &mut self.map[index]
 601     }
 602
 603     /// Converts the entry into a mutable reference to its value.
 604     #[unstable(feature = "collections",
 605                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 606     pub fn into_mut(self) -> &'a mut V {
 607         let index = self.index;
 608         &mut self.map[index]
 609     }
 610
 611     /// Sets the value of the entry with the OccupiedEntry's key,
 612     /// and returns the entry's old value.
 613     #[unstable(feature = "collections",
 614                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 615     pub fn insert(&mut self, value: V) -> V {
 616         let index = self.index;
 617         self.map.insert(index, value).unwrap()
 618     }
 619
 620     /// Takes the value of the entry out of the map, and returns it.
 621     #[unstable(feature = "collections",
 622                reason = "matches collection reform v2 specification, waiting for dust to settle")]
 623     pub fn remove(self) -> V {
 624         let index = self.index;
 625         self.map.remove(&index).unwrap()
 626     }
 627 }
 628
 629 #[stable(feature = "rust1", since = "1.0.0")]
 630 impl<V: PartialEq> PartialEq for VecMap<V> {
 631     fn eq(&self, other: &VecMap<V>) -> bool {
 632         iter::order::eq(self.iter(), other.iter())
 633     }
 634 }
 635
 636 #[stable(feature = "rust1", since = "1.0.0")]
 637 impl<V: Eq> Eq for VecMap<V> {}
 638
 639 #[stable(feature = "rust1", since = "1.0.0")]
 640 impl<V: PartialOrd> PartialOrd for VecMap<V> {
 641     #[inline]
 642     fn partial_cmp(&self, other: &VecMap<V>) -> Option<Ordering> {
 643         iter::order::partial_cmp(self.iter(), other.iter())
 644     }
 645 }
 646
 647 #[stable(feature = "rust1", since = "1.0.0")]
 648 impl<V: Ord> Ord for VecMap<V> {
 649     #[inline]
 650     fn cmp(&self, other: &VecMap<V>) -> Ordering {
 651         iter::order::cmp(self.iter(), other.iter())
 652     }
 653 }
 654
 655 #[stable(feature = "rust1", since = "1.0.0")]
 656 impl<V: fmt::Debug> fmt::Debug for VecMap<V> {
 657     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 658         try!(write!(f, "VecMap {{"));
 659
 660         for (i, (k, v)) in self.iter().enumerate() {
 661             if i != 0 { try!(write!(f, ", ")); }
 662             try!(write!(f, "{}: {:?}", k, *v));
 663         }
 664
 665         write!(f, "}}")
 666     }
 667 }
 668
 669 #[stable(feature = "rust1", since = "1.0.0")]
 670 impl<V> FromIterator<(usize, V)> for VecMap<V> {
 671     fn from_iter<Iter: Iterator<Item=(usize, V)>>(iter: Iter) -> VecMap<V> {
 672         let mut map = VecMap::new();
 673         map.extend(iter);
 674         map
 675     }
 676 }
 677
 678 impl<T> IntoIterator for VecMap<T> {
 679     type Iter = IntoIter<T>;
 680
 681     fn into_iter(self) -> IntoIter<T> {
 682         self.into_iter()
 683     }
 684 }
 685
 686 impl<'a, T> IntoIterator for &'a VecMap<T> {
 687     type Iter = Iter<'a, T>;
 688
 689     fn into_iter(self) -> Iter<'a, T> {
 690         self.iter()
 691     }
 692 }
 693
 694 impl<'a, T> IntoIterator for &'a mut VecMap<T> {
 695     type Iter = IterMut<'a, T>;
 696
 697     fn into_iter(mut self) -> IterMut<'a, T> {
 698         self.iter_mut()
 699     }
 700 }
 701
 702 #[stable(feature = "rust1", since = "1.0.0")]
 703 impl<V> Extend<(usize, V)> for VecMap<V> {
 704     fn extend<Iter: Iterator<Item=(usize, V)>>(&mut self, iter: Iter) {
 705         for (k, v) in iter {
 706             self.insert(k, v);
 707         }
 708     }
 709 }
 710
 711 impl<V> Index<usize> for VecMap<V> {
 712     type Output = V;
 713
 714     #[inline]
 715     fn index<'a>(&'a self, i: &usize) -> &'a V {
 716         self.get(i).expect("key not present")
 717     }
 718 }
 719
 720 #[stable(feature = "rust1", since = "1.0.0")]
 721 impl<V> IndexMut<usize> for VecMap<V> {
 722     type Output = V;
 723
 724     #[inline]
 725     fn index_mut<'a>(&'a mut self, i: &usize) -> &'a mut V {
 726         self.get_mut(i).expect("key not present")
 727     }
 728 }
 729
 730 macro_rules! iterator {
 731     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 732         #[stable(feature = "rust1", since = "1.0.0")]
 733         impl<'a, V> Iterator for $name<'a, V> {
 734             type Item = $elem;
 735
 736             #[inline]
 737             fn next(&mut self) -> Option<$elem> {
 738                 while self.front < self.back {
 739                     match self.iter.next() {
 740                         Some(elem) => {
 741                             match elem$(. $getter ())+ {
 742                                 Some(x) => {
 743                                     let index = self.front;
 744                                     self.front += 1;
 745                                     return Some((index, x));
 746                                 },
 747                                 None => {},
 748                             }
 749                         }
 750                         _ => ()
 751                     }
 752                     self.front += 1;
 753                 }
 754                 None
 755             }
 756
 757             #[inline]
 758             fn size_hint(&self) -> (usize, Option<usize>) {
 759                 (0, Some(self.back - self.front))
 760             }
 761         }
 762     }
 763 }
 764
 765 macro_rules! double_ended_iterator {
 766     (impl $name:ident -> $elem:ty, $($getter:ident),+) => {
 767         #[stable(feature = "rust1", since = "1.0.0")]
 768         impl<'a, V> DoubleEndedIterator for $name<'a, V> {
 769             #[inline]
 770             fn next_back(&mut self) -> Option<$elem> {
 771                 while self.front < self.back {
 772                     match self.iter.next_back() {
 773                         Some(elem) => {
 774                             match elem$(. $getter ())+ {
 775                                 Some(x) => {
 776                                     self.back -= 1;
 777                                     return Some((self.back, x));
 778                                 },
 779                                 None => {},
 780                             }
 781                         }
 782                         _ => ()
 783                     }
 784                     self.back -= 1;
 785                 }
 786                 None
 787             }
 788         }
 789     }
 790 }
 791
 792 /// An iterator over the key-value pairs of a map.
 793 #[stable(feature = "rust1", since = "1.0.0")]
 794 pub struct Iter<'a, V:'a> {
 795     front: usize,
 796     back: usize,
 797     iter: slice::Iter<'a, Option<V>>
 798 }
 799
 800 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 801 impl<'a, V> Clone for Iter<'a, V> {
 802     fn clone(&self) -> Iter<'a, V> {
 803         Iter {
 804             front: self.front,
 805             back: self.back,
 806             iter: self.iter.clone()
 807         }
 808     }
 809 }
 810
 811 iterator! { impl Iter -> (usize, &'a V), as_ref }
 812 double_ended_iterator! { impl Iter -> (usize, &'a V), as_ref }
 813
 814 /// An iterator over the key-value pairs of a map, with the
 815 /// values being mutable.
 816 #[stable(feature = "rust1", since = "1.0.0")]
 817 pub struct IterMut<'a, V:'a> {
 818     front: usize,
 819     back: usize,
 820     iter: slice::IterMut<'a, Option<V>>
 821 }
 822
 823 iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
 824 double_ended_iterator! { impl IterMut -> (usize, &'a mut V), as_mut }
 825
 826 /// An iterator over the keys of a map.
 827 #[stable(feature = "rust1", since = "1.0.0")]
 828 pub struct Keys<'a, V: 'a> {
 829     iter: Map<Iter<'a, V>, fn((usize, &'a V)) -> usize>
 830 }
 831
 832 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 833 impl<'a, V> Clone for Keys<'a, V> {
 834     fn clone(&self) -> Keys<'a, V> {
 835         Keys {
 836             iter: self.iter.clone()
 837         }
 838     }
 839 }
 840
 841 /// An iterator over the values of a map.
 842 #[stable(feature = "rust1", since = "1.0.0")]
 843 pub struct Values<'a, V: 'a> {
 844     iter: Map<Iter<'a, V>, fn((usize, &'a V)) -> &'a V>
 845 }
 846
 847 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 848 impl<'a, V> Clone for Values<'a, V> {
 849     fn clone(&self) -> Values<'a, V> {
 850         Values {
 851             iter: self.iter.clone()
 852         }
 853     }
 854 }
 855
 856 /// A consuming iterator over the key-value pairs of a map.
 857 #[stable(feature = "rust1", since = "1.0.0")]
 858 pub struct IntoIter<V> {
 859     iter: FilterMap<
 860     Enumerate<vec::IntoIter<Option<V>>>,
 861     fn((usize, Option<V>)) -> Option<(usize, V)>>
 862 }
 863
 864 #[unstable(feature = "collections")]
 865 pub struct Drain<'a, V> {
 866     iter: FilterMap<
 867     Enumerate<vec::Drain<'a, Option<V>>>,
 868     fn((usize, Option<V>)) -> Option<(usize, V)>>
 869 }
 870
 871 #[unstable(feature = "collections")]
 872 impl<'a, V> Iterator for Drain<'a, V> {
 873     type Item = (usize, V);
 874
 875     fn next(&mut self) -> Option<(usize, V)> { self.iter.next() }
 876     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 877 }
 878
 879 #[unstable(feature = "collections")]
 880 impl<'a, V> DoubleEndedIterator for Drain<'a, V> {
 881     fn next_back(&mut self) -> Option<(usize, V)> { self.iter.next_back() }
 882 }
 883
 884 #[stable(feature = "rust1", since = "1.0.0")]
 885 impl<'a, V> Iterator for Keys<'a, V> {
 886     type Item = usize;
 887
 888     fn next(&mut self) -> Option<usize> { self.iter.next() }
 889     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 890 }
 891 #[stable(feature = "rust1", since = "1.0.0")]
 892 impl<'a, V> DoubleEndedIterator for Keys<'a, V> {
 893     fn next_back(&mut self) -> Option<usize> { self.iter.next_back() }
 894 }
 895
 896 #[stable(feature = "rust1", since = "1.0.0")]
 897 impl<'a, V> Iterator for Values<'a, V> {
 898     type Item = &'a V;
 899
 900     fn next(&mut self) -> Option<(&'a V)> { self.iter.next() }
 901     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 902 }
 903 #[stable(feature = "rust1", since = "1.0.0")]
 904 impl<'a, V> DoubleEndedIterator for Values<'a, V> {
 905     fn next_back(&mut self) -> Option<(&'a V)> { self.iter.next_back() }
 906 }
 907
 908 #[stable(feature = "rust1", since = "1.0.0")]
 909 impl<V> Iterator for IntoIter<V> {
 910     type Item = (usize, V);
 911
 912     fn next(&mut self) -> Option<(usize, V)> { self.iter.next() }
 913     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 914 }
 915 #[stable(feature = "rust1", since = "1.0.0")]
 916 impl<V> DoubleEndedIterator for IntoIter<V> {
 917     fn next_back(&mut self) -> Option<(usize, V)> { self.iter.next_back() }
 918 }
 919
 920 #[cfg(test)]
 921 mod test_map {
 922     use prelude::*;
 923     use core::hash::{hash, SipHasher};
 924
 925     use super::{VecMap, Occupied, Vacant};
 926
 927     #[test]
 928     fn test_get_mut() {
 929         let mut m = VecMap::new();
 930         assert!(m.insert(1, 12).is_none());
 931         assert!(m.insert(2, 8).is_none());
 932         assert!(m.insert(5, 14).is_none());
 933         let new = 100;
 934         match m.get_mut(&5) {
 935             None => panic!(), Some(x) => *x = new
 936         }
 937         assert_eq!(m.get(&5), Some(&new));
 938     }
 939
 940     #[test]
 941     fn test_len() {
 942         let mut map = VecMap::new();
 943         assert_eq!(map.len(), 0);
 944         assert!(map.is_empty());
 945         assert!(map.insert(5, 20).is_none());
 946         assert_eq!(map.len(), 1);
 947         assert!(!map.is_empty());
 948         assert!(map.insert(11, 12).is_none());
 949         assert_eq!(map.len(), 2);
 950         assert!(!map.is_empty());
 951         assert!(map.insert(14, 22).is_none());
 952         assert_eq!(map.len(), 3);
 953         assert!(!map.is_empty());
 954     }
 955
 956     #[test]
 957     fn test_clear() {
 958         let mut map = VecMap::new();
 959         assert!(map.insert(5, 20).is_none());
 960         assert!(map.insert(11, 12).is_none());
 961         assert!(map.insert(14, 22).is_none());
 962         map.clear();
 963         assert!(map.is_empty());
 964         assert!(map.get(&5).is_none());
 965         assert!(map.get(&11).is_none());
 966         assert!(map.get(&14).is_none());
 967     }
 968
 969     #[test]
 970     fn test_insert() {
 971         let mut m = VecMap::new();
 972         assert_eq!(m.insert(1, 2), None);
 973         assert_eq!(m.insert(1, 3), Some(2));
 974         assert_eq!(m.insert(1, 4), Some(3));
 975     }
 976
 977     #[test]
 978     fn test_remove() {
 979         let mut m = VecMap::new();
 980         m.insert(1, 2);
 981         assert_eq!(m.remove(&1), Some(2));
 982         assert_eq!(m.remove(&1), None);
 983     }
 984
 985     #[test]
 986     fn test_keys() {
 987         let mut map = VecMap::new();
 988         map.insert(1, 'a');
 989         map.insert(2, 'b');
 990         map.insert(3, 'c');
 991         let keys: Vec<_> = map.keys().collect();
 992         assert_eq!(keys.len(), 3);
 993         assert!(keys.contains(&1));
 994         assert!(keys.contains(&2));
 995         assert!(keys.contains(&3));
 996     }
 997
 998     #[test]
 999     fn test_values() {
1000         let mut map = VecMap::new();
1001         map.insert(1, 'a');
1002         map.insert(2, 'b');
1003         map.insert(3, 'c');
1004         let values: Vec<_> = map.values().cloned().collect();
1005         assert_eq!(values.len(), 3);
1006         assert!(values.contains(&'a'));
1007         assert!(values.contains(&'b'));
1008         assert!(values.contains(&'c'));
1009     }
1010
1011     #[test]
1012     fn test_iterator() {
1013         let mut m = VecMap::new();
1014
1015         assert!(m.insert(0, 1).is_none());
1016         assert!(m.insert(1, 2).is_none());
1017         assert!(m.insert(3, 5).is_none());
1018         assert!(m.insert(6, 10).is_none());
1019         assert!(m.insert(10, 11).is_none());
1020
1021         let mut it = m.iter();
1022         assert_eq!(it.size_hint(), (0, Some(11)));
1023         assert_eq!(it.next().unwrap(), (0, &1));
1024         assert_eq!(it.size_hint(), (0, Some(10)));
1025         assert_eq!(it.next().unwrap(), (1, &2));
1026         assert_eq!(it.size_hint(), (0, Some(9)));
1027         assert_eq!(it.next().unwrap(), (3, &5));
1028         assert_eq!(it.size_hint(), (0, Some(7)));
1029         assert_eq!(it.next().unwrap(), (6, &10));
1030         assert_eq!(it.size_hint(), (0, Some(4)));
1031         assert_eq!(it.next().unwrap(), (10, &11));
1032         assert_eq!(it.size_hint(), (0, Some(0)));
1033         assert!(it.next().is_none());
1034     }
1035
1036     #[test]
1037     fn test_iterator_size_hints() {
1038         let mut m = VecMap::new();
1039
1040         assert!(m.insert(0, 1).is_none());
1041         assert!(m.insert(1, 2).is_none());
1042         assert!(m.insert(3, 5).is_none());
1043         assert!(m.insert(6, 10).is_none());
1044         assert!(m.insert(10, 11).is_none());
1045
1046         assert_eq!(m.iter().size_hint(), (0, Some(11)));
1047         assert_eq!(m.iter().rev().size_hint(), (0, Some(11)));
1048         assert_eq!(m.iter_mut().size_hint(), (0, Some(11)));
1049         assert_eq!(m.iter_mut().rev().size_hint(), (0, Some(11)));
1050     }
1051
1052     #[test]
1053     fn test_mut_iterator() {
1054         let mut m = VecMap::new();
1055
1056         assert!(m.insert(0, 1).is_none());
1057         assert!(m.insert(1, 2).is_none());
1058         assert!(m.insert(3, 5).is_none());
1059         assert!(m.insert(6, 10).is_none());
1060         assert!(m.insert(10, 11).is_none());
1061
1062         for (k, v) in &mut m {
1063             *v += k as int;
1064         }
1065
1066         let mut it = m.iter();
1067         assert_eq!(it.next().unwrap(), (0, &1));
1068         assert_eq!(it.next().unwrap(), (1, &3));
1069         assert_eq!(it.next().unwrap(), (3, &8));
1070         assert_eq!(it.next().unwrap(), (6, &16));
1071         assert_eq!(it.next().unwrap(), (10, &21));
1072         assert!(it.next().is_none());
1073     }
1074
1075     #[test]
1076     fn test_rev_iterator() {
1077         let mut m = VecMap::new();
1078
1079         assert!(m.insert(0, 1).is_none());
1080         assert!(m.insert(1, 2).is_none());
1081         assert!(m.insert(3, 5).is_none());
1082         assert!(m.insert(6, 10).is_none());
1083         assert!(m.insert(10, 11).is_none());
1084
1085         let mut it = m.iter().rev();
1086         assert_eq!(it.next().unwrap(), (10, &11));
1087         assert_eq!(it.next().unwrap(), (6, &10));
1088         assert_eq!(it.next().unwrap(), (3, &5));
1089         assert_eq!(it.next().unwrap(), (1, &2));
1090         assert_eq!(it.next().unwrap(), (0, &1));
1091         assert!(it.next().is_none());
1092     }
1093
1094     #[test]
1095     fn test_mut_rev_iterator() {
1096         let mut m = VecMap::new();
1097
1098         assert!(m.insert(0, 1).is_none());
1099         assert!(m.insert(1, 2).is_none());
1100         assert!(m.insert(3, 5).is_none());
1101         assert!(m.insert(6, 10).is_none());
1102         assert!(m.insert(10, 11).is_none());
1103
1104         for (k, v) in m.iter_mut().rev() {
1105             *v += k as int;
1106         }
1107
1108         let mut it = m.iter();
1109         assert_eq!(it.next().unwrap(), (0, &1));
1110         assert_eq!(it.next().unwrap(), (1, &3));
1111         assert_eq!(it.next().unwrap(), (3, &8));
1112         assert_eq!(it.next().unwrap(), (6, &16));
1113         assert_eq!(it.next().unwrap(), (10, &21));
1114         assert!(it.next().is_none());
1115     }
1116
1117     #[test]
1118     fn test_move_iter() {
1119         let mut m = VecMap::new();
1120         m.insert(1, box 2);
1121         let mut called = false;
1122         for (k, v) in m {
1123             assert!(!called);
1124             called = true;
1125             assert_eq!(k, 1);
1126             assert_eq!(v, box 2);
1127         }
1128         assert!(called);
1129     }
1130
1131     #[test]
1132     fn test_drain_iterator() {
1133         let mut map = VecMap::new();
1134         map.insert(1, "a");
1135         map.insert(3, "c");
1136         map.insert(2, "b");
1137
1138         let vec: Vec<_> = map.drain().collect();
1139
1140         assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]);
1141         assert_eq!(map.len(), 0);
1142     }
1143
1144     #[test]
1145     fn test_show() {
1146         let mut map = VecMap::new();
1147         let empty = VecMap::<i32>::new();
1148
1149         map.insert(1, 2);
1150         map.insert(3, 4);
1151
1152         let map_str = format!("{:?}", map);
1153         assert!(map_str == "VecMap {1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
1154         assert_eq!(format!("{:?}", empty), "VecMap {}");
1155     }
1156
1157     #[test]
1158     fn test_clone() {
1159         let mut a = VecMap::new();
1160
1161         a.insert(1, 'x');
1162         a.insert(4, 'y');
1163         a.insert(6, 'z');
1164
1165         assert!(a.clone() == a);
1166     }
1167
1168     #[test]
1169     fn test_eq() {
1170         let mut a = VecMap::new();
1171         let mut b = VecMap::new();
1172
1173         assert!(a == b);
1174         assert!(a.insert(0, 5).is_none());
1175         assert!(a != b);
1176         assert!(b.insert(0, 4).is_none());
1177         assert!(a != b);
1178         assert!(a.insert(5, 19).is_none());
1179         assert!(a != b);
1180         assert!(!b.insert(0, 5).is_none());
1181         assert!(a != b);
1182         assert!(b.insert(5, 19).is_none());
1183         assert!(a == b);
1184
1185         a = VecMap::new();
1186         b = VecMap::with_capacity(1);
1187         assert!(a == b);
1188     }
1189
1190     #[test]
1191     fn test_lt() {
1192         let mut a = VecMap::new();
1193         let mut b = VecMap::new();
1194
1195         assert!(!(a < b) && !(b < a));
1196         assert!(b.insert(2, 5).is_none());
1197         assert!(a < b);
1198         assert!(a.insert(2, 7).is_none());
1199         assert!(!(a < b) && b < a);
1200         assert!(b.insert(1, 0).is_none());
1201         assert!(b < a);
1202         assert!(a.insert(0, 6).is_none());
1203         assert!(a < b);
1204         assert!(a.insert(6, 2).is_none());
1205         assert!(a < b && !(b < a));
1206     }
1207
1208     #[test]
1209     fn test_ord() {
1210         let mut a = VecMap::new();
1211         let mut b = VecMap::new();
1212
1213         assert!(a <= b && a >= b);
1214         assert!(a.insert(1, 1).is_none());
1215         assert!(a > b && a >= b);
1216         assert!(b < a && b <= a);
1217         assert!(b.insert(2, 2).is_none());
1218         assert!(b > a && b >= a);
1219         assert!(a < b && a <= b);
1220     }
1221
1222     #[test]
1223     fn test_hash() {
1224         let mut x = VecMap::new();
1225         let mut y = VecMap::new();
1226
1227         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1228         x.insert(1, 'a');
1229         x.insert(2, 'b');
1230         x.insert(3, 'c');
1231
1232         y.insert(3, 'c');
1233         y.insert(2, 'b');
1234         y.insert(1, 'a');
1235
1236         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1237
1238         x.insert(1000, 'd');
1239         x.remove(&1000);
1240
1241         assert!(hash::<_, SipHasher>(&x) == hash::<_, SipHasher>(&y));
1242     }
1243
1244     #[test]
1245     fn test_from_iter() {
1246         let xs = vec![(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e')];
1247
1248         let map: VecMap<_> = xs.iter().cloned().collect();
1249
1250         for &(k, v) in &xs {
1251             assert_eq!(map.get(&k), Some(&v));
1252         }
1253     }
1254
1255     #[test]
1256     fn test_index() {
1257         let mut map = VecMap::new();
1258
1259         map.insert(1, 2);
1260         map.insert(2, 1);
1261         map.insert(3, 4);
1262
1263         assert_eq!(map[3], 4);
1264     }
1265
1266     #[test]
1267     #[should_fail]
1268     fn test_index_nonexistent() {
1269         let mut map = VecMap::new();
1270
1271         map.insert(1, 2);
1272         map.insert(2, 1);
1273         map.insert(3, 4);
1274
1275         map[4];
1276     }
1277
1278     #[test]
1279     fn test_entry(){
1280         let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1281
1282         let mut map: VecMap<_> = xs.iter().cloned().collect();
1283
1284         // Existing key (insert)
1285         match map.entry(1) {
1286             Vacant(_) => unreachable!(),
1287             Occupied(mut view) => {
1288                 assert_eq!(view.get(), &10);
1289                 assert_eq!(view.insert(100), 10);
1290             }
1291         }
1292         assert_eq!(map.get(&1).unwrap(), &100);
1293         assert_eq!(map.len(), 6);
1294
1295
1296         // Existing key (update)
1297         match map.entry(2) {
1298             Vacant(_) => unreachable!(),
1299             Occupied(mut view) => {
1300                 let v = view.get_mut();
1301                 *v *= 10;
1302             }
1303         }
1304         assert_eq!(map.get(&2).unwrap(), &200);
1305         assert_eq!(map.len(), 6);
1306
1307         // Existing key (take)
1308         match map.entry(3) {
1309             Vacant(_) => unreachable!(),
1310             Occupied(view) => {
1311                 assert_eq!(view.remove(), 30);
1312             }
1313         }
1314         assert_eq!(map.get(&3), None);
1315         assert_eq!(map.len(), 5);
1316
1317
1318         // Inexistent key (insert)
1319         match map.entry(10) {
1320             Occupied(_) => unreachable!(),
1321             Vacant(view) => {
1322                 assert_eq!(*view.insert(1000), 1000);
1323             }
1324         }
1325         assert_eq!(map.get(&10).unwrap(), &1000);
1326         assert_eq!(map.len(), 6);
1327     }
1328 }
1329
1330 #[cfg(test)]
1331 mod bench {
1332     use test::Bencher;
1333     use super::VecMap;
1334     use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
1335
1336     #[bench]
1337     pub fn insert_rand_100(b: &mut Bencher) {
1338         let mut m = VecMap::new();
1339         insert_rand_n(100, &mut m, b,
1340                       |m, i| { m.insert(i, 1); },
1341                       |m, i| { m.remove(&i); });
1342     }
1343
1344     #[bench]
1345     pub fn insert_rand_10_000(b: &mut Bencher) {
1346         let mut m = VecMap::new();
1347         insert_rand_n(10_000, &mut m, b,
1348                       |m, i| { m.insert(i, 1); },
1349                       |m, i| { m.remove(&i); });
1350     }
1351
1352     // Insert seq
1353     #[bench]
1354     pub fn insert_seq_100(b: &mut Bencher) {
1355         let mut m = VecMap::new();
1356         insert_seq_n(100, &mut m, b,
1357                      |m, i| { m.insert(i, 1); },
1358                      |m, i| { m.remove(&i); });
1359     }
1360
1361     #[bench]
1362     pub fn insert_seq_10_000(b: &mut Bencher) {
1363         let mut m = VecMap::new();
1364         insert_seq_n(10_000, &mut m, b,
1365                      |m, i| { m.insert(i, 1); },
1366                      |m, i| { m.remove(&i); });
1367     }
1368
1369     // Find rand
1370     #[bench]
1371     pub fn find_rand_100(b: &mut Bencher) {
1372         let mut m = VecMap::new();
1373         find_rand_n(100, &mut m, b,
1374                     |m, i| { m.insert(i, 1); },
1375                     |m, i| { m.get(&i); });
1376     }
1377
1378     #[bench]
1379     pub fn find_rand_10_000(b: &mut Bencher) {
1380         let mut m = VecMap::new();
1381         find_rand_n(10_000, &mut m, b,
1382                     |m, i| { m.insert(i, 1); },
1383                     |m, i| { m.get(&i); });
1384     }
1385
1386     // Find seq
1387     #[bench]
1388     pub fn find_seq_100(b: &mut Bencher) {
1389         let mut m = VecMap::new();
1390         find_seq_n(100, &mut m, b,
1391                    |m, i| { m.insert(i, 1); },
1392                    |m, i| { m.get(&i); });
1393     }
1394
1395     #[bench]
1396     pub fn find_seq_10_000(b: &mut Bencher) {
1397         let mut m = VecMap::new();
1398         find_seq_n(10_000, &mut m, b,
1399                    |m, i| { m.insert(i, 1); },
1400                    |m, i| { m.get(&i); });
1401     }
1402 }