Как реализовать Boost::Multi-index в списке списков
У меня есть иерархическое дерево следующим образом:
typedef std::list<struct obj> objList // the object list
typedef std::list<objList> topLevelList // the list of top-level object lists
struct obj
{
int Id; // globally unique Id
std::string objType;
std::string objAttributes;
....
topLevelList childObjectlist;
}
На верхнем уровне у меня есть std::list структуры obj. Затем каждый из этих объектов верхнего уровня может иметь любое количество дочерних объектов, которые содержатся в списке topLevelList для этого объекта. Это может продолжаться, когда дочерний элемент во вложенном списке также имеет своих собственных дочерних элементов.
Некоторые объекты могут быть только дочерними, в то время как другие являются контейнерами и могут иметь своих собственных дочерних элементов. Объекты-контейнеры имеют X подконтейнеров, каждый подконтейнер имеет свой собственный список дочерних объектов, и поэтому у меня есть topLevelList в каждой структуре объекта, а не просто objList.
Я хочу проиндексировать этот список списков с помощью boost::Multi-index, чтобы получить произвольный доступ к любому из объектов либо в списке верхнего уровня, либо в списке потомков по его глобально уникальному идентификатору.
Можно ли это осуществить? Я искал примеры без успеха.
Я думаю, что единственный способ получить сглаженный главный поисковый индекс по идентификаторам объектов — это сделать приведенные выше списки списками указателей на объекты, затем пройти по завершенному иерархическому списку и войти в главный поисковый индекс указатель, где находится каждый объект. физически размещается в памяти. Тогда любой объект можно найти с помощью главного поискового индекса.
С Boost::Multi-index мне все равно придется проходить иерархию, хотя, надеюсь, с возможностью использовать случайный, а не последовательный доступ в каждом встречающемся списке, чтобы найти нужный объект.
Использование вложенных векторов вместо списков является проблемой - поскольку в векторах происходят добавления и удаления, это снижает производительность, а также вероятность того, что указатели на объекты станут недействительными при перераспределении векторов.
Я почти уговариваю себя реализовать уплощенный индекс поиска указателей master objId, если только у кого-то нет лучшего решения, которое может использовать Boost::Multi-index.
Редактирование от 31 января 2020 г. У меня возникли проблемы с реализацией вложенных списков ниже. У меня бывают случаи, когда код неправильно помещает родительские объекты верхнего уровня в верхний уровень, и, таким образом, в распечатке «в квадратных скобках» мы не видим иерархию для этого родителя. Однако в распечатке «Дети xxx» дети этого родителя отображаются правильно. Вот раздел main.cpp, демонстрирующий проблему:
auto it=c.insert({170}).first;
it=c.insert({171}).first;
it=c.insert({172}).first;
it=c.insert({173}).first;
auto it141=c.insert({141}).first;
auto it137=insert_under(c,it141,{137}).first;
insert_under(c,it137,{8});
insert_under(c,it137,{138});
auto it9=insert_under(c,it137,{9}).first;
auto it5=insert_under(c,it9,{5}).first;
insert_under(c,it5,{6});
insert_under(c,it5,{7});
insert_under(c,it137,{142});
auto it143=insert_under(c,it137,{143}).first;
insert_under(c,it143,{144});
Если вы поместите этот код в Main.cpp вместо демо-кода и запустите его, вы увидите проблему. Объект 141 является родительским объектом и размещается на верхнем уровне. Но он не печатается в распечатке иерархии «В квадратных скобках». Почему это?
Изменить от 02.02.2020:
Boost::Serialize часто выдает исключение для oarchive, жалуясь на то, что повторное создание определенного объекта приведет к дублированию объектов. Некоторые архивы успешно сохраняются и перезагружаются, но многие приводят к указанной выше ошибке. Мне пока не удалось определить точные условия, при которых возникает ошибка, но я доказал, что ни один контент, используемый для заполнения вложенного_контейнера и плоского списка объектов, не содержит повторяющихся идентификаторов объектов. Я использую текстовый архив, а не бинарный. Вот как я изменил код для nested_container, а также для другого отдельного списка плоских объектов, чтобы выполнить Boost::Serialize:
struct obj
{
int id;
const obj * parent = nullptr;
obj()
:id(-1)
{ }
obj(int object)
:id(object)
{ }
int getObjId() const
{
return id;
}
bool operator==(obj obj2)
{
if (this->getObjId() == obj2.getObjId())
return true;
else
return false;
}
#if 1
private:
friend class boost::serialization::access;
friend std::ostream & operator<<(std::ostream &os, const obj &obj);
template<class Archive>
void serialize(Archive &ar, const unsigned int file_version)
{
ar & id & parent;
}
#endif
};
struct subtree_obj
{
const obj & obj_;
subtree_obj(const obj & ob)
:obj_(ob)
{ }
#if 1
private:
friend class boost::serialization::access;
friend std::ostream & operator<<(std::ostream &os, const subtree_obj &obj);
template<class Archive>
void serialize(Archive &ar, const unsigned int file_version)
{
ar & obj_;
}
#endif
};
struct path
{
int id;
const path *next = nullptr;
path(int ID, const path *nex)
:id(ID), next(nex)
{ }
path(int ID)
:id(ID)
{ }
#if 1
private:
friend class boost::serialization::access;
friend std::ostream & operator<<(std::ostream &os, const path &pathe);
template<class Archive>
void serialize(Archive &ar, const unsigned int file_version)
{
ar & id & next;
}
#endif
};
struct subtree_path
{
const path & path_;
subtree_path(const path & path)
:path_(path)
{ }
#if 1
private:
friend class boost::serialization::access;
friend std::ostream & operator<<(std::ostream &os, const subtree_path &pathe);
template<class Archive>
void serialize(Archive &ar, const unsigned int file_version)
{
ar & path_;
}
#endif
};
//
// My flattened object list
//
struct HMIObj
{
int objId;
std::string objType;
HMIObj()
:objId(-1), objType("")
{ }
bool operator==(HMIObj obj2)
{
if (this->getObjId() == obj2.getObjId())
&& this->getObjType() == obj2.getObjType())
return true;
else
return false;
}
int getObjId() const
{
return objId;
}
std::string getObjType() const
{
return objType;
}
#if 1
private:
friend class boost::serialization::access;
friend std::ostream & operator<<(std::ostream &os, const HMIObj &obj);
template<class Archive>
void serialize(Archive &ar, const unsigned int file_version)
{
ar & objId & objType;
}
#endif
};
