Implement sort with templates. How to use comparator?

Question

I'm implementing a simple sort algorithm just to learn how C++ templates work. I need to sort arrays with elements of different types, so I need to use different functions of comparing them. For example, I want to sort the array of football players by their efficiency. I've written functor in with structure and use it in this way:

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

But in insertionSort I need to pass comparator c to another function:

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

Here is my code:

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]);   
}

Now I have the following compilation error: "default template arguments are only allowed on a class template" in function less and another template functions. Please, can you say, what I'm doing wrong? I can't find out where is my mistake. Thank you for your help!

score 1 · Accepted Answer · edited May 23 '17 at 12:19

You're probably compiling in C++03 mode and default template arguments for functions are not allowed there. See this SO question for details. So if you want default template arguments, you can either switch to C++11 or use a functor instead of the function.

Using class Player as a comparator would work, but you have to instantiate it every time you call insertionSort, which is not for free as the class is not empty. It seems more efficient to have separate functor for comparing Players.

Also, you don't need to call less method in insertionSort, calling the comparator directly is enough. (c(input[j], input[j-1])).

Another solution would be to specialize std::less<Player> and use std::less for the comparison all the time. Please refer to this SO question.

score 0 · Answer 2 · answered Dec 01 '13 at 12:44

0

The message I got back clang makes it pretty clear.

"default template arguments for a function template are a C++11 extension."

This is a feature missing in C++98 which was later added in C++11.

answered Dec 01 '13 at 12:44

mpark

7,574
2
16
18

Implement sort with templates. How to use comparator?

2 Answers2