In a C++ program I have a collection of plain-old-data for which I need be able to efficiently:
Actually, this is all already in the standard library:
std::vector::erasewhich can then act on the very end of the vector (see Erase-remove idiom). Alternatively, you can have a look at boost::remove_erase_if, although I do not know whether this unnecessarily preserves order or not. But at least it is O(n) in the end.
std::vector::insert(end)to efficiently insert a whole range)
std::remove_if also lets you remove a whole bunch of elements in a single iteration.
And, probably most importantly, iteration will be maximally fast due to your data being stores contiguously -> No cache misses.