標準容器比較
這是對 OCaml 標準函式庫提供的不同容器類型的大致比較。在每種情況下，n 是容器中有效元素的數量。
請注意，某些操作的 big-O 成本反映了目前的實現，但官方文件並未保證。希望它不會變得更糟。無論如何，如果您想了解更多詳細資訊，您可以閱讀有關每個模組的文件或 OCaml 的原始碼。通常，閱讀相應的實現也很有啟發性。
Lists：不可變的單向鏈結串列
新增元素總是會從元素 x 和列表 tl 建立一個新的列表 l。tl 保持不變，但也不會被複製。
- 新增元素：O(1)，cons 運算子
:: - 長度：O(n)，函式
List.length - 存取單元格
i：O(i) - 尋找元素：O(n)
適用於：I/O、模式比對
對於以下情況效率不高：隨機存取、索引元素
Arrays：可變的向量
陣列是具有固定長度和隨機存取的可變資料結構。
- 新增元素（透過建立新陣列）：O(n)
- 長度：O(1)，函式
Array.length - 存取單元格
i：O(1) - 尋找元素：O(n)
適用於以下情況：處理已知大小的元素集、透過數字索引存取元素，以及就地修改元素。基本陣列具有固定長度。
Strings：不可變的向量
字串與陣列非常相似，但它們是不可變的。字串專門用於儲存字元（位元組），並具有一些方便的語法。字串具有固定長度。對於可擴展字串，可以使用標準的緩衝區模組（見下文）。
- 新增元素（透過建立新字串）：O(n)
- 長度：O(1)
- 存取字元
i：O(1) - 尋找元素：O(n)
Set 和 Map：不可變的樹
與列表一樣，這些是不可變的，並且它們可能共享一些子樹。這些樹是保留舊版本的項目集合的好解決方案。
- 新增元素：O(log n)
- 傳回元素數量：O(n)
- 尋找元素：O(log n)
集合和映射在編譯和元編程中非常有用，但在其他情況下，雜湊表通常更合適（見下文）。
Hashtbl：自動增長的雜湊表
OCaml 雜湊表是可變的資料結構，它們是在一個地方儲存 (key, data) 配對的好解決方案。
- 新增元素：O(1) 如果表格的初始大小大於它包含的元素數量；如果將 n 個元素新增到最初比 n 小得多的表格中，則平均為 O(log n)。
- 傳回元素數量：O(1)
- 尋找元素：O(1)
Buffer：可擴展字串
緩衝區提供了一種在單個位置累積位元組序列的有效方法。它們是可變的。
- 新增字元：如果緩衝區足夠大，則為 O(1)，或者如果初始緩衝區大小遠小於位元組數 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)