Solution courte pour trier un vecteur C++ d'objets avec des dépendances entre eux?

Question

Je viens d'écrire une partie d'un logiciel où les champs sont commandés correctement pour le traitement. Chaque champ peut dépendre de 0-n autres champs. Les boucles sont déjà vérifiées et empêchées dans une étape précédente.

Mon code actuel fonctionne, mais il n'est pas très élégant. Je parcourt la liste et déplace les entrées dépendantes vers l'avant, jusqu'à ce qu'il n'y ait aucun mouvement requis.

Voici un exemple minimal illustrant le problème:

#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; 
} 

Jouer avec le code ici: http://coliru.stacked-crooked.com/a/902e91b00924a925

Un objet qui fait partie de dependencies dans un autre objet doit trier avant cet objet qui contient la référence dans la liste dependencies.

Je suppose qu'il existe un algorithme bien connu pour résoudre ce genre de problème?

Answer 1

Élaborant sur mon commentaire rapide:

Si vous avez déjà vérifié qu'il n'y a pas de boucles dans vos articles, alors ce que vous avez est un graphe orienté acyclique (DAG).

tri qui est le problème connu sous le nom tri topologique: (https://en.wikipedia.org/wiki/Topological_sorting) qui a connu des solutions efficaces, comme l'algorithme de Kahn, bien que pour tirer parti de son efficacité, vous devrez faire attention à la façon dont vous stockez vos noeuds et les arêtes , de sorte que certaines opérations (par exemple, trouver un noeud sans arêtes entrants) est efficace (constante de temps)

certaines bibliothèques bien connues, comme coup de fouet fournissent également mises en œuvre: http://www.boost.org/doc/libs/1_33_1/libs/graph/doc/topological_sort.html