Boost logo

Boost :

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-05-09 15:26:50


AMDG

Jeremiah Willcock wrote:
>> Quick/introsort requires a random access iterator, if you only have
>> bidirectional iterators, merge sort is more appropriate.
>
> But I do have a random access iterator. The zip_iterator of multiple
> random access iterators is random access; it just fails to work with
> std::sort because its operator* does not return a "real" reference.
> Therefore, quicksort or introsort should work just fine with O(N lg N)
> complexity, but the Standard Library implementations probably won't
> because they make too many assumptions about references.

I'm afraid that these assumptions are written into the current standard.
According to 24.1.3 you do not even have a forward iterator.

In Christ,
Steven Watanabe


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk