模板用于排序和未排序列表

arui69

1.00/5 (4投票s)

2005年6月2日

2分钟阅读

21936

364

排序和无序列表的模板。

引言

我相信任何编写过代码一段时间的人都会遇到需要列表的情况，无论是排序的还是无序的，用于不同类型的对象。无论如何，我确实遇到了这种情况，并且想要一种简单的方法来拥有列表，而无需为每种类型编写基本相同的代码。虽然有 vector 和 map 模板，但我发现它们的使用对我来说有些过于复杂，并且我决心编写自己的代码，到目前为止，它一直为我服务得很好。

模板定义

模板类执行简单的内存分配操作，而派生的排序类则添加了对数级排序功能。列表模板有三个成员：m_list，它是指向对象列表的指针，size 和 max。size 变量是列表中激活的位置数量，而 max 变量是分配位置的实际大小。排序列表还有另一个公共成员 bMultiple，它允许在比较方法指示它们相等的情况下拥有多个对象。

定义

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

T 代表列表的类型，F 代表传递给 Add 方法的对象类型，用于创建新的 T 对象，而 S 是 size 和 max 变量的类型。对于指针的排序列表，对象必须具有一个 int Compare(F&) 方法，对于非指针则需要重载 int 运算符 -(F&)。

方法

以下是基类 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();

示例

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();
}

备注

有三件事值得注意：

Add 和 RemoveAt 方法中的内存分配算法，可以更改为不同的算法

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;
    ...
}

排序列表中 FindHelper 方法中比较结果的 int 类型。int 类型的问题在于，在 float 或 double 类型中，如果差值小于 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; ... 
}
```
可能还有一些改进的空间。

结论

希望您能找到这段代码的用处。任何意见或建议都将不胜感激。