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

[Wolfgang Bangerth <bangerth at ticam dot utexas dot edu>]

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

Correct.

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

Why? The signature of the function is
  void nth_element(RandomAccessIterator first, 
                   RandomAccessIterator nth,
                   RandomAccessIterator last);
and you call it like
  nth_element(a, a+2, a+10);
so the result is that elements 0 and 1 will be smaller than the one at 
position 2, and that elements 3 through 9 will be larger. This is what 
happens in your output.

Regards
  Wolfgang

PS-1: Note that a+2 points to "9" in your example, not "12" as you claim, 
since indices are zero-based.

PS-2: The algorithm sorts such that the values before and after the 
_pointer_ are smaller and larger, respectively, not those elements that 
are smaller and larger than the _element pointed to_! I think this is the 
basic misunderstanding on your behalf. The standard on this reads

  After nth_element the element in the position pointed to by nth is the
  element that would be in that position if the whole range were sorted.
  Also  for  any iterator i in the range [first, nth) and any iterator j
  in the range [nth, last) it holds that: !(*i > *j) or comp(*j, *i)  ==
  false.

-------------------------------------------------------------------------
Wolfgang Bangerth              email:           bangerth@ticam.utexas.edu
                               www: http://www.ticam.utexas.edu/~bangerth