可变与不可变

Question

要使可变 class 不可变，应该考虑什么？例如：我们仍然可以在不可变堆栈 class 中使用 push 和 pop 方法吗？或者我们应该简单地删除任何改变实例化对象状态的方法？

Answer 1

如果您的堆栈是不可变的，那么根据定义它就不能更改。 push() 和 pop() 方法无法完成。

当方法无法成功完成时，可以抛出异常。当方法 never 成功完成时，抛出的标准异常是 UnsupportedOperationException.

例如：

public E[] push (E e) {
    throw new UnsupportedOperationException();
}

编辑：

您在评论中注意到您的 push() 方法只是返回包含新元素的堆栈的深层副本。看起来您将不可变堆栈表示为 class 的实例，并将推送的堆栈表示为数组。

你可以用newElements.length得到newElements引用的两个数组之一的大小。所以你可以这样写代码：

public E[] push (E e) {
   E[] newElements=getNewElements();
   int oldLength = newElements.length;
   newElements=ensureCapacity(newElements);
   int lastIndexInNewArray = oldLength;
   newElements[ lastIndexInNewArray ] = e;
   return newElements;
}

Answer 2

底线是：您最好从class中删除修改实例化对象状态的方法。但是如果你想保留它，那么它应该创建一个状态与原始对象不同的新对象，然后 return 新对象返回。

这里有一个更具体的答案：

在不可变的 class 中不应该有任何方法改变对象状态。

有很多 void 方法可以在可变 class 中更改此对象的状态。所以我们应该以 return 新对象的方式更改它们的签名，而不是更改 "this" 对象的状态。

还有很多非 void 方法可以改变 "this" 对象的状态和 return 它们在 "this" 中改变的值。这些方法的签名也应该以 return 一个新对象而不是更改 "this" 的状态的方式进行更改。谈到列表，通常还需要另一种方法（如 "peek"）来获取某个值。检查下面的示例以了解我的意思：

查看可变堆栈的这些 "push" 和 "pop" 方法 class:

public class Stack <E> {
…
public void push (E e) {
     ensureCapacity();  // This method checks for capacity
     elements[size++] = e;
   }

此方法在堆栈顶部添加一个新元素并以这种方式更改 "this" 对象的状态。

public E pop () {
     if (size == 0) throw new IllegalStateException("Stack.pop");
     E result = elements[--size];
     elements[size] = null;
     return result;
   }
…
}

此方法删除堆栈顶部的元素，然后 return 将其返回并通过删除元素更改 "this" 对象的状态。

现在，假设我们需要更改这些方法以使该堆栈不可变。让我们先处理 "push" 方法：

"push" 是一个 void 方法，它通过向对象添加新元素来更改 "this" 对象的状态。为了使堆栈不可变，我们将创建一个类似于 "this" 的新堆栈，并将新元素添加到这个新堆栈中，然后 return 返回：

public class ImmStack <E> {
...
    /**
     * this method pushes the item to a new object and keeps the original object unchanged 
     * @param e The item to be pushed
     * @return A new list
     * @PRE An original list object is required as well as an item to be pushed
     * @POST A new list would be returned
     */
    @SuppressWarnings({ "unchecked", "rawtypes" }) // All items in this.elements[] are of type E
    public ImmStack<E> push (E e) {

         ImmStack<E> stc = new ImmStack(getNewElements());       
         stc.elements=ensureCapacity(stc.elements);
         stc.elements[size] = e;
         stc.size = size +1;         
         return stc;
       }

"pop" 方法通过删除元素来更改 "this" 对象的状态。为了使 class 不可变，我们将重新创建一个类似于 "this" 的新堆栈，并从这个新堆栈中删除元素，然后 return 将其返回：

   /**
     * This pop method returns a new stack without the element at the top of the original list 
     * @return The new stack
     * @POST The new stack would be returned
     */
    @SuppressWarnings({ "unchecked", "rawtypes" }) // All items in this.elements[] are of type E
    public ImmStack<E> pop () {

        if (size == 0) throw new IllegalStateException("Stack.pop");

        ImmStack<E> stc = new ImmStack(getNewElements());        
         stc.elements=ensureCapacity(stc.elements);
         stc.elements[size-1] = null;
         stc.size=size-1;  
         return stc;
       }

旧的 "pop" 方法是 return 将元素放在顶部。我们还需要一个新方法，returns 顶部的元素来覆盖此功能：

   /**
    * Returns item at front of queue without removing.
    * @return item at front
    * @throws java.util.NoSuchElementException if empty
    */
   public E top()
   {
    if (this.isEmpty())
        {
        throw new NoSuchElementException("Queue underflow");
        }
       return elements[size-1];
   }

这只是一个例子。您可能有更多方法来更改 class 以使其不可变。

Answer 3

下面是 C# 中不可变栈的实现。

压入和弹出给你返回一个全新的堆栈，而 Peek 可以让你在不弹出堆栈的情况下查看堆栈的顶部。
请注意，不需要复制整个堆栈。

这就是在任何重要情况下实现不可变结构的方式。非平凡的不可变结构在某些情况下非常有用。说不能做到这一点的海报是错误的。

原始代码和更多信息可以在这里找到：
https://blogs.msdn.microsoft.com/ericlippert/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack/

public interface IStack<T> : IEnumerable<T>
{
    IStack<T> Push(T value);
    IStack<T> Pop();
    T Peek();
    bool IsEmpty { get; }
}

public sealed class Stack<T> : IStack<T>
{
    private sealed class EmptyStack : IStack<T>
    {
        public bool IsEmpty { get { return true; } }
        public T Peek() { throw new Exception("Empty stack"); }
        public IStack<T> Push(T value) { return new Stack<T>(value, this); }
        public IStack<T> Pop() { throw new Exception("Empty stack"); }
        public IEnumerator<T> GetEnumerator() { yield break; }
        IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
    }
    private static readonly EmptyStack empty = new EmptyStack();
    public static IStack<T> Empty { get { return empty; } }
    private readonly T head;
    private readonly IStack<T> tail;
    private Stack(T head, IStack<T> tail)
    {
        this.head = head;
        this.tail = tail;
    }
    public bool IsEmpty { get { return false; } }
    public T Peek() { return head; }
    public IStack<T> Pop() { return tail; }
    public IStack<T> Push(T value) { return new Stack<T>(value, this); }
    public IEnumerator<T> GetEnumerator()
    {
        for(IStack<T> stack = this; !stack.IsEmpty ; stack = stack.Pop())
            yield return stack.Peek();
    }
    IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator();}
}

可变与不可变

Mutable vs. Immutable

stack

mutable

immutability