Why we need std::partition_point whereas we can use std::find_if

Here is my possible implementation of the algorithm std::partition_point is :

template <typename In_It, typename FUNC>
In_It partitionPoint(In_It b, In_It e, FUNC pred){
    int len = e - b;

    while (len > 0){
        int half = len >> 1;
        In_It middle = b   half;
        if( pred(*middle) ){
            b = middle;
              b;
            len = len - half - 1;
        }
        else
            len = half;
    }
      return b;
}

My code looks like the STL one apart from using std::distance, traits... So it examines the input sequence and returns an iterator to the past-last element in the sequence for which the predicate succeeds. In other words the returned iterator denotes an element that doesn't satisfy the predicate.

int main(){
    std::vector<int> v{1, 3, 5, 7, 9, 1, 3, 6, 8, 10, 12};
    auto it = partitionPoint(v.begin(), v.end(), [](int x){return x % 2; });

    if( it != v.cend() )
        std::cout << *it << " " << it - v.cbegin() << '\n';
}

The output:
```
6 at index: 7
```

It is OK. however why I don't use directly std::find_if_not which returns an iterator to the first element for which the predicate is false?

 auto it2 = findIfNot(v.cbegin(), v.cend(), [](int x){return x % 2; });
 if(it2 != v.cend())
    std::cout << *it2 << " at index: " << it2 - v.cbegin() << '\n';

The output:

  6 at index: 7

CodePudding user response：

std::find_if_not has O(N) complexity as it does a linear traversal. std::partition_point on the other hand has O(logN) complexity as it takes advantage the fact that the set is partitioned and does a binary search to find the element. Depending on the situation, this could be a big performance win.