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