Can anyone spot the bug in this code?

[Disch]

Cookie if someone can spot it. I'm scratching my head.

void MapBlock::trimDeadEnds( wall_t& wall )
{
    for(auto i = wall.begin(); i != wall.end(); ++i)
    {
        auto j = wall.end() - 1;
        while( j > (i + c_DetItemsAhead) )
        {
            if( pointsWithinDistance( *i, *j, c_DetDistance ) )
            {
                i = wall.erase( i + 1, j ) - 1;
                break;
            }
            else
                --j;
        }
    }
}

wall_t is just a typedef of std::vector<some_type>
pointsWithinDistance doesn't do anything spectacular. It doesn't modify any passed params.

In MSVS 2010 Express... Release build works fine.
Debug build crashes on the call to erase() with an Assertion failure:
"Expression: vector iterator + offset out of range"

I don't see anything out of range here. Can somebody spot it?


It might be a bug in Visual Studio... but I *really* don't want to make that assumption unless I've ruled out all other avenues.

Thanks.


EDIT:

I suppose i + c_DetItemsAhead could be out of range.... (c_DetItemsAhead is ~6), but that wouldn't cause an issue in erase()... because if it's out of range the erase call won't happen.


EDIT 2:

Okay after commenting out the erase call, I'm also getting the same assertion failure on the i + c_DetItemsAhead line. Maybe I should rewrite this to use indexes instead of out-of-bound iterators....

[naraku9333]

Maybe testing the iterator + offset against wall.end() in first loop? for(auto i = wall.begin(); (i + c_detItemAhead) < wall.end(); ++i)

[JLBorges]

> Okay after commenting out the erase call, I'm also getting the same assertion failure on the i + c_DetItemsAhead line.

    for(auto i = wall.begin(); i != wall.end(); ++i)
    {
        // *** say, i == wall.end() - k , where k  >= 1
        
        // ...

        while( j > (i + c_DetItemsAhead) ) 
        //  i + c_DetItemsAhead  is undefined for any i where c_DetItemsAhead > k  

[Disch]

Yeah changing it to use indexes works just fine. Guess invalid iterators are invalid even if you don't dereference them:

void MapBlock::trimDeadEnds( wall_t& wall )
{
    for(std::size_t i = 0; i < wall.size(); ++i)
    {
        auto j = wall.size() - 1;
        while( j > (i + c_DetItemsAhead) )
        {
            if( pointsWithinDistance( wall[i], wall[j], c_DetDistance ) )
            {
                wall.erase( i + 1 + wall.begin(), j + wall.begin() );
                break;
            }
            else
                --j;
        }
    }
}

Thanks everyone.

[JLBorges]

> Guess invalid iterators are invalid even if you don't dereference them:

Since iterators are an abstraction of pointers, their semantics is a generalization of most of the semantics of pointers in C++. - IS

We can never get an invalid iterator, just as we can never get an invalid pointer (except in the special case of a pointer/iterator that is uninitialized) unless we had first caused undefined behavoiur.

std::list<int> seq = { 0, 1, 2, 3, 4 } ;
int array[5] = { 0, 1, 2, 3, 4 } ;

auto iter = seq.end() ; // fine
int* ptr = array +5 ; // fine
// *iter ; // error; undefined behaviour
// *ptr ; // error; undefined behaviour
// ++iter ; // error; undefined behaviour
// ++ptr ; // error; undefined behaviour
--iter ; // fine
--ptr ; // fine

iter = seq.begin() ; // fine
ptr = array ; // fine
// --iter ; // // error; undefined behaviour
// --ptr ; // // error; undefined behaviour
*iter ; // fine
*ptr ; // fine
++iter ; // fine
++ptr ; // fine

std::list<int>::iterator wild ; // wild may or may mot be initialized (implementation defined)
wild == seq.end() ; // may result in undefined behaviour  

EDIT: It suddenly occurred to me that what I had posted earlier was wrong.

We can never get an invalid iterator, just as we can never get an invalid pointer (except in the special case of a pointer/iterator that is uninitialized) unless we had first caused undefined behavoiur.

We can. For example:

std::vector<int> seq = [code]std::list<int> seq = { 0, 1, 2, 3, 4 } ;
auto iter = seq.begin() ;
seq.insert( iter, 9 ) ; // iter is no longer valid after this
// there is undefined behaviour only if we try to use the object