How to pass user data to compare function of std::sort?

Like qsort(), it seems that C++ std::sort() does not allow to pass user data to the sort function.

For example: An array of structure like struct A { int version; int index; } array[100] has to be sorted in order, but using this array struct B { int value; } key[100] as the sort key. struct A::index indexes array key.

Here's a non-working sort function. It needs to have a pointer to the key array somehow:

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

How to achieve that using C++? How to pass non-global user data like key to a sort function?

I tried to pass an object instance as the 开发者_如何学Gostd::sort comp, but it seems only qsort()-like functions are allowed.

(In GNU C, a nested compare function could be used to use scoped variables, but GNU C++ does not offer nested functions).

Functors don't have to be functions; they can be objects.

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

You can tell sort exactly how to sort through the use of a comparison functor.

Working example:

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"));

}

Output:

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