Удаление элемента вектора за О(1), если не требуется сохранять порядок элементов
perfectGenius opened this issue · 11 comments
Копируем последний элемент вектора на место удаляемого и сдвигаем указатель конца на один элемент.
Можно назвать что-то типа erase_unordered.
Зачем делать все комбинаторно возможные методы, которые реализуются из различных пар уже существующих методов std::vector? Какая цель? Чтобы что?
Поменьше и попроще кода, больше производительность.
Производительность не больше. Ни на такт.
Зачем делать все комбинаторно возможные методы
Почему же тогда вместо pop_back просто не делать resize -1?
делать
Чтобы понимать, имеется в виду:
std::swap(*it, vec.back());
vec.pop_back();Чтобы понимать, имеется в виду:
std::swap(*it, vec.back()); vec.pop_back();
*it = std::move(vec.back()); vec.pop_back();
std::swap(*it, vec.back());
vec.pop_back();
А как же производительность? Т.е. зачем выделять буфер для обмена и копировать удаляемый элемент? Надежда на компилятор, что он поймёт замысел и не станет делать лишнее?
Скорее уж что-то типа
вектор[it] = вектор.back());
вектор.pop_back();
Производительность не больше. Ни на такт.
Может оказаться, что компилятор в некоторых случаях не поймёт, что эти две строки можно выполнять параллельно после получения адреса последнего элемента. А если это одна функция, то это будет однозначно.
Также может немного повыситься скорость компиляции, т.к. не надо парсить и разбирать лишнее, изучать связи.
Почему не *it = std::move(vec.back());?
move разве автоматически делает pop_back?
Если вы про мой пример, то можно и так, у меня пока мало опыта с итераторами.
Не заменит, я только про первую строчку. Копирование не понравилось.
*it = std::move(vec.back());
vec.pop_back();