[Boost-users] algorithm question

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 
object).
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...

Thanks
Peter

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 = 
_sList.end();
        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;
            ++p1)
                if (sSet.find(*p1) == sSet.end())
                {    bFound = true;
                       break;
                  }
            if (!bFound)
            {    sSorted.push_back(*p);
                _sList.erase(p);
            }
    }
    return sSorted;
}