CODEWITHSUNDEEP
c++c++11
user3504726
user3504726

Reputation:

Custom Sorting a vector of tuples

I have a vector of tuples like 

vector<tuple<T1, T2, T3>> v;

I believe that when the default comparison kicks in for tuple types, it performs a lexicographical comparison.

Can I perform the comparisons by the element I choose ? Eg by the second element in the above example or by the ith element in a tuple containing m types ?

Thank you in advance.

Upvotes: 23

Views: 23944

Answers (4)

EliSquared
EliSquared

Reputation: 1559

So here is the simplest way I learned how to do it (and I think it is even more straightforward than the main answer). This will work on any type in the tuple that can be compared with <.

Here is the sort function TupleLess, which takes advantage of some C style syntax: 

 #include <string>
 #include <vector>
 #include <tuple>      

 template<int index> struct TupleLess
 {
    template<typename Tuple>
    bool operator() (const Tuple& left, const Tuple& right) const
    {
        return std::get<index>(left) < std::get<index>(right);
    }
};

int main(){
    //Define a Person tuple:    
    using Person = std::tuple<std::string, std::string, std::string>;

    //Create some Person tuples and add to a vector
    Person person1 = std::make_tuple("John", "Smith", "323 Fake Street");
    Person person2 = std::make_tuple("Sheila", "Henrod", "784 Unreal Avenue");
    Person person3 = std::make_tuple("Mitch", "LumpyLumps", "463 Falsified Lane");

    std::vector<Person> vPerson = std::vector<Person>();
    vPerson.push_back(person1);
    vPerson.push_back(person2);
    vPerson.push_back(person3);

    //Sort by index at position 2
    std::sort(vPerson.begin(), vPerson.end(), TupleLess<2>());
}

Upvotes: 1

Nikos Athanasiou
Nikos Athanasiou

Reputation: 31607

There are many ways to do that, the one I use boils down to declaring a custom comparison object, actually the following 

// Functor to compare by the Mth element
template<int M, template<typename> class F = std::less>
struct TupleCompare
{
    template<typename T>
    bool operator()(T const &t1, T const &t2)
    {
        return F<typename tuple_element<M, T>::type>()(std::get<M>(t1), std::get<M>(t2));
    }
};

It works for tuples of arbitrary length (avoiding variadic templates - even though it's fairly easy and safer to do it the variadic way because you can declare the arguments of operator() as tuples of arbitrary length) and also works for pairs and you can pass it a custom comparison function/object but uses < operator as the default policy. An example usage would be

int main()
{
    vector<tuple<int, string>> v;
    v.push_back(make_tuple(1, "Hello"));
    v.push_back(make_tuple(2, "Aha"));

    std::sort(begin(v), end(v), TupleCompare<0>());
    return 0;
}

there is ofcourse a more modern way, by using lambdas, so the sorting line would be

std::sort(begin(v), end(v), 
    [](tuple<int, string> const &t1, tuple<int, string> const &t2) {
        return get<0>(t1) < get<0>(t2); // or use a custom compare function
    }
);

I believe it's worth making a function object for this (avoids a lot of boilerplate code) and go with the first approach

EDIT

As Yakk's comment (on c++1y) became standard compliant (c++14), we demonstrate below the case for generic lambdas

std::sort(begin(v), end(v), [](auto const &t1, auto const &t2) {
        return get<0>(t1) < get<0>(t2); // or use a custom compare function
});

which greatly matches the mechanics of TupleCompare since the operator() is templated as well.

Upvotes: 26

Jens Munk
Jens Munk

Reputation: 4725

You can do it like this

#include <tuple>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<tuple<int, float, char>> v;

int main() {
  v.push_back(std::make_tuple(1,1.2,'c'));
  v.push_back(std::make_tuple(1,1.9,'e'));
  v.push_back(std::make_tuple(1,1.7,'d'));

  sort(v.begin(),v.end(),
       [](const tuple<int,float,char>& a,
       const tuple<int,float,char>& b) -> bool
       {
         return std::get<1>(a) > std::get<1>(b);
       });

  cout << std::get<2>(v[0]) << endl;
  return 0;
}

Upvotes: 12

Christian Hackl
Christian Hackl

Reputation: 27548

Yes, you can define custom sorting in C++ when you need it. I assume you need it for std::sort, right? Look at the documentation of std::sort, at the second version of the algorithm to be precise, the one which takes the comp argument.

You have to define a less-than functor, something like this:

struct CustomLessThan
{
    bool operator()(tuple<T1, T2, T3> const &lhs, tuple<T1, T2, T3> const &rhs) const
    {
        return std::get<1>(lhs) < std::get<1>(rhs);
    }
};

And then use it in std::sort:

std::sort(v.begin(), v.end(), CustomLessThan());

In C++11, you can make the code much shorter by using a lambda instead of creating a named struct. The examples given at cppreference.com also show this technique.

Upvotes: 4

Related Questions