c++ - Failed to specialize function template

This is homework, although it's already submitted with a different approach.

I'm getting the following from Visual Studio 2008

error C2893: Failed to specialize function template 'void std::sort(_RanIt,_RanIt,_Pr)'

The code is as follows

main.cpp
    Database<> db; 
    db.loadDatabase();
    db.sortDatabase(sort_by_title());  

Database.cpp
void Database::sortDatabase(const sort_by &s) { 
    std::sort(db_.begin(), db_.end(), s); 
}

And the function objects are defined as

struct sort_by : public std::binary_function { 
    virtual bool operator()(const Media *l, const Media *r) const = 0;
};

struct sort_by_title : public sort_by {

    bool operator()(const Media *l, const Media *r) const { ... }
};
...

What's the cure here?

[Edit]
Sorry, maybe I should have made the inheritance clear

template  >
class Database : public IDatabase 

[/Edit]

[Edit2]
After the suggestion from Toolbox (which seemed very reasonable) I ended up with the following error message

error C2664: 'Database<>::sortMedia' : cannot convert parameter 1 from 'sort_by_title' to 'const sort_by &'

main.cpp is still the same, but with some slight modifications to the functor hierarchy and source files. Forward declarations and such did not work so I had to put the definitions in separate files.

Search.h
struct sort_by_impl {
    virtual bool operator()(const Media *l, const Media *r) const = 0;
};

struct sort_by : public std::binary_function { 
    sort_by_impl *sbp;
    bool operator()(const Media *l, const Media *r) const {
        return (*sbp)(l, r);
    }
};

IDatabase.h
struct sort_by_title : public sort_by_impl {
    bool operator()(const Media *l, const Media *r) const {

        return (l->getTitle() < r->getTitle());
    }
};

I'm really not grokking this, what am I missing here? Some conversion operation, or what?
[/Edit2]

[Edit3]
Last and final edit, I hope. I actually got this working after debugging and rewriting some of the code. This is what I ended up with, and it's the best I could do

class sort_by : public std::binary_function { 
public:
    sort_by(sort_by_impl *sbp) : sbp_(sbp) {};
    bool operator()(const Media *l, const Media *r) const {
        return (*sbp_)(l, r);
    }
private:
    sort_by_impl *sbp_;
};


main.cpp
    db.sortDatabase(&sort_by_title());

Database.cpp
void Database::sortDatabase(const sort_by &s) { 
    std::sort(db_.begin(), db_.end(), s); 

This seems to work, both in a separate project (spending the better part of this day messing with this) and in my actual project which I submitted some days ago.
Thank you very much for your time and help!
[/Edit3]

Answer

I'm not sure this is what's causing the problem, as it has nothing to do with specializing std::sort, but in sortDatabase you shouldn't be passing in a functor that's meant to behave polymorphically. The reason is that std::sort accepts your function object by value, which means it gets copied as a sort_by object, not whatever it actually is (i.e. you have a slicing problem).

If you want the function object to have a virtual operator(), the function object should hold a pointer to the polymorphic class like so:

struct sort_by : public std::binary_function {
    bool operator()(const Media *l, const Media *r) const
    {
        return (*p_impl)(l, r);
    }


    sort_by_impl* p_impl;
};

Then, sort_by_impl can be your abstract base class from which specific sorting function objects derive and override. Hope that helps.

EDIT

Based on the new error message, if I had to guess, you're trying to do something like this inside sortMedia:

Database > db; // initialized elsewhere...

sort_by_title my_sort;
db.sortDatabase(my_sort);

The problem is that my_sort is of type sort_by_title, which is a derived form of sort_by_impl - not of type sort_by. That means you actually want to pass my_sort to be the sbp pointer in a sort_by object, which is the actual function object you'll use. To illustrate:

Database > db; // initialized elsewhere...


sort_by my_sort_fn;
my_sort_fn.sbp = new sort_by_title;
db.sortDatabase(my_sort_fn);

delete my_sort_fn.sbp;

The code isn't exception safe, by the way; consider replacing sbp with a reference-counting smart pointer. Or even easier, just declare the sort_by_title on the stack and pass in its address. Just be careful not to let it be destroyed before it's used. :)

Hopefully that helps. Let me know how it turns out!