std::list Strict Weak Ordering

Question

I am having a lot of trouble using the std::list::sort function, it works a majority of the time, however every once in a while it throws an assertion 'invalid operator<'. Looking into this issue I have realized it is because my sort function is not following strict weak ordering, however when I look at my code I do not understand why it is not following strict weak ordering as it seems correct, what is it I am missing here?

The purpose of this function is to sort a list of elements into a formula string based on the hill system, ie. Carbon First, Hydrogen Second, all others alphabetically. The FormulaStruct simply represents a single element and amount in the full formula.

struct FormulaStruct
{
    FormulaStruct(const std::string & strSymbol, int nNum, bool bHasCarbon)
        :
            m_strSymbol(strSymbol),
            m_nNum(nNum), m_bHasCarbon(bHasCarbon)
    {
    }

    bool operator < (const FormulaStruct & rhs)
    {
        //If the symbols are equal
        if(m_strSymbol == rhs.m_strSymbol)
            return true;

        if(m_bHasCarbon)
        {       
            if(m_strSymbol == "C")
                return true;        
            else        
            if(rhs.m_strSymbol == "H")
                return false;           
        }

        return m_strSymbol < rhs.m_strSymbol;
    }

    bool operator == (const FormulaStruct & rhs)
    {
        return m_strSymbol == rhs.m_strSymbol;
    }

    std::string m_strSymbol;
    int         m_nNum;
    bool        m_bHasCarbon;
};

list<FormulaStruct> FormulaList; //A list of FormulaStructs, assumed to be filled
FormulaList.sort();

EDIT bHasCarbon is the condition when there is carbon in the formula, as the hill system requires that if there is carbon in the formula than hydrogen will be next, otherwise everything is alphabetical including hydrogen, this is dictated in another section of my code.

Answer 1

Other answers have already addressed the m_strSymbol == rhs.m_strSymbol issue.

But, based on your description ("C" first, "H" next, everything else in order), it seems like you could want, if you have C++11:

return std::tie(m_strSymbol != "C", m_strSymbol != "H", m_strSymbol)
    < std::tie(rhs.m_strSymbol != "C", rhs.m_strSymbol != "H", rhs.m_strSymbol);

This is an easy way to write StrictWeakOrderings (stolen from here)

Or, if you don't have C++11 (or Boost pre-C++11), you can do something like this:

// order of checks here is important, in case both are "C"
if(rhs.m_strSymbol == "C")
    return false;
if(m_strSymbol == "C")
    return true;
// neither symbol is "C"
if(rhs.m_strSymbol == "H")
    return false;
if(m_strSymbol == "H")
    return true;
// neither symbol is "C" or "H"
return m_strSymbol < rhs.m_strSymbol;

I'm pretty sure I did that right, but as stated in the article posted above, doing it manually is prone to error and probably should be avoided...also, this could definitely be optimized further to reduce the number of string comparisons, at the risk of introducing bugs and obfuscating the code.

But it's unclear what m_bHasCarbon means and what effect that's supposed to have, so I'm not sure if this is what you need or not.

Answer 2

//If the symbols are equal
if(m_strSymbol == rhs.m_strSymbol)
        return true;

Meaning it is true for both a<b and b<a if the symbols are equal.

Perhaps you should return false, since a==b and thus !a<b, in this case.

Also your second set of compares are confusing.. what is m_bHasCarbon.