CODEWITHSUNDEEP
c++stl
mic_e
mic_e

Reputation: 5830

How to store pointers (or references) to objects in a std::set

Are there any proper means in the C++11 STL to store object pointers in a std::set, and have them sorted properly by the object's operator < method?

There is, of course, the possibility of writing my own Compare type and passing that to the set as its second template argument, but I'd imagine that the STL would provide a much more convenient way.

A bit of googling revealed std::reference_wrapper, which in my opinion should allow code like this:

#include <functional>
#include <set>

struct T {
    int val;
    bool operator <(T& other) {
        return (this->val < other.val);
    }
};

int main() {
    std::set<std::reference_wrapper<T>> s;
    T a{5};
    s.insert(a);
}

But in fact, this causes a compiler error:

clang++ -std=c++11 -Wall -Wextra -pedantic test.cpp -o test
In file included from test.cpp:1:
In file included from /usr/bin/../lib64/gcc/x86_64-unknown-linux-gnu/4.8.2/../../../../include/c++/4.8.2/functional:49:
/usr/bin/../lib64/gcc/x86_64-unknown-linux-gnu/4.8.2/../../../../include/c++/4.8.2/bits/stl_function.h:235:20: error: invalid operands to binary expression ('const std::reference_wrapper<T>'
      and 'const std::reference_wrapper<T>')
      { return __x < __y; }
               ~~~ ^ ~~~

(the gcc error is similar, but a lot longer)

Upvotes: 5

Views: 2046

Answers (3)

BreakBadSP
BreakBadSP

Reputation: 860

The right approach is to create a specialized std::less for our MyStruct.

namespace std
{
    template<> struct  less<MyStruct>
    {
        bool operator() (const MyStruct& lhs, const MyStruct& rhs) const
        {
            return lhs.a < rhs.a;
        }
    };

}

Remember std::set uses std::less by default to compare two elements.

Defined in header <set>

template<

    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

https://en.cppreference.com/w/cpp/container/set

Upvotes: 0

juanchopanza
juanchopanza

Reputation: 227390

You need to make your less-than operator a non-member, and give it const reference parameters:

struct T {
    int val;
};

bool operator <(const T& lhs, const T& rhs) {
    return (lhs.val < rhs.val);
}

This allows for implicit conversions on from std::reference_wrapper<T> to T on both LHS and RHS of the < operator, whereas the member version only allows for an implicit conversion on the RHS. Symmetry between LHS and RHS of binary operators is one of the classic arguments for implementing them as non-members.

Upvotes: 6

wonce
wonce

Reputation: 1921

The object a method is called on cannot be implicitly converted, so you need to implement comparison as a free function to use the conversion from reference_wrapper<T> to T.

Upvotes: 2

Related Questions