Runs with GCC, crashes with MSVC

#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?

re: Runs with GCC, crashes with MSVC

Derek wrote:[color=blue]
> #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();[/color]

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.
[color=blue]
> }
> 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?[/color]

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

re: Runs with GCC, crashes with MSVC

Derek <user@nospam.org> wrote in news:2lqkacFfntmjU1@uni-berlin.de:
[color=blue]
> #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?[/color]

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."

re: Runs with GCC, crashes with MSVC

Andre Kostur wrote:[color=blue]
> Derek <user@nospam.org> wrote in news:2lqkacFfntmjU1@uni-berlin.de:
>
>[color=green]
>>#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?[/color]
>
>
> 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."[/color]

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

re: Runs with GCC, crashes with MSVC

Victor Bazarov wrote:[color=blue]
>
> 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.[/color]

Thanks, Victor. I had to think about it for a few
minutes, but that makes sense.
[color=blue]
> You probably should have done
>
> while (!foo.empty())
> {
> cout << "start of loop\n;
> int temp = *foo.rbegin();
> foo.pop_back();
> }[/color]

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;
}

re: Runs with GCC, crashes with MSVC

Derek wrote:[color=blue]
> Victor Bazarov wrote:[color=green]
> >
> > 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.[/color]
>
> Thanks, Victor. I had to think about it for a few
> minutes, but that makes sense.
>[color=green]
> > You probably should have done
> >
> > while (!foo.empty())
> > {
> > cout << "start of loop\n;
> > int temp = *foo.rbegin();
> > foo.pop_back();
> > }[/color]
>
> 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;
> }[/color]

The correct way to write this would be

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

Victor

re: Runs with GCC, crashes with MSVC

"Derek" <user@nospam.org> wrote in message news:2lqkacFfntmjU1@uni-berlin.de...
[color=blue]
>
> 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?[/color]

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.

re: Runs with GCC, crashes with MSVC

On Fri, 16 Jul 2004 11:15:39 -0700, Derek wrote:
[color=blue]
> #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();[/color]

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.
[color=blue]
> }
> 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?[/color]

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

Ali

re: Runs with GCC, crashes with MSVC

On Fri, 16 Jul 2004 15:25:50 -0700, Ali Cehreli wrote:
[color=blue]
> On Fri, 16 Jul 2004 11:15:39 -0700, Derek wrote:
>[color=green]
>> #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();[/color]
>
> 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();[/color]

I don't this this is relevant or even interesting here :)
[color=blue]
> What is invalid is the temporary iterator (tempIter) that the compiler
> generates to accomplish the post-increment operation. We never touch
> that inaccessible temporary.[/color]

[...]
[color=blue]
> Implementation
> details should not matter because you are not using an invalid iterator.[/color]

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

re: Runs with GCC, crashes with MSVC

"Derek" <user@nospam.org> schrieb im Newsbeitrag
news:2lqkacFfntmjU1@uni-berlin.de...[color=blue]
> #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?[/color]
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();
}
----------------------------------------------------------------------------
---
Greetings
Roland

re: Runs with GCC, crashes with MSVC

On Fri, 16 Jul 2004 19:59:17 GMT, Victor Bazarov
<v.Abazarov@comAcast.net> wrote:
[color=blue]
>Derek wrote:[color=green]
>> Victor Bazarov wrote:[color=darkred]
>> >
>> > 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.[/color]
>>
>> Thanks, Victor. I had to think about it for a few
>> minutes, but that makes sense.
>>[color=darkred]
>> > You probably should have done
>> >
>> > while (!foo.empty())
>> > {
>> > cout << "start of loop\n;
>> > int temp = *foo.rbegin();
>> > foo.pop_back();
>> > }[/color]
>>
>> 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;
>> }[/color]
>
>The correct way to write this would be
>
> while (condition(foo.back()))
> foo.pop_back();[/color]

rather:

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

Tom