Adrian Ratnapala Adrian Ratnapala - 24 days ago 9
C++ Question

O(1) deletion in an unordered vector

In a C++ program I have a collection of plain-old-data for which I need be able to efficiently:


  • Add elements.

  • Iterate over the whole collection.

  • Remove some of those elements (see update below).iteration, see below).



I do not have to use a set or map type because there is no external requirement for:


  • Indexing into it

  • Maintaining ordering.

  • Efficiently finding elements or test for them being in the collection.



If I had to write it from scratch in C, I would use an exponentially growing dynamic array and the deletion operation would move the last element into the freed-up slot. That way deletion is O(1).

If I want to use a C++ standard container it seems I could (a) use a
std::vector
but write the deletion operation by hand or (b) use an
std::list
. I have a mild, but definite, dislike of linked lists.

Both solutions are acceptable to me, but I would really rather have it both ways: to use a vector but using only standard operations. Is there a way to do this.

Update:

The comments below made clear that I am not looking for a general deletion operation. My problem requires me to iterate over the collection frequently and on each pass I expect to discover that some elements have to be removed.

I can do that whole operation in O(n) time regardless of the number of deletions. But this is obviously a bespoke operation and I should have known I need to write my own loop. Surprisingly though
remove_if
almost solves my problem. If the only thing I needed to do in the iteration pass was identify the out-of-date elements, then
remove_if
would do the job, but I need to do other processing too.

Answer

Actually, this is all already in the standard library:

The 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.