How to find a lower bound in a sorted vector

Question

I'm pretty new to C++ and do not understand all the concepts of the STL library, so bear with me. I wrote the following code snippet (pasted below) to find the lower_bound in a sorted vector. Although this code works fine in Release mode, it asserts in debug mode (VStudio-8). I believe this is because less_equal<int> is not a strictly weak ordering .

From the following thread: stl ordering - strict weak ordering

I do sort of understand that a weak ordering is imposed by the STL, but I'm still not very clear why?

In my case below I need to use less_equal<int> since I'm trying to find the nearest element to a given value in a sorted vector.

Is the code snippet below even valid? Also, is there a better way to do it? Also any insights/references to what exactly is weak and partial ordering would be helpful.

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;

}

score 9 · Accepted Answer · answered Feb 09 '11 at 02:53

The STL uses strict weak orderings because given a SWE (let's denote it <), you can define all six of the relational operators:

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

As for the problem you're trying to solve, if you want the value as close as possible to the target value, you really don't need to use less_equal here. Rather, use lower_bound to get an iterator to the smallest element bigger than the value you're looking for (using the default < comparison on integers), then compare that value to the value before it (assuming, of course, that both these values exist!) The value from lower_bound is the smallest element as least as large as x and the element before that value is the largest value no greater than x, so one of the two must be the closest.

As for why the program was asserting, it's quite possible that it's due to the fact that <= is not a strict weak ordering, but I can't be certain about that. Changing to using the above approach should fix it unless the problem is from some other source.

thanks it makes more sense to me now and as you mentioned there is no good reason for me to stick to less_equal:) — keety, Feb 09 '11 at 05:48

How to find a lower bound in a sorted vector

1 Answers1