[C++] Why is this turning into 0? And why a segmentation fault on

[Jamin2112]

the other interpreter I'm using?

I'm practicing my coding chops for an upcoming interview (I don't really have to use any hardcore programming chops I work as a web dev) and have been writing small C++ programs on online compilers/interpreters because I hate having to make entire new projects on my desktop's IDE. These online compilers/interpreters often give different results, making it hard to debug.

Example code piece:

#include <iostream>

template <typename T> class SinglyLinkedList
{

  struct node
  {
  T val;
  node * next;
  };

  public:
    SinglyLinkedList ();
    SinglyLinkedList (T *, size_t);
    ~SinglyLinkedList ();
    void push_back (T);
    void print ();
    void remove_val (T);

  private:
    node * _root;

};int main ()
{
   int myArray [] = { 1, 69, -23942, 11111 };
   SinglyLinkedList<int> myList(myArray, sizeof(myArray)/sizeof(int));
   myList.print();
   return 0;
}

template <typename T> SinglyLinkedList<T>::SinglyLinkedList ( )
{
   _root = NULL;
}

template <typename T> SinglyLinkedList<T>::SinglyLinkedList (T * arr, size_t n)
{
    /* Initialize a singly-linked list of objects of type T from an array of objects of type T */
   if (n > 0)
  { 
       node * lastNode = new node;
       lastNode->val = *arr;
       lastNode->next = NULL;
      _root = lastNode;
     for (T * pa(arr+1), * pb(arr+n); pa != pb; ++pa)
     {
        node * thisNode = new node;
        thisNode->val = *pa;
        thisNode->next = NULL;
        lastNode->next = thisNode;
        lastNode = thisNode;
     }
     delete lastNode;
   }
  else
   {
     _root = NULL;
   }
}

template <typename T> SinglyLinkedList<T>::~SinglyLinkedList ( )
{
     node * thisNode = _root;
    while (thisNode != NULL)
    {
        node * temp = thisNode;
        thisNode = thisNode->next;
       delete temp;
    }
}

template <typename T> void SinglyLinkedList<T>::push_back ( T val )
{
    node * newNode = new node;
    if (_root == NULL)
    {
      // ...
    }
    node * endNode;
}

template <typename T> void SinglyLinkedList<T>::print ( )
{
     if (_root == NULL) return;
     for (node * thisNode = _root; thisNode != NULL; thisNode = thisNode->next)
     {
          std::cout << thisNode->val << "->";
     }
     std::cout << "NULL";
}

template <typename T> void SinglyLinkedList<T>::remove_val ( T val )
{

// ...

}

On http://cpp.sh/ is printed

1->69->-23942->0->NULL

and on

http://codepad.org/ is printed

Segmentation fault

Can someone help me figure out what the problem is?

 

[Jamin2112]

By the way, I was referring to the 11111 turning into a zero

 

[Mark44]

What I would do is use a debugger and find out why the node with 11111 is being ignored and where you're getting the seg fault. I suspect that you have some kind of OBOE (off by one error) as a result of the way your for loop works in the SinglyLinkedList constructor, the one that takes an array arg and a size arg. For the seg fault, you might be trying to store a value in memory that your program doesn't own. I could be off in my analysis here, but those are the things I would look at.

 

[Jamin2112]

Got it compiling (http://codepad.org/RIh8Nx4M), except now the value -16121856 is coming out of left field. What's going on?

Mod note: Removed questionable acronym.

 

[Mark44]

Got it compiling (http://codepad.org/RIh8Nx4M), except now the value -16121856 is coming out of left field. What's going on?

That looks like a garbage value (uninitialized memory) to me. Trace through the for loop in your code to see where the code is tucking the numbers in your array. After that satisfy yourself that each node has been created correctly, with a proper numeric value and next pointer. Your array is very small so it shouldn't be too hard to check each of the pointer fields to see that it is pointing to a node that your code created.

Your print method looks pretty straightforward -- I don't think the problem is there. I would bet that something screwy is happening in your list constructor.

 

[jedishrfu]

While I don't see exactly where your error is, a segmentation fault means you have tried to access memory outside of your allotted memory. The fact that on one machine you get an uninitialized value and on another you get a seg fault could just be the same problem.

I once had an OS/2 C++ program that seg faulted when I attempted to add a 13th character to a 12 character buffer but worked fine when the buffer was smaller than 12. The reason was program memory was allocated in blocks of 16 bytes with the first four bytes holding the size of the buffer.

 

[Svein]

In your list constructor you say " _root = lastNode" and then you go on manipulating lastNode. When you are finished you say "delete lastNode". Now _root contains a "dangling pointer", it does not point to anything valid.

 

[D H]

What's going on?

What's going on is that you aren't doing two things I asked you to do long ago: Learn to execute your code by hand, and learn to use a debugger.

In terms of your code, your constructor logic is wrong (you are adding a bogus element to the list) and your remove logic is very wrong. And just because it's a singly-linked list doesn't mean you can't keep track of the tail. Keeping track of the tail makes push_back much easier implement (and faster to execute, but that's a side benefit).

Constructor bugs
The primary problem with your constructor is your use of pointer arithmetic. Before you touch arr, the end of the array (a pointer to one element past the last element in the array) is at arr+n. But you touched it; in particular you used ++arr. That means the end of the array is at arr+n-1. Your code has an off-by-one error.

The easiest way to avoid this is not to use pointer arithmetic. If you don't care about efficiency (and in general, you shouldn't), the easiest way to implement your non-default constructor is to use the push_back member function:

/**
* Initialize a singly-linked list of objects of type T
* from an array of objects of type T
*/
template <typename T>
inline SinglyLinkedList<T>::SinglyLinkedList (T * arr, size_t n)
{
   _root = _tail = NULL;
   for (int ii = 0; ii < n; ++ii)
   {
      this->push_back (arr[ii]);
   }
}

Some comments on the above:

• Note how simple it is. No special cases, no pointer arithmetic. You could come back in six months after having worked on some completely different tasks and understand the logic.
• Note the use of the word "inline". Declaring template function members out-of-line and failing to use the inline keyword will get you in trouble with the One Definition Rule. As a general rule, it's best to qualify your out-of-line template member function definitions as inline. Even easier, just define your template class Java-style, where one is forced to define all member functions inside the class definition.
  
• Finally, what's that _root = _tail = NULL; nonsense? In particular, what is "_tail? I assumed a new data member named "_tail" (in keeping with your naming convention) that keeps track of the tail of your singly-linked list. Just because it's a singly-linked list doesn't mean you can't keep track of the tail. However, I've railed, many times, against speculative generality and premature optimization. It looks like I'm being a hypocrite! I'm not. You are specifically trying to implement a push_back member function. That's problematic with a list where you only know the head. If you don't keep track of the tail, you have to walk through the list from head to tail to find the tail. Since push_back is a very common operation on lists (and indeed, you are asked to implement push_back), it makes a lot of sense to keep track of the tail. What is and what is not speculative generality takes some judgement.

Remove bugs
Your remove_val member function is buggy. You testing isn't invoking all of the bugs in that function. Some additional tests that will invoke that bugginess you didn't invoke:

• Make the last element in the list have a value that is equal to the one you want removed.
• Make the last two elements in the list both have a value that is equal to the one you want removed.

An easy way to implement this remove function is to rebuild the list. It will help to implement a private push_back member function. In the class definition, add the declaration void push_back (node* new_node); and make sure this is private. The implementation is simple:

/**
* Add the node to the end of the list.
*/
template <typename T>
inline SinglyLinkedList<T>::push_back (node* new_node)
{
   new_node->next = NULL;
   _tail = new_node;
   if (_root == NULL)
   {
      _root = _new_node;
   }
}

And now the public push_back member function is also very simple:

/**
* Add the value as a new node at the end of the list.
*/
template <typename T>
inline SinglyLinkedList<T>::push_back (const T& val)
{
   node*<T> new_node = new node<T>;
   new_node->val = val;
   this->push_back (new_node);
}

Finally, how to implement remove_val? This too is simple given the above. Simply rebuild the list:

/**
* Remove all instances of val from the list.
*/
template <typename T>
inline SinglyLinkedList<T>::remove_val (const T& val)
{
   node<T>* curr = _root;
   _root = _tail = NULL;
   while (curr != NULL)
   {
      node* next = curr->next;
      if (curr->val == val)
      {
         delete curr;
      }
      else
      {
         this->push_back (curr);
      }
      curr = next;
   }
}

Here is how I would have written this code. Some preliminary comments:

• I don't use underscore as a prefix (this can get you in trouble) or even as a suffix (pure personal preference; I think its ugly, so I don't do it).
• Consistency is the hobgoblin of small minds. Given the type name SinglyLinkedList, the type name of the elements of a list should be Node rather than node.
  Note well: A number of groups have come to the conclusion that StudLyCapsTypeNames is a very bad but very widely used coding practice. I'm trying to wean myself from that practice. ItsNotWorkingVeryWell.
• Templates in C++ can be be goofy. I've found that it's best to always use this->foo in C++ templates. Do this and you won't get bit. Don't do this and you will get bit when you least expect it.
• Doxygen is the de facto standard for documenting C++ code. Get in the habit of writing doxygen comments.

// Do not rely on the fact that iostream includes cstddef.
// The code below uses NULL, so #include the header that defines it.
#include <cstddef>
#include <iostream>

/**
* A singly-linked list that keeps track of the head and tail of the list.
*/
template <typename T> class SinglyLinkedList
{

// Public stuff always comes first, except when it can't.
// In this case, it can't. We need a forward declaration, at minimum.

private:
   struct Node;

public:

   /**
    * Default constructor.
    */
   SinglyLinkedList ()
   {
      this->head = this->tail = NULL;
   }

   /**
    * Non-default constructor.
    * @param arr Array whose contents will form the list.
    * @param n   Number of elements in the array.
    */
   SinglyLinkedList (
      T* arr,
      std::size_t n)
   {
      this->head = this->tail = NULL;
      for (std::size_t ii = 0; ii < n; ++ii)
      {
         this->push_back (arr[ii]);
      }
   }

   /**
    * Destructor.
    */
   ~SinglyLinkedList ()
   {
      Node* curr = this->head;
      while (curr != NULL)
      {
         Node* next = curr->next;
         delete curr;
         curr = next;
      }
   }

   // Implementations left to the reader.
   // Do **not** forget these.
   // Note well: In C++11, the rule of three becomes the rule of five.
   SinglyLinkedList (const SinglyLinkedList<T>& src);
   SinglyLinkedList& operator=(const SinglyLinkedList<T>& src);

   /**
    * Add the value as a new node at the end of the list.
    * @param val Value to be added.
    */
   Node* push_back (const T& val)
   {
      return this->push_back (new Node(val));
   }

   /**
    * Remove all occurrences of val from the list.
    * @param val Value to be removed.
    */
   void remove_val (const T& val)
   {
      Node* curr = this->head;
      this->head = this->tail = NULL;
      while (curr != NULL)
      {
         Node* next = curr->next;
         if (curr->val == val)
         {
            delete curr;
         }
         else
         {
            this->push_back (curr);
         }
         curr = next;
      }
   }

   /**
    * Print the list to std::cout.
    */
   void print ()
   {
      for (Node* curr = this->head; curr != NULL; curr = curr->next)
      {
         std::cout << curr->val << " --> ";
      }
      std::cout << "NULL\n";
   }

private:

   /**
    * Represents an element in the list.
    */
   struct Node
   {
      T val;
      Node * next;
      Node(const T& value)
      {
         val = value;
         next = NULL;
      }
   };

   /**
    * The head of the list.
    */
   Node* head;

   /**
    * The tail of the list.
    */
   Node* tail;

   /**
    * Add the already-created node to the end of the list.
    * @param node Node to be added.
    */
   Node* push_back (Node* node)
   {
      node->next = NULL;
      if (this->head == NULL)
      {
         this->head = this->tail = node;
      }
      else
      {
         this->tail->next = node;
         this->tail = node;
      }
      return node;
   }
};/**
* A simple driver that does not test all functionality.
*/
int main ()
{
   int my_array [] = { 1, 69, -23942, 69, 56, 67 };
   SinglyLinkedList<int> myList(my_array, sizeof(my_array)/sizeof(int));
   std::cout << "Constructed list:\n";
   myList.print();

   std::cout << "push_back(33)\n";
   myList.push_back(33);
   myList.print();

   std::cout << "remove_val(69)\n";
   myList.remove_val(69);
   myList.print();
   return 0;
}

 

[Jamin2112]

Wow! Thanks, DH.