C++ strict weak ordering derived class

Question

I'm trying to implement strict weak ordering in a subclass that I want to place in an STL set container. The STL set uses operator< to order its elements in strict weak ordering. In my case I have a hierarchy of types and I am not quite sure how to achieve this for derived types. To this end, I put together a quick live demo showing where I am uncertain. I am ordering the fields using an easy to use std::tie technique. My area of uncertainty is how I should call the superclass' operator< prior to calling the std::tie comparison on the derived fields.

struct Base {
    Base(const int& rIntVal,  const std::string& rStrVal)
        : mIntVal(rIntVal)
        , mStrVal(rStrVal)
    {}
    inline bool operator<(const Base& rhs) const {
        return std::tie(mIntVal, mStrVal) < std::tie(rhs.mIntVal, rhs.mStrVal);
    }
private:    
    int mIntVal;
    std::string mStrVal;
};

struct Derived : public Base {
    Derived(
        const int& rIntVal, 
        const std::string& rStrVal, 
        const std::string& rOtherStrVal,
        const std::string& rOtherStrVal1)
        : Base(rIntVal, rStrVal)
        , mOtherStrVal(rOtherStrVal)
        , mOtherStrVal1(rOtherStrVal1)
    {}
    inline bool operator<(const Derived& rhs) const {
        // not sure what to do here - this is my best guess???
        if( Base::operator<(rhs) ) {
            return std::tie(mOtherStrVal, mOtherStrVal1) < 
                std::tie(rhs.mOtherStrVal, rhs.mOtherStrVal1);
        } else {
            return false;
        }
    }
private:    
    std::string mOtherStrVal;
    std::string mOtherStrVal1;
};

score 4 · Answer 1 · answered Jul 02 '15 at 16:56

You would do best to tie a reference to the base class:

bool operator<(const Derived& rhs) const {
    return std::tie(static_cast<const Base&>(*this), mOtherStrVal, mOtherStrVal1) < 
        std::tie(static_cast<const Base&>(rhs), rhs.mOtherStrVal, rhs.mOtherStrVal1);
}

This will compare by the superclass fields first and then by the subclass fields.

Jonathan Wakely · Accepted Answer · 2015-10-01T10:03:00.877

2

Firstly, you could choose to have the derived fields take priority over the base ones, so that the derived members are considered first, or you could give the base fields priority. Which to do depends on the meaning of your class and how it should be sorted.

You have chosen to compare the base fields first, which is fine, so we'll go with that.

To be a strict weak ordering you should only compare the derived fields when the base sub-objects are equivalent (i.e. neither is less-than the other).

With your current code if you have lhs.mIntVal < rhs.mIntVal you should return true, but instead you go on to compare the derived fields, and might end up saying that lhs is not less than rhs even though the the result from the base class says it is.

So to make the result correct you need something equivalent to:

bool operator<(const Derived& rhs) const {
    if (Base::operator<(rhs))
      return true;
    else if (rhs.Base::operator<(*this))
      return false;
    // base parts are equivalent, compare derived parts:
    return std::tie(mOtherStrVal, mOtherStrVal1) < 
           std::tie(rhs.mOtherStrVal, rhs.mOtherStrVal1);
}

This is logically correct, but sub-optimal because you call Base::operator< twice. You could avoid that by including the base objects in the tie expression as ecatmur shows.

edited Oct 01 '15 at 10:03

answered Jul 02 '15 at 16:56

Jonathan Wakely

166,810
27
341
521

is this equivalent to the answer below by ecatmur? – johnco3 Jul 07 '15 at 03:44
It will give the same answer, but is less efficient than ecatmur's in some cases. My answer explains the problem in detail, but ecatmur's answer gives the best solution to that problem. – Jonathan Wakely Jul 07 '15 at 09:31
great answer, BTW I forgot to ask - In your example, how do I get 'rhs.Base::operator<(lhs)' to compile without performing a static case to a base? – johnco3 Sep 30 '15 at 19:49
@Johanthan Wakely - I have an example here that does not quite compile: http://coliru.stacked-crooked.com/a/a58b44078ffb6d12 – johnco3 Sep 30 '15 at 19:57
`rhs.Base::operator<(lhs)` explicitly names the function `Base::operator<` which accepts an argument of type `const Base&` so no cast is necessary, it converts implicitly. – Jonathan Wakely Oct 01 '15 at 09:58
1

@johnco3, because you've got your braces wrong, you are missing a `{` after the last `else` in `operator<`. Get an editor that allows you to check whether braces match up and it becomes obvious. Also `lhs` should have been `*this` in my answer (fixed now). http://coliru.stacked-crooked.com/a/44dcf43b9a7cae88 – Jonathan Wakely Oct 01 '15 at 10:03
@Johnathan Wakely - my bad!!! fixed now with comments http://coliru.stacked-crooked.com/a/e78a3c0029e2c5a0 thanks for your help. – johnco3 Oct 01 '15 at 15:39

C++ strict weak ordering derived class

2 Answers2