The examples shown below are just toy examples, if you weren't already able to catch on.

In the code snippet below, how should we implement pair_typeid?

class Base1{
    public:
        constexpr virtual ~Base1() noexcept = default;
    protected:
        constexpr Base1() noexcept = default;
        constexpr Base1(const Base1&) noexcept = default;
        constexpr Base1(Base1&&) noexcept = default;

        constexpr Base1& operator=(const Base1&) noexcept = default;
        constexpr Base1& operator=(Base1&&) noexcept = default;
};

class Base2{
    public:
        constexpr virtual ~Base2() noexcept = default;
    protected:
        constexpr Base2() noexcept = default;
        constexpr Base2(const Base2&) noexcept = default;
        constexpr Base2(Base2&&) noexcept = default;

        constexpr Base2& operator=(const Base2&) noexcept = default;
        constexpr Base2& operator=(Base2&&) noexcept = default;
};

class Derived1_1 final: public Base1{/* code */};

class Derived1_2 final: public Base1{/* code */};

class Derived2_1 final: public Base2{/* code */};

class Derived2_2 final: public Base2{/* code */};

/**
 * @brief Gets the `typeid(std::pair<dynamic type of 1st param, dynamic type of 2nd param>)`.
 * 
 * More formally, `pair_typeid(r1, r2) == typeid(std::pair<T1, T2>)`
 * where `T1` is the dynamic type of the referent of `r1`
 * and `T2` is the dynamic type of the referent of `r2`.
 * 
 * @return `const std::type_info&`
 */
constexpr const std::type_info& pair_typeid(const Base1&, const Base2&) noexcept;

If Derived1_1, Derived1_2, Derived2_1, and Derived2_2 were the only classes to use this function, we could use dynamic_cast or typeid, but that's inelegant so we instead use the visitor pattern in the below impl, because it avoids this. Note how we restrict the extent of the double dispatch.

class Base1;

class Base2;

class Derived2_1;

class Derived2_2;

namespace detail{
    template <class T>
    constexpr const std::type_info& visit_pair_typeid(const Base1&, const T&) noexcept;
}

class Base1{
    public:
        constexpr virtual ~Base1() noexcept = default;
    protected:
        constexpr Base1() noexcept = default;
        constexpr Base1(const Base1&) noexcept = default;
        constexpr Base1(Base1&&) noexcept = default;

        constexpr Base1& operator=(const Base1&) noexcept = default;
        constexpr Base1& operator=(Base1&&) noexcept = default;

        constexpr virtual const std::type_info& visit_pair_typeid(const Derived2_1&) const noexcept = 0;
        constexpr virtual const std::type_info& visit_pair_typeid(const Derived2_2&) const noexcept = 0;

        template <class T>
        friend constexpr const std::type_info& detail::visit_pair_typeid(const Base1&, const T&) noexcept;
};

template <class T>
constexpr const std::type_info& detail::visit_pair_typeid(const Base1& star_this, const T& acceptor) noexcept{return star_this.visit_pair_typeid(acceptor);}

/**
 * @brief Gets the `typeid(std::pair<dynamic type of 1st param, dynamic type of 2nd param>)`.
 * 
 * More formally, `pair_typeid(r1, r2) == typeid(std::pair<T1, T2>)`
 * where `T1` is the dynamic type of the referent of `r1`
 * and `T2` is the dynamic type of the referent of `r2`.
 * 
 * @return `const std::type_info&`
 */
constexpr const std::type_info& pair_typeid(const Base1&, const Base2&) noexcept;

class Base2{
    public:
        constexpr virtual ~Base2() noexcept = default;
    protected:
        constexpr Base2() noexcept = default;
        constexpr Base2(const Base2&) noexcept = default;
        constexpr Base2(Base2&&) noexcept = default;

        constexpr Base2& operator=(const Base2&) noexcept = default;
        constexpr Base2& operator=(Base2&&) noexcept = default;

        constexpr virtual const std::type_info& accept_pair_typeid(const Base1&) const noexcept = 0;

        template 
        static constexpr const std::type_info& accept_pair_typeid_impl(const T& star_this, const Base1& visitor) noexcept{return detail::visit_pair_typeid(visitor, star_this);}

        friend constexpr const std::type_info& pair_typeid(const Base1& r1, const Base2& r2) noexcept{return r2.accept_pair_typeid(r1);}
};

class Derived2_1 final: public Base2{
    protected:
        constexpr const std::type_info& accept_pair_typeid(const Base1& visitor) const noexcept final{return accept_pair_typeid_impl(*this, visitor);}
};

class Derived2_2 final: public Base2{
    protected:
        constexpr const std::type_info& accept_pair_typeid(const Base1& visitor) const noexcept final{return accept_pair_typeid_impl(*this, visitor);}
};

class Derived1_1 final: public Base1{
    protected:
        constexpr const std::type_info& visit_pair_typeid(const Derived2_1&) const noexcept final{return typeid(std::pair<Derived1_1, Derived2_1>);}
        constexpr const std::type_info& visit_pair_typeid(const Derived2_2&) const noexcept final{return typeid(std::pair<Derived1_1, Derived2_2>);}
};

class Derived1_2 final: public Base1{
    protected:
        constexpr const std::type_info& visit_pair_typeid(const Derived2_1&) const noexcept final{return typeid(std::pair<Derived1_2, Derived2_1>);}
        constexpr const std::type_info& visit_pair_typeid(const Derived2_2&) const noexcept final{return typeid(std::pair<Derived1_2, Derived2_2>);}
};

A minor benefit of the visitor pattern is that adding more visitors is extremely easy. This allows templatization of the visitor.

class Base1;

class Base2;

class Derived2_1;

class Derived2_2;

namespace detail{
    template <class T>
    constexpr const std::type_info& visit_pair_typeid(const Base1&, const T&) noexcept;
}

class Base1{
    public:
        constexpr virtual ~Base1() noexcept = default;
    protected:
        constexpr Base1() noexcept = default;
        constexpr Base1(const Base1&) noexcept = default;
        constexpr Base1(Base1&&) noexcept = default;

        constexpr Base1& operator=(const Base1&) noexcept = default;
        constexpr Base1& operator=(Base1&&) noexcept = default;

        constexpr virtual const std::type_info& visit_pair_typeid(const Derived2_1&) const noexcept = 0;
        constexpr virtual const std::type_info& visit_pair_typeid(const Derived2_2&) const noexcept = 0;

        template <class T>
        friend constexpr const std::type_info& detail::visit_pair_typeid(const Base1&, const T&) noexcept;
};

template <class T>
constexpr const std::type_info& detail::visit_pair_typeid(const Base1& star_this, const T& acceptor) noexcept{return star_this.visit_pair_typeid(acceptor);}

/**
 * @brief Gets the `typeid(std::pair<dynamic type of 1st param, dynamic type of 2nd param>)`.
 * 
 * More formally, `pair_typeid(r1, r2) == typeid(std::pair<T1, T2>)`
 * where `T1` is the dynamic type of the referent of `r1`
 * and `T2` is the dynamic type of the referent of `r2`.
 * 
 * @return `const std::type_info&`
 */
constexpr const std::type_info& pair_typeid(const Base1&, const Base2&) noexcept;

class Base2{
    public:
        constexpr virtual ~Base2() noexcept = default;
    protected:
        constexpr Base2() noexcept = default;
        constexpr Base2(const Base2&) noexcept = default;
        constexpr Base2(Base2&&) noexcept = default;

        constexpr Base2& operator=(const Base2&) noexcept = default;
        constexpr Base2& operator=(Base2&&) noexcept = default;

        constexpr virtual const std::type_info& accept_pair_typeid(const Base1&) const noexcept = 0;

        template <class T>
        static constexpr const std::type_info& accept_pair_typeid_impl(const T& star_this, const Base1& visitor) noexcept{return detail::visit_pair_typeid(visitor, star_this);}

        friend constexpr const std::type_info& pair_typeid(const Base1& r1, const Base2& r2) noexcept{return r2.accept_pair_typeid(r1);}
};

class Derived2_1 final: public Base2{
    protected:
        constexpr const std::type_info& accept_pair_typeid(const Base1& visitor) const noexcept final{return accept_pair_typeid_impl(*this, visitor);}
};

class Derived2_2 final: public Base2{
    protected:
        constexpr const std::type_info& accept_pair_typeid(const Base1& visitor) const noexcept final{return accept_pair_typeid_impl(*this, visitor);}
};

template <std::size_t N>
class Derived1: public Base1{
    protected:
        constexpr const std::type_info& visit_pair_typeid(const Derived2_1&) const noexcept final{return typeid(std::pair<Derived1, Derived2_1>);}
        constexpr const std::type_info& visit_pair_typeid(const Derived2_2&) const noexcept final{return typeid(std::pair<Derived1, Derived2_2>);}
};

Unfortunately, templatizing the acceptor requires templatizing virtual functions. Workarounds like templatizing base classes don't solve the problem at hand. This problem is a stand-in for a problem where CRTP doesn't work and runtime dispatch is needed, as well as both parameters to the real function being part of an unbounded set of types. What's the real solution to the problem? Which idiom can I use?