История изменений

Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).

В данной задаче как раз массив и список примерно равноценны. Удалять можно без доп. памяти и без N^2 - записывая результат на место исходного массива сразу же (потому что он гарантированно не больше места занимает). Но список лучше, в нём не придётся неудалённые элементы двигать если удалилось что-то перед ними.

Кстати, о птичках. Элементы расположены по алфавиту. Задача «удалить все красные элементы». Считая, что элементы расположены более-менее равномерно, получаем, что стоимость обработки списка - O(N), а массива - O(N^2). Можно, правда, не удалять из вектора, а копировать результат в новый вектор, но тогда расход памяти на операцию - O(N). А в случае списка - O(1).

В данной задаче как раз массив и список равноценны. Удалять можно без доп. памяти и без N^2 - записывая результат на место исходного массива сразу же (потому что он гарантированно не больше места занимает).