时间戳

首页 > 解决方案 > 为什么我们需要 std::partition_point 而我们可以使用 std::find_if_not 算法？

c++ - 为什么我们需要 std::partition_point 而我们可以使用 std::find_if_not 算法？

问题描述

这是我可能的算法实现std::partition_point是：

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;
}

我的代码看起来像 STL，除了使用std::distance, traits... 所以它检查输入序列并返回一个迭代器到谓词成功的序列中的最后一个元素。换句话说，返回的迭代器表示一个不满足谓词的元素。

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';
}

没关系。但是为什么我不直接使用std::find_if_not它将迭代器返回到谓词为假的第一个元素？

 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';

输出：

  6 at index: 7

标签： c++algorithm

解决方案

std::find_if_not具有O(N)复杂性，因为它进行线性遍历。 std::partition_point另一方面具有O(logN)复杂性，因为它利用了集合被分区并进行二进制搜索以找到元素的事实。根据情况，这可能是一个巨大的性能胜利。

推荐阅读