Boost logo

Boost :

Subject: [boost] [container] locking for compact map
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2014-12-07 11:32:55


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).

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)
* The move constructor is not noexcept.

An implementation using vector<optional<T>> should avoid this last issue.

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?


Boost list run by bdawes at, gregod at, cpdaniel at, john at