Overloading << operator on template classes

Question

I have made a template class for a node in a linked list and I'm trying to have it output its contents to an output stream by overloading <<. However my current code:

#include <iostream>
using namespace std;
template<class NType> class Node;

template<class NType>
class Node {
private:
        void deletePointer(NType* p);
public:
        NType data;
        Node *prev, *next;

        template<typename T>
        struct is_pointer { static const bool value = false; };

        template<typename T>
        struct is_pointer<T*> { static const bool value = true; };

        Node();
        Node(NType data);
        ~Node();
};  

int main() {
        Node<int> *n1 = new Node<int>();
        Node<int> *n2 = new Node<int>(10);

        std::cout << "Node 1: " << n1 << std::endl;
        std::cout << "Node 2: " << n2 << std::endl;
}

template<class NType> inline std::ostream & operator << (std::ostream& out, const Node<NType> &node){
        out << node.data;
        return out;
}

template<class NType> inline Node<NType>::Node()
            :data(NULL), prev(NULL), next(NULL)
{
}

template<class NType> inline Node<NType>::Node(NType data)
            :data(data), prev(NULL), next(NULL)
{
}

template<class NType> inline Node<NType>::~Node(){
        if(is_pointer<NType>::value){
                deletePointer(&data);
        } else {
                return;
        }
}

template<class NType> inline void Node<NType>::deletePointer(NType* p){
    delete p;
}

Outputs memory locations rather than the data within the nodes. This happens with primitive types such as int and the like as if it didn't know what kind of data was in the NType container.

Node 1: 0x741010
Node 2: 0x741030
Node 3: 0x741070
Node 4: 0x741090

I've tried using typename rather than class but still no dice... Is there any way to dynamically find out what type the template is using and cast or something prior to insertion? I know I can make a ton of redundant code for all the primitives but that seems wasteful and unnecessary.

If it helps any, I'm compiling on Arch Linux x64 with GCC v4.6.2 20111223

Edit: Since a lot of people are mentioning it. I've also tried putting the class outside as a friend and as a stand alone function neither of which work because the stream outputs address rather than the data itself regardless of where I put it. There are no private data values to be accessed so it's OK for it to not be a friend.

Edit: Test case: http://ideone.com/a99u5 Also updated source above.

Edit: Added the remaining portion of my code to assist Aaron in his understanding of the code.

Solution 1

Your code declares the operator<< as a member function, so it would actually take the this pointer as first argument and ostream as second. Instead it needs to be a free function:

template<class NType> class Node {
public:
    NType data;
    Node *prev, *next;
};
//Note how this is declared outside of the class body, so it is a free function instead of a memberfunction
template<class NType> inline std::ostream& operator<<(std::ostream& out, const Node<NType>& val){
    out << val.data;
    return out;
}

however if your operator<< needs access to private data you need to declare it as a friend function instead:

template<class NType> class Node {
public:
    NType data;
    Node *prev, *next;
    friend std::ostream& operator<<(std::ostream& out, const Node& val){
        out << val.data;
        return out;
    }
};

Now for your output: If your operator<< was invoked the compiler would know the type of NType and do the right thing when streaming the data member. However since your operator<< should not have worked (as written) and it seems to give you memoryaddresses as output I would assume you have something like the following:

Node* n = new Node();
std::cout<<n;
//When it should be:
std::cout<<*n;

Now just for curiosity sake: Why are you implementing what looks curiously like a linked list yourself instead of simply using std::list?

Edit: Now that we can see the testcase it seems the assumptions about how the operator<< was called was correct. The output needs to be changed to:

std::cout << "Node 1: " << *n1 << std::endl;
std::cout << "Node 2: " << *n2 << std::endl;

to actually invoke the operator<< for Node, instead of the generic one for T*

Solution 2

Why are you adding a template<class NType> in front of your already templated class method?

Generally, the best way of overloading operator<< is to make it a friend:

template<typename NType>
friend std::ostream& operator<<(std::ostream& out, const Node<NType>& node)
{
    out << node.data;
    return out; 
}

Edit: To respond to the comment below, this is what I mean:

When you define a class template in the header, you don't redeclare that template for the member functions of the class:

template<typename T>
class Foo
{
    T some_data;

    void member_fn();
}

This is required when you're declaring a non-member friend function, however:

template<typename NType>
class Node 
{
public:

    NType data;
    Node<NType> *prev, *next;

    //Note the different template parameter!
    template<typename NType1>
    friend std::ostream& operator<<(std::ostream& out, const Node<NType1>& node);
};

Implementation of that then becomes the above template<typename NType> std::ostream& operator<<(std::ostream& out, const Node<NType>& node) implementation.

Solution 3

template <class NType>
class Node
{
  public:
    NType data;
    Node *prev, *next;
};

template <class NType>
inline std::ostream& operator<<(std::ostream& os, const Node<NType>& n)
{
    return out << n.data;
}

Comments

[TechWiz]

I've tried that previously (and again once you re-mentioned it just in case), but same deal.

[TechWiz]

I don't follow. You also put template<typename NType> infront of your class? Also this returns addresses as well. Am I missing something else here?

[TechWiz]

I'm aware there are multiple renditions of a linked list on the interwebs and in the standard libraries but I was just trying to put this so I can control how it functions for the sake of my personal understanding of my own data structure.

[TechWiz]

Sorry, I got a little sloppy with my copy and pasting. The function was declared in the class definition and defined outside of the class. But for the sake of brevity I moved it into the class. That was clearly a stupid idea as it created more confusion that it should have it seems.

[TechWiz]

... Wow such a silly mistake... I feel like such a novice haha. Thank you kindly.

[TechWiz]

Yea that was the problem thank you. Dang Java tryna instill terrible habits in me.

[Xeo]

@TechWiz: Don't hold that feeling dear, it'll come back to you soon enough again. ;)

[TechWiz]

The deconstructor checks for pointer data before calling deletePointer, so if data is not a pointer, the deconstructor will not call the function. Also telling delete to delete a member variable from outside of its own deconstruction code seems like something that should bug regardless of if it were properly constructed code or not. That just seems like bad programming. The deconstructor is also not supposed to be called directly but should be part of garbage collection when the program closes AND these nodes are part of something larger so its just not even meant to be used that way.

[Aaron McDaid]

@TechWiz, that's not correct, sorry. Let's be clear. Even if data is a pointer type, then it should be deleted with delete data, not with delete &data.

[Aaron McDaid]

Also @TechWiz, this is C++, not Java. You said "... but should be part of garbage collection".

[Aaron McDaid]

is_pointer<NType>::value will be true if and only if X is a pointer type. For, example is NType is int * then it is a pointer type. Further, if NType is int *, then data will be declared as int * data; As a result, you will need to call delete data to delete the int pointed at by data.

[TechWiz]

I'm sorry you are wrong. It works just fine, try it for yourself. The program neither crashes not creates a memory leak. I know this isn't java but by default the deconstructor is called on all non-pointer values when the program is done executing so long as there is one defined. Please look more carefully at the code, the static struct is_pointer will always be false on non pointer types as NType will not be a pointer unless it is, of course, a pointer type. Also the code for deletePointer() is missing from my post but I will happily edit my question to include it.

[TechWiz]

I see what you mean about the bug, however that would only happen if data were an explicit pointer, which it is not. Instead it is a template for all data types, so if it were a pointer, it would be an implicit pointer so you cannot call delete on it directly unless you either cast it to a pointer as you did (which will make the struct is_pointer false in the process) or send it to an alternate function to delete the pointer having been cast during the call (as I have done) to make it an explicit pointer that can be deleted.

[Aaron McDaid]

I would be interested in the code for deletePointer please. Maybe you did void deletePointer(NType* p) { delete *p; }. Or maybe it is void deletePointer(NType* p) { delete p; } instead?

[TechWiz]

It's already posted above in my question, at the end of the code snippet. It's the latter of your two methods.

[Aaron McDaid]

I have tried the code and it crashes with pointer types - See this on ideone. The important thing is that your current test case does not call the destructor. In C++ you must be very explicit about freeing memory. In C++, if you create an object with new it will not be automatically destructed when the program completes. Therefore, I added delete n1; and delete n2;. Every new must have a matching delete in your code. Also, I included a test of the pointers; I changed n2 to be Node<int*> *n2 = new Node<int*>();.

[TechWiz]

Ah I see what you mean. But it isn't how I deleted my pointer, it's the fact that I've deleted my pointer that is causing the issue. There is a "double deletion" of the data variable which is weird since it was causing leaks earlier because GCC refused to clean it up properly. Thanks for catching that, would have been pretty embarrassing to have to post that bug here later =P

[TechWiz]

Also C++ does have garbage collection, it's just very primitive. Otherwise we would have to call delete on every single variable we create and that is clearly not the case. The reason you were having such trouble explaining this issue to me is because you were referring to me not deleting my n1 and n2 variables in my main which would cause an obvious leak, I just wrote the code quickly to get it done and forgot the 2 delete lines. I didn't understand what you were saying about calling delete &(n1->data); because that's like calling int x; delete &(x); which is definitely gunna crash.

[Aaron McDaid]

It is not a double deletion. It is memory corruption. Here is a much simpler example that demonstrates the problem on ideone

[TechWiz]

That isn't even the same kind of error. Your second ideone test case crashes because you are forcing the deletion of the data member variable which is an implicit pointer, and thus the reason you must cast the variable before you delete it. Please cite an example where it makes sense to go in and delete a member variable from outside the class itself. That just does not seem like proper programming methodology. Also since this is a data node in a linked list, one would delete the entire entity not the data within unless one wanted to reuse the container but for that I made a swap method.

[Aaron McDaid]

Looking again at the first crash, I can make a small change that demonstrates that it is not a double deletion. In version 2 I have made a very small change. I changed the order that the variables are listed; now prev and next are listed before data. Now it crashes with *** glibc detected *** ./prog: free(): invalid pointer: 0x08901020 ***

[TechWiz]

To assess your concerns with the second ideone test case, you are not deleting the data member. Since you made the Node hold a int*, the member data is a pointer so doing delete &(a->data); is deleting a pointer to a pointer which does not exactly exist in memory. To delete the member one does delete a->data; as it is already a pointer. Here is a test case for it: ideone.com/uBinY

[Aaron McDaid]

I can explain all these details, and I know why the error changed from "double deletion" to "invalid pointer". I'm sorry if I was rude earlier, but I am quite confident in my knowledge of these issues.

[TechWiz]

Purge the deletePointer() function and the code works fine, as I stated earlier due to it attempting to delete an already deleted member variable after deletePointer() is called. The reason its a double deletion is because data is an NType type not a NType*. If data were an NType* then yes, you would be completely correct. However, a default deconstructor is called on all non pointer types, including NType. Here's an example that more closely represents my current codebase to prove my point: ideone.com/eTdng

[Aaron McDaid]

Here are two more examples that demonstrate working and broken behaviour. I can see you don't like deleting items from outside, so I've changed that. In version 4a the code crashes. In version 4b. In these examples I have created a new type, called MyOwnType, which prints out a helpful message as it is being destructed. I have then changed main so that it creates one of these objects and stores in in a Node<MyOwnType*> *n3 = new Node<MyOwnType*>( ..... . In the second version I fixed it by using delete *p; instead of delete p.

[Aaron McDaid]

Within Node<int*>, NType is a pointer type. That is non-negotiable and therefore you should delete it with delete data; at some point.

[TechWiz]

Do you have a linux terminal available to you? Checking my code with valgrind I have no leaks whatsoever yet your code does indeed leak as you say. I think this is an issue between pointers to primitives with default deconstructors and pointers to classes. I see the issue you are talking about now and the reason it didn't make sense is because my code does not produce leaks with pointers to int* but int* alone would create a leak. I'm pretty sure this is why I created the deletePointer() method but I was thrown way off by int* not creating leaks.

[Aaron McDaid]

Here are three further examples based on your latest code. In the first version, I simply have the MyOwnType and have created Node<MyOwnType*> *n2 to store it. As expected, this runs OK. In the second version the destructor ~Node includes a call to delete the object pointed to be data; this version runs correctly, you can see the helpful message "I'm being destructed. Bye bye!". Finally, in the third version I have used delete &data. The third version crashed with the "invalid pointer" error.

[Aaron McDaid]

There is a very particular reason why you latest code ideone.com/eTdng does not report any leaks. You have called delete n1 and delete n2, which is good of course. But also, you did not specify any initial value in the brackets in new Node<int*>();. As a result, the data member was set to a null pointer - very similar to the null reference in Java. As a result, you didn't see any leaks. (.. to be continued)

[Aaron McDaid]

.... however, if you made a tiny change and you did new Node<int*>(new int); then you would get a leak. You should try valgrind on a version of your code including a call to ` MyOwnType *p = new MyOwnType; Node<MyOwnType*> *n2 = new Node<MyOwnType*>(p);` - you will see a memory leak.

[Aaron McDaid]

In short, int* will create leaks if you pass in a pointer to a constructed int. You said "but I was thrown way off by int* not creating leaks". Try new Node<int*>(new int);

[TechWiz]

Oh I am a serious idiot... I didn't realize I was deleting the pointer I was feeding into the Node elsewhere. Yes, it creates a leak now. Now my problem is that GCC won't allow me to use non pointers in my nodes because it tries to be "smart" and deconstruct an int but ignores the check for pointers completely.

[Aaron McDaid]

Good. I've got a fix for that. ideone.com/waYAw. Here is a version of deletePointer that correctly can work out if it is dealing with a pointer type, and it will call delete if appropriate. Again, note that the "I'm being destructed. Bye bye!" text appears, confirming that the call to delete is correct.

[TechWiz]

Alright, thank you kindly. This is probably the longest thread of comments ever but it's been pretty educational. I think I know more about pointers than I'd like to now haha. I appreciate you sticking around to fully explain this to me and I apologize for ever doubting you (via misunderstandings).

[Aaron McDaid]

No problem. I could have made life easier for myself but given fewer, but better, answers! See you around on StackOverflow!