问题描述:

I basically have a list of object to create, but some of them are dependant on other.

Each object holds a list of the "IDs" (string in my case) of the object it depends on.

From that I just need an ordered list, where the first element will be the one with no dependency and the latest one will be the one with the most dependency. Taking element one by one in this list and creating them should then work smoothly...

So from the following code, I'd like to get this list out of objects:

typedef std::string Id;

typedef std::set < ID > Ids;

struct ObjectInformation

{

Id const& getId();

Ids const& getDependencies();

};

std::vector < ObjectInformation > objects;

I know BGL (boost graph library can do it, but it seems a bit too complicated

网友答案:

This is a prime example for topological sort. It's easiest to use existing topological sort implementation, so I am not sure why you disqualify boost. Please have a look at this piece of documentation which provides an example.

相关阅读:
Top