Unordered_map действует странно, когда я добавляю новый элемент - PullRequest
Новая
       11

Unordered_map действует странно, когда я добавляю новый элемент

2 голосов
/ 01 мая 2019

Эти строки не работают должным образом: 

for (auto prod : productions_[*productionNonterm])
                productions_[nonterminal].push_back(prod);

Если у продукции _ [* productionNonterm] есть только 1 элемент, все хорошо. Но если в нем есть хотя бы 2 элемента, то ProductionNonterm изменяется, и я понятия не имею, почему. 

vector<string> nonterminals_;
unordered_map<string, vector<string>> productions_;

for (const auto &nonterminal : nonterminals_) {
    for (auto productionNonterm = productions_[nonterminal].begin(); productionNonterm != productions_[nonterminal].end(); ++productionNonterm) {
        if (cntNonterminalsInProduction(*productionNonterm) == 1 && cntTerminalsInProduction(*productionNonterm) == 0) {
            nonterminals_.erase(find(nonterminals_.begin(), nonterminals_.end(), *productionNonterm));

            for (auto prod : productions_[*productionNonterm])
                productions_[nonterminal].push_back(prod);

            productions_[*productionNonterm].erase(productions_[*productionNonterm].begin(), productions_[*productionNonterm].end());

            productions_[nonterminal].erase(productionNonterm);
            --productionNonterm;

        }
    }
}

Ответы [ 2 ]

1 голос
/ 01 мая 2019

проблема с итератором productionNonterm, и он становится недействительным во время цикла:

как только вы начнете цикл 

    for (auto prod : productions_[*productionNonterm])
        productions_[nonterminal].push_back(prod);

вы вступите в контакт с действительным итератором (productionNonterm) указывает на один (первый) элемент в productions_[nonterminal].

, но после того, как тело цикла будет выполнено в первый раз - вектор productions_[nonterminal] перераспределит свои элементы (из-за роста) и ваш указатель (итератор) будет признан недействительным ...

0 голосов
/ 01 мая 2019

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

Взгляните на vector :: push_back , в частности, на обсуждение валидности итераторов.

На практике вы можете избежать этой конкретной проблемы, определив размер вектора, но есть также проблемы отслеживания того, куда вы помещаете новые элементы относительно итератора, и т. Д. В общем, это приводит к трудному для понимания коду, даже когда это правильно (или хуже, выглядит так, но имеет тонкие проблемы).

Я предлагаю вам переписать для двухпроходного подхода, собрать элементы для добавления или удаления за один проход, затем удалить их и т. Д. Если у вас нет очень хороших (и измеримых!) Причин производительности, чтобы не делать этого, это происходит чтобы было легче понять и поддерживать. Напомним, что vector :: erase может принимать диапазон.

Стоит также спросить: важен ли здесь порядок? Если вы используете std :: unordered_set, в этом случае у вас не будет этой конкретной проблемы.

Посмотрите, что вы думаете об этом подходе, прежде чем "исправить" этот.

...