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

Question

我正在寻找一个可以快速迭代的集合。我还将定期添加项目和删除（特定）项目，因此理想情况下希望这些操作也能快速进行。

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

我将在集合中存储 uint（但如果需要的话可以是 int）。不过，通用的解决方案会很好，因为我确信我将来会有需要。

.net 集合将是理想的，否则轻量级和开源的东西会很棒。

有没有适合我需要的集合类？如果没有，我将如何创建一个？

---

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

Answer 1

我有两个建议可以尝试：

首先，使用 Reflector 或 ILSpy 来查看 Generic List 内部怎么样？我假设 CF 中没有实现，或者您可以使用它。通用 List 支持数组，并使用从长度为 4 的数组开始的加倍算法，每次调用 .Add 都会导致容量加倍，并执行 Array.Copy 到新数组中。除非您明确将“容量”设置为零，否则它不会调整大小，因此从内存的角度要小心。添加是一回事，但每次删除都会导致数组在被删除的索引之后被复制并左移。

第二个建议是这样的 - 创建一个自定义类来包装一个整数数组来处理这个问题，它使用与通用 List 类似的双精度算法（或四倍）（以处理调整大小），但是从大小 256 开始。您可以按照您喜欢的速度将对象整数 id 添加到其中，而且它不会经常加倍。您还可以通过将 (int)-1 或 uint.MaxValue 指定为“空索引”来模拟删除，这意味着删除时没有 Array.Copy。然后，在绘制之前对每帧应用某种快速排序来对对象索引数组进行排序。如果按升序排序，所有 -1 将出现在开头（或 uint.MaxValues 在末尾），并且可以被忽略。您可以通过在单独的线程上调整大小和删除前面的 -1 来定期“收集”索引数组（注意 - 使用锁定；）

您觉得怎么样？只是想你会每帧抵消一些计算以进行快速排序（在 xbox 上并不昂贵，而在每个删除和一些添加上进行内存分配/收集（昂贵）。

更新 - BlockArray - List其中 T 对此的进一步评论我最近正在尝试动态大小

列表的最有效的数据结构，并通过实验发现数组块 - 一个由 T[] 列表支持的类。其中每个T[] 是固定大小块的数组，例如 512、4096、8192，与普通 List相比有几个优点

我发现 List对于 List来说，其性能远远优于 Add()，尤其是当总大小变大时，这是由于 List的加倍算法需要一个值。新数组的大小是旧数组的 2 倍，每当超过大小时，memcpy 都会覆盖旧数组，

预分配（预定义容量）比 List慢得多。对于小块大小（512），但对于大块大小（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）。然后，当您需要添加到列表中时，它会从堆栈中弹出已删除的索引并在其中添加值。 （对于多线程，也许 ConcurrentQueue是另一个想法。）
• 枚举器可以跳过已删除的项目（以支持foreach）
• 项目可以从枚举期间收集！ （我必须经常这样做，所以这很好。）
• 索引器提供对包含空值的列表的原始访问。因此，如果您使用 for(;;) 循环，请准备好过滤掉 null。
• 如果/当您想要删除所有空值时，请调用Compact()
• 如果在游戏过程中从不调用compact，我担心会迭代大量空值。因此，对于紧凑型的实验性替代方案，请参阅 SparseListCleaningEnumerator：每次枚举时自动收缩列表，至少对于单线程情况：当 MoveNext 远离某个项目时，它会查看堆栈以查看索引是否较低以及如果是这样，它将将该项目分配给较低的索引，并将其从当前位置删除，这将缩小列表。平衡可能需要多次迭代，并在优化之前涉及多次移动，除非用排序列表替换堆栈，或者偶尔对堆栈进行排序。如果最后一个值为空，则这将不起作用，因为索引将被隐藏在空闲索引堆栈中（用排序的内容替换堆栈可以避免这种情况）。

我实现了这个（尚未测试），但我存储的是对我的游戏实体的实际引用而不是 id，因此您需要以某种方式针对 int 或 Nullable 进行调整。 （好的，为了确保我回答你的问题的 int/uint 要求，我还添加了一个稍有不同的 SparseValueList，使用 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();
    }
}