检查pair的一个值后，对pair的向量执行lower_bound
我在C++中有一个vector< pair< string,int> >对的向量，我想对字符串值执行lower_bound操作，但附加了一个约束条件，即pair的第二个值应该小于或等于给定值。目前，我正在使用比较模板进行比较
bool compare(const T &a,const T &b){
if (a.first<=b.first&&b.second<=a.second) return true;
}但它不能正常工作。向量根据pair的第一个值进行排序。示例->向量包含以下内容：
abcd,1
abcde,4
abcdex,3
abce,2我想在abc,3上使用lower_bound，所以它应该返回abcd,1，但它返回的是abcdex,3.Please帮助。
回答 1
Stack Overflow用户
发布于 2018-06-09 15:34:43
std::lower_bound属于binary search算法家族，第一个版本使用operator<比较元素，第二个版本使用comp比较元素。范围中的元素应该已经根据相同的标准 (operator<或comp)进行了排序，或者至少相对于val进行了分区。
这意味着，您需要首先按照您在前面提到的方式对向量进行排序，以便按照预期执行std::lower_bound。
一旦你以这种方式对数组的向量进行了排序，你就可以使用compare functor/ (我把它做成了一个λ)，你可以使用std::lower_bound了。
#include <vector>
#include <iostream>
#include <algorithm>
int main()
{
using Pair = std::pair< std::string, int> ;
std::vector< Pair > vec =
{
{"abcd", 1},
{"abcde", 4},
{"abcdex", 3},
{"abce", 2}
};
// define the compare lambda/ functor accordingly
auto compare = [](const Pair &lhs, const Pair &rhs)->bool
{ return (rhs.second > lhs.second) ? false: lhs.first <= rhs.first; };
// sorted the vector according to the custom compare
std::sort(vec.begin(), vec.end(), compare);
auto getLower = std::lower_bound(vec.begin(), vec.end(), Pair("abc",3), compare);
if(getLower != vec.cend()) std::cout << getLower->first << " " << getLower->second;
return 0;
}输出：
abcd 1注：为了使用std::lower_bound，你需要首先根据你想要应用下限的方式对你的向量进行排序(这是基本的)。
但是，在您的排序模式中，std::lower_bound不知道该数组是否正确排序的第二个值(int)。换句话说，即使您对前面提到的内容进行了相应的排序，std::lower_bound也不能给您提供所需的结果，因为您以Pair.first和Pair.second相反的顺序对Pair进行了排序。
因此，我建议您使用std::find_if，它将线性搜索元素，并且必须使用与谓词相同的比较函数。如果事先对向量进行了相应的排序(如您所提到的)，那么它应该会给出一个正确的结果。
// sort before
checkPair = Pair("abc",3);
auto getLower = std::find_if( vec.begin(), vec.end(), [&checkPair](const Pair &ele) -> bool
{
if(currPair == ele ) return true;
return (checkPair.first >= ele.first //--> "whose value is greater than or equal to the given string
&& ele.second < checkPair.second); //--> second value is less than a number
});
(getLower != vec.cend()) ?
std::cout << getLower->first << " " << getLower->second:
std::cout << "Nothing found";https://stackoverflow.com/questions/50771818
复制相似问题