F# 编程/可变集合

F# : 可变集合

.NET BCL 自带一套可变集合，它们位于 System.Collections.Generic 命名空间中。这些内置集合与 F# 中的不可变对应物非常相似。

`List<'T>` 类

List<'T> 类表示一个强类型对象列表，可以通过索引访问。从概念上讲，这使得 List<'T> 类类似于数组。但是，与数组不同，List 可以调整大小，不需要在声明时指定其大小。

.NET 列表使用 new 关键字创建，并调用列表的构造函数，如下所示

> open System.Collections.Generic;;
> let myList = new List<string>();;

val myList : List<string>

> myList.Add("hello");;
val it : unit = ()
> myList.Add("world");;
val it : unit = ()
> myList.[0];;
val it : string = "hello"
> myList |> Seq.iteri (fun index item -> printfn "%i: %s" index myList.[index]);;
0: hello
1: world

很容易看出 .NET 列表是可变的，因为它们的 Add 方法返回 unit，而不是返回另一个列表。

底层实现

在幕后，List<'T> 类只是一个用于数组的精美包装器。当构造 List<'T> 时，它会在内存中创建一个包含 4 个元素的数组。添加前 4 个项目是 O(1) 操作。但是，一旦需要添加第 5 个元素，列表就会将内部数组的大小加倍，这意味着它必须重新分配新内存并复制现有列表中的元素；这是一个 O(n) 操作，其中 n 是列表中的项目数。

List<'T>.Count 属性返回当前保存在集合中的项目数，List<'T>.Capacity 集合返回底层数组的大小。以下代码示例演示了如何调整底层数组的大小

open System
open System.Collections.Generic

let items = new List<string>()

let printList (l : List<_>) =
    printfn "l.Count: %i, l.Capacity: %i" l.Count l.Capacity
    printfn "Items:"
    l |> Seq.iteri (fun index item ->
        printfn "    l.[%i]: %s" index l.[index])
    printfn "-----------"

let main() =
    printList items
    
    items.Add("monkey")
    printList items
    
    items.Add("kitty")
    items.Add("bunny")
    printList items
    
    items.Add("doggy")
    items.Add("octopussy")
    items.Add("ducky")
    printList items
    
    printfn "Removing entry for \"doggy\"\n--------\n"
    items.Remove("doggy") |> ignore
    printList items
    
    printfn "Removing item at index 3\n--------\n"
    items.RemoveAt(3)
    printList items
    
    Console.ReadKey(true) |> ignore
            
main()

l.Count: 0, l.Capacity: 0
Items:
-----------
l.Count: 1, l.Capacity: 4
Items:
    l.[0]: monkey
-----------
l.Count: 3, l.Capacity: 4
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
-----------
l.Count: 6, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: doggy
    l.[4]: octopussy
    l.[5]: ducky
-----------
Removing entry for "doggy"
--------

l.Count: 5, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: octopussy
    l.[4]: ducky
-----------
Removing item at index 3
--------

l.Count: 4, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: ducky
-----------

如果事先知道列表的最大大小，可以通过调用 List<'T>(size : int) 构造函数来避免性能下降。以下示例演示了如何在不调整内部数组大小的情况下将 1000 个项目添加到列表中

> let myList = new List<int>(1000);;

val myList : List<int>

> myList.Count, myList.Capacity;;
val it : int * int = (0, 1000)
> seq { 1 .. 1000 } |> Seq.iter (fun x -> myList.Add(x));;
val it : unit = ()
> myList.Count, myList.Capacity;;
val it : int * int = (1000, 1000)

`LinkedList<'T>` 类

LinkedList<'T> 表示一个双向链接的节点序列，它允许高效的 O(1) 插入和删除，支持向前和向后遍历，但它的实现阻止了高效的随机访问。链接列表具有一些有价值的方法

(* Prepends an item to the LinkedList *)
val AddFirst : 'T -> LinkedListNode<'T>

(* Appends an items to the LinkedList *)
val AddLast : 'T -> LinkedListNode<'T>

(* Adds an item before a LinkedListNode *)
val AddBefore : LinkedListNode<'T> -> 'T -> LinkedListNode<'T>

(* Adds an item after a LinkedListNode *)
val AddAfter : LinkedListNode<'T> -> 'T -> LinkedListNode<'T>

请注意，这些方法返回一个 LinkedListNode<'T>，而不是一个新的 LinkedList<'T>。添加节点实际上会更改 LinkedList 对象

> open System.Collections.Generic;;
> let items = new LinkedList<string>();;

val items : LinkedList<string>

> items.AddLast("AddLast1");;
val it : LinkedListNode<string>
= System.Collections.Generic.LinkedListNode`1[System.String]
    {List = seq ["AddLast1"];
     Next = null;
     Previous = null;
     Value = "AddLast1";}
> items.AddLast("AddLast2");;
val it : LinkedListNode<string>
= System.Collections.Generic.LinkedListNode`1[System.String]
    {List = seq ["AddLast1"; "AddLast2"];
     Next = null;
     Previous = System.Collections.Generic.LinkedListNode`1[System.String];
     Value = "AddLast2";}
> let firstItem = items.AddFirst("AddFirst1");;

val firstItem : LinkedListNode<string>

> let addAfter = items.AddAfter(firstItem, "addAfter");;

val addAfter : LinkedListNode<string>

> let addBefore = items.AddBefore(addAfter, "addBefore");;

val addBefore : LinkedListNode<string>

> items |> Seq.iter (fun x -> printfn "%s" x);;
AddFirst1
addBefore
addAfter
AddLast1
AddLast2

Stack<'T> 和 Queue<'T> 类是链接列表的特例（可以认为它们是链接列表，但对可以在哪里添加和删除项目有限制）。

`Stack<'T>` 类

Stack<'T> 仅允许程序员在列表的开头添加/推入和删除/弹出项目，这使其成为一个后进先出 (LIFO) 数据结构。Stack<'T> 类可以被认为是 F# 列表的可变版本。

> stack.Push("First");; (* Adds item to front of the list *)
val it : unit = ()
> stack.Push("Second");;
val it : unit = ()
> stack.Push("Third");;
val it : unit = ()
> stack.Pop();; (* Returns and removes item from front of the list *)
val it : string = "Third"
> stack.Pop();;
val it : string = "Second"
> stack.Pop();;
val it : string = "First"

可以用这种数据结构表示一叠硬币。如果我们将硬币一层叠一层地叠起来，堆栈中的第一枚硬币在堆栈的底部，堆栈中的最后一枚硬币出现在顶部。我们从上到下移除硬币，所以最后添加到堆栈的硬币是最先移除的硬币。

`Queue<'T>` 类

Queue<'T> 仅允许程序员将项目追加/入队到列表的末尾，并从列表的开头删除/出队，这使其成为一个先进先出 (FIFO) 数据结构。

> let queue = new Queue<string>();;

val queue : Queue<string>

> queue.Enqueue("First");; (* Adds item to the rear of the list *)
val it : unit = ()
> queue.Enqueue("Second");;
val it : unit = ()
> queue.Enqueue("Third");;
val it : unit = ()
> queue.Dequeue();; (* Returns and removes item from front of the queue *)
val it : string = "First"
> queue.Dequeue();;
val it : string = "Second"
> queue.Dequeue();;
val it : string = "Third"

一队人可以用队列来表示：人们把自己添加到队列的末尾，并从队列的开头移除。第一个站在队列中的人是第一个被服务的人。

`HashSet<'T>` 和 `Dictionary<'TKey, 'TValue>` 类

HashSet<'T> 和 Dictionary<'TKey, 'TValue> 类是 F# 集合和映射数据结构的可变模拟，并包含许多相同的功能。

使用 HashSet<'T>

open System
open System.Collections.Generic

let nums_1to10 = new HashSet<int>()
let nums_5to15 = new HashSet<int>()

let main() =
    let printCollection msg targetSet =
        printf "%s: " msg
        targetSet |> Seq.sort |> Seq.iter(fun x -> printf "%O " x)
        printfn ""
        
    let addNums min max (targetSet : ICollection<_>) =
        seq { min .. max } |> Seq.iter(fun x -> targetSet.Add(x))
        
    addNums 1 10 nums_1to10
    addNums 5 15 nums_5to15
    
    printCollection "nums_1to10 (before)" nums_1to10
    printCollection "nums_5to15 (before)" nums_5to15
    
    nums_1to10.IntersectWith(nums_5to15) (* mutates nums_1to10 *)
    printCollection "nums_1to10 (after)" nums_1to10
    printCollection "nums_5to15 (after)" nums_5to15
    
    Console.ReadKey(true) |> ignore
            
main()

nums_1to10 (before): 1 2 3 4 5 6 7 8 9 10
nums_5to15 (before): 5 6 7 8 9 10 11 12 13 14 15
nums_1to10 (after): 5 6 7 8 9 10
nums_5to15 (after): 5 6 7 8 9 10 11 12 13 14 15

使用 Dictionary<'TKey, 'TValue>

> open System.Collections.Generic;;
> let dict = new Dictionary<string, string>();;

val dict : Dictionary<string,string>

> dict.Add("Garfield", "Jim Davis");;
val it : unit = ()
> dict.Add("Farside", "Gary Larson");;
val it : unit = ()
> dict.Add("Calvin and Hobbes", "Bill Watterson");;
val it : unit = ()
> dict.Add("Peanuts", "Charles Schultz");;
val it : unit = ()
> dict.["Farside"];; (* Use the '.[key]' operator to retrieve items *)
val it : string = "Gary Larson"

.NET BCL 与 F# 集合之间的差异

.NET BCL 中内置的集合与其 F# 模拟之间的主要区别当然在于可变性。BCL 集合的可变性会极大地影响其实现和时间复杂度

.NET 数据结构	插入	删除	查找	F# 数据结构	插入	删除	查找
`列表`	O(1) / O(n)*	O(n)	O(1)（按索引）/ O(n)（线性）	没有内置的等效项
`链接列表`	O(1)	O(1)	O(n)	没有内置的等效项
`堆栈`	O(1)	O(1)	O(n)	`列表`	O(1)	n/a	O(n)
`队列`	O(1)	O(1)	O(n)	没有内置的等效项
`哈希集`	O(1) / O(n)*	O(1)	O(1)	`集合`	O(log n)	O(log n)	O(log n)
`字典`	O(1) / O(n)*	O(1)	O(1)	`映射`	O(log n)	O(log n)	O(log n)

* 这些类构建在内部数组之上。当添加项目时，它们可能会遇到性能下降，因为内部数组会定期调整大小。

注意：上面的大 O 符号指的是插入/删除/检索操作相对于数据结构中项目数量的时间复杂度，而不是相对于其他数据结构评估操作所需时间的相对数量。例如，按索引访问数组与按键访问字典具有相同的时间复杂度，O(1)，但操作不一定在相同的时间内发生。

前一页：数组

索引

下一页：输入和输出

List<'T> 类

底层实现

LinkedList<'T> 类

Stack<'T> 类

Queue<'T> 类

HashSet<'T> 和 Dictionary<'TKey, 'TValue> 类