#mapped #order #data #vec #vector #store #indices

mapped_vec

A crate for a vector that not only stores it's data but also it's order

1 unstable release

0.1.1 Aug 30, 2020
0.1.0 Aug 30, 2020

#7 in #mapped

MIT license

13KB
245 lines

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);

}

No runtime deps