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.

@jogojapan is right, imagine two objects `a` and `b` with the same symbol: your operator gives both `a < b` and `b < a`... — Andy Prowl, Feb 28 '13 at 02:13
Your m_bHasCarbon cndition is not clear, can you describe what are you trying to do? — Slava, Feb 28 '13 at 02:17
Throwing on an invalid '<' is not standard, is it? Is this UB territory that the compiler can do whatever for? — Stephen Lin, Feb 28 '13 at 02:26
The m_bHasCarbon is needed as the entire list of FormulaStruct's need to know whether there is carbon in the formula, which would dictate the final structure using the hill system. — user1294021, Feb 28 '13 at 04:16

Stephen Lin · Accepted Answer · 2013-02-28T02:56:34.220

2

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.

edited Feb 28 '13 at 02:56

answered Feb 28 '13 at 02:45

Stephen Lin

5,470
26
48

This works great, I am still struggling with the whole "Strict Weak Ordering" rule, I use Visual Studio 2010 and I am unsure whether std::tie made it into the compiler as it is not working for me, so I used the second version and it is working good. – user1294021 Feb 28 '13 at 04:34
See the top answer [here](http://stackoverflow.com/questions/9040689/stl-less-operator-and-invalid-operator-error) for the properties a Strict Weak Ordering needs to fulfill. – Stephen Lin Feb 28 '13 at 04:45
Also, I'll take your word that it's working for you, but I'm ignoring `m_bHasCarbon` and still can't tell if it's important here or not. – Stephen Lin Feb 28 '13 at 04:46
It is only important in the case that there is no carbon, for instance with CHAr would be properly ordered, but with carbon removed, it would be ordered as ArH – user1294021 Feb 28 '13 at 05:13
is `m_bHasCarbon` specific to each `FormulaStruct` or is it the same for the entire `FormulaList`? If it's the latter it probably shouldn't be a member variable of `FormulaStruct`--that's confusing – Stephen Lin Feb 28 '13 at 05:23
(Although if you don't want to bother with changing that and if I'm understanding you correctly, then just put a check to skip four`if` statements if `m_bHasCarbon` is false) – Stephen Lin Feb 28 '13 at 05:27

score 1 · Answer 2 · answered Feb 28 '13 at 02:16

//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.

std::list Strict Weak Ordering

2 Answers2