Oh wow, good catch.<div><br></div><div>Note that I found a bug in msvc 2010's vector, related to the new cxx11 emplace methods, that was also a painful learning experience... Without the quick bug fix from the compiler authors like you found ( I ended up patching the standard headers on my own machine)<br>
<br>On Saturday, 21 December 2013, Sylvain Bougerel wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi All,<div><br></div><div>I found the issue. After few weeks of recompiling, adding debug statements everywhere, and trying to understand why sometime std::nth_element() does not seem to behave well on my machine, I gave up. That's when I googled "nth_element gcc bug". And of course:</div>
<div><a href="http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800" target="_blank">http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800</a></div><div><br></div><div><div>% g++ --version</div><div>g++ (GCC) 4.8.2</div></div><div>
The bug is in libstdc++ -- also used by Clang -- that explains why I was getting the same issue from the 2 different compilers.</div>
<div><br></div><div>I downgraded to 4.8.1 and everything is working. I lost sooo much time on this, not to mention I completely freaked out :(</div><div><br></div><div>Sylvain</div></div><div><br><br><div>
On Mon, Nov 25, 2013 at 12:27 PM, Sylvain Bougerel <span dir="ltr"><<a>sylvain.bougerel.devel@gmail.com</a>></span> wrote:<br><blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<p dir="ltr">Paul,</p>
<p dir="ltr">You are right. I need to revisit both the explanation and the understanding of the crash.</p>
<p dir="ltr">The issue I am getting happens randomly and never happens with partial_sort().</p>
<p dir="ltr">I will investigate more. I will keep you updated.</p>
<p dir="ltr">Regards, <br>
Sylvain </p><div><div>
<div>On Nov 25, 2013 10:57 AM, "Paul" <<a>elegant_dice@yahoo.com</a>> wrote:<br type="attribution"><blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div style="font-size:12pt;font-family:times new roman,new york,times,serif">Hi Sylvain,<br><br>I just saw this email by chance, not sure why it didn't show up bigger in the inbox...<br><br><br><a href="http://www.cplusplus.com/reference/algorithm/nth_element/" target="_blank">http://www.cplusplus.com/reference/algorithm/nth_element/</a><br>
<br>Quote: <br>The
other elements are left without any specific order, except that none of
the elements preceding nth are greater than it, and none of the
elements following it are less.<br><br>So your comment regarding Guarantees cannot be correct.<br>Please check your code again, I assume there is some other problem that is the source of the issue.<br><br>cheers,<br>Paul<br>
<div><span><br></span></div><div style="display:block"> <br> <br> <div style="font-family:times new roman,new york,times,serif;font-size:12pt"> <div style="font-family:times new roman,new york,times,serif;font-size:12pt">
<div dir="ltr"> <font face="Arial"> On Sunday, 24 November 2013 10:19 PM, Sylvain Bougerel <<a>sylvain.bougerel.devel@gmail.com</a>> wrote:<br> </font> </div>
<div><div><div><div dir="ltr">Hi Sebastien and others,<div><br clear="none"></div><div>I will retry with the new addresses.</div><div><br clear="none"></div><div>The real reason why I wanted the latest sources was to do performance comparisons between libkdtree++ and
spatial (<a rel="nofollow" shape="rect" href="https://sourceforge.net/projects/spatial/" target="_blank">https://sourceforge.net/projects/spatial/</a>).</div>
<div><br clear="none"></div><div>During the course of the performance comparisons, I insert 1000000 points in 3 or 9 dimensions and watch how the 2 libraries behave, on insertion and insertion with optimization.</div><div>
<br clear="none"></div><div>
This has lead me to the discovery of one bug very important bug and its fix. Spatial originally (a year ago) suffered from the same issue, so I was able to identify it quickly.</div><div><br clear="none"></div><div>In the KDTree::_M_optimize, the body in the version I have is:</div>
<div><br clear="none"></div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div>
<div>
{</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::nth_element(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div><div><br clear="none"></div>
<div>But it should be:</div>
<div><br clear="none"></div><div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div>
<div> {</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::partial_sort(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div></div><div><br clear="none">
</div><div>
(notice the change from std::nth_element to std::partial_sort)</div><div><br clear="none"></div><div>Using nth_element here is a erroneous, because it does not guarantee that everything in the sequence [__A, __m) is lower than _m nor that everything in the sequence (__m, __B] is greater than __m. This is expected from the algorithm because it operates on a subset where the</div>
</div></div></div></div></div></div></div></div></div></blockquote></div></div></div></blockquote></div></div></blockquote></div>