Custom comparator via explicit constructor for sorting std::set

Question

I've got a set of pointers which I would like to iterate over in a deterministic manner. Obviously if I use the default sort order for set, this will be based on the pointers memory addresses which can be different each time the program runs. So I define a custom comparator which I want to use, but I don't want to change the templated type of the set (because it's used in a million places in the code), so I want to pass in a comparator object to the set constructor which is derived from std::less

class TestClass
{
public:
    TestClass(int id_) : id(id_)    {}
    ~TestClass()                    {}
    int  getId() const              { return id;}
    void setId(int id_)             { id = id_; }
private: 
    int id; 
};

struct TestClassLessThan : public std::less<TestClass*>
{   // functor for operator<
    bool operator()(const TestClass* &_Left, const TestClass* &_Right) const
    {   // apply operator< to operands
        return (_Left->getId() < _Right->getId());
    }
};


int main(void)
{
    TestClassLessThan comp; 
    set<TestClass*> testSet(comp), testSet2(comp);

    TestClass* obj1 = new TestClass(1);
    TestClass* obj2 = new TestClass(2);
    testSet.insert(obj1);
    testSet.insert(obj2);

    TestClass* obj = *(testSet.begin());

    cout << "First run" << endl;
    BOOST_FOREACH(TestClass* o, testSet)  // expecting 1,2 - get 1,2
        cout << o->getId() << endl;

    // now change the ordering (based on id) and insert into a new set in the same order
    obj1->setId(3);
    testSet2.insert(obj1);
    testSet2.insert(obj2);

    cout << "Second run" << endl;
    BOOST_FOREACH(TestClass* o, testSet2) // expecting 2,3 - get 3,2
        cout << o->getId() << endl;

    delete obj1;
    delete obj2;
}

So my question is, what have I forgotten to do?

score 3 · Answer 1 · answered Dec 13 '10 at 02:26

The std::set constructor's formal argument type for the comparator object is Compare const&, where Compare is the template parameter.

So even if the set object retained a reference to your actual comparator object (instead of copying it), it would be treated as type Compare, which you have defaulted to std::less.

And since std::less is non-polymorphic it's std::less::operator() that is called, not your operator() down in TestClassLessThan.

So the short of it is, "you can't do that".

Or rather, you can, as your code illustrates, but you don't get any behavior change.

To change the comparision object you have to specify some other Compare type as template argument.

Which is what you wanted to avoid, but sorry, there's no way around (that I know of).

Cheers & hth.,

score 3 · Accepted Answer · answered Dec 13 '10 at 02:59

All the above is valid. A possible solution is to customise std::less itself using template specialisation:

namespace std
{
    template<>
    struct less< TestClass*>
    {   // functor for operator<
    public:
        bool operator()(  TestClass* const  &_Left,  TestClass* const  &_Right) const
        {   // apply operator< to operands      
            return (_Left->getId() < _Right->getId());
        }
    };
}

You then get your custom behaviour using the default template comparator for std::set.

Depending on how you build your system, you may have problems if the set is "used in a million places " and the custom std::less is not consistently available.

that is perfect... but you are saying that if I declare set in one class but it is then passed to another which doesn't include the custom less - that second class may have different/undefined behaviour? I think i'll make sure that the definition of the set and it's accessor methods all include the custom less specialisation. — Jamie Cook, Dec 13 '10 at 21:11

score 1 · Answer 3 · answered Dec 13 '10 at 02:36

That is not the way to use set with a comparator. operator() of std::less is not a virtual function and will not be overridden.

Instead use this way to initialize and it will do the trick.

set<TestClass*, TestClassLessThan> testSet, testSet2;

For this to work, your compare function should accept const pointers and not pointers to const. To be safe you can change it to

 // functor for operator<
    bool operator()(const TestClass* const&_Left, const TestClass* const&_Right) const
    {   
        cout << "comparing";
        // apply operator< to operands
        return (_Left->getId() < _Right->getId());
    }

if you read the question you'll note that I don't want to change the signature of the set. — Jamie Cook, Dec 13 '10 at 03:28

Custom comparator via explicit constructor for sorting std::set

3 Answers3

Linked