标准容器的比较
这是对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)