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.
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.
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" |
EntryValuesMut |
A type providing mut access to all values associated to "some key" |
GroupedValues |
An iterator of Groups (no fixed iteration order). |
Iter |
Iterator over TotalOrderMultimap in insertion order. |
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 |