Crate mapped_vec

Source
Expand description

This crate is meant to provide an interface for vectors that not only store data, but also its order. This type of vector is called a mapped vector. A mapped vector is suitable for the fast processing of large types, because in the case of large types, it’s faster to move around a few numbers specifying the order of the data than to move around the actual data. The reverse and rotate functions of a mapped vector are O(1), because the reverse function simply changes the function to filter indices with, and the rotate function only has to edit a number offset for each index and possibly swap a few functions. Inserts and removes are also generally faster with this, even for small types. A mapped vector also supports turning into a regular vector, although this can be expensive, so it’s recommended to use the get_mapped method to get a vector of references to elements in order instead. This works on no_std with alloc.

Example Usage with Random Numbers and Timed Functions:

§use mapped_vec::MappedVec;

§use rand::prelude::*;

§

§fn main() {

§let mut rng = rand::thread_rng();

§let mut rgen = (0..100_000).map(|_| rng.gen::()).collect::<Vec>();

§

§let mut mapped = MappedVec::new();

§mapped.extend_from_slice(&rgen);

§

§let ind = rng.gen::() as usize;

§

§let timed = std::time::Instant::now();

§mapped.remove(ind);

§println!(“Remove of mapped vector: {:?}”, timed.elapsed());

§

§let timed = std::time::Instant::now();

§rgen.remove(ind);

§println!(“Remove of regular vector: {:?}”, timed.elapsed());

§

§let timed = std::time::Instant::now();

§mapped.insert(ind, 0.0);

§println!(“Insert of mapped vector: {:?}”, timed.elapsed());

§

§let timed = std::time::Instant::now();

§rgen.insert(ind, 0.0);

§println!(“Insert of regular vector: {:?}”, timed.elapsed());

§

§let timed = std::time::Instant::now();

§mapped.reverse();

§println!(“Time to reverse mapped vector: {:?}”, timed.elapsed());

§

§let timed = std::time::Instant::now();

§rgen.reverse();

§println!(“Time to reverse regular vector: {:?}”, timed.elapsed());

§

§let timed = std::time::Instant::now();

§let rvec = mapped.to_vec();

§println!(“Time to convert mapped vector to real vector: {:?}”, timed.elapsed());

§

§assert_eq!(rvec, rgen);

§}

Structs§

  • See the crate-level documentation for the description of this structure, which is all of the public API in this crate, as well as the method documentation for more info.