2

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

#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

我知道我在声明中搞砸了一些简单的事情，但我无法弄清楚。

4

5 回答 5

12

不能从任何不是已经存在的论点中推断出in TObject，请参见这个问题。std::function<bool(TObject const&, TObject const&)>std::function

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

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

这也是标准库的做法（几乎可以查看每个带有谓词的算法，例如std::sort）。这样，您还可以避免执行（在您的情况下是不必要的）类型擦除std::function。

于 2012-10-23T08:47:05.313 回答
5

你可以看看std::sort：

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

http://en.cppreference.com/w/cpp/algorithm/sort

这样你就可以使用你想要的任何可调用的东西。

于 2012-10-23T08:32:50.273 回答
2

您的功能compare不是，std::function而是您的mergeSort期望。此外，您不应该传递给const_iterator您的函数，因为它应该修改数组。

如果您更改代码并使用它：

std::function<bool(const int&, const int&)> myCompare = compare;
mergeSort(container.begin(), container.end(), myCompare);

它有效（参见http://ideone.com/7FdKTP）。

在我看来，将比较器实现为带有operator(). 这样，您传递一个对象而不是一个函数，这更容易管理。

于 2012-10-23T08:26:22.943 回答
1

虽然我不知道如何完全解决这个问题，但很明显编译器无法推断出参数。明确说明它们可以作为一种解决方法：

mergeSort< std::list<int>::iterator, bool >(container.begin(), container.end(), compare);

另一种方法是将您传递的函数显式转换为std::function.

您也可以通过使最后一个参数 aoperator<而不是比较函数来实现这一点，我认为这会更直观。

于 2012-10-23T08:38:28.713 回答
-1

mergeSort期望和你的const TIterator不是。

于 2012-10-23T08:24:21.773 回答