c++ - 如何正确声明通用排序算法？

Question

我正在尝试实现合并排序算法:

#include <list>
#include <functional>
#include <iterator>
#include <iostream>
#include <random>

template <typename TIterator, typename TObject>
void mergeSort(const TIterator& begin, const TIterator& end,
               std::function<bool (const TObject& left,
                                   const TObject& right)> criterium)
{
    //...
}

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

int main(int argc, char** argv)  // And now to test the algorithm
{
    std::list<int> container;
    for (int i = 0; i < 100; ++i)
        container.push_back(random() % 20);

    mergeSort(container.begin(), container.end(), compare);

    for (auto it = container.begin(); it != container.end(); ++it)
        std::cout << (*it) << std::endl;

    return 0;
}

这个程序不编译:

error: no matching function for call to 
mergeSort(std::list<int>::iterator, std::list<int>::iterator, bool (&)(int, int))

candidate is:

template<class TIterator, class TObject> 
void mergeSort(const TIterator&, const TIterator&, 
std::function<bool(const TObject&, const TObject&)>)

at global scope

我知道我在声明中搞砸了一些简单的事情，但我想不通。

Answer 1

TObject在 std::function<bool(TObject const&, TObject const&)>不能从任何不是 std::function 的参数中推导出来已经，见this question .

你也在滥用 std::function - 仅当您想存储 任何可调用实体时才使用它。如果您只想将任何可调用的东西作为参数，请将其设为模板参数:

template<class Iter, class Comp>
void mergeSort(Iter first, Iter last, Comp comp)
{
  // use 'comp(a, b)'
}

这也是 stdlib 执行此操作的方式(参见几乎所有带有谓词的算法，例如 std::sort )。这样，您还避免了(在您的情况下是不必要的)类型删除 std::function执行。