是否不可变?

17

好的,我理解不可变类型本质上是线程安全的,或者说我在各种地方都读到过这样的说法,也认为我理解了为什么会这样。如果实例的内部状态在对象创建后无法被修改,那么似乎并没有使用该实例本身的并发访问问题。

因此,我可以创建以下List

class ImmutableList<T>: IEnumerable<T>
{
    readonly List<T> innerList;

    public ImmutableList(IEnumerable<T> collection)
    {
         this.innerList = new List<T>(collection);
    }

    public ImmutableList()
    {
         this.innerList = new List<T>();
    }

    public ImmutableList<T> Add(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Add(item);
         return list;
    }

    public ImmutableList<T> Remove(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Remove(item);
         return list;
    } //and so on with relevant List methods...

    public T this[int index]
    {
        get
        {
            return this.innerList[index];
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return innerList.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((System.Collections.IEnumerable)this.innerList).GetEnumerator();
    }
}

所以问题是:这个类型真的是一个不可变类型吗?它真的是线程安全的吗?
显然,这个类型本身是不可变的,但是绝对不能保证T也是不可变的,因此您可能会遇到与通用类型直接相关的并发访问和线程问题。这是否意味着应该将ImmutableList视为可变的?
ImmutableList: IEnumerable where T: struct 这个类是否应该是唯一真正被认为是不可变的类型?
感谢任何关于此问题的输入。
更新:很多答案/评论都集中在我发布的ImmutableList的特定实现上,这可能不是一个非常好的例子。但问题不在于实现。我要问的问题是,考虑到不可变类型所涉及的一切,ImmutableList是否真的是一个不可变类型。

4
结构体可以是可变的,而对象可以是不可变的。 - Sean U
2
你目前的RemoveAdd方法中存在无限递归;-) - BrokenGlass
1
我想提一下,有比使集合不可变更更好的方法来使线程安全。每次想要更改其内容时复制整个集合会降低性能/内存,除非它们始终非常小。此外,许多数据结构的线程安全实现已经存在(或在语言规范中)。 - Servy
1
@SeanU:结构体可以是可变的这一事实并不重要;在这里展示的草图中,没有任何类型为T的变量暴露给调用者,因此他们无法改变结构体类型的变量。相关的重点是结构体可能包含对可变状态的引用 - Eric Lippert
3
不可变的T集合指始终包含相同实例的集合。如果我有一个包含五个Car实例的ImmutableList<Car>,只要它存在,它始终会保存这五个Car实例。尽管有人可能会给车涂上漆或偷走轮罩,但它们仍然是同样的五辆车。 - supercat
显示剩余9条评论
6个回答

28
如果实例的内部状态在对象创建后无法修改,则访问该实例本身并发不会出现问题。通常情况下是这样的。
总之,你有一个可写复制包装器,围绕着一个可变列表。向不可变列表添加新成员不会改变列表;相反,它会复制底层可变列表,将其添加到副本中,并返回一个包装器,围绕着该副本。
只要您包装的底层列表对象在读取时不会改变其内部状态,您就满足了最初的“不可变”定义,所以是的。
请注意,这不是实现不可变列表的非常高效的方法。例如,使用不可变平衡二叉树可能会更好。您的草图每次创建新列表时都需要O(n)的时间和内存;您可以轻松将其提高到O(log n)。
只要底层可变列表对于多个读取器是线程安全的,就可以保证线程安全。
这可能对您有所帮助:

http://blogs.msdn.com/b/ericlippert/archive/2011/05/23/read-only-and-threadsafe-are-different.aspx

显然,类型本身是不可变的,但不能保证T也是不可变的,因此您可能会遇到与泛型类型直接相关的并发访问和线程问题。这是否意味着应该将ImmutableList视为可变的?这是一个哲学问题而不是技术问题。如果您有一个人名的不可变列表,并且该列表从未更改过,但其中一个人死了,那么名字列表是否“可变”?我认为不是。
如果关于列表的任何问题始终具有相同的答案,则列表是不可变的。在我们的人名列表中,“列表上有多少个名称?”是关于列表的问题。“这些人中有多少还活着?”不是关于列表的问题,而是关于列表所涉及的人的问题。对该问题的答案随时间而变化;第一个问题的答案不会改变。
我不明白你的意思。将T限制为结构体如何改变任何内容?好吧,T被限制为结构体。我创建了一个不可变的结构体:
struct S
{
    public int[] MutableArray { get; private set; }
    ...
}

现在我创建一个ImmutableList<S>。是什么阻止了我修改存储在实例S中的可变数组? 仅仅因为列表和结构体不可变,并不能使数组不可变。

1
“除非您认为名称是指向人的适当指针,否则请仅返回翻译文本:与垂死的人类的比喻有点奇怪;在这种情况下,一个人的名字不会改变。更好的比喻是列出人员名单,而不是仅仅列出名字。” - The Nail
1
@TheNail:关键是这些名字是对人的引用。当然,类比的问题在于一个人可能会改变他们的名字而不改变他们的身份。 - Eric Lippert
@TheNail,名称是我们用来“引用”人的东西。当然,可能会有两个人有相同的名字(尝试写关于宗教的文章时,有两个全名相同的人写关于其他宗教!),但我们在一个上下文中使用名称,使得名称成功地指向一个人。这与C#中引用的工作方式非常相似,但优点是不使用“地址”或“指针”这些词。 - Jon Hanna
此外,一个很好的阐述是:'如果关于列表的任何问题总是有相同的答案,则该列表是不可变的'。 - The Nail
1
@InBetween 这是假设保持可变引用列表不可变从未有任何价值。如果它一直是不可变的,你就不能提供相同的保证,但只要知道列表不会改变,至少让某些事情更容易推理了一点。不可变性是一种限制 - 它增加了我们无法做的事情 - 所有的限制都使事情更容易推理 - 这增加了最终可以做的范围,因为你已经迈出了离“我不知道,这只是一堆1和0在移动”更进一步的一步 :) - Jon Hanna
显示剩余6条评论

5
不可变性有时会以不同的方式定义。线程安全也是如此。
创建一个用于不可变性的不可变列表时,您应该记录您所做出的保证。例如,在这种情况下,您保证列表本身是不可变的,并且没有任何隐藏的可变性(一些表面上不可变的对象实际上在幕后是可变的,例如具有记忆化或内部重新排序作为优化的对象),这会消除从不可变性中获得的线程安全性(虽然也可以以不同的方式保证线程安全地执行这些内部突变)。您并未保证存储的对象可以以线程安全的方式使用。
您应记录的线程安全性与此相关。您无法保证另一个对象不会具有相同的对象(如果每次调用时都创建新对象,则可以)。您可以确保操作不会破坏列表本身。
坚持使用 T : struct 可能有所帮助,因为这意味着您可以确保每次返回项目时,它是结构体的新副本(仅使用 T : struct 不能做到这一点,因为您可能会进行不改变列表但会改变其成员的操作,因此您必须这样做)。
但这限制了您既不支持不可变的引用类型(例如 string,在许多现实情况下是集合的成员),也不允许用户利用它并提供自己的方法来确保包含项目的可变性不会导致问题。由于没有线程安全的对象可以保证其使用的所有代码都是线程安全的,因此努力确保(尽可能地帮助,但不要试图确保您无法确保的内容)是没有意义的。
它还不能保护不可变列表中不可变结构体的可变成员!

如果可变结构体存储在不可变列表中,那么该结构体将变为不可变。这是“可变”结构体相对于可变类的优势之一--将它们包装在不会改变它们或将它们作为'ref'参数传递给其他可能这样做的方法,它们将保持不可变。当然,如果结构体持有对可变类类型的引用,则引用可能是不可变的,但从而引用的对象可能不是。真的太糟糕了,没有ImmutableArray类型或任何其他方式让结构体持有一个可变大小的坚固不变的对象集合。 - supercat
@supercat 这也可能是其中一个缺点,因为行为可能会出人意料。 - Jon Hanna
如果结构体字段访问使用与类字段访问不同的字符(类似于C中的->.),或者结构体类型和存储位置的命名约定与类不同,就可以避免混淆。当C#允许在只读上下文中无用地编写结构体时,混淆的可能性是巨大的,但现在由于C#禁止编写只读结构体的字段或属性,唯一的“混淆”将出现在不知道什么是结构体的程序员身上;对于这样的程序员来说,补救措施是学习。 - supercat
一个带有int字段X和Y的结构类型存储位置包含两个信息:X的值和Y的值。一个带有两个字段X和Y的类类型存储位置实际上包含三个信息:X和Y的值,以及持有相同引用的所有其他存储位置的集合。有时候需要拥有可以相互关联的对象--对于这种目的,类显然是适当的。然而,经常管理这样的关联是心理和电子开销,最好避免。 - supercat
顺便说一句,尽管“电话号码”被认为是值类型的候选项,但更自然的操作似乎是:“获取所有带有区号‘708’的电话号码并交换‘475’,将区号更改为‘630’”,还是“获取所有带有区号‘708’的电话号码并交换‘475’,用新的带有区号‘630’的电话号码替换它们,包括原始交换、原始基础号码、原始分机号等?”我认为许多现实世界中的“值”经常是逐步修改的。 - supercat

2
使用您的代码,假设我这样做:
ImmutableList<int> mylist = new ImmutableList<int>();

mylist.Add(1); 

您在StackOverflow上发布的代码引发了StackOverflow异常。有很多明智的方法可以创建线程安全集合,复制集合(至少尝试),并将它们称为不可变的,但这些方法并不能完全解决问题。

Eric Lippert发布了一个非常值得阅读的链接。


@InBetween:然而,复制时写并不是解决这个问题的方法! - Mithrandir
Jon Hanna:实现不可变列表并不是问题...我并没有考虑以这种方式实现列表,这只是一个例子。问题在于ImmutableList<MutableT>是否真的是一个不可变列表。 - InBetween
@InBetween 我删除了那条评论,因为我误读了!不过,这是一个可能可变的东西的不可变列表。这给你一些保证,并且(通过不同的实现)在线程安全方面和其他方面也可能很有价值。 - Jon Hanna

2
一个数据类型的典型例子是,表现为可变对象的不可变列表:MulticastDelegate。MulticastDelegate可以被准确地建模为一个(对象、方法)对的不可变列表。这些方法的集合以及它们作用的对象的身份是不可变的,但在绝大多数情况下,这些对象本身将是可变的。实际上,在许多情况下,代表将会改变它引用的对象的状态。
一个代表无需知道它即将调用的方法是否可能以线程不安全的方式改变目标对象。代表负责确保其函数和对象标识的列表是不可变的,而我不认为任何人都希望它也如此。
ImmutableList同样应该始终保持相同的类型T实例集。这些实例的属性可能会改变,但它们的标识不会。如果创建了一个包含两个福特汽车的List,序列号分别为#1234和#4422,它们都是红色的,而其中一个福特被涂成了蓝色,那么最初的两辆红色汽车的列表将变成一个包含一辆蓝色车和一辆红色车的列表,但仍然保留#1234和#4422。

1
我认为在这个话题上进行较长的讨论时,应该将不可变性/可变性与作用域一起考虑。
举个例子:
假设我正在使用C#项目,并定义了一个静态类和静态数据结构,在我的项目中没有定义任何修改这些结构的方式。实际上,它是一个只读的数据缓存,我可以使用它,在我的程序运行期间,它从一个运行到下一个是不可变的。我完全控制着数据,用户无法在运行时修改它。
现在我在源代码中修改了我的数据并重新运行程序。数据已经改变,因此从最高层面上看,数据不再是不可变的。从最高层面的角度来看,实际上数据是可变的。
因此,我认为我们需要讨论的不是将某些东西归为不可变或可变的黑白问题,而是应该考虑特定实现的可变程度(因为有很少的事情是永远不会改变的,因此真正不可变)。

1
我认为如果元素是可变的,通用列表就不是不可变的,因为它不能代表数据状态的完整快照。
要在您的示例中实现不可变性,您必须创建列表元素的深层副本,这样做并不高效。
您可以在IOG库中查看我的解决方案。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接