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 16:38:52

On Fri, 8 May 2009, Steven Ross wrote:

>>  If not, is there an alternative way to sort one sequence while swapping
>>> elements in another in a corresponding way?  I am not able to join the two
>>> input sequences into a single sequence of pairs because of other factors in
>>> the use case for this code.  Thank you for your help.
>>>
>>
>> std::sort requires a Random Access Iterator.  zip_iterator is not a Random
>> Access Iterator.
>>
>
> I've proposed a sorting library here; it only works for Random Access
> Iterators, but there were some requests in the past for a more general sort
> implementation.
> 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 can
> be iterated and swapped, but does not have a Random Access Iterator?  If so,
> I could reconsider the request and see if I can find (or write) an effective
> 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.

-- Jeremiah Willcock