对相互依赖的对象的 C++ 向量进行排序的简短解决方案？

Question

我刚刚编写了一个软件的一部分，其中字段以正确的方式排序以进行处理。每个字段可以依赖 0-n 个其他字段。在上一步中已经检查并防止了循环。

我当前的代码可以工作，但不是很优雅。我遍历列表并将相关条目移到前面，直到不需要移动为止。

这是一个说明问题的最小示例：

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Obj {
    std::string name;
    std::vector<std::string> dependencies;
};

std::vector<Obj*> objects;

void printObjList(std::string title) {
    std::cout << title << std::endl;
    for (auto obj : objects) {
        std::cout << "- " << obj->name << std::endl;
    }
}

int main()
{
    objects.push_back(new Obj {"d", {}});
    objects.push_back(new Obj {"a", {"c", "d"}});
    objects.push_back(new Obj {"b", {}});
    objects.push_back(new Obj {"c", {"e", "d"}});
    objects.push_back(new Obj {"e", {"b"}});
    printObjList("Unsorted");
    std::stable_sort(objects.begin(), objects.end(), [](Obj *a, Obj *b) {
        return a->name < b->name;
    });
    //std::stable_sort(objects.begin(), objects.end(), [](Obj *a, Obj *b) {
        // ???
    //});
    printObjList("Sorted by Dependencies");
    return 0;
}

玩一下这里的代码： http://coliru.stacked-crooked.com/a/902e91b00924a925

作为另一个对象中 dependencies 的一部分的对象必须在之前排序，该对象包含 dependencies 列表中的引用。

我假设有一些众所周知的算法可以解决这类问题？

Answer 1

详细说明我的快速评论：

如果您已经检查过您的项目中没有循环，那么您所拥有的就是有向无环图 (DAG)。

排序就是所谓的拓扑排序问题： (https://en.wikipedia.org/wiki/Topological_sorting) 具有已知的高效解决方案，例如 Kahn 的算法，尽管要利用它的效率，您必须小心存储节点和边的方式，以便某些操作（例如，找到一个没有传入边的节点）是有效的（恒定时间）

一些著名的库，如 boost 也提供了实现： http://www.boost.org/doc/libs/1_33_1/libs/graph/doc/topological_sort.html

对相互依赖的对象的 C++ 向量进行排序的简短解决方案？

Short Solution to Sort a C++ Vector of Objects with Dependencies to Each Other?

c++

sorting

algorithm

std

c++11