Ответ
Если порядок элементов в 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):
- Вместо сдвига всех элементов после
pos(что стоит O(n)), мы берём последний элемент. - Перемещаем (или копируем) его на место удаляемого с помощью
std::move. - Удаляем последний элемент с помощью
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 и высокопроизводительных вычислениях, где важна скорость, а порядок не критичен.
Ответ 18+ 🔞
А, слушай, вот тебе реально годный лайфхак, если порядок элементов в векторе тебе похуй! Ну правда, зачем городить огород, если можно сделать всё за O(1) и не париться.
Представь себе: у тебя есть вектор, как очередь в столовой. И тебе нужно выкинуть какого-то челика из середины. Обычный vector::erase — это как если бы ты вытащил его, а потом заставил ВСЕХ, кто стоял за ним, сделать шаг вперёд. Ебать колотить, какая морока, особенно если очередь длинная! Сложность O(n), и это пиздец как неэффективно.
А теперь смотри, как делают крутые пацаны в геймдеве и всяких хайперформанс-штуках:
#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(); // И просто отрезаем хвост
}Суть в чём, ёпта?
- Вместо того чтобы сдвигать овердохуища элементов, мы просто берём последний элемент вектора.
- Берём его и перемещаем (через
std::move, это важно!) на место того, кого мы хотим удалить. Это как если бы ты в той очереди из столовой просто позвал последнего человека и сказал: «Слушай, встань-ка ты вот сюда, на место этого чувака, которого мы выгоняем». - А потом просто отрезаешь теперь уже ненужный последний элемент через
pop_back(). Всё, операция завершена!
Но, бля, есть нюансы, о которых кричать надо:
- Порядок ебётся полностью. После такой операции элементы будут не в том порядке, в котором ты их засунул. Последний встал в середину. Если порядок важен — это не твой метод, иди нахуй со своим O(1).
- Итераторы летят в пизду. Все итераторы и ссылки, которые указывали на последний элемент И на тот элемент, который ты «удалил», теперь инвалидированы. Доверия к ним — ебать ноль.
- Как это выглядит на практике:
std::vector<int> data = {10, 20, 30, 40, 50}; erase_unordered(data, 1); // Удаляем 20 (индекс 1) // Теперь data может быть таким: {10, 50, 30, 40} // Видишь? 50 встал на место 20. Порядок изменился, но вектор стал короче, и сделано это было моментально.
Вот такой финт ушами. Если тебе нужна суперскорость, а на порядок элементов тебе чих-пых в сраку — это твой выбор. В играх так постоянно делают, чтобы не тормозить на каждом кадре.
