CODEWITHSUNDEEP
c++
Dave Mendoza
Dave Mendoza

Reputation: 61

How does upper_bound() work if only a less-than comparator is defined?

I was given a class that is built on top of a map with the following K type and V type limitations:

Given that limitation, wouldn't this code not work?

auto it = map.upper_bound(K);

Since upper_bound() (as defined here) returns an iterator pointing to the first element that is greater than key. Meaning the K would use a greater-than comparator?

Or does it follow that a definition of a less-than comparator would also define a greater-than comparator?

Or is my understanding of how upper_bound() works wrong?

Upvotes: 3

Views: 351

Answers (2)

Chee Loong Soon
Chee Loong Soon

Reputation: 3727

Great question, I had a similar confusion. I realize it just swaps the left hand side and right hand side of the operator.

Let elementToSearch be the element you're searching for and elementInSortedList be an element in the sorted list of elements.

With just the less than operator defined,

lower_bound returns the first element that is NOT(elementToSearch < elementInSortedList). Hence, it will return the first element in the sorted list that is >= elementToSearch

upper_bound returns the first element that is (elementToSearch < elementInSortedList). Hence, it will return the first element in the sorted list that is strictly > elementToSearch.

Upvotes: 0

Dave Mendoza
Dave Mendoza

Reputation: 61

As commented by @Nate Eldredge:

I believe you would get the first element y such that key < y. That's what "greater than" means in this context. Not the first y such that y > key

and from C++ documentation of upper_bound():

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
 ForwardIterator it;
 iterator_traits<ForwardIterator>::difference_type count, step;
 count = std::distance(first,last);
 while (count>0)
{
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

upper_bound() uses a < operator for comparison or to be more specific this:!(val<*it)

Upvotes: 2

Related Questions