Runs with GCC, crashes with MSVC

[Derek]

#include <deque>
#include <iostream>
using namespace std;

int main()
{
deque<int> foo;
foo.push_back(42);
deque<int>::reverse_iterator it = foo.rbegin();
while (it != foo.rend())
{
cout << "start of loop\n";
int temp = *it++;
foo.pop_back();
}
return 0;
}

When compiled with GCC 3.3.1, the program above prints
"start of loop" once and exits gracefully (as I would
expect it to do).

When compiled with MSVC 6 (SP6), it displays "start of
loop" twice and crashes.

Who is right?

 

[Ron Natalie]

When compiled with GCC 3.3.1, the program above prints
"start of loop" once and exits gracefully (as I would
expect it to do).

When compiled with MSVC 6 (SP6), it displays "start of
loop" twice and crashes.

Who is right?

Hmm... the operative rule is that "an erase at either end of the deque invalidates
only the interators and references to the erased elements." Your iterator is pointing
at rend() which isn't the erased element, so it should fail the while() test the second
time around.

 

[Andre Kostur]

#include <deque>
#include <iostream>
using namespace std;

int main()
{
deque<int> foo;
foo.push_back(42);
deque<int>::reverse_iterator it = foo.rbegin();
while (it != foo.rend())
{
cout << "start of loop\n";
int temp = *it++;
foo.pop_back();
}
return 0;
}

When compiled with GCC 3.3.1, the program above prints
"start of loop" once and exits gracefully (as I would
expect it to do).

When compiled with MSVC 6 (SP6), it displays "start of
loop" twice and crashes.

Who is right?

Both According to Josuttis, you're working with an invalidated
iterator.

"Thus, any insertion or deletion invalidates all pointers, references,
and iterators that refer to other elements of the deque. The exception
is when elements are inserted at the front or the back."

 

[Victor Bazarov]

#include <deque>
#include <iostream>
using namespace std;

int main()
{
deque<int> foo;
foo.push_back(42);
deque<int>::reverse_iterator it = foo.rbegin();
while (it != foo.rend())
{
cout << "start of loop\n";
int temp = *it++;
foo.pop_back();

pop_back invalidates the iterator what pointed to the popped element.
In your case, since 'it' is a reverse iterator, it really points to
the element right after the one it gives when dereferenced. It's just
one of the iterator implementation tricks, I suppose. So, when you
say it = foo.rbegin(), it basically the same as it = foo.end(), but
with a twist. Now, it++ moves it to point to the last element, which
you promptly pop in the next statement. The iterator is invalid after
that.

}
return 0;
}

When compiled with GCC 3.3.1, the program above prints
"start of loop" once and exits gracefully (as I would
expect it to do).

When compiled with MSVC 6 (SP6), it displays "start of
loop" twice and crashes.

Who is right?

Both are right. You're trying to make use of an invalid iterator,
and therefore get undefined behaviour.

You probably should have done

while (!foo.empty())
{
cout << "start of loop\n;
int temp = *foo.rbegin(); // or int temp = foo.back();
foo.pop_back();
}

Victor

 

[Victor Bazarov]

Both According to Josuttis, you're working with an invalidated
iterator.

"Thus, any insertion or deletion invalidates all pointers, references,
and iterators that refer to other elements of the deque. The exception
is when elements are inserted at the front or the back."

Actually popping from the front or from the back, according to the
Standard, invalidates only the iterators that point to those objects.
The trouble is, the reverse iterators really point to the object one
past the one you think they point to.

Of course, Josuttis' rule is a bit more strict, so if you follow it,
you are less likely to make a mistake, although, you'd be restricted
more (..yeah, I suppose that's what 'strict' means, more restrictions,
right?...)

Victor

 

[Derek]

pop_back invalidates the iterator what pointed to
the popped element. In your case, since 'it' is a
reverse iterator, it really points to the element
right after the one it gives when dereferenced.
It's just one of the iterator implementation tricks,
I suppose. So, when you say it = foo.rbegin(),
it basically the same as it = foo.end(), but with
a twist. Now, it++ moves it to point to the
last element, which you promptly pop in the next
statement. The iterator is invalid after that.

Thanks, Victor. I had to think about it for a few
minutes, but that makes sense.

You probably should have done

while (!foo.empty())
{
cout << "start of loop\n;
int temp = *foo.rbegin();
foo.pop_back();
}

Then maybe I can't do what I need with a deque. In
the full program the pop_back is conditional. What
I wanted is to iterate over all elements in reverse
and pop_back only if it meets some condition and
exit the loop otherwise:

#include <deque>
#include <iostream>
using namespace std;

int main()
{
deque<int> foo;
foo.push_back(42);
deque<int>::reverse_iterator it = foo.rbegin();
while (it != foo.rend())
{
cout << "start of loop\n";
int temp = *it++;
if (condition(temp))
foo.pop_back();
else
break;
}
return 0;
}

 

[Victor Bazarov]

Thanks, Victor. I had to think about it for a few
minutes, but that makes sense.


Then maybe I can't do what I need with a deque. In
the full program the pop_back is conditional. What
I wanted is to iterate over all elements in reverse
and pop_back only if it meets some condition and
exit the loop otherwise:

#include <deque>
#include <iostream>
using namespace std;

int main()
{
deque<int> foo;
foo.push_back(42);
deque<int>::reverse_iterator it = foo.rbegin();
while (it != foo.rend())
{
cout << "start of loop\n";
int temp = *it++;
if (condition(temp))
foo.pop_back();
else
break;
}
return 0;
}

The correct way to write this would be

while (condition(foo.back()))
foo.pop_back();

Victor

 

[Ali Cehreli]

#include <deque>
#include <iostream>
using namespace std;

int main()
{
deque<int> foo;
foo.push_back(42);
deque<int>::reverse_iterator it = foo.rbegin();

while (it != foo.rend())
{
cout << "start of loop\n";
int temp = *it++;
foo.pop_back();

The use of a post-increment operator is essential here. The two lines
above is effectively the equivalent of these lines:

deque<int>::reverse_iterator tempIter = it;
++it;
int temp = *tempIter;
foo.pop_back();

If ++it line was put after pop_back, I can understand how it would be
undefined behavior. But when there is only one item, 'it' now should
be equal to foo.rend(); not invalid.

What is invalid is the temporary iterator (tempIter) that the compiler
generates to accomplish the post-increment operation. We never touch
that inaccessible temporary.

}
return 0;
}

When compiled with GCC 3.3.1, the program above prints "start of loop"
once and exits gracefully (as I would expect it to do).

When compiled with MSVC 6 (SP6), it displays "start of loop" twice and
crashes.

Who is right?

The way I understand it, g++ is behaving correctly
here. Implementation details should not matter because you are not
using an invalid iterator.

Ali

 

[Ali Cehreli]

The use of a post-increment operator is essential here. The two lines
above is effectively the equivalent of these lines:

deque<int>::reverse_iterator tempIter = it;
++it;
int temp = *tempIter;
foo.pop_back();

I don't this this is relevant or even interesting here

What is invalid is the temporary iterator (tempIter) that the compiler
generates to accomplish the post-increment operation. We never touch
that inaccessible temporary.
[...]

Implementation
details should not matter because you are not using an invalid iterator.

I don't think so anymore

I guess if an iterator is invalid, even comparing it with another
iterator should be considered as using it. I don't think even that
would be valid.

#include <deque>
#include <assert.h>

int main()
{
typedef std::deque<int> Numbers;

Numbers numbers;
numbers.push_back(42);

Numbers::iterator it = numbers.begin();
++it;

// We must be at the end
assert(it == numbers.end());

numbers.pop_back();

// Now is this check legal? (I don't think so.)
assert(it == numbers.end());
}

Ali

 

[Roland Wunderer]

#include <deque>
#include <iostream>
using namespace std;

int main()
{
deque<int> foo;
foo.push_back(42);
deque<int>::reverse_iterator it = foo.rbegin();
while (it != foo.rend())
{
cout << "start of loop\n";
int temp = *it++;
foo.pop_back();
}
return 0;
}

When compiled with GCC 3.3.1, the program above prints
"start of loop" once and exits gracefully (as I would
expect it to do).

When compiled with MSVC 6 (SP6), it displays "start of
loop" twice and crashes.

Who is right?

Seems foo.rend() ist changed throuch foo.pop_back().
Try this:
----------------------------------------------------------------------------
---
deque<int>::reverse_iterator it_end = foo.rend();
while (it != it_end)
{
int temp = *it++;
foo.pop_back();
}

 

[tom_usenet]

The correct way to write this would be

while (condition(foo.back()))
foo.pop_back();

rather:

while (!foo.empty() && condition(foo.back()))
foo.pop_back();

Tom