Passing A Function Into A Constructor

Hi,

I have a class provided to me called PQueue. It functions like a "priority queue"--elements can be enqueued in any order, but elements with higher priority are dequeued first.

The class templatized, implemented as a sorted singly-linked list (with the objects of highest priority at the front, while objects of lower priority are at the back. The class also uses a default comparison function:

Code:

template <typename Type>
  int OperatorCmp(Type one, Type two)
	{
		if (one == two) return 0;
		else if (one < two) return -1;
		else return 1;
	}

As you can see, it would only work with int or string because it uses == and < to compare.
The comparison function for a particular PQueue can be customized when invoking the constructor by passing in an alternative comparison function.

Code:

//constructor in PQueue.h
PQueue(int (cmpFn)(Elem one, Elem two) = OperatorCmp);

//there is a private member variable that is a pointer to the comparison function
//(this also in pqueue.h)
int (*cmpfn)(Elem one, Elem two);

Code:

//implementation of constructor in PQueue.cpp
template <typename Elem>
PQueue<Elem>::PQueue(int (cmpFn)(Elem one, Elem two))
{
    head = NULL;
	this->cmpfn = cmpFn;
}

Now, I don't want my PQueue to hold int or string. I want to use the PQueue to hold a struct I defined called "path". So it would be: PQueue<path> myPath.

Here are my struct definitions, in case they might be helpful.

Code:

struct node;
struct arc {
	double dist;
	node *link;
};

struct node {
	string name;
	double x, y;
	Map<arc> connections;
};

struct path {
	Vector<node> route;
	double dist;
};

This means that I have to write a comparison function, which is here:

Code:

int comparePath(path path1, path path2)
{
	if (path1.dist == path2.dist) return 0;
	if (path1.dist < path2.dist) return -1;
	return 1;
}

This comparison function resides in the driver file with main().

The problem arises when I pass it into the constructor for PQueue in the driver file:
PQueue<path> myPath(comparePath);

I get errors when trying to compile referring me back to the default comparison function:

Code:

Error	1	error C2784: 'bool std::operator ==(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	2	error C2784: 'bool std::operator ==(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	3	error C2784: 'bool std::operator ==(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	4	error C2784: 'bool std::operator ==(const std::allocator<_Ty> &,const std::allocator<_Other> &) throw()' : could not deduce template argument for 'const std::allocator<_Ty> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	5	error C2784: 'bool std::operator ==(const std::istreambuf_iterator<_Elem,_Traits> &,const std::istreambuf_iterator<_Elem,_Traits> &)' : could not deduce template argument for 'const std::istreambuf_iterator<_Elem,_Traits> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	6	error C2784: 'bool std::operator ==(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	7	error C2784: 'bool std::operator ==(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	8	error C2676: binary '==' : 'node' does not define this operator or a conversion to a type acceptable to the predefined operator	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	23	
Error	9	error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	24	
Error	10	error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	24	
Error	11	error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	24	
Error	12	error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	24	
Error	13	error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'node'	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	24	
Error	14	error C2676: binary '<' : 'node' does not define this operator or a conversion to a type acceptable to the predefined operator	c:\program files\microsoft visual studio 8\vc\include\cs106cppinc\cmpfn.h	24

I'm at a loss now at what to do. I've been staring at this same thing for several hours now, trying different things and such, but to no avail.

I noticed that I did not pass the arguments by reference in the custom comparison function that I made, so I changed that:

Code:

int comparePath(path &path1, path &path2)

That reduced the amount of errors, somewhat:

Code:

Error	1	error C2664: 'PQueue<Elem>::PQueue(int (__cdecl *)(Elem,Elem))' : cannot convert parameter 1 from 'int (__cdecl *)(path &,path &)' to 'int (__cdecl *)(Elem,Elem)'	171	
Error	2	error C2664: 'PQueue<Elem>::PQueue(int (__cdecl *)(Elem,Elem))' : cannot convert parameter 1 from 'int (__cdecl *)(path &,path &)' to 'int (__cdecl *)(Elem,Elem)'	183

I'm not quite sure what's going wrong. Am I passing the custom comparison function correctly? Is there some kind of special template notation that I am missing?

Thanks in advance!

Just a guess. You might give this a try while waiting for someone who really knows the answer:

Code:

template <typename Type>
int comparePath( Type path1, Type path2 )
{
    if (path1.dist == path2.dist) return 0;
    if (path1.dist < path2.dist) return -1;
    return 1;
}

I don't think you can use references as arguments because the pointer signature has objects, not references.

I tried your suggestion, but it gave me the same errors as it did before I put the &'s in the parameter list.

Looking at this again, it appears that it is doomed to fail to compile as long as the original OperatorCmp function remains in the code. Your supplying an additional comparison function doesn't prevent the compiler from trying to compile the original one also, and that one can't work because it is trying to use == and < to compare two of your path objects. (Even if you don't use it in your program, it still has to be compilable if it's in the class.)

Try commenting out the OperatorCmp function. You won't be using it anyway.

Or, maybe it will work if you also add code to the path struct to overload == and <.

(I also suspect that the reduced number of errors after adding the &s was because the compiler simply gave up before getting to the other errors.)

OperatorCmp is stored in an external file: "cmpfn.h".

The only reference to "cmpfn.h" is
#include "cmpfn.h"
at the top of pqueue.h.

Even after I comment it out--both the #include and the reference to OperatorCmp as a default parameter in the constructor of pqueue.h--oddly enough, I still get the same errors that point me to OperatorCmp even if it's not in the program anymore. What does that mean?

What do you mean "point me to OperatorCmp"? I don't see "OperatorCmp" mentioned in any of the errors.

The previous errors all referred to cmpfn.h. Are you really still getting errors mentioning "cmpfn.h" after commenting out the #include?

Is comparePath now your original version:

Code:

int comparePath(path path1, path path2)
{
	if (path1.dist == path2.dist) return 0;
	if (path1.dist < path2.dist) return -1;
	return 1;
}

?

Perhaps you post something that is complete and compilable, so we can see what is going on?

Right now your approach to comparison functions is both too restrictive and too "C-style". You could template the comparison function too, so you could also accept function objects etc, and it would be more "C++ style" to require comparison functions to define "less-than" returning bool. (Such comparison functions are so much more convenient to write than the 3-way C-style comparison functions and for the implementation of priority_queue you shouldn't need anything else than "less-than".)

The following mimics how std::priority_queue goes about it.

Code:

#include <functional>
#include <string>
#include <iostream>

template <class T, class CompareFunc = std::less<T> >
class PQueue
{
    CompareFunc compare;
    //...
public:
    PQueue(): compare() {}
    PQueue(CompareFunc compare): compare(compare){}
    //...
    bool foo(const T& a, const T& b) const
    {
        return compare(a, b);
    }
};

bool my_compare(const std::string& a, const std::string& b)
{
    return a.size() < b.size();
}

int main()
{
    PQueue<int> int_q; //by default uses operator<
    PQueue<int, std::greater<int> > reversed_int_q; //this one uses operator>
    PQueue<std::string, bool(*)(const std::string&, const std::string&)> string_q(my_compare);
    std::cout << std::boolalpha
        << int_q.foo(1, 2) << '\n'
        << reversed_int_q.foo(1, 2) << '\n'
        << string_q.foo("hello", "world!") << '\n';
}