了解下限/上限接口

Question

我无法理解下限/上限接口的语义。

考虑我写的这个测试片段：

#include <algorithm>
#include <iostream>
#include <vector>

int main() {

  // sorted vector
  std::vector<std::pair<size_t, std::vector<int>>> v = {
      std::make_pair(0, std::vector<int>()),
      std::make_pair(0, std::vector<int>()),
      std::make_pair(3, std::vector<int>()),
      std::make_pair(3, std::vector<int>()),
      std::make_pair(5, std::vector<int>()),
      std::make_pair(20, std::vector<int>())};

  auto key = 3;
  auto itr = std::lower_bound(
      v.begin(), v.end(), key,
      [](const auto &t1, const size_t d) -> bool { return t1.first < d; });

  std::cout << itr->first << "\n";
}

为什么我不需要两个矢量元素？为什么我只需要 key 类型的一个和第二个参数 (d)？ d 到底是什么？文档听起来像是一个转换为 key 类型的矢量元素。但是为什么不接受另一个向量元素作为第二个参数呢？为什么不与 key 进行比较？

为什么界面不是这样的：

auto itr = std::lower_bound(v.begin(), v.end(), 3, [](const auto& t1, const
  auto& t2) -> bool {return t1.first < t2.first;});

您能解释一下参数背后的语义吗，尤其是 d？

Answer 1

下限保证它仅通过 key 作为右手参数。

它进行二分查找，寻找comp(e,key)由true变为false的地方。如果 comp(e,key) 在特定元素 e 处为真，则搜索后面的元素，如果为假则搜索前面的元素，直到找到元素 "kess than" 之间的 "edge"键和元素 "greater than" 键。它通过二进制搜索来做到这一点：首先是迭代器范围的中间，然后是它接下来要搜索的范围的中间，递归地。

然后 returns 到最早元素 e 的迭代器，使得 !comp(e,key) 为真。

只有当所有元素 e 使得 comp(e,key) 都在列表的开头时才有效。

Answer 2

lower_bound 的第 4 个参数是 < 在容器中的元素和你的 key[=39] 之间的定义=].

auto itr = std::lower_bound(v.begin(), v.end(), 3, [](const auto& t1, const auto& t2) -> bool {return t1.first < t2.first;});

这样，lower_bound只知道数组中元素（即{int, vector<int>}）之间的<关系，而不知道之间的关系元素 和键。因此 lower_bound 找不到密钥，因为它不知道要比较的规则！

d这里传为key，即每次都是3进行比较。等于

auto it = std::lower_bound( v.begin(), v.end(), key, [key](const auto &t1, const size_t whatever) -> bool { return t1.first < key; } );

查看来自 cplusplus.com 的代码的更多信息。

http://www.cplusplus.com/reference/algorithm/lower_bound/

了解下限/上限接口

understanding the lower bound/ upper bound interface

c++

interface

lower-bound