Immutable collections?

Question

I am making most of my basic types in my app, immutable. But should the collections be immutable too? To me, this seems like a huge overhead unless I am missing something.

I am talking about collections to hold Point3 values, etc which can be added as it goes at different times. So if there are 1M values in a collection, and you needed to delete 1 of them, you would have to create the same collection all over again, right?

Answer 1

You could define your public interface as IEnumerable, but still use a mutable collection in your implementation.

Answer 2

If you only ever add/remove from the start or end you might be able to cheat - but in general; yes: the implication is that you need to create a new collection for every change.

So: do you need to (effectively) mutate collections? If so, and given their size: I'd be tempted to look at synchronizing access (rather than making them properly immutable). Look at lock (aka Monitor).

Answer 3

It depends on the style your program is written/designed.

Immutable collection do only make sense when you're programming in a functional-programming-influenced style (Imperatively designed programs shouldn't use them).

And like in functional languages, you should use Linked Lists then which can be built up in O(1) per element (cons) and process them functionally (recursions, building new lists from lists).

When your program requires imperative collections (arrays, vectors/lists), keep them mutable.

Answer 4

Eric Lippert has a series on Immutability in C#, and if you read it all the way through he implements a couple different immutable collections:

1. Immutability in C# Part One: Kinds of Immutability
2. Immutability in C# Part Two: A Simple Immutable Stack
3. Immutability in C# Part Three: A Covariant Immutable Stack
4. Immutability in C# Part Four: An Immutable Queue
5. Immutability in C# Part Five: LOLZ!
6. Immutability in C# Part Six: A Simple Binary Tree
7. Immutability in C# Part Seven: More on Binary Trees
8. Immutability in C# Part Eight: Even More On Binary Trees
9. Immutability in C# Part Nine: Academic? Plus my AVL tree implementation
10. Immutability in C# Part Ten: A double-ended queue
11. Immutability in C# Part Eleven: A working double-ended queue

Answer 5

I agree with Eric's comments about choosing the right tool for the problem. Immutability adds value when your goals include providing clear identity semantics, or making your implementation easier to work with in a parallel computing environment. Immutability can also help improve performance by allowing optimizations such as caching or transparent proxying.

On the flip-side, immutability can also incur a performance cost - particularly when you use the "copy-on-write" pattern to model "changes".

You have to decide why you want your entities/collections to be immutable - and that will help drive your decision of whether to do so or not.

Answer 6

It all depends on who is using the collections at the same time. Strings are immutable to prevent boo-boo's like two threads trying to remove the first char at the same time.