我正在收集一个可以非常快速地迭代的集合。我还将相当定期地添加项目和删除（特定）项目，因此理想情况下希望这些操作也很快。
我正在 xbox 上开发，因此仅限于紧凑的框架（或多或少）。将垃圾和对象分配保持在最低限度是非常重要的，所以我可以为我的对象预先分配空间的任何东西都会很棒。
我将在集合中存储uints（但如果需要可以是s）。int不过，一个通用的解决方案会很好，因为我相信我将来会有需要。
.net 集合将是理想的，但轻量级和开源的东西会很棒。
是否有适合我需要的收藏类？如果没有，我将如何创建一个？
更详细地说，它们是类应该处理每一帧的对象ID。它们通常会按升序添加，有间隙。没有上限。但是，可以删除任何内容，这会留下空白。
迭代顺序并不完全重要，但如果它的顺序一致，它将非常有用（特别是对于调试）。
自定义类 SparseList<T> 怎么样：
我实现了这个（尚未测试），但我存储了对我的游戏实体而不是 id 的实际引用，因此您需要以某种方式将其调整为 int 或 Nullable。（确定我回答您的问题的 int/uint 要求，我还添加了一个略有不同的 SparseValueList<T>，使用 default(T) 而不是 null。这意味着您不能在列表中使用 0。）您也许可以如果您认为不需要，请取出版本控制——大多数游戏可能不需要。
/// <summary>
/// Specifying null as value has unspecified results.
/// CopyTo may contain nulls.
/// </summary>
/// <typeparam name="T"></typeparam>
public class SparseList<T> : IList<T>
where T : class
{
int version = 0;
List<T> list = new List<T>();
Stack<int> freeIndices = new Stack<int>();
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);
}
/// <summary>
/// Slow (forces a compact), not recommended
/// </summary>
/// <param name="index"></param>
/// <param name="item"></param>
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);
}
/// <summary>
/// Result may contain nulls
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
public void CopyTo(T[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
//public void CopyNonNullTo(T[] array, int arrayIndex)
//{
//}
/// <summary>
/// Use this for iterating via for loop.
/// </summary>
public int Count { get { return list.Count; } }
/// <summary>
/// Don't use this for for loops! Use Count.
/// </summary>
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<T> GetEnumerator()
{
return new SparseListEnumerator(this);
}
private class SparseListEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseList<T> list;
int version;
int index = -1;
public SparseListEnumerator(SparseList<T> 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;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null.
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
private class SparseListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseList<T> list;
int version;
int index = -1;
public SparseListCleaningEnumerator(SparseList<T> 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;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null.
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
/// <summary>
/// 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()
/// </summary>
/// <typeparam name="T"></typeparam>
public class SparseValueList<T> : IList<T>
{
int version = 0;
List<T> list = new List<T>();
Stack<int> freeIndices = new Stack<int>();
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);
}
/// <summary>
/// Slow (forces a compact), not recommended
/// </summary>
/// <param name="index"></param>
/// <param name="item"></param>
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);
}
/// <summary>
/// Result may contain default(T)'s
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
public void CopyTo(T[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
//public void CopyNonNullTo(T[] array, int arrayIndex)
//{
//}
/// <summary>
/// Use this for iterating via for loop.
/// </summary>
public int Count { get { return list.Count; } }
/// <summary>
/// Don't use this for for loops! Use Count.
/// </summary>
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<T> GetEnumerator()
{
return new SparseValueListEnumerator(this);
}
private class SparseValueListEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseValueList<T> list;
int version;
int index = -1;
public SparseValueListEnumerator(SparseValueList<T> 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;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T).
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
private class SparseValueListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseValueList<T> list;
int version;
int index = -1;
public SparseValueListCleaningEnumerator(SparseValueList<T> 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;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T).
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
使用 Mono 怎么样HashSet<T>？
https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs
它在 MIT X11 下获得许可，这是一个许可许可。
迭代顺序可能是一个问题，具体取决于T实现方式GetHashCode，但在使用时应该不是问题uint。GetHashCode另一方面，默认实现在不同的实例上返回不同的值，这可能导致不同的迭代顺序。
迭代顺序也可能取决于添加的订单项。即，如果项目以不同的顺序添加，则包含相同项目的两个集合可能会以不同的顺序迭代。
还有一个SortedSet<T>合集，但不知道它有什么性能特点。
我有两个建议可以尝试：
首先，如何使用 Reflector 或 ILSpy 来查看 Generic 内部List<T>？我假设实现不在 CF 中，或者您可以使用它。GenericList<T>由数组支持并使用从长度为 4 的数组开始的加倍算法，每次调用 .Add 超过容量都会使其加倍并执行 Array.Copy 到新数组中。除非您将容量显式设置为零，否则它不会调整大小，因此从内存的角度要小心。添加是一回事，但每次删除都会导致数组在被删除的索引之后被复制和左移。
第二个建议是这个 - 关于创建一个自定义类，它包装一个整数数组来处理这个问题，它使用与 Generic 类似的双算法（或四倍）List<T>（处理调整大小），但从说大小 256 开始。你可以添加对象整数id 可以随心所欲地乱序，而且它不会经常翻倍。您还可以通过将 (int)-1 或 uint.MaxValue 指定为“空索引”来模拟删除，这意味着删除时没有 Array.Copy。然后，在绘制之前对每帧应用某种快速排序以对对象索引数组进行排序。如果您按升序排序，所有 -1 将出现在开头（或 uint.MaxValues 在结尾）并且可以忽略。-1您可以通过在单独的线程上调整大小和删除前面的来定期“收集”索引数组（注意 - 使用锁定；
你怎么看？只是认为您将每帧抵消一些计算以进行快速排序（在 xbox 上并不昂贵，而在每个删除和一些添加上的内存分配/收集（昂贵）。
更新 - BlockArray - List<T[]> 其中 T 是固定大小的数组
对此作进一步评论。我最近正在试验动态大小列表的最有效数据结构，并通过实验发现数组块 - 一个由 T[] 列表支持的类，其中每个 T[] 是一个固定大小块的数组，例如512、4096、8192 与普通 List<T> 相比有几个优点。
我发现 List<T[]> 中的 Add()（大小未知）的实现大大优于 List<T> 的 Add()，尤其是当总大小变大时。这是由于 List<T> 的加倍算法要求新数组的大小是旧数组的 2 倍，而当超过大小时，memcpy 会超过旧数组。
迭代速度类似。对于小块大小 (512)，预分配（预定义的容量）比 List<T> 慢得多，但对于大块大小 (8192) 仅稍慢一些。删除是有问题的，因为需要复制/左移许多块。
有趣的是在 List<T[]> （块列表）中，您可以缓存/池化块。如果足够小，T[] 块适合小对象堆（有利于压缩，更快分配），可能适合 L2 缓存，并且可以预先分配和池化许多块