向量对上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();