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-08 19:30:37

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.

-- Jeremiah Willcock