c++c++11templatesstdmetaprogramming

Unclear template resolution


I was going through the exercises in this post https://www.slamecka.cz/posts/2021-03-17-cpp-metaprogramming-exercises-1/

First of all, I want to say huge thanks to the author. The problems were quite interesting, challenging, and engaging.

One part of the problem caused me some issues, and I don't really understand why.

/**
 * 18. Define Insert for Vector, it should take position, value and vector.
 * Don't worry about bounds.
 * Hint: use the enable_if trick, e.g.
 *   template<typename X, typename Enable = void> struct Foo;
 *   template<typename X> struct<std::enable_if_t<..something      about X..>> Foo {...};
 *   template<typename X> struct<std::enable_if_t<..something else about X..>> Foo {...};
 */

// Your code goes here:
// ^ Your code goes here

// static_assert(std::is_same_v<Insert<0, 3, Vector<4,5,6>>::type, Vector<3,4,5,6>>);
// static_assert(std::is_same_v<Insert<1, 3, Vector<4,5,6>>::type, Vector<4,3,5,6>>);
// static_assert(std::is_same_v<Insert<2, 3, Vector<4,5,6>>::type, Vector<4,5,3,6>>);
// static_assert(std::is_same_v<Insert<3, 3, Vector<4,5,6>>::type, Vector<4,5,6,3>>);

I started tackling this issue disregarding the hint from the author.

This was my first try.

template <int P, int I, typename V> struct Insert;

template <int P, int I, int F, int... N> struct Insert<P, I, Vector<F, N...>> {
  using type = Prepend<F, typename Insert<P - 1, I, Vector<N...>>::type>::type;
};

template <int I, int... N> struct Insert<0, I, Vector<N...>> {
  using type = typename Prepend<I, Vector<N...>>::type;
};

As an error message to this approach, the compiler complains about disambiguosity

E:\problems\main.cpp(212,20): error: ambiguous partial specializations of 'Insert<0, 3, (anonymous namespace)::Vector<4, 5, 6>>'
[build]   212 |     std::is_same_v<Insert<0, 3, Vector<4, 5, 6>>::type, Vector<3, 4, 5, 6>>);
[build]       |                    ^
[build] E:\problems\main.cpp(163,49): note: partial specialization matches [with P = 0, I = 3, F = 4, N = <5, 6>]
[build]   163 | template <int P, int I, int F, int... N> struct Insert<P, I, Vector<F, N...>> {
[build]       |                                                 ^
[build] E:\problems\main.cpp(167,35): note: partial specialization matches [with I = 3, N = <4, 5, 6>]
[build]   167 | template <int I, int... N> struct Insert<0, I, Vector<N...>> 

Then I read the hint, and thought, what if I just use std::conditional_t

template <int P, int I, typename V> struct Insert;

template <int P, int I, int F, int... N> struct Insert<P, I, Vector<F, N...>> {
  using type = std::conditional_t<
      P == 0, typename Prepend<I, Vector<N...>>::type,
      typename Prepend<F, typename Insert<P - 1, I, Vector<N...>>::type>::type>;
};

And this time I got a different error message

[build] E:\problems\main.cpp(178,36): error: implicit instantiation of undefined template '(anonymous namespace)::Insert<-3, 3, (anonymous namespace)::Vector<>>'
[build]   178 |       typename Prepend<F, typename Insert<P - 1, I, Vector<N...>>::type>::type>;
[build]       |                                    ^
[build] E:\problems\main.cpp(178,36): note: in instantiation of template class '(anonymous namespace)::Insert<-2, 3, (anonymous namespace)::Vector<6>>' requested here
[build] E:\problems\main.cpp(178,36): note: in instantiation of template class '(anonymous namespace)::Insert<-1, 3, (anonymous namespace)::Vector<5, 6>>' requested here
[build] E:\problems\main.cpp(222,20): note: in instantiation of template class '(anonymous namespace)::Insert<0, 3, (anonymous namespace)::Vector<4, 5, 6>>' requested here
[build]   222 |     std::is_same_v<Insert<0, 3, Vector<4, 5, 6>>::type, Vector<3, 4, 5, 6>>);
[build]       |                    ^
[build] E:\problems\main.cpp(173,44): note: template is declared here
[build]   173 | template <int P, int I, typename V> struct Insert;
[build]       |                                            ^

Could anyone please explain why I get these messages, why do they differ?


Solution

  • The code failed because the template specialization in general is too broad. you cant prevent this

    template <int I, int... N>
    struct Insert<0, I, Vector<N...>> {
        using type = typename Prepend<I, Vector<N...>>::type;
    };
    

    and this

    template <int P, int I, int F, int... N>
    struct Insert<P, I, Vector<F, N...>> {
        using type = typename Prepend<F, typename Insert<P - 1, I, Vector<N...>>::type>::type;
    };
    

    From matching P = 0 even though the second code is intended for recursion. If P = 0 then P = 0. You have to handle it manually.

    An adequate solution for this is using std::enable_if to prevent the recursion specialization from matching with P == 0 when it eventually reaches the case where P = 0

    // forward declaration of Insert with std::enable_if
    template <int P, int I, typename V, typename Enable = void>
    struct Insert;
    
    // specialization for P > 0 for recursion
    template <int P, int I, int F, int... N>
    struct Insert<P, I, Vector<F, N...>, std::enable_if_t<(P > 0)>> {
        using type = typename Prepend<F, typename Insert<P - 1, I, Vector<N...>>::type>::type;
    };