Re: [boost] [tuple] Sorting tuples

From: Stathi Triadis (stathie_at_[hidden])
Date: 2008-04-22 17:50:06

Would anyone be interested in an implementation of a tuple comparator for
boost? I could be like explained above; giving the ability to sort on any
one or more 'indexes' of the tuple:

typedef tuple<int, double, ..., char> MyTuple;
vector<MyTuple> vec;
 sort(vec.begin(), vec.end(), CompareTuple<2, 0, 1>());
sort(vec.begin(), vec.end(), CompareTuple<3>());
sort(vec.begin(), vec.end(), CompareTuple<1, 3>());
sort(vec.begin(), vec.end(), CompareTuple<2, 0, 1, 4, 3>());

etc...

It's so simple yet still an annoyance to implement. It even makes me
reconsider design for simple 'struct' like classes:

struct MyStruct : public boost::tuple<double, int, ...>
{
    double& getMyField();   // Returns get<0>
    int& getMyOtherField(); // Returns get<1>
    ...
};

and you can automatically sort this struct however you want without having
to implement the functor.

Stathi

On Mon, Apr 21, 2008 at 2:33 AM, Hervé Brönnimann <hervebronnimann_at_[hidden]>
wrote:

> 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
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>