依存関係を持つオブジェクトの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）それの効率性を活用するためにも、あなたがあなたのノードとエッジを保存する方法を注意する必要があります、カーンのアルゴリズムと同様に、効率的なソリューションを知っていた：それはトポロジカルソートとして知られている問題でソート

ようにブーストも実装を提供するように、いくつかの操作（例えば、なしの着信エッジを持つノードを見つけること）、（一定の時間）

いくつかのよく知られたライブラリが効率的である： http://www.boost.org/doc/libs/1_33_1/libs/graph/doc/topological_sort.html