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:
>> 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
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.
>> 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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk