Raw pointer in a std vector, stack and queue

Question

I have following problem with a binary tree:

....

template class BinaryTree { private: template struct Node { T value; Node* left; Node* right; }; private: Node* root;

std::stack<Node<T>const *> stack;

stack.push(root);

while(false == stack.empty())
{
    Node<T>*  node = stack.pop();

    this->visited(node->value);

and after that when I tried to implement breath first search: template class BinaryTree { private: template struct Node { T value; Node* left; Node* right; }; private: Node* root;

std::stack<Node<T>const *> stack;

stack.push(root);

while(false == stack.empty())
{
    Node<T>*  node = stack.pop();

    this->visited(node->value);

I have received an error:

Error 4 error C2440: 'initializing' : cannot convert from 'void' to 'BinaryTree::Node *' c:\users\stephan\documents\visual studio 2012\projects\graphs\binarytree\binarytree.cpp 152 1 BinaryTree

NPE NPE · Accepted Answer · 2013-11-09T20:59:07

The problem is here:

Node<T>*  node = stack.pop();

pop() removes the element and returns void. Use top() beforehand.

Node<T>*  node = stack.top();
stack.pop();

The original STL documentation explains the reasons behind this design:

One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack.

Raw pointer in a std vector, stack and queue

1 Answers