Стратегия совместного использования данных в дереве объектов без использования статических элементов
Я нахожусь в ситуации, когда мне нужно обмениваться данными во многих экземплярах полиморфного дерева объектов, но опять же, мне нужно, чтобы общие данные были «для дерева», поэтому использование членов статического класса в базовом классе на самом деле не вариант ,
Я не хочу «перегружать» каждый экземпляр дополнительными указателями на общие данные, поэтому мой текущий подход (учитывая, что я использую деревья) состоит в том, чтобы общие данные были членами корневого узла дерева и каждый доступ к общим данным проходит через цепочку косвенных указаний в зависимости от глубины конкретного узла, через который осуществляется доступ к «древовидным глобальным» данным.
Поскольку существуют сценарии, при которых к совместно используемым данным будут обращаться очень часто (миллионы в секунду … по крайней мере, это то, что предназначено), мне интересно, есть ли какой-то шаблон проектирования, который может помочь мне избежать косвенных обращений к корневому узлу, пока еще не вносит лишнего вздутия в след объектов.
Хотя существует возможность «кэшировать» указатель корневого узла как локальный, скажем, для узкого цикла, который обращается к совместно используемым данным, существует много сценариев, в которых функциональность будет каскадно проходить по узлам дерева и даже переключать деревья в процессе, поэтому кэшировать указатель корневого узла применимо только в узком контексте.
- Обратите внимание, что упоминание статических членов не ограничивает область применения C ++, я также добавил тег C, потому что на данный момент я открыт для любых идей.
Решение
Все методы взаимодействия с узлом дерева в качестве первого параметра принимают указатель на корень.
Класс-оболочка flyweight может скрыть эту деталь реализации, где вы получаете доступ к узлам дерева через непрозрачный класс с указателем реального узла дерева и указателем на корень в нем. Если вы попросите ребенка, он вернет вам другой вес.
Теперь вашему дереву не хватает дополнительного указателя, но интерфейсный класс имеет дополнительный указатель.
Если ваши древовидные узлы являются неизменяемыми (логически), вы даже можете скопировать их состояние, чтобы уменьшить издержки косвенного обращения.
template<class Data>
struct internal_tree {
Data d;
std::unique_ptr<internal_tree> left;
std::unique_ptr<internal_tree> right;
};
template<class Data>
struct flyweight_tree {
private:
internal_tree* internal = nullptr;
internal_tree* root = internal;
flyweight_tree(internal_tree* t, internal_tree* r):internal(t),root(r) {}
public:
flyweight_tree() {}
flyweight_tree(internal_tree* r):internal(r) {}
flyweight_tree left() const { return { internal->left.get(), root }; }
flyweight_tree right() const { return { internal->right.get(), root }; }
};
теперь наш актуальный internal_tree структура данных не хранит указатель на корень. Код, который использует его, обращается к нему через flyweight_tree, который хранит указатель на корень, но этот указатель на корень сохраняется только в точке доступа, а не хранится в течение длительного времени.
Если вы хотите parent, вы могли бы даже реализовать его в качестве навесного, где flyweight_tree хранит std::vector указателей на родителя (вместо root). Это сохраняет еще одну кучу памяти в узлах дерева (без указателя на родителя, но каждый, кто его использует, может получить родительский элемент, потому что он использует его через flyweight_tree).
Мы могли бы либо выполнить большую часть работы в internal_treeгде он принимает в качестве аргументов информацию, flyweight_tree магазины, или мы могли бы реализовать большую часть логики дерева в flyweight_tree и уходи internal_tree как компактная структура «длительного хранения».
Другие решения
Возможности, о которых я могу думать:
- Если количество корней ограничено, вместо этого сохраните смещение (например, в uint8_t) для статического массива, в котором есть ваши корни. Например, если у вас только 5-10 корней, нет необходимости хранить колоссальные 64 бита на узел.
- Почему бы не запустить каждое «дерево» в своем собственном процессе (на уровне ОС)? Таким образом, каждый корень может быть сохранен как статические данные и доступен глобально.
- Если вы можете ограничить количество узлов, возможно, вы могли бы использовать специальный распределитель: сначала выделите свой корень в начале заданной границы памяти, например, 0x0010000, 0x0020000 и т. Д., А затем получите адрес корня с помощью простое вычитание / битовый сдвиг для каждого узла? Но вы должны быть в состоянии гарантировать, что вы можете выделить все свои узлы в области памяти каждого дерева.