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

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

Le 09/12/14 09:41, Joaquin M Lopez Munoz a écrit :
> 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?
yes :)
>
>> 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
I agree for erase with a pointer. However erase with a key is O(1). I 
agree with you having a specific erase function that don't returns the 
iterator avoid this problem, but I would add specific overload.
>
>> * 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.
Why not.
>
>> 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.
>
>
Agreed this is an issue with the functions returning iterators. However, 
as the performances should be better on a lot of other functions, I'm 
wondering if this class could have a wider interest. Adding other erase 
overload would help also.

Best,
Vicente