Как различается сложность удаления элемента по уже полученному итератору в std::vector и std::list?
Для std::vector удаление элемента по итератору обычно имеет линейную сложность: элементы справа приходится сдвигать на одну позицию. Для std::list удаление одного элемента по уже корректному итератору выполняется за константное время, поскольку достаточно перенастроить связи соседних узлов.
Это сравнение не учитывает получение итератора. Если сначала нужно найти элемент, поиск в векторе или списке может занять линейное время.
std::vector и std::list представляют разные модели хранения последовательности. Вектор использует непрерывный массив, обеспечивая хорошую локальность данных и быстрый произвольный доступ. Список хранит элементы в отдельных узлах, связанных между собой указателями, поэтому вставка или удаление известного узла не требует перемещения остальных элементов.
Такое разделение позволяет выбирать контейнер под преобладающую операцию: быстрый доступ и компактное хранение либо эффективное изменение структуры уже найденной последовательности.
Если удалять элемент из середины вектора, свободное место нельзя оставить внутри непрерывного массива. Все последующие элементы должны переместиться влево, иначе нарушится последовательность индексов.
В списке элементы не обязаны располагаться рядом в памяти. Поэтому удаляемый узел можно исключить из цепочки, изменив связи его соседей. Ошибка в оценке сложности может привести к неожиданному ухудшению производительности при массовых удалениях.
Для std::vector удаление элемента в позиции i требует переместить элементы после неё. Сложность составляет O(n − i), а в общем случае — O(n). Удаление последнего элемента является частным случаем и выполняется за O(1), если учитывать только одну операцию удаления.
Для std::list удаление одного элемента по корректному итератору имеет сложность O(1). Контейнер уничтожает объект и перенастраивает связи между предыдущим и следующим узлами; количество остальных элементов не влияет на эту операцию.
Ключевое условие для списка — итератор уже должен указывать на нужный элемент. Получение такого итератора обходом от begin() может занять O(n). Поэтому утверждение «удаление из списка константное» не означает, что поиск и удаление произвольного значения в списке тоже константны.
У контейнеров различается и поведение связанных итераторов. После удаления из вектора итераторы на удалённый элемент и элементы справа обычно становятся недействительными из-за сдвига. При удалении одного узла из списка недействительным становится итератор только на этот узел, а итераторы на остальные узлы сохраняются.
В планировщике задач нужно часто удалять задачи, на которые уже имеются итераторы. Вариант с std::vector обеспечивает компактное хранение, быстрый обход и хорошую локальность памяти, но серия удалений из середины приводит к множественным сдвигам и может иметь квадратичную суммарную стоимость.
Вариант с std::list удаляет найденные узлы за константное время и сохраняет итераторы на остальные элементы. Его недостатки — дополнительные указатели в каждом узле, разрозненное размещение в памяти и более медленный последовательный обход из-за плохой локальности.
Если удаление по известному итератору доминирует, а размер последовательности умеренный и обход не является узким местом, обоснованным выбором может быть std::list. Если же важнее быстрый обход, индексный доступ и компактность, лучше оставить std::vector, изменить модель удаления или применять отложенное удаление с периодической очисткой.
Нет. Теоретическая сложность списка лучше только для удаления уже найденного элемента. На практике узлы списка требуют переходов по указателям и часто находятся далеко друг от друга в памяти. Удаление из середины небольшого вектора может оказаться быстрее благодаря непрерывному размещению и эффективному перемещению данных.
В списке поиск по значению обычно занимает O(n), после чего само удаление занимает O(1). В векторе поиск также может занимать O(n), а последующее удаление — ещё до O(n) из-за сдвига. Если поиск выполняется в отсортированном векторе, позицию можно найти за логарифмическое время, но удаление из середины всё равно останется линейным.
В векторе удаление диапазона требует уничтожить удаляемые элементы и сдвинуть элементы, расположенные после диапазона, поэтому сложность линейна относительно затронутых элементов. В списке удаление диапазона также требует пройти и уничтожить удаляемые узлы, то есть для диапазона длины k это O(k); константной является именно операция удаления одного узла по готовому итератору.