10

我想创建一个记录来保存有关信息

  • a）存在什么样的元素以及
  • b) 存在的每种元素的数量

在树的一个节点中。我将只为叶节点显式存储此信息，而父节点的信息可以通过组合所有子节点的信息来获得（例如，孩子 1 有 3 个 A 对象，1 个 B 对象，孩子 2 有 1 A 的对象，C 的 2 个对象——父级有 A 的 4 个对象，B 的 1 个对象和 C 的 2 个对象）。

当从父节点请求这些信息时我会小心，不要先请求、使用和丢弃子节点的信息，然后再请求它的父节点，但向上构造将是一个常见的操作。其他两个常见的操作直接来自我存储的内容：种类 X 的对象是否存在？有多少 X 类物体存在？还有多少种物体存在？

对象种类表示为整数，并且对象编号始终是整数值。什么是更好的选择（以及所选选择的论据）：

  • 使用std::multiset<int>, 和std::multiset::count()操作std::multiset::find()（更容易联合但元素重复，总的不同元素计数难以获得）
  • 使用std::map<int, std::size_t>种类作为键，对象数量作为值（没有重复的元素，std::map::find()存在函数，大小给出了存储的对象种类的正确数量，但是访问不存在的元素会无意中增加大小）

谢谢你的建议！

4

2 回答 2

12

要为每个比较谓词存储总共n个具有kstd::multiset个不同值的项目，分配n 个二叉搜索树节点 (*)。Anstd::map仅分配k个（稍大）节点。

当您的比较谓词可以认为两个项目相等但仍必须显式存储时，您将使用std::multiset它们，因为它们在比较谓词不检查的某些方面有所不同。此外，迭代a 会生成n 个multiset项目中的每一个，而 a将生成k个不同项目中的每一个，其中每个项目都有计数。map

如果项目只是整数，请使用std::map. 然后，您的“有多少不同的项目”查询将只是对 的调用size，它在恒定时间内运行。

您声称“访问不存在的元素会无意中增加大小”仅在您用于operator[]访问节点时才成立。find不表现出这种行为。

(*) C++ 标准不保证这些容器被实现为（平衡的）BST，但在我见过的所有实现中，它们都是。

于 2012-06-01T12:57:52.103 回答
3

排序的std::vector<int>呢？您需要的操作可以满足如下：

  • X种类的物体存在吗？ std::binary_search
  • 有多少种类 X 的物体？ ,std::equal_range减去.first.second
  • 存在多少种物体？
    • std::unique_copy然后size()是副本，或者...
    • 使用单独的计数器，std::binary_search在插入向量之前调用

与树状结构相比，这种方法的优点是缓存局部性（所有数据都是连续的）和更少的内存占用。在不了解您的数据的情况下，我无法确定它会更快还是更慢。您必须对其进行分析才能找到答案，但我有一种预感，它的性能会比您预期的要好。

这里最大的权衡是表现力。该std::map方法可能在逻辑上传达您正在做的事情方面做得更好，即对象ID 和计数之间的关系。

于 2012-06-01T13:37:40.913 回答