<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Apr 15, 2014 at 10:38 AM, Nico Weber <span dir="ltr"><<a href="mailto:thakis@chromium.org" target="_blank">thakis@chromium.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div class="h5">On Tue, Apr 15, 2014 at 7:50 AM, Marshall Clow <span dir="ltr"><<a href="mailto:mclow.lists@gmail.com" target="_blank">mclow.lists@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><div><div>On Apr 11, 2014, at 9:35 AM, Nico Weber <<a href="mailto:thakis@chromium.org" target="_blank">thakis@chromium.org</a>> wrote:</div>
<br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Apr 11, 2014 at 1:29 AM, Marshall Clow <span dir="ltr"><<a href="mailto:mclow.lists@gmail.com" target="_blank">mclow.lists@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>On Apr 8, 2014, at 1:47 PM, Alexander Potapenko <<a href="mailto:glider@google.com" target="_blank">glider@google.com</a>> wrote:<br>
<br>
> Hi all,<br>
><br>
> We've encountered an incompatibility between libc++ and libstdc++: for<br>
> std::map::erase(pos) libstdc++ (and MSVS as well) first removes the<br>
> item from a map (a) and then calls its destructor (b), while libc++<br>
> calls the destructor before changing the map structure.<br>
><br>
> This results in a crash described at<br>
> <a href="https://code.google.com/p/chromium/issues/detail?id=358707" target="_blank">https://code.google.com/p/chromium/issues/detail?id=358707</a>: the item<br>
> that's being erased from the map queries that map in the destructor<br>
> calls some methods for the elements it finds. With libc++ that item<br>
> manages to find itself (in an inconsistent state, since it's in the<br>
> destructor already) and crashes.<br>
><br>
> Does the standard specify the order of (a) and (b), or it's incorrect<br>
> to rely on the order provided by some of the libraries?<br>
<br>
</div>My belief is that the correct answer is (b).<br>
<br>
As far as I can tell, the standard makes no mention of this.<br>
[ map::erase has no special requirements, and the general container requirements don’t say anything. ]<br>
<br>
However, libc++’s behavior seems a bit odd to me, too.<br>
I committed revision 206024 to change this.<br></blockquote><div><br></div><div>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.</div>
</div></div></div></blockquote><div><br></div></div>That seems … wrong to me.</div><div><br></div><div>The only guarantee you get from random_shuffle is that any output is as likely to occur as any other output.</div></div>
</blockquote><div><br></div></div></div><div>Sure, but in practice there really are only two ways one could write Fisher-Yates :-) (But keeping this the code as-is is certainly fine.)</div></div></div></div></blockquote>
<div><br></div><div>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).</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word"><div>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.</div>
<div><br></div><div><div><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">
<div><br></div><div>(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! </div>
</div></div></div></blockquote><div><br></div></div>Exactly correct.</div><div><div><br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>But it might be nice for other projects.)</div>
</div></div></div></blockquote><br></div></div><div>I’m less inclined to change this, since:</div><div><span style="white-space:pre-wrap"> </span>1) There’s nothing in the standard that says anything about order of operations.</div>
<div><span style="white-space:pre-wrap"> </span>2) random_shuffle is deprecated in C++14.</div><span><font color="#888888"><div><br></div><div>— Marshall</div><div><br></div></font></span></div></blockquote>
</div></div><br></div></div>
<br>_______________________________________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br>
<br></blockquote></div><br></div></div>