Boost logo

Boost :

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." <> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at