Как удалить произвольный элемент вектора за константное время, если не важен порядок?

Если порядок элементов в std::vector не важен, эффективный способ удаления элемента по индексу за O(1) — переместить последний элемент вектора на место удаляемого и вызвать pop_back().

Реализация:

#include <vector>
#include <utility> // для std::move

template <typename T>
void erase_unordered(std::vector<T>& v, typename std::vector<T>::size_type pos) {
    if (pos >= v.size()) return; // Выход за границы
    if (pos != v.size() - 1) {
        v[pos] = std::move(v.back()); // Перемещаем последний элемент
    }
    v.pop_back(); // Удаляем последний элемент (теперь это дубликат)
}

Как это работает и почему O(1):

1. Вместо сдвига всех элементов после pos (что стоит O(n)), мы берём последний элемент.
2. Перемещаем (или копируем) его на место удаляемого с помощью std::move.
3. Удаляем последний элемент с помощью pop_back() (амортизированная константная сложность).

Критические нюансы:

• Нарушение порядка: Элементы меняют местами.
• Инвалидация итераторов: Инвалидируются итераторы и ссылки на последний элемент и на элемент в позиции pos.
• Пример использования:

  std::vector<int> data = {10, 20, 30, 40, 50};
  erase_unordered(data, 1); // Удаляем элемент с индексом 1 (20)
  // data теперь может быть: {10, 50, 30, 40}
  // Порядок изменился: 50 встал на место 20.

  Это стандартный приём в game development и высокопроизводительных вычислениях, где важна скорость, а порядок не критичен.