Sorting a vector using another vector in C++ without lambda function

Question

I want to get an ordered index values based on a vector (later I'll use this indices to sort another vector). The following code works for my purposes:

std::vector<int> order_ideal(std::vector<double> x) {
  std::vector<int> idx(x.size());
  std::iota(idx.begin(), idx.end(), 0);
  std::sort(idx.begin(), idx.end(), [&](int i, int j){return x[i] > x[j];});
  return idx;
}

But, the lambda functions cannot be used in earlier versions of GCC compiler, so I am looking for another way to implement this code without using lambda functions. I really like how [&] captures outer environment variables. In other words, I want to use x from the outer environment in the comparison function of std::sort().

Alternatively, I could make the following work but it is six times slower on my computer than the function above (and I haven't check it's earlier GCC versions compatibility):

bool isGreater(int i, int j, std::vector<double> x)
{
    return x[i] > x[j];
}


std::vector<int> order_bind(std::vector<double> x)
{
  std::vector<int> idx(x.size());
  std::iota(idx.begin(), idx.end(), 0);
  std::sort(idx.begin(), idx.end(), std::bind(isGreater, std::placeholders::_1, std::placeholders::_2, x));
  return idx;
}

I somewhat understand that I need to bind these two vectors (idx and x together) like explained here. But I cannot implement it in this case.

Perhaps the reason the alternative function is very slow is because each time it's called, your poor computer needs to make a duplicate copy of the ***entire*** vector, for no reason whatsoever, in order to pass it a parameter? Have you tried passing the vector parameter by reference? See your C++ textbook for more information. — Sam Varshavchik, Sep 26 '20 at 21:57

Paul Sanders · Accepted Answer · 2020-09-26T22:12:22.310

The 'do it yourself' version of a capturing lambda is an object which captures the required variables manually and exposes a functor to do the actual work, something like this (please note that I have also corrected the issue Sam raised):

class Compare
{
public:
    Compare (const std::vector<double> &v) : m_v (v) {}
    bool operator () (int i, int j) const { return m_v [i] < m_v [j]; }

private:
    const std::vector<double> &m_v;
};

std::vector<int> order_ideal(const std::vector<double>& x) {
    std::vector<int> idx(x.size());
    std::iota(idx.begin(), idx.end(), 0);
    Compare c (x);
    std::sort(idx.begin(), idx.end(), c);
    return idx;
}

Live demo

Sorting a vector using another vector in C++ without lambda function

1 Answers1