理解下界/上限界面

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";
}

为什么我不需要两个向量元素？为什么我只需要一个和第二个参数(d)的类型的key？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

lower_bound的第四个参数是容器中的元素和键之间的元素之间的定义。

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>})，而不知道元素和key之间的关系。因此，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的代码。

1. 装订/

Answer 2

下限保证它只将key作为右手参数传递。

它进行二进制搜索，查找comp(e,key)从true到false的位置。如果在特定元素comp(e,key)为真，则搜索后一个元素(如果为前面的元素为false )，直到找到元素之间的“边缘”(kess大于“e )和元素之间的”边缘“大于”键“。它通过二进制搜索来实现这一点:首先是迭代器范围的中间，然后是它想要搜索的范围的中间，然后是递归搜索。

然后，它将迭代器返回到最早的元素e，从而使!comp(e,key)为真。

只有当所有元素e都位于列表的开头时，comp(e,key)才能工作。