高效、不可变、可扩展的.NET集合

Question

在我看来，.NET中安全、不可变的集合类型似乎极度缺乏，尤其是在BCL中，但我并没有看到在其他地方有太多的工作。有人能指点我一个（最好是）生产质量的、快速的、不可变的集合库吗？快速的列表类型是必不可少的。我还没有准备好转向F#。

*编辑：注意搜索者，这将很快整合到BCL中：.NET不可变集合

- Bent Rasmussen

Answer 1

你可能想要查看FSharp.Core程序集中的Microsoft.FSharp.Collections命名空间。你不必使用F#编程来使用这些类型。

请注意，在从F#外部使用时名称将会不同。例如，F#中的Map在C#中被称为FSharpMap。

- Rich

---

使用F数据类型在C＃中。 - Mauricio Scheffer

不幸的是，所有的F#集合都是以类的形式实现而不是接口。这使得它们不太适合用于API规范。 - Andriy Drozdyuk

@drozzy 我没有尝试过这个，但是文档表明他们实现了所有通常的接口。 - Roman Starkov

你误解了我的意思。我想说的是，没有一个名为ImmutableList的接口。是的，它们实现了IEnumerable和其他标准.NET接口，但是它们都没有提供我们需要的能够编写具有不可变性约束的API的接口。 - Andriy Drozdyuk

这些听起来可能很有趣，但我对F#一无所知。是否有一页以更容易被VB.NET或C#程序员理解的格式描述这些类？ - supercat

Answer 2

.NET BCL团队已经发布了.NET 4.5的不可变集合预览版。

- Wim Coenen

Answer 3

• Functional-dotnet 由Alexey Romanov 开发
• Sasa 由Sandro Magi 开发
• Kinet 由Tony Morris 开发

- Mauricio Scheffer

---

这才像话！你知道这些集合在性能方面与Rich上面提到的Microsoft.FSharp.Collections相比如何吗？感谢参考，Mauricio！ - Bent Rasmussen

这个由Alexey编写的库看起来非常精心设计和整洁。非常感谢你！ :-) - Bent Rasmussen

Answer 4

我一段时间之前编写了一个 ImmutableList<T> 类:

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

public class ImmutableList<T> : IList<T>, IEquatable<ImmutableList<T>>
{
    #region Private data

    private readonly IList<T> _items;
    private readonly int _hashCode;

    #endregion

    #region Constructor

    public ImmutableList(IEnumerable<T> items)
    {
        _items = items.ToArray();
        _hashCode = ComputeHash();
    }

    #endregion

    #region Public members

    public ImmutableList<T> Add(T item)
    {
        return this
                .Append(item)
                .AsImmutable();
    }

    public ImmutableList<T> Remove(T item)
    {
        return this
                .SkipFirst(it => object.Equals(it, item))
                .AsImmutable();
    }

    public ImmutableList<T> Insert(int index, T item)
    {
        return this
                .InsertAt(index, item)
                .AsImmutable();
    }

    public ImmutableList<T> RemoveAt(int index)
    {
        return this
                .SkipAt(index)
                .AsImmutable();
    }

    public ImmutableList<T> Replace(int index, T item)
    {
        return this
                .ReplaceAt(index, item)
                .AsImmutable();
    }

    #endregion

    #region Interface implementations

    public int IndexOf(T item)
    {
        if (_items == null)
            return -1;

        return _items.IndexOf(item);
    }

    public bool Contains(T item)
    {
        if (_items == null)
            return false;

        return _items.Contains(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        if (_items == null)
            return;

        _items.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get
        {
            if (_items == null)
                return 0;

            return _items.Count;
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (_items == null)
            return Enumerable.Empty<T>().GetEnumerator();

        return _items.GetEnumerator();
    }

    public bool Equals(ImmutableList<T> other)
    {
        if (other == null || this._hashCode != other._hashCode)
            return false;
        return this.SequenceEqual(other);
    }

    #endregion

    #region Explicit interface implementations

    void IList<T>.Insert(int index, T item)
    {
        throw new InvalidOperationException();
    }

    void IList<T>.RemoveAt(int index)
    {
        throw new InvalidOperationException();
    }

    T IList<T>.this[int index]
    {
        get
        {
            if (_items == null)
                throw new IndexOutOfRangeException();

            return _items[index];
        }
        set
        {
            throw new InvalidOperationException();
        }
    }

    void ICollection<T>.Add(T item)
    {
        throw new InvalidOperationException();
    }

    void ICollection<T>.Clear()
    {
        throw new InvalidOperationException();
    }

    bool ICollection<T>.IsReadOnly
    {
        get { return true; }
    }

    bool ICollection<T>.Remove(T item)
    {
        throw new InvalidOperationException();
    }

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

    #endregion

    #region Overrides

    public override bool Equals(object obj)
    {
        if (obj is ImmutableList<T>)
        {
            var other = (ImmutableList<T>)obj;
            return this.Equals(other);
        }
        return false;
    }

    public override int GetHashCode()
    {
        return _hashCode;
    }

    #endregion

    #region Private methods

    private int ComputeHash()
    {
        if (_items == null)
            return 0;

        return _items
            .Aggregate(
                983,
                (hash, item) =>
                    item != null
                        ? 457 * hash ^ item.GetHashCode()
                        : hash);
    }

    #endregion
}

所有修改集合的方法都会返回修改后的副本。为了遵守 IList<T> 接口协定，标准的 Add/Remove/Delete/Clear 方法被显式实现，但它们会抛出 InvalidOperationException 异常。

该类使用了一些非标准的扩展方法，以下是它们：

public static class ExtensionMethods
{
    public static IEnumerable<T> Append<T>(this IEnumerable<T> source, T item)
    {
        return source.Concat(new[] { item });
    }

    public static IEnumerable<T> SkipFirst<T>(this IEnumerable<T> source, Func<T, bool> predicate)
    {
        bool skipped = false;
        foreach (var item in source)
        {
            if (!skipped && predicate(item))
            {
                skipped = true;
                continue;
            }

            yield return item;
        }
    }

    public static IEnumerable<T> SkipAt<T>(this IEnumerable<T> source, int index)
    {
        return source.Where((it, i) => i != index);
    }

    public static IEnumerable<T> InsertAt<T>(this IEnumerable<T> source, int index, T item)
    {
        int i = 0;
        foreach (var it in source)
        {
            if (i++ == index)
                yield return item;

            yield return it;
        }
    }

    public static IEnumerable<T> ReplaceAt<T>(this IEnumerable<T> source, int index, T item)
    {
        return source.Select((it, i) => i == index ? item : it);
    }
}

下面是一个帮助类，用于创建 ImmutableList<T> 的实例：

public static class ImmutableList
{
    public static ImmutableList<T> CreateFrom<T>(IEnumerable<T> source)
    {
        return new ImmutableList<T>(source);
    }

    public static ImmutableList<T> Create<T>(params T[] items)
    {
        return new ImmutableList<T>(items);
    }

    public static ImmutableList<T> AsImmutable<T>(this IEnumerable<T> source)
    {
        return new ImmutableList<T>(source);
    }
}

这是一个使用示例：

    [Test]
    public void Test_ImmutableList()
    {
        var expected = ImmutableList.Create("zoo", "bar", "foo");
        var input = ImmutableList.Create("foo", "bar", "baz");
        var inputSave = input.AsImmutable();
        var actual = input
                .Add("foo")
                .RemoveAt(0)
                .Replace(0, "zoo")
                .Insert(1, "bar")
                .Remove("baz");

        Assert.AreEqual(inputSave, input, "Input collection was modified");
        Assert.AreEqual(expected, actual);
    }

我不能说这是生产质量，因为我还没有进行全面测试，但目前看来它似乎运行得很好...

- Thomas Levesque

---

非常棒的实现！然而，如果您直接创建目标数组并使用 Array.Copy，在压力下它可能会更快。IEnumerable<T> 对于可读的函数式代码很好，但老实说，它会变慢。 - Timwi

@Timwi，确实，这个实现肯定可以进行优化。当我编写它时，我并不需要非常高效的实现，所以我选择了Linq方式，因为它更有趣 ;) - Thomas Levesque

@Timwi - 这种方法更加节省内存，因为列表的内容被重复使用，但正如你所说，它并不高效，特别是对于元素的索引访问。类似于使用不可变 cons 单元格（http://en.wikipedia.org/wiki/Cons）的 Lisp 列表将提供一个很好的中间地带 - 其中对连续成员的索引访问可以被优化（获取下一个项目的固定成本），而可枚举解决方案具有可变成本，同时避免了在列表尾部未更改的情况下复制整个列表内容的需要。 - Bittercoder

@Bittercoder：不，这个实现会复制每个不可变列表的新版本（通过在构造函数中调用ToArray）。 - Timwi

Answer 5

C5 这个库让我想起来了，但我不确定它的速度有多快。它已经存在多年了，非常稳定。

此外，List<T>.AsReadOnly() 在我看来也做得很好，但不幸的是，字典或任意 ICollection<T> 没有相应的方法。

- Roman Starkov

---

不幸的是，.AsReadOnly() 只返回原始集合的包装器; 原始引用仍然是可变的，因此只读包装器也是如此。看起来 C5 也是如此。 - Timwi

@Timwi 如果你担心原始引用可能会被其他代码修改，那么只需复制它：return new List<T>(myList).AsReadOnly()。 - Roman Starkov

@romkyns 如果总是复制列表，就没有不可变列表的必要了 :-) - Andriy Drozdyuk

@drozzy .AsReadOnly() 在许多情况下非常不错，我们没有更好的内置方法 :) 此外，您只需要复制一次，之后列表就是完全不可变的，可以在任何地方传递。 - Roman Starkov

Answer 6

你可以查看Extras或System.collections.concurrent tutorial

- Lukasz Madon

Answer 7

你可以尝试由JaredPar开发的BclExtras。

- Roman Starkov