Skip to main content
Code Review

Return to Answer

added 1795 characters in body
Source Link
G. Sliepen
G. Sliepen
  • 69.5k
  • 3
  • 75
  • 180

Handling non-default-constructible containers

You are currently assuming that once you have determined the type of a container using recursive_invoke_result_t<>, that you can default-construct a new container. However, that might not be the case; for example, if an allocator is used that doesn't have a default constructor.

Most STL containers have a get_allocator() member function that will return the allocater object that was used to construct it. You can pass that to the container you want to construct. Of course, that means an increase in complexity of your code. Ideally, you would create an out-of-class function that can create an empty copy of any container, so that you can write:

template<std::size_t unwrap_level = 1, class T, class F>
requires (unwrap_level <= recursive_depth<T>())
constexpr auto recursive_transform(const T& input, const F& f)
{
    if constexpr (unwrap_level > 0)
    {
        auto output = clone_empty_container(input);
        std::ranges::transform(
            input,
            std::inserter(output, std::ranges::end(output)),
            [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
        );
        return output;
    }
    else
    {
        return std::invoke(f, input);
    }
}

You could even consider having it handle comparator and hash objects passed to containers like std::map and std::unordered_map, call reserve() based on the size of the input, handle container adapters like std::stack() that take a container as a parameter in the constructor, and maybe even upcoming types like std::flat_set.

Handling non-default-constructible containers

You are currently assuming that once you have determined the type of a container using recursive_invoke_result_t<>, that you can default-construct a new container. However, that might not be the case; for example, if an allocator is used that doesn't have a default constructor.

Most STL containers have a get_allocator() member function that will return the allocater object that was used to construct it. You can pass that to the container you want to construct. Of course, that means an increase in complexity of your code. Ideally, you would create an out-of-class function that can create an empty copy of any container, so that you can write:

template<std::size_t unwrap_level = 1, class T, class F>
requires (unwrap_level <= recursive_depth<T>())
constexpr auto recursive_transform(const T& input, const F& f)
{
    if constexpr (unwrap_level > 0)
    {
        auto output = clone_empty_container(input);
        std::ranges::transform(
            input,
            std::inserter(output, std::ranges::end(output)),
            [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
        );
        return output;
    }
    else
    {
        return std::invoke(f, input);
    }
}

You could even consider having it handle comparator and hash objects passed to containers like std::map and std::unordered_map, call reserve() based on the size of the input, handle container adapters like std::stack() that take a container as a parameter in the constructor, and maybe even upcoming types like std::flat_set.

Source Link
G. Sliepen
G. Sliepen
  • 69.5k
  • 3
  • 75
  • 180

It's just getting better and better!

Use a constraint instead of static_assert()

You can trivially turn the static_assert() you have in recursive_transform() into a constraint:

template<std::size_t unwrap_level = 1, class T, class F>
requires (unwrap_level <= recursive_depth<T>())
constexpr auto recursive_transform(const T& input, const F& f)
{
    …
}

The problem with the static_assert() is that it only triggers when your function has already recursed as much as possible. The error message that the compilers generate will then be quite large. By using a requires clause, the mistake is caught immediately at the outer call to recursive_transform(), resulting in a much shorter error message. The only drawback is that you cannot include a custom error message in this case. Here is the number of lines of error messages for each method at a given recursion depth:

Method @ depth GCC 12 Clang 17
requires @ 1 22 19
requires @ 2 34 19
requires @ 3 30 19
static_assert @ 1 30 46
static_assert @ 2 114 68
static_assert @ 3 138 105

Use only one method to check if a type is a container

You currently have two ways to check if a type is a container: std::ranges::input_range and is_iterable. These are slightly different, and it's best to use only one of them, on the off-chance that there is a type which satisfies one but not the other, as I imagine this would cause some very hard to debug compiler error.

I think you can just write:

template<…>
requires std::ranges::input_range<Container<T, N>>
constexpr auto recursive_transform(const Container<T, N>& input, const F& f)
{
    …
}

Use std::ranges::transform() for std::arrays as well

For the overload that handles std::array, you can use std::ranges::transform() just like you did in the more generic overload.

Nested std::arrays are not handled

Your code does not handle std::arrays that contain other containers, including other std::arrays.

Ideally, there is only one overload of recursive_transform() that handles all container types. recursive_invoke_result_t<> should handle arrays. The only other issue is that there is no std::inserter<> that works on arrays. You can add some if constexpr code to handle that difference, or create a struct recursive_output_iterator<> to give you the right output iterator.

Call reserve() if possible

Some containers have a reserve() member function (like std::vector and std::deque), and it would help performance a lot if you called it.

What if the input is an rvalue?

Something we haven't looked at is if it makes sense to handle inputs that are rvalues. In case the function we are passing has a return type that is the same as its input, then you can just std::transform() the innermost containers in-place. If not, then there still is the possibility of moving the original values in the input into the function that is being applied. I don't think even std::ranges::transform() does that though.