向量递减/非递增时的下限和上限

Question

我理解递增/递增数组的Lower和Upper的概念。即

1. 下界：迭代器指向范围[first，last(>=值中的第一个元素
2. 上限：迭代器指向范围[first，last(>Value中的第一个元素

下面是我面临问题的递减/非递增矢量的代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> vec = {45,40,35,12,6,3};
auto itr3 = lower_bound(vec.begin(),vec.end(),40);
auto itr4 = upper_bound(vec.begin(),vec.end(),40);
if(itr3 == vec.end() && itr4 == vec.end())
cout<<"Lower & Upper Bound not Foundn";
else
{
cout <<"lower Bound of 40 :"<<*itr3<<endl;
cout <<"Upper Bound of 40 :"<<*itr4<<endl;
}
return 0;
}

输出为：

Lower & Upper Bound not Found.

但如上所述，输出应该类似于：

lower Bound of 40 :40
Upper Bound of 40 :45

请帮助我理解他在向量递减/非递增的情况下的下界和上界行为。

Answer 1

您可以使用反向迭代器来获得40/45结果：

#include <algorithm>
#include <cstdio>
#include <vector>
int main() {
std::vector<int> const vec = { 45, 40, 35, 12, 6, 3 };
auto const it_lb = std::lower_bound(vec.rbegin(), vec.rend(), 40);
auto const it_ub = std::upper_bound(vec.rbegin(), vec.rend(), 40);
std::printf("Lower: %dnUpper: %dn", *it_lb, *it_ub);
}

Answer 2

std::lower_bound和std::upper_bound的目标必须是递增(非递减(的顺序。

您可以更改"；增加"；通过用函数的第4个自变量指定比较器。

可以使用std::greater来处理降序向量。

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
int main()
{
vector<int> vec = {45,40,35,12,6,3};
auto itr3 = lower_bound(vec.begin(),vec.end(),40,std::greater<int>());
auto itr4 = upper_bound(vec.begin(),vec.end(),40,std::greater<int>());
if(itr3 == vec.end() && itr4 == vec.end())
cout<<"Lower & Upper Bound not Foundn";
else
{
cout <<"lower Bound of 40 :"<<*itr3<<endl;
cout <<"Upper Bound of 40 :"<<*itr4<<endl;
}
return 0;
}

Answer 3

您需要将算法std::lower_bound和std::upper_bound的另一个重载声明与比较函数一起使用，例如标准函数对象std::greater。

这是一个示范节目。

#include <iostream>
#include <functional>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
std::vector<int> vec = { 45, 40, 35, 12, 6, 3 };

auto lower_bound = std::lower_bound( std::begin( vec ),
std::end( vec ),
40,
std::greater<int>() );
auto upper_bound = std::upper_bound( std::begin( vec ),
std::end( vec ),
40,
std::greater<int>() );

std::cout << *lower_bound << " <-> " << *upper_bound << 'n';

return 0;
}

程序输出为

40 <-> 35

为了简单起见，我没有检查程序中返回的迭代器是否等于std::end( vec )返回的迭代器。

您可以使用自己的lambda表达式来代替标准函数对象std::greater。例如

auto descending = []( const auto &x, const auto &y )
{
return y < x;
};

auto lower_bound = std::lower_bound( std::begin( vec ),
std::end( vec ),
40,
descending );
auto upper_bound = std::upper_bound( std::begin( vec ),
std::end( vec ),
40,
descending );