Je t’embrasse Salutations from Silicon Valley, California

20Jan/120

std::list iterate + erase

I had an interesting problem the other day where I needed to iterate over an std::list, removing invalid items from that list. The only problem was that the list is a list of pointers, each pointing to allocated values that must be freed.

Here is what I started with:

#include <stdio.h>
#include <list>
using std::list;

struct COORD { int x,y; };

int i,j;
struct COORD *c;
list<struct COORD *> coordList;
list<struct COORD *>::iterator it1;

/* Prep the list */
for (i=0, j=0; i<10, j<10; i++, j++) {
    c = (struct COORD *)malloc(sizeof(struct COORD));
    c->x = i; c->y = j;
    coordList.push_back(c);
}

/* Display while erasing all - for loop */
for (it1=coordList.begin(); it1!=coordList.end(); it1++) {
    c = (*it1);
    printf("A: (%d,%d)\n", c->x, c->y);
    coordList.erase(it1); /* segfault */
    free(c); 
}

As you can see, the problem with this is in the .erase() call. As soon as the item is taken out of the list, "it" still points to that item. Even if you get lucky once or twice, eventually "it1" will point to a value outside of the bounds of coordList.begin() and coordList.end(). At this point, you will continue, because it1!=coordList.end()... and you will segfault when you try to erase the now-invalid iterator.

The fix is to not auto-increment the iterator.

/* Display while erasing all - for loop */
for (it=coordList.begin(); it!=coordList.end(); ) {
    c = (*it);
    printf("A: (%d,%d)\n", c->x, c->y);
    coordList.erase(it++);
    free(c);
}

Note that by removing the increment step from the loop argument, we have to do the increment ourselves.

Of course, you could also use the power of the .erase() method, which states that the return value is:

A bidirectional iterator pointing to the new location of the element that followed the last element erased by the function call, which is the list end if the operation erased the last element in the sequence.

Because of that we can do something a bit fancier:

/* Display while erasing some - for loop #2 */
for (it=coordList.begin(); it!=coordList.end(); ) {
    c = (*it);
    printf("B: (%d,%d)\n", c->x, c->y);
    it = coordList.erase(it);
    free(c);
}

See how we set the iterator value to the next available one by using the return value of the .erase() method. This is a relatively elegant solution, but that also is because we are always updating the iterator through use of the .erase() method. If we had to limit the erase, only deleting odd values (for example), we would have to remember to increment that iterator (otherwise the loop would stay pointing at the same list element forever).

/* Display while erasing some - for loop #3 */
for (it=coordList.begin(); it!=coordList.end(); ) {
    c = (*it);

    if ((c->x % 2) == 1) {
        printf("C: (%d,%d)\n", c->x, c->y);
        it = coordList.erase(it);
        free(c);
    }
    else {
        ++it;
    }
}

That's it. My trial-and-error wisdom, passed on.

Filed under: C/C++ No Comments