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:29:38

On Sat, 9 May 2009, Steven Watanabe wrote:

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

I understand that it is not random access according to the standard.  What 
I was saying is that algorithm-wise (in terms of writing them from 
scratch), the iterator can be treated as having actual random access (with 
the new iterator hierarchy), even though it does not satisfy the 
requirements that are part of the specification for std::sort and such. 
That is, it satisfies some requirements (constant-time +=, etc), and the 
deficiencies can be worked around in a newly-written sorting algorithm. 
The discussion was about whether to use quick sort or merge sort, and 
either of these would be efficient on zip_iterators if they were rewritten 
to handle the swap problem.

-- Jeremiah Willcock