3
\$\begingroup\$

In my code, I need to flatten a two-dimensional std::array into a one-dimensional one at compile time. While writing the code I realized, that I am unsure about several aspects of my implementation (as far as readability is concerned). Therefore I would really appreciate your input! I am especially unsure, if

  1. There is a more obvious / simpler version in which I can achieve my goal (I previously thought of expanding multiple parameter packs with one ... or the like)
  2. if using a nested lambda is a good idea (I do this in order to obtain access to the parameter pack created by the integer_sequence and not expose this API)
  3. If using the requires expression is really more readable than using a std::enable_if_t in this use case
  4. and, even if I kind of like my solution to this problem, whether there is a cleaner way of
    1. having automatic template parameter deduction for the "exposed" API
    2. having access to sizes and type of the nested array
  5. If there are other things I can improve with my code
#include <array>
#include <iostream>

/// Helper struct, which is std::false_type if the type is not a nested array, and otherwise holds
/// inner and outer array sizes.
template<typename Arr> struct NestedArray : std::false_type{};
template <std::size_t sizeOuter, std::size_t sizeInner, typename T>
struct NestedArray<std::array<std::array<T, sizeInner>, sizeOuter>> : std::true_type{
  static constexpr auto outer = sizeOuter; 
  static constexpr auto inner = sizeInner;
  using type = T;
};

/// Return #nestedArray.flatten()[#index].
template <auto nestedArray, std::size_t index,
          typename = std::enable_if_t<NestedArray<std::decay_t<decltype(nestedArray)>>::value>>
consteval auto getValueByIndex() noexcept {
  using NestedArrayHelper = NestedArray<std::decay_t<decltype(nestedArray)>>;
  constexpr std::size_t innerIndex = index % NestedArrayHelper::inner;
  constexpr std::size_t outerIndex = index / NestedArrayHelper::inner;
  static_assert(NestedArrayHelper::inner > innerIndex &&
                    NestedArrayHelper::outer > outerIndex, "Index out of bounds.");
  return std::get<innerIndex>(std::get<outerIndex>(nestedArray));
}

/// Return 1-dimensional array #nestedArray.flatten() from 2-dimensional array #nestedArray.
/// @param nestedArray:   two-dimensional std::array (std::array<std::array<T, I>, O>)
/// @return               flat representation of #nestedArray (std::array<T, I * O>) with 
///                       nestedArray[o][i] = result[i + I * o]
template <auto nestedArray> 
requires requires() { requires NestedArray<std::decay_t<decltype(nestedArray)>>::value; }
consteval auto flattenNestedArray() noexcept {
  using NestedArrayHelper = NestedArray<std::decay_t<decltype(nestedArray)>>;
  using ContainedType = typename NestedArrayHelper::type;

  constexpr std::size_t flatSize = NestedArrayHelper::outer * NestedArrayHelper::inner;
  return []<std::size_t... ix>(std::index_sequence<ix...>) consteval noexcept {
    return std::array<ContainedType, flatSize> {getValueByIndex<nestedArray, ix>()...};
  }(std::make_index_sequence<flatSize>());
}


// Test, only for demonstrating the purpose of the code. 

/// 2d array 
constexpr std::array<std::array<int, 2>, 3> arrayOfPairs{{{1, 2}, {3, 4}, {15, 16}}};

/// Resulting 1d array
constexpr auto flatArray = flattenNestedArray<arrayOfPairs>();

// Test: Print out the resulting 1d array
int main () {
  for (std::size_t i = 0; i < 6; ++i) { std::cout << flatArray[i] << " "; } std::cout << std::endl;
}

I hope that this is appropriate for a Code Review, I linked the code in compilerExplorer. Note that it can only be compiled with gcc trunk, as clang trunk does not allow std::array as non-type template argument. Thanks a lot :)

\$\endgroup\$
  • \$\begingroup\$ I'm new to CodeReview, and would really like to know what the issues are with my question, so I would really appreciate if you could help me improve the question if you think that there are problems, or that the question does not meet the reqirements / isn't on-topic. \$\endgroup\$ – mutableVoid Apr 16 at 19:03
  • 2
    \$\begingroup\$ This has gotten a close vote for not working as intended. I can't see why anyone would vote for that. I can possibly see the final paragraph, where you've said which compiler your code works on, could be misinterpreted. But code working in only one interpreter or compiler is not off-topic - I found out the hard way by posting code that targets a single ancient JavaScript interpreter. \$\endgroup\$ – Peilonrayz Apr 16 at 23:40
  • 2
    \$\begingroup\$ For future readers: the reason the code doesn't compile in Clang is not that the code is wrong, it's because Clang hasn't implemented the C++20 feature \$\endgroup\$ – L. F. Apr 17 at 10:03
  • \$\begingroup\$ If you already work with compile time, then isn't it simpler to make a compile-time copy: just make array<..., x*y> from array<array<...,x>,y> and there is no need for extra class. \$\endgroup\$ – ALX23z Apr 17 at 10:40
2
\$\begingroup\$

The biggest readability concern, in my opinion, is squashing everything on one line. Compare:

int main () {
  for (std::size_t i = 0; i < 6; ++i) { std::cout << flatArray[i] << " "; } std::cout << std::endl;
}

to

int main()
{
    for (std::size_t i = 0; i < 6; ++i) {
        std::cout << flatArray[i] << " ";
    }
    std::cout << std::endl;
}

which can then be improved to:

int main()
{
    for (auto v : flatArray) {
        std::cout << v << ' ';
    }
    std::cout << '\n';
}

We can use some shorthand to make nested arrays easier to understand:

namespace detail {
    template <typename T, std::size_t... Dims>
    struct multi_array;

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

    template <typename T, std::size_t Dim, std::size_t... Dims>
    struct multi_array<T, Dim, Dims...> {
        using type = std::array<
            typename multi_array<T, Dims...>::type, Dim
        >;
    };
}

template <typename T, std::size_t... Dims>
using multi_array = typename detail::multi_array<T, Dims...>::type;

Now, it is more idiomatic to pass the array as an argument instead of a template argument, so that invocation uses more natural syntax and works for both runtime values and compile time values:

template <std::copy_­constructible T, std::size_t N, std::size_t M>
constexpr auto flatten(const multi_array<T, N, M>& array)
    noexcept(std::is_nothrow_copy_constructible_v<T>)
{
    return /* magic */;
}

We can also easily generalize into multiple dimensions from here:

#include <array>
#include <concepts>
#include <type_traits>

namespace detail {
    template <typename T, std::size_t... Dims>
    struct multi_array;

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

    template <typename T, std::size_t Dim, std::size_t... Dims>
    struct multi_array<T, Dim, Dims...> {
        using type = std::array<
            typename multi_array<T, Dims...>::type, Dim
        >;
    };

    template <typename T>
    struct multi_array_traits {
        static constexpr std::size_t size{1};
        using type = T;
    };

    template <typename T, std::size_t N>
    struct multi_array_traits<std::array<T, N>> {
        static constexpr std::size_t size{N * multi_array_traits<T>::size};
        using type = typename multi_array_traits<T>::type;
    };

    template <std::size_t I>
    constexpr const auto& get(const auto& scalar) noexcept
    {
        static_assert(I == 0);
        return scalar;
    }

    template <std::size_t I, typename T, std::size_t N>
    constexpr const auto& get(const std::array<T, N>& array) noexcept
    {
        constexpr auto InnerSize = multi_array_traits<T>::size;

        constexpr auto Outer = I / InnerSize;
        constexpr auto Inner = I % InnerSize;

        return detail::get<Inner>(array[Outer]);
    }

    template <typename T, std::size_t... Indices>
    constexpr auto flatten(const T& array, std::index_sequence<Indices...>)
    {
        constexpr auto Size = multi_array_traits<T>::size;
        using Elem = typename multi_array_traits<T>::type;

        return std::array<Elem, Size>{Elem(detail::get<Indices>(array))...};
    }
}

template <typename T, std::size_t... Dims>
using multi_array = typename detail::multi_array<T, Dims...>::type;

template <std::copy_constructible T>
constexpr auto flatten(const T& array)
{
    constexpr auto Size = detail::multi_array_traits<T>::size;
    return detail::flatten(array, std::make_index_sequence<Size>{});
}

(live demo)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.