.net - .NET 库中是否有稀疏数组实现？

Question

.NET 库中是否已经实现了数据结构，其行为类似于稀疏数组（其中大多数索引为空），通过索引进行 O(1) 访问，对下一个（和上一个）元素进行 O(1) 访问？

Answer 1

我不知道您想要的任何内置容器，但作为一种解决方法，您可以使用Dictionary以下项目之一：

class Entry<T>
{
    int previdx, nextidx;
    T data;
}

（.NET 中的字典具有 O(1) 查找，因为它是基于哈希表的）。对于 O(log n) 的插入，我们需要保留一个已存在索引的排序列表（这不存在开箱即用，但可以很容易地模拟）

Answer 2

几年前，我基于我的“AList”概念实现了一个稀疏集合。它被称为SparseAList，它可能比您自己推出的任何“简单”解决方案都要好。例如，@NathanPhilips 的解决方案Insert具有RemoveAt调用ToDictionary. Enumerable.ToDictionary是一种 O(N) 方法-它“从头开始”重新生成整个字典-因此效率不高。

相比之下， SparseAList基于B+ 树，因此它具有高效的 O(log N) 插入、查找和删除，并且还可以有效地使用内存。它包含在 LoycCore 的Loyc.Collections.dll中，可在 NuGet 上找到（搜索 Loyc.Collections）。

Answer 3

不久前，我在 dotnet 中整理了一个列表。那里没有稀疏列表。
无论如何我都会提到它，因为如果您决定自己开发一个，它可能会有所帮助。

Answer 4

这是一个基于 Dictionary 的稀疏数组（大部分未经测试，我只是在阅读此问题后将其放在一起）：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace NobleTech.Products.Library.Linq
{
    public class SparseList<T> : IList<T>
    {
        private T defaultValue;
        private Dictionary<int, T> dict;
        private IEqualityComparer<T> comparer;

        public SparseList(T DefaultValue = default(T))
            : this(DefaultValue, EqualityComparer<T>.Default)
        {
        }

        public SparseList(IEqualityComparer<T> Comparer)
            : this(default(T), Comparer)
        {
        }

        public SparseList(T DefaultValue, IEqualityComparer<T> Comparer)
        {
            defaultValue = DefaultValue;
            dict = new Dictionary<int, T>();
            comparer = Comparer;
        }

        public int IndexOf(T item)
        {
            if (comparer.Equals(item, defaultValue))
                return LinqUtils.Generate().First(i => !dict.ContainsKey(i));
            return dict.Where(kvp => comparer.Equals(item, kvp.Value))
                .Select(kvp => (int?)kvp.Key).FirstOrDefault() ?? -1;
        }

        public void Insert(int index, T item)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException("index", index, "index must be non-negative");
            if (index < Count)
                dict = dict.ToDictionary(kvp => kvp.Key < index ? kvp.Key : kvp.Key + 1, kvp => kvp.Value);
            this[index] = item;
        }

        public void RemoveAt(int index)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException("index", index, "index must be non-negative");
            dict.Remove(index);
            if (index < Count)
                dict = dict.ToDictionary(kvp => kvp.Key < index ? kvp.Key : kvp.Key - 1, kvp => kvp.Value);
        }

        public T this[int index]
        {
            get
            {
                if (index < 0)
                    throw new ArgumentOutOfRangeException("index", index, "index must be non-negative");
                if (dict.ContainsKey(index))
                    return dict[index];
                return defaultValue;
            }
            set
            {
                if (index < 0)
                    throw new ArgumentOutOfRangeException("index", index, "index must be non-negative");
                dict[index] = value;
            }
        }

        public void Add(T item) { this[Count] = item; }

        public void Clear() { dict.Clear(); }

        public bool Contains(T item)
        {
            return comparer.Equals(item, defaultValue) || dict.Values.Contains(item, comparer);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", arrayIndex, "arrayIndex must be non-negative");
            for (int i = 0; i < array.Length - arrayIndex; ++i)
                array[arrayIndex + i] = this[i];
        }

        public int Count { get { return (dict.Keys.Max(i => (int?)i) ?? -1) + 1; } }

        public bool IsReadOnly { get { return false; } }

        public bool Remove(T item)
        {
            int index = IndexOf(item);
            if (index < 0)
                return false;
            RemoveAt(index);
            return true;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return LinqUtils.Generate(i => this[i]).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
    }
}

的实现LinqUtils.Generate留给读者作为练习:-)