Неизменный или не неизменный?

Question

Хорошо, насколько я понимаю, неизменяемые типы по своей природе являются поточно-ориентированными, поэтому я читал в разных местах и ​​думаю, что понимаю, почему это так. Если внутреннее состояние экземпляра не может быть изменено после создания объекта, кажется, нет проблем с одновременным доступом к самому экземпляру.

Поэтому я мог бы создать следующее List:

class ImmutableList<T>: IEnumerable<T>
{
    readonly List<T> innerList;

    public ImmutableList(IEnumerable<T> collection)
    {
         this.innerList = new List<T>(collection);
    }

    public ImmutableList()
    {
         this.innerList = new List<T>();
    }

    public ImmutableList<T> Add(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Add(item);
         return list;
    }

    public ImmutableList<T> Remove(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Remove(item);
         return list;
    } //and so on with relevant List methods...

    public T this[int index]
    {
        get
        {
            return this.innerList[index];
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return innerList.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((System.Collections.IEnumerable)this.innerList).GetEnumerator();
    }
}

Итак, вопрос: действительно ли это неизменный тип? Это действительно потокобезопасный?

Очевидно, что сам тип является неизменным , но нет абсолютно никакой гарантии, что T, и поэтому у вас могут возникнуть проблемы с параллельным доступом и потоками, связанные непосредственно с универсальным типом. Значит ли это, что ImmutableList следует считать изменяемым ?.

Должен ли class ImmutableList<T>: IEnumerable<T> where T: struct быть единственным типом, который действительно считается неизменным ?

Спасибо за любой вклад по этому вопросу.

ОБНОВЛЕНИЕ : Многие ответы / комментарии сосредоточены на конкретной реализации ImmutableList, которую я опубликовал, что, вероятно, не очень хороший пример. Но вопрос вопроса не в реализации. Я задаю вопрос: действительно ли ImmutableList<MutableT> является неизменным типом, учитывая все, что влечет за собой неизменный тип?

Answer 1

Если внутреннее состояние экземпляра не может быть изменено после создания объекта, похоже, что нет проблем с одновременным доступом к самому экземпляру.

Как правило, это так, да.

Это действительно неизменный тип?

Вкратце: у вас есть оболочка для копирования при записи вокруг изменяемого списка.Добавление нового члена в неизменяемый список не изменяет список;вместо этого он создает копию основного изменяемого списка, добавляет к копии и возвращает оболочку вокруг копии.

При условии, что базовый объект списка, который вы переносите, не изменяет свое внутреннее состояние при чтении из него, вы встретили свое первоначальное определение «неизменяемого», так что да.

Замечу, что это не очень эффективный способ реализации неизменяемого списка.Например, вы бы лучше справились с неизменным сбалансированным бинарным деревом.Ваш набросок O (n) во времени и памяти каждый раз, когда вы создаете новый список;Вы можете улучшить это до O (log n) без особых затруднений.

Действительно ли это потокобезопасно?

При условии, что основной изменяемый список является поточно-ориентированным для нескольких читателей, да.

Это может вас заинтересовать:

http://blogs.msdn.com/b/ericlippert/archive/2011/05/23/read-only-and-threadsafe-are-different.aspx

Очевидно, что сам тип является неизменяемым, но нет абсолютно никакой гарантии, что Tи, следовательно, могут возникнуть проблемы с параллельным доступом и потоками, связанные непосредственно с универсальным типом.Значит ли это, что ImmutableList<T> следует считать изменчивым?

Это философский вопрос, а не технический.Если у вас есть неизменный список имен людей, и этот список никогда не меняется, но один из людей умирает, был ли список имен «изменяемым»?Я бы подумал, что нет.

Список является неизменным, если любой вопрос о списке всегда имеет одинаковый ответ.В нашем списке имен людей "сколько имен в списке?"это вопрос по списку."Сколько из этих людей живы?"это не вопрос о списке, это вопрос о людях, упомянутых в списке.Ответ на этот вопрос со временем меняется;ответ на первый вопрос - нет.

Должен ли класс ImmutableList<T>: IEnumerable<T> where T: struct быть единственным типом, который действительно считается неизменным?

Я не следую за вами.Как ограничение T быть структурой меняет что-либо?Хорошо, T ограничен структурой.Я делаю неизменную структуру:

struct S
{
    public int[] MutableArray { get; private set; }
    ...
}

И теперь я делаю ImmutableList<S>.Что мешает мне изменить изменяемый массив, хранящийся в экземплярах S?Тот факт, что список неизменен, а структура неизменна, не делает массив неизменным.

Answer 2

Неизменяемость иногда определяется по-разному. Так что потокобезопасность.

При создании неизменяемого списка, цель которого состоит в том, чтобы быть неизменным, вы должны документально подтвердить, какие именно гарантии вы даете. Например. в этом случае вы гарантируете, что сам список является неизменным и не имеет скрытой изменчивости (некоторые явно неизменные объекты на самом деле являются изменяемыми за кулисами, например, с запоминанием или внутренней сортировкой в ​​качестве оптимизации), что устраняет возникающую потокобезопасность от неизменности (хотя можно также иметь такие внутренние мутации, выполненные таким образом, который гарантирует потокобезопасность другим способом). Вы не гарантируете, что хранимые объекты могут использоваться в поточно-ориентированном режиме.

Безопасность потока, которую вы должны документировать, относится к этому. Вы не можете гарантировать, что другой объект не будет иметь такой же объект (вы могли бы, если бы вы создавали новые объекты при каждом вызове). Вы можете гарантировать, что операции не повредят сам список.

Настаивать на T : struct может помочь, так как это будет означать, что вы можете быть уверены, что каждый раз, когда вы возвращаете элемент, это новая копия структуры (один T : struct не будет этого делать, так как вы можете иметь операции это не изменяло список, но изменяло его членов, так что, очевидно, вы должны сделать это).

Это ограничивает вас в том, что вы не поддерживаете неизменяемые ссылочные типы (например, string, который, как правило, является членом коллекций во многих реальных случаях), и не позволяет пользователю использовать его и предоставлять свои собственные средства обеспечения того, чтобы изменчивость содержащихся элементов не вызывала проблем. Поскольку ни один потокобезопасный объект не может гарантировать, что весь код, в котором он используется, является потокобезопасным, нет особого смысла пытаться это гарантировать (помогите, насколько можете, любыми средствами, но не пытайтесь гарантировать то, что можете ' т)).

Он также не защищает непостоянные члены неизменяемых структур в вашем неизменяемом списке!

Answer 3

Основной пример типа данных, который ведет себя как неизменный список изменяемых объектов: MulticastDelegate.MulticastDelegate может быть довольно точно смоделирован как неизменный список пар (объект, метод).Набор методов и идентичности объектов, на которые они действуют, являются неизменяемыми, но в подавляющем большинстве случаев сами объекты будут изменяемыми.Действительно, во многих, если не в большинстве случаев, самой целью делегата будет изменение объектов, на которые он ссылается.

Делегат не обязан знать,методы, которые он будет вызывать для своих целевых объектов, могут изменять их в небезопасном режиме.Делегат несет ответственность только за то, чтобы его списки функций и идентификаторов объектов были неизменными, и я не думаю, что кто-то ожидал бы, что это аналогично.

ImmutableList<T> также должен всегда содержать один и тот же набор экземпляровтипа T.Свойства этих экземпляров могут измениться, но не их идентичность.Если был создан List<Car> с двумя Фордами, серийными № 1234 и № 4422, оба из которых оказались красными, а один из Фордов был окрашен в синий, то, что начиналось как список двух красных автомобилей, изменилось бы насписок, содержащий синий автомобиль и красный автомобиль, но он все равно будет содержать # 1234 и # 4422.

Answer 4

Используя ваш код, допустим, я делаю это:

ImmutableList<int> mylist = new ImmutableList<int>();

mylist.Add(1); 

... ваш код, размещенный в StackOverflow, вызывает исключение StackOverflow-Exception. Есть довольно много разумных способов создать коллекцию сохранения потоков, копируя коллекции (по крайней мере, пытаясь) и называя их неизменяемыми, многие из них не совсем подходят.

Эрик Липперт опубликовал ссылку, которая, возможно, очень стоит прочитать.

Answer 5

Я бы сказал, что универсальный список не является неизменным, если элемент является изменяемым, поскольку он не представляет полный снимок состояния данных.

Для достижения неизменности в вашем примере вам потребуется создать глубокие копииэлементов списка, которые не всегда эффективны.

Мое решение этой проблемы вы можете увидеть в IOG library