Subject: Re: [boost] [container] locking for compact map
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2014-12-09 03:41:43
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
> I'm locking for a map<std::size_t, T> implemented as
> array<optional<T>, N>.
> When the key is on the range 0..N-1 and the map is dense enough, the
> advantages are
> * the whole data is much more compact, avoiding allocations and
> deallocations, and should reduce the cash misses.
> * the access insertion/removal/get is direct O(k) instead of O(logN).
You mean O(1), right?
> The liabilities, are the same as array.
> * iterating is not O(k), but O(N) (When the number of elements is not
> too high or when there is no too much holes, this should not be a problem)
This can pose problems on erasure, as discussed (for unordered associative
containers, but the situation is the same) at
> * The move constructor is not noexcept.
> An implementation using vector<optional<T>> should avoid this last issue.
Or just a pointer to array, which is somewhat more efficient.
> You could ask your self why I don't use directly array<optional<T>> or
> vector<optional<T>>. The answer is that I don't want the user manage the
> I'm aware of/flat_(multi)map/set/ associative containers. The difference
> here is that as the key is the position on the array which make things
> perform even better for this particular case.
> Is there something similar in Boost already that I'm missing?
> Do you see other liabilities I have missed?
I think the O(n) erasure problem mentioned above can be an issue.
JoaquÃn M LÃ³pez MuÃ±oz
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk