Re: [boost] [tuple] Sorting tuples

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2008-04-20 21:33:56

There is always the good ol' rdix sort (std::stable_sort by Third,  
then by Second, then by First).  This will scale to any number of  
sort fields.  However, std::stable_sort is somewhat slower than  
std::sort, and beside you will do many more (and some unnecessary)  
moves.

There is a top-down variant of radix sort too, it'll do more or less  
the same comparisons (but fewer) as the lexicographical comparison  
functor you wrote below, but it'll be recursive (of depth equal to  
the number of sorting fields) and it only useful if lots of tuples  
have the same First values, and second values.  If First (top-level)  
values are mostly unique, then your functor is the best.
--
Hervé Brönnimann
hervebronnimann_at_[hidden]
On Apr 20, 2008, at 1:43 PM, Stathi Triadis wrote:
> Hi,
>
> I understand that the < operator is defined for tuples, but I'd  
> like some
> kind of functor that can sort tuples in a different order; for  
> example, the
> second, third, then first element of the tuple. Does boost already  
> have
> something that does this?
>
> I was thinking something like this:
>
> template<uint First, uint Second, uint Third>
> struct SortTuple
> {
>     template<typename Tuple>
>     bool operator()(const Tuple& tup1, const Tuple& tup2) const
>     {
>         if (tuples::get<First>(tup1) != tuples::get<First>(tup2))
>             return tuples::get<First>(tup1) < tuples::get<First> 
> (tup2);
>         if (tuples::get<Second>(tup1) != tuples::get<Second>(tup2))
>             return tuples::get<Second>(tup1) < tuples::get<Second> 
> (tup2);
>         if (tuples::get<Third>(tup1) != tuples::get<Third>(tup2))
>             return tuples::get<Third>(tup1) < tuples::get<Third> 
> (tup2);
>     }
> };
>
> typedef boost::tuple<int, int, int> MyTuple;
> vector<MyTuple> v;
> sort(v.begin(), v.end(), SortTuple<1, 2, 0>());
>
> This was quite easy to implement, but what about an arbitrary  
> number of
> tuple elements? Does this or something else with the equivalent
> functionality exist in boost?
>
> Cheers,
> Stathi
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/ 
> listinfo.cgi/boost