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

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