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

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: David Abrahams (dave_at_[hidden])
Date: 2009-06-04 14:20:43

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.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com