Deletion
The deletion performance story is in many ways analogous to insertion. Many of the statements made with regard to insertion efficiency apply equally as well to deletion.[1] For example:
[1] You can find those and many more performance guarantees in [MS96]. It contains complexity guarantees for all containers and generic algorithms.
A vector excels at insertion (deletion) of elements at the back. This is a constant-time operation as it is independent of collection size.
A vector is a terrible choice for element insertion (deletion) anywhere other than the back. The cost of such insertion (deletion) is proportional to the distance of the insertion (deletion) point and the last element of the vector.
A deque is efficient (constant-time) at ...
Get Efficient C++ Performance Programming Techniques now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
