Problem with linked lists and templates

[laura90]

I'm trying to write a simple linked list program. The header files are compiling successfully, but when I try to compile my driver program to test the program, I'm getting an error. Here's my driver program:

#include <iostream>
#include "Node.h"
#include "List.h"

using namespace std;

template <typename T>
void fill(List <T> &listObject)
{
    T value;

    cout << "Enter value (or 0 to end): ";
    cin >> value;

    while (value != 0)
    {
        listObject.insertAtBack(value);

        cout << "Enter value (or 0 to end): ";
        cin >> value;
    }
}

int main()
{
    List <int> integerList;
    fill(integerList);
}

The error is flagged in my list.h file, (line 21). Here's the error:

error C2664: 'Node<NODETYPE>::Node(void *)' : cannot convert parameter 1 from 'const int' to 'void *'

    template <typename NODETYPE>
    void List <NODETYPE>::insertAtBack(const NODETYPE &value)
    {
        Node <NODETYPE> *newPtr = getNewNode(value);

        if (isEmpty())
        {
            firstPtr = lastPtr = newPtr;
        }
        else
        {
            lastPtr->next = newPtr;
            lastPtr = newPtr;
        }
    }        

    template <typename NODETYPE>
    Node <NODETYPE> *List <NODETYPE>::getNewNode(const NODETYPE &value)
    {
        return new Node <NODETYPE> (value);
    }

And, if it's a help, here's my Node.h file too:

#ifndef NODE_H
#define NODE_H

template <typename NODETYPE> class List;

template <typename NODETYPE>
class Node
{
    friend class List<NODETYPE>;

    void *info;
    Node *next;

    public:
        Node(void *v) { info = v; next = 0;}
        void put_next(Node *n) { next = n;}
        Node *get_next() { return next; }
        void *get_info() { return info; }
};

#endif

I think I'm doing something wrong with the templates, but am unsure. Thanks in advance for the help!

[mike_2000_17]

So, why is the type of info a void * and not a NODETYPE? If info is supposed to contain the information associated to the node and that the node-type is NODETYPE, wouldn't it be logical that that would be the type of info? As so:

template <typename NODETYPE>
class Node
{
    friend class List<NODETYPE>;
    NODETYPE info;
    Node *next;
    public:
        Node(const NODETYPE& v) { info = v; next = 0;}
        void put_next(Node *n) { next = n;}
        Node *get_next() { return next; }
        NODETYPE get_info() { return info; }
        void set_info(const NODETYPE& v) { info = v; }
};

And that will solve your problem.

[laura90]

The node class was given to me in my assignment - my job is to create the list class. Also, in studying the assignment some more, I realized that I'm not required to use templates. So, to remove that extra confusion, I've begun again, but this time am only interesting in creating a list of int nodes.

#ifndef LIST_H
#define LIST_H

class List
{
    private:
        class Node   //given
        {
            friend class List;

            void *info;
            Node *next;

            public:
                Node(void *v) { info = v; next = 0; }
                void put_next(Node *n) { next = n; }
                Node *get_next() { return next; }
                void *get_info() { return info; }
        };

        Node *head;

    public:
        List()
        {
            head = NULL;
        }

        ~List()
        {
            while (head != NULL)
            {
                Node * n = head->next;
                delete head;
                head = n;
            }
        }

        void addToFront (void *value)
        {
            Node * n = new Node();
            n->data = value;
            n->next = head;
            head = n;
        }

#endif

-----------------------------------------------------------

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

using namespace std;

int main()
{
    List list;

    return 0;
}

So now I'm getting this error on line 41:

error C2512: 'List::Node' : no appropriate default constructor available

Since the node class is given, there must be an error in my list class, but I'm confused by the void *info private member of the node class and am unsure of how work with that. Also, I've never wrapped one class inside of another - why is it necessary for me to declare the List class a friend of the Node class if it's contained within the list class (if I don't do that, I get an error for trying to access Node's private members at line 33)?

Thanks for your time.

[mike_2000_17]

Since the node class is given, there must be an error in my list class, but I'm confused by the void *info private member of the node class and am unsure of how work with that.

The node class uses a technique called "type-erasure" (or at least, that's what I understand that it's trying to do). Basically, it stores the value as a void-pointer which means that you have to cast it back and forth to set or get the value. Type-erasure is a horrible technique (and should only be used in very specific performance-critical things), and if that is code given by your prof., then he's a pretty horrible prof because type-erasure can be avoided completely (e.g., with templates), can be very dangerous in the hands of a beginner, and should not be taught at this level. The problem is that type-erasure is common in C, and some people think it's normal (and even, a "good" technique), it's not!

So, I say, if you are unsure of how to work with that void* info, then I say: Good! Forget about this void-pointer business and use the template solution you posted originally, and using the Node class that I posted as a fix.

If you only need a list of int variables, then take the template solution, replace every occurence of NODETYPE with int, and then remove the template <class NODETYPE> part.

Or, take the non-template version and replace void * with int.

[laura90]

From what I've been reading, I've been starting to realize that the void* stuff is similar to a template's function, though templates seem cleaner. Thanks for explaining that more fully.

Can you provide an example of how to do the type casting for type erasure? I can't seem to find any examples.

[mike_2000_17]

Can you provide an example of how to do the type casting for type erasure? I can't seem to find any examples.

Here is a simple example of "type-erasure":

void some_function(void* points_to_anything) {
  // cast the pointer to an int:
  int* points_to_int = static_cast<int*>(points_to_anything);
  // do something, like answering the Ultimate Question of Life, 
  //  the Universe, and Everything:
  *points_to_int = 42;
};

int main() {
  // create an integer:
  int value = 0;
  // call the type-erased function:
  some_function(static_cast<void*>( &value ));  // note, static_cast is not necessary.

  // print the result:
  std::cout << "The Answer to the Ultimate Question of Life, the Universe, and Everything is " << value << std::endl;

  return 0;
};

This is used extensively in C to allow for functions that can take anything as a parameter (e.g., often used to define callback functions in C APIs, allowing the user to provide a void* to be forwarded to the callback function when it gets called, this is often called the "userdata" parameter or pointer). But unless you are interfacing with a C library, there is very little reason to use this technique in C++. And this technique is inherently unsafe because the type information (the type of variables) is the first and most important consistency-assurance mechanism in C++ (or any other strongly-typed language), and erasing the type of variables is dangerous (when casting to a void-pointer you lose any information about the actual type of the pointee, i.e., its type is erased, and the compiler can no longer insure that you use the pointee correctly).

There are only few marginal cases where type-erasure can be useful, and it is always buried deep in the guts of a library (in the encapsulated implementation details), never as part of interfaces (e.g., void-pointers as parameters to functions). At least, when you talk about decent-quality libraries, of course (there is a lot of junk out-there too).

From what I've been reading, I've been starting to realize that the void* stuff is similar to a template's function, though templates seem cleaner.

Exactly, the type-erasure technique is basically a really bad alternative to templates, for where templates aren't possible (like in pretty much any programming language except C++ or D). In C#, Java, Delphi and many other languages, they do this with an Object base-class (i.e., a mandatory (and implicit) base-class for absolutely every other class), which makes type-erasure a bit better because you can retrieve type-information back from the type-erase pointer (or reference). Overall, in C++ (or D), templates are much preferred, because it is not only cleaner, but also safer because the compiler can do all the type-consistency analysis during compilation (instead of delegating it to the run-time, as either a run-time error or a crash, or worse).