Существуют ли версии ассоциативных структур данных C ++ STL, оптимизированные для многочисленных частичных копий?

Question

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

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

Существуют ли варианты ассоциативных структур данных STL, которые предлагают такую ​​частичную оптимизацию копирования? Возможно в Boost? Такая структура данных была бы тривиальной для реализации в Haskell или OCaML, конечно, но это потребовало бы больших усилий в C ++.

Answer 1

Я знаю, что вообще нецелесообразно предлагать другой язык, но стандартные библиотеки контейнеров на Haskell делают именно это.Я помню, как смотрел видео (это был Саймон Пейтон Джонс?), Рассказывающее об этой конкретной проблеме и о том, как решение на Haskell оказалось намного быстрее, чем решение на C ++ для данной работы программиста.Конечно, это было для конкретной проблемы, у которой было много наборов с большим количеством общих элементов.

Существует довольно много исследований по этому вопросу.Если вы ищете ключевые слова, я предлагаю поискать «функциональные структуры данных» вместо «неизменяемых структур данных», так как большинство функциональных парадигм выигрывают от неизменности в целом.Такие структуры, как finger tree , были разработаны для решения именно этой проблемы.

Я не знаю ни одной библиотеки C ++, которая реализует эти структуры данных.Ничто не мешает вам читать соответствующие статьи (или исходный код на Haskell, который составляет около 1 тыс. Строк для Data.Set, включая тесты) и реализовывать его самостоятельно, но я знаю, что это не то, что вы хотели бы услышать.Вам также необходимо выполнить какой-то подсчет ссылок для общих узлов, который для таких глубоких структур может потреблять больше ресурсов, чем даже простые сборщики мусора.

Answer 2

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

Это довольно уникальный случай. Я бы рекомендовал вместо этого использовать std :: vector. (Нет на самом деле!) Код создания узла может по-прежнему использовать set, а переключение на vector в последнюю секунду. Тем не менее, vector меньше и занимает лишь небольшое количество выделенных областей памяти (один, если вы используете reserve), что делает алгоритм намного быстрее.

typedef unsigned int treekeytype;
typedef std::vector<unsigned int> minortreetype;
typedef std::pair<treekeytype, minortreetype> majornode
typedef std::set<treekeytype, minortreetype> majortype;
majortype majortree;

void func(majortype::iterator perform) {
     std::set<unsigned int> results;
     results.assign(perform->second.begin(), perform->second.end());
     majortree[perform->first+1].assign(results.begin(), results.end()); //the only change is here
     majortype::iterator next = majortree.find(perform->first+1);
     func(next);
}

Вы даже можете использовать std::lower_bound и std::upper_bound, чтобы по-прежнему получать O (log (n)) доступ к памяти, поскольку она по-прежнему сортируется так же, как и набор, поэтому вы не потеряете эффективность. Это чистый выигрыш, если вам не нужно часто вставлять / удалять.

Боюсь, однако, что копирование каждого комплекта непомерно дорого.

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

Я понимаю, что это не то, к чему вы стремились с этим вопросом, но, как сказал Джеймс Канзе, я не знаю такого контейнера. Кроме, возможно, странного и опасного использования класса STL rope. Обратите внимание, что я сказал и имел в виду STL, а не стандартную библиотеку C ++. Они разные.

Answer 3

Это практически невозможно в C ++, так как понятие неизменного Контейнер не существует. Вы можете знать, что вы не будете вносить изменения, и что какое-то общее представление было бы предпочтительнее, но компилятор и библиотека не делают, и нет никакого способа сообщить об этом им.