CODEWITHSUNDEEP
c++list
mikhailovich
mikhailovich

Reputation: 229

What are the problems with my List<T> implementation?

I created a small implementation of the container list that performs certain functions based on a test main() I was given.

I wanted to add some extra functions to it. Mainly an operator[], and a reverse() function that displays the numbers in the list backwards.

Here is my code, everything with a comment was added to it yesterday.

#include <iostream> 
#include <algorithm>

using namespace std;

template <class T> class Link;
template <class T> class List_iterator;
template <class T> class Reverse_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);
   List<T> & operator[] (unsigned int x);//OPERATOR []
   iterator reverse() const; //REVERSE 

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
{
    return iterator(first_link);
}

template <class T>
typename List<T>::iterator List<T>::end() const
{
    return iterator (last_link);
}

//RBEGIN
template <class T>
typename List<T>::iterator List<T>::rbegin() const
{
    return iterator (last_link);
}

//REND
template <class T>
typename List<T>::iterator List<T>::rend() const
{
    return iterator(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>;
};

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

template <class T>
List_iterator<T> List_iterator<T>::operator++(int)
{

}

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

template <class T>
List_iterator<T> & List_iterator<T>::operator=(const iterator & rhs)
{
///???
}

template <class T>
List_iterator<T> List_iterator<T>::operator--(int)
{

}

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 );
}

//REVERSE ITERATOR
template <class T> class Reverse_iterator
{
public:
   typedef Reverse_iterator<T> riterator;

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

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

protected:
   Link<T> * current_link;

   friend class List<T>;
};

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

template <class T>
Reverse_iterator<T> Reverse_iterator<T>::operator++(int)
{

}

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

template <class T>
Reverse_iterator<T> & Reverse_iterator<T>::operator=(const riterator & rhs)
{
//???
}

template <class T>
Reverse_iterator<T> Reverse_iterator<T>::operator--(int)
{

}

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

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


//REVERSE FUNCTION
template <class T>
List_iterator<T> List<T>::reverse() const
{
    iterator i, j;
    i = begin();
    j = end();
    for(; i != j; j++, j--)
    {
            T value = *j;
        *j = *i;
        *i = value;
    }
}

//OPERATOR []
template <class T>
List<T> & List<T>:: operator[] (unsigned int x)
{
    Link<T> * current = first_link;
    for(int i = 0; i != x && i < my_size; i++)
    current = current -> next_link;
    return current -> value;
    delete current;
}


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

int main()
{
   List<int> l;

   l.push_back(44);
   l.push_back(33); 
   l.push_back(11); 
   l.push_back(22); 

   List<int> m(l);
   cout << "This is the original list" << endl;
   List<int>::iterator original(m.begin());
   while (original != m.end()) {
        cout << *original << endl;
        ++original;

   //cout << l[4]; //Not working

   //m.reverse();
   //cout << m;//Also Not working
   }
}

I am looking for help in:

Thanks in advance.

Upvotes: 1

Views: 911

Answers (3)

razlebe
razlebe

Reputation: 7144

Regarding List<T>::operator[]

I believe the main problem with your operator[] is that it's return type is List<T>& rather than T&. You want your operator[] to return a reference to a T, not a reference to an entire list. Operator<< has no idea how to deal with a List<T>, so it complains.

Additionally:

  • That delete in operator[] is unreachable code. (As well as being wrong behaviour - why would you want to delete the link?)

  • Your operator[] generates a couple of warnings because i is an int and my_size is unsigned. Easily corrected, see below.

  • Consider what happens if, as @stefaanv has mentioned, someone asks for myList[4] when there are only 4 items in the list (collections index from zero, remember, so [4] is the fifth item. In your current logic, myList[3] would be returned instead - look carefully at the conditions in the for loop.

Here's what I think operator[] should look like: 

template <class T>
T& List<T>:: operator[] (unsigned int x)
{
    if(x > (my_size - 1)
       || x < 0)
    {
        // throw a suitable exception - index out of bounds
    }

    Link<T> * current = first_link;
    for(unsigned int i = 0; i != x && i < my_size; i++)
       current = current -> next_link;
    return current -> value;
}

...and see here on IdeOne.

Regarding List<T>::reverse

First things first - to see the errors from List_iterator<T> List<T>::reverse(), you first need to fix your main():

  //m.reverse();
  //cout << m;//Also Not working

Note that m is of type List<int>, so that cout line is trying to invoke the << opertaor on your List<T> class - but there isn't one, so you get errors. You could fix this either by:

  1. Defining operator<< on your List<T> class
  2. Replacing the cout line with a loop similar to the while loop in main(), which iterates through the list item by item.

Once you do one or the other of those, you'll see the real error messages coming from your reverse() function. For one thing, you've declared reverse as returning a List_iterator<T> - but it currently doesn't return anything!

Hope that helps! Good luck.

Upvotes: 1

Sarfaraz Nawaz
Sarfaraz Nawaz

Reputation: 361352

iterator begin() const;
iterator end() const;
iterator rbegin() const;//REVERSE BEGIN
iterator rend() const; //REVERSE END

I don't think you've to make these functions const.

It's better if you write two sets of these functions, one for non-const and other for const object.

//first set for non-const objects!
iterator begin();
iterator end();
iterator rbegin();
iterator rend();

//second set for const objects!
const_iterator begin() const;
const_iterator end() const;
const_iterator rbegin() const;
const_iterator rend() const;

This is the C++ Standard way of defining begin and end functions!

Upvotes: 1

stefaanv
stefaanv

Reputation: 14392

errors in reverse:

j = end();

end() should points after the container, so j should have an extra decrement if the container is not empty.

for(; i != j; j++, j--)
  1. j++ must be i++
  2. for even numbers of elements, i will never be the same a j, use i > j

errors in main:

cout << l[4];

There are only 4 elements in your list and you're referencing the 5th, so this shouldn't work.

Upvotes: 0

Related Questions