algorithm - 什么数据结构用于对象的评估顺序？

Question

我正在尝试找出以下问题的最佳实现方式:

假设我们有一个类 A它代表一个复杂的数学对象，并且在构建时最初拥有所有需要的内在状态。对于每个对象 a_i的 A可以计算最终数值，它以一种非平凡的方式依赖于其他 a_j与 j < i , 和 a_0众所周知。此外，得出最终答案的方程式需要特殊的求值顺序和 a_i 的比较运算符。可以定义。

我想做的是创建所有需要的 a_i首先，将它们插入某种有序的数据结构，最后以正确的顺序遍历该结构以获得最终结果。

现在开始真正的问题:我应该使用哪种数据结构来以一般方式实现求值顺序的结构？二进制堆？或者我只是使用 std::vector 并在之后对其进行排序？

谢谢!

Answer 1

如果 a_i 的比较运算符(比方说小于)可以根据求值顺序定义，那么自然容器就是 std::set。使用 std::set::iterator 遍历 map 将以递增顺序产生每个 a_i，这将是您的评估顺序。例如。

std::set<A> aMap;
A a_i;
... // You create the rest of the A's
aMap.insert(a_i);
aMap.insert(a_j);

for (std::set<A>::iterator aIter = aMap.begin(); aIter != aMap.end(); ++aIter) {
    // Do your evaluation
}