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

Стандарт 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 элементов подлежит удалению.


c++ iterator invalidation deque erase
person Community    schedule 03.12.2010    source источник
comment
Я считаю, что deque::erase делает недействительными все итераторы.   -  person D.Shawley    schedule 04.12.2010
comment
Стирание не влияет на итераторы/указатели на нестираемые элементы в std::list. Пожалуйста, обратитесь к этому списку: stackoverflow.com/questions/6438086/iterator-invalidation -rules/ для полных правил аннулирования.   -  person metamorphosis    schedule 14.04.2016

Ответы (4)


arrow_upward
8
arrow_downward

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

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

person Fred Larson    schedule 03.12.2010
comment
@Oxsnarder: Но у вас, вероятно, есть еще больше копий, использующих отдельные вызовы erase, как ответ Карла указывает. Дело в том, что удаление элементов из середины vector или deque по своей сути неэффективно. Если вам нужно делать это часто, вам может быть лучше использовать list. В этом случае используйте либо функцию-член remove_if, либо тип цикла стирания, который вы указали. end не будет аннулирован для list. - person Fred Larson; 03.12.2010

arrow_upward
5
arrow_downward

Вызов .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 никогда не может запускаться перед read_location.

person Karl Knechtel    schedule 03.12.2010

arrow_upward
2
arrow_downward

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

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

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

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

person Tony Delroy    schedule 03.12.2010
comment
как эффективно и разумно добавить удаленное состояние в deque‹int› из 10 mil элементов? - person ; 03.12.2010

arrow_upward
0
arrow_downward

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

person D.Shawley    schedule 04.12.2010