[boost] [containers] Vector-like container, which takes O(log(N)) > for insert/erase, question to Adam Wulkiewicz about iterators

Subject: [boost] [containers] Vector-like container, which takes O(log(N)) > for insert/erase, question to Adam Wulkiewicz about iterators
From: Alexander Kuprijanov (alexkupri_at_[hidden])
Date: 2014-04-06 08:40:00

Hi, again, Adam!

>
> Date: Sat, 05 Apr 2014 16:59:18 +0200
> From: Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]>

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

Vector outperforms it only (roughly) 2 times on small arrays (when it 
contains only one leaf) on all operations, only (roughly) 3 times on 
iterating access on all sizes and only log(N) times on random access. 
But it severely (N/log(N)) outperforms vector in all insert/erase cases. 
See my explained test results. I still believe it's close to first choise.

> 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()?

That is very interesting question. Currently such sort of persistent 
iterators (I call them bookmarks) are not implemented.

PLEASE PLEASE PLEASE, EVERYBODY, give me an example of the task when 
such iterators are necessary. Will this feature add feature to my 
container, if implemented?

Best regards,
A.K.