Remove-erase идиома
Удаление элементов из вектора - вещь не совсем тривиальная. Безусловно, в STL есть интерфейс для этого, бери да вызывай. Проблема в том, что удаление вызывает копирование всех элементов вектора, которые находятся правее от удаляемого элемента. То есть, в среднем, сложность удаления одного элемента контейнера будет линейной. А сложность очистки всего контейнера - квадратичная. Это все очень печальные результаты. И хоть для последовательности упорядоченных элементов нет стандартного алгоритма удаления из середины, для вектора, в котором порядок неважен, такой алгоритм есть.
Нам нужно лишь свопнуть удаляемый элемент с последним элементом в векторе и очистить последнюю с конца ячейку. Таким образом, удаление будет занимать всего 2 действия, а значит сложность этой операции - константная. Звучит намного лучше.
А что, если нужно отфильтровать массив по какому-то критерию? Ну удалить все ячейки, которые обладают какими-то характеристиками. Например, из массива удалить все числа, кратные 5. Надо тогда в цикле проделать действия из предыдущего абзаца и все будет пучком.
Однако, есть ощущение, что это задача слишком общая и хотелось бы иметь для нее какое-то более элегантное решение, чем каждый раз писать цикл. Можно конечно объявить функцию, но все-таки хочется чего-то стандартного.
И такое есть. В плюсах это называется remove-erase idiom. Идиома удаления-очистки. Какой у меня прекрасный английский)
Решение хоть и стандартное, но не прям очень элегантное. Ну а что вы хотели? Это плюсы все-таки.
Судя по названию, надо просто скомбинировать стандартный алгоритм std::remove (или std::remove_if) и метод вектора std::vector::erase.
На картинке снизу можете увидеть, как конкретно эта комбинация решает задачу удаления элементов.
Stay cool.
#algorithms #STL #datastructures
Удаление элементов из вектора - вещь не совсем тривиальная. Безусловно, в STL есть интерфейс для этого, бери да вызывай. Проблема в том, что удаление вызывает копирование всех элементов вектора, которые находятся правее от удаляемого элемента. То есть, в среднем, сложность удаления одного элемента контейнера будет линейной. А сложность очистки всего контейнера - квадратичная. Это все очень печальные результаты. И хоть для последовательности упорядоченных элементов нет стандартного алгоритма удаления из середины, для вектора, в котором порядок неважен, такой алгоритм есть.
Нам нужно лишь свопнуть удаляемый элемент с последним элементом в векторе и очистить последнюю с конца ячейку. Таким образом, удаление будет занимать всего 2 действия, а значит сложность этой операции - константная. Звучит намного лучше.
А что, если нужно отфильтровать массив по какому-то критерию? Ну удалить все ячейки, которые обладают какими-то характеристиками. Например, из массива удалить все числа, кратные 5. Надо тогда в цикле проделать действия из предыдущего абзаца и все будет пучком.
Однако, есть ощущение, что это задача слишком общая и хотелось бы иметь для нее какое-то более элегантное решение, чем каждый раз писать цикл. Можно конечно объявить функцию, но все-таки хочется чего-то стандартного.
И такое есть. В плюсах это называется remove-erase idiom. Идиома удаления-очистки. Какой у меня прекрасный английский)
Решение хоть и стандартное, но не прям очень элегантное. Ну а что вы хотели? Это плюсы все-таки.
Судя по названию, надо просто скомбинировать стандартный алгоритм std::remove (или std::remove_if) и метод вектора std::vector::erase.
На картинке снизу можете увидеть, как конкретно эта комбинация решает задачу удаления элементов.
Stay cool.
#algorithms #STL #datastructures