c++ - 在向量对上实现 lower_bound

Question

我知道我们需要包含一些比较功能才能实现这一点。

但不能为这个写。

例如：

向量的元素={(2,4),(4,2),(5,1),(5,3)}

找到=5

lower_bound() 应该返回 2

代码->

#define pp pair<int,int>

bool cmp(const pp &l,const pp &r) {
    return l.first < r.first;
}

int main() {
   vector<pp> v;
   sort(v.begin(), v.end(), cmp);
   int id=(int)(lower_bound(v.begin(), v.end(), ??) - v.begin());
}

Answer 1

无论如何，对（就像元组一样）按字典顺序进行比较。您不需要为此定义任何特殊的比较器。

并且由于您正在使用lower_bound您将搜索不小于val您正在搜索的比较的第一个元素，因此您应该使用一个min值作为第二个对元素。总而言之，一切都可以在“两”行代码中完成：

sort(v.begin(),v.end());
auto id = distance(v.begin(), lower_bound(v.begin(),v.end(), 
       make_pair(5, numeric_limits<int>::min())) );

---

一些注意事项：

1. 用于std::distance计算两个迭代器之间的元素个数
2. 的返回类型std::distance是无符号类型。除非您需要负索引（类似于 Python 的“从末尾计数”索引的语法），否则保持索引无符号是一个好习惯。

Answer 2

由于您不关心 的第二个值pp，因此只需构造一个具有任何值的临时pp对象作为第二个元素。

int id = std::lower_bound(v.begin(), v.end(), pp(5, 0), cmp) - v.begin();

Answer 3

我认为您应该根据lower_bound So 的定义比较这些对，

   typedef pair<int,int> pp;
   //...

   int id=(int)(lower_bound(v.begin(),v.end(), 
                pp(5,std::numeric_limits<int>::min())), //Value to compare
                [](const pp& lhs, const pp& rhs)       // Lambda
                {
                    return lhs < rhs ;                //  first argument < second
                }
                 ) - v.begin()
               );

Answer 4

您可以在具有自定义比较运算符的对向量上使用 lower_bound。

在这种情况下，您需要像这样传递四个参数：-

• it1 = 搜索的迭代器位置

• it2 = 迭代器位置直到要搜索的位置

下界（it1，it2，finding_element，your_comparator）

auto myComp = [&](pair<int,string> e1, pair<int,string> e2) {
if(e1.second!=e2.second)
    return e1.second<e2.second;
else
    return e1.first<e2.first;
};
 
void Show_sample_code()
{
    vector<pair<int,string>> data={{1, "sahil"}, {2, "amin"}};
    sort(data.begin(), data.end(), myComp);
    pair<int, string> p={1,"sahil"};
    auto it=lower_bound( data.begin(), data.end(), p, myComp ) ;
    if(it!=data.end())
         cout<<"found at index="<<distance(data.begin(), it)<<endl;
    else
    cout<<"notfound"<<endl;
return;
}