Template isn't resolving type to correct overload

Question

This is on Visual Studio 2010, utilizing Boost v1.48.0. I'm trying to get a boost::variant with some structs and shared pointers to structs to match the right members of a boost::static_visitor, without success...

For my problem, let's establish this premise, as an example:

struct t_type_A { int key; foo value; };
struct t_type_B { int key; bar value; };
struct t_type_C { int key; baz value; };
struct t_type_D { int key; qux value; };

bool operator<(const t_type_A &, const t_type_A &);
bool operator<(const t_type_B &, const t_type_B &);
bool operator<(const t_type_C &, const t_type_C &);
bool operator<(const t_type_D &, const t_type_D &);

bool operator==(const t_type_A &, const t_type_A &);
bool operator==(const t_type_B &, const t_type_B &);
bool operator==(const t_type_C &, const t_type_C &);
bool operator==(const t_type_D &, const t_type_D &);

typedef std::shared_ptr<t_type_C> t_shared_C;
typedef std::shared_ptr<t_type_D> t_shared_D;

typedef boost::variant<t_type_A, t_type_B, t_shared_C, t_shared_D> t_variant;

I have a visitor as follows:

class variant_less : public boost::static_visitor<bool>
{
public:
    template<typename T>
    result_type operator()(const T &left, const T &right) const
    {
            return left.value < right.value || (left.value == right.value && left.key < right.key);
    }

    template<typename T, typename U>
    result_type operator()(const T &left, const U &right) const
    {
            return left.key < right.key;
    }

    template<typename T>
    result_type operator()(const std::shared_ptr<T> &left, const std::shared_ptr<T> &right) const
    {
            return left->value < right->value || (left->value == right->value && left->key < right->key);
    }

    template<typename T, typename U>
    result_type operator()(const std::shared_ptr<T> &left, const std::shared_ptr<U> &right) const
    {
            return left->key < right->key;
    }
};

In practice, when I apply the visitor to my variants, I get a compiler errors as:

EDIT: I had to look at the error message again. I mistranslated that to this example, it's not complaining about 'value' but'key'. The error is fixed below.

error C2039: 'key' : is not a member of 'std::tr1::shared_ptr<_Ty>'

The compiler is resolving the comparison between two t_shared_C or two t_shared_D as:

template<typename T, typename U>
result_type operator()(const T &left, const U &right) const

being the best fit. This is obviously not what I desire. Alternately, I've tried the following, based on my shaky knowledge of SFINAE:

class variant_less : public boost::static_visitor<bool>
{
public:
    template<typename T>
    result_type operator()(const T &left, const T &right) const
    {
            return left.value < right.value || (left.value == right.value && left.key < right.key);
    }

    template<typename T, typename U>
    result_type operator()(const T &left, const U &right) const
    {
            return left.key < right.key;
    }

    template<typename T>
    result_type operator()(const T &left, const T &right) const
    {
            return left->value < right->value || (left->value == right->value && left->key < right->key);
    }

    template<typename T, typename U>
    result_type operator()(const T &left, const U &right) const
    {
            return left->key < right->key;
    }
};

What am I doing wrong? I don't want to give up and write overloads for every combination.

EDIT: Here is how it's getting invoked:

typedef boost::multi_index::multi_index_container<
    t_variant_vector,
    boost::multi_index::indexed_by<
        boost::multi_index::ordered_unique<variant_extractor<1234>, variant_less>
      , boost::multi_index::ordered_non_unique<variant_extractor<5678>, variant_less>
      // arbitrarily more indexes go here
    >
> t_variant_multi_index;

The vector is a sorted vector of variants, sorted by key. The indexes are so indexed by the presence of variants with particular 'key' values. variant_extractor finds and pulls the variant with the matching key. As a brief on what mult_index is then doing, the result of the 'key extractor', a variant, is then used as a parameter to the 'comparison predicate', variant_less, for sorting that index.

Answer 1

This is related to template instantiation. When compiling, T and shared_ptr are both considered as a certain type, and compiler doesn't differentiate a plain type or a share_ptr type, so the compiler will find the first matched template function definition to instantiate the function, that's how your error happens.

You can do something similar as std traits: provide two tag types:

struct plain_type_tag{};
struct shareptr_type_tag{};

Then change your functions to:

 template<typename T, typename U>
    result_type operator()(const T &left, const U &right, plain_type_tag) const
    {
            return left.key < right.key;
    }

    template<typename T>
    result_type operator()(const std::shared_ptr<T> &left, const std::shared_ptr<T> &right, shareptr_type_tag) const
    {
            return left->value < right->value || (left->value == right->value && left->key < right->key);
    }

For you reference:

1. An Introduction to "Iterator Traits". It deals with similar problems.
2. Function template: explain the function template instantiation

Answer 2

The problem is that apply_visitor must instantiate the operator() of the MultiVisitor for all combinations of the variants' contents: It is a run-time decision which function will be called (since the type of the content of the variant is only known at run-time).

Therefore, the MultiVisitor has to support all combinations of arguments. This includes combinations where one argument is a shared_ptr but the other one is not.

Here's a solution that simply unpacks all shared_ptrs. This also removes the code duplication.

class variant_less : public boost::static_visitor<bool>
{
private:
    template<typename T>
    result_type impl(const T &left, const T &right) const
    {
        return    left.value < right.value
               || (left.value == right.value && left.key < right.key);
    }

    template<typename T, typename U>
    result_type impl(const T &left, const U &right) const
    {
            return left.key < right.key;
    }

    template<typename T>
    static T const& unpack(T const& p)
    {
        return p;
    }
    template<typename T>
    static T const& unpack(std::shared_ptr<T> const& p)
    {
        return *p;
    }

public:
    template<typename T, typename U>
    result_type operator()(const T& left, const U& right) const
    {
        return impl(unpack(left), unpack(right));
    }
};

Live example