What is the problem with this piece of C++ queue implementation?

Question

Hi everyone! I'm trying to write a linked queue in C++, but I'm failing so far. I've created 2 files by now: my main.cpp and box.h. When trying to use my box, I receive the following message:

Description Resource Path Location Type conversion from ‘Box*’ to non-scalar type ‘Box’ requested main.cpp /QueueApplication line 14 C/C++ Problem

My code is as follows:

box.h

#ifndef BOX_H_
#define BOX_H_

template<class T>
class Box
{
public:
    Box(T value)
    {
        this->value = value;
        this->nextBox = NULL;
    }
    T getValue()
    {
        return this->value;
    }
    void setNext(Box<T> next)
    {
        this->nextBox = next;
    }
private:
    T value;
    Box<T> nextBox;
};

#endif /* BOX_H_ */

main.cpp

#include<iostream>
#include "box.h"

using namespace std;
int main(int argc, char** argv)
{
    Box<int> newBox = new Box<int>();
    cout << "lol";
    cin.get();
    cin.ignore();
    return 0;
}

Could you guys help me?

PS: before someone ask me why not to use stl ... I'm in a data structures class.

Answer 1

When you use new, you get a pointer to an object, not a plain object. Declare your variable as a pointer or just allocate your object on the stack instead.

I hope this makes sense to you, since if it doesn't, you should probably go back and read more about the basics of OOP in C++.

Answer 2

There are multiple problems here.

First of all, in order to implement a linked list (or a queue that uses a linked list) in C++ you need to use pointers. In Java everything is a reference. C++, on the other hand, makes a clear distinction between objects and pointers to objects. (There are also references to objects, but they are irrelevant here).

Let's also forget the templates for a moment, because they are not part of the problem here.

class Box
{
  int value;
  Box nextBox;  // wrong! should be a pointer
};

is wrong, because nextBox must be a pointer to the next element of the list/queue. The correct way would be Box *nextBox;

By the same token setNext() should also take a pointer to Box as its argument. setNext(Box b) is an example of pass-by-value, i. e. this member function (method in Java lingo) gets its own copy of the entire Box object. This could lead to performance issues if the object is large, not to mention that any changes done to it by the function will be invisible to the caller. What you want instead here is pass-by-reference, which is accomplished by using a pointer.

The final point is that new in C++ always returns a pointer. You should have Box<int> *newBox = new Box<int>;

Answer 3

I believe your nextBox should be a pointer.

Box<T> * nextBox;

Method setNext should deal with pointers too.

void setNext(Box<T> * next)

And newBox should be a pointer.

Box<int> * newBox = new Box<int>(); 

Since you come from a Java background, you are assuming that all of your objects are references. Syntax is a little different in C++.

Answer 4

The problem is with this line

Box<int> newBox = new Box<int>();

The new operator returns a pointer to a Box object created on the heap. The pointer will be of type Box<int>*. The left side of that expression declares a Box object. You can't directly assign a pointer-to-X to an X. You should probably just omit the new keyword unless you have a reason to want to manage the storage lifetime of the object manually. Incidentally, I'm betting you come from Java, where new is always required to create objects. Not so in C++.

Also I think it's awesome that your data structures class is introducing you to templates right off the bat.

Answer 5

Removing unimportant stuff, we see you've declared a new class like this:

template<class T>
class Box
{
    T value;
    Box<T> nextBox;
};

How big is Box<T>?

Clearly

sizeof Box<T> >= sizeof(Box<T>::value) + sizeof(Box<T>::nextBox)
sizeof Box<T> >= sizeof(T) + sizeof(Box<T>)
0 >= sizeof (T)

uh-oh

Answer 6

Guys. No raw pointers in C++ unless you really need them. Please. Especially for some poor soul who doesn't even know that operator new returns a pointer. Get a std::auto_ptr or a std::shared_ptr.