Oops, sorry Abdel, I forgot to send to the list. > > Why? RandomAccessList::iterator is a std::list::iterator... > > Right but operator[] is fast. There was a fast iterator version once
The code is full std::advance(pit, something) or boost::next(pit, something) that is currently O(n). That's why we started wondering about our container choice... > though but I don't know where it went... Yeah, this is possible (by e.g. storing a reference to the container inside the iterator) > >> insertion as a list"... > > > > We have O(n) insertions/deletions like std::vector, std::list speed is O(1) > > We use vector as the container for list::iterator not for the Paragraph > itself. insertion/deletion of an iterator in a vector is cheap (fixed > size element) so O(n) is OK. Insertion/deletion of a Paragraph is not > cheap, hence the list container choice. This is true, the constant is small. But don't underestimate the change in complexity. Having O(n) insertion means that a loop in which we erase/insert stuff can be O(n^2) if one is not careful. This is not acceptable IMO. > >>> The only problem could be if we assume list-type iterator stability on > >>> insertion. Not many cases (if any) I presume, but hard to catch. > > > > What do you mean, that we need the stability or that it is hard to find > > where we > > use it? > > Both I guess. That being said, I am not religious about that, you can > get rid of it if you find a proper replacement AFAIAC; but I don't think > there is a need to optimize anything here. There is a lot more > inefficient stuff in the source code. This is possibly true. But changes here are easy and potentially affect positively large portions of the code, other optimizations need thinking ;-) Besides, blame JMarc, he started it ;-) A/
