CODEWITHSUNDEEP
c++algorithm
CodersSC
CodersSC

Reputation: 710

Binary search with lower_bound function

I am using the lower_bound function so that an iterator is returned instead of a boolean.

auto testPair = make_pair(0, 0);
auto it3 = std::lower_bound(vec[1].begin(), vec[1].end(), testPair, [](const std::pair<int, double> a, const std::pair<int, double> b)
{
    return a.first < b.first;
});
if (it3 != vec[1].end() && !(testPair.first < it3->first))
    vec[1].erase(it3);

I basally took the original implementation and changed it so that it returns an iterator so that I can use pairs.

My question is on the following line:

if (it3 != vec[1].end() && !(testPair.first < it3->first))

My feeling is that the second logical statement could be removed because by using lower_bound it should mean that testPair.first should never be greater than it3->first. However if I remove that part of the if statement it does not work properly in some scenarios.

Could anyone insight me on why this is and why it is needed?

if i pass a pair of 

    auto testPair = make_pair(0, 0);

into a vector of pairs which hold the following

std::push_back(std::make_pair(1,1.6));
std::push_back(std::make_pair(2,1.7));

it will remove the second pair when it should not remove any.

Upvotes: 1

Views: 402

Answers (1)

Vlad from Moscow
Vlad from Moscow

Reputation: 310950

Algorithm std::lower_bound returns iterator before which the target value can be inserted in the sequence such a way that the sequence would be still ordered. This does not mean that the algorithm always returns iterator that points to an element with the same target value.

For example if you have a sequence like

{ 0, 2, 4, 6 }

and use the algorithm for value 3 then it will return the iterator that points to 4. The sequence does not have the element with value 3. So you should check yourself whether the iterator points to an element that has the same value.

For objects of type int as in your example you could write simply

if ( it3 != vec[1].end() && testPair.first == it3->first )
                                           ^^^

But in general (as for example when float numbers are used) it is better to use operator < because it is this operator is usually used to sort sequences. For example there is no need to declare operator == in your class to sort a sequence of objects of your class by means of operator < and then to use algorithm std::lower_bound to find the target element

In fact for your code snippet this statement

if (it3 != vec[1].end() && !(testPair.first < it3->first))

is equivalent to the above statement. testPair.first can not be greater than it3->first. At the same time if it is not less than it3->first then you may conclude that they are equal.

Upvotes: 2

Related Questions