C++ multimap iterator invalidation

Question

Я пытаюсь выяснить, как работают итераторы std::multimap, поэтому я создал простой пример, который показывает суть моей проблемы. Если uncomment case 1, я ожидаю, что итератор укажет на первый элемент с ключом 1, но на самом деле он печатает все значения, связанные с ключом 0 (например, ничего не было удалено), а иногда он сбой, вероятно, потому, что итератор недействителен. Однако, если раскол 2, все значения с ключом 1 удаляются должным образом.

Есть ли способ узнать, что является следующим действительным итератором для multimap после стирания? (например std::vector.erase(...) возвращает один)

std::multimap<int, int> m; 

for(int j=0; j<3; ++j) { 
    for(int i=0; i<5; ++i) { 
     m.insert(std::make_pair(j, i)); 
    } 
} 

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Answer 1

Причиной проблемы

При вызове m.erase(0) в вас, например, it точки на элементе с ключом 0 - так it аннулируется. m.erase(1) работает, потому что, когда он вызывается в первый раз, it не указывает на элемент с ключом 1, поэтому он не изменяется. В последующих итерациях не осталось элементов с ключом 1, поэтому ничего не удаляется, и на итератор не влияет.

Решение

multimap не имеет erase -метод, который возвращает следующий действительный итератор. Один из вариантов заключается в вызове it = m.upper_bound(deleted_key); после удаления. Это логарифмическое, хотя это может быть слишком медленным для вашего сценария (erase(x) и upper_bound - две логарифмические операции).

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

std::multimap<int, int>::iterator interval_start = m.begin(); 
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) { 
    if(interval_start->first < it->first) // new interval starts here 
     interval_start == it; 
    if((*it).second == 3) { 
     std::multimap<int, int>::iterator interval_end = it; 
     while((interval_end != m.end()) && (interval_end->first == it->first)) { 
      ++interval_end; // search for end of interval - O(n) 
     } 
     m.erase(interval_start, interval_end); // erase interval - amortized O(1) 
     it = interval_end; // set it to first iterator that was not erased 
     interval_start = interval_end; // remember start of new interval 
    } 
} 

При этом используется одна линейная операция , все остальное - постоянное время. Если ваша карта очень большая, и у вас есть только несколько предметов с одинаковыми ключами, это, скорее всего, будет быстрее. Однако, если у вас много элементов с одинаковыми ключами, поиск конца интервала, вероятно, лучше сделать, используя upper_bound (O(log n) вместо O(n) при поиске в конце интервала).

Answer 2

Первый ответ

std::multimap<int, int> m; 
// ^^^^^^^^ 
std::map<int, int>::iterator it=m.begin(); 
// ^^^ 

Hum ....

Второй ответ, Re: отредактированный вопрос

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    .... stuff .... 
     m.erase(1); // container mutation 
    .... stuff .... 
} 

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

так называемые «узловые на основе контейнеров» (list, set, map ...) являются наиболее надежным контейнером WRT итератора недействительности: они только недействительных итераторы удаленных элементов (нет никакого способа, чтобы эти итераторы не быть аннулированный).

В этом случае вы должны проверить, что элемент, который вы собираетесь удалить, на самом деле не является *it.

Я не совсем уверен, что вы пытаетесь сделать с вашей петлей.

Answer 3

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

std::map<int,int>::iterator next = m + 1; 
m.erase 
m = next; 

Answer 4

От взгляда на ваш код, я думаю, что ваш ++ это вызывает проблему. Вы назначаете это место, которое могло быть удалено. переместите его до конца, после утверждения if и теста. как так:

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
    ++it; 
} 

Answer 5

(Edited)

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

В дополнение к недействительности it итератора из-за m.erase, которые могут возникнуть в зависимости от содержания multimap (уже охвачены в другой ответ) всегда есть проблема, которую вы разыменования m.end() Итератор на последней итерации вашего цикла for, когда вы делаете if((*it).second == 3) каждый раз, когда вы запускаете свою программу.

Предлагаю запустить и отладить с помощью отладочных сборников. Я почти уверен, что всякая нормальная стандартная реализация библиотеки должна содержать assert для обнаружения разыменования end().

Answer 6

Некоторые ребята выше уже ответили, что вы играете с огнем.

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