storing std::reference_wrapper<MyType> into std::set

Question

I was hoping infer std::reference_wrapper<MyType> to MyType& automagically on bool operator<(. It is not matching the method. But the code is compiling when I add additional bool operator<( method. Am I missing something?

#include <iostream>
#include <set>
#include <functional>


class MyType {
public:
    bool operator<(const MyType& target) const {
        return this < &target;
    }
};

// it doesn't compile if remove the method below.
bool operator<(const std::reference_wrapper<MyType>& a, const MyType& b) {
    return a.get() < b;
}

int main(int argc, char* argv[]) {

    std::set<std::reference_wrapper<MyType>> types;

    MyType t1, t2, t3;

    types.insert(std::ref(t1));
    types.insert(std::ref(t2));
    types.insert(std::ref(t3));
    types.insert(std::ref(t1));

    std::cout << "size: " << types.size() << std::endl;

    return 0;
}

Answer 1

The std::less compare functor as used in this answer does not yield the expected result. The reason is that it uses the content of the reference of type MyType instead of the reference to the variable of type MyType as index into the set. Try this:

template<typename T>
void printReferenceContainer(T &container) {
    std::cout << "content of container:" << std::endl;
    for (auto item: container) {
        std::cout << "item: " << item.get() << std::endl;
    }
    std::cout << "done" << std::endl;
    std::cout << std::endl;
}

int main() {
    std::set<std::reference_wrapper<std::string>, std::less<std::string>> container;

    std::string a = "val 1";
    std::string b = "val 2";
    std::string c = "val 2"; // same value as b
    std::string d = "val 4";

    container.emplace(a);
    container.emplace(b);
    container.emplace(c);
    container.emplace(d);

    printReferenceContainer(container);

    a = "val 10";
    b = "val 11";
    c = "val 12";
    d = "val 13";

    printReferenceContainer(container);

    return 0;
}

While one expects 4 values in the set, because the references to 4 different variables have been added, there are only 3, because the value of variable b and c is the same, leading to c not being added, because its value is already contained in the set:

content of container:
item: val 1
item: val 2
item: val 4
done

content of container:
item: val 10
item: val 11
item: val 13
done

The std::less functor in fact does not take the reference for comparison, but its content, by using the implicit type cast operator to MyType, in this case std::string.

To solve this a closer look to what std::reference_wrapper really does is necessary. References do not really exist in a way that they occupy memory. In a very simplified way, they are just compiler aliases for the variable they are assigned with. See https://isocpp.org/wiki/faq/references for a more detailed explanation.

The std::reference_wrapper mimics this behavior by holding an internal pointer to the variable it references. It supplies all the necessary member functions like an implicit constructor, assignment operator, type cast operator, etc. to act like a normal compiler generated reference. But it is in fact just a struct that holds a pointer. Being this it can be stored in a standard container, other than a real reference. The downside is that it does not have comparison operators, like less than, that compares the reference itself.

As the std::set stores only unique values, whose uniqueness and order it determines by using the less than operator, it cannot naively store a std::reference_wrapper. It needs help, by providing a comparison functor. When using std::less<std::string>, the std::reference_wrapper now does exactly what it is expected to do. It acts like a real reference to its originally assigned variable and therefore the std::less functor compares the content of the reference, as stated above, leading to the undesired behavior.

The solution is to provide a custom comparison functor that compares the std::reference_wrapper class instance itself, not its content. It can do so, by comparing the internal pointer of the std::reference_wrapper struct. As the internal pointer very likely is a private member, its value can be derived only by using the get() member, which returns a reference to the contained value and then taking its address. This in terms is of course the address of the originally assigned variable:

std::string myVar = "Hello World";
std::reference_wrapper<std::string> wrappedRef = myVar;

std::string * pWrappedRefContent = &wrappedRef.get();
std::string * pMyVar = &myVar;

std::cout << "&wrappedRef.get(): " << pWrappedRefContent << std::endl;
std::cout << "&myVar           : " << pMyVar << std::endl;
std::cout << "&wrappedRef.get() and &myVar are " << (pWrappedRefContent==pMyVar? "equal" : "not equal") << std::endl;

Yields:

&wrappedRef.get(): 0x7fffffffe2e0
&myVar           : 0x7fffffffe2e0
&wrappedRef.get() and &myVar are equal

With this knowledge a ref_less comparison functor can be defined like this:

template<typename T>
struct ref_less {
    // use the 'take address' operator of the reference_wrappers get() for comparison
    bool operator()(const T &x, const T &y) const {
        return &x.get() < &y.get();
    }
};

int main() {
    std::set<std::reference_wrapper<std::string>, ref_less<std::reference_wrapper<std::string>>> container;

    std::string a = "val 1";
    std::string b = "val 2";
    std::string c = "val 2"; // same value as b
    std::string d = "val 4";

    container.emplace(a);
    container.emplace(b);
    container.emplace(c);
    container.emplace(d);

    printReferenceContainer(container);

    a = "val 10";
    b = "val 11";
    c = "val 12";
    d = "val 13";

    printReferenceContainer(container);

    return 0;
}

As can be seen this time it holds all variables:

content of container:
item: val 1
item: val 2
item: val 2
item: val 4
done

content of container:
item: val 10
item: val 11
item: val 12
item: val 13
done

There's still one drawback or better possibly unexpected behavior. As the std::set is ordered by the given functor, the sets sort order is determined by the address of the referenced variables rather than by their content. The sort order is therefore meaningless and possibly compiler dependent. Of course it would be meaningless anyway, as the content can change at any time and the set has no means of knowing it.

If the variable d is defined first, with this compilers implementation it is ordered first:

std::string d = "val 4";
std::string a = "val 1";
std::string b = "val 2";
std::string c = "val 2"; // same value as b

The output is:

content of container:
item: val 4
item: val 1
item: val 2
item: val 2
done

content of container:
item: val 13
item: val 10
item: val 11
item: val 12
done

So this sort of container may serve the very particular purpose, that it holds a bunch of references to variables and makes sure a variable cannot be added twice, but looses the sorting property of the set.

Answer 2

Adding a comparator is solved the problem.

std::set<std::reference_wrapper<MyType>> types;

to

std::set<std::reference_wrapper<MyType>, std::less<MyType>> types;