Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase, feedback

Subject: Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase, feedback
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-04-05 10:59:18

Hi Alexander,

Please respond one email at a time, otherwise it's hard to follow the 
discussion. See http://www.boost.org/community/policy.html.

Alexander Kuprijanov wrote:
> Hi, everybody!
> The most important feature of my container is performance. However, 
> other features will appear later.
> https://github.com/alexkupri/array/blob/master/description/description.txt 
>
> Today I compared my container with rope. My container outperformed it 
> 10 times.
>

Again, the times you measure are too small to reasonably tell which one 
is faster. You could perform each test 10k more times to keep the 
results around 1s.

Instead of comparing it with a different implementation I guess it would 
be sufficient to contain only 2 children in the internal nodes.

<snip>

>> Message: 9
> From: Lars Viklund <zao_at_[hidden]>
>> Date: Fri, 4 Apr 2014 14:10:06 +0200
>> If it doesn't have contiguous storage, it's not a replacement for
>> vector, however much you want it to be the universal container that
>> everyone uses for everything.
>> It may be a better general-purpose container compared to the
>> usual default containers, deque and vector, but it isn't a replacement
>> for either of them.
> Well, I would see it as first choise container for non-sorted data. 
> It's comparable with vector/deque
> on small arrays and outperforms them on large sizes. It's more 
> preferrable than list at least
> in terms of malloc/free calls. And it's probably better for strings.
> So one should use it by default in all cases with unsorted data and 
> use list, vector, deque and string only
> if he/she really understands what he/she does.

I agree with Lars. Your container shouldn't be seen as a replacement. It 
has different properties, hence it may be useful in some situations but 
not all of them.

And I strongly dissagree with the statement that your container should 
be the first choice. std::vector<> will outperform it in most of the 
real-life use-cases.
Also, IMHO the most important feature of std::list<> is insert() and 
erase() not invalidating other iterators. AFAIU in your container 
iterators may be invalid after insert()?

Regards,
Adam