Templates for sorted and unsorted lists

arui69

1.00/5 (4 votes)

Jun 2, 2005

2 min read

21864

364

Templates for sorted and unsorted lists.

Introduction

I believe anyone who programmed for a while would have encountered the need for lists, sorted or unsorted, for different types of objects. Anyway, I did, and I wanted an easy way to have lists without the need of writing basically the same code for each type. Although there are the vector and map templates, I found their use a bit too demanding for me, and I had set my mind to write my own code, which so far served me very well.

Template's Definition

The template class does the simple act of taking care of memory allocation, while the derived sorted one adds logarithmic sorting functionality as well. The list template has three members. m_list which is a pointer to the list of objects, size and max. The size variable is the number of active places in the list, and the max variable is the actual size of allocated places in the list. Sorted lists have another public member bMultiple which allows them to have multiple objects in case the comparison method indicates they are equal.

Definition:

template <class T, class F=T, class S=Int16> 
class AIList {

T stands for the list's type, F for the type of object passed for the Add method for creating new T objects, and S is the type for the size and max variables. In the sorted list for pointers, the object has to have an int Compare(F&) method, and for non pointers an overloaded int operator -(F&).

Methods

Here are the methods of the base class AIList:

// Allocation functions 
void Attach (AIList <T, F, S>& p) 
    { RemoveAll(true); size = p.GetSize(); 
    max = p.GetMax(); m_list = p.Detach(); }
void Attach (T* p, S n)
    { if (m_list) delete [] m_list; size = max = n; m_list = p; }
void SetMinSize (S n) { if (max < n) GrowBy (n - max); }
void GrowBy (S n);
void AddActive (S n) 
    { if (size + n > max) { GrowBy (size + n - max); size = max; } 
      else size +=n; }
void Add (F& obj, S nPos = -1);
void Add (AIList <T, F, S>& obj, S nPos);
AIList <T, F, S>& operator += (AIList <T, F, S>& p);
AIList <T, F, S>& operator = (AIList <T, F, S>& p) 
    { RemoveAll(); return *this += p; }
// Dellocation functions 
T* Detach () { T* tmp = m_list; size = max = 0; m_list = 0; return tmp; } 
void RemoveAt (S pos, T* obj = 0);
void RemoveAll (bool bReset = true) 
    { if (max && bReset) 
      { delete []m_list; m_list = 0; max = 0; } 
      size = 0; }
void Remove (T& p, T* obj = 0) { RemoveAt (Find (p), obj); }
void RemoveLast (T* obj = 0) { RemoveAt (size-1, obj); }
// for list of pointers only 
void FreeList (bool bReset = true) 
    { for (S i=size ; i-- ; ) 
      { if (m_list[i]) delete m_list[i]; } 
      RemoveAll(bReset); }
 
// Access functions 
const T& GetLast() const { ASSERT (size); return m_list[size-1]; }
const T& operator [] (S pos) const 
    { ASSERT (!pos || pos < size); return m_list[pos]; }
T& GetLast() { ASSERT (size); return m_list[size-1]; }
T& operator [] (S pos) { ASSERT (!pos || pos < size); return m_list[pos]; }
S Find (T& obj, S nStart = 0) const { ... }
bool operator == (AIList <T, F, S>& p) const;
void FitToSize();

Example

class Word {
    char* m_desc;
public:
    Word() { m_desc = 0; }
    Word(char* p) { m_desc = strdup(p); }
    ~Word() { if (m_desc) delete m_desc; }
    int Compare(char* p) { return stricmp (m_desc, p); }
    const char* GetDesc() { return m_desc; }
};
void main() {
   AISortedList<Word, char*> words; 
   char* pp = "foo";
   words.Add (pp);
   ...
   // since it's a pointers list
   words.FreeList();
}

Remarks

Three things that are worth noting are:

The algorithm for memory allocation in the Add and RemoveAt methods, which might be changed to a different one:

template<class T, class F, class S>
void AIList<T, F, S>::Add (F& obj, S nPos) {
    ...
    if (size == max) {
    ==>    max += max/2 + 1;
        tmp = new T [max];
        for (i=0 ; i<nPos ; i++) tmp[i] = m_list[i];
    } else tmp = m_list;
    ...
}
template<class T, class F, class S>
void AIList<T, F, S>::RemoveAt (S pos, T* obj) {
    ...
    ==> if (size < max / 2) {
    ==>    tmp = new T [size];
        for (i=0 ; i<pos ; i++) tmp[i] = m_list[i];
        max = size;
    } else tmp = m_list;
    ...
}

The int type for the comparison results in the FindHelper method for the sorted lists. The problem with the int type is that in float or double types the comparison is of course not valid if the difference is less than 1.
```
template <class T, class F, class S>
bool AISortedList2<T, F, S>::FindHelper (F& p, S& pos) const {
    int r; ... 
    r = m_list[pos] - p; ... 
}
```
There are probably some places for improvement.

Conclusion

I hope you find good use for this code. Any remarks or suggestions are more than welcome.