Before we move on to other kinds of immutable data structures, some miscellany about how we might improve on the
ImmutableStack<T> we already have - or perhaps just do things differently. All of these observations were submitted by blog readers - thanks everyone for the feedback.
We created a predicate for testing to see if an
ImmutableStack<T> contains any elements or not, a property called
For clarity, we might want to instead call this property
IsEmpty, making it clearer to the reader that this is a query that tells us about the stack, not a command that changes it.
Our stacks have a command for throwing away the top item of the stack, revealing the item beneath (if any). We called this command
It turns out that there is considerable precedence for calling this command
Pop() even though it differs from the classic definition of a queue because doesn’t return the top item.
I’m not quite sure on which side of this decision I fall - on the one hand, using a different name for the command might improve clarity, given that the semantics of the command are subtly different from the usual
Pop(). But, on the other hand, developers expect to have a method called
Pop() and some might be thrown if there isn’t one available.
While we have implemented
IEnumerable, we haven’t implemented any explicit
Count property, forcing any consumer to iterate through the stack to get the number of elements.
It may be worth adding
Count as a property so that obtaining the size of the stack becomes a trivial operation - we can calculate the size of the stack in our constructor as a performance optimization.
The down side is that we’ll be increasing the memory footprint very slightly. This may have no discernable effect.
There are some data structures that use stacks as building blocks and these sometimes require a
Reverse() method that takes one stack and returns another with all the items in the reverse order.
One way to implement this would be to define it on our base interface
IImmutableStack<T>. However, this would require every implementation to rewrite essentially the same algorithm; a better approach might be to create an extension method that can be used with any stack.
One reader wondered whether the precalculation of the hash code in the constructor for every instance of
SimpleImmutableStack was appropriate.
Performing the calculation of
GetHashCode() on demand, whenever required, would reduce the size of each instance, possibly saving memory (though, only if the memory allocator isn’t rounding the size up to a boundary size anyway).
Deferring the calculation until later, by using
Lazy<T> to calculate the hash code the first time it is needed, would increase memory allocation (for the instance of
In either case, using the hashcode becomes more expensive and it would probably be appropriate to remove the optimization we added to our equality testing.
On balance, I’d suggest that calculation in the constructor is appropriate - it’s a single bitwise calculation (fast), requires access to data already referenced (and therefore likely already in the processor’s memory caches), and the optimization for equality testing is beneficial.
IImmutableStack<T> implementations be marked as sealed?
Some suggest that sealing a class gives the compiler more opportunity for micro-optimization, but others contend that any benefit is so small as to be meaningless.
There is value, however, in marking the implementations as sealed from a communication perspective. Marking our implementations as sealed is an easy way to inform any maintenance developer about our intentions.