C ++ недопустимость многокарточного итератора

Question

Я пытаюсь выяснить, как работают std::multimap итераторы, поэтому я создал простой пример, который показывает суть моей проблемы.Если раскомментировать случай 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::map<int,int>::iterator next = m + 1;
m.erase
m = next;

Answer 3

Первый ответ

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

Hum ....

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

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 4

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

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

Answer 5

(отредактировано)

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

Глядя на ваш код, я думаю, что ваш ++ вызывает проблему.Вы назначаете это место, которое могло быть удалено.переместите его до конца, после оператора 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;
}