测试lower_bound对结束迭代器的返回值

Question

在Scott Meyers(第195页)的有效STL中,有以下行:

"必须测试lower_bound的结果,看它是否指向你正在寻找的值.与find不同,你不能只测试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如果找不到该元素,则返回将是不一致的.实际上,此算法返回的迭代器可以用作后续插入操作的提示.