Boost::Multi-嵌套列表的索引

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;
}

在 top-level，我有一个 std::list 的 struct obj 那么，这些top-levelobj中的每一个都可以有任意数量的childobjects，包含在 object 的 topLevelList 列表中。这可以继续，嵌套列表中的 child 也有自己的 children.

有的object只能是children，有的是容器，可以有自己的children。容器 object 有 X 个 sub-containers，每个 sub-container 都有自己的 child object 列表，这就是为什么我在每个对象结构中都有 topLevelList ，而不是简单的 objList.

我想用 boost::Multi-index 为这个列表列表建立索引，以随机访问 top-level 列表或后代列表中的任何 object全局唯一 ID。

这能实现吗？我已经搜索了没有成功的示例。

我认为通过 object ID 获得扁平主搜索索引的唯一方法是使上面的列表成为指向 object 的指针列表，然后遍历完整的层次列表, 并将每个 object 在内存中物理分配的指针登录到主搜索索引中。然后任何 object 都可以通过主搜索索引找到。

使用 Boost::Multi-index，我仍然需要遍历层次结构，但希望能够在遇到的每个列表中使用随机访问而不是顺序访问，以便找到所需的 object.

使用嵌套向量而不是列表是一个问题 - 由于在向量中进行添加和删除，因此会降低性能，并且指向 object 的指针可能会随着向量重新分配而失效.

我几乎要说服自己实现指针的扁平主 objId 搜索索引，除非有人有更好的解决方案可以利用 Boost::Multi-index.

2020 年 1 月 31 日编辑： 我在执行下面的嵌套列表时遇到了问题。我遇到过代码没有正确地将 top-level parent objects 放入顶层的情况，因此在 "bracketed" 打印输出中，我们看不到层次结构parent。但是，在 "Children of xxx" 打印输出中，parent 的 children 确实显示正确。这是 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 而不是演示代码中运行，您就会发现问题所在。 Object 141 是一个 parent object 并且被放置在顶层。但它不会打印在 "Bracketed" 层次结构打印输出中。这是为什么？

2020 年 2 月 2 日编辑：

Boost::Serialize 经常在 oarchive 上传递异常，抱怨 re-creating 特定的 object 会导致重复的 object。一些存档保存并 re-load 成功，但许多导致上述错误。我还不能确定错误发生的确切条件，但我已经证明 none 用于填充 nested_container 和平面 object 列表包含重复的 object ID。我正在使用文本存档，而不是二进制文件。以下是我如何修改 nested_container 以及另一个单独的平面 object 列表的代码以执行 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
};

Answer 1

如果有帮助，您可以使用 Boost.MultiIndex 使用 路径排序.

的概念来实现一种分层容器

假设我们有以下对象层次结构，由它们的 ID 标识：

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

我们将每个对象的路径定义为从根到对象的ID序列：

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) 访问 ID 和基于层次结构的索引：

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.get<1>().begin(),c.get<1>().end(),print);  
  std::cout<<"\n"; 

  std::cout<<"top level:\t";
  for_each_in_level(c,c.get<1>().begin(),c.get<1>().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.get<1>().begin(),c.get<1>().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 ]

2020/02/02 更新：

访问顶级元素时，我更改了以下代码：

std::for_each(c.begin(),c.end(),...;  
for_each_in_level(c,c.begin(),c.end(),...);

至

std::for_each(c.get<1>().begin(),c.get<1>().end(),...;  
for_each_in_level(c,c.get<1>().begin(),c.get<1>().end(),...);

这是因为索引 #0 是散列的，不一定显示按 ID 排序的元素。

例如，如果按此顺序插入 ID 为 (170,171,173,173,141) 的元素，则索引 #0 将它们列为

170,171,173,173,141（巧合，与插入的顺序相同），

而索引 #1 将它们列为

141,170,171,173,173（按ID排序）。

代码的实现方式，for_each_in_level(c,c.begin(),c.end(),...); 被内部映射到 index #1 范围 [170,...,173]，遗漏了 141。确保包含所有顶级元素的方法是编写 for_each_in_level(c,c.get<1>().begin(),c.get<1>().end(),...);.

Boost::Multi-嵌套列表的索引

Boost::Multi-index for nested lists

boost

nested-lists

multi-index

boost-multi-index