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 01:39:17

> How about this:
> [...]
> The calls and overloads for my suggestion would be:
> flex_sort(first, last)
> flex_sort(first, last, compare)
> flex_sort(first, last, compare, swap)

Exactly what I had in mind, except I was more thinking about something like

template 
<
        typename Iterator, 
        typename Compare, 
        int SmallThreshold,
        int DepthFallback, 
        typename MainSort, 
        typename FallbackSort, 
        typename Swapper
>
void flex_sort(Iterator first, Iterator last, Compare compare)

Mainsort would be something like

Template <typename Iterator, typename Compare, typename Swapper> 
struct
{
        size_t distance(Iterator first, Iterator last);
        // finds pivot & partition
        Iterator split(Iterator first, Iterator last);
};

And all MainSort and FallbackSort would share some traits and tell what kind
of iterator they need (to have static assertions and stuff, at compile time
you would know that you're trying to use a sort algorithm that's inefficient
for the iterators you have).

Swapper would be

struct
{

        Element get_elem(Iterator i);
          void operator()(Iterator left, Iterator right);
};

So basically flex_sort would be something like (typing as I think, not valid
C++):

void flex_sort(Iterator first, Iterator last, Compare compare, int depth =
0)
{
        if (depth >= DepthFallBack)
        {
                FallbackSort<...>(compare, swapper)(first, last);
        }
        else
        {
                Iterator pivot = MainSort<...>(compare,
swapper).split(first, last);

                // pivot => last we didn't split but sort the stuff (means
the data was too small to be split)
                if (pivot != last)
                {
                        ++depth;

                        flex_sort(first, pivot, compare, depth);
                        advance(pivot, 1);
                        flex_sort(pivot, last, compare, depth);
                }
        }
}

For quicksort, split would be:

void MainSort::split(first, last)
{
        Iterator pivot = last;

        if (distance(first, last) > threshold)
        {
                pivot = find_pivot(first, last);

                Iterator start = first;
                advance(start, 1);
                pivot = partition (start, last, std::bind2nd(compare,
swapper.get_elem(pivot)));
                        
                swapper(pivot, first);
        }
        else
        {
                insert_sort(first, last... ?);
        }

        return pivot;
}

What do you think?

-- 
EA