从零开始的扩展泛型集合
4.64/5 (9投票s)
从头开始构建一个通用集合类，而不是简单地包装 List 或 ArrayList。
引言
我决定尝试制作一个自定义的通用集合类，并开始研究通用集合类的实现，例如 List<T> 或 ICollection<T> 这样的接口。但随着研究的深入，我发现有用的信息很多，但最终，在我查看了一个又一个简单和复杂的 CollectionBase 或 ICollection<T> 的实现示例时，一个问题浮现在脑海中：它们的核心都只是在内部包装了一个 ArrayList 或 List<T>，这在我看来，违背了实现一个基础类或接口的初衷。如果你能写一个成功包装 List<T> 的类，为什么还要费力去实现 ICollection 或 IList 呢，如果你可以直接在你的类里放一个 List<T> 呢？如果我不想包装一个比我考虑的更基础的接口更高级的现有结构呢？有什么选择吗？
背景
最终，我有了自己的集合类，我认为即使在 3.0 时代它仍然很有用 - HashSet<T> 是一个快速的唯一值列表，在 Contains 检查方面可以胜过我的集合，但它依赖于唯一性且无法排序，而 List<T> 在排序方面比我的集合稍快，但快不了多少。两者都没有原生提供一个单值排序的唯一值列表。（请参阅最后的性能测试以获取实际数字。）
即使通过扩展 List<T> 来添加 Unique 函数会使其过时，我认为知道这一点仍然很有价值。我以前从未将集合分解到这个层面，并学到了一些新概念。
开始编码
我开始问的最基本的问题就是：
给定一个类 A，如何实现 A[index]？ 很快就有了使用内部数组的直接答案，但最明显的缺点是静态大小，因为我们显然需要一个动态的 Add 选项，该选项不会在每次 Add 时都重新创建数组。我立即看到的、导致我编写了过多代码的、不太明显的缺点是：它完全违背了我的意愿，即它实现了一个预定义的集合类 (Array)，即使它比 List<T> 及其类似物要简单得多。 11
我最终的答案是 **嵌套类**。嵌套类就是一个在你的类内部声明的类，在这种情况下，我声明了一个具有泛型类型属性的嵌套类，并且可以将该泛型类型值传递给嵌套类中的构造函数。在这段代码中，我们既看到了一个带有“泛型”值类型的类声明，也看到了一个承载相同 T 类型的嵌套类。请注意，我没有实现任何继承，它们直接从 System.Object 派生。
public class basicList<T>
{
//basicList constructors
//...
private class basicItem
{
private T _data;
public T Value { get { return _data; } set { _data = value; } }
public basicItem(T t) { _data = t; }
}
}
请注意，嵌套类是 private 的，但构造函数/属性是 public 的 - 如果你有一个公共嵌套类，它可以在父类外部访问，但由于它是私有的，只有父类才能访问它；但是，你的父类需要使用的方法（包括构造函数）**不能**是 private 的。
现在，我们需要一个父类 basicList 上的方法来创建 basicItem，如下所示
public class basicList<T>
{
public Add(T t) { basicItem newItem = new basicItem(t);}
//basicItemClass
//...
}
你可能在说，我们创建了一个带有数据的 basicItem 很好，但一旦离开 Add，我们如何找到它呢？
**答案：我们需要实现某种形式的索引。** 这可能是更有常识或比我更忙的人会选择实现 List 或 ArrayList 的地方，因为当你想到“我可以用什么来存储值的集合并轻松地通过索引访问？”时，它们很容易就会浮现在脑海中。但是，这个项目的一部分是 **不实现其他集合类**，部分原因是我想要直接访问数据，而不是仅仅通过另一个集合，部分原因也是我当初开始这个项目的整个目的。
那么，用一个包含 T 数据的 basicItem 对象集合，我该如何为索引跟踪它们呢？答案就是让我最终前进的动力：每个 basicItem 都需要一个指向另一个 basicItem 的引用属性，我们需要跟踪对象的数量，并且父对象需要保留一个指向其中一个对象的引用。这个引用链将使类不被垃圾回收，并提供简单的枚举实现。出于性能原因，我选择了向前或向后移动的能力，所以我需要跟踪
basicList:- 指向第一个
basicItem的引用 - 指向最后一个
basicItem的引用 - 当前项目数
basicItem:- 指向前一个
basicItem的引用 - 指向下一个
basicItem的引用
当在基础的 Add 函数中构造一个 basicItem 时，如果它不是第一个，它可以知道前一个项目，但不知道下一个，因为在基础的 Add 中，新项目被追加，后面没有东西。
新的 basicItem 构造函数和 basicList 构造函数，以及 Add 方法
public class basicList<T>
{
private basicItem _firstItem, _lastItem;
private int _count;
public basicList()
{
_firstItem = null;
_lastItem = null;
_count = 0;
}
public void Add(T t)
{
basicItem n = new basicItem(t, _lastItem);
if (_count == 0) { _firstItem = n; } //store first node
else { _lastItem.Next = n; }
//not first, put reference to previous last
_lastItem = n;
_count++;
}
private class basicItem
{
//next and previous as from a zero-based perspective
private basicItem _prev, _next;
private T _data;
//properties
public basicItem Previous { get { return _prev; } set { _prev = value; } }
public basicItem Next { get { return _next; } set { _next = value; } }
public T Value { get { return _data; } set { _data = value; } }
//constructors
public basicItem(T t) : this(t, null) { }
public basicItem(T t, basicItem prev)
{
_prev = prev;
_data = t;
}
}
}
现在我们开始有进展了！当调用 basicList.Add() 并传入一个值时，它首先调用 basicItem 构造函数，并将给定值和指向 _lastItem 的链接存储在 Previous 中。请注意，如果它是集合中的第一个项目，它会从 basicList 构造函数获得一个 null 引用，如果不是，则前一个 _lastItem 会获得一个指向新的 basicItem 的 Next 链接。默认情况下，通过 Add 添加的项目是追加的，因此创建的项目始终是 _lastItem。 _count 增加 1，如果它是第一个项目，它也会被放入 _firstItem。此系统还具有一个 **优点**，即不硬编码 basicItem 中的索引，而是通过使其相对，我们可以通过简单地更改 basicItem 的链接来任意地移动/删除/添加。
**现在来实现索引！** 有了我们现有的东西，我们知道 _firstItem 且其索引始终为 0，我们有 _lastItem 且我们知道其索引始终为 _count - 1。我们可以在这里实现两件事 - 一是泛型的 IEnumerator<T> 以支持 foreach 操作，二是 this[int index] 以允许直接访问。既然我们要实现 IEnumerator<T>，我们的父类也可以从 IENumerable<T> 继承，而无需额外成本，只需将其 IEnumerator<T> 的实现指向我们正在创建的那个即可。顺便说一句，这是 basicList 类将获得的唯一继承 - 它可能没有增加太多，但我认为最好还是加上。
新代码
public class basicList<T> : IEnumerable<T>
{
//snip unchanged basicList constructor
//and Add method and basicItem class
public IEnumerator<T> GetEnumerator()
{
basicItem current = _lastItem;
while (current != null)
{
yield return current.Value;
current = current.Previous;
}
}
IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
//IENumerable<T> implementation
public T this[int index]
{
get
{
int curIndex = 0;
basicItem curItem = _firstItem;
while(curIndex < index)
{
curItem = _firstItem.Next;
curIndex++;
}
if(curItem != null) { return curItem.Value;}
return default(T);
}
set
{
int curIndex = 0;
basicItem curItem = _firstItem;
while(curIndex < index)
{
curItem = _firstItem.Next;
curIndex++;
}
if(curItem != null) { curItem.Value = value;}
}
}
}
**我们现在拥有一个功能齐全的通用列表！** 我们可以 Add 一个项目，通过 foreach 遍历集合，或者通过遍历我们的集合（从开头或结尾，稍后详述）直接按索引获取/设置值。
扩展列表功能
好的，那么一个可以追加项目、枚举和按索引访问的列表是最基础的列表。当然，我们可以在保留零继承（除了免费的那个）并保持完全通用的同时实现一些其他功能！当然可以！
基本列表功能 - 零继承且完全通用
AddRangeAddAtRemoveAtClearContains
在本节中，我将不重写 AddAt/RemoveAt 的代码，因为我实现了一些尚未介绍的性能增强 - 但基本上，由于索引不是硬编码的，您只需重新连接链接即可。对于 RemoveAt，您获取指定索引处的 basicItem，然后将 Previous 和 Next 直接链接在一起，然后将项目设置为 null（实际删除）或者如果要在原地重新插入，则将其重新链接到所需位置。对于 AddAt，您获取前一个和后一个项目，并将它们链接到新项目，然后将新项目链接到前一个和后一个。在这两种情况下，都需要检查第一个/最后一个项目是否需要替换，并且需要更新计数。
AddRange 再简单不过了，只需获取一个 T[] 并遍历它们，对每个值调用 Add。对于 Clear，我实际上钩住了构造函数来调用它，但它将所有内容置为 null，将值重置为 0，并遍历集合移除链接，以确保我们不会有一个庞大的链条漂浮在集合不清理的深渊中。此时我们可以实现 Contains，尽管我们仅限于 Object 继承的 Equals。
public class basicList<T> : IEnumerable<T>
{
public basicList() { this.Clear(); } //moved to Clear function
public void AddRange(T[] t) { for (int i = 0; i < t.Length; i++) { Add(t[i]); } }
public bool Contains(T t)
{
foreach (T tVal in this) { if (tVal.Equals(t)) { return true; } }
return false;
}
public void Clear()
{
if (_firstItem != null)
{
basicItem curItem = _firstItem;
while (curItem.Next != null)
{
curItem = curItem.Next;
basicItem prevItem = curItem.Previous;
prevItem = null;
}
}
_firstItem = null;
_lastItem = null;
_count = 0;
}
}
这就是一个不受限制的通用 Object 派生无继承列表所能达到的极限。我们只有基本 Object 函数，而没有限制 T。此时，如果我们想要更多，我们可以子类化 basicList，或者只是使用对 T 的最小限制来获得其余想要的功能。
性能增强
我将直接进入实现排序和扩展功能的部分，但不幸的是，这相当复杂，并使用了我将要描述的。与其重写整个代码段使其有意义而不解释这个系统，不如我先解释一下。
我实现的是我称之为 **指针系统**。这是我的列表类能够与预定义的集合类竞争（甚至超越其中一些）的主要原因。我知道指针的含义，但我实际上并没有使用指针。我使用的是对象引用，但为了我自己的清晰起见，我称它们为指针，因为通过获取一个指针，你基本上就获取了它引用的对象。
回想一下，_firstNode 和 _lastNode 基本上是第一个和最后一个节点的引用，它们的位置已知为 0 和（Count - 1）。这个系统维护了更多的这些引用，除了不是固定在第一个和最后一个，它们可以在这些边界内的任何地方自由移动。必然地，这个系统很难跟踪，但它对于执行除追加项目之外的任何操作都至关重要。请记住，**在这个阶段，要获取索引[y]，我们必须从 0 开始迭代 0 -> y**。通过确定 y 更靠近结尾还是开头并从那里开始，可以获得一些性能提升，而这正是我最初的实现。但当我们需要逐个遍历集合并在节点之间来回切换时（例如排序操作所需要的）会发生什么？我告诉你 - 在小型集合中，它并不明显，但在大型集合中，它非常明显，因为要到达集合的中间，它总是必须从开头或结尾开始。
在我的实现中，我允许用户选择性地设置使用的指针数量；在大型集合中，更多的指针数量会有所帮助，尽管我所有的测试都使用了默认数量，即 4。
由于本文已经很长了，我将简要解释实现方式，您可以在源代码中看到。
- 指针存储在两个单独的数组中，一个
basicItem[] _curPointers和一个int[] _curPointerIndices。 _curPointers[]包含实际的对象引用_curPointerIndices[]对应于basicList[index]到当前节点索引- 当调用获取指针的函数时，
_getClosestPointer函数只是返回最策略性指针的索引，然后将其传递给_getNodeAt，_getNodeAt再将其传递给调用者。 - 如果没有，它会在零或结尾处创建一个，取决于哪个更靠近
_createNewPointer - 如果存在一些，但创建新的指针在零或结尾处会更近
- 如果有一个空位可以创建一个，就获取它并创建它
- 如果不是，则替换
_calcPointerWorthLeast中战略性最差的指针（基于与其他指针以及开头/结尾的距离）。 - 函数然后获取该索引，并只使用
_getClosestPointer，而获取对象引用的函数使用_getNodeAt。- 函数跟踪它们从指针获取的工作对象及其索引，或者只跟踪索引，具体取决于函数。
- 它们在需要时更新指针/索引，无论是通过直接输入到
_curPointers/_curPointerIndices还是使用_updatePointer。 - 如果在使用的过程中添加/删除了任何节点，受影响的指针索引会相应地使用
_movePointers进行更新。 - 指针支持反向查找，给定一个
basicItem，_getPointerIndex可以返回指针的索引以进行更新。
增强功能
既然我已经稍微解释了一下，让我们继续进行最后一部分，设置 Sort 和重构 Contains，并启用 Add 上的自动排序。首先，要进行任何除了基本 Object 派生的 Equals(obj) 之外的比较，我们需要最终对我们的 T 添加一些限制，即要求它实现 IComparable<T>，通过将 where T:Comparable<T> 添加到类名。我选择增强当前列表，而不是在此停止类并继承它，然后将请求的继承添加到 T，因为 IComparable<T> 非常容易实现。它只有一个方法 - CompareTo，给定 t1.CompareTo(obj t2)，如果 t1 < t2 则返回 -1，如果 t1 = t2 则返回 0，如果 t1 > t2 则返回 1。我通常会在自定义类中通过重定向到特定类型的比较来实现，并避免普通的 Object 技巧。
既然我们可以保证 T 是 IComparable，我们就可以更新 Contains 并实现排序。一个基本的排序例程会很好，但既然是我写的，它就不那么 basic 了。但在那之前，这是更新后的 Contains 方法；回想一下，在此之前，我们只能使用 Object.Equals；现在要快得多。
public bool Contains(T t)
{
//new and improved
foreach (T tVal in this) { if (tVal.CompareTo(t) == 0) { return true; } }
return false;
}
它现在使用 CompareTo == 0。您还可以做的另一件事是首先快速比较 Object.getHashCode，因为它比 CompareTo 快（仍然比 Equals 快）。但请记住，getHashCode 不是一个万无一失的比较运算符，如果哈希码相等，并不意味着两个对象相等，因此需要第二次检查 CompareTo。我用整数测试过，它显著加快了值检查，但当我使用字符串时，它却减慢了速度 - 我猜想哈希码相等的可能性更大，或者计算字符串的哈希码需要更长时间，而且由于这是一个旨在尽量减少限制的通用 List，我不想设置一个特殊的字符串处理程序、一个特殊的整数处理程序等，所以将其改回最可靠的比较。如果我打算用它处理字符串，我只会覆盖一个新字符串目标类中继承 basicList 的比较。
**开始排序！** 本质上，排序只依赖于几件事 - 你有一个可靠的比较两个值的方法，我们现在有了 CompareTo，并且你在切换时可以跟踪你的位置。后者通过我上面描述的指针系统要复杂得多，但对于排序操作来说非常令人印象深刻。
我这里使用的排序是几个部分的组合。我将发布实际的排序处理代码，尽管其中大部分代码可能难以理解，因为我们没有深入介绍指针系统，并且排序函数本身会调用另一个函数，然后又调用另一个函数。尽管如此，这是当前的 _handleSortCall（公共的 Sort 会查看 _autosort，如果已自动排序，则忽略该调用）。
private void _handleSortCall()
{
//private method allows public sort to decide if
//it wants to actually sort or not and permits
//autosort property handler to bypass
basicItem nEnd = _firstItem, nStart = _firstItem;
int posEnd = 0; //start is always 0
//working index so we don't have to enumerate
//every one in the sort op function to place it
int workingIndex = 0;
while (nEnd.Next != null)
{//start at the 2nd node and work until there are no more nodes
basicItem thisNode = nEnd.Next;
workingIndex++;
//first check to see if it even needs to be moved
//since we are moving forward, we just need
//to make sure the previous is worth less
if (thisNode.Value.CompareTo(thisNode.Previous.Value) < 0)
{
//remove before looking so we don't find the same value
_removeNodeAtIndex(workingIndex, ref thisNode);
int newIndex = _findProperIndexByValue(thisNode.Value, 0);
_addNodeAtIndex(newIndex, ref thisNode);
posEnd++;
workingIndex++;
}
else
{//sort not necessary
nEnd = thisNode;
posEnd++;
}
}
}
由于这是基本的排序调用，因此没有传递任何参数。下一个更具体的函数是 _findProperIndexByValue，它给定一个值，找出下一个值更大的第一个索引，基本上是一个升序查找器。为了做到这一点，它创建最多 10 个区域，一次检查一个起始值，然后递归，缩小区域，重复直到区域少于 20 个可能性，此时，它调用另一个函数 _findFirstBiggerValueIndex，您大概可以猜到它的功能。函数 _removeNodeAtIndex 和 _addNodeAtIndex 正如您所想的那样，是 AddAt 和 RemoveAt 函数背后的主力，并且对于排序操作至关重要，因为我们基本上是从一个位置移除一个节点并将其放到另一个位置。
由于我们从头开始向前移动，因此前一个工作节点后面的任何值都保证等于或小于当前节点，这意味着对于我们向前移动的每个节点，我们只需检查值是否大于上一个值，如果大于，我们可以继续移动，因为任何差距将由后面的节点回移来覆盖。
结语
如果您读到这里，我为您感到非常自豪。这比我预期的要长得多，我甚至开始缩短它，一旦我们进入了复杂的部分。我确实有一丝希望，尽管有明显的替代方案，但有人会发现这很有用。从零开始构建一个几乎能与已建立的王者匹敌的工具，有一种特殊的自豪感。如果没有，这对我们双方来说都是一次很棒的脑力锻炼。
性能测试！
我对我的小实验与大名鼎鼎的类相比如何感到好奇，所以我进行了一个使用 500K int 集合的实验。我还进行了一个 10K string 集合的实验，但结果在各个方面都非常相似，所以我直到对这个结果满意才搁置它。关于字符串，我只想说的是，我的未排序列表的 Add 时间与所有其他列表完全相同，而它的排序时间与 List<string> 和 ArrayList 完全相同，所以我就不隐藏差的结果了。
用于性能测试的代码（在代码中，加上两个简短的验证，确保最后 50 个和前 50 个是正确的）
for (int x = 500000; x > 0; x--) { list.Add(x); }
list.Sort();
for (int x = 500000; x > 0; x--) { if (!list.Contains(x)) { list.Add(x, null); } }
我为其中每个操作包装了一个小计时器函数，以提供经过的毫秒数，以下是结果
| Collection Class | Add Test | Sort Test | Contains Test |
|---|---|---|---|
basicList !_autoSort |
141 ms. | 203 ms. | 在 10 秒内停止 - 完成 8022 次。估计需要 623 次。 |
basicList _autoSort |
453 ms. | 0 ms. | 在 10 秒内停止 - 完成 11648 次。估计需要 429 次。 |
ArrayList |
109 ms. | 718 ms. | 在 10 秒内停止 - 完成 652 次。估计需要 7692 次。 |
List<int> |
31 ms. | 78 ms. | 在 10 秒内停止 - 完成 805 次。估计需要 6250 次。 |
Hashset |
125 ms. | 不适用 | 765 ms. |
Hashtable(int, null) |
281 ms. | 不适用 | 968 ms. |
SortedList<int, object> added (int, null) |
约 1 分钟添加了 100k | 不适用 | 不适用 |
Dictionary<int, object> added (int, null) |
156 ms. | 不适用 | 765 ms. |
SortedDictionary<int, object> added (int, null) |
703 ms. | 0 ms. | 781 ms. |
我确实使用了 3.0 进行测试，正如您从 HashSet 看到的，但将程序集降级到了 2.0，因为它不需要更多。有趣的是，SortedList 甚至无法开始。未排序列表在 Add 和 Sort 方面都输给了通用 List，但正如您所见，它处理了 10 倍多的 Contains，并且排序时间远好于 ArrayList。autoSorted basicList 在 10 秒内处理了 50% 更多的 Contains，但对我来说还不足以实现一个唯一的函数。如果我能将其降低到 Dictionary 的排序时间，那么我终于拥有了一个完全可定制的、具有竞争力的唯一值自动排序 Set，它与预定义的 Set 处于同等水平。在我看来，非唯一的未排序和已排序列表与其他列表处于相当的水平。但我有偏见！
未来计划
目前（截至最初撰写时），类中还有一个唯一的属性/公共属性/处理方法，它是注释掉的。您可以实现它，这只需要在 Add/AddAt/AddRange 中添加另一个条件来处理唯一值。我没有实现它的原因不是因为难度，而是因为我对 Contains 检查的性能不满意。由于 Unique 会在每次 Add 时命中 Contains 检查，因此满足我的要求是完全必要的。但当然，我是在 500K 集合上进行性能测试的，而大多数应用程序可能都没问题。
结论
希望您觉得这个练习很有趣。但即使是一小部分，也足以让我对编写它感到满意！
请随时告诉我您发现的错误，我进行了相当彻底的测试，但我确信我没有发现所有错误。
作为注释，如果您习惯于每个函数上的常规 ///文档，我表示歉意 - 我只在我认为必要的地方进行了注释，我不喜欢翻阅数百万页的大部分注释。但是，如果这能获得一些下载，并且有此要求，我可以更新它。我还没有看到是否有人对下载实际代码感兴趣，我感兴趣的是这个概念。
历史
- 2010/3/8 - 发布此内容！