Accessing list element pointed by an iterator

Question

The natural answer would be to dereference the iterator and get the value. However, I'm stuck at using VC++ 2010 which doesn't allow dereferencing the list iterator (or does it?) I'm confused because, at one point, I need to dereference two list iterators and compare their values using: (*it) == (*it2) The program crashes with an error, only due to this line. I'm also dereferencing the iterator in a statement: printf("%d\n", (*it)); This works perfectly fine though. So, is there any way to access an element without dereferencing or using a cliext::list.

for (it=sList.begin(); it != sList.end(); it++)
{
    for (it2=it; it2 != sList.end(); it2++)
    {
        it2++;
        if ((*it) == (*it2))
        {
           sList.erase(it, it2);
        }
        it2--;
    }
}

The error I get is:

Debug Assertion Failed

Expression: list iterator not dereferencable

Surprisingly the same code runs without a problem when compiled on DevC++ (MinGW)

Solution 1

You can in fact dereference list iterators. If you couldn't, your comparison code wouldn't have even compiled. Most likely you're accidentally dereferencing an end iterator though rather than a valid one, causing the crash. Without more code it's hard to make further observations.

EDIT: I can't make out quite what it is you're trying to do. The code you've written erases all the elements between two equal elements. I'll assume you're actually trying to remove all the duplicate elements, and that sorting the list first for performance isn't a concern/option.

EDIT2: I saw in a comment below you really want to delete the range. Updated my code.

Then try something like this:

for (it=sList.begin(); it != sList.end(); ++it)
{
    it2 = it;
    ++it2;
    while(it2 != sList.end())
    {
        if ((*it) == (*it2))
        {
           it = it2 = sList.erase(it, it2);  // Reset it as well since it will be blown away. It'll still point to the same value it did before though.
        }
        else
            ++it2;
    }
}

Solution 2

"select" Isn’t Broken.

It is rare to find a bug in the OS or the compiler, or even a third-party product or library. The bug is most likely in the application. - from The Pragmatic Programmer

It's highly likely due to your problem, not MS. Make it sure that your iterators are not invalidated while you are using them. You could accidentally erase the element which invalidate the iterator. Check this thread: What is the lifetime and validity of C++ iterators? and Good Luck! :)

UPDATE:

As I mentioned earlier, you are invalidating your iterators by erasing them in the middle of the loop. See my code below to do it properly.

std::list<int>::iterator EraseElements(std::list<int>& sList, std::list<int>::iterator start)
{
    for (std::list<int>::iterator itor1 = start; itor1 != sList.end(); ++itor1)
    {
        std::list<int>::iterator itor2(itor1);
        ++itor2;

        for ( ; itor2 != sList.end(); ++itor2)
        {
            if ((*itor1) == (*itor2))
            {
                return sList.erase(itor1, itor2);
            }
        }
    }

    return sList.end();
}


void main()
{
    // Test
    list<int> sList;
    sList.push_back(1);

    // elements will be erased
    sList.push_back(2);
    sList.push_back(3);
    //
    sList.push_back(2);

    sList.push_back(4);
    sList.push_back(5);

    // elements will be erased
    sList.push_back(6);
    sList.push_back(7);
    //
    sList.push_back(6);


    list<int>::iterator next = sList.begin();
    while (next != sList.end())
    {
        next = EraseElements(sList, next);
    }

    // It will print 1 2 4 5 6
    for (std::list<int>::const_iterator itor = sList.begin(); itor != sList.end(); ++itor)
    {
        cout << *itor << endl;
    }
}

Solution 3

Its surely your code. It has two problems as far as I can see. Checkout the comments.

for (it2=it; it2 != sList.end(); it2++)
    {
        it2++;
            // there is no guarantee that it2 will now be valid
            // it should be validated again
        if ((*it) == (*it2))
        {
            // you should not modify the list here.
            // this will invalidate your iterators by default.
           sList.erase(it, it2);
        }
        it2--;
    }

Solution 4

Try this instead:

for (it=sList.begin(); it != sList.end(); it++)
{
    for (it2=sList.end()-1; it2 != it+1; it2--)
    {
        if ((*it) == (*it2))
        {
            it = sList.erase(it, it2)-1;
            break;
        }
    }
}

This new version avoids two errors in the original version of the code. First, the code now properly handles the edge conditions of the inner for loop. In the original code, the for loop allowed it2 to go up to sList.end()-1, but then the next line incremented it to sList.end() on the last iteration. The next line then dereferenced this (invalid) iterator which is one past the last value of the list (because that's what end returns, it's not an iterator to the last value of the list).

Second, calling erase invalidates any iterators pointing to any of the values erased (which in this case would including any iterators from it to it2-1). By starting at the end of the list and working our way forward, we no longer have to continue iterating when we find the value, and can break from the inner loop once we find it. erase returns an iterator to the next element in the list after the elements deleted (which would be the next element we want to try for it). But since the for loop increments it, we subtract 1 from what's returned by erase so that it points to the right element once it's incremented at the beginning of the next loop iteration. (Note that in the case that it points to the first element, we actually temporarily set it to point an element before the beginning of the list; however, this is only temporary and we don't dereference the iterator while it's pointing outside the list).

Note that this preserves the original behavior of the code for the case 0 2 3 4 5 1 6 7 8 0 9 10 11 1. You haven't explicitly stated what order the deletes should occur (should the elements between 0's be erased first, or the elements between 1's, or do we need to add additional logic to actually erase the whole range except for the first 0 and 1?), but this code behaves like the original and erases the numbers in between the 0's and ignores the fact that the 9 10 11 afterwards was original in between matching 1's.

View more solutions