[libc++] Implementation of std::map::erase() in libc++ doesn't match that in libstdc++

Hi all,

We've encountered an incompatibility between libc++ and libstdc++: for
std::map::erase(pos) libstdc++ (and MSVS as well) first removes the
item from a map (a) and then calls its destructor (b), while libc++
calls the destructor before changing the map structure.

This results in a crash described at
https://code.google.com/p/chromium/issues/detail?id=358707: the item
that's being erased from the map queries that map in the destructor
calls some methods for the elements it finds. With libc++ that item
manages to find itself (in an inconsistent state, since it's in the
destructor already) and crashes.

Does the standard specify the order of (a) and (b), or it's incorrect
to rely on the order provided by some of the libraries?

TIA,
Alexander Potapenko
Software Engineer
Google Moscow

My belief is that the correct answer is (b).

As far as I can tell, the standard makes no mention of this.
[ map::erase has no special requirements, and the general container requirements don’t say anything. ]

However, libc++’s behavior seems a bit odd to me, too.
I committed revision 206024 to change this.

— Marshall

> Hi all,
>
> We've encountered an incompatibility between libc++ and libstdc++: for
> std::map::erase(pos) libstdc++ (and MSVS as well) first removes the
> item from a map (a) and then calls its destructor (b), while libc++
> calls the destructor before changing the map structure.
>
> This results in a crash described at
> https://code.google.com/p/chromium/issues/detail?id=358707: the item
> that's being erased from the map queries that map in the destructor
> calls some methods for the elements it finds. With libc++ that item
> manages to find itself (in an inconsistent state, since it's in the
> destructor already) and crashes.
>
> Does the standard specify the order of (a) and (b), or it's incorrect
> to rely on the order provided by some of the libraries?

My belief is that the correct answer is (b).

As far as I can tell, the standard makes no mention of this.
[ map::erase has no special requirements, and the general container
requirements don’t say anything. ]

However, libc++’s behavior seems a bit odd to me, too.
I committed revision 206024 to change this.

Speaking of spec-compliant-but-odd things: libc++'s std::random_shuffle
walks the array backwards, while libstdc++ and msvs's implementation walk
forward. We used to have code that called random_shuffle with a fixed
generator and relied on that producing always the same shuffle, but
libc++'s shuffle was different than the one produced by other standard
libraries. Maybe you want to change this too.

(Not required for spec compliance, but it'd make libc++ less surprising. In
Chromium, we've stopped using random_shuffle in this case since if we need
this property and the spec doesn't guarantee it, relying on it seems like a
pretty bad idea! But it might be nice for other projects.)

That seems … wrong to me.

The only guarantee you get from random_shuffle is that any output is as likely to occur as any other output.
I suspect (but the standard doesn’t require, as far as I can tell), if you give it the same inputs, and a RNG that spits out the same random sequence, you should get the same output each time, but there’s nothing about a “correct” result.

Exactly correct.

I’m less inclined to change this, since:

  1. There’s nothing in the standard that says anything about order of operations.
  2. random_shuffle is deprecated in C++14.

— Marshall

> Hi all,
>
> We've encountered an incompatibility between libc++ and libstdc++: for
> std::map::erase(pos) libstdc++ (and MSVS as well) first removes the
> item from a map (a) and then calls its destructor (b), while libc++
> calls the destructor before changing the map structure.
>
> This results in a crash described at
> https://code.google.com/p/chromium/issues/detail?id=358707: the item
> that's being erased from the map queries that map in the destructor
> calls some methods for the elements it finds. With libc++ that item
> manages to find itself (in an inconsistent state, since it's in the
> destructor already) and crashes.
>
> Does the standard specify the order of (a) and (b), or it's incorrect
> to rely on the order provided by some of the libraries?

My belief is that the correct answer is (b).

As far as I can tell, the standard makes no mention of this.
[ map::erase has no special requirements, and the general container
requirements don’t say anything. ]

However, libc++’s behavior seems a bit odd to me, too.
I committed revision 206024 to change this.

Speaking of spec-compliant-but-odd things: libc++'s std::random_shuffle
walks the array backwards, while libstdc++ and msvs's implementation walk
forward. We used to have code that called random_shuffle with a fixed
generator and relied on that producing always the same shuffle, but
libc++'s shuffle was different than the one produced by other standard
libraries. Maybe you want to change this too.

That seems … wrong to me.

The only guarantee you get from random_shuffle is that any output is as
likely to occur as any other output.

Sure, but in practice there really are only two ways one could write
Fisher-Yates :slight_smile: (But keeping this the code as-is is certainly fine.)

> Hi all,
>
> We've encountered an incompatibility between libc++ and libstdc++: for
> std::map::erase(pos) libstdc++ (and MSVS as well) first removes the
> item from a map (a) and then calls its destructor (b), while libc++
> calls the destructor before changing the map structure.
>
> This results in a crash described at
> https://code.google.com/p/chromium/issues/detail?id=358707: the item
> that's being erased from the map queries that map in the destructor
> calls some methods for the elements it finds. With libc++ that item
> manages to find itself (in an inconsistent state, since it's in the
> destructor already) and crashes.
>
> Does the standard specify the order of (a) and (b), or it's incorrect
> to rely on the order provided by some of the libraries?

My belief is that the correct answer is (b).

As far as I can tell, the standard makes no mention of this.
[ map::erase has no special requirements, and the general container
requirements don’t say anything. ]

However, libc++’s behavior seems a bit odd to me, too.
I committed revision 206024 to change this.

Speaking of spec-compliant-but-odd things: libc++'s std::random_shuffle
walks the array backwards, while libstdc++ and msvs's implementation walk
forward. We used to have code that called random_shuffle with a fixed
generator and relied on that producing always the same shuffle, but
libc++'s shuffle was different than the one produced by other standard
libraries. Maybe you want to change this too.

That seems … wrong to me.

The only guarantee you get from random_shuffle is that any output is as
likely to occur as any other output.

Sure, but in practice there really are only two ways one could write
Fisher-Yates :slight_smile: (But keeping this the code as-is is certainly fine.)

The libc++ algorithm is Fisher-Yates; the libstdc++ algorithm is not.
Fisher-Yates incrementally builds a random sequence by repeatedly appending
a randomly-selected element from the unchosen set, and that's what libc++
does. The libstdc++ algorithm incrementally builds a random sequence by
repeatedly swapping the next element of the unchosen set into a random
position within the already-built random sequence (this is a time-reversal
of Fisher-Yates).

I suspect (but the standard doesn’t require, as far as I can tell), if you