MC++ 中的链表集合类

• 下载源代码文件 - 18 Kb
• 下载演示项目 - 44 Kb

引言

如果你检查 ArrayList 类的功能，你会发现它非常荒谬。 当数组达到最大容量时，它会创建一个容量翻倍的新数组，将旧数组中的项目复制到新数组中，然后丢弃旧数组。 复杂而混乱。

每个 C/C++ 程序员都知道，使结构“真正”动态的唯一方法是使用链表。 我在托管 C++ 中创建了一个类，它就是这样做的。 此外，我还包含了一个 TypedListBase 抽象类，你可以继承它来创建强类型集合。 所有这些都被放入一个 .NET dll 中，并且我有一个用 C# 编写的程序，我用它来测试它。

这些类实际上并没有做比实现 IList、ICollection、 IEnumerable 和 ICloneable 更多的事情。 因此，就使用它的程序员而言，它的行为与 ArrayList 完全相同。 我在这里不深入讨论这些接口的方法和属性的细节，但它们非常简单明了，并且 .NET Framework 参考文档对它们进行了很好的解释。

实现链表

LinkedList 类维护一个 LinkedListNode 结构的链表，如下所示

__nogc struct LinkedListNode
{
    LinkedListNode __nogc* pNext;
    LinkedListNode __nogc* pPrev;
    gcroot<object*> item; // #include <vcclr.h> in StdAfx.h  
                          // makes this template available.
};

LinkedListNode::item 存储对象。 需要 gcroot 模板才能在非托管 struct/class 中保存托管对象。

除了构造函数、析构函数和接口实现之外，链表类还包括以下项目

public __gc __sealed class LinkedList : public IList, 
    public IEnumerable, public ICollection, public ICloneable
{
// Implementation
private:
    LinkedListNode __nogc* m_pHead;
    // Future versions will support reverse enumeration, 
    // like the STL classes.
    // Therefore, we need to store the tail as well.
    LinkedListNode __nogc* m_pTail;
    int m_count;
    // Used by the enumerator to check 
    // whether the list is modified after the
    // enumerator has been created.
    int m_version;	

    LinkedListNode* GetNodeAt(int index);
public:
    int GetVersion();

. . .
. . .

实现枚举器

LinkedList::GetEnumerator 的代码是

IEnumerator* LinkedList::GetEnumerator()
{
    return new LinkedListEnumerator(this, m_pHead);
}

此类需要一个指向它正在处理的列表的指针和一个指向头部的指针。 类声明如下所示

private  __gc __sealed class LinkedListEnumerator : public IEnumerator
{
// Implementation
private:
    LinkedList* m_list;
    LinkedListNode* m_pNode;
    LinkedListNode* m_pHead;
    int m_version;
public:
    LinkedListEnumerator(LinkedList* list, LinkedListNode* pHead);
    // Overrides of IEnumerator
public:
    __property Object* get_Current();
    bool MoveNext();
    void Reset();
};

构造函数调用 list->GetVersion() 并将返回值存储在 m_version 中。 该数字代表创建枚举器时列表的状态。 当列表被修改（通过调用 Add、Remove、Clear 等）时，版本号会递增。 IEnumerator 函数检查以确保存储的版本和当前版本相同

if (m_version != m_list->GetVersion())
    throw new InvalidOperationException(
        S"The list was modified after the enumerator was created.");

如果在创建枚举器后修改了列表，则 LinkedListEnumerator::m_pNode 和 m_pHead 有可能无效，因此会抛出异常。 这确实有点牵强，但如果列表被修改超过 40 亿次（我认为这是 int 的容量），就会发生溢出。 好吧，这就是 Microsoft 在 ArrayList 中实现此行为的方式。

使用程序测试 DLL

查看我包含的程序。 它有一个 GUI，允许你逐个将字符串添加到列表中，也可以添加 500 个随机字符串。 它测试了所有函数，并允许你使用多个线程枚举列表。 尝试在某些线程正在枚举时添加项目。 它们会抛出 InvalidOperationException，但在添加项目后创建的枚举器将“平静地”运行。