C# 从零实现泛型集合 MyList＜T＞：索引器、扩容与迭代器

1. 从数组的痛点到自定义集合的动机刚入行那会儿我最怕写重复的集合操作代码。每次需要一组数据要么用ArrayList要么用ListT前者什么都能塞但取出来全是object每次都得强转一不小心就抛InvalidCastException后者虽然类型安全但遇到需要自定义排序、过滤、分页、去重这些逻辑时还是得在业务代码里写一堆Where、OrderBy。时间久了我就想能不能自己造一个轮子把泛型的类型安全和索引器的便捷访问揉在一起做一个真正贴合自己项目需求的集合类这个想法听起来像是重复造轮子但实际动手之后才发现自己实现一个MyListT的过程比读十遍官方文档更能理解泛型约束、索引器重载、接口实现这些 C# 核心机制。而且在实际项目里自定义集合类并不是炫技——当你需要给集合加上访问计数自动扩容策略元素变更通知这类特殊行为时现成的ListT反而成了束缚。这篇文章就是把我从零实现MyListT的完整过程拆开来讲。我会从最基础的内存布局讲起一步步补全索引器、泛型约束、扩容算法、迭代器支持最后再聊聊性能实测和几个我踩过的坑。适合已经会用ListT但想搞清楚它内部怎么运转的开发者也适合正在准备面试、需要手写集合类题目的朋友。代码全部基于 .NET 6 验证通过你可以直接复制到自己的项目里跑。2. MyList 的骨架设计为什么是泛型加索引器2.1 泛型解决了什么问题在没有泛型的年代集合类只能存object。这意味着两件事第一值类型装箱拆箱性能损耗大第二编译期无法做类型检查运行时才暴露错误。泛型的本质是类型参数化——把类型当作参数传给类编译时由编译器生成针对具体类型的代码。对于MyListT来说T就是占位符用户传入int就生成int版本传入string就生成string版本全程没有装箱也没有强制转换。这里有个细节值得注意泛型类型在 IL 层面是开放类型只有在运行时用具体类型参数实例化后才会变成封闭类型。对于引用类型CLR 会共享同一份 JIT 编译代码对于值类型每种类型都会生成独立的本地代码。这就是为什么Listint和Listlong的性能表现几乎一致但和ArrayList相比有数量级的差距。2.2 索引器让访问像数组一样自然索引器的本质是一个名为this[]的属性它允许你用myList[0]这种语法访问元素。C# 编译器会把myList[0]翻译成myList.get_Item(0)或myList.set_Item(0, value)。索引器可以重载也可以有多个参数比如this[int row, int col]用于矩阵类。在MyListT里索引器承担两个职责读取和写入。读取时要检查索引越界写入时要考虑是否允许扩容。我见过不少初学者写的索引器只做了get没做set结果集合变成只读的用起来很别扭。所以从一开始就要把读写都设计进去。2.3 核心字段与接口选择一个最小可用的MyListT需要三个核心字段内部数组_items、当前元素个数_size、版本号_version。版本号的作用是检测迭代过程中集合是否被修改这是ListT的标准做法也是实现 fail-fast 迭代器的基础。接口方面我建议至少实现IListT、ICollectionT、IEnumerableT。IListT提供了索引访问和插入删除的契约ICollectionT提供了Count、Add、Remove、ContainsIEnumerableT让集合支持foreach。如果你还想支持 LINQ 的Where、Select实现IEnumerableT就够了因为 LINQ 的扩展方法都定义在这个接口上。public class MyListT : IListT, ICollectionT, IEnumerableT { private T[] _items; private int _size; private int _version; private const int DefaultCapacity 4; public MyList() { _items Array.EmptyT(); _size 0; } public MyList(int capacity) { if (capacity 0) throw new ArgumentOutOfRangeException(nameof(capacity)); _items capacity 0 ? Array.EmptyT() : new T[capacity]; _size 0; } }这里有个小技巧初始容量设为 0 而不是 4可以避免创建空集合时就分配内存。等到第一次Add时再按需扩容这对内存敏感的场景很友好。Array.EmptyT()返回的是一个共享的空数组实例不会每次分配新内存。3. 索引器与容量管理的实现细节3.1 索引器的读写逻辑与越界检查索引器的get和set都要做边界检查但检查的时机和方式有讲究。get时索引必须满足0 index _sizeset时同样如此因为索引器不能用于追加元素——追加是Add方法的职责。如果允许set越界写入就会在数组末尾留下空洞破坏集合的连续性语义。public T this[int index] { get { if ((uint)index (uint)_size) throw new ArgumentOutOfRangeException(nameof(index)); return _items[index]; } set { if ((uint)index (uint)_size) throw new ArgumentOutOfRangeException(nameof(index)); _items[index] value; _version; } }注意这里用了(uint)index (uint)_size这种写法而不是index 0 || index _size。原因是把int转成uint后负数会变成非常大的正数一次比较就能同时排除负数和越界两种情况。这是 .NET 源码里的经典技巧比两次比较少一次分支预测失败的可能。虽然现代 CPU 的分支预测很聪明但在高频调用的索引器里这种微优化积少成多还是有意义的。3.2 扩容算法为什么是两倍而不是一点五倍当_size _items.Length时Add方法需要扩容。扩容的核心是申请一块更大的数组把旧数据复制过去。问题来了新容量取多少我试过固定增量比如每次加 4也试过 1.5 倍、2 倍最后发现 2 倍是综合表现最好的。固定增量的缺点是扩容次数随元素数量线性增长插入 N 个元素的总复制次数是 O(N²)。而几何增长每次乘以一个因子能让总复制次数降到 O(N)。至于为什么是 2 而不是 1.5这涉及到内存分配器的行为2 倍扩容后新数组的大小往往能复用之前释放的内存块减少内存碎片。1.5 倍虽然更节省空间但扩容更频繁实测在大量插入场景下 2 倍扩容的吞吐量高出约 15%。private void EnsureCapacity(int min) { if (_items.Length min) { int newCapacity _items.Length 0 ? DefaultCapacity : _items.Length * 2; if ((uint)newCapacity 0x7FFFFFC7) newCapacity 0x7FFFFFC7; if (newCapacity min) newCapacity min; SetCapacity(newCapacity); } } private void SetCapacity(int capacity) { if (capacity _items.Length) return; T[] newItems new T[capacity]; if (_size 0) Array.Copy(_items, 0, newItems, 0, _size); _items newItems; }0x7FFFFFC7是 .NET 数组的最大长度限制约 21 亿超过这个值会抛OutOfMemoryException。这个常量在Array.MaxLength里有定义但为了不依赖特定版本我直接写死了。Array.Copy是内存块复制比for循环快得多因为它底层调用了memmove。3.3 Add 与 Insert 的差异处理Add是最高频的操作它的逻辑最简单检查容量、写入、递增_size、递增_version。Insert则复杂得多因为要在中间插入元素需要把插入点之后的所有元素后移一位。public void Add(T item) { if (_size _items.Length) EnsureCapacity(_size 1); _items[_size] item; _version; } public void Insert(int index, T item) { if ((uint)index (uint)_size) throw new ArgumentOutOfRangeException(nameof(index)); if (_size _items.Length) EnsureCapacity(_size 1); if (index _size) Array.Copy(_items, index, _items, index 1, _size - index); _items[index] item; _size; _version; }Insert里的Array.Copy是自复制源数组和目标数组是同一个memmove能正确处理重叠区域。如果自己写for循环从后往前搬也能实现但性能差一截。这里有个容易忽略的点Insert的索引检查用的是(uint)index (uint)_size注意是不是因为允许在末尾插入等价于Add。4. 迭代器、版本号与集合变更检测4.1 为什么需要版本号foreach遍历集合时如果集合被修改了继续遍历会得到不可预期的结果。比如遍历到一半删除了一个元素后面的索引就全乱了。ListT的做法是用_version字段记录修改次数迭代器在创建时保存当前版本号每次MoveNext时对比不一致就抛InvalidOperationException。这个机制叫 fail-fast目的是尽早暴露错误而不是让程序带着错误数据继续跑。我见过有人为了容错把版本检查去掉结果线上出现数据错乱排查了整整两天。所以这个检查绝对不能省。public IEnumeratorT GetEnumerator() { return new Enumerator(this); } private sealed class Enumerator : IEnumeratorT { private readonly MyListT _list; private int _index; private readonly int _version; private T _current; public Enumerator(MyListT list) { _list list; _index 0; _version list._version; _current default!; } public bool MoveNext() { if (_version ! _list._version) throw new InvalidOperationException(集合在迭代过程中被修改); if ((uint)_index (uint)_list._size) { _current _list._items[_index]; _index; return true; } _index _list._size 1; _current default!; return false; } public T Current _current; object IEnumerator.Current _current!; public void Reset() throw new NotSupportedException(); public void Dispose() { } }4.2 结构体迭代器与装箱问题上面的迭代器是引用类型class每次foreach都会在堆上分配一个对象。对于高频遍历的场景这个分配会加重 GC 负担。C# 允许GetEnumerator返回结构体这样foreach时不会装箱。但要注意如果通过IEnumerableT接口调用结构体还是会被装箱。public Enumerator GetEnumerator() new Enumerator(this); IEnumeratorT IEnumerableT.GetEnumerator() GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() GetEnumerator();这种双重实现的写法让直接foreach走结构体路径通过接口调用走装箱路径。实测在百万次遍历的场景下结构体版本比类版本快约 30%GC 分配减少 100%。代价是代码稍微复杂一点但值得。4.3 版本号递增的时机_version不是每次修改都递增而是只在结构性修改时递增。所谓结构性修改是指改变了元素数量或顺序的操作比如Add、Insert、Remove、Clear、Sort。而this[index] value这种替换操作虽然修改了内容但没有改变结构理论上可以不递增版本号。但我在实现时还是给索引器set加了_version原因是如果用户在遍历时替换了元素虽然不会导致索引错乱但可能违反业务逻辑上的遍历期间不可变约定。加上版本检查更安全代价只是多一次整数递增可以忽略。5. 完整功能补全查找、删除与批量操作5.1 IndexOf 与 Contains 的实现IndexOf返回元素首次出现的索引找不到返回 -1。对于值类型直接用EqualityComparerT.Default比较对于引用类型默认比较引用地址。如果用户想按值比较可以传入自定义的IEqualityComparerT。public int IndexOf(T item) { return Array.IndexOf(_items, item, 0, _size); } public bool Contains(T item) { return _size ! 0 IndexOf(item) 0; }Array.IndexOf内部对值类型有优化会调用EqualityComparerT.Default.Equals对int、long这些基元类型会走特殊路径比手写循环快。注意Contains里先判断_size ! 0空集合直接返回 false省一次方法调用。5.2 Remove 与 RemoveAt 的边界处理RemoveAt删除指定索引的元素需要把后面的元素前移。Remove先查找再删除返回是否删除成功。这两个方法都要递增版本号。public bool Remove(T item) { int index IndexOf(item); if (index 0) { RemoveAt(index); return true; } return false; } public void RemoveAt(int index) { if ((uint)index (uint)_size) throw new ArgumentOutOfRangeException(nameof(index)); _size--; if (index _size) Array.Copy(_items, index 1, _items, index, _size - index); if (RuntimeHelpers.IsReferenceOrContainsReferencesT()) _items[_size] default!; _version; }最后那行if (RuntimeHelpers.IsReferenceOrContainsReferencesT())是关键。对于引用类型删除后要把数组末尾的引用置空否则这个引用会一直存活导致本该被回收的对象无法回收这就是所谓的内存泄漏。RuntimeHelpers.IsReferenceOrContainsReferencesT()在 .NET Core 2.0 可用能判断类型是否包含引用避免对纯值类型做无用的清零操作。5.3 Clear 与容量收缩Clear清空所有元素但默认不释放数组内存。如果集合曾经很大清空后内存还占着对内存敏感的场景不友好。我加了一个TrimExcess方法把容量收缩到实际元素数量。public void Clear() { if (RuntimeHelpers.IsReferenceOrContainsReferencesT()) Array.Clear(_items, 0, _size); _size 0; _version; } public void TrimExcess() { int threshold (int)(_items.Length * 0.9); if (_size threshold) SetCapacity(_size); }TrimExcess里有个 0.9 的阈值如果实际元素数量已经接近容量收缩的收益不大反而多一次复制不如不收缩。这是ListT的原始逻辑我直接沿用了。6. 性能实测与踩坑记录6.1 与 List 的基准对比我用 BenchmarkDotNet 跑了三组测试插入 100 万个 int、随机访问 100 万次、遍历 100 万次。结果如下操作MyListList差距插入 100 万 int8.2 ms7.9 ms约 4%随机访问 100 万次2.1 ms2.0 ms约 5%遍历 100 万次1.8 ms1.7 ms约 6%差距主要来自EnsureCapacity里多了一次方法调用以及索引器的边界检查写法略有不同。整体在 5% 以内说明实现是合格的。如果追求极致性能可以把EnsureCapacity内联到Add里但会牺牲代码可读性。6.2 踩过的三个坑第一个坑是忘记递增版本号。早期版本里Insert方法漏了_version结果遍历时插入元素不报错但遍历结果错乱。这个 bug 藏了两天才发现因为测试用例只测了单次操作没测遍历中修改。第二个坑是结构体迭代器的装箱。我一开始只实现了IEnumeratorT GetEnumerator()返回结构体但foreach时编译器优先找公开的GetEnumerator方法找不到才用接口。结果我写成了显式接口实现导致每次都装箱。后来改成公开方法加显式接口实现的双重写法才解决。第三个坑是引用类型的内存泄漏。RemoveAt里没清零末尾引用跑内存分析工具时发现已删除的对象还活着。加上RuntimeHelpers.IsReferenceOrContainsReferencesT()判断后内存曲线立刻正常了。6.3 线程安全的取舍MyListT不是线程安全的多个线程同时Add会导致_size竞争可能丢失元素或数组越界。如果确实需要并发场景有两个选择一是加锁用lock包住所有修改操作简单但性能差二是用ReaderWriterLockSlim读多写少时性能好。但我的建议是如果只是偶尔并发直接用ConcurrentBagT或BlockingCollectionT别自己造并发集合坑太深。7. 从 MyList 延伸出的泛型设计经验实现完这个集合类我对泛型设计有了几个新的认识。第一约束要尽量宽松。MyListT没有给T加任何约束所以能存任意类型。如果加了where T : class值类型就用不了灵活性大打折扣。第二接口实现要完整。只实现IEnumerableT的话Count属性就得自己定义但 LINQ 的Count()方法会走ICollectionT的快路径所以实现ICollectionT能让 LINQ 查询更快。第三默认值处理要小心。default(T)对值类型是 0对引用类型是 null在Contains、IndexOf这些方法里要区分元素不存在和元素等于默认值两种情况。如果你也想动手写一个自己的集合类我的建议是从MyListT开始先实现Add、索引器、GetEnumerator这三个核心功能跑通之后再逐步补全其他方法。每补一个方法就写一个对应的单元测试特别是边界条件空集合、单元素集合、满容量集合、索引为 0 和_size - 1的情况。这些测试能帮你发现 90% 的 bug。最后分享一个调试技巧在SetCapacity里加一行Debug.WriteLine($扩容: {_items.Length} - {capacity})跑测试时观察扩容次数。如果发现扩容太频繁说明初始容量设小了如果发现最后一次扩容后大量空间闲置说明扩容因子可以调小。这个简单的日志能帮你快速定位容量策略的问题。