swap_remove Trades Vector Order for Constant-Time Removal

Vec::swap_remove(index) removes the selected value by moving the vector's last value into its place. It avoids shifting the remaining suffix, but relative order is not preserved. The failing fixture removes "index" from four jobs and gets parse, report, serve, not parse, serve, report.

The method name describes the mechanism

The swap_remove documentation is direct: the removed position is replaced with the last element. Conceptually, it is a swap with the tail followed by pop. The operation does not promise a stable sequence.

This makes removal fast because a vector stores contiguous elements. Preserving order after removing position i requires every later element to move one position left. Vec::remove performs that shift. swap_remove avoids it when order is irrelevant.

I treat this as a data-model decision, not a local micro-optimization. If positions carry meaning, changing order changes the program.

Order is often an invisible API

A queue, priority tie-breaker, rendering list, migration plan, or user-facing search result can depend on relative order without documenting it. Tests may only check membership, so the bug survives until an input happens to remove a middle element.

Index-based side tables make the risk larger. Suppose a vector of connections has a parallel vector of metrics. Moving the final connection into a removed slot requires moving or updating every associated index. If external code stores indices, the moved item now has a different identity location.

In an entity store this can be intentional. Dense slot maps often use swap removal and update a handle-to-index map. The method is excellent there because unordered dense storage is part of the design. The failure comes from adopting its cost model without adopting its invariant.

Choose remove when the sequence matters

The repaired fixture uses remove(1). It returns the same removed element while preserving the order of elements after it. This is the simplest honest repair when vector order is observable.

For many removals, repeatedly calling remove can shift the suffix many times. I may use retain, drain a range, partition into another collection, or build a new vector in one pass. These choices still preserve or intentionally redefine order at the algorithm level.

If only the final element is removed, pop is clearer and constant time. If the collection is naturally keyed, a map or slab may express identity better than exposing vector indices. Performance work becomes easier after the storage contract is explicit.

The moved value is not cloned

swap_remove moves the last value. It does not require T: Clone. This is useful for unique resources such as owned sockets, buffers, and state machines. The removed value is returned to the caller, which remains responsible for dropping, reusing, or transferring it.

Any reference into a vector already prevents mutable removal in safe Rust. Numeric indices do not receive that protection. They are plain values, so the compiler cannot update them when an element moves. I use generation-based handles or a lookup table where stale positions would be dangerous.

Tests should assert the real contract

When order matters, I assert the complete sequence after first, middle, and last removal. When order does not matter, I avoid accidentally freezing today's order in a snapshot. I compare sets or sorted test copies and separately verify the moved element's index bookkeeping.

Benchmarks must include realistic element sizes and removal positions. Shifting a few small values can be cheaper than maintaining extra maps. Conversely, large vectors with frequent unordered removal benefit strongly from swap_remove. The API gives a mechanism, not a universal performance answer.

My removal checklist

• Is relative order observable to callers, users, or deterministic tests?
• Does another structure store indices into this vector?
• If the tail moves, which metadata must be updated?
• Is remove, retain, drain, or pop a clearer operation?
• Are benchmarks measuring the real element type and removal pattern?
• Do tests verify sequence when sequence matters and ignore it when it does not?
• Is unordered dense storage documented as an invariant?

The core principle is that complexity improvements usually spend a semantic guarantee. swap_remove spends ordering to avoid shifting a suffix. I use it confidently when order has no meaning and treat it as a design bug when a sequence is part of the contract.