Choose std::queue or std::priority_queue, depending on whether "<" is defined

Question

Inspired by SFINAE to check if std::less will work, I come to this:

template <typename F, typename S, typename = void>
struct QueueImpl {
    using type = std::queue<std::pair<F, S>>;
};

template <typename F, typename S>
struct QueueImpl<F, S, decltype(std::declval<F>() < std::declval<F>())> {
    using type = std::priority_queue<std::pair<F, S>>;
};

template <typename F, typename S>
using Queue = typename QueueImpl<F, S>::type;

with the intention that if < has been defined for type F, Queue will be std::priority_queue and otherwise std::queue. But it seems always to match the std::queue case:

class C {};

int main()
{
    Queue<int, char> q1;
    Queue<C, char> q2;
    std::cout << typeid(q1).name() << std::endl;
    std::cout << typeid(q2).name() << std::endl;
    return 0;
}

which shows both Queue's are std::queue:

St5queueISt4pairIicESt5dequeIS1_SaIS1_EEE
St5queueISt4pairI1CcESt5dequeIS2_SaIS2_EEE

My second attempt uses std::conditional:

template <typename F, typename S>
using Queue = typename std::conditional_t<
    std::is_same_v<bool, decltype(std::declval<F>() < std::declval<F>())>,
    std::priority_queue<std::pair<F, S>>,
    std::queue<std::pair<F, S>>>;

For q1, it successfully chooses std::priority_queue and prints St14priority_queueISt4pairIicESt6vectorIS1_SaIS1_EESt4lessIS1_EE. But when q2 is defined in the same way as the first attempt, the code cannot compile:

error: no match for ‘operator<’ (operand types are ‘C’ and ‘C’)

So how to make the code work?

There was a deleted answer from Sergey Kolesnik, which suggested using `std::void_t() < std::declval())>` in the specialized `QueueImpl` and in fact works. But why does this compile error happen in the substitution and the original one doesn't? And how is `std::void_t` different from the `void` in the base template? — Ziyuan, Sep 22 '22 at 21:35
I think your first attempt should work, but to be using the priority_queue a type needs to fail the requirements for queue (it is the first option the compiler and linker find), no type should fail that. Try swapping the declarations around, everything that fails the requirement for the priority_queue should then find the implementation using queue. Order sometimes does matter. — ZwergofPhoenix, Sep 22 '22 at 22:15

score 3 · Answer 1 · answered Sep 22 '22 at 21:48

For C++20 I'd go for concepts like in this answer. If you are using C++11 to C++17, you could use an old-school type trait:

template<class T>
struct has_less_than {
    static std::false_type test(...);
    
    template<class U>
    static auto test(U&&u) -> decltype(u < u, std::true_type{});

    static constexpr bool value = decltype(test(std::declval<T>()))::value;
};

#if __cplusplus >= 201402L
template<class T>     // variable template, available since C++14
static constexpr bool has_less_than_v = has_less_than<T>::value;
#endif

template <typename F, typename S>
using Queue = typename std::conditional<has_less_than<F>::value,
                                          std::priority_queue<std::pair<F, S>>,
                                          std::queue<std::pair<F, S>>
                                          >::type;

score 3 · Accepted Answer · answered Sep 23 '22 at 02:19

Your first attempt fails for the following reason. When you use the template, you don't specify the third argument. Hence, it is supplied from the default type in the primary template, namely void. Then, the specialization can only match the argument types if the decltype results in void, whereas when F is int, the type is bool.

Fixing this is as simple as casting the argument to decltype to void:

template <typename F, typename S, typename = void>
struct QueueImpl {
    using type = std::queue<std::pair<F, S>>;
};

template <typename F, typename S>
struct QueueImpl<F, S, decltype(void(std::declval<F>() < std::declval<F>()))> {
    using type = std::priority_queue<std::pair<F, S>>;
};

template <typename F, typename S>
using Queue = typename QueueImpl<F, S>::type;

Demo.

If both are `void`, why is one a specialization of the other? — Ziyuan, Sep 24 '22 at 16:39
The primary template has an arbitrary third type. True, there's a default, but you could specify a different type explicitly if you wanted. The specialization specifies the third type to be always decltype(void(std::declval() < std::declval())), which always evaluates to void when there is no substitution failure. — Eric M Schmidt, Sep 24 '22 at 19:12

score 2 · Answer 3 · answered Sep 22 '22 at 21:22

If C++20 concepts are acceptable, I would write it like this:

template <typename T>
concept HasLessThan = requires(const T& x, const T& y)
{
    { x < y } -> std::same_as<bool>;
};

template <typename F, typename S>
using Queue = typename std::conditional_t<
    HasLessThan<F>,
    std::priority_queue<std::pair<F, S>>,
    std::queue<std::pair<F, S>>>;

Choose std::queue or std::priority_queue, depending on whether "<" is defined

3 Answers3