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