Проблема с аннулированием итераторов 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. Я думаю, что ссылка на статью в Википедии даже показывает, что вы делаете - удаляете нечетные элементы.

Копирование этого 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 и зарезервировать это много. Таким образом, у вас будет одно выделение памяти.