У меня есть класс C++, представляющий иерархически организованное дерево данных, которое является очень большим (~Gb, в основном столь большим, как мне может сойти с рук в памяти). Это использует список STL, чтобы хранить информацию в каждом узле плюс итераторы к другим узлам. Каждый узел имеет только одного родителя, но 0-10 детей. Абстрактный, это смотрит что-то как:
struct node {
public:
node_list_iterator parent; // iterator to a single parent node
double node_data_array[X];
map<int,node_list_iterator> children; // iterators to child nodes
};
class strategy {
private:
list<node> tree; // hierarchically linked list of nodes
struct some_other_data;
public:
void build(); // build the tree
void save(); // save the tree from disk
void load(); // load the tree from disk
void use(); // use the tree
};
Я хотел бы реализовать загрузку () и сохранить () к диску, и это должно быть довольно быстро, однако очевидные проблемы:
Я не знаю размера заранее;
Данные содержат итераторы, которые энергозависимы;
Мое незнание C++ является потрясающим.
Кто-либо мог предложить чистое решение C++?
Похоже, вы можете сохранить данные в следующем синтаксисе:
File = Meta-data Node
Node = Node-data ChildCount NodeList
NodeList = sequence (int, Node)
То есть, при сериализации корневой узел содержит все узлы, прямо (дочерние) или косвенно (другие потомки). Запись формата довольно проста: достаточно иметь функцию рекурсивной записи, начинающуюся с корневого узла.
Читать не намного сложнее. итераторы std :: list
стабильны. После того, как вы вставили корневой узел, его итератор не изменится даже при вставке его дочерних узлов. Следовательно, когда вы читаете каждый узел, вы уже можете установить родительский итератор. Это, конечно, оставляет вам дочерние итераторы, но они тривиальны: каждый узел является дочерним по отношению к своим родителям. Итак, после того, как вы прочитали все узлы, вы исправите дочерние итераторы. Начните со второго узла, первого дочернего элемента (первый узел был корнем) и перейдите к последнему дочернему элементу. Затем для каждого дочернего элемента C поместите его родительский элемент и дочерний элемент в его родительскую коллекцию. Теперь это означает, что вам нужно отложить дочерние идентификаторы int
во время чтения, но вы можете сделать это с помощью простого std :: vector параллельно std :: list
. После того, как вы пропатчили все дочерние идентификаторы в соответствующих родителях, вы можете отказаться от вектора.
Я уже ответил примерно так на SO, поэтому резюмирую:
1. Используйте базу данных.
2. Замените смещения файлов на ссылки (указатели).
3. Храните данные без древовидной структуры в записях , как в базе данных .
4. Используйте XML для создания древовидной структуры, используя имена узлов вместо ссылок.
5. Это было бы намного проще, если бы вы использовали такую базу данных, как SqLite или MySQL .
Когда вы тратите слишком много времени на «сериализацию» и меньше времени на основную цель вашего проекта, вам необходимо использовать базу данных .
На самом деле, Думаю, ваш лучший вариант - переместить всю структуру данных в таблицы базы данных. Таким образом, вы получаете выгоду от людей, гораздо более умных, чем вы (или я), имея дело с проблемами сериализации. Это также избавит вас от беспокойства о том, поместится ли структура в память.
Увеличить сериализацию уже было предложено, и это, безусловно, разумная возможность.
Многое зависит от того, как вы собираетесь использовать данные - тот факт, что вы используете многостороннее дерево в памяти, не означает, что вы обязательно должны хранить его как многостороннее дерево на диске.Поскольку вы (очевидно) уже раздвигаете пределы того, что вы можете хранить в памяти, очевидный вопрос заключается в том, заинтересованы ли вы просто в сериализации данных, чтобы при необходимости вы могли воссоздать одно и то же дерево. или хотите ли вы что-то вроде базы данных, чтобы вы могли загружать части информации в память по мере необходимости и обновлять записи по мере необходимости.
Если вы хотите последнее, некоторые из ваших вариантов также будут зависеть от того, насколько статична структура. Например, если конкретный узел имеет N дочерних узлов, является ли это число постоянным или может измениться? Если он подлежит изменению, существует ли ограничение на максимальное количество дочерних элементов?
Если вы действительно хотите иметь возможность перемещаться по структуре на диске, одна очевидная возможность будет заключаться в том, что при записи замените смещение файла на соответствующие данные вместо итератора, который вы используете в памяти.
В качестве альтернативы, поскольку кажется, что (по крайней мере, большая часть) данные в отдельном узле имеют фиксированный размер, вы можете создать структуру записей фиксированного размера, подобную базе данных, и в каждой записи записывать номера записей родитель / дети.
Знать общий размер заранее не особенно важно (навскидку, я не могу придумать, как бы я использовал размер, даже если бы он был известен заранее).
Вы можете использовать библиотеку boost.serialization. Это сохранит все состояние вашего контейнера, даже итераторы.
boost.serialization - это решение, или ИМХО, вы можете использовать шаблон SQLite + Visitor для загрузки и сохранения этих узлов, но это будет непросто. звучит.