Crate total_order_multi_map[−][src]
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,
(e.g. Box<T>, Rc<T>, Arc<T>, &T) and when
accessing the map references to the inner values are
returned (e.g. with a Box<T> references to &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 and multiple
iterators are implemented.
Example
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.
Structs
| Entry | |
| EntryValues |
A type providing access to all values associated to "some key" |
| GroupedValues |
an iterator of Groups (no fixed iteration order) |
| Iter | |
| IterMut | |
| Keys | |
| SyncSendHelper |
Delegate the job of deciding about Send, Sync to rustc (ignore this) |
| TotalOrderMultiMap |
A multi map with keeps the total ordering of inserted elements |