标准容器的比较

这是对OCaml标准库所提供的不同容器的一个粗略的比较。以下的n代表容器中元素的数量。

值得注意的是，大O所代表的是当前实现下的效率，并不为官方文档保证。希望以后这些实现不会 变得更糟糕吧。总之，文档才是理解这些模块最好的来源。当然，你也可以尝试阅读源代码。

Lists: 不可变的单链表

添加一个元素会创建一个新的链表l，从x指向链表tl。tl不会被改变，因此不会被拷贝。

• 添加一个元素： O(1), cons 操作符 ::
• 长度： O(n), List.length
• 索引第i个元素: O(i)
• 寻找一个元素: O(n)

这个结构比较适合IO和模式匹配。

但不太适合索引。

数组和字符串：可变数组

数组和字符串很相似。只不过字符串是用来紧凑地存贮字符，和一些方便的语法而已。

• 添加一个元素： O(n)
• 长度： O(1), Array.length
• 索引第i个元素: O(1)
• 寻找一个元素: O(n)

比较适合一些已知大小的元素，下标索引，和在位编辑。数组和字符串的长度都是固定的。如果你想改变 字符串的长度，Buffer模块比较合适。

Set 和 Map：不可变的树

如链表，他们都是不可变的，但是他们有可能共享一些子树。他们比较适合用于保存一些旧版本的数据。

• 添加一个元素： O(log n)
• 返回元素的数量: O(n)
• 寻找一个元素: O(log n)

集合和映射对于编译和元编程(meta-programming)都很有用，但是在某些情况，哈希表会更加合适。

Hashtbl: 自动增长的哈希表

Ocaml的哈希表是可变的，可以把键值存储在同一个数据结构。

• 添加一个元素：如果表的初始大小比元素数量要大，则是O(1)，如果往很小的表插入n个元素，则平均是O(log n)
• 返回元素的数量： O(1)
• 寻找一个元素： O(1)

Buffer: 可变长字符串

Buffer提供了一个有效的方式在一个数据结构中累计字节。他们是可变的，

• 添加一个元素：如果buffer足够大则是O(1)，如果buffer远远小于n，那么则平均是O(log n)。
• 添加一个 k 字符长的字符串: O(k * 添加一个元素)
• 长度: O(1)
• 索引第i个元素: O(1)

Queue

OCaml的队列是可变的FIFO，。

• 添加一个元素：O(1)
• 获取一个元素： O(1)
• 长度: O(1)

Stack

Ocaml的栈是可变的LIFO。他们除了可变以外和链表没有区别。

• 添加一个元素：O(1)
• 获取一个元素： O(1)
• 长度: O(1)