c++ - 了解下限/上限接口(interface)

Question

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

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

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

为什么我不需要两个 vector 元素？为什么我只需要 key 类型的一个和第二个参数 (d)？ d 到底是什么？文档听起来像是一个 vector 元素转换为 key 类型。但是为什么不接受另一个 vector 元素作为第二个参数呢？为什么不与 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 的第 4 个参数是 < 的定义在容器中的元素和您的键之间。

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找不到 key ，因为它不知道要比较的规则!

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. http://www.cplusplus.com/reference/algorithm/lower_bound/