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

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