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

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Edouard A. (edouard_at_[hidden])
Date: 2009-05-10 00:56:16

> I understand that it is not random access according to the standard.
> What
> I was saying is that algorithm-wise (in terms of writing them from
> scratch), the iterator can be treated as having actual random access
> (with
> the new iterator hierarchy), even though it does not satisfy the
> requirements that are part of the specification for std::sort and such.
> That is, it satisfies some requirements (constant-time +=, etc), and
> the
> deficiencies can be worked around in a newly-written sorting algorithm.
> The discussion was about whether to use quick sort or merge sort, and
> either of these would be efficient on zip_iterators if they were
> rewritten
> to handle the swap problem.

Ok now I clearly see the problem.

You need a sort algorithm that takes the dereference to the element and the
swap as template policy parameters. One could write a specialized sort, but
I think it would be even nicer to have a customizable introsort (ie you
could customize the pivot selection, thresholds, fallback algorithms,
comparison, dereference and maybe other things). 

Performances would probably be a tiny bit below std::sort (because inlining
doesn't always work as expected) but you would use it when std::sort doesn't
work, or when you are in a case where the default pivot (generally median of
3 or median of 5) is suboptimal for you.

As for quicksort vs mergesort (I would include heapsort in the comparison as
well) I would bet on quicksort, but benchmarking is the only way to know.

-- 
EA