c++ - 使用模板实现排序。如何使用比较器？

Question

我正在实现一个简单的排序算法，只是为了了解 C++ 模板的工作原理。 我需要用不同类型的元素对数组进行排序，所以我需要使用不同的函数来比较它们。例如，我想按效率对足球运动员的数组进行排序。我用结构编写了仿函数并以这种方式使用它:

 insertionSort(players, 0, players.size() - 1, Player());

但是在 insertionSort 中我需要将比较器 c 传递给另一个函数:

 less(input[j], input[j-1], c); // can I do so?

这是我的代码:

struct Player
{
    int number;
    ulong efficiency;

    Player(int numb, ulong ef) : number(numb), efficiency(ef) {}
    Player() : number(0), efficiency(0) {}

    // functor for comparing players by efficiency 
    bool operator() (const Player &left, const Player &right)
    {
        return left.efficiency < right.efficiency;
    }
};

// template function for comparing various elements
template<typename T, typename Comp = std::less<T> >
bool less (const T &left, const T &right, Comp c = Comp())
{
    return c(left, right);
}

template <typename T>
void swap (T &a, T &b)
{
    T tempr = a;
    a = b;
    b = tempr;
}

template<typename T, typename Comp = std::less<T> >
void insertionSort (vector<T>& input, int begin, int end, Comp c = Comp())
{
    for (int i = begin; i <= end; ++i)
        for (int j = i; j > begin && less(input[j], input[j-1], c); --j)
            swap(input[j], input[j-1]);   
}

现在我有以下编译错误:"default template arguments are only allowed on a class template" in function less 和另一个模板函数。拜托，你能说，我做错了什么吗？我找不到我的错误在哪里。感谢您的帮助!

Answer 1

您可能在 C++03 模式下编译，并且函数的默认模板参数在那里是不允许的。参见 this SO question了解详情。因此，如果您需要默认模板参数，您可以切换到 C++11 或使用仿函数代替函数。

使用类 Player作为比较器可以工作，但每次调用 insertionSort 时都必须实例化它，这不是免费的，因为类(class)不是空的。使用单独的仿函数来比较玩家似乎更有效。

此外，您无需调用 less insertionSort 中的方法，直接调用比较器就足够了。 (c(input[j], input[j-1]))。

另一种解决方案是专门化 std::less<Player>并使用 std::less随时进行比较。请refer to this SO question .