diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/algorithm')
4 files changed, 282 insertions, 141 deletions
diff --git a/third_party/abseil-cpp/absl/algorithm/BUILD.bazel b/third_party/abseil-cpp/absl/algorithm/BUILD.bazel index 6a96420b96..afc5263998 100644 --- a/third_party/abseil-cpp/absl/algorithm/BUILD.bazel +++ b/third_party/abseil-cpp/absl/algorithm/BUILD.bazel @@ -14,7 +14,6 @@ # limitations under the License. # -load("@rules_cc//cc:defs.bzl", "cc_library", "cc_test") load( "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", @@ -24,14 +23,16 @@ load( package(default_visibility = ["//visibility:public"]) -licenses(["notice"]) # Apache 2.0 +licenses(["notice"]) cc_library( name = "algorithm", hdrs = ["algorithm.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, - deps = ["//absl/base:config"], + deps = [ + "//absl/base:config", + ], ) cc_test( diff --git a/third_party/abseil-cpp/absl/algorithm/CMakeLists.txt b/third_party/abseil-cpp/absl/algorithm/CMakeLists.txt index 56cd0fb85b..609d858946 100644 --- a/third_party/abseil-cpp/absl/algorithm/CMakeLists.txt +++ b/third_party/abseil-cpp/absl/algorithm/CMakeLists.txt @@ -35,7 +35,7 @@ absl_cc_test( ${ABSL_TEST_COPTS} DEPS absl::algorithm - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -65,5 +65,5 @@ absl_cc_test( absl::core_headers absl::memory absl::span - gmock_main + GTest::gmock_main ) diff --git a/third_party/abseil-cpp/absl/algorithm/container.h b/third_party/abseil-cpp/absl/algorithm/container.h index d72532decf..c38a4a63db 100644 --- a/third_party/abseil-cpp/absl/algorithm/container.h +++ b/third_party/abseil-cpp/absl/algorithm/container.h @@ -90,10 +90,10 @@ using ContainerPointerType = // lookup of std::begin and std::end, i.e. // using std::begin; // using std::end; -// std::foo(begin(c), end(c); +// std::foo(begin(c), end(c)); // becomes // std::foo(container_algorithm_internal::begin(c), -// container_algorithm_internal::end(c)); +// container_algorithm_internal::end(c)); // These are meant for internal use only. template <typename C> @@ -188,7 +188,7 @@ bool c_any_of(const C& c, Pred&& pred) { // c_none_of() // // Container-based version of the <algorithm> `std::none_of()` function to -// test if no elements in a container fulfil a condition. +// test if no elements in a container fulfill a condition. template <typename C, typename Pred> bool c_none_of(const C& c, Pred&& pred) { return std::none_of(container_algorithm_internal::c_begin(c), @@ -340,24 +340,45 @@ container_algorithm_internal::ContainerDifferenceType<const C> c_count_if( // c_mismatch() // // Container-based version of the <algorithm> `std::mismatch()` function to -// return the first element where two ordered containers differ. +// return the first element where two ordered containers differ. Applies `==` to +// the first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)). template <typename C1, typename C2> container_algorithm_internal::ContainerIterPairType<C1, C2> c_mismatch(C1& c1, C2& c2) { - return std::mismatch(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2)); + auto first1 = container_algorithm_internal::c_begin(c1); + auto last1 = container_algorithm_internal::c_end(c1); + auto first2 = container_algorithm_internal::c_begin(c2); + auto last2 = container_algorithm_internal::c_end(c2); + + for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) { + // Negates equality because Cpp17EqualityComparable doesn't require clients + // to overload both `operator==` and `operator!=`. + if (!(*first1 == *first2)) { + break; + } + } + + return std::make_pair(first1, first2); } // Overload of c_mismatch() for using a predicate evaluation other than `==` as -// the function's test condition. +// the function's test condition. Applies `pred`to the first N elements of `c1` +// and `c2`, where N = min(size(c1), size(c2)). template <typename C1, typename C2, typename BinaryPredicate> container_algorithm_internal::ContainerIterPairType<C1, C2> -c_mismatch(C1& c1, C2& c2, BinaryPredicate&& pred) { - return std::mismatch(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2), - std::forward<BinaryPredicate>(pred)); +c_mismatch(C1& c1, C2& c2, BinaryPredicate pred) { + auto first1 = container_algorithm_internal::c_begin(c1); + auto last1 = container_algorithm_internal::c_end(c1); + auto first2 = container_algorithm_internal::c_begin(c2); + auto last2 = container_algorithm_internal::c_end(c2); + + for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) { + if (!pred(*first1, *first2)) { + break; + } + } + + return std::make_pair(first1, first2); } // c_equal() @@ -539,12 +560,20 @@ BidirectionalIterator c_move_backward(C&& src, BidirectionalIterator dest) { // c_swap_ranges() // // Container-based version of the <algorithm> `std::swap_ranges()` function to -// swap a container's elements with another container's elements. +// swap a container's elements with another container's elements. Swaps the +// first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)). template <typename C1, typename C2> container_algorithm_internal::ContainerIter<C2> c_swap_ranges(C1& c1, C2& c2) { - return std::swap_ranges(container_algorithm_internal::c_begin(c1), - container_algorithm_internal::c_end(c1), - container_algorithm_internal::c_begin(c2)); + auto first1 = container_algorithm_internal::c_begin(c1); + auto last1 = container_algorithm_internal::c_end(c1); + auto first2 = container_algorithm_internal::c_begin(c2); + auto last2 = container_algorithm_internal::c_end(c2); + + using std::swap; + for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) { + swap(*first1, *first2); + } + return first2; } // c_transform() @@ -562,16 +591,23 @@ OutputIterator c_transform(const InputSequence& input, OutputIterator output, } // Overload of c_transform() for performing a transformation using a binary -// predicate. +// 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> OutputIterator c_transform(const InputSequence1& input1, const InputSequence2& input2, OutputIterator output, BinaryOp&& binary_op) { - return std::transform(container_algorithm_internal::c_begin(input1), - container_algorithm_internal::c_end(input1), - container_algorithm_internal::c_begin(input2), output, - std::forward<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); + } + + return output; } // c_replace() @@ -869,11 +905,11 @@ void c_sort(C& c) { // Overload of c_sort() for performing a `comp` comparison other than the // default `operator<`. -template <typename C, typename Compare> -void c_sort(C& c, Compare&& comp) { +template <typename C, typename LessThan> +void c_sort(C& c, LessThan&& comp) { std::sort(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_stable_sort() @@ -889,11 +925,11 @@ void c_stable_sort(C& c) { // Overload of c_stable_sort() for performing a `comp` comparison other than the // default `operator<`. -template <typename C, typename Compare> -void c_stable_sort(C& c, Compare&& comp) { +template <typename C, typename LessThan> +void c_stable_sort(C& c, LessThan&& comp) { std::stable_sort(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_is_sorted() @@ -908,11 +944,11 @@ bool c_is_sorted(const C& c) { // c_is_sorted() overload for performing a `comp` comparison other than the // default `operator<`. -template <typename C, typename Compare> -bool c_is_sorted(const C& c, Compare&& comp) { +template <typename C, typename LessThan> +bool c_is_sorted(const C& c, LessThan&& comp) { return std::is_sorted(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_partial_sort() @@ -930,22 +966,23 @@ void c_partial_sort( // Overload of c_partial_sort() for performing a `comp` comparison other than // the default `operator<`. -template <typename RandomAccessContainer, typename Compare> +template <typename RandomAccessContainer, typename LessThan> void c_partial_sort( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter<RandomAccessContainer> middle, - Compare&& comp) { + LessThan&& comp) { std::partial_sort(container_algorithm_internal::c_begin(sequence), middle, container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_partial_sort_copy() // // Container-based version of the <algorithm> `std::partial_sort_copy()` -// function to sort elements within a container such that elements before -// `middle` are sorted in ascending order, and return the result within an -// iterator. +// function to sort the elements in the given range `result` within the larger +// `sequence` in ascending order (and using `result` as the output parameter). +// At most min(result.last - result.first, sequence.last - sequence.first) +// elements from the sequence will be stored in the result. template <typename C, typename RandomAccessContainer> container_algorithm_internal::ContainerIter<RandomAccessContainer> c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) { @@ -957,15 +994,15 @@ c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) { // Overload of c_partial_sort_copy() for performing a `comp` comparison other // than the default `operator<`. -template <typename C, typename RandomAccessContainer, typename Compare> +template <typename C, typename RandomAccessContainer, typename LessThan> container_algorithm_internal::ContainerIter<RandomAccessContainer> c_partial_sort_copy(const C& sequence, RandomAccessContainer& result, - Compare&& comp) { + LessThan&& comp) { return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(result), container_algorithm_internal::c_end(result), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_is_sorted_until() @@ -981,12 +1018,12 @@ container_algorithm_internal::ContainerIter<C> c_is_sorted_until(C& c) { // Overload of c_is_sorted_until() for performing a `comp` comparison other than // the default `operator<`. -template <typename C, typename Compare> +template <typename C, typename LessThan> container_algorithm_internal::ContainerIter<C> c_is_sorted_until( - C& c, Compare&& comp) { + C& c, LessThan&& comp) { return std::is_sorted_until(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_nth_element() @@ -1006,14 +1043,14 @@ void c_nth_element( // Overload of c_nth_element() for performing a `comp` comparison other than // the default `operator<`. -template <typename RandomAccessContainer, typename Compare> +template <typename RandomAccessContainer, typename LessThan> void c_nth_element( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter<RandomAccessContainer> nth, - Compare&& comp) { + LessThan&& comp) { std::nth_element(container_algorithm_internal::c_begin(sequence), nth, container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } //------------------------------------------------------------------------------ @@ -1035,12 +1072,12 @@ container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( // Overload of c_lower_bound() for performing a `comp` comparison other than // the default `operator<`. -template <typename Sequence, typename T, typename Compare> +template <typename Sequence, typename T, typename LessThan> container_algorithm_internal::ContainerIter<Sequence> c_lower_bound( - Sequence& sequence, T&& value, Compare&& comp) { + Sequence& sequence, T&& value, LessThan&& comp) { return std::lower_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<T>(value), std::forward<Compare>(comp)); + std::forward<T>(value), std::forward<LessThan>(comp)); } // c_upper_bound() @@ -1058,12 +1095,12 @@ container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( // Overload of c_upper_bound() for performing a `comp` comparison other than // the default `operator<`. -template <typename Sequence, typename T, typename Compare> +template <typename Sequence, typename T, typename LessThan> container_algorithm_internal::ContainerIter<Sequence> c_upper_bound( - Sequence& sequence, T&& value, Compare&& comp) { + Sequence& sequence, T&& value, LessThan&& comp) { return std::upper_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<T>(value), std::forward<Compare>(comp)); + std::forward<T>(value), std::forward<LessThan>(comp)); } // c_equal_range() @@ -1081,12 +1118,12 @@ c_equal_range(Sequence& sequence, T&& value) { // Overload of c_equal_range() for performing a `comp` comparison other than // the default `operator<`. -template <typename Sequence, typename T, typename Compare> +template <typename Sequence, typename T, typename LessThan> container_algorithm_internal::ContainerIterPairType<Sequence, Sequence> -c_equal_range(Sequence& sequence, T&& value, Compare&& comp) { +c_equal_range(Sequence& sequence, T&& value, LessThan&& comp) { return std::equal_range(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<T>(value), std::forward<Compare>(comp)); + std::forward<T>(value), std::forward<LessThan>(comp)); } // c_binary_search() @@ -1103,12 +1140,12 @@ bool c_binary_search(Sequence&& sequence, T&& value) { // Overload of c_binary_search() for performing a `comp` comparison other than // the default `operator<`. -template <typename Sequence, typename T, typename Compare> -bool c_binary_search(Sequence&& sequence, T&& value, Compare&& comp) { +template <typename Sequence, typename T, typename LessThan> +bool c_binary_search(Sequence&& sequence, T&& value, LessThan&& comp) { return std::binary_search(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward<T>(value), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } //------------------------------------------------------------------------------ @@ -1129,14 +1166,14 @@ OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result) { // Overload of c_merge() for performing a `comp` comparison other than // the default `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare> +template <typename C1, typename C2, typename OutputIterator, typename LessThan> OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result, - Compare&& comp) { + LessThan&& comp) { return std::merge(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), result, - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_inplace_merge() @@ -1152,13 +1189,13 @@ void c_inplace_merge(C& c, // Overload of c_inplace_merge() for performing a merge using a `comp` other // than `operator<`. -template <typename C, typename Compare> +template <typename C, typename LessThan> void c_inplace_merge(C& c, container_algorithm_internal::ContainerIter<C> middle, - Compare&& comp) { + LessThan&& comp) { std::inplace_merge(container_algorithm_internal::c_begin(c), middle, container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_includes() @@ -1176,13 +1213,13 @@ bool c_includes(const C1& c1, const C2& c2) { // Overload of c_includes() for performing a merge using a `comp` other than // `operator<`. -template <typename C1, typename C2, typename Compare> -bool c_includes(const C1& c1, const C2& c2, Compare&& comp) { +template <typename C1, typename C2, typename LessThan> +bool c_includes(const C1& c1, const C2& c2, LessThan&& comp) { return std::includes(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_set_union() @@ -1206,7 +1243,7 @@ OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) { // Overload of c_set_union() for performing a merge using a `comp` other than // `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, +template <typename C1, typename C2, typename OutputIterator, typename LessThan, typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C1>::value, void>::type, @@ -1214,18 +1251,18 @@ template <typename C1, typename C2, typename OutputIterator, typename Compare, !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output, - Compare&& comp) { + LessThan&& comp) { return std::set_union(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_set_intersection() // // Container-based version of the <algorithm> `std::set_intersection()` function -// to return an iterator containing the intersection of two containers. +// to return an iterator containing the intersection of two sorted containers. template <typename C1, typename C2, typename OutputIterator, typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C1>::value, @@ -1235,6 +1272,11 @@ template <typename C1, typename C2, typename OutputIterator, void>::type> OutputIterator c_set_intersection(const C1& c1, const C2& c2, OutputIterator output) { + // In debug builds, ensure that both containers are sorted with respect to the + // default comparator. std::set_intersection requires the containers be sorted + // using operator<. + assert(absl::c_is_sorted(c1)); + assert(absl::c_is_sorted(c2)); return std::set_intersection(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1243,7 +1285,7 @@ OutputIterator c_set_intersection(const C1& c1, const C2& c2, // Overload of c_set_intersection() for performing a merge using a `comp` other // than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, +template <typename C1, typename C2, typename OutputIterator, typename LessThan, typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C1>::value, void>::type, @@ -1251,12 +1293,17 @@ template <typename C1, typename C2, typename OutputIterator, typename Compare, !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> OutputIterator c_set_intersection(const C1& c1, const C2& c2, - OutputIterator output, Compare&& comp) { + OutputIterator output, LessThan&& comp) { + // In debug builds, ensure that both containers are sorted with respect to the + // default comparator. std::set_intersection requires the containers be sorted + // using the same comparator. + assert(absl::c_is_sorted(c1, comp)); + assert(absl::c_is_sorted(c2, comp)); return std::set_intersection(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_set_difference() @@ -1281,7 +1328,7 @@ OutputIterator c_set_difference(const C1& c1, const C2& c2, // Overload of c_set_difference() for performing a merge using a `comp` other // than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, +template <typename C1, typename C2, typename OutputIterator, typename LessThan, typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C1>::value, void>::type, @@ -1289,12 +1336,12 @@ template <typename C1, typename C2, typename OutputIterator, typename Compare, !container_algorithm_internal::IsUnorderedContainer<C2>::value, void>::type> OutputIterator c_set_difference(const C1& c1, const C2& c2, - OutputIterator output, Compare&& comp) { + OutputIterator output, LessThan&& comp) { return std::set_difference(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_set_symmetric_difference() @@ -1320,7 +1367,7 @@ OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, // Overload of c_set_symmetric_difference() for performing a merge using a // `comp` other than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare, +template <typename C1, typename C2, typename OutputIterator, typename LessThan, typename = typename std::enable_if< !container_algorithm_internal::IsUnorderedContainer<C1>::value, void>::type, @@ -1329,13 +1376,13 @@ template <typename C1, typename C2, typename OutputIterator, typename Compare, void>::type> OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, OutputIterator output, - Compare&& comp) { + LessThan&& comp) { return std::set_symmetric_difference( container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } //------------------------------------------------------------------------------ @@ -1354,11 +1401,11 @@ void c_push_heap(RandomAccessContainer& sequence) { // Overload of c_push_heap() for performing a push operation on a heap using a // `comp` other than `operator<`. -template <typename RandomAccessContainer, typename Compare> -void c_push_heap(RandomAccessContainer& sequence, Compare&& comp) { +template <typename RandomAccessContainer, typename LessThan> +void c_push_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::push_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_pop_heap() @@ -1373,11 +1420,11 @@ void c_pop_heap(RandomAccessContainer& sequence) { // Overload of c_pop_heap() for performing a pop operation on a heap using a // `comp` other than `operator<`. -template <typename RandomAccessContainer, typename Compare> -void c_pop_heap(RandomAccessContainer& sequence, Compare&& comp) { +template <typename RandomAccessContainer, typename LessThan> +void c_pop_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::pop_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_make_heap() @@ -1392,11 +1439,11 @@ void c_make_heap(RandomAccessContainer& sequence) { // Overload of c_make_heap() for performing heap comparisons using a // `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> -void c_make_heap(RandomAccessContainer& sequence, Compare&& comp) { +template <typename RandomAccessContainer, typename LessThan> +void c_make_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::make_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_sort_heap() @@ -1411,11 +1458,11 @@ void c_sort_heap(RandomAccessContainer& sequence) { // Overload of c_sort_heap() for performing heap comparisons using a // `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> -void c_sort_heap(RandomAccessContainer& sequence, Compare&& comp) { +template <typename RandomAccessContainer, typename LessThan> +void c_sort_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::sort_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_is_heap() @@ -1430,11 +1477,11 @@ bool c_is_heap(const RandomAccessContainer& sequence) { // Overload of c_is_heap() for performing heap comparisons using a // `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> -bool c_is_heap(const RandomAccessContainer& sequence, Compare&& comp) { +template <typename RandomAccessContainer, typename LessThan> +bool c_is_heap(const RandomAccessContainer& sequence, LessThan&& comp) { return std::is_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_is_heap_until() @@ -1450,12 +1497,12 @@ c_is_heap_until(RandomAccessContainer& sequence) { // Overload of c_is_heap_until() for performing heap comparisons using a // `comp` other than `operator<` -template <typename RandomAccessContainer, typename Compare> +template <typename RandomAccessContainer, typename LessThan> container_algorithm_internal::ContainerIter<RandomAccessContainer> -c_is_heap_until(RandomAccessContainer& sequence, Compare&& comp) { +c_is_heap_until(RandomAccessContainer& sequence, LessThan&& comp) { return std::is_heap_until(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } //------------------------------------------------------------------------------ @@ -1476,12 +1523,12 @@ container_algorithm_internal::ContainerIter<Sequence> c_min_element( // Overload of c_min_element() for performing a `comp` comparison other than // `operator<`. -template <typename Sequence, typename Compare> +template <typename Sequence, typename LessThan> container_algorithm_internal::ContainerIter<Sequence> c_min_element( - Sequence& sequence, Compare&& comp) { + Sequence& sequence, LessThan&& comp) { return std::min_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_max_element() @@ -1498,12 +1545,12 @@ container_algorithm_internal::ContainerIter<Sequence> c_max_element( // Overload of c_max_element() for performing a `comp` comparison other than // `operator<`. -template <typename Sequence, typename Compare> +template <typename Sequence, typename LessThan> container_algorithm_internal::ContainerIter<Sequence> c_max_element( - Sequence& sequence, Compare&& comp) { + Sequence& sequence, LessThan&& comp) { return std::max_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_minmax_element() @@ -1521,12 +1568,12 @@ c_minmax_element(C& c) { // Overload of c_minmax_element() for performing `comp` comparisons other than // `operator<`. -template <typename C, typename Compare> +template <typename C, typename LessThan> container_algorithm_internal::ContainerIterPairType<C, C> -c_minmax_element(C& c, Compare&& comp) { +c_minmax_element(C& c, LessThan&& comp) { return std::minmax_element(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } //------------------------------------------------------------------------------ @@ -1551,15 +1598,15 @@ bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2) { // Overload of c_lexicographical_compare() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. -template <typename Sequence1, typename Sequence2, typename Compare> +template <typename Sequence1, typename Sequence2, typename LessThan> bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2, - Compare&& comp) { + LessThan&& comp) { return std::lexicographical_compare( container_algorithm_internal::c_begin(sequence1), container_algorithm_internal::c_end(sequence1), container_algorithm_internal::c_begin(sequence2), container_algorithm_internal::c_end(sequence2), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_next_permutation() @@ -1575,11 +1622,11 @@ bool c_next_permutation(C& c) { // Overload of c_next_permutation() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. -template <typename C, typename Compare> -bool c_next_permutation(C& c, Compare&& comp) { +template <typename C, typename LessThan> +bool c_next_permutation(C& c, LessThan&& comp) { return std::next_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } // c_prev_permutation() @@ -1595,11 +1642,11 @@ bool c_prev_permutation(C& c) { // Overload of c_prev_permutation() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. -template <typename C, typename Compare> -bool c_prev_permutation(C& c, Compare&& comp) { +template <typename C, typename LessThan> +bool c_prev_permutation(C& c, LessThan&& comp) { return std::prev_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward<Compare>(comp)); + std::forward<LessThan>(comp)); } //------------------------------------------------------------------------------ diff --git a/third_party/abseil-cpp/absl/algorithm/container_test.cc b/third_party/abseil-cpp/absl/algorithm/container_test.cc index 0a4abe9462..605afc8040 100644 --- a/third_party/abseil-cpp/absl/algorithm/container_test.cc +++ b/third_party/abseil-cpp/absl/algorithm/container_test.cc @@ -57,9 +57,7 @@ class NonMutatingTest : public testing::Test { }; struct AccumulateCalls { - void operator()(int value) { - calls.push_back(value); - } + void operator()(int value) { calls.push_back(value); } std::vector<int> calls; }; @@ -68,7 +66,6 @@ bool BinPredicate(int v1, int v2) { return v1 < v2; } bool Equals(int v1, int v2) { return v1 == v2; } bool IsOdd(int x) { return x % 2 != 0; } - TEST_F(NonMutatingTest, Distance) { EXPECT_EQ(container_.size(), absl::c_distance(container_)); EXPECT_EQ(sequence_.size(), absl::c_distance(sequence_)); @@ -151,13 +148,90 @@ TEST_F(NonMutatingTest, CountIf) { } TEST_F(NonMutatingTest, Mismatch) { - absl::c_mismatch(container_, sequence_); - absl::c_mismatch(sequence_, container_); + // Testing necessary as absl::c_mismatch executes logic. + { + auto result = absl::c_mismatch(vector_, sequence_); + EXPECT_EQ(result.first, vector_.end()); + EXPECT_EQ(result.second, sequence_.end()); + } + { + auto result = absl::c_mismatch(sequence_, vector_); + EXPECT_EQ(result.first, sequence_.end()); + EXPECT_EQ(result.second, vector_.end()); + } + + sequence_.back() = 5; + { + auto result = absl::c_mismatch(vector_, sequence_); + EXPECT_EQ(result.first, std::prev(vector_.end())); + EXPECT_EQ(result.second, std::prev(sequence_.end())); + } + { + auto result = absl::c_mismatch(sequence_, vector_); + EXPECT_EQ(result.first, std::prev(sequence_.end())); + EXPECT_EQ(result.second, std::prev(vector_.end())); + } + + sequence_.pop_back(); + { + auto result = absl::c_mismatch(vector_, sequence_); + EXPECT_EQ(result.first, std::prev(vector_.end())); + EXPECT_EQ(result.second, sequence_.end()); + } + { + auto result = absl::c_mismatch(sequence_, vector_); + EXPECT_EQ(result.first, sequence_.end()); + EXPECT_EQ(result.second, std::prev(vector_.end())); + } + { + struct NoNotEquals { + constexpr bool operator==(NoNotEquals) const { return true; } + constexpr bool operator!=(NoNotEquals) const = delete; + }; + std::vector<NoNotEquals> first; + std::list<NoNotEquals> second; + + // Check this still compiles. + absl::c_mismatch(first, second); + } } TEST_F(NonMutatingTest, MismatchWithPredicate) { - absl::c_mismatch(container_, sequence_, BinPredicate); - absl::c_mismatch(sequence_, container_, BinPredicate); + // Testing necessary as absl::c_mismatch executes logic. + { + auto result = absl::c_mismatch(vector_, sequence_, BinPredicate); + EXPECT_EQ(result.first, vector_.begin()); + EXPECT_EQ(result.second, sequence_.begin()); + } + { + auto result = absl::c_mismatch(sequence_, vector_, BinPredicate); + EXPECT_EQ(result.first, sequence_.begin()); + EXPECT_EQ(result.second, vector_.begin()); + } + + sequence_.front() = 0; + { + auto result = absl::c_mismatch(vector_, sequence_, BinPredicate); + EXPECT_EQ(result.first, vector_.begin()); + EXPECT_EQ(result.second, sequence_.begin()); + } + { + auto result = absl::c_mismatch(sequence_, vector_, BinPredicate); + EXPECT_EQ(result.first, std::next(sequence_.begin())); + EXPECT_EQ(result.second, std::next(vector_.begin())); + } + + sequence_.clear(); + { + auto result = absl::c_mismatch(vector_, sequence_, BinPredicate); + EXPECT_EQ(result.first, vector_.begin()); + EXPECT_EQ(result.second, sequence_.end()); + } + { + auto result = absl::c_mismatch(sequence_, vector_, BinPredicate); + EXPECT_EQ(result.first, sequence_.end()); + EXPECT_EQ(result.second, vector_.begin()); + } } TEST_F(NonMutatingTest, Equal) { @@ -519,11 +593,9 @@ TEST_F(SortingTest, IsSortedUntil) { TEST_F(SortingTest, NthElement) { std::vector<int> unsorted = {2, 4, 1, 3}; absl::c_nth_element(unsorted, unsorted.begin() + 2); - EXPECT_THAT(unsorted, - ElementsAre(Lt(3), Lt(3), 3, Gt(3))); + EXPECT_THAT(unsorted, ElementsAre(Lt(3), Lt(3), 3, Gt(3))); absl::c_nth_element(unsorted, unsorted.begin() + 2, std::greater<int>()); - EXPECT_THAT(unsorted, - ElementsAre(Gt(2), Gt(2), 2, Lt(2))); + EXPECT_THAT(unsorted, ElementsAre(Gt(2), Gt(2), 2, Lt(2))); } TEST(MutatingTest, IsPartitioned) { @@ -676,6 +748,15 @@ TEST(MutatingTest, SwapRanges) { absl::c_swap_ranges(odds, evens); EXPECT_THAT(odds, ElementsAre(1, 3, 5)); EXPECT_THAT(evens, ElementsAre(2, 4, 6)); + + odds.pop_back(); + absl::c_swap_ranges(odds, evens); + EXPECT_THAT(odds, ElementsAre(2, 4)); + EXPECT_THAT(evens, ElementsAre(1, 3, 6)); + + absl::c_swap_ranges(evens, odds); + EXPECT_THAT(odds, ElementsAre(1, 3)); + EXPECT_THAT(evens, ElementsAre(2, 4, 6)); } TEST_F(NonMutatingTest, Transform) { @@ -690,6 +771,20 @@ TEST_F(NonMutatingTest, Transform) { EXPECT_EQ(std::vector<int>({1, 5, 4}), z); *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); + + 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, Replace) { @@ -755,10 +850,9 @@ MATCHER_P2(IsElement, key, value, "") { TEST(MutatingTest, StableSort) { std::vector<Element> test_vector = {{1, 1}, {2, 1}, {2, 0}, {1, 0}, {2, 2}}; absl::c_stable_sort(test_vector); - EXPECT_THAT( - test_vector, - ElementsAre(IsElement(1, 1), IsElement(1, 0), IsElement(2, 1), - IsElement(2, 0), IsElement(2, 2))); + EXPECT_THAT(test_vector, + ElementsAre(IsElement(1, 1), IsElement(1, 0), IsElement(2, 1), + IsElement(2, 0), IsElement(2, 2))); } TEST(MutatingTest, StableSortWithPredicate) { @@ -766,10 +860,9 @@ TEST(MutatingTest, StableSortWithPredicate) { absl::c_stable_sort(test_vector, [](const Element& e1, const Element& e2) { return e2 < e1; }); - EXPECT_THAT( - test_vector, - ElementsAre(IsElement(2, 1), IsElement(2, 0), IsElement(2, 2), - IsElement(1, 1), IsElement(1, 0))); + EXPECT_THAT(test_vector, + ElementsAre(IsElement(2, 1), IsElement(2, 0), IsElement(2, 2), + IsElement(1, 1), IsElement(1, 0))); } TEST(MutatingTest, ReplaceCopyIf) { |