C++

Forum

 
Help with templated doubly linked list assignment?!

jordannn15 (6)
Okay, first off like the title says this is an assignment I need to turn it in soon. My program works until line 62 in main after it has gone through the loop on line 59 four times, then it gives me a seg fault. Would really appreciate the help!

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
 
#ifndef DNODE_H
#define DNODE_H
#include <iostream>

template <class T>
class dnode {
        public:
                dnode(T d = T(), dnode *n = NULL, dnode *p = NULL)
                {datafield = d; nextfield = n; previousfield = p;}

                void set_next(dnode *n) {nextfield = n;}
                void set_prev(dnode *p) {previousfield = p;}
                void set_data(T d) {datafield = d;}

                dnode *next() {return nextfield;}
                dnode *prev() {return previousfield;}
                T data() {return datafield;}

                const dnode *next() const{return nextfield;}
                const dnode *prev() const{return previousfield;}
                const T data() const{return datafield;}

        private:
                dnode *nextfield;
                dnode *previousfield;
                T datafield;
};

#endif 


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
 
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "dnode.h"
#include "node_iterator.h"

template <class T>
class list {
        public:
                typedef node_iterator<T> iterator;
                typedef node_iterator<T> const_iterator;

                list(dnode<T> *h = NULL, dnode<T> *t = NULL) {head = h; tail = t;}
                ~list();

                list(const list& other);
                list& operator =(const list& other);

                void front_insert(const T& item);
                void front_remove();
                void rear_insert(const T& item);
                void rear_remove();

                iterator begin() {return iterator(head);}
                const_iterator begin() const{return const_iterator(head);}

                iterator end() {return iterator();}
                const_iterator end() const{return const_iterator();}

                iterator r_begin() {return iterator(tail);}
                const_iterator r_begin() const{return const_iterator(tail);}

                iterator r_end() {return iterator(head->prev());}
                const_iterator r_end() const {return const_iterator(head->prev());}

                void insert_before(iterator spot, T item);
                void insert_after(iterator spot, T item);
                void remove(iterator spot);

                int size();

        private:
                dnode<T> *head;
                dnode<T> *tail;
};

#include "list.template"

#endif 


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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
template <class T>
list<T>::~list(){
        dnode<T> *cur;

        while(head != NULL){
                cur = head->next();
                delete head;
                head = cur;
        }
        tail = NULL;
}

template <class T>
list<T>::list(const list<T>& other){
        if(!other.head)
                head = tail = NULL;
        else{
                head = new dnode<T>(other.head->data());

                dnode<T> *dest = head;
                dnode<T> *source = other.head;

                while(source != NULL){
                        dest->set_next(new dnode<T>);
                        dest = dest->next();
                        dest->set_data(source->data());
                }
                dest->set_next(NULL);
                tail = dest;
        }
}

template <class T>
list<T>& list<T>::operator =(const list<T>& other){
        if(this == &other)
                return *this;

        dnode<T> *rmptr;

        while(head != NULL){
                rmptr = head;
                head = head->next();
                delete rmptr;
        }

        tail = NULL;
        const dnode<T> *source = other.head;

        while(source != NULL){
                rear_insert(source->data());
                source = source->next();
        }
}

template <class T>
void list<T>::front_insert(const T& item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                head = new dnode<T>(item);
                head->set_next(tail);
                tail->set_prev(head);
        }else{
                dnode<T> *old_head = head;
                head = new dnode<T>(item);
                head->set_next(old_head);
                old_head->set_prev(head);
        }
}

template <class T>
void list<T>::front_remove(){
        iterator rmspot = head;
        remove(rmspot);
}

template <class T>
void list<T>::rear_insert(const T& item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                tail = new dnode<T>(item);
                tail->set_prev(head);
                head->set_next(tail);
        }else{
                dnode<T> *old_tail = tail;
                tail = new dnode<T>(item);
                tail->set_prev(old_tail);
                old_tail->set_next(tail);
        }
}

template <class T>
void list<T>::rear_remove(){
        iterator rmspot = tail;
        remove(rmspot);
}

template <class T>
void list<T>::insert_before(iterator spot, T item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                head = new dnode<T>(item);
                tail->set_prev(head);
                head->set_next(tail);
        }else if(head == spot.current)
                front_insert(item);
        else if(spot.current != NULL){
                dnode<T> *s = spot.current;
                dnode<T> *new_node = new dnode<T>(item, s, s->prev());
                s->prev()->set_next(new_node);
                s->set_prev(new_node);
        }
}

template <class T>
void list<T>::insert_after(iterator spot, T item){
        if(head == NULL)
                head = tail = new dnode<T>(item);
        else if(head == tail){
                tail = new dnode<T>(item);
                head->set_next(tail);
                tail->set_prev(head);
        }else if(tail == spot.current)
                rear_insert(item);
        else if(spot.current != NULL){
                dnode<T> *s = spot.current;
                s->set_next(new dnode<T>(item));
                s->next()->set_prev(s);
                s->prev()->set_next(s);
        }
}

template <class T>
void list<T>::remove(iterator spot){
        dnode<T> *rmptr = spot.current;

        if(rmptr){
                if(head == NULL)
                        std::cout << "Can't remove anything, list is empty.\n";
                else if(rmptr == head && rmptr == tail){
                        delete rmptr;
                        head = tail = NULL;
                }else if(rmptr == head){
                        dnode<T> *new_head = head;
                        head = head->next();
                        delete new_head;
                        head->set_prev(NULL);
                }else if(rmptr == tail){
                        dnode<T> *new_tail = tail;
                        tail = tail->prev();
                        tail->set_next(NULL);
                        delete new_tail;
                        new_tail = NULL;
                }else{
                        rmptr->prev()->set_next(rmptr->next());
                        rmptr->next()->set_prev(rmptr->prev());
                        delete rmptr;
                        rmptr = NULL;
                }
        }
}

template <class T>
int list<T>::size(){
        int len = 0;
        dnode<T> *new_head = head;

        while(new_head != NULL){
                len++;
                new_head = new_head->next();
        }

        return len;
}


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
 
#ifndef NODE_ITERATOR_H
#define NODE_ITERATOR_H
#include <iostream>
#include "dnode.h"

template <class T>
class list;

template <class T>
class node_iterator {
        public:
                friend class list<T>;

                node_iterator(dnode<T> *c = NULL) {current = c;}

                T operator *() {return current->data();}

                bool operator !=(const node_iterator& other) const
                {return current != other.current;}

                bool operator ==(const node_iterator& other) const
                {return current == other.current;}

                node_iterator operator ++() {current = current->next(); return *this;}
                node_iterator operator ++(int);

                node_iterator operator --() {current = current->prev(); return *this;}
                node_iterator operator --(int);

        private:
                dnode<T> *current;
};

#include "node_iterator.template"

#endif
jordannn15 (6)
Here's the rest of my code that I couldn't put in the first part:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
template <class T>
node_iterator<T> node_iterator<T>::operator ++(int){
        node_iterator original(current);
        current = current->next();
        return *this;
}

template <class T>
node_iterator<T> node_iterator<T>::operator --(int){
        node_iterator original(current);
        current = current->prev();
        return *this;
}


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
 
#include <iostream>
#include <fstream>
#include "dnode.h"
#include "list.h"
#include "node_iterator.h"
#include "swatches.h"

int main(){
        list<Swatch> colors;
        list<Swatch> colors2;
        list<Swatch>::iterator it;
        Swatch tmp;

        std::ifstream ifs("swatches.txt");
        while(ifs >> tmp){
                if(tmp.get_red() > tmp.get_green() && tmp.get_red() > tmp.get_blue())
                        colors.front_insert(tmp);
                else if(tmp.get_green() > tmp.get_red() && tmp.get_green() > tmp.get_blue())
                        colors.rear_insert(tmp);
                else{
                        it = colors.begin();
                        for(int i = 0; i < colors.size() / 2; i++){
                                it++;
                                colors.insert_after(it, tmp);
                        }
                }
        }

        ifs.close();

        colors2 = colors;

        colors2.front_remove();
        colors2.rear_remove();
        it = colors2.begin();
        for(int i = 0; i < colors2.size() / 2; i++)
                it++;

        colors2.remove(it);

        it = colors.begin();
        while(it != colors.end()){
                std::cout << *it << std::endl << std::endl << std::endl;
                it++;
        }

        it = colors2.begin();
        while(it != colors2.end()){
                std::cout << *it << std::endl << std::endl << std::endl;
                it++;
        }

        it = colors.r_begin();
        while(it != colors.r_end()){
                std::cout << *it << std::endl << std::endl << std::endl;
                it--;
        }

        it = colors.begin();
        while(it != colors.end()){
                std::cout << *colors.begin() << std::endl << std::endl << std::endl;
                colors.front_remove();
                std::cout << *colors.r_begin() << std::endl << std::endl << std::endl;
                colors.rear_remove();
        }

        it = colors2.r_begin();
        while(it != colors2.r_end()){
                std::cout << *it << std::endl << std::endl << std::endl;
                it--;
        }

        return 0;
}
naraku9333 (2163)
My guess is the iterator becomes invalidated.
jordannn15 (6)
I'm sorry could you elaborate on "becomes invalidated" please?
kevinkjt2000 (1063)
There maybe something wrong with the remove function. Segmentation faults occur when a program accesses memory that it should not be accessing. Somehow remove is not properly fixing the pointers. That is my guess.
naraku9333 (2163)
Meaning it doesn't point to a valid element(or end()) in the container. I'm not certain this is the issue as I haven't tested your code, but this looks suspicious to me. 
1
2
3
4
5
6
7
 
it = colors.begin();
        while(it != colors.end()){
                std::cout << *colors.begin() << std::endl << std::endl << std::endl;
                colors.front_remove();
                std::cout << *colors.r_begin() << std::endl << std::endl << std::endl;
                colors.rear_remove();
        }
jordannn15 (6)
I know it's is either in my remove , insert_before, or inser_after function. I just don't know where or why it is seg faulting I have changed a million things and I just get core dump after core dump.
kevinkjt2000 (1063)
That section of code that naraku pointed out looks suspicious to me as well. You should probably try making the while loop conditional on the size of the list. Setting the condition for when the size of the list is >= 2. If the size of the list is just one deleting two things at once would be bad.
naraku9333 (2163)
After some debugging it looks like you are dereferencing null iterators in the cout statements in that loop, try 
1
2
3
4
5
6
7
8
 
while(colors.size() > 0){
	if(colors.begin() != NULL)
		std::cout << *colors.begin() << std::endl << std::endl << std::endl;
	colors.front_remove();
	if(colors.r_begin() != NULL)
		std::cout << *colors.r_begin() << std::endl << std::endl << std::endl;
	colors.rear_remove();
}
Last edited on
jordannn15 (6)
Yeah naraku9333 that almost works but I need to destroy the whole list. How do I do that?
jordannn15 (6)
Nevermind I got it to work with the code like this:

1
2
3
4
5
6
7
8
9
 
while(colors.size() > 1){
             if(colors.begin() != NULL)
                        std::cout << *colors.begin() << std::endl << std::endl << std::endl;
             colors.front_remove();

             if(colors.r_begin() != NULL)
                        std::cout << *colors.r_begin() << std::endl << std::endl << std::endl;
             colors.rear_remove();
}


Thanks for the help!
Topic archived. No new replies allowed.