又一个STL树

Question

我有一个有趣的问题。

我现在正在使用HTML解析器，我使用矢量<HTMLTag>用于我的所有输入目的，这对于创建树来说似乎非常好和快速。

在另一个应用程序中，我需要编辑HTML结构，现在插入或重新排序元素将非常痛苦使用向量，所以我决定切换到更像树状结构。

我读了一些关于树及其实现的文章，我正在为此目的考虑std :: map。

像这样的东西：

std::map< element, *child_map >

因此，当我想在中间插入一个标签并让它们全部按某个键排序时（例如，唯一的整数id），我仍然有问题在插入后更新分支中的所有键。

例如：

1:SCRIPT
2:HEAD
3:BODY

当我想在HEAD之后插入新元素“SCRIPT”时，我需要将Body Key增加到4，并且具有以下内容：

1:SCRIPT
2:HEAD
3:SCRIPT
4:BODY

对我来说似乎有点麻烦。我错过了什么吗？

作为替代方案，我想到了做list<pair<>>实现。因此，排序不是由键确定的，我可以在任何地方添加元素而无需任何额外的更新。

Answer 1

我会让子设置元素的成员并使用std :: list：

class Element {
/* ... */
  std::list<boost::shared_ptr<Element> > children;
/* ... */
};

也就是说，您可能希望使用现有的DOM库而不是自己的DOM库。例如，您可以使用htmlcxx。

Answer 2

List <pair>可以很好地模拟任何形式的树结构，例如你要做的事情：

list <pair <“html”，list>允许您存储任意数量的子节点以及控制子列表中对象的顺序。

走这棵树玩得开心。