标准容器比较
这是对 OCaml 标准库提供的不同容器类型的一个粗略比较。在每种情况下，n 是容器中有效元素的数量。
请注意，某些操作的 Big-O 成本反映了当前实现，但没有得到官方文档的保证。希望它不会变得更糟。无论如何，如果您需要更多详细信息，您可以阅读有关每个模块的 文档 或 OCaml 源代码。通常，阅读相应的实现也很有启发性。
列表：不可变单链表
添加元素总是从元素 x 和列表 tl 创建一个新列表 l。tl 保持不变，但也不会被复制。
- 添加元素：O(1)，cons 运算符
:: - 长度：O(n)，函数
List.length - 访问单元格
i：O(i) - 查找元素：O(n)
适用于：I/O，模式匹配
不适用于：随机访问，索引元素
数组：可变向量
数组是可变数据结构，具有固定长度和随机访问。
- 添加元素（通过创建新数组）：O(n)
- 长度：O(1)，函数
Array.length - 访问单元格
i：O(1) - 查找元素：O(n)
适用于以下情况：处理已知大小的元素集、通过数字索引访问元素以及就地修改元素。基本数组具有固定长度。
字符串：不可变向量
字符串与数组非常相似，但它们是不可变的。字符串专门用于存储字符（字节）并具有一些便捷的语法。字符串具有固定长度。对于可扩展字符串，可以使用标准缓冲区模块（见下文）。
- 添加元素（通过创建新字符串）：O(n)
- 长度：O(1)
- 访问字符
i：O(1) - 查找元素：O(n)
集合和映射：不可变树
与列表一样，它们是不可变的，并且它们可能共享一些子树。这些树是保存较旧版本项目集的良好解决方案。
- 添加元素：O(log n)
- 返回元素数量：O(n)
- 查找元素：O(log n)
集合和映射在编译和元编程中非常有用，但在其他情况下，哈希表通常更合适（见下文）。
Hashtbl：自动增长的哈希表
OCaml 哈希表是可变数据结构，是将（键，数据）对存储在同一个地方的良好解决方案。
- 添加元素：如果表的初始大小大于它包含的元素数量，则为 O(1)；如果在初始大小远小于 n 的表中添加了 n 个元素，则平均为 O(log n)。
- 返回元素数量：O(1)
- 查找元素：O(1)
缓冲区：可扩展字符串
缓冲区提供了一种有效的方式在一个地方累积字节序列。它们是可变的。
- 添加一个字符：如果缓冲区足够大，则为 O(1)；如果初始缓冲区大小远小于字节数 n，则平均为 O(log n)。
- 添加一个包含 k 个字符的字符串：O(k * “添加一个字符”)
- 长度：O(1)
- 访问单元格
i：O(1)
队列
OCaml 队列是可变先进先出 (FIFO) 数据结构。
- 添加元素：O(1)
- 获取元素：O(1)
- 长度：O(1)
栈
OCaml 栈是可变后进先出 (LIFO) 数据结构。它们就像列表一样，只是它们是可变的，即添加元素不会创建新的栈，而是简单地将其添加到栈中。
- 添加元素：O(1)
- 获取元素：O(1)
- 长度：O(1)