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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk