C++

Forum

 
Segmentation fault with empty string

rodentMinn (10)
I've been in panic recently because I have code that works fine on one computer,
but crashes on the server where I submit my code. I have a class called "Person" which carries a string called "givnName" which represents a given name for the person. When overloading the ">" operator, I made a boolean to take the right-hand side Person and check to see if its givnName string is empty. That works fine in one computer, but with a segmentation fault on the server. Any help would be greatly appreciated. Bare in mind also that I am not using C++11. I think I'm using C++98.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
class Person
{
public:
	string givnName;        // The person's given name
	string lastName;        // The person's last name
	string birth;           // The person's date of birth
	int year;               // The person's birth year
. . .
    bool operator > (const Person & rhs) const
    {
        // Set up booleans to determine who has what data. If it is
        // not empty, the bool will be labeled as "true".
        bool gn = !givnName.empty();
        bool rgn = !rhs.givnName.empty();   // <-- Segmentation Fault Here
        bool ln = !lastName.empty(); 
        bool rln = !rhs.lastName.empty()
        bool b = !birth.empty();
        bool rb = !rhs.birth.empty();
. . .


If you have a question or if you need more code, please tell me.
Last edited on
Thomas1965 (4571)
The code you have shown us looks ok.
Calling the empty method on a string will not cause a Segmentation fault.
The problem must be somewhere else.
Best is to show the complete code.
dhayden (5795)
I think it's most likely that you're passing garbage for rhs. As Thomas1965 said, post your full code.
rodentMinn (10)
So what my whole program is supposed to do is take a "GEDCOM" file and based on the data present, place them in a sorted linked list by last name, or if last names don't exist or they are the same, by given name, and if they are still the same, by their birth year, if that makes sense.

I used my own list class and it has its own iterator class. Doing a backtrace, I found out this happens on the way to the crash.

My main function looks like 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
 
int main()
{
    // We need a list of Persons.
    List<Person> a;
    // Read the GEDCOM file and add the data from that file
    // to our list. That data being the last and given names,
    // plus the individual identifier and date of birth.
    bool r = read(a);
    // If the file was not read correctly, exit the program.
    if (r == false)
    {
        return 1;
    }
    // Save our sorted list of Persons to a file called "sorted.dat".
    bool w = write(a);
    // If the file was not written correctly, exit the program.
    if (w == false)
    {
        return 1;
    }
    // The program completed successfully at this point. End
    // the program.
	return 0;
}


Then it passes the list by reference to a read function which carries 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
 
    // Set up a scanner. The GEDCOM file starts with a
    // number followed by a keyword.
    int scan;
    string keyword;
    // This boolean variable will indicate whether we are reading
    // a birth day or not.
    bool bday = false;
    // We are dealing with "Persons", so we need to make a person;
    Person p;
    // So long as the file is open and there is data
    // to be read...
    while(fin.is_open() && fin >> scan)
    {
    . . .
        // If we scanned a 3...
        else if (scan == 3)
        {
            // The only thing that follows a 3 is a TIME code, and the
            // end of an individual record. We now send the person to
            // our list. Unless of course, there was no data to apply
            // to a person.
            if (p.id != -1)
            {
                data.sortedInsert(p); // My list class has a function called sortedInsert to keep 
                                      // in sorted order.
            }
            // Clear out our person data so we can use it again.
            p.clear();
        }
    }


As stated in my code, my linked list class has a function called sortedInsert which inserts items in sorted form.
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
 
template <class T>
void List <T> :: sortedInsert(const T & t) throw (const char *)
{
    // Set an iterator to the beginning of the list.
    ListIterator<T> it = this->begin();
    // Set up a boolean to determine whether we found the right
    // spot or not.
    bool found = false;
    // Now then, until we either ran to the end of the list or
    // we find he right spot to insert at...
    while (found == false && it != this->end())
    {
        // Is this item greater to what we are pointing to in
        // the list?
        if (t > *it) // <- This is where it checks to see if what is being added is greater than what is already
                    // present in the list.
        {
            // If it is, move on to the next item in the list.
            it++;
        }
        // Otherwise...
        else
        {
            // We found the right spot!
            found = true;
        }
    }
    // Insert the item at the spot we just discovered.
    this->insert(it, t);
    // Exit the function.
    return;
}


When the sortedInsert function compares "Persons", it reaches my original code I posted and segfaults
at that very line.
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
 
class Person
{
public:
	string givnName;        // The person's given name
	string lastName;        // The person's last name
	string birth;           // The person's date of birth
	int year;               // The person's birth year
	int id;                 // The person's individual inetifier

    // Default constructor for a Person
    Person()
    {
        givnName.clear();
        lastName.clear();
        birth.clear();
        year = -1;
        id = -1;
    }

    // Assignment operator for a Person, copying the data in the
    // right-hand side to the data of the left.
    Person & operator = (const Person & rhs)
    {
        this->givnName = rhs.givnName;
        this->lastName = rhs.lastName;
        this->birth = rhs.birth;
        this->year = rhs.year;
        this->id = rhs.id;
        return *this;
    }

    bool operator > (const Person & rhs) const
    {
        // Set up booleans to determine who has what data. If it is
        // not empty, the bool will be labeled as "true".
        bool gn = !givnName.empty();
        bool rgn = !rhs.givnName.empty();   // <- Segmentation Fault Here
        bool ln = !lastName.empty();
        bool rln = !rhs.lastName.empty();
        bool b = !birth.empty();
        bool rb = !rhs.birth.empty();
    . . .
        // If the left and right don't have last names or the
        // last names are equal, then check given names.
        // If the left has a given name but not the right...
        else if (gn == true && rgn == false)
        {
            // The left is larger.
            return true;
        }
        // If the left is void of a given name, but not the right...
        else if (gn == false && rgn == true)
        {
            // The right is larger.
            return false;
        }
        // If both people have given names, and they are not the same...
        else if (gn == true && rgn == true && tempgn != temprgn)
        {
            // Is the left person's given name greater than the right's
            // given name? If so, the left is larger. Otherwise, the right
            // is larger.
            if (tempgn > temprgn)
                return true;
            else
                return false;
        }
    . . .
}
rodentMinn (10)
Do you think a segmentation fault could come from a null parameter? Like, a bad variable being passed?
icy1 (596)
Possible spots:

- is there a line 68 that looks like "return false;" so if somehow all the mysterious conditionals are bypassed the function still returns something?
- ListIterator<T> it = this->begin(); I'm curious what the very first if (t > *it) will do, particularly the *it part. If the "List" is empty you probably just want to insert it right then and there and be done. As it stands, it might be trying to do null.givnName() or so.


Other notes:
- Would've been better if you provided a working minimum example instead of all the mysterious "...".
- initial std::string is already empty; the constructor could be simplified to Person() : year(-1), id(-1) {}
- why sort based on operator> when the whole world uses operator<?
- the variables should be private, not public
rodentMinn (10)
Hey icy1, I tried doing what you recommended, and I still get a segfault at that same line. There was nothing being returned if all the conditionals were bypassed, so I added a "return true;". Also, I added a check to see if the list is empty, and if it is, it pushes the item to the back.

The overloaded > operator now looks like 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
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
 
    bool operator > (const Person & rhs) const
    {
        // Set up booleans to determine who has what data. If it is
        // not empty, the bool will be labeled as "true".
        bool gn = !givnName.empty();
        bool rgn = !rhs.givnName.empty();   // Still segfaults...
        bool ln = !lastName.empty();
        bool rln = !rhs.lastName.empty();
        bool b = !birth.empty();
        bool rb = !rhs.birth.empty();

        // Convert all names we are handling to have a capital first
        // letter.
        string tempgn;
        string temprgn;
        string templn;
        string temprln;
        if (gn == true)
        {
            tempgn = givnName;
            tempgn = capitalize(tempgn);
        }
        if (rgn == true)
        {
            temprgn = rhs.givnName;
            temprgn = capitalize(temprgn);
        }
        if (ln == true)
        {
            templn = lastName;
            templn = capitalize(templn);
        }
        if (rln == true)
        {
            temprln = rhs.lastName;
            temprln = capitalize(temprln);
        }

        // If the left person has a last name, but not the right...
        if (ln == true && rln == false)
        {
            // The left is larger.
            return true;
        }
        // If the left person does not have a last name, but the right
        // does...
        else if (ln == false && rln == true)
        {
            // The right is larger.
            return false;
        }
        // If both the left person and the right person have last names,
        // and they are not equivalent...
        else if (ln == true && rln == true && templn != temprln)
        {
            // Is the last name greater than the right name? If so,
            // the left is larger. Otherwise, the right is.
            if (templn > temprln)
                return true;
            else
                return false;
        }
        // If the left and right don't have last names or the
        // last names are equal, then check given names.
        // If the left has a given name but not the right...
        else if (gn == true && rgn == false)
        {
            // The left is larger.
            return true;
        }
        // If the left is void of a given name, but not the right...
        else if (gn == false && rgn == true)
        {
            // The right is larger.
            return false;
        }
        // If both people have given names, and they are not the same...
        else if (gn == true && rgn == true && tempgn != temprgn)
        {
            // Is the left person's given name greater than the right's
            // given name? If so, the left is larger. Otherwise, the right
            // is larger.
            if (tempgn > temprgn)
                return true;
            else
                return false;
        }
        // If the left and right don't have given names or the
        // given names are equal, then check dates of birth.
        // If the left has a birth date but not the right...
        else if (b == true && rb == false)
        {
            // The left is larger.
            return true;
        }
        // If the right has a borth date but not the left...
        else if (b == false && rb == true)
        {
            // The right is larger.
            return false;
        }
        // If both the left and right both have borth dates and they
        // are not equal to each other...
        else if (b == true && rb == true && birth != rhs.birth)
        {
            // Check to see if the borth YEAR of the left
            // is greater than than that of the right. If it is,
            // then the left is larger. Otherwise, the right
            // is larger.
            if (year > rhs.year)
                return true;
            else
                return false;
        }
        // At this point, check to see if the left's id is greater than
        // the right's id. If it is...
        else if (id > rhs.id)
        {
            // The left is larger.
            return true;
        }
        // If it's not...
        else
        {
            // The right is larger.
            return false;
        }
        // If all else fails, just claim the larger is the left.
        return true;
    }


I didn't know the string by default is empty, so I simplified my constructor. As for why I overloaded the > operator, it was originally part of an insertion sort that simply didn't work. Instead of recreating new conditions for a < operator, I just kept the > operator.

Thanks for the help so far, but there is still something causing the program to segfault at that very same line. Another thing I remembered that may be of some help is that not every "Person" has a given name, but I didn't think that would mean anything, because the string would simply be empty.

Also, the debugging backtrace for what is being passed to the > operator says:
(this=0x7fffffffdd00, rhs=...)
Last edited on
mbozzi (3910)
While your comparison operator is a mess, it's probably not the problem.

The failure occurs on the first access to the referent of rhs. This suggests that the parameter is a dangling reference.

Post enough code to reproduce the problem.
Last edited on
rodentMinn (10)
Because of the massive size of the code that this goes through, I'll have to make multiple posts.

Person 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
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
 
class Person
{
public:
	string givnName;        // The person's given name
	string lastName;        // The person's last name
	string birth;           // The person's date of birth
	int year;               // The person's birth year
	int id;                 // The person's individual identifier

    // Default constructor for a Person
    Person()
    {
        year = -1;
        id = -1;
    }

    // Assignment operator for a Person, copying the data in the
    // right-hand side to the data of the left.
    Person & operator = (const Person & rhs)
    {
        this->givnName = rhs.givnName;
        this->lastName = rhs.lastName;
        this->birth = rhs.birth;
        this->year = rhs.year;
        this->id = rhs.id;
        return *this;
    }
    bool operator > (const Person & rhs) const
    {
        // Set up booleans to determine who has what data. If it is
        // not empty, the bool will be labeled as "true".
        bool gn = !givnName.empty();
        bool rgn = !rhs.givnName.empty();   // Still segfaults...
        bool ln = !lastName.empty();
        bool rln = !rhs.lastName.empty();
        bool b = !birth.empty();
        bool rb = !rhs.birth.empty();

        // Convert all names we are handling to have a capital first
        // letter.
        string tempgn;
        string temprgn;
        string templn;
        string temprln;
        if (gn == true)
        {
            tempgn = givnName;
            tempgn = capitalize(tempgn);
        }
        if (rgn == true)
        {
            temprgn = rhs.givnName;
            temprgn = capitalize(temprgn);
        }
        if (ln == true)
        {
            templn = lastName;
            templn = capitalize(templn);
        }
        if (rln == true)
        {
            temprln = rhs.lastName;
            temprln = capitalize(temprln);
        }

        // If the left person has a last name, but not the right...
        if (ln == true && rln == false)
        {
            // The left is larger.
            return true;
        }
        // If the left person does not have a last name, but the right
        // does...
        else if (ln == false && rln == true)
        {
            // The right is larger.
            return false;
        }
        // If both the left person and the right person have last names,
        // and they are not equivalent...
        else if (ln == true && rln == true && templn != temprln)
        {
            // Is the last name greater than the right name? If so,
            // the left is larger. Otherwise, the right is.
            if (templn > temprln)
                return true;
            else
                return false;
        }
        // If the left and right don't have last names or the
        // last names are equal, then check given names.
        // If the left has a given name but not the right...
        else if (gn == true && rgn == false)
        {
            // The left is larger.
            return true;
        }
        // If the left is void of a given name, but not the right...
        else if (gn == false && rgn == true)
        {
            // The right is larger.
            return false;
        }
        // If both people have given names, and they are not the same...
        else if (gn == true && rgn == true && tempgn != temprgn)
        {
            // Is the left person's given name greater than the right's
            // given name? If so, the left is larger. Otherwise, the right
            // is larger.
            if (tempgn > temprgn)
                return true;
            else
                return false;
        }
        // If the left and right don't have given names or the
        // given names are equal, then check dates of birth.
        // If the left has a birth date but not the right...
        else if (b == true && rb == false)
        {
            // The left is larger.
            return true;
        }
        // If the right has a borth date but not the left...
        else if (b == false && rb == true)
        {
            // The right is larger.
            return false;
        }
        // If both the left and right both have borth dates and they
        // are not equal to each other...
        else if (b == true && rb == true && birth != rhs.birth)
        {
            // Check to see if the borth YEAR of the left
            // is greater than than that of the right. If it is,
            // then the left is larger. Otherwise, the right
            // is larger.
            if (year > rhs.year)
                return true;
            else
                return false;
        }
        // At this point, check to see if the left's id is greater than
        // the right's id. If it is...
        else if (id > rhs.id)
        {
            // The left is larger.
            return true;
        }
        // If it's not...
        else
        {
            // The right is larger.
            return false;
        }
        // If all else fails, just claim the larger is the left.
        return true;
    }

    // Reset the Person to defaults.
    void clear()
    {
        givnName.clear();
        lastName.clear();
        birth.clear();
        year = -1;
        id = -1;
    }
}
dhayden (5795)
Also, the debugging backtrace for what is being passed to the > operator says:
(this=0x7fffffffdd00, rhs=...)

As I said before, it's likely that you're passing garbage for rhs. What is the value of rhs here?

Please post the entire List class.

You're making the comparison much more complicated than necessary:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
    bool operator > (const Person & rhs) const
    {
        int cmp;

        // Empty strings are less than non-empty strings.
        cmp = capitalize(LastName).compare(capitalize(rhs.LastName));
        if (cmp < 0) return false;
        if (cmp > 0) return true;

        // Last names are equal. Try given names
        cmp = capitalize(GivenName).compare(capitalize(rhs.GivenName));
        if (cmp < 0) return false;
        if (cmp > 0) return true;

        // Given names are equal. Try year
        return (year > rhs.year);
    }

rodentMinn (10)
My list class is huge, and can't fit in one post. Here it is nonetheless.
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
177
 
#include <cassert>

// forward declaration for List
template <class T>
class List;

// forward declaration for ListIterator
template <class T>
class ListIterator;

/***********************************************
 * NODE
 * A component of a daisy chain method of
 * storing data, known as a linked-list.
 * I just like the sound of a daisy chain
 * better.
 **********************************************/
template <class T>
class Node
{
public:
	T data;   // Data in each node
	Node<T>* pNext;	  // Pointer to next node
	Node<T>* pPrev;   // Pointer to previous node

	Node() { pNext = NULL; pPrev = NULL; }   // Create a new node
	Node(T item) { data = item; }   // Node with data initialized to item
	Node(T item, Node<T>* next, Node<T>* prev);   // Initialize item and next pointer
};

/************************************************
 * LIST
 * A class that holds stuff
 ***********************************************/
template <class T>
class List
{
public:
	// Default constructor
	List() { numItems = 0; head = tail = NULL; }

	// Copy constructor
    List(const List & rhs);

	// Clear list
	void clear();

	// Destructor
	~List() { clear(); }

	// Assignemnt operator
    List <T> & operator = (const List & rhs);

	// Empty list check
	bool empty() const { return numItems == 0; }

	// Size of list
	int size() const { return numItems; }

	// Push item to back of list
    void push_back(const T & t) throw (const char *);

	// Push item to front of list
	void push_front(const T & t) throw (const char *);

	// Reveal front item
	T & front() { return head->data; }

	// Reveal back item
	T & back() { return tail->data; }

	// Insert item anywhere
	ListIterator <T> insert(ListIterator <T> ptr, const T & t) throw (const char *);

	// Insert item into sorted space
	void sortedInsert(const T & t) throw (const char *);

	// Remove item
	void remove(ListIterator <T> ptr) throw (const char *);

	// Set iterator to beginning
	ListIterator <T> begin() const { return ListIterator<T>(head); }

	// Set iterator to ending
    ListIterator <T> rbegin() const { return ListIterator<T>(tail); }

	// Set iterator to past-the-end
    ListIterator <T> end() const { return ListIterator<T>(NULL); }

	// Set iterator to before-the-beginning
    ListIterator <T> rend() const { return ListIterator<T>(NULL); }

private:
	Node <T> * head;					// The head of the list.
	Node <T> * tail;					// The tail of the list.
	int numItems;						// The number of items in the list.
};

/**************************************************
 * LIST ITERATOR
 * An iterator through List
 *************************************************/
template <class T>
class ListIterator
{
  public:
   // default constructor
  ListIterator() : p(NULL) {}

   // initialize to direct p to some item
  ListIterator(Node<T> * p) : p(p) {}


   // assignment operator
   ListIterator <T> & operator = (const ListIterator & rhs)
   {
      this->p = rhs.p;
      return *this;
   }

   // not equals operator
   bool operator != (const ListIterator & rhs) const
   {
      return rhs.p != this->p;
   }

	// equals operator
   bool operator == (const ListIterator & rhs) const
   {
      return rhs.p == this->p;
   }

   // dereference operator
   T & operator * ()
   {
      return p->data;
   }

   // prefix increment
   ListIterator <T> & operator ++ ()
   {
      p = p->pNext;
      return *this;
   }

   // postfix increment
   ListIterator <T> operator++(int postfix)
   {
      ListIterator tmp(*this);
      p = p->pNext;
      return tmp;
   }

   // prefix decrement
   ListIterator <T> & operator -- ()
   {
      p = p->pPrev;;
      return *this;
   }

   // postfix decrement
   ListIterator <T> operator--(int postfix)
   {
      ListIterator tmp(*this);
      p = p->pPrev;
      return tmp;
   }

  private:
   Node<T> * p;

	// These functions in the List class are friends of the ListIterator,
	// because we need access to private node "p" in order to insert and
	// remove anywhere in the function.
	friend ListIterator <T> List <T> :: insert(ListIterator <T> ptr, const T & t) throw (const char *);
	friend void List <T> :: remove(ListIterator <T> ptr) throw (const char *);
};
Last edited on
rodentMinn (10)
The functions for my list 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
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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
 
/*******************************************
 * LIST :: COPY CONSTRUCTOR
 *******************************************/
template <class T>
List <T> :: List(const List <T> & rhs)
{
	// Get an empty list
   numItems = 0;
   head = tail = NULL;
	// Traverse through the list
	for (ListIterator<T> temp = rhs.begin(); temp != rhs.end(); temp++)
	{
		this->push_back(*temp);
	}
}

/*******************************************
 * LIST :: CLEAR
 * Releases the allocated memory for the
 * linked-list. This is also the destructor.
 *******************************************/
template <class T>
void List <T> :: clear()
{
	// Get a new node.
	Node<T> * temp;
	// Set it as the head.
	temp = head;
	// So long as the head isn't null...
	while (head != NULL)
	{
		// Move to the next item in the list.
		temp = temp->pNext;
		// Kill the old head.
		delete head;
		// Set the head as the new node again.
		head = temp;
	}
	// Once all is said and done, reset the numItems to 0.
	numItems = 0;
	// Nullify the head and tail.
	head = tail = NULL;
}

/*******************************************
 * LIST :: ASSIGNMENT OPERATOR
 * Assigns the contents of one list to
 * another, thereby functioning like a copy
 * constructor in essance.
 *******************************************/
template <class T>
List <T> & List <T> :: operator = (const List & rhs)
{
	// Kill the left-hand side.
	clear();
	// Get a new list.
    numItems = 0;
    head = tail = NULL;
	// Traverse the list and copy over the data.
	for (ListIterator<T> temp = rhs.begin(); temp != rhs.end(); temp++)
	{
		this->push_back(*temp);
	}
    return *this;
}

/*******************************************
 * LIST :: PUSH_BACK
 * Adds an item to the back of the list.
 *******************************************/
template <class T>
void List <T> :: push_back(const T & t) throw (const char *)
{
	try
	{
		// Make a new node.
		Node <T> *a = new Node <T> (t);
		if (head != NULL)
		{
         assert(head != NULL);
			// If the head exists, set the tail as the new node.
			tail->pNext = a;
			a->pPrev = tail;
			tail = a;
		}
		// Otherwise, make the new node the member of a new list.
		else
		{
			head = a;
			tail = a;
		}
	}
	catch (std::bad_alloc)
	{
		throw "ERROR: Unable to allocate new node for list\n";
	}
	tail->pNext = NULL;
	// Keep track of the number of items, as usual.
	numItems++;
}

/********************************************
 * LIST :: PUSH_FRONT
 * Adds an item to the front of the list.
 ********************************************/
template <class T>
void List <T> :: push_front(const T & t) throw (const char *)
{
	try
	{
		// Like the push_back, only this time, if there exists a
		// head, make the head the new node.
		Node <T> *a = new Node <T> (t);
		if (head != NULL)
		{
         assert(head != NULL);
			head->pPrev = a;
			a->pNext = head;
			head = a;
		}
		// Once again, make a new list with the new node the only
		// member if there is no head to begin with.
		else
		{
			head = a;
			tail = a;
		}
	}
	catch (std::bad_alloc)
	{
		throw "ERROR: Enable to allocate new node for list\n";
	}
	head->pPrev = NULL;
	// Make note of another item being added to the list.
	numItems++;
}

/********************************************
 * LIST :: INSERT
 * Adds an item to any spot in the list.
 ********************************************/
template <class T>
ListIterator <T> List <T> :: insert(ListIterator <T> ptr, const T & t) throw (const char *)
{
	try
	{
		Node<T> * temp  =  new Node<T>(t);	// Make a new node
		if (!head)							// insert into an empty list
		{
			head = temp;
			tail = temp;
		}
		else if (ptr == end())     			// insert at end of list
		{
			tail->pNext = temp;
			temp->pPrev = tail;
			tail = temp;
		}
		else
		{
			temp->pNext = ptr.p;			// insert at beginning or middle
			temp->pPrev = ptr.p->pPrev;
			ptr.p->pPrev = temp;
			if (ptr == begin())
				head = temp;				// insert at beginning
			else
				temp->pPrev->pNext = temp;	// insert in middle
		}
		numItems++;							// Incrememnt number of items
		return ListIterator<T>(temp);		// Get out of the function
	}
	catch (std::bad_alloc)
	{
		throw "ERROR: unable to allocate a new node for a list";
	}
}

/********************************************
 * LIST :: SORTEDINSERT
 * Inserts an item into the list where it
 * makes the list sorted.
 ********************************************/
template <class T>
void List <T> :: sortedInsert(const T & t) throw (const char *)
{
    // Set an iterator to the beginning of the list.
    ListIterator<T> it = this->begin();
    // If the list is empty, push the item onto the list.
    if (this->empty() || it == NULL)
    {
        this->push_back(t);
    }
    else
    {
        // Set up a boolean to determine whether we found the right
        // spot or not.
        bool found = false;
        // Now then, until we either ran to the end of the list or
        // we find the right spot to insert at...
        while (found == false && it != this->end())
        {
            // Is this item greater to what we are pointing to in
            // the list?
            if (t > *it)
            {
                // If it is, move on to the next item in the list.
                it++;
            }
            // Otherwise...
            else
            {
                // We found the right spot!
                found = true;
            }
        }
        // Insert the item at the spot we just discovered.
        this->insert(it, t);
    }
    // Exit the function.
    return;
}

/********************************************
 * LIST :: REMOVE
 * Removes an item from any spot in the list.
 ********************************************/
template <class T>
void List <T> :: remove(ListIterator <T> ptr) throw (const char *)
{
   try
   {
		// Make sure the function is not empty.
      if (ptr == end()) { throw 'e'; }
		else
		{
			if (ptr.p->pPrev != NULL)     			// If the previous pointer exists...
			{
				ptr.p->pPrev->pNext = ptr.p->pNext;	// set the previous pointer to the
                                                    // next pointer.
			}
			else if (ptr.p == head)
			{
				head = ptr.p->pNext;				// Otherwise, make the head the head's
                                                    // next.
			}
			if (ptr.p->pNext != NULL)				// If the next pointer exists...
			{
				ptr.p->pNext->pPrev = ptr.p->pPrev;	// Set the next pointer to the
                                                    // previous pointer.
			}
			else if (ptr.p == tail)
			{
				tail = ptr.p->pPrev;				// Otherwise, make the tail the tail's
                                                    // previous.
			}
			delete ptr.p;
		}
		numItems--;									// Decrement the number of items.
   }
   catch (char)
   {
      throw "ERROR: unable to remove from an invalid location in a list";
   }
}
dhayden (5795)
Node(T item) { data = item; } // Node with data initialized to item
This leads pPrev and pNext uninitialized. Without fixing it, the program below crashes. After fixing it, the program works:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
using std::cout;

int main()
{
    List<int> L;
    ListIterator<int> iter;
    L.sortedInsert(5);
    L.sortedInsert(7);
    L.sortedInsert(4);
    L.sortedInsert(6);

    for (iter = L.begin(); iter != L.end(); ++iter) {
        cout << *iter << ' ';
    }
    cout << '\n';
}
icy1 (596)
I was just about to say that it's something wrong with Node's previous and next not being correct. I put what I believe is a full "min working example" on repl.it (something OP shouldve done). Tweaked a few things here and there (another Person constructor, replaced NULL with nullptr, made postfix depend on prefix, comparison operators with some debugging ), but it was nearly compiling as presented.

https://repl.it/@icy_1/FearfulMadVoxels

The iterator doesn't make it particularly easy to work with the contents, since there's no pointer math (e.g. it+1 for the next element). But still you can see that after the default sorting of the people, the pointers jump twice or so

1
2
3
4
5
6
7
8
9
10
11
12
13
 
    List<Person> ppl;
    ppl.sortedInsert({"Lauren", "Schwartz", "2/4/1987", 1987, 100000});
    ppl.sortedInsert({"Lauren", "Jones", "2/4/1987", 1987, 200000});
    ppl.sortedInsert({"Lauren", "Schwartz", "2/4/1987", 1987, 300000});
    ppl.sortedInsert({"Lauren", "Jones", "2/4/1987", 1987, 400000});
    Show(ppl);

    cout << "\n--------\n\n";
    cout << boolalpha;
    auto it = ppl.begin();    
    cout << ((*it) == (*++it)) << '\n' << '\n';
    cout << ((*it) == (*++it)) << '\n' << '\n';
    cout << ((*it) == (*++it)) << '\n' << '\n';


is giving the following output (debug output from operator==). It fails to compare element #1 with element #2, skipping past it:
[Jones, Lauren 2/4/1987   1987  400000] [Jones, Lauren 2/4/1987   1987  200000] [Schwartz, Lauren 2/4/1987   1987  300000] [Schwartz, Lauren 2/4/1987   1987  100000] 

--------

last: Jones  first: Lauren
rhs.last: Jones  rhs.first: Lauren
true

last: Schwartz  first: Lauren
rhs.last: Schwartz  rhs.first: Lauren
true

last: Schwartz  first: Lauren
rhs.last: Schwartz  rhs.first: Lauren
true
rodentMinn (10)
dhayden, that was it! In the Node(T item) function, I initialized the pNext and pPrev variables as NULL and now the program works!

1
2
3
4
5
6
7
8
9
10
11
12
 
template <class T>
class Node
{
public:
	T data;   // Data in each node
	Node<T>* pNext;   // Pointer to next node
	Node<T>* pPrev;   // Pointer to previous node

	Node() { pNext = NULL; pPrev = NULL; }   // Create a new node
	Node(T item) { data = item; pNext = NULL; pPrev = NULL; }   // Node with data initialized to item
	Node(T item, Node<T>* next, Node<T>* prev);   // Initialize item and next pointer
};


Thanks to Thomas1965, dhayden, icy1, and mbozzi for all the help. It means a lot.

Also, I'm sorry I didn't provide a minimum working example. Two reasons I didn't do it was because I was a little skeptical about releasing the list class, as it was part of a school assignment (actually, this whole project is a school assignment that I mentioned in the original post I submitted anyway) and I was paranoid that the school would yell at me for releasing it, but I released it anyway because I wanted to know why this code worked on one computer and not the other, and also because it's my list class, I can do whatever I want with it. The other reason was because this whole program is huge, and it was going to take me a long time to do that. Even the one icy1 made looked super large, in addition to not working anyway because it has "auto" and "nullptr" in it, which don't work in C++98...

Again, thanks for all the help. If this whole topic disappears, you'll know why.
Last edited on
dhayden (5795)
Sometimes when people have been reluctant to post code they can find someone who will look at it offline. I know I've done this a few times. So if you're in that situation again, just say that you're rather not release the code and can you send it privately.
Topic archived. No new replies allowed.