使用函数对象在C++中对向量进行排序

Question

我正在尝试使用另一个向量v2对向量v1进行排序。我无法理解这个错误：
终止调用后抛出了“std::out_of_range”的实例
what(): vector::_M_range_check
Abort trap
当运行以下代码时：

#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和v2的大小相同，为什么会出现out_of_range错误？

非常感谢您提供的任何指导。

- ram

---

你的 Comp 类应该持有对向量的引用，而不是复制它。 - Tim

Answer 1

我认为您的问题出在这一行代码上：

我相信您的问题出现在这一行：

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

问题在于，当std::sort算法使用自定义回调时，它传递的是存储在vector中特定位置的实际值，而不是这些位置在vector中的索引。因此，当你调用排序算法时，如果需要在回调函数中访问元素的索引，则需要进行额外处理。

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

您编写的Comp比较器将会作为参数传递存储在v1向量中的值，并尝试在这些位置上进入v2向量。由于v1中的值大于v2的大小，调用_V.at(i)将导致抛出一个out_of_range异常。

如果您想按照彼此排序两个范围，您需要采用不同的方法。我不知道有没有直接的方法来做到这一点，但是如果我想到了，我会告诉您的。

- templatetypedef

Answer 2

< p > v1 的大小只有 3，但是您将 v2 的每个值用作 v1 的索引。由于 v2 中有一个值 9 大于 v1 的大小，这就导致了此处的 std::out_of_range 错误。

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

std::vector::at 函数在其参数所传递的索引大于向量大小时会抛出 std::out_of_range 异常。也就是说，索引必须小于 vector::size()。

- Nawaz

Answer 3

正如其他答案中所述，问题在于排序算法传递的是实际值而不是索引。

以下是解决方法：

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

- rovaughn

Answer 4

现在你可能已经意识到，i和j是实际存储在vector中的值，而不是索引。这是有道理的：排序关注的是值，而不是索引。请注意，您正在向sort方法传递迭代器，因此它无法为您提取索引。当然，您可以获得相对于第一个迭代器的索引，但没有理由这样做。

然而，让我们疯狂一下，想象一下如果您在比较器中获取的是索引而不是值。假设您的代码能够按照您的意愿执行，然后考虑以下情况：

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

我假设您希望输出如下：

v1 = {10, 20}

对吧？现在想象一下，我是一个您正在调用的排序函数，并且我执行以下步骤：

• v2[0] < v2[1]为false，因此swap(&v1[0], &v1[1])

它被排序了，是吗？但是等等，我是一个疯狂的排序函数，所以我想确保它已经排序了，所以我执行以下操作：

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

再一次：

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

一遍又一遍...

你看到问题了吗？排序函数有一些要求，你肯定违反了其中一个基本要求。

我怀疑您需要完全不同的容器（也许是具有来自vec1的键和来自vec2的值的std::map），或者至少需要像vector< pair<double, double> >这样的东西，这样您就可以轻松地按第一个或第二个值进行排序。如果不是，请考虑创建具有值范围[0，v2.size())的vector，使用您的比较器进行排序（值等于索引，因此将是正确的），然后从v1中打印正确的值。这段代码可以正常工作：

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

- tomasz

---

+1 是因为你给出了真正的原因，而不只是说 std::sort 使用值而不是索引。 - leftaroundabout