Re: [boost] [container] locking for compact map

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:

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

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf

> * 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
Telefónica