Kuidas saab eemaldada suvalise elemendi massiivist (vektorist) konstantse aja jooksul, kui elementide järjekord ei ole oluline?

Kui massiivi (vektori) elementide järjekord ei ole oluline, saab ükskõik millise elemendi eemaldada konstantse aja jooksul, asendades eemaldatava elemendi massiivi viimase elemendiga ja seejärel vähendades massiivi suurust 1-ga.

See väldib kõigi järgnevate elementide nihutamist, mis tavaliselt võtab lineaarse aja.

Näide C++-s:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // asendab eemaldatava elemendi viimasega
    vec.pop_back();          // eemaldab viimase elemendi
}