Questions about defaut template type argument

[CoolPint]

As a self-exercise, I am trying to write a generic Priority Queue,
which would store any type and and accept any user-definable
"priority" function.

After much tinkering, I came up with something like below:

class PMinimum {
public:
template <typename T>
bool operator()(const T & a, const T & b)
{ return ( a < b ? true : false); }
};

template <typename T, typename F = PMinimum >
class PQueue {
public:
PQueue();
template <typename Iterator>
PQueue(Iterator, Iterator);
bool isEmpty() const;
bool isFull() const;
bool enQueue(const T &);
bool deQueue(T &);
bool getTop(T &);
void clear();
private:
int counter;
DArray<T> heap; // DArray is my own template which works like
<vector>
F cmp;
void buildHeap();
void shiftdown(int);
};

I tested it and it works fine, but there are two things which I cannot
do.

First, how can I hide class PMinimum as a private member of PQueue
template?
If I bring the class definition as a private member, how do I specify
it as the default template type argument? I tried below but it won't
compile

template <typename T, typename F = PQueue<T>:Minimum >

I tried putting forward declarations of PQueue template and
PQueue<T>:Minimum, but it still doesn't work. Making it a public
nested class doesn't help either. But I want it to be hidden as a
private member since I believe users of PQueue template doesn't need
to know about it. How can I achieve it?

Secondly, I noticed that PQueue works only if Functor classes are
provided as the type argument to the second type parameter. For
example, follwoing
PQueue<double, Priority> pdq;
would work only if "Priority" is a name of Functor class. Is it
possible to make it accept both normal functions (function pointers)
as well as Functors?

I tried changing the interface so that the constructor accepts the
"priority" function rather than accepting it as a type argument, but I
cannot make it work to accept both function pointers and functors
either. Making "cmp" a generic type requires a type parameter to be
specified for the PQueue template, which brings me to the same
problem.

I would very much appreciate any help on these two problems. I can
accept second problem might not be solved and only solution is to pass
only functor classes. But if it can be done to accept both normal
function pointers and functors, I would love to learn about it even it
requires many changes to the interface.

I think the first problem is due to my misunderstanding of the
language syntax, feature, etc. So please help me learn to correct my
mistakes. Thank you very much in advance.

 

[Rob Williscroft]

CoolPint wrote in
[snip]

I tested it and it works fine, but there are two things which I cannot
do.

First, how can I hide class PMinimum as a private member of PQueue
template?
If I bring the class definition as a private member, how do I specify
it as the default template type argument? I tried below but it won't
compile

template <typename T, typename F = PQueue<T>:Minimum >

Catch 22 applies, PQueue< T > depends on PQueue<T>:Minimum, the
compiler can't know PQueue<T>:Minimum till it knows (instantiats)
PQueue<T>.

[snip]

Secondly, I noticed that PQueue works only if Functor classes are
provided as the type argument to the second type parameter. For
example, follwoing
PQueue<double, Priority> pdq;
would work only if "Priority" is a name of Functor class. Is it
possible to make it accept both normal functions (function pointers)
as well as Functors?

you need to give the function type say bool (*)(int, int) as the type
argument and have ctor that take such a function-pointer.

[snip]

#include <iostream>
#include <ostream>
#include <set>

template < typename NonVoid, typename Alt >
struct select_non_void
{
typedef NonVoid type;
};

template < typename Alt >
struct select_non_void< void, Alt >
{
typedef Alt type;
};


template < typename A, typename B = void >
struct PQ
{
private:

class PMinimum {
public:
template <typename T>
bool operator()(const T & a, const T & b)
{ return ( a < b ? true : false); }
};

typedef typename select_non_void< B, PMinimum >::type comp_t;
comp_t comp;

public:

template < typename T >
bool test( T const &l, T const &r )
{
return comp( l, r );
}

PQ( comp_t c ) : comp( c ) {}
PQ() {}
};


bool comp_int( int a, int b )
{
return a > b;
}


int main()
{
using namespace std;

PQ< int > pq;
cout << pq.test( 1, 2 ) << endl;

PQ< int, bool (*)(int, int) > pq2( comp_int );
cout << pq2.test( 1, 2 ) << endl;
}

HTH.

Rob.

 

[CoolPint]

#include <ostream>
#include <set>

template < typename NonVoid, typename Alt >
struct select_non_void
{
typedef NonVoid type;
};

template < typename Alt >
struct select_non_void< void, Alt >
{
typedef Alt type;
};


template < typename A, typename B = void >
struct PQ
{
private:

class PMinimum {
public:
template <typename T>
bool operator()(const T & a, const T & b)
{ return ( a < b ? true : false); }
};

typedef typename select_non_void< B, PMinimum >::type comp_t;
comp_t comp;

public:

template < typename T >
bool test( T const &l, T const &r )
{
return comp( l, r );
}

PQ( comp_t c ) : comp( c ) {}
PQ() {}
};


bool comp_int( int a, int b )
{
return a > b;
}


int main()
{
using namespace std;

PQ< int > pq;
cout << pq.test( 1, 2 ) << endl;

PQ< int, bool (*)(int, int) > pq2( comp_int );
cout << pq2.test( 1, 2 ) << endl;
}

That was so clever! Thank you so much!
This is a kind of eye-opener for me! What books should I read to learn
about techniques like this?