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 22:51:22

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.  To make it as general as possible,
I think it would be best to define a simple_sort that works on bidirectional
iterators and lets the user override the swap method to allow tuple
swapping, for example.  The idea is a fallback sort that can sort almost any
sortable data structure, though not necessarily at optimal speed.
You're welcome to write this yourself, possibly using the quicksort part of
the STL introsort definition, or you could wait for me to write it, which I
should eventually get to.