Re: [boost] [iterator] std::sort on zip_iterator (repost)

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-06-05 10:05:52

On Thu, Jun 4, 2009 at 11:20 AM, David Abrahams <dave_at_[hidden]> wrote:

>
> on Sat May 09 2009, "Edouard A." <edouard-AT-fausse.info> wrote:
>
> >> You'd have to use a specialized sorting algorithm that does not
> >> dereference
> >> any elements and does not use std::swap.  To make it as general as
> >> possible,
> >> I think it would be best to define a simple_sort that works on
> >> bidirectional
> >> iterators and lets the user override the swap method to allow tuple
> >> swapping, for example.  The idea is a fallback sort that can sort
> >> almost any
> >> sortable data structure, though not necessarily at optimal speed.
> >> You're welcome to write this yourself, possibly using the quicksort
> >> part of
> >> the STL introsort definition, or you could wait for me to write it,
> >> which I
> >> should eventually get to.
> >
> > Quick/introsort requires a random access iterator, if you only have
> > bidirectional iterators, merge sort is more appropriate.
>
> Quicksort really doesn't take advantage of random access at all, other
> than possibly for choosing better pivots.  The basic structure is a
> recursive "partition, then sort-both-halves," which you can do nicely
> with bidirectional iterators. With a little extra storage I think you
> can even do it with forward iterators.
>

The partition step is more efficient with random access (unless you
partition on the first or last element, which is bad for sorted data), but
agreed, Quicksort is good with bidirectional iterators, once you partition.

You can trivially convert a list of forward iterators into reverse iterators
by holding a vector of them, using O(n) memory, but then you might as well
use LSB radix sort and sort the memory externally if you're willing to
sacrifice the memory.  I was thinking that for general sorting, a more
appropriate solution would be to create O(square_root(n)) index locations in
the reverse iteration array, along with storing the local square_root(n)
locations, which get refreshed (in O(square_root(n)) time) every time an
iterator backs over a point in the index.  This approach could be
generalized in a class, but each "reverse iterator" would take
O(square_root(n)) memory, though reference counting could be used to avoid
duplication (to a maximum of n + square_root(n) additional locations, if
there were square_root(n) reverse iterators, at least 1 for each location in
the index).
Would that be worth putting into boost?  Is reverse iterating over a forward
iterator a common problem that occurs outside sorting that would be worth
creating a class for?