C++ sort on vector using function object

Question

I'm trying to sort a vector v1 using another vector v2. I can't wrap my head around this error:

terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check
Abort trap

while running this code:

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

class Comp
{
    public:
        Comp(vector<double>& inVec): _V(inVec) {}
        bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));}
    private:
        vector<double> _V;
};

int main(int argc, char** argv)
{
    double x1[] = {90.0, 100.0, 80.0};
    double x2[] = {9.0, 3.0, 1.0};
    vector<double> v1(x1,x1+3);
    vector<double> v2(x2,x2+3);

    sort(v1.begin(), v1.end(), Comp(v2));  // sort v1 according to v2

    for(unsigned int i=0; i<v1.size(); i++)
    {
        cout << v1.at(i) << " " << v2.at(i) << endl;
    }

    return 0;
}

v1 and v2 are of the same size. Why the out_of_range error?

Thanks in advance for any pointers.

Answer 1

Like said in other answers, the problem is that the sort algorithm passes the actual values to compare rather than indices.

Here is how you can solve it:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<double, double> Zipped; // Represent an element of two lists
                                     // "zipped" together

// Compare the second values of two pairs
bool compareSeconds ( Zipped i, Zipped j )
{
    return i.second < j.second;
}

int main ( int argc, char **argv )
{
    double x1[] = { 90, 100, 80 };
    double x2[] = { 9, 3, 1 };

    vector<double> v1(x1, x1 + 3);
    vector<double> v2(x2, x2 + 3);

    vector<Zipped> zipped(v1.size()); // This will be the zipped form of v1
                                      // and v2

    for ( int i = 0; i < zipped.size(); ++i )
    {
        zipped[i] = Zipped(v1[i], v2[i]);
    }

    sort(zipped.begin(), zipped.end(), &compareSeconds);

    for ( int i = 0; i < zipped.size(); ++i )
    {
        cout << zipped[i].first << " " << zipped[i].second << endl;
    }

    for ( int i = 0; i < v1.size(); ++i )
    {
        v1[i] = zipped[i].first;
    }

    // At this point, v1 is sorted according to v2

    return 0;
}

Answer 2

Ok, now you're probably aware of the fact, that i and j are actual values held in vector rather than indices. There is a good reason for that: sorting is all about values, not indexes. Note you're passing iterators to sort method, so there is no way it can extract index for you. Of course, you could get index relative to first iterator, but there is no reason for doing this.

However, let's be insane for awhile and imagine you would get indices rather than values in your comparator. Assume that your code does what you want and let's think about following scenario:

v1 = {20,10}; v2 = {2,1}

I secretly assume you want the following output:

v1 = {10, 20}

right? Now imagine I'm a sorting function you're calling and I do following steps:

• v2[0] < v2[1] is false, so swap(&v1[0], &v1[1])

It's sorted, isn't it? But wait, I'm a crazy sorting function, so I want to make sure it's sorted, so I do the following:

• v2[0] < v2[1] is false, swap(&v1[0], &v1[1])

And again:

• v2[0] < v2[1] is false, swap(&v1[0], &v1[1])

and again, again, again...

Can you see a problem? Sorting function has some requirements and for sure you're breaking fundamental one.

I suspect you need completely different container (maybe std::map with keys from vec1 and values from vec2) or at least something like vector< pair<double, double> >, so you can easily sort by either first or second value. If not, consider creating vector with values in range [0, v2.size()), sorting it using your comparator (values are equal to indices, so will be all right) and then print correct values from v1. This code works fine:

vector<size_t> indices;
for(size_t i =0; i < v1.size(); ++i)
{
  indices.push_back(i);
}

// yes, it works using your original comparator
sort(indices.begin(), indices.end(), Comp(v2));

for(size_t i =0; i < indices.size(); ++i)
{
    cout << v1.at(indices[i]) << " " << v2.at(indices[i]) << endl;
}

Answer 3

Size of v1 is just 3, but you're using each value of v2 as index of v1. And as v2 has one value 9 which is greater than the size of v1, that is what gives std::out_of_range error in here:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));}

std::vector::at function gives std::out_of_range exception of the index passed to it as argument is greater than the size of vector. That is, the index must be less than vector::size().

Answer 4

I believe that your problem is in this line:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));}

The problem is that when the std::sort algorithm uses a custom callback, it passes in the actual values stored in the vector at particular locations, not the indices of those locations within the vector. As a result, when you call

sort(v1.begin(), v1.end(), Comp(v2));  // sort v1 according to v2

The Comp comparator you've written will be getting passed as parameters the values stored in the v1 vector and will then try indexing at those positions into the v2 vector. Since the values in v1 are larger than the size of v2, the call to _V.at(i) will cause an out_of_range exception to be thrown.

If you want to sort the two ranges with respect to one another, you'll need to adopt a different approach. I'm not aware of a straightforward way of doing this, but I'll let you know if I think of one.