Thread: Pleas take a look & give a critique

  1. #1
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127

    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

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    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!

  5. #5
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    but I would like to know what is bazaar about it. That might be more helpful...

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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)

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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);
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    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?

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Both.

  10. #10
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    also, for reverse(), would it be more efficient to just exchange values?

  11. #11
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    And how would you modify the value?

    Code:
    Iterator i(list.begin());
    
    *i = 10;

    ??????????

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  13. #13
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    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

  14. #14
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  15. #15
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    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;
    ?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Give me some opinions on setting up a server
    By Shadow in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 04-19-2004, 10:38 AM
  2. Can you give me your tip plz :)
    By dionys in forum C Programming
    Replies: 6
    Last Post: 04-11-2004, 11:14 PM
  3. Replies: 1
    Last Post: 10-01-2001, 10:39 AM
  4. How To Give A Font Colour ?
    By Unregistered in forum Windows Programming
    Replies: 1
    Last Post: 09-14-2001, 01:22 PM
  5. Just to give you an idea of what we're going through...
    By rick barclay in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 09-13-2001, 02:09 PM