C#并发编程经典实例（第2版）

108

｜

第

9

章

9.2

　不可变列表

问题

假设需要一个可以建立索引的数据结构，该结构不会经常更改，并且可以被多个线程安全

访问。

解决方案

列表是一种通用型数据结构，可用于所有种类的应用程序状态。不可变列表确实支持索

引，但需要留意性能特性。它们并不单纯是

List<T>

的替代品。

ImmutableList<T>

支持类似于

List<T>

的方法，如下所示：

ImmutableList<

int

> list = ImmutableList<

int

>.Empty;

list = list.Insert(0, 13);

list = list.Insert(0, 7);

// 在

13

之前显示

7

foreach

(

int

item

in

list)

Trace.WriteLine(item);

list = list.RemoveAt(1);

该不可变列表的内部组织为二叉树，如此一来，不可变列表实例与其他实例的共享内存可

以最大化。对于某些常见操作，

ImmutableList<T>

和

List<T>

之间存在性能差异，如表

9-2

所示。

表9-2：列表与不可变列表的性能差异

操作

List<T> ImmutableList<T>

添加 均摊

O

(1)

O

(log

N

)

插入

O

(

N

)

O

(log

N

)

移除某项

O

(

N

)

O

(log

N

)

索引

O

(1)

O

(log

N

)

注意，

ImmutableList<T>

的索引操作是

O

(log

N

)

，而不是

O

(1)

，这一点应该很好理解。如果

用

ImmutableList<T>

替换现有代码中的

List<T> ...