Hello, I am creating an implementation of LIST that displays a list of 4 elements and also displays them in reverse. It seems to be correctly displaying the first list but I am getting a segmentation fault error before it displays the reverse list and I am not sure why. Can anybody point out why the code is doing that? I believe there may be something wrong with my begin() and end() functions but I am not sure what it is.

#include <iostream> 
#include <algorithm>

using namespace std;

template <class T> class Link;
template <class T> class List_iterator;

template <class T> 
class List
{
public:
   typedef List_iterator<T> iterator;

   List();
   List(const List<T> & l);
   ~List();

   bool empty() const;
   unsigned int size() const; 
   T & back() const;
   T & front() const;
   void push_front(const T & x);
   void push_back(const T & x);
   void pop_front();
   void pop_back();
   iterator begin() const;
   iterator end() const;
   iterator rbegin() const;//REVERSE BEGIN
   iterator rend() const; //REVERSE END
   void insert(iterator pos, const T & x);
   void erase(iterator & pos); 
   List<T> & operator=(const List<T> & l);

protected:
   Link<T> * first_link;
   Link<T> * last_link;
   unsigned int my_size;
};

template <class T>
List<T>::List()
{
        first_link = 0;
        last_link = 0;
        my_size = 0;
}

template <class T>
List<T>::List(const List & l)
{
        first_link = 0;
        last_link = 0;
        my_size = 0;
        for (Link<T> * current = l.first_link; current != 0; current = current -> next_link)
                push_back(current -> value);
}

template <class T>
typename List<T>::iterator List<T>::begin() const
{
        Link<T> * begin = first_link; //return iterator(first_link);
}

template <class T>
typename List<T>::iterator List<T>::end() const
{
        Link<T> * end = last_link + 1;
}

//RBEGIN
template <class T>
typename List<T>::iterator List<T>::rbegin() const
{
	Link<T> * rbegin = last_link + 1;
}

//REND
template <class T>
typename List<T>::iterator List<T>::rend() const
{
	Link<T> * rend = first_link;
}

template <class T> 
class Link 
{
private:
   Link(const T & x): value(x), next_link(0), prev_link(0) {}
                
   T value;     
   Link<T> * next_link;
   Link<T> * prev_link;

   friend class List<T>;
   friend class List_iterator<T>;
};

template <class T> class List_iterator
{
public:
   typedef List_iterator<T> iterator;

   List_iterator(Link<T> * source_link): current_link(source_link) { }
   List_iterator(): current_link(0) { }
   List_iterator(List_iterator<T> * source_iterator): current_link(source_iterator.current_link) { }

   T & operator*();
   iterator & operator=(const iterator & rhs);
   bool operator==(const iterator & rhs) const;
   bool operator!=(const iterator & rhs) const;
   iterator & operator++(); 
   iterator operator++(int);
   iterator & operator--(); 
   iterator operator--(int); 

protected:
   Link<T> * current_link;

   friend class List<T>;
};

//NEW CLASS - REVERSE ITERATOR
template <class T> class Reverse_iterator
{
public:
   typedef Reverse_iterator<T> iterator;
  
   Reverse_iterator(Link<T> * source_link): current_link(source_link) {}
   Reverse_iterator(): current_link(0) { }
   Reverse_iterator(Reverse_iterator<T> * source_iterator): current_link(source_iterator.current_link) { }

   T & operator*();
   iterator & operator=(const iterator & rhs);
   bool operator==(const iterator & rhs) const;
   bool operator!=(const iterator & rhs) const;
   iterator & operator++(); 
   iterator operator++(int);
   iterator & operator--(); 
   iterator operator--(int); 

protected:
   Link<T> * current_link;

   friend class List<T>;
};

template <class T>
Reverse_iterator<T> & Reverse_iterator<T>::operator++()
{
	current_link = current_link -> prev_link;
	return *this;
}

template <class T>
T & List_iterator<T>::operator*()
{
        return current_link -> value;
}

template <class T>
List_iterator<T> & List_iterator<T>::operator++()
{
        current_link = current_link -> next_link;
        return *this;
}

template <class T>
void List<T>::push_back(const T & x)
{
    Link<T> * new_link = new Link<T> (x);
    if (first_link == 0)
	first_link = last_link = new_link;
    else
    {
	new_link->prev_link = last_link;
        last_link->next_link = new_link;	
        last_link = new_link;
    }
    my_size++;
}

template <class T>
List <T>::~List()
{
    Link <T> * first = first_link;
    while (first != 0)
    {
	Link <T> * next = first->next_link;
        delete first;
	first = next;
    }
}

template<class T>
bool List_iterator<T>::operator==(const iterator & rhs) const
{
    return ( this->current_link == rhs.current_link ); 
}

template <class T>
bool List_iterator<T>::operator!=(const iterator & rhs) const
{
    return !( *this == rhs );
}

int main()
{
   List<int> l;

   l.push_back(44);  // list = 44
   l.push_back(33);  // list = 44, 33
   l.push_back(11);  // list = 44, 33, 11
   l.push_back(22);  // list = 44, 33, 11, 22

   List<int> m(l);

   List<int>::iterator original(m.begin());
   while (original != m.end()) {
        cout << *original << endl;
        ++original;
   }

   List<int> n(l);   

   List<int>::iterator reverse(n.rend());
   while (reverse != n.rbegin()) {
        cout << *reverse << endl;
        ++reverse;
   }
}

Your begin, end, rbegin, and rend functions don't have any return statements in them, so they return garbage.

Your begin, end, rbegin, and rend functions don't have any return statements in them, so they return garbage.

What should they return?
Can you please give me an example of one?

On line 62, you define and initialize a local variable named begin. You never do anything with that variable again, which means that it serves no purpose. On the same line, you have a return statement that is commented out. Why?

Independently of these problems, your uses of first_link + 1 in lines 68 and 75 are just wrong. The only time it makes sense to add an integer and a pointer is when that pointer points to an element of an array, and first_link does not do so in this case.

I am reluctant to tell you how to solve these problems, because I don't want to do your homework for you. If you make a serious effort to do so yourself, and explain what you did, I may change my mind.

That sounds fair, I put in the '+1' because it was displaying all of the values, except for the last one. So when the program ran, it would display 44, 33, 11, but not 22. The '+1' made the program display all four elements of the list but that is also what started the segmentation fault error that appears after the numbers are displayed.

As far as changing the return value for begin (the one I commented out), it was because I was just looking for different ways to do the same thing, which I obviously failed at.

Are you saying that the code I commented out was actually correct?

Are you saying that the code I commented out was actually correct?

It looked correct at first glance. I haven't analyzed the code thoroughly, as I've been doing about three other things at the same time today.

It looked correct at first glance. I haven't analyzed the code thoroughly, as I've been doing about three other things at the same time today.

It's alright, I pretty much failed at this implementation.
I'm pretty sure that the begin() function was correct but the end() function was wrong, playing around with it a bit showed me that the segmentation fault error came from there, specifically because of the +1 but I couldn't figure out any other way to display all the elements of the list.

It sounds to me that perhaps you're thinking about the program's output rather than the properties that you want your iterators to have.

If you have an iterator that refers to the last element of a list, and you apply ++ to it, what does that iterator refer to? Whatever your answer is to that question, the value returned by end() has to have the same answer.

It sounds to me that perhaps you're thinking about the program's output rather than the properties that you want your iterators to have.

If you have an iterator that refers to the last element of a list, and you apply ++ to it, what does that iterator refer to? Whatever your answer is to that question, the value returned by end() has to have the same answer.

I thought it was invalid to apply ++ to the last element of the list, because there would be nothing there for it to refer to at all?

What do you think end() returns for a container?

I tried looking up how it works earlier, I read that it has to return an element past the end in the list.
I just have no clue how to set this element that goes past the end.

This article has been dead for over six months. Start a new discussion instead.