Истинно неизменный словарь в .NET

Question

Доброе утро, день или ночь,

Все еще опираясь на мой вопрос о неизменяемых словарях в .NET, у меня возник следующий вопрос: а если тогда TKey и TValue - это типы значений, которые можно сделать словарем действительно неизменным, в том смысле, что ни его внутренняя структура, ни сами значения не могут измениться, если эти параметры ссылочные типы ключи и значения могут быть легко изменены, что приведет к изменениюсам словарь.Я прав?

Большое спасибо.

Answer 1

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

Не совсем так.Вы выявили реальную проблему, но ваша характеристика ее не до конца продумана.

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

Однако, даже если тип значения сам по себе неизменен тип неизменяемого значенияможет содержать ссылку на изменяемый тип ссылки , и теперь у нас та же проблема.Ограничение словаря типами значений только отталкивает проблему от уровня, но не решает ее!Что вам действительно нужно для гарантии «глубокой» неизменности, так это словарь типов значений blittable .Под «blittable» я подразумеваю тип значения без полей ссылочного типа.(Так называемый, потому что вы можете сериализовать один из них в хранилище, «перетаскивая» биты прямо на диск.)

К сожалению, в системе универсальных типов нет ограничений, ограничивающих blittable типы значений.

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

Ну, первое, что приходит на ум, это то, что неизменный словарь должен давать один и тот же ответ дваждыодин и тот же вопрос дважды, и теперь это уже не так.Если вы скажете «клиенты [имя]. Адрес», вы ожидаете получить один и тот же ответ дважды, но если клиент является ссылочным типом, который может изменяться, вы получите потенциально другой ответ.Это может быть или не быть желательным.(И обратите внимание, что словарь дает один и тот же ответ дважды: он дает одну и ту же ссылку на объект customer. На самом деле это объект customer, который не дает один и тот же ответ дважды.)

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

Большая проблема возникает, когда объект, который находится в хэш-таблице в качестве ключа, видоизменяется, изменяя тем самымего хэш-значение и «потеря» объекта в таблице.

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

Answer 2

Взгляните на новые неизменные коллекции BCL: http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx

Это предварительная версия, но она содержит следующие типы:

• ImmutableStack<T>
• ImmutableQueue<T>
• ImmutableList<T>
• ImmutableHashSet<T>
• ImmutableSortedSet<T>
• ImmutableDictionary<K, V>
• ImmutableSortedDictionary<K, V>

Мне бы хотелось, чтобы в следующей версии C # были включены ключевые слова для определения ограничений неизменяемости на уровне класса (аналогично тому, что предлагается здесь ), а также способ клонирования объектов подробнее.легко, например , что можно сделать в F # с ключевым словом with:

var o1 = new CustomObject { Field1 = 0, Field2 = 3 }
var o2 = o1 with { Field1 = 1} 

Answer 3

Структуры являются типами значений и не обязательно являются неизменяемыми, поэтому ответ - нет. Вы можете создавать неизменяемые типы (сделать все поля и свойства доступными только для чтения). Однако нет доступных ограничений типа (например, where TKey : class), которые позволили бы вам применять их.

Обновление : Пример:

class Bar { public int I; }
struct Foo { public Bar B; }

var b = new Bar();
var f = new Foo { B = b; }

dict[key] = f;
b.I++;

Немного сконструировано, я признаю.

Answer 4

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

[Immutable]
class ImmutableDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
    public ImmutableDictionary(IEnumerable<KeyValuePair<TKey, TValue>> keysValues)
    {
        // Ensure TKey is immutable...
        if (typeof(TKey).GetCustomAttribute(typeof(ImmutableAttribute), false).Length == 0)
            throw new InvalidOperationException(String.Format("Type '{0}' must be immutable.", typeof(TKey).AssemblyQualifiedName);

        // Ensure TValue is immutable...
        if (typeof(TValue).GetCustomAttribute(typeof(ImmutableAttribute), false).Length == 0)
            throw new InvalidOperationException(String.Format("Type '{0}' must be immutable.", typeof(TValue).AssemblyQualifiedName);

        foreach(var keyValue in keysValues)
            base.Add(keyValue.Key, keyValue.Value);
    }

    public new void Add(TKey key, TValue value)
    {
        throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
    }

    public new void Clear()
    {
        throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
    }

    public new void Remove(TKey key)
    {
        throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
    }

    public TValue this[TKey key]
    {
        get { return base[key]; }
        set
        {
            throw new InvalidOperationException("Cannot modify contents of immutable dictionary.");
        }
    }
}

Answer 5

взгляните на это: http://ayende.com/blog/164739/immutable-collections-performance Кстати, будьте осторожны при использовании ImmutableDictionary

Answer 6

Чтобы понять, что происходит, перейдите к типу, более простому, чем словарь: a List<T>.Если кто-то создает List<T>, бросает в него некоторые элементы, затем создает, передает его конструктору ReadOnlyCollection<T> и уничтожает все ссылки на этот список, кроме той, которая содержится в ReadOnlyCollection<T>, тогда этот список будет неизменным.Его состояние никогда не изменится, независимо от того, является ли T изменяемым или неизменным, классом или структурой.Любой, кто рассматривает такой список как изменяемый, если T является изменяемым типом класса, терпит неудачу, ошибочно рассматривает список как содержащий объекты.Это не так.

Если T является типом класса, List<T> не содержит объекты - он идентифицирует их. Если List<int[]> сделан неизменным, как описано выше, после того, как к нему добавлено пять ссылок на массив int, то, пока он существует, он всегда будет содержать ссылки на те же самые пять массивов.Содержимое массивов может измениться, но свойства объектов, на которые ссылается List<T>, не являются частью состояния списка .

Состояние Dictionary<TKey,TValue> являетсяего немного сложнее определить, чем состояние List<T>, особенно если учесть возможности запутанных состояний, вызванных ненадежными реализациями GetHashCode(), но применяются те же принципы.Если TKey является типом класса, единственными аспектами экземпляра TKey, которые составляют часть состояния словаря, являются значение, возвращаемое GetHashCode, и класс эквивалентности, подразумеваемый его методом Equals;обе эти вещи должны быть неизменными.Ни один законно изменяемый аспект объекта класса TKey или TValue не должен рассматриваться как часть состояния TDictionary<TKey,TValue>.