CRITIQUES WELCOME!

[eboyd]

In a previous post, I asked for some help on my template linked-list program. Well between watching my daughter and going to the hospital (after a bad accident), I've managed to get quite a bit done. I know some of the functions are probably a bit overkill, but my goal was to learn how to write a template, and to refresh myself on linked-lists. One thing I'm really stuck on is the list copy constructor. Any help, comments, critiques, etc. are most welcome.

Thanx to all!

Code: Select all

template <typename T> class dlist{    
    
    
    struct type{
        
        T data;
        type *prev, *next;
        type(const T& x, type* y = 0, type* z = 0) : data(x), prev(y), next(z) {}
        type(const type& src) : data(src.data), prev(src.prev), next(src.next) {}
        type& operator=(const type& src){
            if(this != &src){
                type* x, y;
                try{
                    x = new type(*src.prev);
                    y = new type(*src.next);
                }
                catch(...){
                    delete x, y;
                    throw;
                }
                delete prev, next;
                x = src.prev;
                y = src.next;
            }
            return *this;
        }
    };
    
    type *head, *tail;


    public:
    
        dlist() : head(new type(T())), tail(new type(T())) {}
        dlist(const dlist& src);
       ~dlist(){ clear(); delete head; delete tail; }
       
        bool empty();
        unsigned int size();
        bool sorted(); 
        bool prox(const T&);
        void makef(const T&); 
        void pushf(const T&);
        void pushb(const T&);
        void popf();
        void popb();
        void insert(const T&);
        void revins(const T&);     
        void ins(const T&);  
        void remove(const T&);
        void revrem(const T&);
        void rem(const T&);
        void remall(const T&);
        void dis();
        void revdis();
        void sort();
        void revsort();
        void rev();
        bool search(const T&);
        void consearch(const T&);
        void clear();    
};

const bool HEAD = 1;




template <typename T> inline bool dlist<T>::empty(){
    
    bool b = ((head->next == 0 && tail->prev == 0) || (head->next == tail && tail->prev == head)) ? 1 : 0;
    return b;
}




template <typename T> inline bool dlist<T>::sorted(){
    
    bool sortd;
    type *curr, *p;
    curr = (head->next)->next;
    p = head->next;
    while(p->data <= curr->data && curr != tail){
        
        p = curr;
        curr = curr->next;
    }
    
    sortd = (curr == tail) ? 1 : 0;
    return sortd;
}




template <typename T> inline bool dlist<T>::prox(const T& x){
    
    if(!empty()){
        
        T diff1 = ((head->next)->data) - x;
        T diff2 = ((tail->prev)->data) - x;
        diff1 = (diff1 < 0) ? diff1 * -1 : diff1;
        diff2 = (diff2 < 0) ? diff2 * -1 : diff2;
        if(diff1 <= diff2){
            
            return 1;
        }
        
        else{ return 0; }
    }
}




template <typename T> inline void dlist<T>::clear(){
    
    while(!empty()){
        
        if(!empty()){ popf(); }
        if(!empty()){ popb(); }
    }
}




template <typename T> inline unsigned int dlist<T>::size(){
    
    if(!empty()){
        
        type* curr = head->next;
        unsigned int x = 0;
        while(curr != tail){
            
            curr = curr->next;
            x++;
        }
        
        return x;
    }
    
    else{ return 0; }
}




template <typename T> inline void dlist<T>::makef(const T& x){
    
    type* temp = new type(x);
    head->next = temp;
    tail->prev = temp;
    temp->prev = head;
    temp->next = tail;
}




template <typename T> inline void dlist<T>::pushf(const T& x){
    
    if(!empty()){
        
        type *temp = new type(x);
        temp->next = head->next;
        temp->prev = head;
        head->next = temp;
        (temp->next)->prev = temp;
    }
    
    else{ makef(x); }
}



  
template <typename T> inline void dlist<T>::pushb(const T& x){
    
    if(!empty()){
        
        type* temp = new type(x);
        temp->prev = tail->prev;
        temp->next = tail;
        tail->prev = temp;
        (temp->prev)->next = temp;
    }
    
    else{ makef(x); }
}



  
template <typename T> inline void dlist<T>::popf(){
    
    if(!empty()){

        type* temp = head->next;
        head->next = temp->next;
        (temp->next)->prev = head;
        delete temp;
    }
}



            
template <typename T> inline void dlist<T>::popb(){
    
    if(!empty()){
        
        type* temp = tail->prev;
        tail->prev = temp->prev;
        (temp->prev)->next = tail;
        delete temp;
    }
}



            
template <typename T> void dlist<T>::insert(const T& x){
    
    if(!empty()){
        
        if(!sorted()){ sort(); }
        
        type *curr, *temp;
        curr = head->next;
        temp = new type(x);
        while(curr != tail && curr->data <=x){
            
            curr = curr->next;
        }
        
        if(curr == head->next){ pushf(x); }
        
        else if(curr == tail){ pushb(x); }
        
        else{
            
            temp->prev = curr->prev;
            (curr->prev)->next = temp;
            temp->next = curr;
            curr->prev = temp;
        }
    }
               
    else{ makef(x); }
}




template <typename T> void dlist<T>::revins(const T& x){
    
    if(!empty()){
        
        if(!sorted()){ sort(); }
        
        type *curr, *temp;
        curr = tail->prev;
        temp = new type(x);
        while(curr != head && curr->data >= x){
            
            curr = curr->prev;
        }
        
        if(curr == tail->prev){ pushb(x); }
        
        else if(curr == head){ pushf(x); }
        
        else{
            
            temp->next = curr->next;
            (curr->next)->prev = temp;
            temp->prev = curr;
            curr->next = temp;
        }
    }
               
    else{ makef(x); }
}




template <typename T> void dlist<T>::ins(const T& x){
    
    unsigned int sz = size();
    if(!(sz > 1 )){ insert(x); }
    else{
        
        if(prox(x) == HEAD){ insert(x); }
        
        else{ revins(x); }    
    }
}



         
template <typename T> void dlist<T>::remove(const T& x){
    
    if(!empty()){
        
        int sz = size();
        bool found = search(x);
        if(found){
            
            if(sz == 1){ popf(); }
            else{
                
                type* curr = head->next;
                while(curr != tail && curr->data != x){
                
                    curr = curr->next;
                }
                
                if(curr == head->next){ popf(); }
                
                else if(curr == tail->prev){ popb(); }
                
                else{

                    (curr->prev)->next = curr->next;
                    (curr->next)->prev = curr->prev;
                    delete curr;
                }
            }        
        }
    }
}


template <typename T> void dlist<T>::revrem(const T& x){
    
    if(!empty()){
        
        int sz = size();
        bool found = search(x);
        if(found){
            
            if(sz == 1){ popf(); }
            else{
                
                type* curr = tail->prev;
                while(curr != head && curr->data != x){
                
                    curr = curr->prev;
                }
                
                if(curr == tail->prev){ popb(); }
                
                else if(curr == head->next){ popf(); }
                
                else{

                    (curr->next)->prev = curr->prev;
                    (curr->prev)->next = curr->next;
                    delete curr;
                }
            }        
        }
    }
}




template <typename T> void dlist<T>::rem(const T& x){
    
    unsigned int sz = size();
    if(!(sz > 1 )){ clear(); }
    else{
        
        if(prox(x) == HEAD){ remove(x); }
        
        else{ revrem(x); }
    }
}




template <typename T> void dlist<T>::remall(const T& x){
    
    bool found = search(x);
    if(found){

        while(found){
            
            rem(x);
            found = search(x);
        }
    }
}





template <typename T> void dlist<T>::consearch(const T& x){

    bool found = 0;
    if(!empty()){
        
        type* curr = head->next;
        unsigned int position = 1;
        while(curr != tail){
            
            if(curr->data == x){
                
                std::cout << "SEARCH: Found at position " << position << "." << std::endl;
                found = 1;
            }
            
                curr = curr->next;
                position++;
        }
        
        if(found != 1){
            
            std::cout << "*FAILURE* SEARCH: Entry not found." << std::endl;
        }
    }
    
    else{ std::cout << "*FAILURE* SEARCH: Empty list." << std::endl; }
}




template <typename T> bool dlist<T>::search(const T& x){

    bool found = 0;
    if(!empty()){
        
        type* curr = head->next;
        unsigned int position = 1;
        while(curr != tail){
            
            if(curr->data == x){

                found = 1;
            }
            
                curr = curr->next;
                position++;
        }
    }
    
    return found;
}




template <typename T> void dlist<T>::dis(){
    
    if(!empty()){
        
        type* curr = head->next;
        while(curr != tail){
        
            std::cout << curr->data << std::endl;
            curr = curr->next;
        }
    }
}




template <typename T> void dlist<T>::revdis(){
    
    if(!empty()){
        
        type* curr = tail->prev;
        while(curr != head){
            
            std::cout << curr->data << std::endl;
            curr = curr->prev;
        }
    }
}




template <typename T> void dlist<T>::sort(){
    
    if(!empty()){
        
        type *curr, *p;
        curr = (head->next)->next;
        p = head->next;
        while(curr != tail){
            
            if(curr->data < p->data){
  
                p->next = curr->next;
                curr->prev = p->prev;
                curr->next = p;
                p->prev = curr;
                (curr->prev)->next = curr;
                (p->next)->prev = p;
                curr = (head->next)->next;
                p = head->next;
            }
            
            else{
            
                p = curr;
                curr = curr->next;
            }
        }
    }        
}




template <typename T> void dlist<T>::revsort(){
if(!empty()){
        
        type *curr, *p;
        curr = (head->next)->next;
        p = head->next;
        while(curr != tail){
            
            if(curr->data > p->data){
                
                p->next = curr->next;
                curr->prev = p->prev;
                curr->next = p;
                p->prev = curr;
                (curr->prev)->next = curr;
                (p->next)->prev = p;
                curr = (head->next)->next;
                p = head->next;
            }
            
            else{
            
                p = curr;
                curr = curr->next;
            }
        }
    }        
}


template <typename T> void dlist<T>::rev(){

    if(!empty()){
    
        type* curr = head->next;
        int sz = size();
        while(curr != tail){
            
            T temp = curr->data;
            pushfront(temp);
            curr = curr->next;
        }
        
        for(int i = 0; i < sz; i++){
            
            popb();
        }
    }
}

[os64dev]

way to long post, you can add attachments you know.

One thing I'm really stuck on is the list copy constructor

Well this is one of the more difficult things in general. The problem with copy constructs is either the shallow or deep copy. In case of lists you generally need a deep copy. meaning that you need to make a copy of each value in the list. not just a pointer copy. If you have a list and make a shallow copy of that list (pointers only) the problems becomes clear when you delete an item in the original list. The copied list does not remove the item but the data it points to becomes in valid. With a deep copy you do no have this problem.

[eboyd]

The problem with copy constructs is either the shallow or deep copy.

ya' think.
Sorry for the sarcasm, that just struck me as funny. I don't mean to offend

Interestingly enough though, I've played around with it, and I get the impression that the copy ctor/assignment optor can be written in either the type struct OR the list class. If I take it out of the type struct, it seems like the compiler is complaining that it can't find it in the list class. But I've checked the copy ctor/assignment optor in main() (with the copy ctor/assignment optor i have in the type struct) and I'm getting no issues with either.

Here's what i've tested:

Code: Select all

#inlcude <iostream>
#include "dlist.h"

int main(){

    dlist<int> list;
    for(int i = 0; i < 10; i++){
        list.pushf(i);
    }

    dlist<int> list2(list);
    list.rem(1);
    dlist<int> list3 = list2;
    list2.rem(5);
    list.dis();
    list3.dis();

    system("pause");
    return 0;

It seems to be working with no issues (pointing to invalid memory locations.)
I'm not sure if it matters where the copy ctor/@$$ optor are written, if someone knows the answer, i'd sure like to know!

[Candy]

Here's what i've tested:

Code: Select all

#inlcude <iostream>
#include "dlist.h"

I doubt that.

[eboyd]

well, maybe not that!

i had the files separated dlist.h & dlist.cpp
typing still eludes me after all this time...

[eboyd]

i was hoping someone could just easily copy and paste what i had into "dlist.h" and play 'round with it, but i guess you'll need my spell-checking-enabled compiler!

[Candy]

i was hoping someone could just easily copy and paste what i had into "dlist.h" and play 'round with it, but i guess you'll need my spell-checking-enabled compiler!

While we're on the subject, read up on so-called Test Driven Development, TDD. You first develop an interface for an object, then you develop its test cases (that are designed to test the full interface), make sure they work by making each of them fail and then add code to make all of them work. If you then find a case that doesn't work, add it to the test program, fix the code and keep it in there as a continual regression test against past code.

It takes a while to start with but if you got a base in it, you'll love it. Especially when fixing a base layer of your software after which all hell breaks loose - or one test case fails.

[os64dev]

Interestingly enough though, I've played around with it, and I get the impression that the copy ctor/assignment optor can be written in either the type struct OR the list class. If I take it out of the type struct, it seems like the compiler is complaining that it can't find it in the list class. But I've checked the copy ctor/assignment optor in main() (with the copy ctor/assignment optor i have in the type struct) and I'm getting no issues with either.

Wierdly enough i can't find all the copy constructors code in your post. but you need to implement the copy constructor in the list.

Code: Select all

  struct type {
  type(const type& src) : data(src.data), prev(src.prev), next(src.next) {
  }
}

The problem with is is that it copies the data and the pointer next and prev. Though the data is corrects the pointers are not because they belong to the other(source) list. So what to do is.

Code: Select all

dlist(const dlist& src) {
  clear(); //- empty the list it currently holds.
  for(type * iter = src.head; iter != src.tail; iter = iter->next) {
    //- make a deep copy of each item in the src list.
    pushb(iter->data);
  }
}

[Candy]

MSVC specific item: make sure your copy constructor takes a const reference. If you define one taking a non-const reference and one taking a const-reference MSVC screws up horribly, if you only define the former it screws up nontraceable but less horrible.

[eboyd]

oh, by msvc you mean microsoft visual studio? i'm not using that. i'm using devc++.

[eboyd]

thnx for the help on the copy ctor os64dev. i never actually WROTE the one for the list class, hence why you see its prototype but no implementation. i couldn't figure it out. my only question about yours, is don't i need to reinitialize the head and tail pointers such as:

Code: Select all

list(const list& src) : head(new type(t())), tail(new type(t())){

blah, blah, blah
}

[earlz]

I just have to say...
DON'T TYPE LIKE THIS!!!! ESPECIALLY IN TITLES!!!

[os64dev]

thnx for the help on the copy ctor os64dev. i never actually WROTE the one for the list class, hence why you see its prototype but no implementation. i couldn't figure it out. my only question about yours, is don't i need to reinitialize the head and tail pointers such as:

Code: Select all

list(const list& src) : head(new type(t())), tail(new type(t())){

blah, blah, blah
}

your welcome, i did not look into that but i assumed the 'clear' method reset both of them to null and the 'add' method updates them. If this is truly the case then there is no need to initialize the head and tail pointers.

[eboyd]

SRRY HCKR83!!!
I DINDNT MEAN TO UPSET YOU!!!
IT WONT HAPPEN AGAIN!!!

[eboyd]

ima confused.

should i reset them like so in clear()

Code: Select all

    head->prev = 0;
    head->next = 0;
    tail->prev = 0;
    tail->next = 0;

and will that solve all my problems, at least my lists problems anyway?