Здравствуйте, Sinclair, Вы писали:
S> ImmutableValue(T && value) : value_(value) {}
S>Хм. А там точно будет ссылка на оригинал, а не дубликат?

Там будет и не ссылка, и не дубликат.


S>А если "исправить" ваш код так:
S> const T& value_;

Тогда мы храним ссылку, а не значение, т.е. теряем контроль над другими потенциальными ссылками на это значение.
Я ж не просто так храню именно значение. ))

Семантика перемещения активно использовалась в С++ еще до поддержки её в стандарте C++11, это популярный паттерн проектирования для плюсов, особенно в сценарии read-modify-write.
Соответственно, однажды поддержали в синтаксисе языка.

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

std::vector<int> v1;
std::vector<int> v2;
std::swap(v1, v2);

в процессе обмена содержимым переменных копии данных не создаются, вектора поэлементно не копируются.
Происходит обмен 3-х указателей: begin_, end_, capacity_end_;


S>Покажите мне пример кода, в котором вы изготавливаете из мутабельного объекта иммутабельный, и продемонстрируйте, что вы после этого не можете этот иммутабельный изменить.

template<typename T>
class ImmutableValue {
    const T value_;
public:
    ImmutableValue(T && value) : value_(move(value)) {}
    const T & value() const { return value_; }
};

int main()
{
    using namespace std;
    typedef ImmutableValue<string> istring;

    string s1 = "it is a long enough string";
    istring s2 = move(s1);
    assert(s2.value() == "it is a long enough string");
    assert(s1 == "");

    s1 = "42";
    assert(s2.value() == "it is a long enough string");
    assert(s1 == "42");

    return 0;
}

Здесь "it is a long enough string/0" выделяется в динамической памяти, затем через std::move перемещается в иммутабельную строку s2, при этом строка s1 теряет своё содержимое.
Далее мы изменяем значение строки s1, в то время как зачение s2 не изменяется.
Изменить законными способами значение переменной s2 нельзя;

    istring s3 = s2; // создание копии строки
    assert(s3.value() == "it is a long enough string");
    assert(s2.value().data() != s3.value().data()); // именно копии, по разным адресам

    s2 = s3; // ошибка компиляции: operator=(const ImmutableValue<std::string> &) удалён

Последняя строка тоже важна для понимания — получив однажды ссылку на ImmutableValue<std::string> я могу быть уверен, что переменную не затрут.


V>>Далее в своём коде используешь шаблонный ImmutableMap.
S>Вот прямо так сразу использовать шаблонный ImmutableMap не получится. Вы, как водится, привели тот самый фрагмент кода, который был очевиден и без обсуждения.
S>Как вы реализуете метод add(const TKey & key, const TValue & value)?

Никак.
Для иммутабельных типов это будут внешние ф-ии и операторы, разумеется.
Просто в дотнете сплошные методы. ))


S>Внезапно окажется, что нельзя просто взять произвольный mutable тип, завернуть его в ImmutableValue и наслаждацца.

Можно.


S>Даже если вы сможете реализовать своё обещание с "zero-overhead" конструктором перемещения (в чём я почему-то сомневаюсь)

Зря сомневаешься.


S>реализация изменяющих методов "в лоб" потребует от вас реализовать copy-on-write, что убъёт производительность.

Это смотря, какова природа/структура и объемы данных.
copy-on-write для небольших объемов линейно-расположенных в памяти данных работает лучше иммутабельного графа.
У меня выходило что-то до 2-3-х десятков машинных слов выгодней было создавать линейные копии.

Но это мы уже ответвились в другую область — в область алгоритмов и структур данных, а они зависят от конкретных задач (или классов задач, бо практически все задачи уже известны, бгг).


S>Чтобы ваш "мутабельно-иммутабельный" словарь можно было применять в реальной жизни, придётся особенным образом проектировать его мутабельную версию.

В моём случае не придётся для сценария, скажем, для которого разработали FrozenDictionary в 8-м дотнете.

Я имено сегодня прошёлся по нововведениям 8-й версии и малость поржал, бо там описали аккурат предложенный мною сценарий.
http://www.rsdn.org/forum/flame.comp/8494901.1
"У дураков мысли сходятся" (С)


S>Посмотрите для примера в код классов ImmutableXXX.Builder всё в том же неймспейсе.

Смотрел сразу же по выходу.
Не любопытно.
И странно, что оно не было сделано еще лет 20 назад, когда тема иммутабельных деревьев была модной на слуху.

Разумеется, я и сам не раз использовал аналогичные типы данных, например, в утилите описания лексических анализаторов, там узлы графов состояний НКА и ДКА.
Т.е., эта техника была отшлифована в ФП еще черти когда.

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


V>>В С++ ключевое слово const применимо так же к полям структур/классов.
V>>Такие поля могут быть инициализированы только в конструкторе.
V>>Это аналог readonly в C#.
S>Это всё понятно.

Всё это обсуждение подзатянулось из-за того, что это было непонятно тебе.
В C# ключевое слово const у мемберов объявляет аналог статического readonly поля объекта.

В С++ это аналог readonly во всех случаях.
В случае статической инициализации поля, если компилятор видит эту инициализацию, он сразу подставляет видимое значение.


S>Да, слово const есть, можно применять его к мемберам. Счастье-то в чём?

Тебе нужны были железобетонные гарантии — ну и вот.
Если же речь об алгоритмах и структурах данных — ну так пиши эти структуры и алгоритмы над ними.
Весь механизм для этого есть.


V>>Это не столько про саму иммутабельность, сколько про специальные алгоритмы на иммутабельных графах и списках.
S>Чегось? Какие ещё алгоритмы? Какие графы? Там ровно то, что написано в названии неймспейса — реализация иммутабельного списка, словаря, множества, массива, стека, очереди, и ещё пары классов.

Проснись, коллега. ))
Это именно реализация некоторых иммутабельных алгоритмов над некоторыми иммутабельными структурами данных.

Collections.Immutable не приносит в язык иммутабельность как таковую, эта либа лишь реализует некоторые структуры и алгоритмы, доказавшие свою полезность в ФП.


V>>Соответственно, ценностью этого раздела библиотеки является уже готовая функциональность, а не какие-то там гарантии.
V>>(никаких гарантий та система типов не даёт)
S>Конечно даёт.

Не-а.
Я могу нарушать гарантии интерфейсов, например, реализовывать тип как мутабельный и возвращать this из методов.


S>Вот мой метод:
S>

S>public void RegisterState(ImmutableDictionary<string, int> state)
S>{
S>  _visited[state] = true;
S>}
S>

S>Попробуйте "сломать" его, передав в него мутабельный state.

У тебя ошибка, должно быть так:

_visited = _visited.SetItem(state, true);

Возвращается ссылка на другой экземпляр.
(который в общем случае включает узлы исходного дерева)

И это у тебя оно гарантируется из-за использования конкретного типа ImmutableDictionary<,>, а если сделать так:

public void RegisterState<TDict, TKey, TValue>(TDict state)
    where TDict : IImmutableDictionary<TKey, TValue> {...}

то прощай гарантии, можно начинать хулиганить. ))

В плюсах, напротив, можно определить некий концепт ImmutableMap и юзать так:

template<ImmutableMap TDict>
void RegisterState(TDict state) {
   visited_ = merge(visited_, state, true);
}

Где концепт ImmutableMap требует, например, быть инстансом шаблонного типа ImmutableMapWrapper, которому в кач-ве аргумента подали тип, удовлетворяющий публичному интерфейсу std::map.

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