Неизменяется или не является неизменным?

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

Поэтому я мог бы создать следующий 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> действительно является неизменным типом, учитывая все, что влечет за собой неизменный тип.

Ответы

Ответ 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 является единственным типом, который по-настоящему считается неизменным?

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

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

mylist.Add(1);

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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