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