C++ vector of set gives segmentation fault after performing push_back

Question

I have created a vector of sets in my program, and I need to go through each of the sets. In case a specific element is found in the set, I need to add a new set to the vector. However, this gives me a segmentation fault as soon as my array's counter reaches the elements that I inserted later (within the loop). In the following code, switching on list.push_back(cS) gives me a segmentation fault.

int main(void)  {
set<int> cS;
vector<set<int> > list;

cS.insert(1);
list.push_back(cS);

cS.insert(2);
list.push_back(cS);

for (int ctr = 0; ctr < list.size(); ctr++)
{
    for (set<int>::iterator itr = list[ctr].begin(); itr != list[ctr].end(); itr++)
    {
        if (*itr == 1 || *itr == 2)
        {
            cS.clear();
            cS.insert(3);
            //list.push_back(cS);
        }
    }
}

for (int ctr = 0; ctr < list.size(); ctr++)
{
    for (set<int>::iterator itr = list[ctr].begin(); itr != list[ctr].end(); itr++)
    {
        cout << *itr << endl;
    }
}

return 0;
}

I would be grateful if someone could explain why this gives an error (in gcc).

Thank you for going through my post.

Just out of curiosity, why do you use iterators for the set but not the vector? — Some programmer dude, Mar 23 '12 at 07:41
Out of habit, I guess. As far as I know, for a vector, using an iterator or an index are equivalent. — Arani, Mar 23 '12 at 16:13

Andreas Brinck · Accepted Answer · 2012-03-23T07:52:58.413

6

When you push_back into your vector you invalidate all references to elements in it in the case the vector needs to allocate more memory. In your case the iterator itr becomes invalid after the push_back. One solution would be to add the sets to a separate list (vector) and then append them all at once after the for loop:

vector<set<int> > add;
for (int ctr = 0; ctr < list.size(); ctr++)
{
    for (set<int>::iterator itr = list[ctr].begin(); itr != list[ctr].end(); itr++)
    {
        if (*itr == 1 || *itr == 2)
        {
            cS.clear();
            cS.insert(3);
            add.push_back(cS);
        }
    }
}
list.insert(list.end(), add.begin(), add.end());

edited Mar 23 '12 at 07:52

answered Mar 23 '12 at 07:39

Andreas Brinck

51,293
14
84
114

In that case, is there no way to iterate through each element of the vector, while in special cases inserting some elements to it? – Arani Mar 23 '12 at 07:41
`push_back` doesn't *necessarily* invalidate iterators, some call to `push_back` might invalidate. – Nawaz Mar 23 '12 at 07:43
@user571376: use index-based iteration. – Nawaz Mar 23 '12 at 07:43
The exact rules here are covered in an FAQ post: http://stackoverflow.com/questions/6438086/iterator-invalidation-rules – je4d Mar 23 '12 at 07:44
@user571376: yeah, there are two ways it can work. One is to store indices instead of iterators (they can always be converted back into iterators when needed). The other is to call `reserve` on the vector in advance, to ensure that `push_back` doesn't need to reallocate. But that relies on you knowing the max size of the vector in advance – jalf Mar 23 '12 at 07:44
1

@Nawaz Correct, but the only way to code is to assume it does. – Andreas Brinck Mar 23 '12 at 07:45
@AndreasBrinck: Actually it depends. You can call `reserve` to set the maximum size if you know this in advance; then you can use `push_back` without problem. In other words, all that you need to make sure that vector doesn't reallocate memory. – Nawaz Mar 23 '12 at 07:47
Thank you Nawaz, Andreas Brinck and je4d for your solutions. They really helped, and I understood the concept of iterators a lot better. – Arani Mar 23 '12 at 07:57

C++ vector of set gives segmentation fault after performing push_back

1 Answers1