Pleas take a look & give a critique

Code:

---

#ifndef LIST_H
#define LIST_H


/*      -- BEGIN CLASS LIST --
*/
template <typename T>
class List{
   
   
   
/*      -- BEGIN PRIVATE DEFINITIONS --
*/
    private:
             
        /*      -- BEGIN CLASS NODE --
        */
        struct Node{
           
            T data;
           
            Node *next, *prev;
           
            Node(const T& d) : data(d), next(0), prev(0) {};
           
            Node(const Node& src) : data(src.data), next(src.next), prev(src.prev) {};
           
            Node& operator=(const Node& src){
               
                if(this != &src){
                   
                    Node *n, *p;
                   
                    try{
                       
                        n = new Node(*src.next); // Test for self-assignment
                        p = new Node(*src.prev);
                    }
                   
                    catch(...){ 
                       
                        delete n, p; // If self-assignment occurred, throw an exception
                        throw;
                    }
                   
                    delete next, prev;
                    n = src.next;
                    p = src.prev;
                }
               
                return *this;
            };
       
        }; /*      -- END CLASS NODE --
        */
       
       
        /*  List Private Fields:
        */
        Node *head, *tail; // Pointers to first and last Nodes in List
       
        unsigned int size; // Number of elements in List
       
        bool empty; // TRUE if NO elements in List, FALSE if ( >= 1 ) elements in List
   
   
   
   
/*      -- BEGIN PUBLIC DECLARATIONS --
*/
    public:
       
        /*      -- BEGIN CLASS ITERATOR --
        */
        class Iterator{
           
            private:
               
                Node *curr;
           
            public:
               
                /*  Iterator Constructor:
                */
                Iterator(Node* n = 0) : curr(n) {};
               
                /*  Overloaded Operators:
                   
                    NOTE: Postfix & Prefix operators preform the same
                          function.
                */
                Iterator& operator++() { curr = curr->next; return *this; };
               
                Iterator& operator++(int) { curr = curr->next; return *this; };
               
                Iterator& operator--() { curr = curr->prev; return *this; };
               
                Iterator& operator--(int) { curr = curr->prev; return *this; };
               
                bool operator!=(const Iterator& i) { return i.curr != curr; };
               
                bool operator==(const Iterator& i) { return i.curr == curr; };
                       
                const T& operator*() const { return curr->data; };
               
                Node* get_curr() const { return curr; }
       
       
        }; /*      -- END CLASS ITERATOR --
        */       
       
       



/*      -- PUBLIC INTERFACE --
*/


        /*  List Constructors:
        */
        List<T>(); // Creates an instance of List
       
        List<T>(const List& src); // Copies an existing List
       
        List<T>& operator=(const List& src); // Copies an existing List through assignment
       
      ~List<T>(); // Deletes all instances of Node & List
       
       
        /*  List Functions:
        */
        bool is_empty(){ return empty; } // Returns 1 if the List is Empty
       
        unsigned int size_of(){ return size; } // Returns an integer (size of List)
       
        void push_front(const T&); // Appends to beginning of List
       
        void pop_front(); // Deletes Node in head position
       
        void push_back(const T&); // Appends to end of List
       
        void pop_back(); // Deletes Node in tail position
       
        void insert(const T&); // Assumes List is sorted, inserts with <
       
        void remove(const T&); // Removes all elements w/matching value
       
        void sort(); // Sorts List with <
       
        void swap(Node*); // Swaps next and prev pointers for specified Node
       
        void reverse(); // Reverses order of List
       
        void unique(); // Removes duplicate values
       
        void clear(); // Deletes all elements in List
       
        void display(); // Displays values to std::cout
       
       
        /*  Iteration-based Functions:
        */
        Iterator begin() const { return Iterator(head); }; // Beginning of List (head)
       
        Iterator end() const { return Iterator(0); }; // End of List (tail->next = 0)
       
        Iterator rbegin() const { return Iterator(tail); }; // Beginning of List (tail)
       
        Iterator rend() const { return Iterator(0); }; // End of List (head->prev = 0)
       
        Iterator at(Node* x) const { return Iterator(x); }; // Returns an Iterator at specified Node
       
        Iterator at(Iterator i) const { return Iterator(i.get_curr()); };
       
        Iterator at(int n) const {
                       
                        Iterator iter = begin();
                        for(int i = 0; i < n; i++){
                               
                                iter++;
                        }
                       
                        return iter;
                }
           
        Iterator insert(Iterator, const T&); // Insert at specified position, return position
       
        Iterator remove(Iterator); // Removes element at specified position, return position
       
       
}; /*      -- END CLASS LIST -- 
*/





/*  LIST CONSTRUCTOR:
*/
template <typename T>
List<T>::List() : head(0), tail(0), size(0), empty(1) {}



/*  LIST COPY-CONSTRUCTOR:
*/
template <typename T>
List<T>::List(const List& src) : head(0), tail(0), size(0), empty(1){
   
        clear();
        for(Iterator i = at(src.head); i != end(); i++){
           
            push_back(*i);
        }
       
        /*  Implementation w/out Iterators
       
        clear();
        for(Node* curr = src.head; curr != (src.tail)->next; curr = curr->next){
           
            push_back(curr->data);           
        }
        */
}



/*  LIST ASSIGNMENT OPERATOR:
*/
template <typename T> List<T>&
List<T>::operator=(const List& src){
   
    if(this != &src){
       
        Node *h, *t;
       
        try{
           
            h = new Node(*src.head); // Test for self-assignment
            t = new Node(*src.tail);
        }
       
        catch(...){
           
            delete h, t; // If self-assignment occurred, throw an exception
            throw;
        }
       
        delete head, tail;
        h = src.head;
        t = src.tail;
    }
   
    return *this;
}



/*  LIST DESTRUCTOR:
*/
template <typename T>
List<T>::~List(){
   
    clear();
    delete head;
    delete tail;
}



/*  FUNCTION: push_front(const T&)
   
    PURPOSE:  Creates an instance of Node in the
              head position.
*/
template <typename T> void
List<T>::push_front(const T& x){
   
    if(!empty){
       
        head->prev = new Node(x);
        (head->prev)->next = head;
        head = head->prev;
        head->prev = 0;
    }
   
    else{
       
        head = tail = new Node(x);
        empty = !empty;
    }
   
    size++;
}



/*  FUNCTION: pop_front()
   
    PURPOSE:  deletes the Node in the head position
*/
template <typename T> void
List<T>::pop_front(){
   
    if(!empty){
       
        if(head != tail){
           
            Node *curr(head);
            (head->next)->prev = 0;
            head = head->next;
            delete curr;
        }
       
        else{
           
            Node* curr = head;
           
            head = tail = 0;
            delete curr;
            empty = !empty;
        }
       
        size--;
    }
}



/*  FUNCTION: push_back(const T&)
   
    PURPOSE:  Creates an instance of Node in the
              tail position
*/
template <typename T> void
List<T>::push_back(const T& x){
   
    if(!empty){
       
        tail->next = new Node(x);
        (tail->next)->prev = tail;
                tail = tail->next;
        tail->next = 0;
    }
   
    else{
       
        head = tail = new Node(x);
        empty = !empty;
    }
   
    size++;
}



/*  FUNCTION: pop_back()
   
    PURPOSE:  deletes the Node in the tail position
*/
template <typename T> void
List<T>::pop_back(){
   
    if(!empty){
     
      if(head != tail){
           
            Node* curr(tail);
            (tail->prev)->next = 0;
            tail = tail->prev;
            delete curr;
        }
       
        else{
           
            Node* curr = head;
            head = tail = 0;
            delete curr;
            empty = !empty;
        }
       
        size--;
        }
}



/*  FUNCTION: insert(const T&)

    PURPOSE:  Assumes List is sorted, Inserts with <
*/
template <typename T> void
List<T>::insert(const T& x){
   
    if(!empty){
       
                Iterator i = begin();
                while(i != end() && *i <= x){

                        i++;
                }
               
                if(i == begin()){ push_front(x); }
               
                else if(i == end()){ push_back(x); }
               
                else{
           
            Node* curr = i.get_curr();
                        Node* temp = new Node(x);
                        (curr->prev)->next = temp;
                        temp->prev = curr->prev;
                        temp->next = curr;
                        curr->prev = temp;
                        size++;
                }
        }
       
        else{
       
        head = tail = new Node(x);
        empty = !empty;
        size++;
    }
}



/*  FUNCTION: remove(const T&)

    PURPOSE:  Removes all elements w/matching value (x)
*/
template <typename T> void
List<T>::remove(const T& x){
   
    if(!empty){
               
                Iterator i = begin();
                while(i != end()){
                       
                        if(*i == x){
                               
                                if(i == begin()){
                                       
                                        pop_front();
                                        i = begin();
                                }
                               
                                else if(i == rbegin()){
                                       
                                        pop_back();
                                        i = begin();
                                }
                               
                                else{
                                       
                                        Node* curr = i.get_curr();
                                        (curr->prev)->next = curr->next;
                                        (curr->next)->prev = curr->prev;
                                        delete curr;
                                        curr = head;
                                        size--;
                                }
                               
                        }/*      -- END IF(*i == x) --
                        */
                       
                        else{
                               
                                i++;
                        }
                       
                }/*      -- END WHILE --
        */
        }
}



/*  FUNCTION: sort()

    PURPOSE:  Sorts List with <
*/
template <typename T> void
List<T>::sort(){
}



/*  FUCNTION: swap(Node*)

    PURPOSE:  Swaps next and prev pointers for specified Node
*/
template <typename T> void
List<T>::swap(Node* x){
       
        Node* temp = x->next;
    x->next = x->prev;
    x->prev = temp;
}



/*  FUNCTION: reverse()

    PURPOSE:  Reverses the order of the List
*/
template <typename T> void
List<T>::reverse(){
   
    if(!empty){
   
        for(Iterator i = begin(); i != end(); i--){
               
                    swap(i.get_curr());
            }
       
            Node* temp = head;
            head = tail;
            tail = temp;
    }
}



/*  FUNCTION: unique()

    PURPOSE:  Removes duplicate values
*/
template <typename T> void
List<T>::unique(){
}



/*  FUNCTION: clear()
   
    PURPOSE:  deletes all elements in List
*/
template <typename T> void
List<T>::clear(){
   
    if(!empty){
       
        while(!empty){
           
            if(!empty){ pop_front(); }
            if(!empty){ pop_back(); }
        }
    }
}



/*  FUNCTION: display()
   
    PURPOSE:  displays values to std::cout
*/     
template <typename T> inline void
List<T>::display(){

    if(!empty){
       
        for(Iterator i = begin(); i != end(); i++){
           
            std::cout << *i << std::endl;
        }
    }
}


#endif

---

While it is hard to comment on all of it, there are some very strange things going on.

For example Node assignment:

Code:

---

Node& operator=(const Node& src){               
    if(this != &src){                   
        Node *n, *p;                   
        try{
           
            n = new Node(*src.next); // Test for self-assignment
            p = new Node(*src.prev);
        }                   
        catch(...){                 
            delete n, p; // If self-assignment occurred, throw an exception
            throw;
        }                   
        delete next, prev;
        n = src.next;
        p = src.prev;
    }             
    return *this;
};

---

Firstly, I don't get all what this code is doing (each assignment allocates its neighbours, but would the new neighbours be pointing to right things?). However, the try-catch block shows some profound misunderstandings. Firstly, there is no test for self-assignment there. And secondly, if an exception is thrown by either of the new statements, at least one of the pointers will be invalid and can't be deleted.

But a Node is such a simple thing that it shouldn't need any special copy construction and assignment. Just make sure that a Node cannot possibly be available to the user (why does get_curr return a Node*).

The list's assignment has similar flaws and absolutely doesn't do what it is supposed to do. Why not simply base it on the copy-constructor + swap idiom (which was discussed recently)?

Another good constructor to have is one that takes two iterators (a range).

Other nitpicks are some naming conventions, e.g I'd expect a method named size() not size_of() and the signature of swap(Node*) is rather unexpected, even for internal use only.

There are also some meaningless tests, e.g

Code:

---

    if(!empty){       
        while(!empty){

---

The while loop begins with the same test as the if and would be skipped anyhow if empty.

Similarly:

Code:

---

    if(!empty){       
        for(Iterator i = begin(); i != end(); i++){

---

The for loop end condition would be false if empty and the loop skipped.

And in the end, the List doesn't need a special member for empty, because in an empty list head and tail should be 0, so these could be used for these tests.

---
Concerning Iterators: the *overload should return a non-const reference, so you could also modify items in the list. (It's the const_iterator that returns a const reference.)

--------------
To test your list, you might use a class like this:

Code:

---

struct Tester
{
   
    static int constructor;
    static int copy_constructor;
    static int destructor;
    Tester() {++constructor;}
    Tester(const Tester&) {++copy_constructor;}
    ~Tester() {++destructor;}
    static void print()
    {
        std::cout << "Constructor: " << constructor <<
        "\nCopy constructor: " << copy_constructor <<
        "\nDestructor: " << destructor << '\n';
    }
};

---

When the list goes up of scope, the sum of constructor and copy-constructor calls and destructor calls should be equal. Add data members as needed.

This is an absolute WTF:

Code:

---

template <typename T> void
List<T>::swap(Node* x){
       
    Node* temp = x->next;
    x->next = x->prev;
    x->prev = temp;
}

---

There are some seriously bazaar things in the posted code.
Stop reinventing the standard C++ library!

Quote:

---

Originally Posted by iMalc

There are some seriously bazaar things in the posted code.
Stop reinventing the standard C++ library!

---

Ha! I actually just want to reproduce it, so I can understand every aspect of it (or at least most of it). Tis' why I appreciate the critiques, so I can be pointed in the right direction!

but I would like to know what is bazaar about it. That might be more helpful...

swap usually swaps two nodes. Your swap doesn't swap two nodes, it just makes the next and prev pointers point backwards, ruining the list:

Code:

---

1-->2-->3-->4-->NULL (next pointers)
NULL<--1<--2<--3<--4 (prev pointers)

swap(3);

1-->2-->3-->2  4-->NULL (next pointers)
NULL<--1<--2  4<--3<--4 (prev pointers)

---

Well, the issue is that the function is named unconventionally. It is used for reversing the list, and in this usage it does the right thing. (It should not be a public method though.)
However, it would be much less confusing to use: swap(prev, next);

my value look-up:

Code:

---

const T& operator*() const { return curr->data; };

---

which "const" should be removed to allow the user to modify the value?

Both.

also, for reverse(), would it be more efficient to just exchange values?

And how would you modify the value?

Code:

---


Iterator i(list.begin());

*i = 10;

---

??????????

You should have both versions of operator*, the const version and the non-const version. If you do, then *i = 10 will work in changing the data (it will call the non-const version, which returns a reference and so the value stored in the list will be updated through the reference).

>> for reverse(), would it be more efficient to just exchange values?
No. You should move pointers around. The function name swap threw me off, it is normally used for something else.

This is the test I have for the operator*:

List.h

Code:

---

#ifndef LIST_H
#define LIST_H

template <typename T> class List{
   
    private:
       
        struct Node{
           
            T data;
            Node *next, *prev;
            Node(const T& d, Node* n = 0, Node* p = 0) : data(d), next(n), prev(p) {};
           
        };
       
        unsigned int size;
        Node *head, *tail;
       
    public:
       
        class Iterator{
           
            private:
               
                Node* curr;
               
            public:
               
                Iterator(Node* c = 0) : curr(c) {};
               
                T& operator*() { curr->data; };
                const T& operator*() const { return curr->data; };
               
        };

        List<T>();
        Iterator begin() const { return Iterator(head); };
       
       
       
       
};/*      -- END CLASS LIST
*/


/*  CONSTRUCTOR
*/
template <typename T>
List<T>::List() : head(0), tail(0), size(0) {}

#endif

---

and Main.cpp

Code:

---

#include <iostream>
#include "List.h"

int main(){
   
    List<int> list;
    List<int>::Iterator i = list.begin();   

    *i = 10;
    std::cout << *i << "\n";
   
    return 0;
}

---

I hope I have this right so far

Don't you have to add something to the list before you modify it? If that was an STL list you'd probably make your program crash because the list is empty but you're using an iterator to a non-existent first object.

Quote:

---

Originally Posted by Daved

Don't you have to add something to the list before you modify it? If that was an STL list you'd probably make your program crash because the list is empty but you're using an iterator to a non-existent first object.

---

i fixed that (it was a bad example).

Now I'm wondering about at()
Should the handle of at() look like:

Code:

---

Iterator at(int);

---

If so, then should I enable the list to perform an assignment like:

Code:

---

list.at(n) = aNumber;

---

?