Completely enumerate indices of D-dimensional arra

问题:

To test some multidimensional structures there is a need to generate compile time multidimensional indices to fully cover all the possible cases.

I search for compile-time inexpensive way to achieve above purpose.

What I do currently:

#include <type_traits>
#include <utility>

template< typename F, std::size_t ...indices >
struct enumerator;

template< typename F >
struct enumerator< F >
{

    constexpr
    enumerator(F && _f)
        : f(std::forward< F >(_f))
    { ; }

    template< std::size_t ...I >
    constexpr
    bool
    operator () () const
    {
        return f(std::index_sequence< I... >{});
    }

private :

    F f;

};

template< typename F, std::size_t first, std::size_t ...rest >
struct enumerator< F, first, rest... >
    : enumerator< F, rest... >
{

    constexpr
    enumerator(F && _f)
        : enumerator< F, rest... >(std::forward< F >(_f))
    { ; }

    template< std::size_t ...I >
    constexpr
    bool
    operator () () const
    {
        return enumerator::template operator () < I... >(std::make_index_sequence< first >{}); // ltr
    }

    template< std::size_t ...I, std::size_t ...J >
    constexpr
    bool
    operator () (std::index_sequence< J... >) const
    {
        return (enumerator< F, rest... >::template operator () < I..., J >() && ...); // rtl, `< J, I... >` - ltr
    }

};

template< std::size_t ...I, typename F >
constexpr
enumerator< F, I... >
make_enumerator(F && f)
{
    static_assert(0 < sizeof...(I));
    static_assert(((0 < I) && ...));
    return std::forward< F >(f);
}

// main.cpp

#include <iostream>

#include <cstdlib>
#include <cassert>

struct truth
{

    template< std::size_t ...I >
    constexpr
    bool
    operator () (std::index_sequence< I... >) const
    {
        return true;
    }

};

struct printer
{

    template< std::size_t ...I >
    bool
    operator () (std::index_sequence< I... >) const
    {
        for (std::size_t const & i : {I...}) {
            std::cout << i << ' ';
        }
        std::cout << std::endl;
        return true;
    }

};

int
main()
{  
    static_assert(make_enumerator< 10, 10, 10, 10 >(truth{})());
    assert((make_enumerator< 3, 3, 3 >(printer{})()));
    return EXIT_SUCCESS;
}

For 10⁴ generated cases it consume about ten seconds of a processor time. How to improve the solution, or are there a better ways to achive the goal?

回答1:

As for runtime, I would linear the indexes and do a to_multi_index, something like:

// Is0 * Is1 * ... * Isn
template <std::size_t ... Is>
struct accum_mul;

template <>
struct accum_mul<> : std::integral_constant<std::size_t, 1u>{};

template <std::size_t I, std::size_t ... Is>
struct accum_mul<I, Is...> :
    std::integral_constant<std::size_t, I * accum_mul<Is...>::value>{};

template <typename Seq, typename Res = std::tuple<>>
struct coeff;

template <typename Res>
struct coeff<std::index_sequence<>, Res> {
  using type = Res;
};

template <std::size_t I, std::size_t ... Is, typename ... TRes>
struct coeff<std::index_sequence<I, Is...>,
             std::tuple<TRes...>>
    : coeff<std::index_sequence<Is...>,
            std::tuple<TRes..., accum_mul<Is...>>> {};

template <std::size_t I, typename coeffs, typename dims, typename Seq>
struct to_multi_index;

template <std::size_t I, typename coeffs, typename dims, std::size_t... Is>
struct to_multi_index<I, coeffs, dims, std::index_sequence<Is...>>
{
    using type = std::index_sequence<(I / (std::tuple_element<Is, coeffs>::type::value)
    % (std::tuple_element<Is, dims>::type::value))...>;
};

template <typename Indexes, typename coeffs, typename dims, typename dim_indexes>
struct to_multi_indexes;

template <std::size_t... Is, typename coeffs, typename dims, typename dim_indexes>
struct to_multi_indexes<std::index_sequence<Is...>, coeffs, dims, dim_indexes>
{
    using type = std::tuple<typename to_multi_index<Is, coeffs, dims, dim_indexes>::type...>;
};

template <std::size_t...Is>
struct all_indexes
{
private:
    using as_seq = std::index_sequence<Is...>;
    using as_tuple = std::tuple<std::integral_constant<std::size_t, Is>...>;
    using dim_index = std::make_index_sequence<sizeof...(Is)>;
    using coeffs = typename coeff<as_seq>::type;
    using elem_count = accum_mul<Is...>;
    using index_seq = std::make_index_sequence<elem_count::value>;
public:
    using type = typename to_multi_indexes<index_seq, coeffs, as_tuple, dim_index>::type;
};

Live demo