On Fri, Sep 14, 2007 at 03:44:50PM +0200, Helge Hafting wrote: > Alfredo Braunstein wrote: > >>> > >>>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. > > O(n^2) for inserting n elements is pretty bad considering that this > sometimes is doable in O(1) time.
We are talking about vectors containing a maximum of, say, a few hundred _pointers_. O(n) is certainly no problem there (for sensible constants) Andre'
