Use const predicate operators in algorithms

[zoecarver]

Summary

This patch ensures that algorithms in libc++ use const overloads for predicate operators. It also adds a file called test_predicates.h which holds helpful testing predicates. See bug 34536 and LWG3031 for reference.

[jloser]

test/support/test_predicates.h

1

Nit: typo -- should be stateful.

[zoecarver]

Fix typo

[zoecarver]

Ping. I can split this into three patches if that would be better.

include/algorithm

 
 template <class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 {
     for (; __first != __last; ++__first)
-        if (!__pred(*__first))
+        if (!__pred(as_const(*__first)))
             return false;
     return true;
 }
 
 // any_of
 
 template <class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 {
     for (; __first != __last; ++__first)
-        if (__pred(*__first))
+        if (__pred(as_const(*__first)))
             return true;
     return false;
 }
 
 // none_of
 
 template <class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline

 
 template <class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _InputIterator
 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 {
     for (; __first != __last; ++__first)
-        if (__pred(*__first))
+        if (__pred(as_const(*__first)))
             break;
     return __first;
 }
 
 // find_if_not
 
 template<class _InputIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT inline

 _ForwardIterator
 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
 {
     if (__first != __last)
     {
         _ForwardIterator __i = __first;
         while (++__i != __last)
         {
-            if (__pred(*__first, *__i))
+            if (__pred(as_const(*__first), as_const(*__i)))
                 return __first;
             __first = __i;
         }
     }
     return __last;
 }
 
 template <class _ForwardIterator>

test/std/algorithms/alg.nonmodifying/alg.adjacent.find/adjacent_find_pred.pass.cpp

 //   adjacent_find(Iter first, Iter last, Pred pred);
 
 #include <algorithm>
 #include <functional>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
-
+#include "test_predicates.h"
 
 #if TEST_STD_VER > 17
 TEST_CONSTEXPR bool eq (int a, int b) { return a == b; }
 
 TEST_CONSTEXPR bool test_constexpr() {
     int ia[] = {0, 1, 2, 2, 0, 1, 2, 3};
     int ib[] = {0, 1, 2, 7, 0, 1, 2, 3};
 
assert(std::adjacent_find(forward_iterator<const int*>(ia),
                               forward_iterator<const int*>(ia),
                               std::equal_to<int>()) ==
                               forward_iterator<const int*>(ia));
     assert(std::adjacent_find(forward_iterator<const int*>(ia+3),
                               forward_iterator<const int*>(ia + sa),
                               std::equal_to<int>()) ==
                               forward_iterator<const int*>(ia+sa));
 
+    // Test that const overloads are used
+    std::adjacent_find(std::begin(ia),
+                       std::end(ia),
+                       force_const_predicate<int>());
+
 #if TEST_STD_VER > 17
     static_assert(test_constexpr());
 #endif
 
   return 0;
 }

test/std/algorithms/alg.nonmodifying/alg.all_of/all_of.pass.cpp

 //     constpexr bool       // constexpr after C++17
 //   all_of(InputIterator first, InputIterator last, Predicate pred);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "test_predicates.h"
 
 struct test1
 {
     TEST_CONSTEXPR bool operator()(const int& i) const
     {
         return i % 2 == 0;
     }
 };

 {
     {
         int ia[] = {2, 4, 6, 8};
         const unsigned sa = sizeof(ia)/sizeof(ia[0]);
         assert(std::all_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia + sa), test1()) == true);
         assert(std::all_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia), test1()) == true);
+
+        // Test that const overloads are used
+        std::all_of(std::begin(ia),
+                    std::end(ia),
+                    force_const_predicate<int>());
     }
     {
         const int ia[] = {2, 4, 5, 8};
         const unsigned sa = sizeof(ia)/sizeof(ia[0]);
         assert(std::all_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia + sa), test1()) == false);
         assert(std::all_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia), test1()) == true);
     }
 
 #if TEST_STD_VER > 17
     static_assert(test_constexpr());
 #endif
 
   return 0;
 }

test/std/algorithms/alg.nonmodifying/alg.any_of/any_of.pass.cpp

 //     constpexr bool       // constexpr after C++17
 //   any_of(InputIterator first, InputIterator last, Predicate pred);
 
 #include <algorithm>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "test_predicates.h"
 
 struct test1
 {
     TEST_CONSTEXPR bool operator()(const int& i) const
     {
         return i % 2 == 0;
     }
 };

 {
     {
         int ia[] = {2, 4, 6, 8};
         const unsigned sa = sizeof(ia)/sizeof(ia[0]);
         assert(std::any_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia + sa), test1()) == true);
         assert(std::any_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia), test1()) == false);
+        // Test that const overloads are used
+        std::any_of(std::begin(ia),
+                    std::end(ia),
+                    force_const_predicate<int>());
     }
     {
         const int ia[] = {2, 4, 5, 8};
         const unsigned sa = sizeof(ia)/sizeof(ia[0]);
         assert(std::any_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia + sa), test1()) == true);
         assert(std::any_of(input_iterator<const int*>(ia),
                            input_iterator<const int*>(ia), test1()) == false);

test/std/algorithms/alg.nonmodifying/alg.find/find_if.pass.cpp

 //   find_if(Iter first, Iter last, Pred pred);
 
 #include <algorithm>
 #include <functional>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "test_predicates.h"
 
 struct eq {
     TEST_CONSTEXPR eq (int val) : v(val) {}
     TEST_CONSTEXPR bool operator () (int v2) const { return v == v2; }
     int v;
     };
 
 #if TEST_STD_VER > 17
input_iterator<const int*> r = std::find_if(input_iterator<const int*>(ia),
                                                 input_iterator<const int*>(ia+s),
                                                 eq(3));
     assert(*r == 3);
     r = std::find_if(input_iterator<const int*>(ia),
                      input_iterator<const int*>(ia+s),
                      eq(10));
     assert(r == input_iterator<const int*>(ia+s));
 
+    // Test that const overloads are used
+    std::find_if(std::begin(ia),
+                 std::end(ia),
+                 force_const_predicate<int>());
+
 #if TEST_STD_VER > 17
     static_assert(test_constexpr());
 #endif
 
   return 0;
 }

test/support/test_predicates.h

+struct statefull_predicate
+{
+    statefull_predicate (int i) : i_(i) {};
+    ~statefull_predicate() { i_ = -32767; }
+    bool operator() (const statefull_predicate &p) const { return p.i_ == i_; }
+
+    bool operator==(int i) const { return i == i_;}
+    int i_;
+};
+
+template <typename T>
+struct force_const_predicate
+{
+    T value;
+    force_const_predicate(T value = 1) : value(value) {}
+
+    bool operator()(T&) { assert(false); return false; }
+    bool operator()(const T&p) const { return value == p; }
+    bool operator()(T&, T&) { assert(false); return false; }
+    bool operator()(const T&p0, const T&p1) const { return p0 == p1; }
+    bool operator==(T&) { assert(false); return false; }
+    bool operator==(const T&p) const { return value == p; }
+    bool operator!=(T&) { assert(false); return false; }
+    bool operator!=(const T&p) const { return value != p; }
+    bool operator< (T&) { assert(false); return false; }
+    bool operator< (const T&p) const { return value < p; }
+    bool operator> (T&) { assert(false); return false; }
+    bool operator> (const T&p) const { return value > p; }
+};
 No newline at end of file