"Peter Foelsche" wrote in message news:iv8fia$6gl$1@dough.gmane.org...

"Peter Foelsche" wrote in message news:iv8fap$5ju$1@dough.gmane.org...

something was missing:

...

std::list sort(std::list _sList) { std::set sSet; std::list sSorted; while (_sList.size()) for (std::list::iterator p = _sList.begin(), pNext = p, pEnd = _sList.end(); p != pEnd; p = pNext) { ++pNext; bool bFound = false; for (std::set::const_iterator p1 = (*p)->m_sPredecessors.begin(), p1End = (*p)->m_sPredecessors.end(); p1 != p1End; ++p1) if (sSet.find(*p1) == sSet.end()) { bFound = true; break; } if (!bFound) { sSorted.push_back(*p); sSet.insert(*p); _sList.erase(p); } } return sSorted; }

ok -- one could use std::includes http://www.cplusplus.com/reference/algorithm/includes/ to find out if all elements of the set attached to the object currently considered are contained in the local sSet instead of iterating...

"Gordon Woodhull" wrote in message news:62FB31DF-8393-4DB1-B8F7-63FE4E2B522D@woodhull.com...

On Jul 8, 2011, at 10:44 PM, Peter Foelsche wrote:

...

Dear All,

I'm trying to get some objects sorted. Every object has a set of pointers to other objects, which need to come before this object (or are considered smaller than this object).

No cycles, right? This sounds and looks like your standard topological sort, O(N).

thanks a lot -- I learned something: http://en.wikipedia.org/wiki/Topological_sorting I'll read up about it... Peter

You could put your objects in a graph and use the algo in Boost.Graph.

Or you could do the depth first search yourself with a function that first recursively adds all predecessors to the sorted list, then adds the current item. Then keep calling this with any items not yet added to the sorted list. (Topological sort is depth first search with a postorder traversal.)

HTH, Gordon