Re: [boost] Re: [string algo formal review]

From: Rob Stewart (stewart_at_[hidden])
Date: 2003-10-31 15:21:10

From: Daniel Spangenberg <dsp_at_[hidden]>
> Rob Stewart schrieb:
> > From: "Peter Dimov" <pdimov_at_[hidden]>
> > > Have you looked at the signature of std::nth_element? ;-)
> 
> Yes I have, What is the problem?
> 
> > Actually, I searched to find it and then skimmed the description,
> > assuming that Daniel had looked more closely.  I didn't look at
> > the signature until you questioned me.
> >
> > As it turns out, std::nth_element() operates strictly with
> > iterators and returns void!  Doh!
> >
> > Given my now enlightened understanding of nth_element, I don't
> > consider it analogous to find_nth() at all, so you can consider
> > all of my capitulation above rescinded!
> >
> > Choosing a different name will resolve the problem as previously
> > stated.
> 
> Maybe a misunderstanding on my side. I did not want to say, that
> the complete signature of nth_element is related to the find_nth
> signature nor that we should adopt that signature. I only wanted to
> show that nth_element actually means (n - 1)th element for normal
> speakers. Given the example from Austern's book
> 
> int array[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
> enum { arraylength = sizeof(array)/array[0] };
> std::nth_element(array, array + 6, array + arraylength);
> 
> we finally have the array reordered such that:
> - The element array[6] has the same value that it would have if the entire
> array had been sorted
> - The elements array[0] through array[5] are less than the elements in
> the positions array[6] through array[11];
> 
> To my opinion this shows that the meaning of nth relates to a zero-
> based index (provided that the actual iterator is an array) and not
> to the usual ordinals description.

Sure, nth_element() *relates* to a zero-based index.  It
partially sorts a range such that the requested *index* of the
range is in its correct, sorted position.  IOW, nth_element() is
used to ensure that the element indexed from the beginning of a
range is in its correct, sorted position.

Think of it this way.  nth_element() views the specified range as
an array and uses an ordinary, zero-based index to refer to the
desired element.  You tell nth_element() which element you want
in the right position.  How you find that element in the range
given by the iterators is your business.

The end result is that nth_element() is quite a different animal
than find_nth(), so nth_element() can't be used as a precedent
for find_nth().

-- 
Rob Stewart                           stewart_at_[hidden]
Software Engineer                     http://www.sig.com
Susquehanna International Group, LLP  using std::disclaimer;