on Fri May 08 2009, Steven Ross <spreadsort-AT-gmail.com> wrote:
On Fri, May 8, 2009 at 4:30 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Fri, 8 May 2009, Steven Ross wrote:
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)).
I think you would need an implementation of swap_tuples like in my later email (containing "[tuple] swap" in the subject). You can use ++ on the array, but there is also constant-time --, +=, -=, [], etc. The zip_iterators have full random access capability; they just do not model the old Random Access Iterator concept because operator* does not return a reference (it returns a tuple of references instead). The test code (using std::sort) is in the email that started this thread.
You'd have to use a specialized sorting algorithm that does not dereference any elements and does not use std::swap.
The usual trick to handle proxy refs is to do everything in terms of iter_swap. -- Dave Abrahams BoostPro Computing http://www.boostpro.com