Programming Forums > Application Development > C++

Griz803 · Sep 23rd, 2005, 1:48 PM

I'm not new to programming, but I'm trying to make the jump to using OOP in C++ and specifically trying to understand templates better. I decided to "reinvent the wheel" on a linked list container template to see how things work. Below is my code. I'm using Dev-C++ and it seems to run okay, but I'm not sure of the memory allocation and freeing it after. I seem to find no leaks, but guidance on this and any other issues you find would be apreciated. Thanks in advance.

LList.h:

(Toggle Plain Text)

#ifndef _LLISTTOBJ_HPP_
#define _LLISTTOBJ_HPP_

template <class T>
class LList{
      private:
             LList *Prev, *Cur, *Next;
             T * Data;
             LList * GetNext(void);
             LList * GetPrev(void);
             void SetNext(LList * Nx);
             void SetPrev(LList * Pr);
              
      public:
             LList(){
                     Data = new T;
                     Prev = NULL;
                     Next = NULL;
                     Cur = this;
                     } 
                     
             ~LList(){
                      Cur = FindHead();
                      delete Data;
                      delete Cur;
                      }
                      
             LList * FindHead(void);
             LList * AddNode(void);
             LList * MoveNext(int Step);
             LList * MovePrev(int Step);
             T * GetData(void);
};

template <class T>
void LList<T>::SetNext(LList<T> * Nx){
          Next = Nx;                   
} 

template <class T>                            
void LList<T>::SetPrev(LList<T> * Pr){
          Prev = Pr;
}                                

template <class T>
LList<T> * LList<T>::GetNext(void){
        return Next;
}

template <class T>
LList<T> * LList<T>::GetPrev(void){
        return Prev;
}

template <class T>
LList<T> * LList<T>::FindHead(void){
         LList * Head, * Temp;
         
         Head = Temp = Cur;
         if(Prev == NULL){
                 return(Head);
                 }
         while(Temp != NULL){
                    Temp = Temp->GetPrev();
                    if(Temp != NULL){
                            Head = Temp;
                            }
                    }
         return(Head);
}
 
template <class T>  
LList<T> * LList<T>::AddNode(void){
         Cur->SetNext(new LList<T>);
         Next->SetPrev(Cur);
         return Next;         
}

template <class T>
LList<T> * LList<T>::MoveNext(int Step){
         int i;
         LList<T> * Temp = Cur;
         
         for(i=0; i<Step; i++){
                  if(Temp->GetNext() != NULL){
                                Temp = Temp->GetNext();
                                }
                  }
         return(Temp);
}

template <class T>
LList<T> * LList<T>::MovePrev(int Step){
         int i;
         LList<T> * Temp = Cur;
         
         for(i=0; i<Step; i++){
                  if(Temp->GetPrev() != NULL){
                                Temp = Temp->GetPrev();
                                }
                  }
         return(Temp);
}

template <class T>
T * LList<T>::GetData(void){
         return(Data);
}


#endif

#ifndef _LLISTTOBJ_HPP_
#define _LLISTTOBJ_HPP_

template <class T>
class LList{
      private:
             LList *Prev, *Cur, *Next;
             T * Data;
             LList * GetNext(void);
             LList * GetPrev(void);
             void SetNext(LList * Nx);
             void SetPrev(LList * Pr);
              
      public:
             LList(){
                     Data = new T;
                     Prev = NULL;
                     Next = NULL;
                     Cur = this;
                     } 
                     
             ~LList(){
                      Cur = FindHead();
                      delete Data;
                      delete Cur;
                      }
                      
             LList * FindHead(void);
             LList * AddNode(void);
             LList * MoveNext(int Step);
             LList * MovePrev(int Step);
             T * GetData(void);
};

template <class T>
void LList<T>::SetNext(LList<T> * Nx){
          Next = Nx;                   
} 

template <class T>                            
void LList<T>::SetPrev(LList<T> * Pr){
          Prev = Pr;
}                                

template <class T>
LList<T> * LList<T>::GetNext(void){
        return Next;
}

template <class T>
LList<T> * LList<T>::GetPrev(void){
        return Prev;
}

template <class T>
LList<T> * LList<T>::FindHead(void){
         LList * Head, * Temp;
         
         Head = Temp = Cur;
         if(Prev == NULL){
                 return(Head);
                 }
         while(Temp != NULL){
                    Temp = Temp->GetPrev();
                    if(Temp != NULL){
                            Head = Temp;
                            }
                    }
         return(Head);
}
 
template <class T>  
LList<T> * LList<T>::AddNode(void){
         Cur->SetNext(new LList<T>);
         Next->SetPrev(Cur);
         return Next;         
}

template <class T>
LList<T> * LList<T>::MoveNext(int Step){
         int i;
         LList<T> * Temp = Cur;
         
         for(i=0; i<Step; i++){
                  if(Temp->GetNext() != NULL){
                                Temp = Temp->GetNext();
                                }
                  }
         return(Temp);
}

template <class T>
LList<T> * LList<T>::MovePrev(int Step){
         int i;
         LList<T> * Temp = Cur;
         
         for(i=0; i<Step; i++){
                  if(Temp->GetPrev() != NULL){
                                Temp = Temp->GetPrev();
                                }
                  }
         return(Temp);
}

template <class T>
T * LList<T>::GetData(void){
         return(Data);
}


#endif

DaWei · Sep 23rd, 2005, 2:00 PM

Just a cursory look, Griz, I didn't compile it and run it, or evaluate it stylistically, or anything like that, but I don't see anything being allocated that isn't being freed. Nothing wrong with reinventing the wheel as a learning tool; may be the best way I know.

grumpy · Sep 23rd, 2005, 7:20 PM

On a cursory look, I've found some concerns. If I've read it correctly.... the working of the destructor is a bit strange. The process of destructing a node also destroys (deletes) the head of the list that node is in. But it does not destroy any other nodes in that list. Those other nodes will then be leaked. As object.FindHead() also returns &object of object.Prev is NULL, this can also cause object to be deleted twice. That yields undefined behaviour.

A few issues of style. Some of these can emerge as technical concerns depending on how you evolve the class, but (in your code as is) are not actually incorrect. Suggestions along this line are;

1) It is not necessary to have a member named Cur which points to "this".

2) The default constructor is better implemented as (assuming you've eliminated usage of Cur);

(Toggle Plain Text)

LList(): Data(new T), Prev(NULL), Next(NULL)
{
}

The reason for this guideline is that, if LList() has two members that are both dynamically allocated, then the constructor in your first form will yield a memory leak in some situations if an exception is thrown. Compare what happens with;

(Toggle Plain Text)

LList()
{
   Data = new T;
   Data2 = new T;    // a second data member is also dynamically allocated
   Prev(NULL);
   Next(NULL);
}

In this form, if the creation of Data2 throws an exception, the object pointed to by Data1 is leaked.

However, in the alternate form,

(Toggle Plain Text)

LList(): Data(new T), Data2(new T), Prev(NULL), Next(NULL)
{
}

the standard requires the compiler to clean up if an exception is thrown when creating either Data or Data 2.

3) Your MoveNext and MovePrev methods can be tweaked a bit.

(Toggle Plain Text)

template<class T>
LList<T> * LList<T>::MoveNext(int Step){
         LList<T> *Temp = this, Temp2;
         
         for(i=0; i<Step && (Temp2 = Temp->GetNext()) != NULL; ++i){
                   Temp = Temp2;
                  }
         return Temp;
}

4) You might want GetData() to exist in both const and non-const versions.

5) As your class assumes that T has a default constructor, and you're only making Data point to a single instance, you may wish to simply have Data as a member of type T, rather than a pointer to T. This avoids the need to muck around with managing lifetime of Data: the compiler will do it for you implicitly,

Griz803 · Sep 24th, 2005, 11:10 AM

Thanks for taking a look, both of you.

Grumpy, in reply I have a couple of questions that still remain. Item by item:

1). So, passing this explicitly to delete will work as well as passing it the Cur pointer? Ok, I beleive it. I just didn't know for sure and needed it as a kind of mental insurance policy.

2). I realize that proper error checking hasn't been implemented. That is a later deal, but thanks for the easy suggestion.

3). Yes, that is much tighter code, thanks.

4). Ok, now the question. Not to act like a three year old, but why? Having a "Duh" moment and just not getting the purpose. Explain a bit more please.

5). One of the best reasons to put my code out on the forum. You're 100% right. I let myself get involved with the pointer forest and missed a very good way to simplify my code!

Thanks, have a good day!

grumpy · Sep 24th, 2005, 5:31 PM

Quote:

Originally Posted by Griz803

1). So, passing this explicitly to delete will work as well as passing it the Cur pointer? Ok, I beleive it. I just didn't know for sure and needed it as a kind of mental insurance policy.

"delete this" works fine from a member function. There are some caveats that catch people out (eg after "delete this", one shouldn't try to access the members of the instance), but assigning "Cur = this; delete Cur;" does not change that.

Quote:

Originally Posted by Griz803

2). I realize that proper error checking hasn't been implemented. That is a later deal, but thanks for the easy suggestion.

My suggestion was actually about avoiding the need to explicitly do error checking. One of the common traps is to put too much error checking into constructors. Particularly as the C++ standard specifies what the compiler is required to do if an exception is thrown.

Quote:

Originally Posted by Griz803

4). Ok, now the question. Not to act like a three year old, but why? Having a "Duh" moment and just not getting the purpose. Explain a bit more please.

The reason you're not understanding is probably that you do not use const anywhere. Specifying that an object is const is a very useful hint, to both compiler and programmer, about what will happen during an object's life time -- or even that a particular function guarantees not to do certain things.

For example, if you want to output a LList to an output stream, it is reasonable to expect that operation will not change the LList or any of it's elements. So you might do this;

(Toggle Plain Text)

template<class T> std::ostream &operator<<(std::ostream &s, const LList<T> &list)
{
      s << *(list.GetData()) << '\n';
      return s;
}

The problem with this is that, unless you have a const version of GetData(), you cannot offer such a guarantee.

Not using const in the specification of operator<<() is one way to avoid a need for a const version of GetData() --- and consistent with the fact you have not used const anywhere in your class. But I would not encourage that .....

There are lots of times where const is overused in code (people attach some magic meaning to it). But there are pleny of examples where using it allows the compiler to pick up subtle errors in coding. One pretty common approach in defining test cases is write data from an object to some file at selected points using the supplied operator<<() --- and such test cases can easily fail if a side-effect outputting an object is changing that object.

Griz803 · Sep 25th, 2005, 2:25 PM

Thanks a bunch. Now I at least know why and what parts of my books to hit again. Your answers are great ways to check what it is I think I learned. Have a great day!

Sep 23rd, 2005, 1:48 PM	#1
Griz803 Newbie Join Date: Jul 2004 Location: Somewhere in them thar hills Posts: 23 Rep Power: 0	Trying to Learn About Templates... I'm not new to programming, but I'm trying to make the jump to using OOP in C++ and specifically trying to understand templates better. I decided to "reinvent the wheel" on a linked list container template to see how things work. Below is my code. I'm using Dev-C++ and it seems to run okay, but I'm not sure of the memory allocation and freeing it after. I seem to find no leaks, but guidance on this and any other issues you find would be apreciated. Thanks in advance. LList.h: (Toggle Plain Text) #ifndef _LLISTTOBJ_HPP_ #define _LLISTTOBJ_HPP_ template <class T> class LList{ private: LList Prev, Cur, Next; T Data; LList * GetNext(void); LList * GetPrev(void); void SetNext(LList * Nx); void SetPrev(LList * Pr); public: LList(){ Data = new T; Prev = NULL; Next = NULL; Cur = this; } ~LList(){ Cur = FindHead(); delete Data; delete Cur; } LList * FindHead(void); LList * AddNode(void); LList * MoveNext(int Step); LList * MovePrev(int Step); T * GetData(void); }; template <class T> void LList<T>::SetNext(LList<T> * Nx){ Next = Nx; } template <class T> void LList<T>::SetPrev(LList<T> * Pr){ Prev = Pr; } template <class T> LList<T> * LList<T>::GetNext(void){ return Next; } template <class T> LList<T> * LList<T>::GetPrev(void){ return Prev; } template <class T> LList<T> * LList<T>::FindHead(void){ LList * Head, * Temp; Head = Temp = Cur; if(Prev == NULL){ return(Head); } while(Temp != NULL){ Temp = Temp->GetPrev(); if(Temp != NULL){ Head = Temp; } } return(Head); } template <class T> LList<T> * LList<T>::AddNode(void){ Cur->SetNext(new LList<T>); Next->SetPrev(Cur); return Next; } template <class T> LList<T> * LList<T>::MoveNext(int Step){ int i; LList<T> * Temp = Cur; for(i=0; i<Step; i++){ if(Temp->GetNext() != NULL){ Temp = Temp->GetNext(); } } return(Temp); } template <class T> LList<T> * LList<T>::MovePrev(int Step){ int i; LList<T> * Temp = Cur; for(i=0; i<Step; i++){ if(Temp->GetPrev() != NULL){ Temp = Temp->GetPrev(); } } return(Temp); } template <class T> T * LList<T>::GetData(void){ return(Data); } #endif #ifndef _LLISTTOBJ_HPP_ #define _LLISTTOBJ_HPP_ template <class T> class LList{ private: LList Prev, Cur, Next; T Data; LList * GetNext(void); LList * GetPrev(void); void SetNext(LList * Nx); void SetPrev(LList * Pr); public: LList(){ Data = new T; Prev = NULL; Next = NULL; Cur = this; } ~LList(){ Cur = FindHead(); delete Data; delete Cur; } LList * FindHead(void); LList * AddNode(void); LList * MoveNext(int Step); LList * MovePrev(int Step); T * GetData(void); }; template <class T> void LList<T>::SetNext(LList<T> * Nx){ Next = Nx; } template <class T> void LList<T>::SetPrev(LList<T> * Pr){ Prev = Pr; } template <class T> LList<T> * LList<T>::GetNext(void){ return Next; } template <class T> LList<T> * LList<T>::GetPrev(void){ return Prev; } template <class T> LList<T> * LList<T>::FindHead(void){ LList * Head, * Temp; Head = Temp = Cur; if(Prev == NULL){ return(Head); } while(Temp != NULL){ Temp = Temp->GetPrev(); if(Temp != NULL){ Head = Temp; } } return(Head); } template <class T> LList<T> * LList<T>::AddNode(void){ Cur->SetNext(new LList<T>); Next->SetPrev(Cur); return Next; } template <class T> LList<T> * LList<T>::MoveNext(int Step){ int i; LList<T> * Temp = Cur; for(i=0; i<Step; i++){ if(Temp->GetNext() != NULL){ Temp = Temp->GetNext(); } } return(Temp); } template <class T> LList<T> * LList<T>::MovePrev(int Step){ int i; LList<T> * Temp = Cur; for(i=0; i<Step; i++){ if(Temp->GetPrev() != NULL){ Temp = Temp->GetPrev(); } } return(Temp); } template <class T> T * LList<T>::GetData(void){ return(Data); } #endif __________________ /* Bad command or filename --- go stand in the corner */

Sep 23rd, 2005, 2:00 PM	#2
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Just a cursory look, Griz, I didn't compile it and run it, or evaluate it stylistically, or anything like that, but I don't see anything being allocated that isn't being freed. Nothing wrong with reinventing the wheel as a learning tool; may be the best way I know. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Sep 23rd, 2005, 7:20 PM	#3
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,260 Rep Power: 5	On a cursory look, I've found some concerns. If I've read it correctly.... the working of the destructor is a bit strange. The process of destructing a node also destroys (deletes) the head of the list that node is in. But it does not destroy any other nodes in that list. Those other nodes will then be leaked. As object.FindHead() also returns &object of object.Prev is NULL, this can also cause object to be deleted twice. That yields undefined behaviour. A few issues of style. Some of these can emerge as technical concerns depending on how you evolve the class, but (in your code as is) are not actually incorrect. Suggestions along this line are; 1) It is not necessary to have a member named Cur which points to "this". 2) The default constructor is better implemented as (assuming you've eliminated usage of Cur); (Toggle Plain Text) LList(): Data(new T), Prev(NULL), Next(NULL) { } LList(): Data(new T), Prev(NULL), Next(NULL) { } The reason for this guideline is that, if LList() has two members that are both dynamically allocated, then the constructor in your first form will yield a memory leak in some situations if an exception is thrown. Compare what happens with; (Toggle Plain Text) LList() { Data = new T; Data2 = new T; // a second data member is also dynamically allocated Prev(NULL); Next(NULL); } LList() { Data = new T; Data2 = new T; // a second data member is also dynamically allocated Prev(NULL); Next(NULL); } In this form, if the creation of Data2 throws an exception, the object pointed to by Data1 is leaked. However, in the alternate form, (Toggle Plain Text) LList(): Data(new T), Data2(new T), Prev(NULL), Next(NULL) { } LList(): Data(new T), Data2(new T), Prev(NULL), Next(NULL) { } the standard requires the compiler to clean up if an exception is thrown when creating either Data or Data 2. 3) Your MoveNext and MovePrev methods can be tweaked a bit. (Toggle Plain Text) template<class T> LList<T> * LList<T>::MoveNext(int Step){ LList<T> Temp = this, Temp2; for(i=0; i<Step && (Temp2 = Temp->GetNext()) != NULL; ++i){ Temp = Temp2; } return Temp; } template<class T> LList<T> LList<T>::MoveNext(int Step){ LList<T> *Temp = this, Temp2; for(i=0; i<Step && (Temp2 = Temp->GetNext()) != NULL; ++i){ Temp = Temp2; } return Temp; } 4) You might want GetData() to exist in both const and non-const versions. 5) As your class assumes that T has a default constructor, and you're only making Data point to a single instance, you may wish to simply have Data as a member of type T, rather than a pointer to T. This avoids the need to muck around with managing lifetime of Data: the compiler will do it for you implicitly,

Sep 24th, 2005, 11:10 AM	#4
Griz803 Newbie Join Date: Jul 2004 Location: Somewhere in them thar hills Posts: 23 Rep Power: 0	Thanks for taking a look, both of you. Grumpy, in reply I have a couple of questions that still remain. Item by item: 1). So, passing this explicitly to delete will work as well as passing it the Cur pointer? Ok, I beleive it. I just didn't know for sure and needed it as a kind of mental insurance policy. 2). I realize that proper error checking hasn't been implemented. That is a later deal, but thanks for the easy suggestion. 3). Yes, that is much tighter code, thanks. 4). Ok, now the question. Not to act like a three year old, but why? Having a "Duh" moment and just not getting the purpose. Explain a bit more please. 5). One of the best reasons to put my code out on the forum. You're 100% right. I let myself get involved with the pointer forest and missed a very good way to simplify my code! Thanks, have a good day! __________________ /* Bad command or filename --- go stand in the corner */

Sep 25th, 2005, 2:25 PM	#6
Griz803 Newbie Join Date: Jul 2004 Location: Somewhere in them thar hills Posts: 23 Rep Power: 0	Thanks a bunch. Now I at least know why and what parts of my books to hit again. Your answers are great ways to check what it is I think I learned. Have a great day! __________________ /* Bad command or filename --- go stand in the corner */

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > C++

Trying to Learn About Templates...