> If you want O(1) removal of a random element, you use a data structure that guarantees O(1) removal of a random element
Like std::list.
It's guaranteed that insertion and removal is done in constant time. It does mean that you need an iterator pointing to the element you want to insert in front of ahead of time.
If you want to be more specific, it guarantees is that given a list of elements to insert, the insertion and deletion will be linear in the number of elements inserted or deleted (ie, independent of the size of the list being inserted into; the insertion or removal of each value passed to insert() or erase() is required to be O(1))
(That's one thing that I like about the C++ STL: It usually guarantees a certain complexity for the data structures it provides)
Like std::list.
It's guaranteed that insertion and removal is done in constant time. It does mean that you need an iterator pointing to the element you want to insert in front of ahead of time.
If you want to be more specific, it guarantees is that given a list of elements to insert, the insertion and deletion will be linear in the number of elements inserted or deleted (ie, independent of the size of the list being inserted into; the insertion or removal of each value passed to insert() or erase() is required to be O(1))
(That's one thing that I like about the C++ STL: It usually guarantees a certain complexity for the data structures it provides)