c++ - 分层优先级索引

Question

我正在寻找一个 C++ 库，它具有以下问题的索引解决方案。我曾尝试制定自己的解决方案，但得出的结论是我在这里发明了一个轮子。

我有一个接收水的源桶。它需要在层次结构之间拆分水。我想它也可以表示为具有优先级的队列。在具有更高优先级的桶装满之前，其他桶不会接收任何水。有些水桶有子水桶，它们应该从那里过水。所有的 child 都可以有自己的 child ，所以他们也是一些人的母亲。 Mother 水桶可以按严格队列(一个接一个)传水或按比例分享水。

在下面的图片中，我试图说明情况。我们将 Bucket 作为层次结构的顶部。它有 3 个 child 。他们根据优先级(1、2、3)严格按顺序接水。在桶 1 装满之前，桶 2 不会接收任何水。 Bucket 1 也有 3 个 child 。两个优先级相同且分别分配 50% 和 50% 的 child ，第三个 child 只有在其他两个 child 吃饱后才会喝水。第一个 child 有了 child ，他们将水分成 20% 和 80%。

任何级别的整数 1 具有最高优先级。如果桶在同一层次上有相似的整数，我们可以认为它们的优先级相等，然后看 split 的比例。第一层编号为 1 的桶将首先接收水。然后它必须将水传递到第二级，在那里水将被分配 50%-50%，然后 50% 将在最后一级之间按 50%(20% 和 80%)分配。

                                             +--------------+
                                             |              |
                                             |   Bucket     |
                                             +-+-----+----+-+
                                               |     |    |
                                               |     |    |
                                      1        |     |    |       3
                              +----------------+     |    +-----------------+
                              |                      |                      |
                              |                      |2                     |
                              ^                      |                      ^
                           +------+                  |                   +--+--+
                           |  |   |                  ^                   |     |
                  1        |  |   |   2           +--+--+                +-----+
                  0.5      |  |   |               |     |
                +----------+  |1  +-------+       +-----+
                |             |0.5        |
                ^             ^           ^
             +--+--+      +---+---+     +-+---+
             |     |      |       |     |     |
             ++-+--+      +-------+     +-----+
              | |
     1 0.2    | |
   +----------+ |1 0.8
   |            |
   |            |
   v            v
+--+--+      +--+--+
|     |      |     |
+-----+      +-----+

我需要为所有 child 及其比例编制索引，这样，当我收到水时，我会根据所有优先级和共享权重拆分水。我的想法是使用 double 变量的整数部分的位来表示层次结构每个级别的优先级，并使用小数部分来存储比例。

Answer 1

您可以通过与访问者一起深度优先遍历您的树，将您的问题从树表示转换为队列:

#include <map>
#include <list>

struct Bucket
{
    std::map<unsigned int, Bucket> children; // <priority, children>

    template<class Visitor>
    void visit(const Visitor& visitor)
    {
        for (auto it = children.rbegin(); it!= children.rend(); ++it)
        {
            visitor(&it->second);
            it->second.visit(visitor);
        }
    }
};

int main()
{
    Bucket root_bucket;
    // populate root_bucket
    // ...

    // index root_bucket
    std::list<Bucket*> indexed_buckets;
    root_bucket.visit( [&](Bucket* b){ indexed_buckets.push_back(b); });
}

Demo

之后，indexed_buckets 将包含指向填充顺序中的桶的指针。只需将第一个注满，然后用剩余的水注满下一个。