Instrusive List Container using the Base class as the node

[pnayak]

Hi,

I am trying to write an intrusive List template class that accepts any type that is derived from a class called Link. I've derived a class called Student from Link to experiment. When I use the Link and Student class without List they work very well but when I used them through the List class the new operator doesn't throw but seems to be return 0.

I've pasted the full code here and the program output. The commented part of main works very well. The issue I think is specifically in the List<T>::add(T t) function where new is being called. Does anyone know the reason?

Many Thanks,
pnayak

I am using gcc 3.4.6 on FreeBSD .

Output from the Program
p->next was not allocated
p->next was not allocated
Id:10 Name:Jack

Program Source Code

#include <iostream>
 
struct Link
{
    Link():next(0) {};
    Link(const Link& l):next(l.next) {};
    virtual void print() const {std::cout<<"parent\n";} ;
    Link* next;
};
 
class Student: public Link
{
    public:
        Student(int id, char * name): Link(), id_(id), name_(name) {}
        Student(const Student& s): Link(s), id_(s.id_), name_(s.name_) {}
        virtual void print() const { std::cout<<"Id:"<<id_<<" Name:"<<name_<<'\n'; }
 
    private:
        int id_;
        char* name_;
};
 
template<class T> class List
{
    public:
        [indent]List():head(0) {};
        void print() { for (Link* p = head; p; p = p->next) p->print(); }
        void add(const T& t);
 
    private:
        Link* head;
};
 
 
template<class T> void List<T>::add(const T& t)
{
    Link* p;
 
    if (!head)
    {
        head = new T(t);
        if (!head)
            std::cout<<"head was not allocated\n";
        return;
    }
 
    for ( p = head; p->next; p = p->next)
 
    p->next = new T(t);
 
    if (!p->next)
        std::cout<<"p->next was not allocated\n";
}
 
int main()
{
    List<Student> students;
 
    students.add(Student(10, "Jack"));
    students.add(Student(12, "Jill"));
    students.add(Student(14, "Bill"));
    students.print();
 
    //Link* head = NULL;
    //Link* t = NULL;
 
    //Student s(25, "George");
 
    //head = new Student(10, "Purush");
    //head->next = new Student(12, "Jack");
    //
    //for (t = head; t->next; t = t->next);
 
    //t->next = new Student(20, "Bill");
    //t = t->next;
    //t->next = new Student(s);
 
    //for (t = head; t; t = t->next)
    //    t->print();
 
}

[Savage]

I believe you are missing a semicolon here ;)

template<class T> void List<T>::add(const T& t)
{
 
    Link* p;
 
    if (!head)
    {
 
        head = new T(t);
        if (!head)
        std::cout<<"head was not allocated\n";
        return;
 
    }
 
    for ( p = head; p->next; p = p->next)//<-----
 
    p->next = new T(t);
 
    if (!p->next)
    std::cout<<"p->next was not allocated\n";
 
}

[pnayak]

OH MY HOLY GOD. You are right.

I wasted an entire evening on this. I pretty much tore apart the c++ template vocabulary to understand this "obscure" behavior. Turned out to be a semi colon !!!!.

Thank you so much.
Purush

[weaknessforcats]

I don't think you object model is correct. That is, a Student is not a Link. A Student can be a member of a Link.

So there should be a pointer to a Student in the Link.

Also, the Link is not a list. It's just a link. I expect there is a missing class LinkedList that has Link pointers to the beginning, end and current position in the list.

Doing it this way, you create a LinkedList, have a member function, like AddToEnd, take a Student* argument and it is there you create the Link and install the Student* in the Link and add the Link as the new end of the LinkedList.

Once you get this working, you convert your code to a template so the Student* becomes a T*. That's how you get multiple types in your Link rather than incorrectly using inheritance.

[pnayak]

That's a nice point, however, what I am trying to do here is to develop an intrusive list and not a non-intrusive list, which is what you are describing. One way of developing an intrusive list it to use the Link object as a member of the application class. The other option is to make the Link a common base class.

I am trying to ascertain whether intrusive lists have better performance as opposed to non-intrusive lists since the Link class does not need to have an additional pointer to an application object (the Student in this case) since the application object has the link embedded in it. However the drawback being that there is no non-obscure way of using a list of built-in types. On the other hand, a non-intrusive list is really somewhere down below an intrusive list. Because to implement any list structure there needs to be something in common among the list items based on which we can traverse the list.

So now, I create a new list based on the previous list. And see how much performance slow down is observed when traversing a large list. And see if it worth forcing users (of the class) to force to derive from a common base class or just let them use a non-intrusive list.

If you know anything more on the topic please do let me know.

Purush

[weaknessforcats]

One way of developing an intrusive list it to use the Link object as a member of the application class. The other option is to make the Link a common base class.

The List object as a member of the Student is identical to private inheritance. That is, you inherit the List but not the List interface.

Your real question is whether the Student can vary indendently from List. Like if the Student changes do you have to traverse your entire list to find the thing to change or does the change to Student occur independently.

In the first case you can use a member List but in the second you can't. Instead you will need a List with nodes that contain pointers (or handles) to Student.

That means this is larger than a simple question of performance. You are really comparing two different object models and they are not equivalent so your comparison results won't make sense.

[pnayak]

I completely disagree.

The choice of intrusive and non-intrusive lists with regards to performance and flexibility is very important in Container design and form a fairly large part of any literature that deals with the topic. Their comparison is very important and makes a lot of sense.

[weaknessforcats]

Maybe you should read this.

http://www.codefarms.com/publication.../Intrusive.pdf.

[pnayak]

That's the same paper from which I was testing the conclusion. The entire paper is about comparing the the two types on performance and flexibility. But according to you they are not equivalent and comparing them makes no sense!

You should also read The C++ Programming Language by Stroustrup [16.2]. That will give you a better understanding of the concepts involved.

Here are a few of lines from the papers abstract.

This article compares two styles of building data structures and data structure libraries in C++: (a) Intrusive data structures formed by pointers stored inside the application objects, (b) Containers where auxiliary objects form the required data structure, and only point to the application objects without adding any pointers or other data to them.

Each style works better in different situations, and the first half of the article discusses the impact of this choice on program performance, code maintainability, ease of use and data integrity.

[weaknessforcats]

Each style works better in different situations, and the first half of the article discusses the impact of this choice on program performance, code maintainability, ease of use and data integrity.

This is what I meant by saying there are two object models. Intrusive containers work poorly where the objects need to change independently of the container.

Maybe I just wasn't communicating clearly.