std::array is not really comparable since its size is fixed at compile time. std::vector or std::list are more similar.

The big advantage is creating copies. Copying a list or vector is O(n) in both time and memory, while this is O(1) in both.

An std::shared_ptr to a const list or vector is O(1) in both for copies. But almost any modifications will be O(n).

For this data structure, almost all operations are O(log(n)).

A summary of their algorithmic complexities:

  Copy:
  std::vector : O(n) time and memory
  std::shared_ptr<const std::vector> : O(1) time and memory
  immutable::Array : O(1) time and memory

  Append:
  std::vector : Amortized O(1)
  std::shared_ptr<const std::vector> : O(n)
  immutable::Array : O(log(n))

  Access at index:
  std::vector : O(1)
  std::shared_ptr<const std::vector> : O(1)
  immutable::Array : O(log(n))

  Insert at index:
  std::vector : O(n)
  std::shared_ptr<const std::vector> : O(n)
  immutable::Array : O(log(n))

  Replace at index:
  std::vector : O(1)
  std::shared_ptr<const std::vector> : O(n)
  immutable::Array : O(log(n))

Well, when you pass a variable around, it doesn't and cannot change. This means that different threads can't get in eachothers' way anymore, for instance, but also that you can't make a big chunk of mistakes at all.

They also have serious disadvantages : they can't be memory managed in the traditional way (since they tend to reuse other instances' memory in complex ways), and thus require a GC (refcounting can work, but ...). They are VERY allocation intensive, and they are worse than most non-persistent data structures. Assuming an O(1) allocator they can match non-persistent data structures in O-ness (ie. when making an invalid assumption that is quite popular in academia. In practice memory allocation is O(1) for small values, then O(n^2) once you get close to the system's memory capacity (scanning for holes in a long list) but don't go over it, and then O(oh fuck it let's just reboot this bloody BOAT ANCHOR) when crossing that line).

Clojure is famous for having good persistent data structures. Rich Hickey went touring academia touting the benefits of immutable/persistent/functional data structures : https://www.youtube.com/watch?v=dGVqrGmwOAw&feature=youtu.be...

There's also a famous book: https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...