Add container overloads for absl::c_transform. PiperOrigin-RevId: 932773193 Change-Id: I07717242a36a768b657249c95d0f7956768344dd
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index fef2911..a6b60cb 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h
@@ -126,14 +126,14 @@ using OutputIter = ContainerIter<OutputRange>; if constexpr (base_internal::IsAtLeastForwardIterator<InputIter>::value) { - base_internal::HardeningAssert( - n <= std::distance(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input))); + base_internal::HardeningAssertLE( + n, std::distance(container_algorithm_internal::c_begin(input), + container_algorithm_internal::c_end(input))); } if constexpr (base_internal::IsAtLeastForwardIterator<OutputIter>::value) { - base_internal::HardeningAssert( - n <= std::distance(container_algorithm_internal::c_begin(output), - container_algorithm_internal::c_end(output))); + base_internal::HardeningAssertLE( + n, std::distance(container_algorithm_internal::c_begin(output), + container_algorithm_internal::c_end(output))); } } @@ -143,9 +143,9 @@ using OutputIter = ContainerIter<OutputRange>; if constexpr (base_internal::IsAtLeastForwardIterator<InputIter>::value && base_internal::IsAtLeastForwardIterator<OutputIter>::value) { - base_internal::HardeningAssert( + base_internal::HardeningAssertLE( std::distance(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input)) <= + container_algorithm_internal::c_end(input)), std::distance(container_algorithm_internal::c_begin(output), container_algorithm_internal::c_end(output))); } @@ -756,33 +756,109 @@ // result in an iterator pointing to the last transformed element in the output // range. template <typename InputSequence, typename OutputIterator, typename UnaryOp> -constexpr OutputIterator c_transform(const InputSequence& input, - OutputIterator output, - UnaryOp&& unary_op) { +constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer< + InputSequence, OutputIterator> +c_transform(const InputSequence& input, OutputIterator&& output, + UnaryOp&& unary_op) { return std::transform(container_algorithm_internal::c_begin(input), - container_algorithm_internal::c_end(input), output, + container_algorithm_internal::c_end(input), + std::forward<OutputIterator>(output), std::forward<UnaryOp>(unary_op)); } +// Performs a transformation using a unary predicate. Stores the result in +// `output`. `absl::c_transform(input, output, unary_op)` is equivalent to +// `std::transform(std::begin(input), std::end(input), std::begin(output), +// unary_op)`. +// +// The `output` container must be large enough to hold all elements of `input`; +// this function does not resize `output`. +template <typename InputSequence, typename OutputRange, typename UnaryOp> +constexpr container_algorithm_internal::ResultOfRangeToRangeTransfer< + InputSequence, OutputRange> +c_transform(const InputSequence& input, OutputRange&& output, + UnaryOp&& unary_op) { + container_algorithm_internal::AssertCopySize(input, output); + absl::c_transform( + input, + container_algorithm_internal::c_begin(std::forward<OutputRange>(output)), + std::forward<UnaryOp>(unary_op)); +} + // Overload of c_transform() for performing a transformation using a binary // predicate. Applies `binary_op` to the first N elements of `c1` and `c2`, // where N = min(size(c1), size(c2)). template <typename InputSequence1, typename InputSequence2, typename OutputIterator, typename BinaryOp> -constexpr OutputIterator c_transform(const InputSequence1& input1, - const InputSequence2& input2, - OutputIterator output, - BinaryOp&& binary_op) { +constexpr container_algorithm_internal::ResultOfRangeToIteratorTransfer< + InputSequence1, OutputIterator> +c_transform(const InputSequence1& input1, const InputSequence2& input2, + OutputIterator&& output, BinaryOp&& binary_op) { auto first1 = container_algorithm_internal::c_begin(input1); auto last1 = container_algorithm_internal::c_end(input1); auto first2 = container_algorithm_internal::c_begin(input2); auto last2 = container_algorithm_internal::c_end(input2); - for (; first1 != last1 && first2 != last2; - ++first1, (void)++first2, ++output) { - *output = binary_op(*first1, *first2); + std::decay_t<OutputIterator> out = std::forward<OutputIterator>(output); + for (; first1 != last1 && first2 != last2; ++first1, (void)++first2, ++out) { + *out = binary_op(*first1, *first2); } + return out; +} - return output; +// Performs a transformation using a binary predicate. Stores the result in +// `output`. Applies `binary_op` to the first N elements of `input1` and +// `input2`, where N = min(size(input1), size(input2)). +// +// The `output` container must be large enough to hold all N elements; +// this function does not resize `output`. +template <typename InputSequence1, typename InputSequence2, + typename OutputRange, typename BinaryOp> +constexpr std::common_type_t< + container_algorithm_internal::ResultOfRangeToRangeTransfer<InputSequence1, + OutputRange>, + container_algorithm_internal::ResultOfRangeToRangeTransfer<InputSequence2, + OutputRange>> +c_transform(const InputSequence1& input1, const InputSequence2& input2, + OutputRange&& output, BinaryOp&& binary_op) { + using InputIter1 = + container_algorithm_internal::ContainerIter<InputSequence1>; + using InputIter2 = + container_algorithm_internal::ContainerIter<InputSequence2>; + using OutputIter = container_algorithm_internal::ContainerIter<OutputRange>; + if constexpr (base_internal::IsAtLeastForwardIterator<OutputIter>::value) { + constexpr bool input1_has_size = + base_internal::IsAtLeastForwardIterator<InputIter1>::value; + constexpr bool input2_has_size = + base_internal::IsAtLeastForwardIterator<InputIter2>::value; + auto output_size = + std::distance(container_algorithm_internal::c_begin(output), + container_algorithm_internal::c_end(output)); + + if constexpr (input1_has_size && input2_has_size) { + base_internal::HardeningAssertLE( + (std::min)(std::distance( + container_algorithm_internal::c_begin(input1), + container_algorithm_internal::c_end(input1)), + std::distance( + container_algorithm_internal::c_begin(input2), + container_algorithm_internal::c_end(input2))), + output_size); + } else if constexpr (input1_has_size) { + base_internal::HardeningAssertLE( + std::distance(container_algorithm_internal::c_begin(input1), + container_algorithm_internal::c_end(input1)), + output_size); + } else if constexpr (input2_has_size) { + base_internal::HardeningAssertLE( + std::distance(container_algorithm_internal::c_begin(input2), + container_algorithm_internal::c_end(input2)), + output_size); + } + } + absl::c_transform( + input1, input2, + container_algorithm_internal::c_begin(std::forward<OutputRange>(output)), + std::forward<BinaryOp>(binary_op)); } // c_replace()
diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc index 0b67001..2dd74e4 100644 --- a/absl/algorithm/container_test.cc +++ b/absl/algorithm/container_test.cc
@@ -857,7 +857,6 @@ EXPECT_THAT(actual, ElementsAre(1, 2, 0, 0, 0)); } -#if GTEST_HAS_DEATH_TEST bool IsHardened() { bool hardened = false; @@ -871,77 +870,96 @@ TEST(MutatingTest, CopyToCArrayInvalidSize) { const std::vector<int> input = {1, 2, 3}; int actual[2] = {0, 0}; + (void)actual; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy(input, actual), ""); } +#endif } TEST(MutatingTest, CopyNToCArrayInvalidSize) { const std::vector<int> input = {1, 2, 3}; int actual[2] = {0, 0}; + (void)actual; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy_n(input, 3, actual), ""); } +#endif } TEST(MutatingTest, CopyNToCArrayNGreaterThanInput) { const std::vector<int> input = {1, 2, 3}; int actual[4] = {0, 0, 0, 0}; + (void)actual; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy_n(input, 4, actual), ""); } +#endif } TEST(MutatingTest, CopyToContainerInvalidSize) { const std::list<int> input = {1, 2, 3, 4, 5}; std::list<int> actual = {0, 0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy(input, actual), ""); } +#endif } TEST(MutatingTest, CopyNToContainerNGreaterThanInput) { const std::vector<int> input = {1, 2, 3}; std::vector<int> actual = {0, 0, 0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy_n(input, 4, actual), ""); } +#endif } TEST(MutatingTest, CopyNToContainerNGreaterThanOutput) { const std::vector<int> input = {1, 2, 3}; std::vector<int> actual = {0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy_n(input, 3, actual), ""); } +#endif } TEST(MutatingTest, CopyToForwardListInvalidSize) { const std::forward_list<int> input = {1, 2, 3, 4, 5}; std::forward_list<int> actual = {0, 0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy(input, actual), ""); } +#endif } TEST(MutatingTest, CopyNToForwardListNGreaterThanInput) { const std::forward_list<int> input = {1, 2, 3}; std::forward_list<int> actual = {0, 0, 0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy_n(input, 4, actual), ""); } +#endif } TEST(MutatingTest, CopyNToForwardListNGreaterThanOutput) { const std::forward_list<int> input = {1, 2, 3}; std::forward_list<int> actual = {0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_copy_n(input, 3, actual), ""); } +#endif } -#endif // GTEST_HAS_DEATH_TEST - TEST(MutatingTest, CopyIf) { const std::list<int> input = {1, 2, 3}; std::vector<int> output; @@ -1083,34 +1101,38 @@ EXPECT_EQ(*actual[0], 1); } -#if GTEST_HAS_DEATH_TEST TEST(MutatingTest, MoveToCArrayInvalidSize) { std::vector<int> input = {1, 2, 3}; int actual[2] = {0, 0}; + (void)actual; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_move(input, actual), ""); } +#endif } TEST(MutatingTest, MoveToContainerInvalidSize) { std::list<int> input = {1, 2, 3, 4, 5}; std::list<int> actual = {0, 0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_move(input, actual), ""); } +#endif } TEST(MutatingTest, MoveToForwardListInvalidSize) { std::forward_list<int> input = {1, 2, 3, 4, 5}; std::forward_list<int> actual = {0, 0, 0}; +#if GTEST_HAS_DEATH_TEST if (IsHardened()) { EXPECT_DEATH(absl::c_move(input, actual), ""); } +#endif } -#endif // GTEST_HAS_DEATH_TEST - TEST(MutatingTest, SwapRanges) { std::vector<int> odds = {2, 4, 6}; std::vector<int> evens = {1, 3, 5}; @@ -1141,19 +1163,138 @@ *end = 7; EXPECT_EQ(std::vector<int>({1, 5, 4, 7}), z); - z.clear(); - y.pop_back(); - end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>()); - EXPECT_EQ(std::vector<int>({1, 5}), z); - *end = 7; - EXPECT_EQ(std::vector<int>({1, 5, 7}), z); + std::vector<int> x2{1, 2, 3}; + std::vector<int> y2{10, 20, 30}; + std::vector<int> z2(3); + auto out_it = z2.begin(); + absl::c_transform(x2, y2, out_it, std::plus<int>()); + // The caller's iterator should not be modified. + EXPECT_EQ(out_it, z2.begin()); + EXPECT_EQ(z2, std::vector<int>({11, 22, 33})); +} - z.clear(); - std::swap(x, y); - end = absl::c_transform(x, y, std::back_inserter(z), std::plus<int>()); - EXPECT_EQ(std::vector<int>({1, 5}), z); - *end = 7; - EXPECT_EQ(std::vector<int>({1, 5, 7}), z); +TEST(MutatingTest, TransformToContainer) { + const std::vector<int> input = {1, 2, 3}; + std::vector<int> actual = {0, 0, 0, 4, 5}; + absl::c_transform(input, actual, [](int x) { return x * 2; }); + EXPECT_THAT(actual, ElementsAre(2, 4, 6, 4, 5)); +} + +TEST(MutatingTest, BinaryTransformToContainer) { + { + const std::vector<int> input1 = {1, 2, 3}; + const std::vector<int> input2 = {10, 20, 30}; + std::vector<int> actual = {0, 0, 0, 4, 5}; + absl::c_transform(input1, input2, actual, std::plus<int>()); + EXPECT_THAT(actual, ElementsAre(11, 22, 33, 4, 5)); + } + { + const std::vector<int> input1 = {1, 2, 3, 4}; + const std::vector<int> input2 = {10, 20}; + std::vector<int> actual = {0, 0, 0, 4, 5}; + absl::c_transform(input1, input2, actual, std::plus<int>()); + EXPECT_THAT(actual, ElementsAre(11, 22, 0, 4, 5)); + } + { + const std::vector<int> input1 = {1, 2}; + const std::vector<int> input2 = {10, 20, 30, 40}; + std::vector<int> actual = {0, 0, 0, 4, 5}; + absl::c_transform(input1, input2, actual, std::plus<int>()); + EXPECT_THAT(actual, ElementsAre(11, 22, 0, 4, 5)); + } +} + +TEST(MutatingTest, TransformToDifferentContainerType) { + const std::list<int> input = {1, 2, 3}; + std::array<int, 5> actual = {0, 0, 0, 4, 5}; + absl::c_transform(input, actual, [](int x) { return x * 2; }); + EXPECT_THAT(actual, ElementsAre(2, 4, 6, 4, 5)); +} + +TEST(MutatingTest, TransformToCArray) { + const std::vector<int> input = {1, 2, 3}; + int actual[5] = {0, 0, 0, 4, 5}; + absl::c_transform(input, actual, [](int x) { return x * 2; }); + EXPECT_THAT(actual, ElementsAre(2, 4, 6, 4, 5)); +} + +TEST(MutatingTest, TransformFromCArray) { + const int input[5] = {1, 2, 3, 4, 5}; + std::vector<int> actual = {0, 0, 0, 0, 0}; + absl::c_transform(input, actual, [](int x) { return x * 2; }); + EXPECT_THAT(actual, ElementsAre(2, 4, 6, 8, 10)); +} + +TEST(MutatingTest, TransformToCArrayInvalidSize) { + const std::vector<int> input = {1, 2, 3}; + int actual[2] = {0, 0}; + (void)actual; +#if GTEST_HAS_DEATH_TEST + if (IsHardened()) { + EXPECT_DEATH(absl::c_transform(input, actual, [](int x) { return x * 2; }), + ""); + } +#endif +} + +TEST(MutatingTest, BinaryTransformToCArrayInvalidSize) { + const std::vector<int> input1 = {1, 2, 3}; + const std::vector<int> input2 = {10, 20, 30}; + int actual[2] = {0, 0}; + (void)actual; +#if GTEST_HAS_DEATH_TEST + if (IsHardened()) { + EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()), + ""); + } +#endif +} + +TEST(MutatingTest, TransformToContainerInvalidSize) { + const std::list<int> input = {1, 2, 3, 4, 5}; + std::list<int> actual = {0, 0, 0}; +#if GTEST_HAS_DEATH_TEST + if (IsHardened()) { + EXPECT_DEATH(absl::c_transform(input, actual, [](int x) { return x * 2; }), + ""); + } +#endif +} + +TEST(MutatingTest, BinaryTransformToContainerInvalidSize) { + const std::vector<int> input1 = {1, 2, 3, 4, 5}; + const std::vector<int> input2 = {10, 20, 30, 40, 50}; + std::vector<int> actual = {0, 0, 0}; +#if GTEST_HAS_DEATH_TEST + if (IsHardened()) { + EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()), + ""); + } +#endif +} + +TEST(MutatingTest, BinaryTransformInput2InvalidSize) { + const std::vector<int> input1 = {1, 2, 3}; + const std::vector<int> input2 = {10, 20}; + std::vector<int> actual = {0}; +#if GTEST_HAS_DEATH_TEST + if (IsHardened()) { + EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()), + ""); + } +#endif +} + +TEST(MutatingTest, BinaryTransformInput1InvalidSize) { + const std::vector<int> input1 = {1, 2}; + const std::vector<int> input2 = {10, 20, 30}; + std::vector<int> actual = {0}; +#if GTEST_HAS_DEATH_TEST + if (IsHardened()) { + EXPECT_DEATH(absl::c_transform(input1, input2, actual, std::plus<int>()), + ""); + } +#endif } TEST(MutatingTest, Replace) { @@ -2633,6 +2774,27 @@ std::declval<Output>()))>> : std::true_type {}; +template <typename Container, typename Output, typename UnaryOp, + typename = void> +struct CanTransformUnary : std::false_type {}; +template <typename Container, typename Output, typename UnaryOp> +struct CanTransformUnary<Container, Output, UnaryOp, + absl::void_t<decltype(absl::c_transform( + std::declval<Container>(), std::declval<Output>(), + std::declval<UnaryOp>()))>> : std::true_type {}; + +template <typename Container1, typename Container2, typename Output, + typename BinaryOp, typename = void> +struct CanTransformBinary : std::false_type {}; +template <typename Container1, typename Container2, typename Output, + typename BinaryOp> +struct CanTransformBinary< + Container1, Container2, Output, BinaryOp, + absl::void_t<decltype(absl::c_transform( + std::declval<Container1>(), std::declval<Container2>(), + std::declval<Output>(), std::declval<BinaryOp>()))>> : std::true_type { +}; + TEST(CanCopyTest, CopyToMultiDimArray) { static_assert(CanCopy<std::vector<int>, int (&)[10]>::value); static_assert(!CanCopy<std::vector<int>, int (&)[2][2]>::value); @@ -2706,6 +2868,47 @@ "Should not be able to move to rvalue vector"); } +TEST(CanTransformTest, TransformToMultiDimArray) { + using Negate = std::negate<int>; + using Plus = std::plus<int>; + + static_assert( + CanTransformUnary<std::vector<int>, int (&)[10], Negate>::value); + static_assert( + !CanTransformUnary<std::vector<int>, int (&)[2][2], Negate>::value); + + static_assert(CanTransformUnary<int[10], int (&)[10], Negate>::value); + static_assert(!CanTransformUnary<int[10], int (&)[2][2], Negate>::value); + static_assert(!CanTransformUnary<int[2][2], int (&)[4], Negate>::value); + static_assert(!CanTransformUnary<int[2][2], int (&)[2][2], Negate>::value); + + static_assert(CanTransformBinary<std::vector<int>, std::vector<int>, + int (&)[10], Plus>::value); + static_assert(!CanTransformBinary<std::vector<int>, std::vector<int>, + int (&)[2][2], Plus>::value); + + static_assert(CanTransformBinary<int[10], int[10], int (&)[10], Plus>::value); + static_assert( + !CanTransformBinary<int[10], int[10], int (&)[2][2], Plus>::value); + static_assert( + !CanTransformBinary<int[2][2], int[4], int (&)[4], Plus>::value); + static_assert( + !CanTransformBinary<int[2][2], int[2][2], int (&)[2][2], Plus>::value); +} + +TEST(CanTransformTest, AmbiguousTypeFailsToCompile) { + using Vec = std::vector<int>; + using Negate = std::negate<int>; + using Plus = std::plus<int>; + + // Because AmbiguousType is both an iterator and a container, + // the compiler should fail to resolve the c_transform overload. + static_assert(!CanTransformUnary<Vec, AmbiguousType&, Negate>::value, + "Ambiguous types should not compile!"); + static_assert(!CanTransformBinary<Vec, Vec, AmbiguousType&, Plus>::value, + "Ambiguous types should not compile!"); +} + template <typename C, typename T, typename = void> struct CanFill : std::false_type {};