集合具有非常快速的迭代和良好的添加和移除速度

我正在追踪一个可以快速迭代的集合。 我还会定期添加项目和删除（特定）项目，因此理想情况下这些操作也会很快。

我正在开发xbox，因此仅限于紧凑框架（或多或少）。 将垃圾和对象分配保持在最低限度非常重要，因此我可以为我的对象预先分配空间的任何事情都会很棒。

我将在集合中存储uint （但如果需要可以是int ）。 一般的解决方案会很好，因为我相信我将来会有需求。

一个.net集合将是理想的，没有一个轻量级和开源的东西会很棒。

是否有适合我需求的collections课程？ 如果没有，我将如何创建一个？

---

为了详细说明，它们是对象id，类应该处理每个帧。 它们通常按升序添加，有间隙。 没有上限。 任何可以删除，这将留下空白。
迭代顺序并不完全重要，但如果顺序一致，它将非常有用（特别是对于调试）。

Answer 1

我有两个建议要尝试：

首先，如何使用Reflector或ILSpy查看Generic List ？ 我假设实现不在CF中，或者您可以使用它。 Generic List是数组支持的，并且使用从4长度数组开始的加倍算法，每次调用.Add都会导致它加倍并将Array.Copy执行到新数组中。 除非您明确将Capacity设置为零，否则不会resize，因此请从内存的角度提防。 添加是一回事，但每次删除都会导致在删除索引后复制和左移数组。

第二个建议就是这个 – 关于创建一个自定义类，它包装一个整数数组来处理它，它使用类似的双重算法（或四倍）到Generic List （处理resize），但从大小为256开始。你可以根据需要随意添加对象整数id，并且它不会经常加倍。 您还可以通过将（int）-1或uint.MaxValue指定为“空索引”来模拟删除，这意味着删除时不会有Array.Copy。 然后，每帧应用某种快速排序，以在绘制之前对对象索引数组进行排序。 如果按升序排序，则所有-1将出现在开头（或结尾处的uint.MaxValues），可以忽略。 您可以通过在单独的线程上resize并删除前面的-1来定期“收集”索引数组（注意 – 使用锁定;）

你怎么看？ 只是认为你会为每个帧一次性地计算一次计算以进行快速排序（对于每个Remove和一些Adds（昂贵），xbox与内存分配/收集并不昂贵）。

UPDATE – BlockArray – List 其中T是固定大小的数组

对此进一步评论。 我最近试验了动态大小的列表最有效的数据结构，并通过实验发现了数组块 – 一个由List of T []支持的类，其中每个T []是一个固定大小的块数组，例如512,4096,8192作为普通List 的几个优点。

我发现List 中的Add（）（其中大小未知）的实现远远优于List 的Add（），特别是当总大小变大时。 这是由于List 的双倍算法，它要求新的数组大小为旧的2x，而memcpy是超过大小时的旧数组。

迭代速度类似。 对于小块大小（512），预分配（预定义容量）比List 慢得多，但对于大块大小（8192）仅略慢。 删除是有问题的，因为需要复制/左移多个块。

有趣的是在List （块列表）中，您可以缓存/池化块。 如果足够小，T []的块适合小对象堆（有利于压缩，更快的分配），可能适合L2缓存并且可以预先分配和汇集多个块

Answer 2

如何使用Mono的HashSet ？

https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs

它是在MIT X11下获得许可的，这是一个许可许可。

---

迭代顺序可能是一个问题，具体取决于T如何实现GetHashCode ，但在使用uint时这应该不是问题。 另一方面， GetHashCode的默认实现在不同的实例上返回不同的值，这可能导致不同的迭代顺序。

迭代顺序可能还取决于添加的订单项。 即，如果项目以不同的顺序添加，则包含相同项目的两个集合可能以不同的顺序迭代。

还有一个SortedSet集合，但我不知道它具有什么性能特征。

Answer 3

自定义类SparseList 怎么样：

• 允许您通过将缺失值设置为null （或者对于SparseValueList，一个特殊值，如-1（如ABT博士的解决方案），0（默认（T））或int.MinValue或uint.MaxValue， ）和
• 然后维护已删除索引的列表 （Stack ）。 然后，当您需要添加到列表时，它会从堆栈中弹出已删除的索引并在其中添加值。 （对于multithreading，也许ConcurrentQueue 可能是另一个想法。）
• 枚举器可以跳过已删除的项目 （以支持foreach ）
• 枚举期间可以从集合中删除项目 ！ （我必须这么做，所以这很好。）
• indexer提供对包含空值的列表的原始访问。 因此， 如果您使用for（;;）循环，请准备过滤掉空值 。
• 如果/当你想删除所有空值时调用Compact（）
• 如果一个人在游戏中从不调用紧凑型游戏，我担心会迭代大量的空值。 因此，对于compact的实验性替代方法，请参阅SparseListCleaningEnumerator：每次枚举时自动收缩列表，至少对于单线程情况：当MoveNext离开项目时，它会查看堆栈以查看索引是否更低并且如果是这样，它将项目分配给较低的索引，将其从当前位置删除，这将缩小列表。 平衡可能需要多次迭代并在优化之前涉及多个移动，除非堆栈被替换为已排序列表，或者堆栈偶尔被排序。 如果最后一个值为null，这将不起作用，因为索引将被隐藏在自由索引堆栈中（用排序的东西替换堆栈将避免这种情况）。

我实现了这个（尚未经过测试），但我将实际的引用存储到我的游戏实体而不是id中，因此你需要以某种方式将其调整为int或Nullable。 （好的是为了确保我回答你的问题的int / uint要求我还添加了一个稍微不同的SparseValueList ，使用默认值（T）而不是null。这意味着你不能在列表中使用0。）你可能也许如果你不认为你需要它，请取出版本 – 大多数游戏可能不会。

 /// 
 /// Specifying null as value has unspecified results. /// CopyTo may contain nulls. /// 
 ///  public class SparseList : IList where T : class { int version = 0; List list = new List(); Stack freeIndices = new Stack(); public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } } public void Compact() { var sortedIndices = freeIndices.ToList(); foreach (var i in sortedIndices.OrderBy(x => x).Reverse()) { list.RemoveAt(i); } freeIndices.Clear(); list.Capacity = list.Count; version++; // breaks open enumerators } public int IndexOf(T item) { return list.IndexOf(item); } /// 
 /// Slow (forces a compact), not recommended /// 
 ///  ///  public void Insert(int index, T item) { // One idea: remove index from freeIndices if it's in there. Stack doesn't support this though. Compact(); // breaks the freeIndices list, so apply it before insert list.Insert(index, item); version++; // breaks open enumerators } public void RemoveAt(int index) { if (index == Count - 1) { list.RemoveAt(index); } else { list[index] = null; freeIndices.Push(index); } //version++; // Don't increment version for removals } public T this[int index] { get { return list[index]; } set { if (value == null) throw new ArgumentNullException(); list[index] = value; } } public void Add(T item) { if (item == null) throw new ArgumentNullException(); if (freeIndices.Count == 0) { list.Add(item); return; } list[freeIndices.Pop()] = item; //version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators } public void Clear() { list.Clear(); freeIndices.Clear(); version++; } public bool Contains(T item) { if (item == null) return false; return list.Contains(item); } /// 
 /// Result may contain nulls /// 
 ///  ///  public void CopyTo(T[] array, int arrayIndex) { list.CopyTo(array, arrayIndex); } //public void CopyNonNullTo(T[] array, int arrayIndex) //{ //} /// 
 /// Use this for iterating via for loop. /// 
 public int Count { get { return list.Count; } } /// 
 /// Don't use this for for loops! Use Count. /// 
 public int NonNullCount { get { return list.Count - freeIndices.Count; } } public bool IsReadOnly { get { return false; } } public bool Remove(T item) { int i = list.IndexOf(item); if (i < 0) return false; if (i == list.Count - 1) { // Could throw . Could add check in list.RemoveAt(i); } else { list[i] = null; freeIndices.Push(i); } //version++; // Don't increment version for removals return true; } public IEnumerator GetEnumerator() { return new SparseListEnumerator(this); } private class SparseListEnumerator : IEnumerator, IRemovingEnumerator { SparseList list; int version; int index = -1; public SparseListEnumerator(SparseList list) { this.list = list; this.version = list.version; //while (Current == null && MoveNext()) ; } public T Current { get { if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access return list[index]; } } public void Dispose() { list = null; } object IEnumerator.Current { get { return Current; } } public bool MoveNext() { do { if (version != list.version) { throw new InvalidOperationException("Collection modified"); } index++; return index < list.Count; } while (Current == null); } public void Reset() { index = -1; version = list.version; } /// 
 /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null. /// 
 public void RemoveCurrent() { list.RemoveAt(index); } } private class SparseListCleaningEnumerator : IEnumerator, IRemovingEnumerator { SparseList list; int version; int index = -1; public SparseListCleaningEnumerator(SparseList list) { this.list = list; this.version = list.version; //while (Current == null && MoveNext()) ; } public T Current { get { if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access return list[index]; } } public void Dispose() { list = null; } object IEnumerator.Current { get { return Current; } } public bool MoveNext() { do { if (version != list.version) { throw new InvalidOperationException("Collection modified"); } if (index > 0 && Current != null // only works for values that are set, otherwise the index is buried in the free index stack somewhere ) { int freeIndex = list.freeIndices.Peek(); if (freeIndex < index) { list.freeIndices.Pop(); list[freeIndex] = list[index]; list.RemoveAt(index); } } index++; return index < list.Count; } while (Current == null); } public void Reset() { index = -1; version = list.version; } /// 
 /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null. /// 
 public void RemoveCurrent() { list.RemoveAt(index); } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } } /// 
 /// Like SparseList but Supports value types, using default(T) in place of null. /// This means values of default(T) are not permitted as values in the collection. /// CopyTo may contain default(T). /// TODO: Use EqualityComparer<T>.Default instead of default(T).Equals() /// 
 ///  public class SparseValueList : IList { int version = 0; List list = new List(); Stack freeIndices = new Stack(); public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } } public void Compact() { var sortedIndices = freeIndices.ToList(); foreach (var i in sortedIndices.OrderBy(x => x).Reverse()) { list.RemoveAt(i); } freeIndices.Clear(); list.Capacity = list.Count; version++; // breaks open enumerators } public int IndexOf(T item) { return list.IndexOf(item); } /// 
 /// Slow (forces a compact), not recommended /// 
 ///  ///  public void Insert(int index, T item) { // One idea: remove index from freeIndices if it's in there. Stack doesn't support this though. Compact(); // breaks the freeIndices list, so apply it before insert list.Insert(index, item); version++; // breaks open enumerators } public void RemoveAt(int index) { if (index == Count - 1) { list.RemoveAt(index); } else { list[index] = default(T); freeIndices.Push(index); } //version++; // Don't increment version for removals } public T this[int index] { get { return list[index]; } set { if (default(T).Equals(value)) throw new ArgumentNullException(); list[index] = value; } } public void Add(T item) { if (default(T).Equals(item)) throw new ArgumentNullException(); if (freeIndices.Count == 0) { list.Add(item); return; } list[freeIndices.Pop()] = item; //version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators } public void Clear() { list.Clear(); freeIndices.Clear(); version++; } public bool Contains(T item) { if (default(T).Equals(item)) return false; return list.Contains(item); } /// 
 /// Result may contain default(T)'s /// 
 ///  ///  public void CopyTo(T[] array, int arrayIndex) { list.CopyTo(array, arrayIndex); } //public void CopyNonNullTo(T[] array, int arrayIndex) //{ //} /// 
 /// Use this for iterating via for loop. /// 
 public int Count { get { return list.Count; } } /// 
 /// Don't use this for for loops! Use Count. /// 
 public int NonNullCount { get { return list.Count - freeIndices.Count; } } public bool IsReadOnly { get { return false; } } public bool Remove(T item) { int i = list.IndexOf(item); if (i < 0) return false; if (i == list.Count - 1) { // Could throw . Could add check in list.RemoveAt(i); } else { list[i] = default(T); freeIndices.Push(i); } //version++; // Don't increment version for removals return true; } public IEnumerator GetEnumerator() { return new SparseValueListEnumerator(this); } private class SparseValueListEnumerator : IEnumerator, IRemovingEnumerator { SparseValueList list; int version; int index = -1; public SparseValueListEnumerator(SparseValueList list) { this.list = list; this.version = list.version; //while (Current == default(T) && MoveNext()) ; } public T Current { get { if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access return list[index]; } } public void Dispose() { list = null; } object IEnumerator.Current { get { return Current; } } public bool MoveNext() { do { if (version != list.version) { throw new InvalidOperationException("Collection modified"); } index++; return index < list.Count; } while (default(T).Equals(Current)); } public void Reset() { index = -1; version = list.version; } /// 
 /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T). /// 
 public void RemoveCurrent() { list.RemoveAt(index); } } private class SparseValueListCleaningEnumerator : IEnumerator, IRemovingEnumerator { SparseValueList list; int version; int index = -1; public SparseValueListCleaningEnumerator(SparseValueList list) { this.list = list; this.version = list.version; while (default(T).Equals(Current) && MoveNext()) ; } public T Current { get { if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access return list[index]; } } public void Dispose() { list = null; } object IEnumerator.Current { get { return Current; } } public bool MoveNext() { do { if (version != list.version) { throw new InvalidOperationException("Collection modified"); } if (index > 0 && (!default(T).Equals(Current)) // only works for values that are set, otherwise the index might be buried in the stack somewhere ) { int freeIndex = list.freeIndices.Peek(); if (freeIndex < index) { list.freeIndices.Pop(); list[freeIndex] = list[index]; list.RemoveAt(index); } } index++; return index < list.Count; } while (default(T).Equals(Current)); } public void Reset() { index = -1; version = list.version; } /// 
 /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T). /// 
 public void RemoveCurrent() { list.RemoveAt(index); } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } }