contain-rs / vec-map Goto Github PK

Not sure if this was intentional, but the nightly Travis build generates the docs without the nightly features enabled:

    - cargo doc --no-deps
after_success: |
    [ "$TRAVIS_RUST_VERSION" = nightly ] &&

I don't know if we want to host the stable docs or the nightly docs, but the configuration should be changed to the following, regardless:

    - cargo doc --no-deps $FEATURES

I would like to add the methods get_or_insert and get_or_insert_with, but this crate won't accept PRs it says. Is there a more maintained fork?

It would be useful to have a maplit-like macro for VecMap, similar to this:
https://github.com/bluss/maplit/blob/master/src/lib.rs#L47-L62

The maplit crate only covers the Map types in std, so it would make sense to have the macro in this crate.

macro_rules! vec_map {
	(@single $($x:tt)*) => (());
	(@count $($rest:expr),*) => (<[()]>::len(&[$(vec_map!(@single $rest)),*]));

	($($key:expr => $value:expr,)+) => { vec_map!($($key => $value),+) };
	($($key:expr => $value:expr),*) => {
		{
			let _cap = vec_map!(@count $($key),*);
			let mut _map = ::vec_map::VecMap::with_capacity(_cap);
			$(
				_map.insert($key, $value);
			)*
			_map
		}
	};
}

The url (https://contain-rs.github.io/vec-map/vec_map) provided in the Readme produces a 404 error since the gh-pages branch with the documentation doesn't exist.

Instead of using options, consider storing a full/empty bit-vector (backed by a RawVec for storing the actual values).

1. This takes less space when the null pointer optimization doesn't apply.
2. It allows for faster cache friendly iteration over reasonably sparse vec-maps.

Hi, I have a compile problem with rustc nightly: rustc 1.12.0-nightly (197be89f3 2016-08-15).

error[E0308]: mismatched types
   --> /home/sfr/.cargo/registry/src/github.com-1ecc6299db9ec823/vec_map-0.6.0/src/lib.rs:952:84
    |
952 |     fn into_iter_covariant<'a, T>(iter: IntoIter<&'static T>) -> IntoIter<&'a T> { iter }
    |                                                                                    ^^^^ lifetime mismatch
    |
    = note: expected type `IntoIter<&'a T>`
    = note:    found type `IntoIter<&'static T>`
note: the lifetime 'a as defined on the block at 952:81...
   --> /home/sfr/.cargo/registry/src/github.com-1ecc6299db9ec823/vec_map-0.6.0/src/lib.rs:952:82
    |
952 |     fn into_iter_covariant<'a, T>(iter: IntoIter<&'static T>) -> IntoIter<&'a T> { iter }
    |                                                                                  ^^^^^^^^
    = note: ...does not necessarily outlive the static lifetime

error: aborting due to previous error

Build failed, waiting for other jobs to finish...
error: Could not compile `vec_map`.

I want to bring up an item for discussion: should VecMap be changed to include a list of free indices?

I have been trying to look at users of VecMap to see how much usage of VecMap actually cares about the value of the key (https://crates.io/crates/vec_map/reverse_dependencies). But that only shows other libraries, not applications. It was not a very good data set in general. So from my side this reflection is only based on technical details and other reasoning, not actual data on current usage.

I suggest an implementation based on changing

pub struct VecMap<V> {
    v: Vec<Option<V>>,
}

to

#[derive(Clone)]
enum VecMapSlot<V> {
    Taken(V),
    Free(usize),
}
pub struct VecMap<V> {
    v: Vec<VecMapSlot<V>>,
    first_free: usize,
}

Where the list of free indices is stored as a linked list in the free slots themselves. Would also add a method that inserts new value at first available slot:

pub fn add(&mut self, value: V) -> usize

So... pros and cons...
Pro:

• For users who don't care about the key (any key will do, just used as a unique ID to later retrieve Value, for example a general graph structure based on VecMap) it is much nicer not to have to find or write your own list to keep track of free slots, store that as a variable along side the VecMap and making sure to keep it up to date in all places the VecMap is modified.
• By storing the list of free indices inside the VecMap itself it makes for both memory and cpu-efficient implementation. Can be zero extra memory requirement in some cases (depending on the type of V)

Con:

• For some types of V, this will make each slot of the Vec take more space. It seems to be only when size_of V is smaller than usize, or when V contains a pointer in which case rustc is smart enough to have zero overhead for Option (by using null pointer value as None I think). Using u32 indices in the Free slots could be one acceptable option to save space on 64 bit ISAs, I think... If this really is a concern at all.
  • Small added processing overhead on insert() because if the requested slot was free we need to traverse the free-list from start in order to find the preceding slot (not a double-linked list...)

I have already a proof of concept implementation which I am willing to submit PR for.

Of course, one other option is also to create a seperate struct in contain-rs (VecMap2 hehehe) to do this instead. Or perhaps say that it is so unlikely to be useful that it does not even belong in contain-rs at all. Discuss! :)

This method is missing.

Currently, VecMap::len() takes O(highest index) time to compute every time (same goes for VecMap::is_empty(). It'd be nice if VecMap instead kept track of the number of Some it has, and just use this value in len() and is_empty(). It would add a usize to the VecMap struct, but this seems negligible compared to the performance gains of doing so. I'll submit a PR shortly which you can merge if you feel like this would be a useful addition :)

Hi,

I'm getting a build error for vec_map 0.6:
https://travis-ci.org/dan-t/rusty-tags/builds/153615676

It's a bit irritating that I'm getting the error only for the current
rustc beta, but not for the stable and the nightly.

Any ideas?

Greetings,
Daniel

Why does the get function (amongst others) take a pointer to usize, as opposed to just a usize?

https://github.com/contain-rs/vec-map/blob/master/src/lib.rs#L433
https://github.com/contain-rs/vec-map/blob/master/src/lib.rs#L457
https://github.com/contain-rs/vec-map/blob/master/src/lib.rs#L475
https://github.com/contain-rs/vec-map/blob/master/src/lib.rs#L475

The underscore is a bit confusing.

vec-map does not seem to use unsafe code, which is very good :)

To prevent this from ever happening, add following line to the top:

#![forbid(unsafe_code)]

of https://github.com/contain-rs/vec-map/blob/master/src/lib.rs

This will make the package green in
https://github.com/rust-secure-code/cargo-geiger

https://serde.rs/serialize-map.html or something similar.

Error:

error[E0308]: mismatched types
   --> [...] /.cargo/registry/src/github.com-1ecc6299db9ec823/vec_map-0.6.0/src/lib.rs:952:84
    |
952 |     fn into_iter_covariant<'a, T>(iter: IntoIter<&'static T>) -> IntoIter<&'a T> { iter }
    |                                                                                    ^^^^ lifetime mismatch
    |
    = note: expected type `IntoIter<&'a T>`
    = note:    found type `IntoIter<&'static T>`
note: the lifetime 'a as defined on the block at 952:81...
   --> [...] /.cargo/registry/src/github.com-1ecc6299db9ec823/vec_map-0.6.0/src/lib.rs:952:82
    |
952 |     fn into_iter_covariant<'a, T>(iter: IntoIter<&'static T>) -> IntoIter<&'a T> { iter }
    |                                                                                  ^^^^^^^^
    = note: ...does not necessarily outlive the static lifetime

error: aborting due to previous error

Build failed, waiting for other jobs to finish...
error: Could not compile `vec_map`.

To learn more, run the command again with --verbose.

Would be nice to start using latest serde, because 0.6.0 is very old, unsupported and has a lot of outdated dependencies.

See here: https://travis-ci.org/matthiasbeyer/imag/jobs/154256610

The serde feature for vec-map is currently counter-intuitively called edres, presumably because of rust-lang/cargo#1286. There is a workaround for this problem in serde itself (https://github.com/serde-rs/serde/blob/v1.0.0/serde/src/lib.rs#L222-L260), whereby you depend on serde with the derive feature, which in turn re-exports derive(Serialize, Deserialize) from serde_derive. This allows the feature of the top-level crate (in this case vec-map) to also be called serde. Or rather, it allows you to not explicitly add a feature called serde, but instead rely on the behavior that optional dependencies are implicitly also features.

VecMap perfectly fits my current use case, except that my integer keys are newtype-wrapped for safety reasons. It'd be really cool if any types that can convert from and into usize could be used. The inner workings need not be changed, and I think the interface can even be extended in a backwards-compatible way if that's desired.