DefaultVecMap class with benchmark

vec_map_bench.rs

#![feature(test, rand)]

/// benchmarks for different map implementation
extern crate test;
extern crate rand;

use test::Bencher;
use rand::Rng;
use std::mem::replace;

#[bench]
fn empty(b: &mut Bencher) {
    b.iter(|| ())
}

#[bench]
fn setup_random_hashmap(b: &mut Bencher) {
    let mut val : u32 = 0;
    let mut rng = rand::IsaacRng::new_unseeded();
    let mut map = std::collections::HashMap::new();

    b.iter(|| { map.insert(rng.gen::<u8>() as usize, val); val += 1; })
}

#[bench]
fn setup_random_vecmap(b: &mut Bencher) {
    let mut val : u32 = 0;
    let mut rng = rand::IsaacRng::new_unseeded();
    let mut map = std::collections::VecMap::new();

    b.iter(|| { map.insert((rng.gen::<u8>()) as usize, val); val += 1; })
}

#[bench]
fn setup_random_vecmap_cap(b: &mut Bencher) {
    let mut val : u32 = 0;
    let mut rng = rand::IsaacRng::new_unseeded();
    let mut map = std::collections::VecMap::with_capacity(256);

    b.iter(|| { map.insert((rng.gen::<u8>()) as usize, val); val += 1; })
}

#[bench]
fn setup_default_vecmap(b: &mut Bencher) {
    let mut val : u32 = 0;
    let mut rng = rand::IsaacRng::new_unseeded();
    let mut map = DefaultVecMap::new(std::u32::MAX);

    b.iter(|| { map.insert((rng.gen::<u8>()) as usize, val); val += 1; })
}

#[bench]
fn setup_default_vecmap_cap(b: &mut Bencher) {
    let mut val : u32 = 0;
    let mut rng = rand::IsaacRng::new_unseeded();
    let mut map = DefaultVecMap::with_capacity(std::u32::MAX, 256);

    b.iter(|| { map.insert((rng.gen::<u8>()) as usize, val); val += 1; })
}

#[derive(Clone)]
pub struct DefaultVecMap<V: PartialEq<V>> {
	default: V,
    v: Vec<V>,
}

impl<V: PartialEq<V> + Clone> DefaultVecMap<V> {
	pub fn new(default: V) -> DefaultVecMap<V> {
		DefaultVecMap { default: default, v: vec![], }
	}

	pub fn with_capacity(default: V, capacity: usize) -> DefaultVecMap<V> {
        DefaultVecMap { default: default, v: Vec::with_capacity(capacity), }
    }

	pub fn capacity(&self) -> usize { self.v.capacity() }

	pub fn clear(&mut self) {
		self.v.clear();
	}

	pub fn get(&self, key: &usize) -> Option<&V> {
		if *key < self.v.len() {
			let value = &self.v[*key];
			if value != &self.default {
				Some(&self.v[*key])
			} else {
				None
			}
		} else { None }
	}

	pub fn reserve_len(&mut self, len: usize) {
		let cur_len = self.v.len();
        if len >= cur_len {
            self.v.reserve(len - cur_len);
        }
	}

	pub fn reserve_len_exact(&mut self, len: usize) {
		let cur_len = self.v.len();
        if len >= cur_len {
            self.v.reserve_exact(len - cur_len);
        }
	}

	pub fn insert(&mut self, key: usize, value: V) -> Option<V> {
		debug_assert!(&value != &self.default);
		let len = self.v.len();
		if len <= key {
			let default = &self.default;
			self.v.extend((0..key - len + 1).map(|_| default.clone()));
			None
		} else {
			let old_value = replace(&mut self.v[key], value);
			if old_value == self.default { None } else { Some(old_value) }
		}
	}
}