lower_bound()的一個未預期的執行行爲

前一陣,後輩問了我一個問題:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6};

    auto p = lower_bound(a.begin(), a.end(), 3, greater<int>());

    cout << *p << endl;

    return 0;
}

爲什麽這段代碼爲什麽執行結果爲0?

確實,從直觀思虑上來說,返回結果確實有些詭異。一時間我也不太理解。

我的第一反應是比較 pa.end()的位置關系,發現 p=a.end()。也就是說,函數並沒有在容器中找到比a大年夜的元素,這並分歧适預期的執行結果。

遇事不決翻文檔,因而我找到了這篇文┞仿。此中詳細介紹了 upper_bound函数的原型與定义,此中先容中的┞封句话解决了这个题目:

範圍 [first, last) 必须已相对表达式 !(value < element) 或 !comp(value, element) 划分,即所有令此表达式为 true 的元素必须前趋所有令此表达式为 false 的元素。完全排序的範圍满足此辨别标准。

除常提到的序列有序条件以外,lower_bound對重載的比較關系也有必然的要求,這也就導致了上例中 lower_bound函數分歧适預期的執行。

參考其給出了函數可能的實現:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first,last);
 
    while (count > 0) {
        it = first; 
        step = count / 2;
        std::advance(it, step);
        if (!comp(value, *it)) {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }
    return first;
}

也對應了介紹中的┞穎法,當采取上例的函數模版重載大年夜小關系,會使叠代器 it不竭向后迭代,直至與 a.end()重合。

所以,要使運行結果正確,可以對函數傳遞 a的反向叠代器 a.rbegin()a.rend()。即:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6};

    auto p = lower_bound(a.rbegin(), a.rend(), 3, greater<int>());

    cout << *p << endl;

    return 0;
}

或利用 reverse函數先對序列進行反轉,當然,這樣會造成性能損掉。

利用 Hugo 構建
主題 StackJimmy 設計
xxfseo.com