push_back to list in loop

Question

I have a problem with pushing elements to a QList when iterating over it. Let's see example code below:

typedef struct
{
    int a[2];
} myType;

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    MainWindow w;

    QList<myType> list;

    // Create list
    for( int i = 0; i < 1000; i++)
    {
        list << (myType){ i, i };
    }

    int iteration = 0;

    for ( auto &i : list )
    {
        i.a[1] = 5;

        if ( ! (i.a[0] % 10) )
        {
            list.push_back( (myType){ 7, 7 } );
        }
        iteration++;
    }

    w.show();
    return a.exec();
}

When I debug the code I have a segmentation fault (i got value 0xfeeefeeefeeefeee):

What is the reason?

It is undefined behavior to change the container you're looping on in a ranged-based `for` loop. — PaulMcKenzie, Jul 11 '20 at 06:09
This example is not great but what is a correct way to add/remove elements from the list depending from items values? — Mikolaj, Jul 11 '20 at 06:24
Use a regular loop, or restructure your loop, or use the [erase-remove](https://stackoverflow.com/questions/39019806/using-erase-remove-if-idiom) idiom. A ranged-based `for` is not a panacea -- it has wide usage, but it's utility is restricted in just iterating over a container using simpler and safer syntax -- nothing more, nothing less. If you want to do all sorts of things to the container you're iterating over, you need to formulate your own looping construct to do so and not use ranged-based `for`. — PaulMcKenzie, Jul 11 '20 at 06:26

score 1 · Accepted Answer · answered Jul 11 '20 at 06:25

1

The reason for the segmentation fault is that altering the size of the container that you are looping over in a ranged-based for loop is undefined behavior. Thus the loop needs to be rewritten.

Looking at your code, you could still use the ranged-based for, but not alter the list. The following code seems to be equivalent (but not tested):

int numExtra = 0;
for ( auto &i : list )
{
    i.a[1] = 5;

    if ( ! (i.a[0] % 10) )
        ++numExtra;
    iteration++;
}

for (int i = 0; i < numExtra; ++i)
    list.push_back( (myType){ 7, 7 } );

Since the value being added to the list is the same value, the code just counts up the number of eventual push_back calls that will be invoked. After the initial loop is completed, we just call push_back a total of numExtra times.

answered Jul 11 '20 at 06:25

PaulMcKenzie

34,698
4
24
45

Thank you, I will test it. If I would have more complex structure to add, do you think it's a good idea to create other list containing new elements and append it after loop? I think it could be efficient. – Mikolaj Jul 11 '20 at 06:29
1

You could do that. You should measure the performance before drawing any conclusions as to whether it is efficient or not. – PaulMcKenzie Jul 11 '20 at 06:32
`altering the size of the container that you are looping over in a ranged-based for loop is undefined behavior` I'm not sure this is true, performing operations that invalidate iterators inside a range based for loop is undefined but changing the size of a container doesn't always invalidate iterators, e.g. `std::list` doesn't invalidate iterators on insertion and `std::vector` invalidates on capacity changes not size changes – Alan Birtles Jul 11 '20 at 07:21

score 0 · Answer 2 · answered Jul 11 '20 at 08:42

If you use iterator based for loop, this will still work if you are only appending to the list:

for ( auto it = list.begin(); it != list.end(); ++it )
{
    it->a[1] = 5;

    if ( ! (it->a[0] % 10) )
    {
        list.push_back( myType({ 7, 7 }) );
    }
    iteration++;
}

With a range-based for, list.end() is evaluated only once at the start and so will become invalid when a new item is inserted.

push_back to list in loop

2 Answers2