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
>> any elements and does not use std::swap. To make it as general as
>> I think it would be best to define a simple_sort that works on
>> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk