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. For example, when
the n elements is in a list already, and this list is linked into
another list.
Lists can be very nice for cut&paste.
Helge Hafting
