how to sort a vector in c++ according to the ratio of its values [duplicate]

Question

This question already has answers here:

Standard library sort and user defined types (3 answers)

Closed 9 years ago.

I have a vector that its elements consists of two integers. I want to compute the ratio of these 2 integers for every element first, and then sort the vector descending according to this ratio.

Answer 1

Have a look at std::sort. That function allows you to sort a collection using a predicate that you may specify yourself. In the example code below I create a vector of pairs. The cmp function compares two of these pairs by calculating the ratio for each and returning true if a's ratio is greater than b's.

So effectively you need to specify a function (or a function object, or lambda or whatever) that takes two arguments of your collections element-type and compares them. If a should come before b, then the function should return true, and if not then it should return false. That function is the third argument for std::sort

#include <algorithm>
#include <vector>

bool cmp(const std::pair<int, int>& a, const std::pair<int, int>& b)
{
    // you should probably also add some code to prevent dividing by zero...
    return (static_cast<double>(a.first)/a.second) > (static_cast<double>(b.first)/b.second);
}

int main()
{
    std::vector<std::pair<int, int> > pairs;
    std::sort(pairs.begin(), pairs.end(), &cmp);
}

Answer 2

In C++11:

#include <algorithm>
#include <vector>

int main ( )
{
    typedef std::pair<int, int> elem_t;
    std::vector<std::pair<int, int>> pairs;
    std::sort(pairs.begin(), pairs.end(), [](elem_t const & e1, elem_t const & e2)
    {
        e1.first * e2.second < e1.second * e2.first;
    });
}

If you don't know the [](...){...} syntax, it is a lambda-expression from c++11.

Note that comparing multiplies the way I done it has a better precision that dividing (because integer division takes place), but can lead to overflow.