如何将用户数据传递给std::sort的比较函数？

Question

与qsort()一样，C++ std::sort()似乎也不允许将用户数据传递给排序函数。

例如:像struct A { int version; int index; } array[100]这样的结构数组必须按顺序排序，但使用此数组struct B { int value; } key[100]作为排序关键字。struct A::index索引数组key。

这是一个不能工作的排序函数。它需要有一个指向key数组的指针：

bool comp(struct A *a1, struct A *a2) {
    return key[a1->index].value < key[a2->index].value;
}

如何使用C++实现这一点？如何将像key这样的非全局用户数据传递给排序函数？

我试图将对象实例作为std::sort组件传递，但似乎只允许使用qsort()-like函数。

(在GNU C中，嵌套的比较函数可用于使用限定了作用域的变量，但GNU C++不提供嵌套函数)。

Answer 1

函数器不一定是函数；它们可以是对象。

struct Comparator {
   Comparator(int* key) : key(key) {};
   bool operator()(struct A *a1, struct A *a2) {
      return key[a1->index].value < key[a2->index].value;
   }

   int* key;
};

/* ... */

std::sort(container.begin(), container.end(), Comparator(<pointer-to-array>));

Answer 2

您可以确切地告诉sort如何通过使用比较函数进行排序。

工作示例：

struct Foo
{
    int a_;
    std::string b_;
};

Foo make_foo(int a, std::string b)
{
    Foo ret;
    ret.a_ = a;
    ret.b_ = b;
    return ret;
}
struct ByName : public std::binary_function<Foo, Foo, bool>
{
    bool operator()(const Foo& lhs, const Foo& rhs) const
    {
        return lhs.b_ < rhs.b_;
    }
};

template<class Stream> Stream& operator<<(Stream& os, const Foo& foo)
{
    os << "[" << foo.a_ << "] = '" << foo.b_ << "'";
    return os;
}
int main()
{
    vector<Foo> foos;
    foos.push_back(make_foo(1,"one"));
    foos.push_back(make_foo(2,"two"));
    foos.push_back(make_foo(3,"three"));

    sort(foos.begin(), foos.end(), ByName());

    copy(foos.begin(), foos.end(), ostream_iterator<Foo>(cout, "\n"));

}

输出：

[1] = 'one'
[3] = 'three'
[2] = 'two'