C++中的有序树

Question

C++ STL 显然缺少有序树数据结构。请参阅 here. Boost is also missing an ordered tree, but it does have an "un"ordered one, Property Tree，其中数据按插入排序。我希望顺序与内存无关。

属性树上的 boost 页面说这在概念上是 boost::ptree 结构。

struct ptree
{
   data_type data;                         // data associated with the node
   list< pair<key_type, ptree> > children; // ordered list of named children by insertion
};

我想扩展 boost 以跟踪订单。

这是正确的方法吗？

class ordered_ptree : public boost::property_tree::ptree {
public:
  ordered_ptree(int id) : _id{id}{};

 protected:
  int _id;
};

Answer 1

（根据您问题中的评论，我了解到您想要类似 Python 的 OrderedDict，但考虑到键的相对顺序。）

由于 none 的标准库（或提升的）容器正是您想要的，您可能想要扩展 std::map（特别是如果您不需要所有接口）。

假设您从

开始

template<
    typename Key, 
    typename Value, 
    class Compare=std::less<Key>,
    class Alloc=std::allocator<pair<const Key, Value> >
class ordered_map
{
    // This needs to be filled.
};

现在在里面，你可以放一个插入计数器：

    std::size_t m_ins_count;

初始化为 0 并在每次插入时递增。

在内部，您的新密钥将是原始密钥和插入计数的 std::pair 秒。 binary search trees 的标准属性意味着键仅与第二个 pair 项（即插入计数）不同的节点将在有序遍历中连续，这意味着

您保留不同键的顺序
您保留键内的插入顺序
运算是对数时间
遍历相同键项是（摊销的）线性时间

所以，在内部你会有类似

的东西

    typedef
        std::map<
            std::pair<Key, std::size_t>,
            Value,
            lex_compare<Compare>,
            std::allocator<std::pair<std::pair<Key, std::size_t>,     Value> >
        internal_map_t;

（其中 lex_compare<Compare> 首先比较给定的仿函数，然后比较插入索引）。

现在您可以选择一个（最小）接口，并通过转换 "outer world" 中的键和 "inner world" 中的键对 + 插入索引来实现它。

如果您还计划提供迭代器接口，您可能会发现 boost iterator library 很有用，因为您只想修改 std::map 的迭代器。

C++中的有序树

Ordered Tree in C++

c++

tree

boost

stl