Re: [boost] [iterator] std::sort on zip_iterator (repost)

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