Segmentation fault error thrown with certain compilers for linked list implementation

Question

I'm getting segmentation fault error with the follow main function. The header file has a linked list implementation with an iterator class and different testing members.

The thing is that the segmentation fault error shows up on a certain compilers and goes away on other. I tried using GDB to debug for any errors, but the program executes fine.

This is really bugging me as I cannot find the reason this would throw a segmentation fault error.

Any help is greatly appreciated.

EDIT: I noticed that with this updated main, the logic is flawed and does not insert the node at the specified location. So, I'll have to do some more debugging to figure out the issue.

It seems the else if block inside insert() is executed instead of the else block.

Main.cpp

#include <iostream>
#include "List.h"
int main(){
 List<double> l;
 l.push_back(1.1);
 l.push_back(2.2);
 l.insert(l.begin()++, 3.3);
 l.printList();
}

List.h

#include <cstdint>
#include <iostream>
#include <memory>
template<typename T>
class List
{
public:
 class Node {
 public:
 Node(T value) : value_(value) {}
 Node(T value, Node* prev, Node* next) : value_(value), prev_(prev), next_(next) {}
 T value_;
 Node* next_;
 Node* prev_;
 };
 Node* head_;
 Node* tail_;
 //! An iterator over the list
 class iterator
 {
 public:
 Node* iNode;
 iterator(Node* head): iNode(head){ }
 ~iterator() {}
 T& operator*() {
 return iNode -> value_;
 }
 
 iterator& operator++() {
 iNode = iNode->next_;
 return *this;
 }
 iterator operator++(int ignored) {
 iNode = iNode->next_;
 return *this;
 }
 iterator& operator--() {
 iNode = iNode->prev_;
 return *this;
 }
 //! Is this iterator pointing at the same place as another one?
 bool operator== (const iterator& it) const {
 return this->iNode == it.iNode;
 }
 //! Is this iterator pointing at a different place from another?
 bool operator!= (const iterator& it) const {
 return this->iNode != it.iNode;
 }
 };
 //! Default constructor
 List() :tail_(nullptr) {}
 void push_back_node(T value)
 {
 Node* newnode = new Node(value, tail_, nullptr); //make and link new tail node
 if (tail_)
 {
 tail_->next_ = newnode; // link in new node
 }
 else
 {
 head_ = newnode;
 }
 tail_ = newnode; // update tail
 }
 //! Copy constructor
 List(const List& lst) : head_(nullptr), tail_(nullptr)
 {
 Node* cur = lst.head_; //get first source item.
 while (cur) // if there is a source item to copy
 {
 push_back_node(cur->value_); // stick the item on the end of this list
 cur = cur->next_; // get next source item
 }
 }
 void clear()
 {
 while (head_)
 {
 delete std::exchange(head_, head_->next_);
 }
 tail_ = head_;
 }
 //! Copy assignment operator
 List& operator= (const List& list_copy) {
 List tmp(list_copy);
 clear();
 std::swap(*this, tmp);
 return *this;
 }
 
 //! Move constructor
 List(List&& move) {
 head_ = std::move(move.head_);
 tail_ = std::move(move.tail_);
 }
 ////! Move assignment operator
 List& operator= (List&& list) { 
 head_ = std::move(list.head_);
 tail_ = std::move(list.tail_);
 return *this;
 }
 //! Destructor
 ~List() {}
 //
 // Accessors:
 //
 //! How many elements are in this list?
 size_t size() const {
 size_t size = 0;
 auto temp = head_;
 while (temp != nullptr)
 {
 size++;
 temp = temp->next_;
 }
 return size;
 }
 //! Is this list empty?
 bool empty() const {
 return tail_ == nullptr && head_ == nullptr;
 }
 //! Get an iterator to the beginning of the list
 iterator begin() {
 return List<T>::iterator(head_);
 }
 //! Get an iterator just past the end of the list
 iterator end() {
 return List<T>::iterator(tail_);
 }
 //
 // Mutators:
 //
 //! Copy an element to the front of the list
 void push_front(const T& value) {
 
 Node* node = new Node(value);
 if (head_ == nullptr) {
 head_ = node;
 }
 else {
 node->next_ = head_;
 head_ = node;
 }
 }
 //! Move an element to the front of the list
 void push_front(T&& value) {
 Node* node = new Node(value);
 if (head_ == nullptr) {
 head_ = node;
 }
 else {
 node->next_ = head_;
 head_ = node;
 }
 }
 //! Copy an element to the back of the list
 void push_back(const T& value) {
 Node* node = new Node(value);
 if (tail_) {
 tail_->next_ = node;
 tail_ = tail_->next_;
 }
 else {
 head_ = node;
 tail_ = head_;
 }
 }
 //! Add an element to the back of the list
 void push_back(T&& value) {
 Node* node = new Node(value);
 if (tail_) {
 tail_->next_ = node;
 tail_ = tail_->next_;
 }
 else {
 head_ = node;
 tail_ = head_;
 }
 }
 iterator insert(iterator position, const T& value) {
 Node* newNode = new Node(value);
 if (position == List<T>::iterator(head_)) {
 newNode->next_ = head_;
 head_ = newNode;
 }
 else if (!position.iNode->next_) {
 position.iNode->next_ = newNode;
 }
 else {
 Node* curr = head_;
 while (curr->next_ != position.iNode)
 {
 curr = curr->next_;
 }
 newNode->next_ = curr->next_;
 curr->next_ = newNode;
 }
 return position;
 }
 void printList() const{
 auto node = head_;
 while (node != nullptr)
 {
 std::cout << node -> value_ << " ";
 node = node->next_;
 }
 }
 iterator insert(iterator position, T&& value){
 
 Node* newNode = new Node(value);
 if (position == List<T>::iterator(head_)) {
 newNode->next_ = head_;
 head_ = newNode;
 }
 else if (!position.iNode->next_) {
 position.iNode->next_ = newNode;
 }
 else {
 Node* curr = head_;
 while (curr->next_ != position.iNode)
 {
 curr = curr->next_;
 }
 newNode->next_ = curr->next_;
 curr->next_ = newNode;
 }
 
 return position;
 }
 //! Remove an element from an arbitrary location
 void erase(iterator it) {
 
 Node* temp = it.iNode->next_;
 // Copy data of the next node to current node 
 it.iNode->value_ = it.iNode->next_->value_;
 // Perform conventional deletion 
 it.iNode->next_ = it.iNode->next_->next_;
 free(temp);
 }
};

• PaulMcKenzie: free(temp); -- Undefined behavior. Do not use free with memory allocated with new. Why would you reach for a C deallocation function, knowing that you are writing C++ code?
• SegFaulter: I changed that to delete temp. Thanks for pointing it out.
• PaulMcKenzie: bool operator != (const iterator& it) const -- Prefer writing it in terms of the existing operator ==. i.e. return !(iNode == it.iNode);
• user4581301: Side note: When you get bugs with some compilers, you probably have bugs with all compilers. The bug is visible in some compilers and you're getting unlucky in the other compilers. Crashes are your friend. They tell you that without a doubt you have a bug. Code that fails silently... that's the stuff you have to fear.

Answer 1

Node(T value) : value_(value) {}

does not point prev_ or next_ anywhere useful, so

Node* node = new Node(value);

produces a node that is a timebomb unless you later set its prev_ and next_ members to point somewhere safe. push_back doesn't do this.

Solution:

Use the

Node(T value, Node* prev, Node* next) : value_(value), prev_(prev), next_(next) {}

instead:

Node* node = new Node(value, nullptr, nullptr);

You will find a similar defects in all of the variants of push_back, push_front, and insert. You can also use the Node(T value, Node* prev, Node* next) constructor to simplify some of the work adding, pushing and inserting nodes by using the surrounding nodes in place of the nullptrs

• SegFaulter: Thanks, that made the segmentation fault errors go away. I couldn't even debug since it wasn't even show up and the terminal didn't really crash.
• SegFaulter: I just need to fix the logic of some members like the iterator class since it doesn't seem to reach the end of the list when iterating.
• user4581301: What I would do to debug this: Step over the first call to push_back. Display the contents of l. Display head_ and make sure prev_ and next_ are legitimate values. If they are and not null, display next_ and make sure prev_ and next_ are good. Keep displaying next_ until I get to the end and make sure the last _next is null.
• SegFaulter: Quick question, I realized that my iterator::end() method is wrong since I'm returning an iterator at tail_ but that's wrong since you need to return the iterator one position after the last node right?
• user4581301: That would work, but return List<T>::iterator(nullptr) would do the same thing. Note that would make rend indistinguishable from end. Might be worth digging up the code for std::list and taking a look at how the gurus did it.