C++

Forum

 
Polymorphism with linked list

dem7w2 (67)
I'm working on a program for an internship interview, and I came across a problem. The program consists of a base class, Document, which PdfDocument and WordDocument derive from. You can't (shouldn't be able to) make a Document by itself. Then I have a class called PrinterQueue which is just a linked list of Documents. You can pop a document from the front or add one to the back. I made a tiny node struct that allowed me to link them together via Node *next;

Anyways, in data structures class, our node class had T data; as a templated variable. Due to a virtual string Type() = 0; in Document, I can't make a Node of type Document because data is not a pointer. Also, if I change that to virtual string Type() {return "undefined";} I now have an error where if I print the contents of PrinterQueue, it says all the Types are undefined instead of .pdf or .doc which they actually should be.

So what is the right thing to do? I thought as an abstract data type, a linked list could link anything together but I guess not. If I change data to *data, and did delete data; in ~Node(), I got an error saying I deleted something that wasn't allocated. Any help would be appreciated.
ne555 (10692)
> it says all the Types are undefined instead of .pdf or .doc which they actually should be.
A base class object behaves as a base class object.
You've got polymorphism when a base class pointer (o reference) refers to a derived object.
So your container should be std::list<Document*>

> I got an error saying I deleted something that wasn't allocated.
¿Did you allocate it? with new
cire (8284)
You must deal with pointers or references to get polymorphic behavior. Storing a pdfDocument or a WordDocument in a Document variable would cause slicing - the part of the class that is unique to pdfDocument or WordDocument is effectively sliced off.


If I change data to *data, and did delete data; in ~Node(), I got an error saying I deleted something that wasn't allocated. Any help would be appreciated.

Make sure the memory is allocated by the linked list so that you can safely delete it (although using a smart pointer would be preferred to manual deletion.)
closed account (D80DSL3A)
I do not see a need for any template classes or functions.
You have a node with a Document* and a node* as members.
I set it up so that the document (pdf or word) is allocated to the Document in the node.
For brevity, I have used the class names doc (abstract base), pdfDoc and wordDoc (both derived from doc).

The following works:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
#include <iostream>

using namespace std;

class doc// abstract base
{
    public:
    int myNum;
    virtual void show(void)const = 0;// print a message
    virtual doc* clone(void)const  = 0;// for dynamic copy
    doc( int MyNum ): myNum( MyNum ) {}
    virtual ~doc() {}
};

class pdfDoc : public doc
{
    public:
    virtual void show(void)const { cout << "pdf doc # " << myNum << "here." << endl; }
    virtual pdfDoc* clone(void)const { return new pdfDoc(*this); }
    pdfDoc( int MyNum ): doc( MyNum ) {}
};

class wordDoc : public doc
{
    public:
    virtual void show(void)const { cout << "word doc # " << myNum << "here." << endl; }
    virtual wordDoc* clone(void)const { return new wordDoc(*this); }
    wordDoc( int MyNum ): doc( MyNum ) {}
};

struct node
{
    doc* pDoc;// the document will be allocated to this *
    node* next;
    // ctor to create a node with a pdf document
    node( const pdfDoc& pdf_doc, node* Next ): pDoc(new pdfDoc(pdf_doc)), next(Next) {}
    // ctor to create a node with a word document
    node( const wordDoc& word_doc, node* Next ): pDoc(new wordDoc(word_doc)), next(Next) {}
    // copy ctor
    node( const node& rNode ): pDoc( rNode.pDoc->clone() ), next(NULL) {}//( rNode.next ) {}
    ~node() { delete pDoc; }
};

class printerQueue
{
    public:
    node* front, *back;

    printerQueue(): front(NULL), back(NULL) {}
    ~printerQueue();

    void push_back( const pdfDoc& pdf_doc );
    void push_back( const wordDoc& word_doc );
    bool peek( const doc*& pDoc );// value returned thru *
    bool pop_front(void);// node is destroyed
    void showAll(void);
};

printerQueue::~printerQueue()
{
    unsigned N = 0;
    while( front )
    {
        node* temp = front;
        front = front->next;
        delete temp;
        ++N;
    }
    cout << "printerQueue dtor: " << N << " nodes deleted." << endl;
}// dtor

void printerQueue::push_back( const pdfDoc& pdf_doc )
{
    if( back )
    {
        back->next = new node( pdf_doc, NULL );
        back = back->next;
    }
    else
    {
        front = back = new node( pdf_doc, NULL );
    }
}
void printerQueue::push_back( const wordDoc& word_doc )
{
    if( back )
    {
        back->next = new node( word_doc, NULL );
        back = back->next;
    }
    else
    {
        front = back = new node( word_doc, NULL );
    }
}

bool printerQueue::peek( const doc*& p_Doc )// value returned thru *
{
    if( front )
    {
        p_Doc = front->pDoc;
        return true;
    }

    p_Doc = NULL;
    return false;
}
bool printerQueue::pop_front(void)// node is destroyed
{
    if( front )
    {
        node* temp = front;
        front = front->next;
        delete temp;
        if( front == NULL ) back = NULL;// EDIT: Added this line
        return true;
    }
    return false;
}
void printerQueue::showAll(void)
{
    for( node* pNode = front; pNode != NULL; pNode = pNode->next )
    {
        pNode->pDoc->show();
    }
}


int main()
{
    printerQueue Q;

    // for node ctor args, etc..
    pdfDoc pdf_temp(1);
    wordDoc word_temp(1);

    // add some nodes
    Q.push_back( pdf_temp );// pdf - 1
    Q.push_back( word_temp );// word - 1
    word_temp.myNum = 2; Q.push_back( word_temp );// word - 2
    pdf_temp.myNum  = 2; Q.push_back(  pdf_temp );// pdf - 2

    // show the list contents
    Q.showAll(); cout << endl;

    // pop a node then showall again
    Q.pop_front();
    Q.showAll();

    // peek
    const doc* pDoc = NULL;
    Q.peek( pDoc );
    if( pDoc )
        cout << endl << "front ele = "; pDoc->show();

    cout << endl;
    return 0;
}


EDIT: Correction to printerQueue::pop_front()
Last edited on
ne555 (10692)
1
2
 
    // ctor to create a node with a pdf document
    node( const pdfDoc& pdf_doc, node* Next ): pDoc(new pdfDoc(pdf_doc)), next(Next) {}
¿why did you do the clone method? You are coupling with all the derived classes, if you want another document type you'll need to add a method to node (¿?)

> I do not see a need for any template classes or functions.
Because the container logic does not depend on the elements. The code is already there, you just need to reuse it.
dem7w2 (67)
Thanks for all the help, especially fun2code. Sorry for the template confusion -- I was reusing a templated node I've used before, and did not realize I could use <Document*> as a template type. Anyways, the node is no longer an issue. When I have some time I need to run it through valgrind again and see if I have any memory leaks.

fun2code, I understand why you did two ctors for node -- one for pdf and one for word -- but I believe I could just pass in Document* instead and set pDoc to that.

I'll update this when the problem is resolved.
closed account (D80DSL3A)
@ne555. I used the clone method because I set up this queue for each node to own the document stored in it. A copy of the document will have to be made from the local instance of a document passed to the push_back().

Oddly, I included the clone() just to handle the copy ctor issue with the node structure, forgetting that I could also use it to provide a single "type neutral" ctor for the nodes. With this node ctor I no longer need to add new ctors for new document types:
 
 
node( const doc& r_doc, node* Next ): pDoc( r_doc.clone() ), next(Next) {}


Now I can make due with a single push_back() for the printerQueue class:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
void printerQueue::push_back( const doc& r_doc )
{
    if( back )
    {
        // the node ctor will construct the right document type via use of the virtual clone()
        back->next = new node( r_doc, NULL );
        back = back->next;
    }
    else
    {
        front = back = new node( r_doc, NULL );
    }
}

Is that better? What were you thinking of?

@dem7w2: I am down to 1 ctor now.
If you were to pass in a Document* and just equate pDoc to it then the node would not "own" the document. The printerQueue would merely be a list of pointers to Documents allocated elsewhere. It could be done this way and it would be somewhat simpler too.
Besides, the extra dynamic allocation issue makes the problem more interesting.
Last edited on
ne555 (10692)
Yep, that was what I mean.
closed account (D80DSL3A)
@ne555:
Thanks. That was quite the oversight on my part, not using the clone() for the primary purpose that one would add the method for!

ne555 wrote:
> I do not see a need for any template classes or functions.
Because the container logic does not depend on the elements. The code is already there, you just need to reuse it.

I think I get this. If I create a template class for the node, I would be able to use the queue for any type which provides a virtual clone(), not just Document types.
closed account (D80DSL3A)
Following up further then...

Here is a (workable) generic queue class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
// T = data type, N = node type
template<class T, class N>
class myQueue
{
    public:
    N *front, *back;

    myQueue(): front(NULL), back(NULL) {}
    ~myQueue();

    void push_back( const T& r_data );
    bool peek( const T*& rpData );// value returned thru *
    bool pop_front(void);// node is destroyed
};

template<class T, class N>
myQueue<T,N>::~myQueue()
{
    unsigned nodeCount = 0;
    while( front )
    {
        N* temp = front;
        front = front->next;
        delete temp;
        ++nodeCount;
    }
    cout << "myQueue dtor: " << nodeCount << " nodes deleted." << endl;
}// dtor

template<class T, class N>
void myQueue<T,N>::push_back( const T& r_data )
{
    if( back )
    {
        back->next = new N( r_data, NULL );
        back = back->next;
    }
    else
    {
        front = back = new N( r_data, NULL );
    }
}

template<class T, class N>
bool myQueue<T,N>::peek( const T*& rpData )// value returned thru *
{
    if( front )
    {
        rpData = front->pData;
        return true;
    }

    rpData = NULL;
    return false;
}

template<class T, class N>
bool myQueue<T,N>::pop_front(void)// node is destroyed
{
    if( front )
    {
        N* temp = front;
        front = front->next;
        delete temp;
        if( front == NULL ) back = NULL;
        return true;
    }
    return false;
}


Here's a "special" type of node for use with types which implement the virtual cloning() method:
1
2
3
4
5
6
7
8
9
10
 
// a special type of node for types supplying a clone method
template<class T>
struct cloningNode
{
    T* pData;
    cloningNode* next;
    cloningNode( const T& r_data, cloningNode* Next ): pData( r_data.clone() ), next(Next) {}
    cloningNode( const cloningNode& rNode ): pData( rNode.pData->clone() ), next(NULL) {}//( rNode.next ) {}
    ~cloningNode() { delete pData; }
};


Here's a simple driver for using a myQueue with cloningNodes to hold doc types:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
int main()
{
    myQueue< doc, cloningNode<doc> > Q;

    // for node ctor args, etc..
    pdfDoc pdf_temp(1);
    wordDoc word_temp(1);

    // add some nodes
    Q.push_back( pdf_temp );// pdf - 1
    Q.push_back( word_temp );// word - 1
    word_temp.myNum = 2; Q.push_back( word_temp );// word - 2
    pdf_temp.myNum  = 2; Q.push_back(  pdf_temp );// pdf - 2

    // show the list contents
    for( cloningNode<doc>* pNode = Q.front; pNode != NULL; pNode = pNode->next )
        pNode->pData->show();

    cout << endl;

    // pop a node then showall again
    Q.pop_front();
    for( cloningNode<doc>* pNode = Q.front; pNode != NULL; pNode = pNode->next )
        pNode->pData->show();

    // peek
    const doc* pDoc = NULL;
    Q.peek( pDoc );
    if( pDoc )
        cout << endl << "front ele = "; pDoc->show();

    cout << endl;
    return 0;
}


ne555: Is this about what you meant for a template setup?

@dem7w2: I don't mean to hijack your thread here! I hope that you are finding these posts useful.
ne555 (10692)
Kind off, but prefer to simply use the STL than implement the container myself.
With the `cloningNode' the memory management is solved, so one less thing to worry about :)

By the way myQueue< doc, cloningNode<doc> > Q;
The template parameters are dependent (the nodes will contain the type of the data),
so to avoid misuse you could 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class T>
struct cloningNode{
   typedef T data_type;
//...
};

// N = node type
template<class N>
class myQueue
{
public:
   typedef typename N::data_type data_type; // the `T'
//...
};
And instantiate it as myQueue< cloningNode<doc> > Q;
closed account (D80DSL3A)
Thanks. I saw that flaw in the template parameter list too but I did not know how to close the loophole.

Topic archived. No new replies allowed.