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

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: David Abrahams (dave_at_[hidden])
Date: 2009-06-04 14:18:36

on Fri May 08 2009, Steven Ross <spreadsort-AT-gmail.com> wrote:

> On Fri, May 8, 2009 at 4:30 PM, Jeremiah Willcock <jewillco_at_[hidden]>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