Проблема с аннулированием итераторов STL при вызове erase

Question

Стандарт STL определяет, что когда стирание происходит в контейнерах, таких как std :: deque, std :: list и т.д., итераторы становятся недействительными.

Мой вопрос заключается в следующем, предполагая список целых чисел, содержащихся вstd :: deque и пара индикаторов, указывающих диапазон элементов в std :: deque, как правильно удалить все четные элементы?

Пока у меня есть следующее, однако проблема здесьявляется то, что предполагаемый конец становится недействительным после стирания:

#include <cstddef>
#include <deque>

int main()
{
   std::deque<int> deq;
   for (int i = 0; i < 100; deq.push_back(i++));

   // range, 11th to 51st element
   std::pair<std::size_t,std::size_t> r(10,50);

   std::deque<int>::iterator it = deq.begin() + r.first;
   std::deque<int>::iterator end = deq.begin() + r.second;

   while (it != end)
   {
      if (*it % 2 == 0)
      {
         it = deq.erase(it);
      }
      else
        ++it;
   }

   return 0;
}

Изучая, как реализован std :: remove_if, кажется, что происходит очень дорогостоящий процесс копирования / переключения вниз.

• Существует ли более эффективный способ достижения вышеуказанного без всех копий / сдвигов

• Как правило, удаление / удаление элемента обходится дорожечем заменить его следующим n-ным значением в последовательности (где n - количество удаленных / удаленных элементов)

Примечание: Ответы должны принимать последовательностьразмер довольно велик, + 1 мил элементов и что в среднем 1/3 элементов будет на стирание.

Answer 1

Я бы использовал Erase-Remove Idiom .Я думаю, что ссылка на статью в Википедии даже показывает, что вы делаете - удаляя нечетные элементы.

Копирование, которое делает remove_if, не дороже, чем то, что происходит, когда вы удаляете элементы из середины контейнера.Это может быть даже более эффективно.

Answer 2

Вызов .erase() также приводит к «очень дорогостоящему процессу копирования / переключения вниз».При удалении элемента из середины контейнера все остальные элементы после этой точки должны быть сдвинуты на одну позицию вниз в доступное пространство.Если вы удалите несколько элементов, вы понесете эту стоимость за каждый удаленный элемент.Некоторые из не стертых элементов будут перемещаться на несколько точек, но будут вынуждены перемещаться по одной точке за раз, а не за все сразу.Это очень неэффективно.

Стандартные библиотечные алгоритмы std::remove и std::remove_if оптимизируют эту работу.Они используют хитрый трюк, чтобы гарантировать, что каждый перемещенный элемент перемещается только один раз.Это намного, намного быстрее , чем то, что вы делаете сами, вопреки вашей интуиции.

Псевдокод выглядит так:

read_location <- beginning of range.
write_location <- beginning of range.
while read_location != end of range:
    if the element at read_location should be kept in the container:
        copy the element at the read_location to the write_location.
        increment the write_location.
    increment the read_location.

Как видите,каждый элемент в исходной последовательности рассматривается ровно один раз, и если его нужно сохранить, он копируется ровно один раз в текущую запись write_location.Он никогда не будет рассматриваться снова, потому что write_location никогда не может выполняться перед read_location.

Answer 3

Помните, что deque является непрерывным контейнером памяти (например, вектором и, возможно, совместно используемой реализацией), поэтому удаление элементов в середине контейнера обязательно означает копирование последующих элементов через отверстие. Вам просто нужно убедиться, что вы делаете одну итерацию и копируете каждый объект, который не будет удален, прямо в его конечную позицию, а не перемещаете все объекты по одному во время каждого удаления. remove_if эффективен и уместен в этом отношении, ваш цикл erase - нет: он делает огромное количество ненужного копирования.

FWIW - альтернативы:

• добавляет «удаленное» состояние к вашим объектам и помечает их как удаленные, но затем каждый раз, когда вы работаете с контейнером, вам нужно проверять себя
• использовать список, который реализован с использованием указателей на предыдущий и следующий элементы, так что удаление элемента списка изменяет соседние точки, чтобы обойти этот элемент: нет копирования, эффективная итерация, просто нет произвольного доступа, более маленький (т.е. неэффективный) выделение кучи и издержки указателя

Что выбрать, зависит от характера, относительной частоты и требований к производительности конкретных операций (например, может случиться так, что вы можете позволить себе медленное удаление, если они выполняются в некритическое время, но нуждаются в максимально быстрой итерации - что угодно это, убедитесь, что вы понимаете свои потребности и последствия различных структур данных).

Answer 4

Одной альтернативой, которая не была упомянута, является создание нового deque, копирование элементов, которые вы хотите сохранить в нем, и swap его со старым deque.

void filter(std::deque<int>& in, std::pair<std::size_t,std::size_t> range) {
    std::deque<int> out;
    std::deque<int>::const_iterator first = in.begin();
    std::deque<int>::const_iterator curr = first + range.first;
    std::deque<int>::const_iterator last = first + range.second;
    out.reserve(in.size() - (range.second-range.first));
    std::copy(first, curr, std::back_inserter(out));
    while (curr != last) {
        if (*curr & 1) {
            out.push_back(*curr);
        }
        ++curr;
    }
    std::copy(last, in.end(), std::back_inserter(out));
    in.swap(out);
}

Я не уверен, достаточно ли у вас памяти для создания копии, но обычно копирование выполняется быстрее и проще, чем пытаться встроить элементы стирания из большой коллекции. Если вы все еще видите, что память бьется, выясните, сколько элементов вы собираетесь сохранить, позвонив по номеру std::count_if и зарезервировав это количество. Таким образом, у вас будет одно выделение памяти.