Boost logo

Boost :

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>> writes:

> Hi,
> 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
> holes.
> 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, gregod at, cpdaniel at, john at