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