Edward Diener <eddielee@abraxis.com> writes:

>
> The standard list template has a member function for sorting called sort(). The
> reason that you can not call the generic sort function is that it takes random
> access iterators, not bidirectional iterators.
>

Well, yes.  The quesion is why?  One can implement quicksort to sort
in O(n log n) expected time using bidirectional iterators.

--

- Rephael Wenger, Associate Professor, Ohio State U.,
Dept. of Comp. Sci., 2015 Neil Ave., Columbus, OH 43210-1277.
tel: (614) 292-6253. e-mail: wenger@cis.ohio-state.edu
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Rephael Wenger <wenger@cis.ohio-state.edu> wrote:
> (somebody who ought to be embarrassed, now, wrote:)
>> The standard list template has a member function for sorting called
>> sort(). The reason that you can not call the generic sort function
>> is that it takes random access iterators, not bidirectional iterators.
>
>Well, yes.  The quesion is why?  One can implement quicksort to sort
>in O(n log n) expected time using bidirectional iterators.

The original STL proposal didn't have sort for bidirectional iterators.
It wasn't added later because nobody on the committee wanted it badly
enough.  Perhaps by the next round of standardization everybody will
have added it, and then it will be easy to put in the standard.

(If I recall correctly, there was some FUD (perhaps justified,
temporarily) at the time relating to a patent on the general
bidirectional-iterator-sort algorithm.)

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In <6bsuaj$3g6$1@shell7.ba.best.com>, ncm@nospam.cantrip.org (Nathan Myers) writes:

>>Well, yes.  The quesion is why?  One can implement quicksort to sort
>>in O(n log n) expected time using bidirectional iterators.

There is even a quicksort variant which would only require forward
iterators.  It is also, of course, O(n log n), but there might be a
slightly higher constant (and yes, I have implemented it, although in
a C variant -- the changes required mainly relate to saving copies of
iterators at the right point to avoid the need for indexing).


Michael Lee Finney



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

The standard list template has a member function for sorting called sort(). The
reason that you can not call the generic sort function is that it takes random
access iterators, not bidirectional iterators.

Rephael Wenger wrote:

> Why isn't there a sort for bidirectional iterators, i.e. lists?
>


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Why isn't there a sort for bidirectional iterators, i.e. lists?

--

- Rephael Wenger, Associate Professor, Ohio State U.,
Dept. of Comp. Sci., 2015 Neil Ave., Columbus, OH 43210-1277.
tel: (614) 292-6253. e-mail: wenger@cis.ohio-state.edu
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]