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

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-05-08 17:37:01

On Fri, May 8, 2009 at 1:38 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

>
> Theoretically, anything that can be iterated and swapped can be sorted.  Do
>> you have a genuine usage case where a sort would be useful where an item
>> can
>> be iterated and swapped, but does not have a Random Access Iterator?  If
>> so,
>> I could reconsider the request and see if I can find (or write) an
>> effective
>> algorithm and template it.
>>
>
> Yes, I do -- the case of sorting two (or more) corresponding sequences
> using a zip_iterator.  This capability is important to save memory when
> explicitly zipping the sequences into a new sequence is not possible. Note
> that zip_iterator still has random access in constant time, but just does
> not return an actual reference but a tuple of references.
>

so if I (theoretically) were to use ++ to iterate over the array, calling
std::swap(element_position, correct_position), then the zip_iterators would
be sorted correctly?
Can I use -- (Is it bidirectional)?  That would improve runtime.  I would
expect begin() and end() to be passed in as the arguments to the sort
method.
If so, please send me a testcase you expect to work, and I can try to find
an appropriate algorithm, and template it (Quicksort would work, but it's
O(n*n)).