Проблема с недействительностью итераторов STL при вызове erase

Question

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

Мой вопрос заключается в следующем, предполагая список целых чисел, содержащихся в 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; 
} 

Исследование как станд :: реализуется remove_if, кажется, что это очень дорого копия/смена процесса продолжается.

• Есть ли более эффективный способ достижения выше, не все копии/сдвигает

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

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

Answer 1

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

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

Answer 2

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

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

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

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

Answer 3

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