Boost logo

Boost Users :

Subject: [Boost-users] algorithm question
From: Peter Foelsche (foelsche_at_[hidden])
Date: 2011-07-08 22:44:39

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
It is kind of a make-tool algorithm.
I can imagine the straight-forward way to attack this -- searching.
Is there some more elegant way I'm missing?
The number of objects not small.
I tried to write some recursive functor to be passed to std::sort -- caching
the result of previous comparisions
-- but I was not successful.
My brain is hurting...


struct object
{ std::set<object*> m_sPredecessors;

// to be sorted:
std::list<object*> sList;

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at