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
>> be iterated and swapped, but does not have a Random Access Iterator? If
>> I could reconsider the request and see if I can find (or write) an
>> 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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk