variadic template: SFINAE on last argument

user_2646505 0
Viewed 90

I have an array (of any rank), and I would like to have an index operator that:

  1. Allows for missing indices, such that the following is equivalent

    a(1, 0, 0, 0);
a(1, my::missing);

    This in itself if straightforward (see example implementation below): one just recursively adds arg * strides[dim] until my::missing it hit.

  2. Allows automatic prepending of zeros, such that the following is equivalent

    a(0, 0, 0, 1);
a(1);

    Also this is not hard (see example implementation below): one recursively adds arg * strides[dim + offset].

What I cannot get my head around is: How to combine the two? The implementation of 2. makes me start of the wrong foot for 1. (I'm limited to <= C++14)

Example implementation of "my::missing" without auto pre-pending zeros

enum class my { missing };

template <size_t dim, class S>
inline size_t index_impl(const S&) noexcept
{
    return 0;
}

template <size_t dim, class S, class... Args>
inline size_t index_impl(const S& strides, enum my arg, Args... args) noexcept
{
    return 0;
}

template <size_t dim, class S, class Arg, class... Args>
inline size_t index_impl(const S& strides, Arg arg, Args... args) noexcept
{
    return arg * strides[dim] + index_impl<dim + 1>(strides, args...);
}

template <class S, class Arg, class... Args>
inline size_t index(const S& strides, Arg arg, Args... args)
{
    return index_impl<0>(strides, arg, args...);
}

int main()
{
    std::vector<size_t> strides = {8, 4, 2 ,1};
    std::cout << index(strides, 1, 2, 0, 0) << std::endl;
    std::cout << index(strides, 1, 2, my::missing) << std::endl;
}

Example implementation of prepending zeros without "my::missing"

template <size_t dim, class S>
inline size_t index_impl(const S&) noexcept
{
    return 0;
}

template <size_t dim, class S, class Arg, class... Args>
inline size_t index_impl(const S& strides, Arg arg, Args... args) noexcept
{
    return arg * strides[dim] + index_impl<dim + 1>(strides, args...);
}

template <class S, class Arg, class... Args>
inline size_t index(const S& strides, Arg arg, Args... args)
{
    constexpr size_t nargs = sizeof...(Args) + 1;
    if (nargs == strides.size())
    {
        return index_impl<0>(strides, arg, args...);
    }
    else if (nargs < strides.size())
    {
        return index_impl<0>(strides.cend() - nargs, arg, args...);
    }
    return index_impl<0>(strides, arg, args...);
}

int main()
{
    std::vector<size_t> strides = {8, 4, 2 ,1};
    std::cout << index(strides, 1, 2) << std::endl;
    std::cout << index(strides, 0, 0, 1, 2) << std::endl;
}
c++
2 Answers

In earlier version of this answer I didn't provided full implementation since something was not adding up for me.

If this index should calculate index for flattened multidimensional array then your example implementation is invalid. Problem is hidden since you are comparing two results for index with all indexes provided and shorten version where zero padding is assumed.
Sadly I flowed this pattern in first versions of test in Catch2.

Here is proper test for index of flattened multidimensional array, where last index matches flattened index:

TEST_CASE("index")
{
    std::vector<size_t> strides = { 4, 6, 3, 5 };

    SECTION("Padding with leading zeros")
    {
        constexpr auto i0 = 4;
        constexpr auto i1 = 2;
        constexpr size_t expected = i0 + i1 * 5;

        CHECK(index(strides, 0, 0, i1, i0) == expected);
        CHECK(index(strides, 0, 0, i1, i0 - 1) == expected - 1); // last index indexes by one
        CHECK(index(strides, i1, i0) == expected);
        CHECK(index(strides, i1, i0 - 1) == expected - 1);
    }

    SECTION("Use my::missing to use padding with tailing zeros")
    {
        constexpr auto i2 = 4;
        constexpr auto i3 = 2;
        constexpr size_t expected = (i3 * 6 + i2) * 5 * 3;

        CHECK(index(strides, i3, i2, 0, 0) == expected);
        CHECK(index(strides, i3, i2, my::missing) == expected);
    }
}

Now starting from your code and passing those test I've got this implementation:

template <typename T, typename... Ts>
struct last_type_helper {
    using type = typename last_type_helper<Ts...>::type;
};

template <typename T>
struct last_type_helper<T> {
    using type = T;
};

template <typename... Ts>
using last_type = typename last_type_helper<Ts...>::type;

enum class my { missing };
template <typename... Ts>
constexpr bool LastTypeIsMy = std::is_same<my, last_type<Ts...>>::value;

template <class StrideIter>
size_t index_impl(size_t base, StrideIter)
{
    return base;
}

template <class StrideIter>
size_t index_impl(size_t base, StrideIter, my)
{
    return base;
}

template <class StrideIter, typename Tn, typename... Ts>
size_t index_impl(size_t base, StrideIter it, Tn xn, Ts... x)
{
    return index_impl(base * *it + xn, it + 1, x...);
}

template <class S, class... Args>
size_t index(const S& strides, Args... args)
{
    const size_t offset = strides.size() - sizeof...(Args);
    const size_t advenceBy = LastTypeIsMy<Args...> ? 0 : offset;
    const size_t lastStrides = LastTypeIsMy<Args...> ? offset + 1 : 0;
    const size_t tailFactor = std::accumulate(std::end(strides) - lastStrides, std::end(strides),
        size_t { 1 }, std::multiplies<> {});

    return index_impl(0, std::begin(strides) + advenceBy, args...) * tailFactor;
}

Here is live demo (passing tests).

user_13874380

C++14 distinctively lacks fold expressions, which usually makes parameter packs much harder to work with. Thankfully, we can use array initializations to fake fold expressions, which is allowed in constexpr functions, so we can get away with no recursion and better code readability.

template<typename... Idxs>
constexpr int indexing_type()
{
    size_t integrals = 0;
    bool unused[] = {(integrals += std::is_integral<Idxs>::value, false)...};
    (void)unused;
    bool mys[] = {std::is_same<my, Idxs>::value...};
    bool last = mys[sizeof(mys) - 1];
    if(integrals == sizeof...(Idxs))
        return 1;
    if(integrals == sizeof...(Idxs) - 1 && last)
        return 2;
    return 0;
}

template<typename S, size_t... Is, typename... Idxs>
inline auto mul_reduce(const S& strides, size_t off, std::index_sequence<Is...>, Idxs... idxs)
{
    size_t sum = 0;
    bool unused[] = {(sum += strides[off + Is] * size_t(idxs), false)...};
    (void)unused;
    return sum;
}

template<typename S, typename... Idxs>
inline auto index(const S& strides, Idxs... idxs)
-> std::enable_if_t<indexing_type<Idxs...>() == 1, size_t>
{
    auto off = strides.size() - sizeof...(Idxs);
    return mul_reduce(strides, off, std::make_index_sequence<sizeof...(Idxs)>{}, idxs...);
}

template<typename S, typename... Idxs>
inline auto index(const S& strides, Idxs... idxs)
-> std::enable_if_t<indexing_type<Idxs...>() == 2, size_t>
{
    return mul_reduce(strides, 0, std::make_index_sequence<sizeof...(Idxs)>{}, idxs...);
}

indexing_type tells you which function to dispatch to, and also disables index from overload resolution in case the parameter types are wrong.

In mul_reduce, we abuse the fact that size_t(missing) == 0 to avoid needing to remove it from the end.

user_48324990
Related