C++:为 std::sort 提供模板化比较函数

Question

假设我想让 std::sort 根据指针指向的 int 值对指向 int 的指针 vector 进行排序。忽略那里明显的性能问题。简单吧？ 做一个函数:

bool sort_helper(const int *a, const int *b) 
{   
    return *a < *b;
}   

并提供给 std::sort。

现在，如果我们还想对指向大对象的指针 vector 做同样的事情。同样的事情适用: 首先我们定义一个<对象中的运算符，然后按照以下几行创建一个函数:

bool sort_helper(const ob_type *a, const ob_type *b) 
{   
    return *a < *b;
}   

或其他任何东西，将其提供给 std::sort。

现在，这就是它变得棘手的地方:如果我们想使用任意比较函数对指向任何类型的指针 vector 进行排序怎么办(我们假设我们使用该函数的任何类型都能够使用它)- 提供上面的 sort_helper 函数的模板版本很容易:

template <class ob_type>
bool sort_helper(const ob_type *a, const ob_type *b) 
{   
    return *a < *b;
}   

然而，提供一个任意的比较函数更难:像这样的东西-

template <typename comparison_function, class ob_type>
bool sort_template_helper(const ob_type *a, const ob_type *b)
{
    return comparison_function(*a, *b);
}

template <typename comparison_function, class iterator_type>
void t_sort(const iterator_type &begin, const iterator_type &end, comparison_function compare)
{
    std::sort(begin, end, sort_template_helper<compare>);
}

是我想做的，但是这样做:

bool less_than(const int a, const int b) 
{   
    return a < b;
}   

void do_stuff()
{
    t_sort(ipoint_vector.begin(), ipoint_vector.end(), sort_template_helper<less_than>);
}

不起作用。 如何使用提供给 std::sort 的任意比较函数，根据指向的对象的值对指向已知类型的指针 vector 进行排序？假设我在这里展示的测试用例是实际场景的疯狂简化版本，并且有充分的理由想要以这种方式做事，这将花费太长时间来研究问题并分散注意力。

[编辑:出于各种原因，我正在寻找一种也适用于 C++03 的解决方案——感谢 Nir ​​的 C++14 答案]

Answer 1

基本上您需要的是高阶函数:返回函数的函数。

template <class T, class F>
auto make_pointee_comparison(F f) {
    return [=] (T const * l, T const * r) { return f(*l, *r); };
}

这里我明确指定了T；您可能可以通过额外的编程来推导 T，但要使其对函数对象和函数指针都正确工作可能会非常棘手。

编辑:为了使它在 C++03 中工作，我们显然必须删除对 lambda 的使用。不过，将 lambda 转换为函数对象非常简单。我们声明一个结构:

template <class F>
struct PointeeComparisonHelper {
    PointeeComparisonHelper(F f) : m_f(f) {}

    template <class T>
    bool operator()(T const * l, T const * r) const {
        return m_f(*l, *r);
    }

    F m_f;
};

template <class F>
PointeeComparisonHelper<F> make_pointee_comparison(F f) {
    return PointeeComparisonHelper<F>(f);
}

编辑:我在 03 示例中模板化了调用运算符(operator)；要使用 lambda 执行此操作，您需要 C++14，而不仅仅是 11。如果您使用的是 03 形式，则无需显式指定 <int>。至 make_pointee_comparison .

用法:

auto c = make_pointee_comparison<int>([] (int x, int y) { return x < y; });
int x = 5;
int y = 6;
std::cerr << c(&x, &y) << c(&y, &x);

打印 10 (真假)。请注意，这采用函数对象而不是函数指针，这在 C++ 中更为惯用。但是你也可以传递一个函数指针:

bool compare(int x, int y) { return x > y; }

auto c2 = make_pointee_comparison<int>(&compare);
std::cerr << c2(&x, &y) << c2(&y, &x);

然后你可以这样写你的函数:

template <typename comparison_function, class iterator_type>
void t_sort(const iterator_type &begin, const iterator_type &end, comparison_function compare)
{
    using deref_type = const decltype(*begin);
    std::sort(begin, end, make_pointee_comparison<deref_type>(compare));
}