c++ - 针对结束迭代器测试 lower_bound 的返回值

Question

在 Scott Meyers 的有效 STL 中（第 195 页）有以下行：

“必须测试 lower_bound 的结果以查看它是否指向您要查找的值。与 find 不同，您不能仅针对 end 迭代器测试 lower_bound 的返回值。”

谁能解释为什么你不能这样做？似乎对我来说很好。

Answer 1

它对您来说很好，因为您的元素存在。

lower_bound返回不小于给定值的第一个元素的迭代器，并upper_bound返回大于给定值的第一个元素的迭代器。

给定数组1, 2, 3, 3, 4, 6, 7，lower_bound(..., 5)将返回一个指向 6 的迭代器。

因此，有两种检查值是否存在的方法：

• 也equal_range可以用来获取upper_bound（单独计算lower_bound，upper_bound可能不是最理想的）。如果std::distance边界之间的值大于 0，则元素存在。

  1, 2, 3, 3, 4, 6, 7
  std::distance(std::lower_bound(v.begin(),v.end(),5), std::upper_bound(v.begin(),v.end(),5)) == 0 // 6 is absent
  std::distance(std::lower_bound(v.begin(),v.end(),3), std::upper_bound(v.begin(),v.end(),3)) == 2 // 3 is present
  

• 将迭代器指向的元素与您的值进行比较（提供运算符!=并且<是连贯的），但您必须确保它不会返回结束迭代器。

  *(std::lower_bound(v.begin(), v.end(), 5)) != 5
  

此外，由于是二进制搜索算法，因此如果未找到元素，则lower_bound返回不一致。end实际上，该算法返回的迭代器可以用作例如后续插入操作的提示。