4
\$\begingroup\$

This is a follow-up question for A recursive_transform Template Function Implementation with std::invocable concept in C++, A recursive_transform Template Function with Execution Policy, A recursive_transform Template Function Implementation with std::invocable Concept and Execution Policy in C++, std::array and std::vector Type Arbitrary Nested Iterable Generator Functions Implementation in C++ and A Various Container Type Arbitrary Nested Iterable Generator Function Implementation in C++. Thanks to G. Sliepen's answer. In the parallel execution part, std::for_each() structure is used instead of std::back_inserter() usage. With Boost.Test tool, the transform operation for each element in nested std::deque and nested std::vector (nested level less than 16) is tested as below.

The experimental implementation

  1. Nested ranges comparison

In order to compare two std::ranges::input_range things is equal or not, the operator == overloading implementation is as below.

//  Equal operator for std::ranges::input_range
template<std::ranges::input_range Range1, std::ranges::input_range Range2>
bool operator==(const Range1& input1, const Range2& input2)
{
    if (input1.size() != input2.size())
    {
        return false;
    }
    for (size_t i = 0; i < input1.size(); i++)
    {
        if (input1.at(i) != input2.at(i))
        {
            return false;
        }
    }
    return true;
}

//  Not equal operator for std::ranges::input_range
template<std::ranges::input_range Range1, std::ranges::input_range Range2>
bool operator!=(const Range1& input1, const Range2& input2)
{
    if (input1.size() != input2.size())
    {
        return true;
    }
    for (size_t i = 0; i < input1.size(); i++)
    {
        if (input1.at(i) != input2.at(i))
        {
            return true;
        }
    }
    return false;
}

Note: I've check this and the usage (test_result == expected_result) as below should be compiled without any error. However, the error like binary '==': no operator found which takes a left-hand operand of type 'std::vector<std::vector<char,std::allocator<char>>,std::allocator<std::vector<char,std::allocator<char>>>>' (or there is no acceptable conversion) occurred so that I write my own equal operator for std::ranges::input_range. Maybe this is caused by the design of test case template with automated registration, but I am not quite sure.

  1. Nested std::deque test cases
BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_0dimension, TestType, test_types)
{
    constexpr size_t dim_num = 0;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_1dimension, TestType, test_types)
{
    constexpr size_t dim_num = 1;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_2dimension, TestType, test_types)
{
    constexpr size_t dim_num = 2;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_3dimension, TestType, test_types)
{
    constexpr size_t dim_num = 3;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_4dimension, TestType, test_types)
{
    constexpr size_t dim_num = 4;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_5dimension, TestType, test_types)
{
    constexpr size_t dim_num = 5;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_6dimension, TestType, test_types)
{
    constexpr size_t dim_num = 6;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_7dimension, TestType, test_types)
{
    constexpr size_t dim_num = 7;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_8dimension, TestType, test_types)
{
    constexpr size_t dim_num = 8;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_9dimension, TestType, test_types)
{
    constexpr size_t dim_num = 9;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_10dimension, TestType, test_types)
{
    constexpr size_t dim_num = 10;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_11dimension, TestType, test_types)
{
    constexpr size_t dim_num = 11;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_12dimension, TestType, test_types)
{
    constexpr size_t dim_num = 12;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_13dimension, TestType, test_types)
{
    constexpr size_t dim_num = 13;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_14dimension, TestType, test_types)
{
    constexpr size_t dim_num = 14;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(deque_lambda_with_auto_15dimension, TestType, test_types)
{
    constexpr size_t dim_num = 15;
    auto test_object = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_container_generator<dim_num, std::deque, TestType>(static_cast<TestType>(2) * 2, 3);

    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}
  1. Nested std::vector test cases
BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_0dimension, TestType, test_types)
{
    constexpr size_t dim_num = 0;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_1dimension, TestType, test_types)
{
    constexpr size_t dim_num = 1;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_2dimension, TestType, test_types)
{
    constexpr size_t dim_num = 2;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_3dimension, TestType, test_types)
{
    constexpr size_t dim_num = 3;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_4dimension, TestType, test_types)
{
    constexpr size_t dim_num = 4;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_5dimension, TestType, test_types)
{
    constexpr size_t dim_num = 5;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_6dimension, TestType, test_types)
{
    constexpr size_t dim_num = 6;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_7dimension, TestType, test_types)
{
    constexpr size_t dim_num = 7;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_8dimension, TestType, test_types)
{
    constexpr size_t dim_num = 8;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_9dimension, TestType, test_types)
{
    constexpr size_t dim_num = 9;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_10dimension, TestType, test_types)
{
    constexpr size_t dim_num = 10;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_11dimension, TestType, test_types)
{
    constexpr size_t dim_num = 11;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_12dimension, TestType, test_types)
{
    constexpr size_t dim_num = 12;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_13dimension, TestType, test_types)
{
    constexpr size_t dim_num = 13;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_14dimension, TestType, test_types)
{
    constexpr size_t dim_num = 14;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_15dimension, TestType, test_types)
{
    constexpr size_t dim_num = 15;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

Full Testing Code

The full testing code:

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <complex>
#include <concepts>
#include <deque>
#include <execution>
#include <exception>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <mutex>
#include <numeric>
#include <optional>
#include <stdexcept>
#include <string>
#include <thread>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
#include <boost/utility.hpp>
//#define USE_BOOST_MULTIDIMENSIONAL_ARRAY
#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
#include <boost/multi_array.hpp>
#include <boost/multi_array/algorithm.hpp>
#include <boost/multi_array/base.hpp>
#include <boost/multi_array/collection_concept.hpp>
#endif

#define BOOST_TEST_MODULE tests_for_recursive_transform
#include <boost/test/included/unit_test.hpp>
#include <boost/test/test_tools.hpp>
#include <boost/mpl/list.hpp>

template<typename T>
concept is_inserterable = requires(T x)
{
    std::inserter(x, std::ranges::end(x));
};

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<typename T>
concept is_multi_array = requires(T x)
{
    x.num_dimensions();
    x.shape();
    boost::multi_array(x);
};
#endif

template<std::ranges::input_range Range>
Range recursive_print(const Range& input, const int level = 0)
{
    Range output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [level](auto& x)
        {
            std::cout << std::string(level, ' ') << x << std::endl;
            return x;
        }
    );
    return output;
}

template<std::ranges::input_range Range>
requires std::ranges::input_range<std::ranges::range_value_t<Range>>
Range recursive_print(const Range& input, const int level = 0)
{
    Range output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::transform(input.cbegin(), input.cend(), output.begin(),
        [level](auto& element)
        {
            return recursive_print(element, level + 1);
        }
    );
    return output;
}

//  recursive_transform implementation
template<class T, class F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    return f(input);
}

//  specific case for std::array
template<class T, std::size_t S, class F>
constexpr auto recursive_transform(const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));

    std::array<TransformedValueType, S> output;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [&f](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );
    return output;
}

template<template<class...> class Container, class Function, class... Ts>
requires (is_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));
    Container<TransformedValueType> output;

    std::transform(input.cbegin(), input.cend(), std::inserter(output, std::ranges::end(output)),
        [&](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );

    return output;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<is_multi_array T, class F>
requires(!std::invocable<F, T>)
constexpr auto recursive_transform(const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i{}; i != input.shape()[0]; ++i)
    {
        output[i] = recursive_transform(input[i], f);
    }
    return output;
}
#endif

//  recursive_transform implementation (with execution policy)
template<class ExPo, class T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
{
    return f(input);
}

//  specific case for std::array
template<class ExPo, class T, std::size_t S, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_transform(ExPo execution_policy, const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(execution_policy, *input.cbegin(), f));

    std::array<TransformedValueType, S> output;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [execution_policy, &f](auto&& element)
        {
            return recursive_transform(execution_policy, element, f);
        }
    );
    return output;
}

template<class ExPo, template<class...> class Container, class Function, class... Ts>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (is_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(ExPo execution_policy, const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(execution_policy, *input.cbegin(), f));
    Container<TransformedValueType> output(input.size());
    std::mutex mutex;

    std::for_each(execution_policy, input.cbegin(), input.cend(),
        [&](auto&& element)
        {
            auto result = recursive_transform(execution_policy, element, f);
            std::lock_guard lock(mutex);
            output.emplace_back(std::move(result));
        }
    );

    return output;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<class ExPo, is_multi_array T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (!std::invocable<F, T>)
constexpr auto recursive_transform(const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i{}; i != input.shape()[0]; ++i)
    {
        output[i] = recursive_transform(execution_policy, input[i], f);
    }
    return output;
}
#endif

template<std::size_t dim, class T>
constexpr auto n_dim_vector_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_vector_generator<dim - 1>(input, times);
        std::vector<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, std::size_t times, class T>
constexpr auto n_dim_array_generator(T input)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_array_generator<dim - 1, times>(input);
        std::array<decltype(element), times> output;
        std::fill(std::begin(output), std::end(output), element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_deque_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_deque_generator<dim - 1>(input, times);
        std::deque<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_list_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_list_generator<dim - 1>(input, times);
        std::list<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, template<class...> class Container = std::vector, class T>
constexpr auto n_dim_container_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        return Container(times, n_dim_container_generator<dim - 1, Container, T>(input, times));
    }
}

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

template <std::ranges::range T>
struct recursive_iter_value_t_detail<T>
    : recursive_iter_value_t_detail<std::iter_value_t<T>>
{ };

template<typename T>
using recursive_iter_value_t = typename recursive_iter_value_t_detail<T>::type;

//  Equal operator for std::ranges::input_range
template<std::ranges::input_range Range1, std::ranges::input_range Range2>
bool operator==(const Range1& input1, const Range2& input2)
{
    if (input1.size() != input2.size())
    {
        return false;
    }
    for (size_t i = 0; i < input1.size(); i++)
    {
        if (input1.at(i) != input2.at(i))
        {
            return false;
        }
    }
    return true;
}

//  Not equal operator for std::ranges::input_range
template<std::ranges::input_range Range1, std::ranges::input_range Range2>
bool operator!=(const Range1& input1, const Range2& input2)
{
    if (input1.size() != input2.size())
    {
        return true;
    }
    for (size_t i = 0; i < input1.size(); i++)
    {
        if (input1.at(i) != input2.at(i))
        {
            return true;
        }
    }
    return false;
}

typedef boost::mpl::list<char, int, short, long, long long int, unsigned char, unsigned int, unsigned short int, unsigned long int, float, double, long double> test_types;

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_0dimension, TestType, test_types)
{
    constexpr size_t dim_num = 0;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_1dimension, TestType, test_types)
{
    constexpr size_t dim_num = 1;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_2dimension, TestType, test_types)
{
    constexpr size_t dim_num = 2;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_3dimension, TestType, test_types)
{
    constexpr size_t dim_num = 3;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_4dimension, TestType, test_types)
{
    constexpr size_t dim_num = 4;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_5dimension, TestType, test_types)
{
    constexpr size_t dim_num = 5;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_6dimension, TestType, test_types)
{
    constexpr size_t dim_num = 6;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_7dimension, TestType, test_types)
{
    constexpr size_t dim_num = 7;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_8dimension, TestType, test_types)
{
    constexpr size_t dim_num = 8;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_9dimension, TestType, test_types)
{
    constexpr size_t dim_num = 9;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_10dimension, TestType, test_types)
{
    constexpr size_t dim_num = 10;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_11dimension, TestType, test_types)
{
    constexpr size_t dim_num = 11;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_12dimension, TestType, test_types)
{
    constexpr size_t dim_num = 12;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_13dimension, TestType, test_types)
{
    constexpr size_t dim_num = 13;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_14dimension, TestType, test_types)
{
    constexpr size_t dim_num = 14;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_15dimension, TestType, test_types)
{
    constexpr size_t dim_num = 15;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

If the enough memory and compile time / run time resource is available, the test output is like:

Running 192 test cases...

*** No errors detected

A Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

You are correct in your intuition that this isn’t really the best way to do this with Boost.Test. In fact, Boost.Test has about a half-dozen better ways to handle this, but I’ll focus on the one that I think will be of the most use for you.

Normally I try to review the code as written, but in this case, it’s actually much easier to start from scratch and build up toward what you have, showing you alternatives along the way.

The set up

I’ll pretend you have a single header file with your algorithm, recursive_transform.hpp, and absolutely nothing else:

// recursive_transform.hpp

#ifndef RECURSIVE_TRANSFORM_INC
#define RECURSIVE_TRANSFORM_INC

#include <algorithm>
#include <array>
#include <concepts>
#include <execution>
#include <iterator>
#include <mutex>
#include <ranges>
#include <utility>

//#define USE_BOOST_MULTIDIMENSIONAL_ARRAY

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
#   include <boost/multi_array.hpp>
#endif

template<typename T>
concept is_inserterable = requires(T x)
{
    std::inserter(x, std::ranges::end(x));
};

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<typename T>
concept is_multi_array = requires(T x)
{
    x.num_dimensions();
    x.shape();
    boost::multi_array(x);
};
#endif

//  recursive_transform implementation
template<class T, class F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    return f(input);
}

//  specific case for std::array
template<class T, std::size_t S, class F>
constexpr auto recursive_transform(const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));

    std::array<TransformedValueType, S> output;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [&f](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );
    return output;
}

template<template<class...> class Container, class Function, class... Ts>
requires (is_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));
    Container<TransformedValueType> output;

    std::transform(input.cbegin(), input.cend(), std::inserter(output, std::ranges::end(output)),
        [&](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );

    return output;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<is_multi_array T, class F>
requires(!std::invocable<F, T>)
constexpr auto recursive_transform(const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)
    {
        output[i] = recursive_transform(input[i], f);
    }
    return output;
}
#endif

//  recursive_transform implementation (with execution policy)
template<class ExPo, class T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
{
    return f(input);
}

//  specific case for std::array
template<class ExPo, class T, std::size_t S, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_transform(ExPo execution_policy, const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(execution_policy, *input.cbegin(), f));

    std::array<TransformedValueType, S> output;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [execution_policy, &f](auto&& element)
        {
            return recursive_transform(execution_policy, element, f);
        }
    );
    return output;
}

template<class ExPo, template<class...> class Container, class Function, class... Ts>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (is_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(ExPo execution_policy, const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(execution_policy, *input.cbegin(), f));
    Container<TransformedValueType> output(input.size());
    std::mutex mutex;

    std::for_each(execution_policy, input.cbegin(), input.cend(),
        [&](auto&& element)
        {
            auto result = recursive_transform(execution_policy, element, f);
            std::lock_guard lock(mutex);
            output.emplace_back(std::move(result));
        }
    );

    return output;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<class ExPo, is_multi_array T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (!std::invocable<F, T>)
constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)
    {
        output[i] = recursive_transform(execution_policy, input[i], f);
    }
    return output;
}
#endif

#endif // include guard

The first test

Now the first thing you should do with a header like this is create a paired source file. Yes, even if that source file is going to be completely empty (which is actually quite common with template code). The reason why is to test whether this header is actually self-contained. All you need is this:

// recursive_transform.cpp

#include <recursive_transform.hpp>

That’s it. It should be able to compile (but not link!). Using g++ as an example:

$ g++ --std=c++20 --pedantic -Wall -Wextra -c recursive_transform.cpp
$ 

Note that I’m enabling a bunch of warnings. You really want to do that when testing.

So it compiles. If it didn’t, then there are either errors in the header, or you have forgotten to include a necessary header. (In my case, in my first attempt, I got an error about std::is_execution_policy_v, because I’d forgotten to include <execution>.)

Though this isn’t using a test framework, it is a test. It’s a very basic pass/fail compile test to check whether the header is valid and complete on its own. When you actually compile your test executable, it’s usually free and harmless to do this at the same time and link it in, so you might as well.

Starting with Boost.Test

Okay, the biggest problem with your existing test code, in my opinion, is that is ABSURDLY slow. Like… criminally slow. I was awestruck that both the compilation and running brought my 8-core beast to its knees.

That’s simply not acceptable. Tests should be fairly quick… no more than a couple seconds, ideally. Why? Two reasons:

  1. Because you should be running them often. In fact, my own development cycle is basically:
    1. Look over code to see what changes are needed.
    2. Make the changes.
    3. Compile/run the tests.
    4. If the previous step takes more than 5 or so seconds, go back to looking over the code in anticipation of the next iteration.
    5. Check the test results. In other words, I’m running the tests dozens, if not hundreds of times during a decent coding session. If they took minutes to run each time… that would not only slow down my progress to a crawl, it would break my concentration every time I had to wait.
  2. Because you will probably want to use a continuous integration facility—like, say, Travis CI—and those services run on tiny servers and will often just timeout and die when a compile/test job takes too long.

Especially for something like a generic algorithm like this (which, I mean, recursive_transform() should be fast, shouldn’t it? so why would the tests be slow?), there’s no real justification for a test suite that takes several minutes to run.

One thing you can do to really speed up Boost.Test is to use the shared libraries, rather than the header-only variant. Boost.Test itself recommends this. If you doubt whether this is really that important, try compiling and running this:

#define BOOST_TEST_MODULE tests_for_recursive_transform
#include <boost/test/included/unit_test.hpp>

BOOST_AUTO_TEST_CASE(test)
{
    BOOST_TEST(1 == 1);
}

// g++ --std=c++20 --pedantic -Wall -Wextra -c test.cpp
// g++ --std=c++20 --pedantic -Wall -Wextra test.o

… versus this:

#define BOOST_TEST_MODULE tests_for_recursive_transform
#define BOOST_TEST_DYN_LINK
#include <boost/test/unit_test.hpp>

BOOST_AUTO_TEST_CASE(test)
{
    BOOST_TEST(1 == 1);
}

// g++ --std=c++20 --pedantic -Wall -Wextra -c test.cpp
// g++ --std=c++20 --pedantic -Wall -Wextra test.o -lboost_unit_test_framework

On my machine, the latter is over 5× faster, and the test executable is over 30× smaller. And that speed difference gets really important when you have more tests, and more complicated test structures.

(Actually, when I code, I quite often have a process where a single command triggers a make of the entire project with all unit tests THREE TIMES; once with GCC, once with Clang, and once with Clang using libc++ rather than libstdc++. This all happens lightning fast, generally (and in parallel), so my process is to edit some code, make and run the tests, grab a sip of my drink and a nibble of my snack, and by the time I look at the screen again, the tests are already complete… and, hopefully, have all passed… and I’m ready for the next iteration. This turnaround needs to be fast to work, and that means the tests have to build and run in mere seconds.)

You can get the best of both worlds by doing this:

// recursive_transform.test.cpp

#define BOOST_TEST_MODULE tests_for_recursive_transform
#ifdef BOOST_TEST_DYN_LINK
#   include <boost/test/unit_test.hpp>
#else
#   include <boost/test/included/unit_test.hpp>
#endif // BOOST_TEST_DYN_LINK

BOOST_AUTO_TEST_CASE(test)
{
    BOOST_TEST(1 == 1);
}

If you want to use the header-only variant, you do:

$ g++ --std=c++20 --pedantic -Wall -Wextra -c recursive_transform.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra -c recursive_transform.test.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra recursive_transform.test.o recursive_transform.o
$ ./a.out
Running 1 test case...

*** No errors detected
$ 

… but normally, you’ll want to do:

$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.test.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra recursive_transform.o recursive_transform.test.o -lboost_unit_test_framework
$ ./a.out
Running 1 test case...

*** No errors detected
$ 

The first tests

Now, you use test case templates, that get instantiated with a dozen types:

  • char
  • int
  • short
  • long
  • long long int
  • unsigned char
  • unsigned int
  • unsigned short int
  • unsigned long int
  • float
  • double
  • long double

… so each test case gets instantiated a dozen times, even though each instantiation is basically a completely identical test. This is really just getting carried away. You can’t possibly test EVERY type your algorithms are going to get instantiated with; even TRYING to do that is just quixotic. What you want to do is consider the MINIMAL set of types you really need to test the algorithm with, based on which types are likely to trigger different behaviour. Put another way, consider the following two usages of the algorithm:

// with int:
auto v1 = vector<vector<int>>{
    { 1, 2, 3 },
    { 4, 5 },
};

auto r1 = recursive_transform(execution::par, v1, [](int v) { return v * 2; });

// with double:
auto v2 = vector<vector<double>>{
    { 1, 2, 3 },
    { 4, 5 },
};

auto r2 = recursive_transform(execution::par, v2, [](double v) { return v * 2; });

… is there ANY plausible reason to suspect that the function call in the two cases will behave differently (other than one returning a nested int vector while the other returns a nested double vector… and if you’re concerned about testing the return type, you should do just that; it can be done at compile time with no need to actually run the function)? I can’t see any. If there ever comes a time where you suspect that there is a difference, well, then you can add a test case to consider that. But with no reason to suspect that there will be any practical difference between int and double (or long or short or unsigned or…), don’t waste everyone’s time with pointless tests. They just become a maintenance burden.

So let’s just throw all that template junk out and write some straightforward test cases.

Let’s start with the simplest case: not only non-recursive, but not even the range version at all:

// recursive_transform.test.cpp

#define BOOST_TEST_MODULE tests_for_recursive_transform
#ifdef BOOST_TEST_DYN_LINK
#   include <boost/test/unit_test.hpp>
#else
#   include <boost/test/included/unit_test.hpp>
#endif // BOOST_TEST_DYN_LINK

#include <recursive_transform.hpp>

BOOST_AUTO_TEST_CASE(simple_int)
{
    auto const input = 42;

    auto const result = recursive_transform(std::execution::par, input, [](auto&& v) { return v + 27; });

    BOOST_TEST(result == 69);
}

Compile and run, and…:

$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.test.cpp
In file included from recursive_transform.test.cpp:8:
./recursive_transform.hpp: In instantiation of ‘constexpr auto recursive_transform(ExPo, const T&, const F&) [with ExPo = __pstl::execution::v1::parallel_policy; T = int; F = simple_int::test_method()::<lambda(auto:24&&)>]’:
recursive_transform.test.cpp:18:104:   required from here
./recursive_transform.hpp:92:41: warning: unused parameter ‘execution_policy’ [-Wunused-parameter]
   92 | constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
      |                                    ~~~~~^~~~~~~~~~~~~~~~
$ g++ --std=c++20 --pedantic -Wall -Wextra recursive_transform.o recursive_transform.test.o -lboost_unit_test_framework
$ ./a.out
Running 1 test case...

*** No errors detected

… and you can see now why turning all the warnings on is important. The test compiled and passed, but there’s a warning because the execution policy isn’t used in the non-range variant. An easy fix.

Discovering, diagnosing, and dealing with a critical defect

Okay, now let’s add a test case for a non-recursive range:

BOOST_AUTO_TEST_CASE(empty_1d_int_vector)
{
    auto const input = std::vector<int>{};

    auto const result = recursive_transform(std::execution::par, input, [](auto&&) { return -1; });

    BOOST_TEST(result.empty());
}

Compile and and…:

$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.test.cpp
In file included from /opt/boost_1_75_0/include/boost/test/test_tools.hpp:52,
                 from /opt/boost_1_75_0/include/boost/test/unit_test.hpp:18,
                 from recursive_transform.test.cpp:3:
recursive_transform.test.cpp: In member function ‘void empty_1d_int_vector::test_method()’:
recursive_transform.test.cpp:28:23: error: request for member ‘empty’ in ‘result’, which is of non-class type ‘const int’
   28 |     BOOST_TEST(result.empty());
      |                       ^~~~~
/opt/boost_1_75_0/include/boost/test/tools/interface.hpp:41:47: note: in definition of macro ‘BOOST_TEST_BUILD_ASSERTION’
   41 |     (::boost::test_tools::assertion::seed()->*P)    \
      |                                               ^
/opt/boost_1_75_0/include/boost/test/tools/interface.hpp:134:5: note: in expansion of macro ‘BOOST_TEST_TOOL_ET_IMPL’
  134 |     BOOST_TEST_TOOL_ET_IMPL( P, level )                                     \
      |     ^~~~~~~~~~~~~~~~~~~~~~~
/opt/boost_1_75_0/include/boost/test/detail/pp_variadic.hpp:27:51: note: in expansion of macro ‘BOOST_TEST_TOOL_UNIV’
   27 | #  define BOOST_TEST_INVOKE_VARIADIC( tool, ... ) tool (__VA_ARGS__)
      |                                                   ^~~~
/opt/boost_1_75_0/include/boost/test/detail/pp_variadic.hpp:35:5: note: in expansion of macro ‘BOOST_TEST_INVOKE_VARIADIC’
   35 |     BOOST_TEST_INVOKE_VARIADIC(                                     \
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~
/opt/boost_1_75_0/include/boost/test/tools/interface.hpp:155:45: note: in expansion of macro ‘BOOST_TEST_INVOKE_IF_N_ARGS’
  155 | #define BOOST_TEST( ... )                   BOOST_TEST_INVOKE_IF_N_ARGS(    \
      |                                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~
recursive_transform.test.cpp:28:5: note: in expansion of macro ‘BOOST_TEST’
   28 |     BOOST_TEST(result.empty());
      |     ^~~~~~~~~~
$ 

What? The return type of recursive_transform(std::execution::par, std::vector<int>{}, [](auto&&) { return -1; }) is int? But… how?

Well, this review is not about the algorithm itself (I think I mentioned in a previous review that trying to deduce the returned container type is a broken, hopeless endeavour), so I’ll just spill the beans. The issue here is the interaction between the lambda [](auto&&) { return -1; } and the requires clause. Specifically, the !std::invocable<Function, Container<Ts...>> check. That lambda IS invocable with a std::vector<int>… it’s invocable with literally ANYTHING. And no matter what you give it, it will return a… you guessed it… int. Specifically -1.

You’ll get a similar error if you actually tried to do anything useful in the lambda, like [](auto&& element) { return element * 2; } (that will give you “can’t multiply std::vector<int> by 2!”).

One way to “fix” this problem by rewriting the lambda to explicitly take an int: [](int) { return -1; }. But that’s only a bandage. The problem is still there.

Which leads to the million-dollar question: Why didn’t you detect this problem in your existing tests?

Let’s take a look at your existing tests. Let’s pick out the analogous test:

BOOST_AUTO_TEST_CASE_TEMPLATE(vector_lambda_with_auto_1dimension, TestType, test_types)
{
    constexpr size_t dim_num = 1;
    auto test_object = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2), 3);
    auto test_result = recursive_transform(std::execution::par, test_object, [](auto& element) { return element * 2; });

    auto expected_result = n_dim_vector_generator<dim_num, TestType>(static_cast<TestType>(2) * 2, 3);
    
    //  Content comparison
    if (test_result == expected_result)
    {
        BOOST_TEST(true);
    }
    else
    {
        BOOST_TEST(false);
    }
}

And now take a look at the two lambdas side-by-side:

[](auto&& element) { return element * 2; } // doesn't work
[](auto& element) { return element * 2; } // works

See the difference?

As for what’s going on here… that’s complicated. It stems from this constraint: !std::invocable<Function, Container<Ts...>>.

For simplicity, let’s ignore the negation, and just say std::invocable<Function, Container<Ts...>> must be false. But if Function takes auto&&, then std::invocable<Function, Container<Ts...>> will NEVER be false. The auto allows it to take any type, and the && allows it to take it in any configuration: lvalue, rvalue, const lvalue, etc.. So if you use a lambda with auto&&, the constraint will ALWAYS fail.

But it works with auto&! … sort of. It doesn’t actually work; it only appears to. Why? Because if the lambda takes an auto& it will work with any type (because of auto)… but not every configuration. auto& will bind to lvalues… but not to rvalues. Which means, that if F refers to a lambda that takes an auto&:

Check Result
invocable<F, T> false
invocable<F, T&> true
invocable<F, T const&> true
invocable<F, T&&> false

And now note that the first line in that table is the way the constraint is written in the requires clause: std::invocable<Function, Container<Ts...>>

Which means that:

  • If the lambda takes auto&&, then std::invocable<Function, Container<Ts...>> will NEVER be false.
  • If the lambda takes auto&, then std::invocable<Function, Container<Ts...>> will ALWAYS be false.

Which means that all the checking you think is happening… isn’t.

  • [](auto&&) { /* ... */ } doesn’t work because the invocable check ALWAYS passes, which when negated, always fails.
  • [](auto&) { /* ... */ } “works” because the invocable check ALWAYS fails, which when negated, always passes.

In other words, your deduction scheme just doesn’t work with generic lambdas. You need to always give the actual type.

That means all of your existing tests are broken. They are passing, but only by fluke because of the way you happened to write the lambdas. If you didn’t use auto&—if you used literally anything else, like auto const& or auto&& or even just auto—then they would break.

Oof, terrible news, right?

So this is what the test code we have so far should look like:

#define BOOST_TEST_MODULE tests_for_recursive_transform
#ifdef BOOST_TEST_DYN_LINK
#   include <boost/test/unit_test.hpp>
#else
#   include <boost/test/included/unit_test.hpp>
#endif // BOOST_TEST_DYN_LINK

#include <recursive_transform.hpp>

#include <vector>

BOOST_AUTO_TEST_CASE(simple_int)
{
    auto const input = 42;

    auto const result = recursive_transform(std::execution::par, input, [](int v) { return v + 27; });

    BOOST_TEST(result == 69);
}

BOOST_AUTO_TEST_CASE(empty_1d_int_vector)
{
    auto const input = std::vector<int>{};

    auto const result = recursive_transform(std::execution::par, input, [](int) { return -1; });

    BOOST_TEST(result.empty());
}

Testing types

Okay, but we skipped a very important issue. Your tests are broken (as were mine, before that last code block)… but they passed. What could we have done to detect this problem?

Well, one option would be to test that the return types are what you expected. Normally you don’t bother to test the return types of functions because, normally, they’re tautologically obvious, and there’s no point in testing things that are functionally impossible to be wrong. For example, the return type of std::copy(InputIterator, InputIterator, OutputIterator) -> OutputIterator is going to be OutputIterator. The function is literally declared that way; it can’t be wrong.

But recursive_transform() is doing some complicated gymnastics to determine the return type. “Complicated” = “potential to fail”, thus this is something you should test.

But how?

Let’s build it up step-by-step. First we fake a recursive_transform() call using declval(). We’ll just use an int as the type, and give it a function that will transform it into a double:

recursive_transform(
    std::execution::par,
    std::declval<int>(),
    std::declval<double (*)(int)>()
)

Then we get the return type of that call:

decltype(
    recursive_transform(
        std::execution::par,
        std::declval<int>(),
        std::declval<double (*)(int)>()
    )
)

… which should be double:

std::is_same_v<
    decltype(
        recursive_transform(
            std::execution::par,
            std::declval<int>(),
            std::declval<double (*)(int)>()
        )
    ),
    double
>

Now let’s pull out the concrete types, and use placeholders instead:

using Container = int;
using Function = double (*)(int);
using Result = double;

std::is_same_v<
    decltype(
        recursive_transform(
            std::execution::par,
            std::declval<Container>(),
            std::declval<Function>()
        )
    ),
    Result
>

Already we can use this to make a test:

BOOST_AUTO_TEST_CASE(return_type)
{
    using Container = int;
    using Function = double (*)(int);
    using Result = double;

    BOOST_TEST((
        std::is_same_v<
            decltype(
                recursive_transform(
                    std::execution::par,
                    std::declval<Container>(),
                    std::declval<Function>()
                )
            ),
            Result
        >
    ));
}

But let’s do better by taking advantage of templated test cases, and tuples:

using return_type_test_types = std::tuple<
    // Container, Func, Result
    std::tuple<int, double (*)(int), double>
>;

BOOST_AUTO_TEST_CASE_TEMPLATE(return_type, Types, return_type_test_types)
{
    using Container = std::tuple_element_t<0, Types>;
    using Function  = std::tuple_element_t<1, Types>;
    using Result    = std::tuple_element_t<2, Types>;

    BOOST_TEST((
        std::is_same_v<
            decltype(
                recursive_transform(
                    std::execution::par,
                    std::declval<Container>(),
                    std::declval<Function>()
                )
            ),
            Result
        >
    ));
}

Now it’s trivial to add more tests for different variations on the types:

using return_type_test_types = std::tuple<
    //         Container   Function                Result
    std::tuple<int,        double (*)(int),        double>, // Basic non-range variant
    std::tuple<int,        double (*)(int const&), double>, // Func works with const&
    std::tuple<int const,  double (*)(int const&), double>, // Can be called with a const value...
    std::tuple<int&,       double (*)(int const&), double>, // ... or lvalue ...
    std::tuple<int const&, double (*)(int const&), double>, // ... or const lvalue ...
    std::tuple<int&&,      double (*)(int const&), double>  // ... or rvalue
>;

You don’t need to use just ints and doubles. In fact you could replace any of those with basically any other type. It might even be smart to mix it up, and throw in some char, some custom types, or whatever.

And with pretty much no extra work, you can also test the range variants as well:

    // Non-recursive array.
    std::tuple<std::array<double, 5>, int (*)(double), std::array<int, 5>>,
    // Non-recursive vector.
    std::tuple<std::vector<char>, unsigned (*)(char), std::vector<unsigned>>,

And even the recursive range variants:

    // Recursive array.
    std::tuple<std::array<std::array<int, 3>, 4>, char (*)(int), std::array<std::array<char, 3>, 4>>,
    //std::tuple<std::array<std::vector<int>, 4>, char (*)(int), std::array<std::vector<char>, 4>>, //???
    std::tuple<std::vector<std::array<int, 3>>, char (*)(int), std::vector<std::array<char, 3>>>,
    // Recursive vector.
    std::tuple<std::vector<std::vector<int>>, char (*)(int), std::vector<std::vector<char>>>,
    std::tuple<std::vector<std::vector<std::vector<int>>>, char (*)(int), std::vector<std::vector<std::vector<char>>>>,

And so on….

(Note that the line marked ??? doesn’t compile. I can’t be bothered to figure out why, because I’m reviewing the test code, not the algorithm.)

So:

using return_type_test_types = std::tuple<
    //         Container   Function                Result
    // Non-range.
    std::tuple<int,        double (*)(int),        double>, // Basic non-range variant
    std::tuple<int,        double (*)(int const&), double>, // Func works with const&
    std::tuple<int const,  double (*)(int const&), double>, // Can be called with a const value...
    std::tuple<int&,       double (*)(int const&), double>, // ... or lvalue ...
    std::tuple<int const&, double (*)(int const&), double>, // ... or const lvalue ...
    std::tuple<int&&,      double (*)(int const&), double>, // ... or rvalue
    // Non-recursive array.
    std::tuple<std::array<double, 5>, int (*)(double), std::array<int, 5>>,
    // Non-recursive vector.
    std::tuple<std::vector<char>, unsigned (*)(char), std::vector<unsigned>>,
    // Recursive array.
    std::tuple<std::array<std::array<int, 3>, 4>, char (*)(int), std::array<std::array<char, 3>, 4>>,
    //std::tuple<std::array<std::vector<int>, 4>, char (*)(int), std::array<std::vector<char>, 4>>, //???
    std::tuple<std::vector<std::array<int, 3>>, char (*)(int), std::vector<std::array<char, 3>>>,
    // Recursive vector.
    std::tuple<std::vector<std::vector<int>>, char (*)(int), std::vector<std::vector<char>>>,
    std::tuple<std::vector<std::vector<std::vector<int>>>, char (*)(int), std::vector<std::vector<std::vector<char>>>>
>;

BOOST_AUTO_TEST_CASE_TEMPLATE(return_type, Types, return_type_test_types)
{
    using Container = std::tuple_element_t<0, Types>;
    using Function  = std::tuple_element_t<1, Types>;
    using Result    = std::tuple_element_t<2, Types>;

    BOOST_TEST((
        std::is_same_v<
            decltype(
                recursive_transform(
                    std::execution::par,
                    std::declval<Container>(),
                    std::declval<Function>()
                )
            ),
            Result
        >
    ));
}

You can also add tests with std::list, and maybe std::forward_list, and so on.

Another variant of this technique is to add not only the expected result type, but the actual result type, to the test type tuple, like so:

template <typename Container, typename Function, typename Expected>
using return_type_test_type = std::tuple<
    Container,
    Function,
    Expected,
    decltype(recursive_transform(std::execution::par, std::declval<Container>(), std::declval<Function>()))
>;

using return_type_test_types = std::tuple<
    //                    Container   Function                Result
    // Non-range.
    return_type_test_type<int,        double (*)(int),        double>,
    return_type_test_type<int,        double (*)(int const&), double>,
    // ... and so on...
>;

BOOST_AUTO_TEST_CASE_TEMPLATE(return_type, Types, return_type_test_types)
{
    //using Container = std::tuple_element_t<0, Types>;
    //using Function  = std::tuple_element_t<1, Types>;
    using Expected  = std::tuple_element_t<2, Types>;
    using Result    = std::tuple_element_t<3, Types>;

    BOOST_TEST((std::is_same_v<Expected, Result>));
}

The benefit of this is that you not only get the test failure message, you also get both the expected and actual result types named in the error message.

So generic lambdas don’t work with the current design, but assuming they did, how would you test them? Well, one way is to simply write a test case for them:

BOOST_AUTO_TEST_CASE(generic_lambdas)
{
    BOOST_TEST((std::is_same_v<
        decltype(recursive_transform(std::execution::par, int{}, [](auto&&) { return 0.0; })),
        double
    >));

    // ... and so on with different lamdba and container types
}

Another way is to note that:

[](auto&& x) { return x + 1; }

is simply:

struct unnameable
{
    template <typename T>
    auto operator()(T&& x) { return x + 1; }
};

So all you need to do is create some testing function objects:

struct generic_function_object_byval
{

    template <typename T>
    auto operator()(T) { return 0.0; }
}

struct generic_function_object_bylref
{

    template <typename T>
    auto operator()(T&) { return 0.0; }
}

struct generic_function_object_byclref
{

    template <typename T>
    auto operator()(T const&) { return 0.0; }
}

struct generic_function_object_byrref
{

    template <typename T>
    auto operator()(T&&) { return 0.0; }
}

Then you can simply add new tuples to the return_type_test_types:

using return_type_test_types = std::tuple<
    // ...
    return_type_test_type<int, generic_function_object_byval, double>,
    return_type_test_type<int, generic_function_object_bylref, double>,
    return_type_test_type<std::vector<int>, generic_function_object_byval, std::vector<double>>,
    // ... and so on...
>;

Comparing containers

After all that we finally get to the actual question, about comparing whether two ranges are equal. As I mentioned at the start, Boost.Test has easily a half-dozen or more ways to handle this nicely.

Perhaps the easiest is to use the per-element modifier with BOOST_TEST(). For example:

BOOST_AUTO_TEST_CASE(simple_1d_int_vector)
{
    auto const input = std::vector<int>{1, 2, 3, 4};
    auto const expected = std::vector<int>{5, 6, 7, 8};

    auto const result = recursive_transform(std::execution::par, input, [](int i) { return i + 4; });

    BOOST_TEST(result == expected, boost::test_tools::per_element());
}

Compile and run the tests…:

$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.test.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra recursive_transform.o recursive_transform.test.o -lboost_unit_test_framework
$ ./a.out
Running 15 test cases...
recursive_transform.test.cpp(80): error: in "simple_1d_int_vector": check result == expected has failed
Collections size mismatch: 8 != 4

*** 1 failure is detected in the test module "tests_for_recursive_transform"
$ 

… and, oh, look, we’ve already found a bug.

What’s causing this? Well, in the generic range-based recursive_transform() with an execution policy, you create the output container like this:

Container<TransformedValueType> output(input.size());

… which creates a vector<int> initialized with 4 ints. And then you add more ints to the end of that vector with emplace_back() in the loop:

output.emplace_back(std::move(result));

Thus you end up with a vector twice the size of the input vector, with the last half being the actual output you want.

Anywho, moving on. Another option to test containers is to use BOOST_CHECK_EQUAL_COLLECTIONS() (or BOOST_WARN_EQUAL_COLLECTIONS() or BOOST_REQUIRE_EQUAL_COLLECTIONS(), if necessary):

BOOST_AUTO_TEST_CASE(simple_1d_int_vector)
{
    auto const input = std::vector<int>{1, 2, 3, 4};
    auto const expected = std::vector<int>{5, 6, 7, 8};

    auto const result = recursive_transform(std::execution::par, input, [](int i) { return i + 4; });

    BOOST_CHECK_EQUAL_COLLECTIONS(result.begin(), result.end(), expected.begin(), expected.end());
}

This does basically the same thing as the per-element modifier, except it gives you more control (you can compare sub-ranges), and more information:

$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra -DBOOST_TEST_DYN_LINK -c recursive_transform.test.cpp
$ g++ --std=c++20 --pedantic -Wall -Wextra recursive_transform.o recursive_transform.test.o -lboost_unit_test_framework
$ ./a.out
Running 15 test cases...
recursive_transform.test.cpp(80): error: in "simple_1d_int_vector": check { result.begin(), result.end() } == { expected.begin(), expected.end() } has failed. 
Mismatch at position 0: 0 != 1
Mismatch at position 1: 0 != 2
Mismatch at position 2: 0 != 3
Mismatch at position 3: 0 != 4
Collections size mismatch: 8 != 4

*** 1 failure is detected in the test module "tests_for_recursive_transform"
$ 

Okay, but you have a unique situation in which you want to test containers recursively. Unsurprisingly, Boost.Test doesn’t come with that functionality built it. So you’re going to have to roll your own.

NORMALLY you should avoid writing any if tests or loops in a test. Anything other than a straight, one-way through path is just asking for trouble; the more complexity you add to your tests, the more likely they are to break, and you really don’t want to get into a situation where you have to test your test code.

BUT this is a special case, because you’re specifically testing recursive algorithms… so you kinda need to do some recursion to test the data structures. I say again, this is NOT something you should consider “normal” for writing tests… but you’re probably going to need to write some nested loops to do proper testing:

BOOST_AUTO_TEST_CASE(simple_3d_int_vector)
{
    auto const input = std::vector<std::vector<std::vector<int>>>{
        {
            {1, 1, 2},
            {3, 5, 8}
        },
        {
            {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
        },
        {
            {0, -1},
            {1, -1},
            {420}
        }
    };

    auto const expected = std::vector<std::vector<std::vector<int>>>{
        {
            {2, 2, 4},
            {6, 10, 16}
        },
        {
            {20, 18, 16, 14, 12, 10, 8, 6, 4, 2}
        },
        {
            {0, -2},
            {2, -2},
            {840}
        }
    };

    auto const result = recursive_transform(std::execution::par, input, [](int i) { return i + 4; });

    auto index_1 = std::size_t{0};
    auto index_2 = std::size_t{0};

    auto result_next_1 = result.begin();
    auto result_last_1 = result.end();
    auto expected_next_1 = expected.begin();
    auto expected_last_1 = expected.end();

    while (result_next_1 != result_last_1 and expected_next_1 != expected_last_1)
    {
        BOOST_TEST_INFO_SCOPE("element[" << index_1 << "]");

        auto result_next_2 = result_next_1->begin();
        auto result_last_2 = result_next_1->end();
        auto expected_next_2 = expected_next_1->begin();
        auto expected_last_2 = expected_next_1->end();

        BOOST_TEST((result_next_2 != result_last_2));
        BOOST_TEST((expected_next_2 != expected_last_2));

        while (result_next_2 != result_last_2 and expected_next_2 != expected_last_2)
        {
            BOOST_TEST_INFO_SCOPE("element[" << index_1 << "][" << index_2 << "]");

            BOOST_CHECK_EQUAL_COLLECTIONS(result_next_2->begin(), result_next_2->end(), expected_next_2->begin(), expected_next_2->end());

            ++result_next_2;
            ++expected_next_2;
            ++index_2;
        }

        if (result_next_2 != result_last_2 or expected_next_2 != expected_last_2)
        {
            auto size_1 = index_2;
            auto size_2 = index_2;
            if (result_next_2 != result_last_2)
                size_1 += std::distance(result_next_2, result_last_2);
            else
                size_2 += std::distance(expected_next_2, expected_last_2);

            BOOST_ERROR("size mismatch: " << size_1 << " != " << size_2);
        }

        ++result_next_1;
        ++expected_next_1;
        ++index_1;
    }

    if (result_next_1 != result_last_1 or expected_next_1 != expected_last_1)
    {
        auto size_1 = index_1;
        auto size_2 = index_1;
        if (result_next_1 != result_last_1)
            size_1 += std::distance(result_next_1, result_last_1);
        else
            size_2 += std::distance(expected_next_1, expected_last_1);

        BOOST_ERROR("size mismatch: " << size_1 << " != " << size_2);
    }
}

(This test will fail, of course, because recursive_transform() is currently broken.)

This is NOT what a normal test case should look like. But this kind of complexity is unavoidable for testing nested structures recursively. It MIGHT be worthwhile to create a RECURSIVE_CHECK_EQUAL_COLLECTIONS(first1, last1, first2, last2, n) test tool that works like BOOST_CHECK_EQUAL_COLLECTIONS(first1, last1, first2, last2), except recursively down to n levels, or maybe spelled recursive_check_equal_collections<size_t n>(first1, last1, first2, last2) where it’s just BOOST_CHECK_EQUAL_COLLECTIONS() when n is 1. (Do be careful about handling input iterators carefully when doing any of this. In the code above I could just get the sizes of the two containers with .size() or even distance(begin, end)… but neither of those strategies would work for an input range, so I did it a different way.)

You should generally not need to add too much extra junk to your testing code like that… but again, you’re dealing with recursive structures, so some amount of additional test code complexity is unavoidable. Just don’t go too far.

Now, what you’ve done—defining operator== for ANY input range—is not a great idea. One thing you should carefully avoid when testing is changing the interface of the stuff being tested. You don’t want different behaviour when testing than when not testing; that would be bad. Adding equality comparisons between types that don’t have it is changing their public interface. That’s a no-no.

If you want to compare objects that don’t have operator==, then you can use a custom predicate.

Summary

I think that should be a deep enough review of your testing code. There are couple key issues I think need looking at.

  1. The testing code is FAR too slow (both to compile and run). And worse, it’s completely unnecessarily slow. Slow testing code means:

    1. the tests won’t be run as often, which defeats the purpose; and
    2. the tests may fail to run in constrained environments… which, unfortunately, often includes CI servers.
  2. Related to the previous point, the vast majority of the tests are completely pointless. If the algorithm works for vector<int>, there’s no reason to assume it won’t work for vector<unsigned int> or vector<short>. Sure you could imagine contrived scenarios where the person writing the algorithm is being deliberately silly or malicious, and might create problems like this, but that’s not really the mindset you should approach testing with. You’re looking for mistakes, not monsters. You’re looking for Murphy, not Machiavelli. You can test pretty much every conceivable form of your algorithm by checking 0- to 3-dimensional input ranges… there’s no need to check all the way up to 15-dimensional ranges. If a 3D range works, a 15D or 150D range will work as well. (And if you have a reason to think it won’t THEN you write those tests.)

    And not only the are tests unnecessary by being redundant, they don’t actually test everything you should really be testing. I wrote 4 tests (well, 3 + 1 templated test that has a dozen or so instantiations), in a total of less than 100 lines, and I found bugs and errors missed by those ~200 tests that delve into 15-dimensional ranges. Having more tests isn’t a good thing if those tests are superfluous, and it might even be a bad thing because it slows compilation and running.

  3. Test code should be as simple as possible. Ideally there should be no control flow at all: no loops, no ifs, no function calls, no nothing. Just:

    1. set up
    2. do thing being tested; then
    3. check results.

    That’s 1, 2, 3, in order, no breaks, branches, or cycles. And everything should be right there in the test case, self-contained, easy to process. If you need to stop and think about what a test is doing, then you’ve failed somehow.

    IF your test NEEDS to be more complex—which is almost never true, but sorta-kinda is in your case because you’re interested in recursive data structures—then you should make it MINIMALLY complex. If testing code needs to be tested, then you’ve failed somehow.

I would toss out all of your testing code for everything higher than 3 dimensions; I don’t see a purpose to it. I would also throw out at least 3⁄4 of your type list, if not the whole thing; if it works for int, why wouldn’t it work for short? That alone should speed up your tests by several orders of magnitude, and make them worthwhile to run frequently.

Because you’re generating the return types in a non-trivial way, you should make some tests that use type traits to check that everything works the way you expect. For example, you could make sure the return type of recursive_transform(execution::par, vector<string>{"abc", "123"}, [](string const& s) { return size_t(s.size()); }) returns a vector<size_t>. You can use declval<T>() to really control the types explicitly, because declval<string>() and declval<string const&>() are two very different things.

Rather than just throwing everything you can think of into the tests, you should take the time to carefully consider the SUBSTANTIVELY different use cases of the algorithm, and where the sharp edges might be. Like, you know there’s no reason to think that if the algorithm works for vector<double>, that it might not work for vector<int>. So don’t bother to test that. But it might work for vector<double> but fail for vector<string> (with a lambda that takes a string)! So test that! And you don’t need to test for every container in the standard library. You can test vector (because it should always be your default), array (because you have it special-cased), and then, maybe, list (for bidirectional iterators) or forward_list (for forward iterators). (There are no containers in the standard with input iterators, but you can slap one together by using istream_iterators and ranges::subrange. Not that it matters because the algorithm won’t work with ranges with input iterators.)

I won’t tell you exactly how to test your algorithm—because it’s your algorithm, and all of this is pretty subjective—but here’s what I’d consider testing if I were writing the tests for it:

  1. I’d test non-range inputs. This need be only one or two tests at most, to verify that the output type is correct, and that the transform is done.

  2. I’d test 1D ranges—that is, vector<int>, forward_list<double>, or deque<custom_type>. I would check at least std::array with a couple different sizes and value types, std::vector with a couple different value types, and then a range type that isn’t random-access, like std::forward_list (that was my go-to for testing more restricted iterator types in the past, because it is the only standard container with forward iterators). In each case, I’d check the return type, and that the result value is kosher.

  3. I’d test 1D ranges with a string or string_view value type, where the transform function handles strings (or string views). Why? Because this is one of the sharp edges of the algorithm, where it could easily get confused between a 1D range of strings and a 2D range of ranges of characters.

  4. I’d test 2D ranges, because this is the third option in the algorithm—0D ranges are covered by the first overload, and 1D ranges just degrade to std::transform(); 2D ranges are where the algorithm first becomes recursive. I’d check arrays of arrays, arrays of vector, vectors of arrays (all of the previous to trigger the array special case, and ensure it works), vectors of vectors, and then maybe a more exotic option or two, like a deque<forward_list<int>>.

  5. I’d test 3D ranges, because this is where the recursion really gets tested. If it can properly handle doing “3D recursive → 2D recursive → 1D non-recursive → 0D value”, then there’s no reason to suspect it can’t keep adding additional levels of recursion to the beginning there.

And that’s it. I probably wouldn’t bother testing 4D or greater, or if I did, it would be as a single case, just for the hell of it.

As for how I’d organize all this, I’d break it into 0D, 1D, 2D, and 3D tests.

The 0D tests are simple. I probably wouldn’t even bother to use templates or data-driven tests. I’d just make a couple of simple test cases, and do very basic tests, like the simple_int test I wrote above.

The 1D tests I’d use templated tests. I’d set up a tuple of tuples with the input range type, and the expected output range type, and maybe the actual output range type. Then I might do:

  • 1 templated test case that checks that the expected and actual output types are the same
  • 1 templated test case that creates an empty instance of the input range, runs a dummy transform function, and then check that the output range is empty; and
  • 1 templated test case that creates an instance of the input range filled with a set of values like “1, 2, 3”, and then runs a simple transform like doubling or squaring, and then check that the output range is as expected.

I’d also include special tests for arrays and vectors (and maybe a list or forward list) of strings with a string transform function, to make sure that they’re treated like a 1D range of strings and not a 2D range of chars. Both arrays and vectors need to be checked, because arrays are special cased. (You should also check Boost’s multi-array if that’s special-cased as well.)

The logic for the 2D and 3D tests is basically identical. To actually test that the output range is as expected, you will probably need to write a custom predicate to do the comparison. (Or you can do it inline, as I did above… but that’s not a great idea.) You don’t need to write a predicate that can support arbitrarily recursive structures. You can just write one for 2D structures, and one for 3D structures. (And if you want to test a 4D or greater structure, well, then you can write one for that, too, I suppose. Though if there’s only a single test, it might be better do that one inline.)

Remember that with testing, more is better, but with test code, less is more.

  • Test code should be simple, clear, self-contained, idempotent, quick, and with no complicated or hidden logic. If you have to think about what a test is doing, something has gone horribly wrong. (As always, this is a rule of thumb, not a rule. If you need a complicated test… well, then you need it. C’est la vie.)

  • Test anything that might fail. Your tests check that the transform worked, and that’s good, but that’s not the only thing recursive_transform() does. It also deduces the return type, and can construct a rather complicated structure within the return value, and you never test whether any of that works. Those should be their own test case(s). For recursive_transform(), there are basically three things you need to check:

    • is the return type correct?
    • is the return value’s structure correct (that is, if it’s a 3D vector of vector of vectors, are the sizes of all the vectors and sub-vectors correct)?; and
    • is the return value correct (that is, are all the recursively-contained values correct)?

    I’m simplifying because there are other possible things you could check, like whether the transform function is called the correct number of times, and so on; those are esoteric concerns that should be checked separately (and, honestly, I wouldn’t bother in a first pass of writing the code… maybe if the algorithm became heavily used or really important to some core facility). But basically, the three things above are what you want to check, and should ideally all be checked separately. (In practice, I’d just check the latter two at the same time, because meh, why not?)

  • Don’t needlessly repeat tests. If you tested with int and it worked, there’s almost never a reason to test with short or long (for example). Unless you know or suspect there might be different behaviour between two cases, just test one of them. There is something to be said for fuzz testing to really slam your algorithm with every kind of input imaginable, but that should really be done separately, not as part of your standard unit test that you run repeatedly during the development cycle.

  • And finally, turn all warnings on, especially for testing. You’ll find a lot little bullshit with warnings—most of it is harmless, but some of it shines a light on things you missed or didn’t consider.

Note that I’ve focused this review on the testing code, not so much on the algorithm code itself (though some issues in the algorithm code did come up during the testing discussion, of course). I gather there are separate reviews on the algorithm code, so I won’t belabour the points they make.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This is absolute devotion. \$\endgroup\$
    – L. F.
    Dec 26, 2020 at 9:22
  • \$\begingroup\$ Need more people like this on code review @SE ! \$\endgroup\$
    – user228914
    Dec 26, 2020 at 11:28
1
\$\begingroup\$

Avoid code duplication

You can implement operator!= in terms of operator==, or the other way around, like so:

template<std::ranges::input_range Range1, std::ranges::input_range Range2>
bool operator!=(const Range1& input1, const Range2& input2)
{
    return !(input1 == input2);
}

Make use of std::ranges::mismatch

There is a already a function in the standard library to compare two ranges to each other, and find the first element that differs. You can make use of that:

template<std::ranges::input_range Range1, std::ranges::input_range Range2>
bool operator==(const Range1& input1, const Range2& input2)
{
    auto [in1, in2] = std::ranges::mismatch(input1, input2);
    return in1 == std::end(input1) && in2 == std::end(input2);
}

Consider whether you want to overload operator== this way

One problem of your code is that there is already an operator== for STL containers, but you are introducing an overload that now accepts two containers with a different value type. For example, the following gives an error without your overload:

std::array<int, 3> a{1, 2, 3};
std::array<float, 3> b{1, 2, 3};
return a == b;

Whereas it compiles and returns true with your overload. Maybe that is convenient for you, but consider that other templated code might depend on the fact that a == b is ill-formed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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