Comparison of Standard Containers

This is a rough comparison of the different container types provided by the OCaml standard library. In each case, n is the number of valid elements in the container.

Note that the big-O cost given for some operations reflects the current implementation but is not guaranteed by the official documentation. Hopefully it will not become worse. Anyway, if you want more details, you can read the documentation about each of the modules or the OCaml source code. Often, it is also instructive to read the corresponding implementation.

Lists: Immutable Singly-Linked Lists

Adding an element always creates a new list l from an element x List tl. tl remains unchanged, but it is not copied either.

• Adding an element: O(1), cons operator ::
• Length: O(n), function List.length
• Accessing cell i: O(i)
• Finding an element: O(n)

Well-suited for: I/O, pattern-matching

Not very efficient for: random access, indexed elements

Arrays: Mutable Vectors

Arrays are mutable data structures with a fixed length and random access.

• Adding an element (by creating a new array): O(n)
• Length: O(1), function Array.length
• Accessing cell i: O(1)
• Finding an element: O(n)

Well-suited for the following cases: dealing with sets of elements of known size, accessing elements by numeric index, and modifying in-place elements. Basic arrays have a fixed length.

Strings: Immutable Vectors

Strings are very similar to arrays, but they are immutable. Strings are specialised for storing chars (bytes) and have some convenient syntax. Strings have a fixed length. For extensible strings, the standard buffer module can be used (see below).

• Adding an element (by creating a new string): O(n)
• Length: O(1)
• Accessing character i: O(1)
• Finding an element: O(n)

Set and Map: Immutable Trees

Like lists, these are immutable, and they may share some subtrees. These trees are a good solution for keeping older versions of sets of items.

• Adding an element: O(log n)
• Returning the number of elements: O(n)
• Finding an element: O(log n)

Sets and maps are very useful in compilation and metaprogramming, but in other situations, hash tables are often more appropriate (see below).

Hashtbl: Automatically Growing Hash Tables

OCaml hash tables are mutable data structures, which are a good solution for storing (key, data) pairs in one single place.

• Adding an element: O(1) if the initial size of the table is larger than the number of elements it contains; O(log n) on average if n elements have been added in a table which is initially much smaller than n.
• Returning the number of elements: O(1)
• Finding an element: O(1)

Buffer: Extensible Strings

Buffers provide an efficient way to accumulate a byte sequence in a single place. They are mutable.

• Adding a char: O(1) if the buffer is big enough, or O(log n) on average if the initial buffer size was much smaller than the number of bytes n.
• Adding a string of k chars: O(k * "adding a char")
• Length: O(1)
• Accessing cell i: O(1)

Queue

OCaml queues are mutable first-in-first-out (FIFO) data structures.

• Adding an element: O(1)
• Taking an element: O(1)
• Length: O(1)

Stack

OCaml stacks are mutable last-in-first-out (LIFO) data structures. They are just like lists except they are mutable, i.e., adding an element doesn't create a new stack but simply adds it to the stack.

• Adding an element: O(1)
• Taking an element: O(1)
• Length: O(1)