Erasing From the Middle: Compaction and the Order It Destroys

Removing the last element of an array is one decrement. Removing any other element leaves a hole in the middle of a contiguous region, and a hole is not representable: the array’s defining property is that element i sits at offset i * sizeof(T). Either the elements after the hole move down to close it, or the array stops being an array. Every technique for removal is a choice between those two, and the consequences of the choice reach further than the cost of the shift.

The shift and its two directions

Erasing element i from an array of n elements requires moving elements i+1 through n−1 down one position, which is n − i − 1 moves. The work is proportional to the number of elements after the erased one, so erasing near the front is expensive and erasing near the back is cheap. Erasing the last element is free beyond the length decrement.

The copy must handle overlap. memmove is specified for overlapping regions and chooses a direction based on the relative addresses; memcpy is not, and using it here is undefined behaviour that happens to work when the destination is below the source and the copy proceeds forward. The standard library containers call the overlapping variant, which is why erasing from a std::vector is correct even though it moves bytes within the same allocation.

/* Erase element i by shifting the tail down; O(n - i) moves. */
void erase_at(int *a, size_t *n, size_t i) {
    size_t tail = *n - i - 1;
    if (tail)
        memmove(a + i, a + i + 1, tail * sizeof *a);
    (*n)--;
}

For an array of a million 8-byte elements, erasing index zero moves nearly 8 MB. That is a memory-bandwidth operation: the source and destination overlap by all but one element, so the copy reads and writes essentially the same bytes, and the total traffic is about twice the array’s size, moving the tail down and then writing it back. A bulk copy routine moves them a cache line at a time in the direction that avoids clobbering unread source bytes. The floor for the pass is set by the memory path, and the cost grows worse when the array does not fit in cache, because the lines must be fetched before they can be written and the fetch is not overlapped perfectly with the store stream.

The direction choice is not incidental. If the destination is below the source, a forward copy is safe because each byte is read before it is overwritten. If the destination is above the source, as in an insertion that shifts elements up, the copy must run backward. A routine that always copies forward corrupts the tail of the region it is moving; the corruption is a repeated pattern of the first bytes, which is why the symptom looks like duplicated data rather than missing data.

Element lifetime is not byte movement

For a type with a destructor or with owned resources, the shift is not a memmove. The erased element’s destructor must run, and the moved elements must be relocated rather than bit-copied if their addresses matter. std::vector::erase requires the element type to be move-assignable and destroys the last element after shifting the tail, so the sequence is: move-assign the tail down, destroy the vacated last slot, decrement the size. For a type whose move assignment throws, the standard leaves the container in a valid but unspecified state; the elements are not lost, but their order is not guaranteed.

A type that registers its own address — an object that inserts this into an index, or a node whose neighbours hold pointers to it — cannot be relocated by any shift. Such objects must live in a container that does not move them, which is the reason node-based containers exist at all. The array’s cheap random access and its immovability requirement are in direct conflict, and the resolution is always to store pointers or indices in the array and the immovable objects elsewhere.

Swap-and-pop: constant time, destroyed order

If the order of the remaining elements does not matter, removal can be constant time: move the last element into the hole and decrement the length. The hole is filled by the element that was at the end, which is one move regardless of the array’s size.

/* Unordered removal: the last element takes the hole. O(1). */
void swap_remove(int *a, size_t *n, size_t i) {
    a[i] = a[--(*n)];      /* self-assignment is harmless when i is last */
}

The trade is exact and worth stating plainly: O(1) instead of O(n − i), at the price of losing the order of every element after i. A loop that removes elements while iterating forward cannot use this form, because the element moved into position i has not been examined yet; the loop must not increment its index after a removal. A loop that iterates backward can, because the moved element came from a position already visited. The same substitution appears in containers that do not keep order at all: the block map of a deque makes room at both ends but not in the middle, and a hash table’s probe sequence is rebuilt from scratch when an entry moves, because its position is derived rather than promised.

This is the same trade that an object pool makes when it reuses freed slots, and the same one a hash table makes when it deletes by moving another entry into the hole. The identity of “position” is what is being given up, so any code that holds indices into the array as stable references is incompatible with swap-and-pop. Holding the element’s value or a separately allocated handle is not.

Retain and the stable partition

The stable removal of many elements is not a sequence of single erases, because each erase shifts the tail and a filter that removes half the elements that way does quadratic work. The linear approach is a single pass with two indices: one reads, one writes. Every element that survives is written at the write position, and the write position advances. At the end the length is the write position.

/* Stable filter in one pass: survivors keep their relative order. */
size_t retain(int *a, size_t n, int (*keep)(int)) {
    size_t w = 0;
    for (size_t r = 0; r < n; r++)
        if (keep(a[r]))
            a[w++] = a[r];        /* w <= r always, so no overwrite */
    return w;                     /* new length */
}

The invariant w ≤ r is what makes the in-place write safe: the write position never overtakes the read position, so the element being written has already been consumed. The loop is a compaction, and it moves each surviving element at most once — s moves for s survivors, against s·(n/2) for repeated single erases on a filter that removes half.

The same pass with a different predicate produces a partition: elements satisfying the predicate first, the rest after, with relative order preserved on both sides. The two-index form is the stable partition; the one-index-per-end swap form is the unstable one, and it is what quicksort’s partition step uses. A stable partition needs the auxiliary space or the quadratic movement that an unstable one avoids, which is the same trade as stable versus unstable sorting in miniature.

Tombstones and deferred compaction

When removals are frequent and the array is large, even the linear filter may be too expensive to run on every removal. The alternative is to mark the slot as dead and leave it in place. A lookup skips dead slots; an insertion reuses the first dead slot it finds; compaction happens when the fraction of dead slots crosses a threshold.

The cost model changes from per-removal to per-compaction. A tombstone makes removal O(1), and the compaction pass that follows is O(n) but happens once per d removals, where d is the number of dead slots tolerated. The amortized cost per removal is then O(1 + n/d), which is constant only if d grows with n. Setting the threshold as a fraction of capacity — compact when a quarter of the slots are dead — gives that property.

The failure modes are the ones that any deferred maintenance has. A reader that scans the array must understand the marker, so the marker becomes part of the on-disk or on-wire format if the array is persisted. A tombstone that is never collected is a leak, and a structure that is mostly tombstones has the memory cost of the full array with the useful capacity of the survivors. And the compaction pass invalidates every index and pointer into the array at once, which is a far larger invalidation event than a single erase.

Databases use the same mechanism under the name of a deleted-row bitmap, and the compaction pass under the name of vacuum or merge. The array-of-records case has an extra wrinkle: a dead record’s slot can be reused by a record of a different shape only if the array has fixed-size slots, so variable-length records are stored out of line with the array holding offsets. That indirection is the same one a deque’s block map uses, and it converts the compaction into a pass over offsets rather than over records.

Iterators and the invalidation rule

Every removal from a contiguous array invalidates iterators and pointers at or after the removed position, and a swap-and-pop invalidates the last position as well. The rule is a consequence of the layout, not a library quirk: the elements after the hole have moved, so an address computed before the removal no longer refers to the same element.

A loop that erases while iterating must therefore use the index returned by the erase, which points at the element that followed the erased one, rather than incrementing a saved iterator. This is the single most common bug in removal code, and it is invisible in a test where the removed element is the last one, because the shift is empty and the stale iterator happens to still be in range.

The alternative containers make the opposite promise. A node-based list’s erase invalidates only the iterator to the erased node, which is what allows a loop to erase and continue with a saved next pointer. The price is the pointer chase per access and the allocation per element. A contiguous array’s price is the shift; a linked list’s price is the locality. Removal is where the two prices are easiest to compare, because both structures perform the same logical operation and the difference is entirely in what they move. A structure that avoids the question altogether is the persistent vector, where an update copies a path rather than moving elements, as described in Immutable Sequences and Structural Sharing.