Modifying set while iterating gives me segfault

Question

I am currently working on a function working with a vector of sets of int. I want my function merge( ) to merge all sets that share an int in common, so for example I want this to happen :

  [0]  -  0, 1, 2                              
  [1]  -  1, 3            Then it will              [0]  -  0, 1, 2, 3
  [2]  -  0, 3            output this vector ->     [1]  -  4, 5
  [3]  -  4, 5                                      [2]  -  6, 7, 8, 9
  [4]  -  6, 7, 8                                   
  [5]  -  8, 9

I have already written this function, of which code is presented down here. I have commented almost every line so that it is not too difficult to understand my code !

// Merges all sets that shares at least one int
//
// PARAMETERS...
//      vectorE         : vector of sets of int
void mergeStates( std::vector< std::set< int > >& vectorE )
{
    // For every set of ints
    for( auto &currentSet : vectorE )
    {
        // For every ints of the set
        for( auto currentInt : currentSet )
        {   
            // The two for( ) loops down there allow me to iterate over 
            // every int of every set of the vectorE
            for( auto setToCheck : vectorE )
            {
                // If the set is different from the one we're already targeting
                if( currentSet != setToCheck )
                {
                    for( auto intToCheck : setToCheck )
                    {
                        // if we have found an int that is the same as the one we're targeting
                        if( intToCheck == currentInt )
                        {
                            // Merge
                            etatsetEtudie.insert( setToCheck.begin(), setToCheck.end() );

                            // Deleting the set we copied from, because we won't need it anymore
                            for(auto setToErase = vectorE.begin() ; setToErase != vectorE.end() ; ){
                                if( *setToErase == setToCheck )
                                    setToErase = vectorE.erase( setToErase );
                                else
                                    ++setToErase;
                            }
                        }
                    }
                }
            }
        }
    }
}

Every time I run my program, I get a segfault when it comes to deleting the set we copied from : where is my error?

Edit : I got it to work !

Alright, thanks guys I simply made my parameter const and added a return value so that I can add dynamically every constructed set I need to a new vector, and return this vector :-)

If I am coming to you, it is because I really can't find my error. — Fumée Noire, Dec 14 '17 at 09:38
You can't modify a container while iterating over it. That's undefined behavior. — Galik, Dec 14 '17 at 09:41
Possible duplicate of [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) — mch, Dec 14 '17 at 09:45
@Galik Not true in general. Every container has its own invalidation rules. — Sebastian Redl, Dec 14 '17 at 09:46
@Galik: you can `erase()` from a `std::vector` while iterating - as long as you make sure you use the iterator returned from `erase()` *and* you compare against the updated `end()`. Inconveniently, though, the specification of `std::vector::erase()` doesn't state what is actually returned... (see 26.3.11.5 [vector.modifiers] paragraphs 3 to 5). Turns out, the specification for the return value is in 26.2.3 [sequence.reqmts] paragraph 11. — Dietmar Kühl, Dec 14 '17 at 09:50

score 0 · Answer 1 · answered Dec 14 '17 at 09:46

The problem isn't modifying any set, it's modifying the vector.

Erasing something from a vector shifts the elements after it. First, this means iterators into the vector after the erased position (the for-range loop uses iterators internally) are no longer valid. Second, if the shifting copied and overwrote sets (instead of moving them), all your iterators into the sets will no longer be valid.

The result is lots of undefined behavior in your code.

Also, your innermost loop is not a good way to go about erasing the set, even if the method was valid. It's very, very inefficient.

You need to rethink, at the very least, the way you're erasing elements. But I think that coming up with a generally better algorithm would be the better approach.

Ron · Answer 2 · 2017-12-14T09:52:31.313

0

You are using the std::vector::erase function which invalidates iterators. Consequently your code inside the range based for loop tries to access the iterator past the container end.

edited Dec 14 '17 at 09:52

answered Dec 14 '17 at 09:46

Ron

14,674
4
34
47

score 0 · Answer 3 · answered Dec 14 '17 at 09:47

0

Try to make a new vector instead of modifying the original one:

std::vector<std::set<int>> mergeStates(const std::vector<std::set<int>> & vectorE ) {
    std::vector<std::set<int>> new_vector;

    ...

    return new_vector;
}

answered Dec 14 '17 at 09:47

Sekkmer

103
1
12

score -1 · Answer 4 · answered Dec 14 '17 at 09:46

The end iterator used by the range-based for is determined prior to the loop. Since you erase() during the iteration, the end actually changes. Obtaining the iterator from the result of the erase() is insufficient as the end also changed. I think you can get away not using range-based for loops for the ranges you erase from.

Modifying set while iterating gives me segfault

Edit : I got it to work !

4 Answers4