Custom Sorting a vector of tuples

Question

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.

Answer 1

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.

Answer 2

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;
}

Answer 3

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.

Answer 4

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>());
}