libstdc++/8195: n-th algorithm (STL) doesn`t work properly

Belov, Eugeny Eugeny_Belov@stl.sarov.ru
Fri Oct 11 08:42:00 GMT 2002


    Hello Wolfgang

  I am understanding that the principle of this algorithm (in simple 
terms) is to divide the sequence into 2 parts like this:
smaller elements , n-th element, bigger elements,  and in the general 
case both parts can be unsorted.
  But the real problem in this case is that smaller elements comes after 
n-th ("n-th" is the integer with value 12 - the biggiest of all other 
elements), i.e. the sequence after using the nth_element() is "4 4 5 6 6 
6 9 _12_ 8 10" and in this case I think the n-th algorithm 
implementation make a mistake.

With best regards.
Eugeny.


Wolfgang Bangerth wrote:

>This is not a bug, so may be closed.
>
>nth_element does not sort the _entire_ array, it only makes sure that the 
>elements before the nth-pointer are smaller, and the ones behind that are 
>larger than the element pointed to by nth (the second argument). It makes 
>no guarantees that each of these two parts of the entire range is sorted 
>itself.
>
>Regards
>  Wolfgang
>
>-------------------------------------------------------------------------
>Wolfgang Bangerth              email:           bangerth@ticam.utexas.edu
>                               www: http://www.ticam.utexas.edu/~bangerth
>



More information about the Gcc-bugs mailing list