Skip to content
Tutorials Center
My learning

Topics

C# Reference ยท Collections

Immutable collections

Reference for System.Collections.Immutable: ImmutableList, ImmutableArray, ImmutableDictionary, builders, structural sharing, and when to use them.

The System.Collections.Immutable namespace provides collections that can never change after they are created. Every "modifying" method, such as Add or Remove, leaves the original untouched and returns a new collection with the change applied. That makes them safe to share between threads without locks and easy to reason about: a snapshot stays a snapshot.

The main types are ImmutableArray<T>, ImmutableList<T>, ImmutableDictionary<TKey,TValue>, ImmutableHashSet<T>, ImmutableSortedDictionary<TKey,TValue>, ImmutableSortedSet<T>, ImmutableQueue<T> and ImmutableStack<T>. The library ships with .NET, so no extra package is needed.

C#
using System.Collections.Immutable;

ImmutableList<int> a = ImmutableList.Create(1, 2, 3);
ImmutableList<int> b = a.Add(4);   // a is still 1, 2, 3

Try it

C# Changes return new collections

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

C# Builders for bulk changes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Syntax

C#
// Each type has a static factory class of the same name without <T>
ImmutableList<T>        ImmutableList.Create<T>(params T[] items);
ImmutableArray<T>       ImmutableArray.Create<T>(params T[] items);
ImmutableDictionary<TKey,TValue> ImmutableDictionary.Create<TKey,TValue>();
ImmutableHashSet<T>     ImmutableHashSet.Create<T>(params T[] items);

// Conversions from IEnumerable<T>
ToImmutableList(), ToImmutableArray(), ToImmutableDictionary(...),
ToImmutableHashSet(), ToImmutableSortedSet(), ToImmutableSortedDictionary(...)
Type Behaves like Typical cost of Add
ImmutableArray<T> T[] (a struct wrapper) O(n), copies the array
ImmutableList<T> List<T> (balanced tree) O(log n)
ImmutableDictionary<TKey,TValue> Dictionary<TKey,TValue> O(log n)
ImmutableHashSet<T> HashSet<T> O(log n)
ImmutableSortedSet<T> SortedSet<T> O(log n)
ImmutableQueue<T>, ImmutableStack<T> Queue<T>, Stack<T> O(1) amortized

Returns: methods such as Add, AddRange, Remove, Insert, SetItem and Sort return a new collection; if nothing would change, many return the same instance.

Errors: the usual argument exceptions (duplicate keys in ImmutableDictionary.Add throw ArgumentException, but adding the same key with the same value is allowed). A default(ImmutableArray<T>) throws NullReferenceException or InvalidOperationException when used.

Usage notes

  • Ignoring the result is a bug. list.Add(4); on an immutable list does nothing useful. The compiler may warn; always assign the returned collection.
  • Structural sharing. The tree-based types reuse most nodes between versions, so a new version shares memory with the old one. That is why Add is O(log n), not O(n).
  • ImmutableArray<T> is the fast read type. It is a struct around a plain array, so indexing and iteration are as quick as an array. Changes are O(n) copies. Use builders when assembling it.
  • ImmutableList<T> is slower to read than List<T>: indexing is O(log n) and iteration allocates less friendly nodes. Prefer it only when you need cheap versions.
  • Immutable is not deep. The collection is fixed, but the objects inside can still be mutable. Store immutable items (records, strings) for real safety.
  • Thread safety. Readers never need locks. To update a shared reference from several threads, use ImmutableInterlocked.Update or Interlocked.CompareExchange.
  • Alternatives. ReadOnlyCollection<T> is only a read-only view over a list that can still change; FrozenDictionary is a build-once, read-fast collection.