[][src]Crate total_order_multi_map

A multi map implementation which also keeps the total order of inserted elements. I.e. if you insert (k1, v1) then (k2, v2) then (k1, v3). The order when iterating over it will be exact this insertion order. Through there is an grouped_values method returning a iterator over the values grouped by key, instead of iteration order.

The map makes sure that normal iteration is roughly as fast a iterating over a vector but using get to get a (group of) values is also roughly as fast as using get on a HashMap. The draw back is that insertion is a bit slower.

Note that this implementation is made for values which dereference to the actually relevant values. It is also temporary limited to values which implement DerefMut, this can be lifted in the future. (I.e. currently Box<T> is supported but Rc<T> can be supported in the future just not for _mut methods). When accessing the map references to the inner values are returned (e.g. with a Box<T> references to &T/&mut T are returned and the Box is not accessible).

Because of implementation details it is required that the value containers implement StableDeref. Note that this multi map can, or more precisely is made to, handle unsized values like trait object or slices.

State of Implementation

Currently a lot of possible and useful methods are missing, take a look at the readme for more details. Through core methods like insert, get, get_mut and multiple iterators are implemented.

Also currently it is limited to StableDeref + DerefMut but this is only needed for _mut methods.


see the example directories from_readme.rs example, which is also present in the README.

Implementation Details

This implementation internally has a Vec and a HashMap. The Vec contains key-value pairs and "owns" the values. It is used for simple iteration and keeps the insertion order. The HashMap is a map from keys to vectors of pointers to inner values. And represents the multi map part. The code makes sure that only pointers are in the hash map iff their "owned" value is in the Vec at any part of execution, even during insertion. This is needed to make sure that this type is unwind safe. Also to make sure that the pointers to the inner values are always valid the values have to implement StableDeref, so even if the vec is moved/resized the pointers stay valid as they don't point into the vec, but to the inner value the value in the vec points to. In turn this also means that mutable references to the containers/values should never be exposed, through mutable references to the inner values can be exposed.

Note that for ease of implementation only Copy keys are allowed, this should be improved on in later versions.



A type providing access to all values associated to "some key"


A type providing mut access to all values associated to "some key"


A iterator over &V::Target values returned by GroupedValues.


A iterator over &mut V::Target values returned by GroupedValues.


An iterator of Groups (no fixed iteration order).


An iterator of Groups (no fixed iteration order).


Iterator over TotalOrderMultimap in insertion order.


Delegate the job of deciding about Send, Sync to rustc (ignore this)


A multi map with keeps the total ordering of inserted elements