Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk