c++ - vector 对上 lower_bound 的实现

Question

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

但不能写这个。

例如:

vector 的元素={(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

对 ( just like tuples ) 无论如何按字典顺序 进行比较。您不需要为此定义任何特殊的比较器。

并且由于您使用的是 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 的“从末尾计数”索引的语法)，否则最好让您的索引保持无符号。