c++ - 如何在排序 vector 中找到下界

Question

我是 C++ 的新手，不了解 STL 库的所有概念，所以请多多包涵。我编写了以下代码片段(粘贴在下面)以在排序的 vector 中找到 lower_bound。尽管此代码在 Release模式下运行良好，但它在 Debug模式下断言 (VStudio-8)。我相信这是因为 less_equal<int>不是严格的弱排序。

来自以下线程:stl ordering - strict weak ordering

我有点理解 STL 强加了弱排序，但我还是不太清楚为什么？

在我下面的例子中，我需要使用 less_equal<int>因为我试图在排序 vector 中找到最接近给定值的元素。

下面的代码片段是否有效？另外，有没有更好的方法呢？此外，任何关于弱点和偏序的见解/引用都会有所帮助。

int main() {

  vector<int> dest;
  for(int i = 0;i <6;i++) {

     dest.push_back(i);
  }

  vector<int>::iterator i = 
  std::lower_bound(dest.begin(),dest.end(),4,less_equal< int >());

  return 1;

}

Answer 1

STL 使用严格的弱排序，因为给定一个 SWE(我们将其表示为 < )，您可以定义所有六个关系运算符:

x <  y      iff     x <  y
x <= y      iff   !(y <  x)
x == y      iff   !(x <  y || y <  x)
x != y      iff    (x <  y || y <  x)
x >= y      iff   !(x <  y)
x >  y      iff     y <  x

至于你要解决的问题，如果你希望值尽可能接近目标值，你真的不需要使用less_equal这里。相反，使用 lower_bound获取比您要查找的值大的最小元素的迭代器(使用默认的 < 整数比较)，然后将该值与它之前的值进行比较(当然，假设这两个值都存在! ) 来自 lower_bound 的值是与 x 一样大的最小元素，而该值之前的元素是不大于 x 的最大值，因此两者之一必须是最接近的。

至于为什么程序断言，很可能是因为<=不是严格的弱排序，但我不能确定。除非问题来自其他来源，否则更改为使用上述方法应该可以解决问题。