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

Question

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

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

并提供给std :: sort.

现在,如果我们也想用一个指向大对象的指针向量做同样的事情.同样的事情适用:首先我们<在对象中定义一个运算符,然后沿着以下行创建一个函数:

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

或者其他什么,将它提供给std :: sort.

现在,这就是它变得棘手的地方:如果我们想要将任何类型的指针向量排序,使用任意比较函数(我们假设我们使用该函数的任何类型,将能够使用它) ) - 提供上面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的任意比较函数,通过指向的对象的值对已知类型的指针向量进行排序？假设我在这里展示的测试用例是实际场景的疯狂简化版本,并且有正当理由想要以这种方式做事,这需要很长时间才能进入并分散注意力.

[编辑:由于各种原因,我正在寻找一个也适用于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示例中模拟了调用操作符; 用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));
}