下面是我可能實作的演算法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;
}
我的代碼除了使用std::distance，traits之外，看起來和STL的代碼一樣。因此，它檢查了輸入序列，并回傳一個迭代器到序列中最后一個元素，對該元素來說，謂詞是成功的。換句話說，回傳的迭代器表示一個不滿足謂詞的元素。
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() << '
'。
輸出：
6 at index: 7
這是好的。然而，為什么我不直接使用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() << '
'/span>。
輸出：
6 at index: 7
uj5u.com熱心網友回復：
std::find_if_not具有O(N)復雜度，因為它做了一個線性遍歷。 std::partition_point則具有O(logN)的復雜性，因為它利用了集合被分割的事實，并進行二進制搜索來尋找元素。 根據不同的情況，這可能是一個很大的性能優勢。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/326070.html
標籤：