Boost logo

Boost :

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-09 15:04:04

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

-- Jeremiah Willcock

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