Boost :: Multi-index для вложенных списков

Question

Как реализовать 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;
}

На верхнем уровне у меня есть стандарт:: список struct obj Тогда каждый из этих объектов верхнего уровня может иметь любое количество дочерних объектов, которые содержатся в списке topLevelList для этого объекта. Это может продолжаться, когда дочерний элемент во вложенном списке также имеет своих собственных дочерних элементов.

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

Я хочу проиндексировать этот списоксписков с boost :: Multi-index для получения произвольного доступа к любому из объектов в списке верхнего уровня или списке потомков по его глобально уникальному идентификатору.

Можно ли это сделать? Я искал примеры, но безуспешно.

Я думаю, что единственный способ получить сводный основной поисковый индекс по идентификаторам объектов - сделать перечисленные выше списки списками указателей на объекты, а затем пройти по завершенной иерархической структуре. список и войдите в основной поисковый индекс указатель, где каждый объект физически размещен в памяти. Тогда любой объект может быть найден через главный поисковый индекс.

С Boost :: Multi-index мне все равно придется обходить иерархию, хотя, надеюсь, с возможностью использовать случайный вместо последовательного доступа в каждомСписок найден, чтобы найти нужный объект.

Использование вложенных векторов вместо списков является проблемой - поскольку в векторах происходят добавления и удаления, существует снижение производительности, а также перспектива указателей на объекты. становится недействительным по мере перераспределения векторов.

Я почти уговариваю себя реализовать уплощенный основной указатель поиска objId указателей, если только у кого-то нет лучшего решения, которое может использовать Boost :: Multi-index.

Answer 1

Если это поможет, вы можете использовать Boost.MultiIndex для реализации своего рода иерархического контейнера, используя понятие упорядочение пути .

Предположим, у нас есть следующая иерархия объектов, идентифицированныхпо их идентификаторам:

|-------
|      |
0      4
|----  |----
| | |  | | |
1 2 3  5 8 9
       |--
       | |
       6 7

Мы определяем путь каждого объекта как последовательность идентификаторов от корня до объекта:

0 --> 0
1 --> 0, 1
2 --> 0, 2
3 --> 0, 3
4 --> 4
5 --> 4, 5
6 --> 4, 5, 6
7 --> 4, 5, 7
8 --> 4, 8
9 --> 4, 9

Эти путиможет быть упорядочен лексикографически, так что последовательность объектов, отсортированных по пути, фактически является представлением базовой иерархии. Если мы добавим указатель parent к объектам для моделирования родительских и дочерних отношений:

struct obj
{
   int        id;
   const obj* parent=nullptr;
};

, тогда мы можем определить multi_index_container с доступом O (1) по идентификатору и индексацией на основе иерархии:

using nested_container=multi_index_container<
  obj,
  indexed_by<
    hashed_unique<member<obj,int,&obj::id>>,
    ordered_unique<identity<obj>,obj_less>
  >
>;

, где obj_less сравнивает объекты в соответствии с порядком пути. Все виды манипуляций с деревьями и посещения возможны, как показано ниже (код не совсем тривиален, не стесняйтесь спрашивать).

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <iterator>

struct obj
{
   int        id;
   const obj* parent=nullptr;
};

struct subtree_obj
{
  const obj& obj_;
};

struct path
{
  int         id;
  const path* next=nullptr;
};

struct subtree_path
{
  const path& path_;
};

inline bool operator<(const path& x,const path& y)
{
       if(x.id<y.id)return true;
  else if(y.id<x.id)return false;
  else if(!x.next)  return y.next;
  else if(!y.next)  return false;
  else              return *(x.next)<*(y.next);
}

inline bool operator<(const subtree_path& sx,const path& y)
{
  const path& x=sx.path_;

       if(x.id<y.id)return true;
  else if(y.id<x.id)return false;
  else if(!x.next)  return false;
  else if(!y.next)  return false;
  else              return subtree_path{*(x.next)}<*(y.next);
}

inline bool operator<(const path& x,const subtree_path& sy)
{
  return x<sy.path_;
}

struct obj_less
{
private:
  template<typename F>
  static auto apply_to_path(const obj& x,F f)
  {
    return apply_to_path(x.parent,path{x.id},f); 
  }

  template<typename F>
  static auto apply_to_path(const obj* px,const path& x,F f)
    ->decltype(f(x))
  { 
    return !px?f(x):apply_to_path(px->parent,{px->id,&x},f);
  }

public:
  bool operator()(const obj& x,const obj& y)const
  {
    return apply_to_path(x,[&](const path& x){
      return apply_to_path(y,[&](const path& y){
        return x<y;
      });
    });
  }

  bool operator()(const subtree_obj& x,const obj& y)const
  {
    return apply_to_path(x.obj_,[&](const path& x){
      return apply_to_path(y,[&](const path& y){
        return subtree_path{x}<y;
      });
    });
  }

  bool operator()(const obj& x,const subtree_obj& y)const
  {
    return apply_to_path(x,[&](const path& x){
      return apply_to_path(y.obj_,[&](const path& y){
        return x<subtree_path{y};
      });
    });
  }
};

using namespace boost::multi_index;
using nested_container=multi_index_container<
  obj,
  indexed_by<
    hashed_unique<member<obj,int,&obj::id>>,
    ordered_unique<identity<obj>,obj_less>
  >
>;

template<typename Iterator>
inline auto insert_under(nested_container& c,Iterator it,obj x)
{
  x.parent=&*it;
  return c.insert(std::move(x));
}

template<typename Iterator,typename F>
void for_each_in_level(
  nested_container& c,Iterator first,Iterator last, F f)
{
  if(first==last)return;

  const obj* parent=first->parent;
  auto       first_=c.project<1>(first),
             last_=c.project<1>(last);

  do{
    f(*first_);
    auto next=std::next(first_);
    if(next->parent!=parent){
      next=c.get<1>().upper_bound(subtree_obj{*first_});
    }
    first_=next;
  }while(first_!=last_);
}

template<typename ObjPointer,typename F>
void for_each_child(nested_container& c,ObjPointer p,F f)
{
  auto [first,last]=c.get<1>().equal_range(subtree_obj{*p});
  for_each_in_level(c,std::next(first),last,f);
}

#include <iostream>

auto print=[](const obj& x){std::cout<<x.id<<" ";};

void print_subtree(nested_container& c,const obj& x)
{
  std::cout<<x.id<<" ";
  bool visited=false;
  for_each_child(c,&x,[&](const obj& x){
    if(!visited){
      std::cout<<"[ ";
      visited=true;
    }
    print_subtree(c,x);
  });
  if(visited)std::cout<<"] ";
}

int main()
{
  nested_container c;
  auto it=c.insert({0}).first;
    insert_under(c,it,{1});
    insert_under(c,it,{2});
    insert_under(c,it,{3});
  it=c.insert({4}).first;
    auto it2=insert_under(c,it,{5}).first;
      insert_under(c,it2,{6});
      insert_under(c,it2,{7});
    insert_under(c,it,{8});
    insert_under(c,it,{9});

  std::cout<<"preorder:\t";
  std::for_each(c.begin(),c.end(),print);  
  std::cout<<"\n"; 

  std::cout<<"top level:\t";
  for_each_in_level(c,c.begin(),c.end(),print);
  std::cout<<"\n"; 

  std::cout<<"children of 0:\t";
  for_each_child(c,c.find(0),print);
  std::cout<<"\n";

  std::cout<<"children of 4:\t";
  for_each_child(c,c.find(4),print);
  std::cout<<"\n";

  std::cout<<"children of 5:\t";
  for_each_child(c,c.find(5),print);
  std::cout<<"\n"; 

  std::cout<<"bracketed:\t";
  for_each_in_level(c,c.begin(),c.end(),[&](const obj& x){
    print_subtree(c,x);
  });
  std::cout<<"\n"; 
}

Выход

preorder:       0 1 2 3 4 5 6 7 8 9 
top level:      0 4 
children of 0:  1 2 3 
children of 4:  5 8 9 
children of 5:  6 7 
bracketed:      0 [ 1 2 3 ] 4 [ 5 [ 6 7 ] 8 9 ]