2

I am trying to implement the Merge sort algorithm:

#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;
}

This program does not compile:

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

I know that I messed something simple in my declaration but I cannot figure it out.

Martin Drozdik
  • 12,742
  • 22
  • 81
  • 146

5 Answers5

12

The TObject in std::function<bool(TObject const&, TObject const&)> can not be deduced from any argument that is not a std::function already, see this question.

You're also misusing std::function - only use it if you want to store any callable entity. If you just want to take anything callable as a parameter, make it a template parameter:

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

This is also the way the stdlib does it (see virtually every algorithm with a predicate, like std::sort). This way, you're also avoiding the (in your case unnecessary) type erasure that std::function performs.

Community
  • 1
  • 1
Xeo
  • 129,499
  • 52
  • 291
  • 397
  • Thank you! I tried to declare the criterium as an additional parameter, but it still doesn't compile. I think, that the problem is with the TObject template parameter. That is the object that the iterator is pointing to. – Martin Drozdik Oct 23 '12 at 08:54
  • 2
    @Martin: You never need to know what `TObject` really is in C++11 thanks to `auto`, so just declare the function as I did in the answer. :) – Xeo Oct 23 '12 at 08:56
  • This approach probably instantiates the entire algorithm for each new criterium. Is there a way to avoid this? – Martin Drozdik Oct 23 '12 at 08:56
  • @Martin: For functions, it will instantiate new versions for different signatures, and for function objects, for every type, but I don't see the problem with that. Don't tell me you're worried about "code bloat"? Note that you'd have the same problem for every different signature with `std::function`. – Xeo Oct 23 '12 at 08:58
  • 1
    @Martin: Only if you've read books that are long outdated. Nowadays, disk-space is cheap anyways. A good linker will also fold identical instantiations, and anything that is left after that would need to be written anyways for every `TObject` if you didn't use templates. – Xeo Oct 23 '12 at 09:01
  • @Xeo: Actually... folding identical instantiations is not so easy. The problem is that in C++ different functions are supposed to have different addresses, so unless you can prove that their addresses are not taken you need to ensure that the addresses will be different (unless you are called MSVC of course...). There are technics in assembly to avoid the bloat (`.func1 nop .func2 nop .func3 /* real code */), but I do not know any linker that do so yet. – Matthieu M. Oct 23 '12 at 09:10
  • 3
    @MartinDrozdik: if the *user* decides that he has created too many distinct instantiations of the template, then he can change his code to use fewer different types for the `Comp` template parameter. One way to do that would be to use `std::function` to get only one instantiation per signature. The result would be the same as what you were aiming to do, but it's the user's choice rather than your algorithm restricting it. Having a different instantiation per comparator and inlining it is often a win for algorithms, but by trying to prevent "code bloat" you prevent that too. – Steve Jessop Oct 23 '12 at 09:44
5

You could just take a look at std::sort:

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

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

This way you can use whatever callable thing you want to.

cooky451
  • 3,460
  • 1
  • 21
  • 39
2

Your function compare isn't a std::function but your mergeSort expects one. Moreover, you should not pass const_iterator to your function because it's supposed to modify the array.

If you change your code and use this:

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

It works (see http://ideone.com/7FdKTP).

In my opinion, it's easier to implement comparators as structs with an operator(). This way, you pass an object instead of a function, which is easier to manage.

alestanis
  • 21,519
  • 4
  • 48
  • 67
  • 1
    `std::function` is constructible from any callable entity, so this is not a problem. The problem here is template argument deduction. – Xeo Oct 23 '12 at 08:27
  • The problem would be the std::function arguments? – alestanis Oct 23 '12 at 08:28
  • The std::function means "anything that can be called with two same arguments that returns a result implicitly converitble to a bool". This is exactly what I want – Martin Drozdik Oct 23 '12 at 08:30
  • Thank you! Indeed your suggestion works! But why is my program invalid? – Martin Drozdik Oct 23 '12 at 08:37
  • Nitpick: you absolutely do *not* want a `const_iterator` actually, since a `sort` has to shuffle elements around. – Matthieu M. Oct 23 '12 at 08:41
  • Well I do think it was because your compiler didn't understand `compare` was a std::function. Maybe because of the `compare` arguments not being `const int&`. You can check different configurations until you find out :) – alestanis Oct 23 '12 at 08:43
  • @MatthieuM. you're right, i'll edit. EDIT: actually... it depends on what you do inside mergeSort... – alestanis Oct 23 '12 at 08:44
  • @alestanis: if `mergeSort` does not sort, I'll whip the OP for worst misleading name ever ;) – Matthieu M. Oct 23 '12 at 09:34
  • @MatthieuM. I didn't see its signature, you are right :) actually I was thinking about mergeSort making a copy of the original array, calling a sorting recursive function then returning the sorted array. I edited :) – alestanis Oct 23 '12 at 10:21
1

Though I don't know how to completely fix this, it's obvious that the compiler fails to deduce the arguments. Explicitly stating them could work as a workaround:

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

Another way would be explicitly converting the function you are passing into std::function.

You could also implement this by making the last argument a operator< instead of a comparing function, that would be more intuitive I think.

SingerOfTheFall
  • 29,228
  • 8
  • 68
  • 105
-1

The mergeSort expects const TIterator and yours isn't.

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
  • That is true, but is not the problem in this case. The problem would be if it were the other way around. That is, if I would try to pass a const TIterator to a function where it is not declared constant. – Martin Drozdik Oct 23 '12 at 08:27
  • Converting non-const to const is always allowed. – Griwes Oct 23 '12 at 08:41
  • 1
    @MartinDrozdik: Actually, if the function takes the parameter by copy, the `const` is irrelevant (for the caller). – Matthieu M. Oct 23 '12 at 08:42