[Bug libstdc++/64903] New: is_partitioned should not apply a predicate more than (last - first) times

[Bug libstdc++/64903] New: is_partitioned should not apply a predicate more than (last - first) times

[kariya_mitsuru at hotmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64903

            Bug ID: 64903
           Summary: is_partitioned should not apply a predicate more than
                    (last - first) times
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kariya_mitsuru at hotmail dot com

Created attachment 34645
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34645&action=edit
g++ -v

Please see the sample code below.

================================= sample code =================================
#include <iostream>
#include <algorithm>

int main()
{
    int v[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    int c = 0;
    std::cout << std::boolalpha
        << std::is_partitioned(v, v + 10, [&c](int x) { return ++c, (x & 1) !=
0; })
        << std::endl;
    std::cout << c << " times" << std::endl;
}
================================= sample code =================================

================================= output =================================
true
11 times
================================= output =================================

cf. http://melpon.org/wandbox/permlink/OHXgHtbgmm4Ak8pJ


The C++11 standard 25.3.13[alg.partitions]/p.3 says, "At most last - first
applications of pred."

So the sample code above should output

================================= output =================================
true
10 times
================================= output =================================

[Bug libstdc++/64903] is_partitioned should not apply a predicate more than (last - first) times

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64903

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-02-02
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I notice that libc++ has the same bug.

I think the problem is that we end up testing the partition point twice. Here's
a completely untested patch that avoids that:

--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -583,6 +583,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
                   _Predicate __pred)
     {
       __first = std::find_if_not(__first, __last, __pred);
+      if (__first == __last)
+       return true;
+      std::advance(__first, 1);
       return std::none_of(__first, __last, __pred);
     }