Re: Problems with c++ templates
Mr B wrote:
Hi all,
I'm currently studying templates in C++ and i'm really puzzled by why
the compiler doesn't like my code!!! I think I understand the concept.
I have created a Stack class which has a pointer to a Node class. The
Node class stores a value and a pointer to the previously added node.
Any reason why you don't rely on a std::list? Its templated and if you
really want to learn templates and iterators, wrap the std::list in
your own class - that forces you to learn its interface.
#include <list>
class MyList
{
std::list thelist;
public:
.... // you have to provide a compatible interface
};
Its typical to write a single-linked list with nodes having pointer to
the next node, not the previous. That way you know when you've reached
the end when node's p_next is 0. Anyway, thats not a requirement, it
just helps forward iteration. Imagine if you had to sort in reverse
because your list only supports reverse iterators.
My code is below:
template< typename T > class MyStack; // ugh!
//------------------------------------------------------------------------------
template <typename T>
class Node
{
friend class MyStack< T >;
The Node class should be a private embedded class in MyStack<>, that
would make your code much simpler since MyStack would provide
encapsulation _and_ the template parameter with no need for a getter.
private:
Node *PreviousNode;
T NodeVal;
public:
Node(T InitVal);
T GetVal() { return NodeVal; }
T GetVal() const { return NodeVal; }
};
//------------------------------------------------------------------------------
template <typename T>
Node<T>::Node(T InitVal)
{
NodeVal = InitVal;
PreviousNode=NULL;
}
Init lists are remarkeable because the above creates a pointer and a
node and _then_ uses an assignment operator to set them. Why not
initialize them at once in the proper order?
template <typename T>
Node<T>::Node(T InitVal) : PreviousNode(NULL), NodeVal(InitVal)
{
// use the body for something else
}
//------------------------------------------------------------------------------
template <typename DT>
class MyStack
{
private:
Node<DT> *TopNode;
int MaximumNodes;
int NumNodes;
public:
MyStack(int Size);
~MyStack();
void Push(DT Val);
void Push(const DT& Val);
DT Pop();
};
//------------------------------------------------------------------------------
MyStack::MyStack(int Size)
{
MaximumNodes = Size;
NumNodes=0;
TopNode = NULL;
}
init list + proper order
template <typename DT>
MyStack< DT >::MyStack(int Size)
: TopNode(NULL), MaximumNodes(Size), NumNodes(0)
{
}
//------------------------------------------------------------------------------
MyStack::~MyStack()
{
while(NumNodes > 0)
{
Pop();
}
}
//------------------------------------------------------------------------------
template <typename DT>
void MyStack<DT>::Push(DT Val)
{
Node *NewNode;
template< typename DT >
void MyStack<DT>::Push(const DT& Val)
{
Node< DT >* NewNode;
if (NumNodes < MaximumNodes)
{
NewNode = new Node(Val);
NewNode->PreviousNode = TopNode;
TopNode = NewNode;
NumNodes++;
}
else { throw "Stack Overflow error"; }
}
//------------------------------------------------------------------------------
template <typename DT>
DT MyStack<DT>::Pop()
{
Node *Popped;
DT PopVal;
if(NumNodes >= 1)
{
Popped = TopNode;
TopNode = TopNode->PreviousNode;
PopVal=Popped->GetVal();
delete Popped;
NumNodes--;
return PopVal;
}
else { throw "Stack Underflow error"; }
}
//------------------------------------------------------------------------------
void main()
int main()
{
MyStack <int>*NewStack(0);
try
{
MyStack <int>*NewStack = new MyStack<int>(5);
NewStack = new MyStack<int>(5); // bad idea anyways
Consider what happens when the try-block throws an exception. Try it,
add an std::cout output to MyStack's d~tor, also add a Node d~tor and
corresponding output, and throw something.
better:
MyStack<int> NewStack(5); // stack allocated
NewStack.Push(6);
NewStack->Push(6);
NewStack->Push(30);
NewStack->Push(2);
NewStack->Push(4);
NewStack->Push(7);
cout << NewStack->Pop() << "\n";
cout << NewStack->Pop() << "\n";
cout << NewStack->Pop() << "\n";
cout << NewStack->Pop() << "\n";
cout << NewStack->Pop() << "\n";
}
At this point in main(), you've lost NewStack. You now officially have
a memory leak.
catch (char *Str)
{
puts(Str);
}
delete NewStack;
NewStack can't be deleted here since it lives inside the try-block's
scope. Another reason why the above allocation does not make sense.
Either allocate outside the scope or declare that NewStack pointer
outside the try-block.
getchar();
}
Amongst errors I get a 'Type mismatch in redeclaration of 'MyStack''
Could somebody please tell me where i'm going wrong!!
Thanks
Daniel
You should reconsider your nomenclature / naming mechanism as well. Its
hard to identify which name represents a variable or a type, a member
function or for that matter a pointer.
#include <iostream>
#include <string>
#include <memory>
template < typename T >
class SingleLinkedList
{
struct Node
{
T t;
Node* p_next;
Node(T t_)
: t(t_), p_next(0) { std::cerr << "Node()\n"; }
~Node() { std::cerr << "~Node()\n"; }
} *p_head, *p_tail;
size_t maxnodes;
size_t count;
public:
SingleLinkedList(size_t);
SingleLinkedList(const SingleLinkedList& copy); //disabled for a
reason
~SingleLinkedList();
void push(const T&);
T pop();
/* friend */
friend std::ostream&
operator<<(std::ostream& os, const SingleLinkedList& r_l)
{
Node* p_current = r_l.p_head;
while(p_current != 0)
{
os << p_current->t << "\n";
p_current = p_current->p_next;
}
return os;
}
};
/* ctor */
template< typename T >
SingleLinkedList< T >::SingleLinkedList(size_t sz)
: p_head(0), p_tail(0), maxnodes(sz), count(0)
{
std::cerr << "SingleLinkedList()\n"; // ah - feedback
}
/* d~tor */
template< typename T >
SingleLinkedList< T >::~SingleLinkedList()
{
while(count > 0)
{
pop();
}
std::cerr << "~SingleLinkedList()\n";
}
/* member functions */
template< typename T >
void SingleLinkedList< T >::push(const T& t)
{
if (count < maxnodes)
{
if (p_head == 0)
{
p_head = p_tail = new Node(t);
} else {
p_tail->p_next = new Node(t);
p_tail = p_tail->p_next;
}
++count;
} else { throw std::string("SingleLinkedList Overflow error"); }
}
template< typename T >
T SingleLinkedList< T >::pop()
{
if(count > 0)
{
Node* p_pop = p_tail;
if(p_head != p_tail)
{
Node* p_prev = p_head;
while(p_prev->p_next != p_tail)
p_prev = p_prev->p_next; // we need to dig for p_tail
p_prev->p_next = 0; // set end
p_tail = p_prev;
} else {
p_head = p_tail = 0; // so you can reuse container
}
T val = p_pop->t;
delete p_pop;
--count;
return val;
}
else { throw std::string("SingleLinkedList Underflow error"); }
}
int main()
{
try
{
const size_t size(5);
SingleLinkedList< double > dlist(size); // stack allocated
for(size_t i = 0; i < size; ++i)
{
dlist.push( i + static_cast< double >(i)/10 );
}
std::cout << dlist;
typedef SingleLinkedList< std::string > StringListType;
std::auto_ptr< StringListType > p_slist(new StringListType(1)); //
auto pointer
p_slist->push("string 0");
// p_slist->push("string 1"); // for an exception test
std::cout << *p;
} // the slist gets zapped here
catch (const std::string& e)
{
std::cerr << e << std::endl;
}
return 0;
}
/*
SingleLinkedList()
Node()
Node()
Node()
Node()
Node()
0
1.1
2.2
3.3
4.4
SingleLinkedList() <-- slist
Node()
string 0
~Node()
~SingleLinkedList() <-- slist
~Node()
~Node()
~Node()
~Node()
~Node()
~SingleLinkedList()
*/
And i'm sure that you'll find a bug or two if you dissect the above.
However, i'm not too worried about that. Consider what happens now when
an exception is thrown. Uncomment the commented line in main(). Can you
see why allocating in main() with new (or whatever) is not good? At
least, with the stack, an auto_ptr or even better - a boost/shared_ptr,
an exception recovers the original system's state.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]