CODEWITHSUNDEEP
c++c++11stl
user9236635
user9236635

Reputation:

Unordered_map acts strange when I add a new element

This lines are not working properly:

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

If productions_[*productionNonterm] has only 1 element, everything is good. But if it has at least 2 elements, productionNonterm is modified and I have no idea why.

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;

        }
    }
}

Upvotes: 2

Views: 98

Answers (2)

simon
simon

Reputation: 7022

It is tricky modifying a collection while iterating it, and usually not worth the overhead to support it in the container. In this case (vector) you are invalidating the iterator (i.e. a pointer to vector storage) as soon as the vector re-allocates when you grow it.

Have a look at vector::push_back, particularly the discussion of iterator validity.

In practice you can avoid this particular problem by sizing the vector but there are also issues keeping track of where you are putting new elements relative to the iterator, etc. In general it leads to difficult-to-follow code, even when it is correct (or worse, looks it but has subtle issues).

I suggest you rewrite to a two-pass approach, collect up the elements to add or remove in one pass, then remove them etc. Unless you have very good (and measured!) performance reasons to not do this, it's going to be easier to understand and maintain. Recall that vector::erase can take a range.

It's also worth asking: does order matter here? Should you be using std::unordered_set, in which case you wouldn't have this particular problem.

See what you think of that approach before "fixing" this one.

Upvotes: 0

Dmitry
Dmitry

Reputation: 1293

problem with the iterator productionNonterm and it's getting invalidated during the loop:

once you start your loop

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

you'll get into with with a valid iterator (productionNonterm) pointing to a one (first) element in the productions_[nonterminal].

but after loop's body gets executed the first time - vector productions_[nonterminal] will reallocate its elements (due to growing) and your pointer (iterator) will be invalidated...

Upvotes: 1

Related Questions