std::lower_bound on std::vector with reverse iterators yields a wrong result

Question

Recently I have came across a need to count elements that are outside of a given interval.

For example, if I have a sorted vector { 10, 20, 30 } and another sorted vector { 15, 25 }, whose boundaries define the interval. I want to count '10' and '30' (only 20 is inside the range). For this I use std::vector and std::lower_bound, once forward-scanning the vector, and once backward-scanning.

The code looks as following:

    int t[] = { 15, 25 };
int c[] = { 10, 20, 30 };

std::vector<int> tt(t, t + 2);
std::vector<int> cc(c, c + 3);

auto lower = std::lower_bound(cc.begin(), cc.end(), tt.front(), [](int a, int b){ return a < b; });
auto upper = std::lower_bound(cc.rbegin(), cc.rend(), tt.back(), [](int a, int b){ return a > b; });

size_t beforeCount = lower - cc.begin();
size_t afterCount = upper - cc.rbegin();

I expect both 'lower' and 'upper' to point to the same element: 20.

I've spent some time on this, does anyone see a problem here? I really want to use STL for that.

Thank you, Alex

Answer 1

I think that you are confused between the difference of an iterator, and the value pointed-to by an iterator.

Your program is doing exactly what you think, see it here.

beforeCount and afterCount are both equal to 1. They are iterators, not the value of any of your vector element, they are merely pointer to values in your vector.

To print the corresponding elements, simply do :

std::cout << cc[beforeCount] << std::endl;
std::cout << cc[afterCount] << std::endl;

Output:

20

20

Note:

You can initialize your vector without the intermediate arrays:

std::vector<int> tt { 15, 25 };
std::vector<int> cc  { 10, 20, 30 } ;