Templates, policy-based design, partial specialisation and pointers

[Erik Wikström]

In school (no I will not ask you to do my schoolwork for me) we talked
about policy-based design and got an assignment where we got the a code-
fragment from a stack-implementation. The idea with the code was that
if, when its destructor was called, it still contained any elements it
would run 'delete' on them if they were pointers and do nothing if they
were not.

Our assignment was to reimplement the stack using policies so that the
user could (when instansiating the stack) specify if they wanted
'delete' to be run on pointers or not. My problem is that I did not
fully understand the code given, I know what it does but not why it is
possible to do it like that.

Here is the code given:

#include<deque> // stack’s implementation type
#include<string> // for testing
#include<iostream>

namespace non_generic {
struct Yes {}; // a type, corresponding to true
struct No {}; // a type, corresponding to false

template<typename T>
struct IsPtr {
typedef No Result;
};

template<typename T>
struct IsPtr<T*> { // partial specialization <-- HERE HERE
typedef Yes Result;
};

template<typename T>
class Stack {
public:
~Stack() {
cleanup (typename IsPtr<T>::Result() );
}
void push(T t) { s_.push_back(t); }

private:
void cleanup ( Yes ) {
for (I i( s_.begin()); i != s_.end(); ++i)
{
std::cout << "Delete " << **i << "\n";
delete *i;
}
}
void cleanup ( No ) {
for (I i( s_.begin()); i != s_.end(); ++i)
std::cout << "Do nothing for " << *i << "\n";
}
typedef std::deque<T> C;
typedef typename C::iterator I;
C s_;
};
}

The part I don't understand is the one marked with HERE HERE above. What
it does is that if the type T is a pointer the second struct (the one
marked) will be used and hence 'cleanup(Yes)' will be called while if
type T is not a pointer the first struct will be used and 'cleanup(No)'
will be used.

Now, the way I understand things if type T on the line above HERE HER is
a pointer to something, then the T* on the next line (marked HERE HERE)
should correspond to a pointer to a pointer. But somehow that partial
specialisation is used when T is pointer, and that's the part I don't
understand.

My second question is if there's some other more elegant way (I don't
think the one above is elegant) to determine if the type given is a
pointer or not.

--
Erik Wikström

[John Harrison]

Erik Wikström wrote:

In school (no I will not ask you to do my schoolwork for me) we talked
about policy-based design and got an assignment where we got the a code-
fragment from a stack-implementation. The idea with the code was that
if, when its destructor was called, it still contained any elements it
would run 'delete' on them if they were pointers and do nothing if they
were not.

Our assignment was to reimplement the stack using policies so that the
user could (when instansiating the stack) specify if they wanted
'delete' to be run on pointers or not. My problem is that I did not
fully understand the code given, I know what it does but not why it is
possible to do it like that.

Here is the code given:

#include<deque> // stack’s implementation type
#include<string> // for testing
#include<iostream>

namespace non_generic {
struct Yes {}; // a type, corresponding to true
struct No {}; // a type, corresponding to false

template<typename T>
struct IsPtr {
typedef No Result;
};

template<typename T>
struct IsPtr<T*> { // partial specialization <-- HERE HERE
typedef Yes Result;
};

template<typename T>
class Stack {
public:
~Stack() {
cleanup (typename IsPtr<T>::Result() );
}
void push(T t) { s_.push_back(t); }

private:
void cleanup ( Yes ) {
for (I i( s_.begin()); i != s_.end(); ++i)
{
std::cout << "Delete " << **i << "\n";
delete *i;
}
}
void cleanup ( No ) {
for (I i( s_.begin()); i != s_.end(); ++i)
std::cout << "Do nothing for " << *i << "\n";
}
typedef std::deque<T> C;
typedef typename C::iterator I;
C s_;
};
}

The part I don't understand is the one marked with HERE HERE above. What
it does is that if the type T is a pointer the second struct (the one
marked) will be used and hence 'cleanup(Yes)' will be called while if
type T is not a pointer the first struct will be used and 'cleanup(No)'
will be used.

Now, the way I understand things if type T on the line above HERE HER is
a pointer to something, then the T* on the next line (marked HERE HERE)
should correspond to a pointer to a pointer. But somehow that partial
specialisation is used when T is pointer, and that's the part I don't
understand.
The type T could be anything, but the type T* must be a pointer (obviously).

Remember that T in each of the templates is not necessarilty the same
type. If you have stack<int*> then T in the stack template is int*, and
T in the first version of IsPtr would also be int*, but T in the second
version of IsPtr would be int.

Because the second version of the IsPtr (with T=int) is more specialized
than the first version (with T=int*) the second version is picked.

My second question is if there's some other more elegant way (I don't
think the one above is elegant) to determine if the type given is a
pointer or not.

I guess you just gonig to have to get used to it. And remember that
although the implementation is messy, the use IsPtr<T>::Result couldn't
be much clearer.

john

[John Carson]

"Erik Wikström" <Er***********@telia.com> wrote in message
news:GW*******************@newsb.telia.net

In school (no I will not ask you to do my schoolwork for me) we talked
about policy-based design and got an assignment where we got the a
code- fragment from a stack-implementation. The idea with the code
was that if, when its destructor was called, it still contained any
elements it would run 'delete' on them if they were pointers and do
nothing if they were not.

Our assignment was to reimplement the stack using policies so that the
user could (when instansiating the stack) specify if they wanted
'delete' to be run on pointers or not. My problem is that I did not
fully understand the code given, I know what it does but not why it is
possible to do it like that.

Here is the code given:

#include<deque> // stack’s implementation type
#include<string> // for testing
#include<iostream>

namespace non_generic {
struct Yes {}; // a type, corresponding to true
struct No {}; // a type, corresponding to false

template<typename T>
struct IsPtr {
typedef No Result;
};

template<typename T>
struct IsPtr<T*> { // partial specialization <-- HERE HERE
typedef Yes Result;
};

template<typename T>
class Stack {
public:
~Stack() {
cleanup (typename IsPtr<T>::Result() );
}
void push(T t) { s_.push_back(t); }

private:
void cleanup ( Yes ) {
for (I i( s_.begin()); i != s_.end(); ++i)
{
std::cout << "Delete " << **i << "\n";
delete *i;
}
}
void cleanup ( No ) {
for (I i( s_.begin()); i != s_.end(); ++i)
std::cout << "Do nothing for " << *i << "\n";
}
typedef std::deque<T> C;
typedef typename C::iterator I;
C s_;
};
}

The part I don't understand is the one marked with HERE HERE above.
What it does is that if the type T is a pointer the second struct
(the one marked) will be used and hence 'cleanup(Yes)' will be called
while if type T is not a pointer the first struct will be used and
'cleanup(No)' will be used.

Now, the way I understand things if type T on the line above HERE HER
is a pointer to something, then the T* on the next line (marked HERE
HERE) should correspond to a pointer to a pointer. But somehow that
partial specialisation is used when T is pointer, and that's the part
I don't understand.
Suppose that you have

Stack<int*> s2;

Then the destructor calls

cleanup (typename IsPtr<int*>::Result() );

There are two ways to match IsPtr<int*>

1. Make T = int* and use
template<typename T>
struct IsPtr {
typedef No Result;
};
2. Make T = int and use
template<typename T>
struct IsPtr<T*> {
typedef Yes Result;
};

Both match, but which matches better? The rules say that 2. matches better.
This is because the language says that the "more specialized" version is a
better match and 2. is more specialized than 1.

What does it mean to say that 2. is more specialised? In this case, it means
that if you declare

IsPtr<X> ip;

then X must be a pointer to use 2., whereas it can be a pointer or
non-pointer and use 1.

Since 2. is a better match, it will be the one that is used.
--
John Carson

[Erik Wikström]

On 2005-11-05 13:16, John Carson wrote:

"Erik Wikström" <Er***********@telia.com> wrote in message
news:GW*******************@newsb.telia.net

In school (no I will not ask you to do my schoolwork for me) we talked
about policy-based design and got an assignment where we got the a
code- fragment from a stack-implementation. The idea with the code
was that if, when its destructor was called, it still contained any
elements it would run 'delete' on them if they were pointers and do
nothing if they were not.

Our assignment was to reimplement the stack using policies so that the
user could (when instansiating the stack) specify if they wanted
'delete' to be run on pointers or not. My problem is that I did not
fully understand the code given, I know what it does but not why it is
possible to do it like that.

Here is the code given:

#include<deque> // stack’s implementation type
#include<string> // for testing
#include<iostream>

namespace non_generic {
struct Yes {}; // a type, corresponding to true
struct No {}; // a type, corresponding to false

template<typename T>
struct IsPtr {
typedef No Result;
};

template<typename T>
struct IsPtr<T*> { // partial specialization <-- HERE HERE
typedef Yes Result;
};

template<typename T>
class Stack {
public:
~Stack() {
cleanup (typename IsPtr<T>::Result() );
}
void push(T t) { s_.push_back(t); }

private:
void cleanup ( Yes ) {
for (I i( s_.begin()); i != s_.end(); ++i)
{
std::cout << "Delete " << **i << "\n";
delete *i;
}
}
void cleanup ( No ) {
for (I i( s_.begin()); i != s_.end(); ++i)
std::cout << "Do nothing for " << *i << "\n";
}
typedef std::deque<T> C;
typedef typename C::iterator I;
C s_;
};
}

The part I don't understand is the one marked with HERE HERE above.
What it does is that if the type T is a pointer the second struct
(the one marked) will be used and hence 'cleanup(Yes)' will be called
while if type T is not a pointer the first struct will be used and
'cleanup(No)' will be used.

Now, the way I understand things if type T on the line above HERE HER
is a pointer to something, then the T* on the next line (marked HERE
HERE) should correspond to a pointer to a pointer. But somehow that
partial specialisation is used when T is pointer, and that's the part
I don't understand.

Suppose that you have

Stack<int*> s2;

Then the destructor calls

cleanup (typename IsPtr<int*>::Result() );

There are two ways to match IsPtr<int*>

1. Make T = int* and use

template<typename T>
struct IsPtr {
typedef No Result;
};

2. Make T = int and use

template<typename T>
struct IsPtr<T*> {
typedef Yes Result;
};

Both match, but which matches better? The rules say that 2. matches better.
This is because the language says that the "more specialized" version is a
better match and 2. is more specialized than 1.

What does it mean to say that 2. is more specialised? In this case, it means
that if you declare

IsPtr<X> ip;

then X must be a pointer to use 2., whereas it can be a pointer or
non-pointer and use 1.

Since 2. is a better match, it will be the one that is used.

Thank you John (and John) for your quick answers, I think I got it now.

--
Erik Wikström

[Erik Wikström]

On 2005-11-05 12:44, Erik Wikström wrote:

In school (no I will not ask you to do my schoolwork for me) we talked
about policy-based design and got an assignment where we got the a code-
fragment from a stack-implementation. The idea with the code was that
if, when its destructor was called, it still contained any elements it
would run 'delete' on them if they were pointers and do nothing if they
were not.

So, with some help from John and John I've managed to come up with the
following piece of code and I was wondering if someone have any thoughts
about it.

#include<deque>
#include<string>
#include<iostream>

namespace generic {

// This policy does nothing.
class NoDelete
{
public:
template<typename T>
static void cleanup(T t)
{
std::cout << "Do nothing for " << t << "\n";
}
};

// This policy deletes if the cleanup is called
// with a pointer else it does nothing.
class PointerDelete
{
public:
template<typename T>
static void cleanup(T t)
{
std::cout << "Do nothing for " << t << "\n";
}

template<typename T>
static void cleanup(T* t)
{
std::cout << "Delete " << *t << "\n";
delete t;
}
};

// Partial implementation of stack
template<typename T, typename Policy = PointerDelete>
class Stack
{
public:
~Stack()
{
// Take care of remaining elements according to policy
for (std::deque<T>::iterator i(s_.begin()); i != s_.end(); ++i)
{
Policy::cleanup( *i );
}
}
void push(T t) { s_.push_back(t); }
private:
std::deque<T> s_;
};
}

int main()
{
// Create every kind of stack/policy pair
generic::Stack<std::string> stack1;
generic::Stack<std::string, generic::NoDelete> stack2;
generic::Stack<std::string*> stack3;
generic::Stack<std::string*, generic::NoDelete> stack4;

stack1.push("1");
stack2.push("2");
stack3.push(new std::string("3"));
stack4.push(new std::string("4"));

return 0;
}

Specifically I've seen that some lets the class (stack in this instance)
inherit from the policy instead of calling a static function. What are
the pros and cons of such an approach compared to the one I've used? Is
there anything else one should know/think of when using a policy-based
design?

On another topic, anyone have a link to some good article/tutorial about
template template parameters? I just can't seem to get them.

Erik Wikström
--
"I have always wished for my computer to be as easy to use as my
telephone; my wish has come true because I can no longer figure
out how to use my telephone" -- Bjarne Stroustrup