Hogyan lehet egy tetszőleges elemet törölni egy tömbből (vektorból) állandó idő alatt, ha az elemek sorrendje nem számít?

Ha a tömb (vektor) elemeinek sorrendje nem számít, akkor tetszőleges elemet állandó idő alatt törölhetünk úgy, hogy az eltávolítandó elemet a tömb utolsó elemével helyettesítjük, majd a tömb méretét 1-gyel csökkentjük.

Ez elkerüli az összes következő elem eltolását, ami általában lineáris időt vesz igénybe.

Példa C++-ban:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // az eltávolítandó elemet az utolsóval helyettesíti
    vec.pop_back();          // eltávolítja az utolsó elemet
}