Lower_Bound == Upper_Bound

lower_bound == upper_bound

• Lower bound: first element that is greater-or-equal.

• Upper bound: first element that is strictly greater.

Example:

+- lb(2) == ub(2)       +- lb(6)        +- lb(8)
|        == begin()     |  == ub(6)     |   +- ub(8) == end()
V                       V               V   V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
    ^               ^                       ^
    |               |                       |
    +- lb(4)        +- ub(4)                +- lb(9) == ub(9) == end()

    |- eq-range(4) -|

As you can see, the half-open equal-range for n is [lb(n), ub(n)).

Note that both bounds give you meaningful insertion locations for an element of the desired value so that the ordering is maintained, but lower_bound has the distinguishing feature that if the element already exists, then you get an iterator which actually points to that element. Thus you can use lower_bound on an ordered range to implement your own unique-membership or multiple-membership container.

void insert(Container & c, T const & t)
{
    auto it = std::lower_bound(c.begin(), c.end(), t);

    // if unique container:
    if (it != c.end() && *it == t) { /* error, element exists! */ return; }

    c.insert(it, t);
}

Naming of lower_bound, upper_bound c++

Igor Tandetnik answered this in the comments.

The set in question is the the elements which the given value can be inserted before while preserving the order.

For example if we want to insert 2 in to the range [0,1,2,2,3,4] then we could insert it at index 2, 3 or 4. lower_bound gives the iterator to the start of the range. upper_bound gives the last element in this range.

I suppose this is a name for library implementers writing pivots, rather than me trying to look up keys/indices of a vector of numerics.

lower_bound and upper_bound for after and before

lower_bound will return the first element that is greater than or equal to the search item. In this case that is element 6.0.

upper_bound will return the first element that is greater but not equal to the search item. In this case that is also element 6.0.

To get the element before the number you're searching for, you need to explicitly decrement the iterator returned from lower_bound. To prevent undefined behavior you will first need to make sure it isn't already at begin().

Think of lower_bound and upper_bound as returning the range of where that item would be placed in the sorted array. If the search item doesn't occur in the sequence, they will always return the same iterator.

lower_bound and upper_bound in Map of Pairs

You are storing this by key value in an ordered map. The ordering of the maps' keys will be as follows:

<2, 3> | <2, 5> | <5, 0> | <7, 1> | <9, 3> 

See here.

So, the actual std::map::upper_bound reference says the following:

iterator upper_bound( const Key& key );

Returns an iterator pointing to the first element that is greater than key.

From this it is easy to see, the first key in the list that is greater than <2, 2> is <2, 3> (for the call mp.upper_bound(std::make_pair(2, 2))).

std::set, how do lower_bound and upper_bound work?

From cppreference.com on std::set::lower_bound:

Return value

Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator (see end()) is returned.

In your case, since you have no elements in your set which is not less (i.e. greater or equal) than 11, a past-the-end iterator is returned and assigned to it_l. Then in your line:

std::cout << *it_l << " " << *it_u << std::endl;

You're deferencing this past-the-end iterator it_l: that's undefined behavior, and can result in anything (1 in your test, 0 or any other value with an other compiler, or the program may even crash).

Your lower bound should be less than, or equal to to the upper bound, and you should not dereference the iterators outside a loop or any other tested environment:

#include <iostream>
#include <set>

using std::set;

int main(int argc, char argv) {
   set<int> myset;
   set<int>::iterator it_l, it_u;
   myset.insert(9);
   myset.insert(10);
   myset.insert(11);
   it_l = myset.lower_bound(10);
   it_u = myset.upper_bound(10);

    while(it_l != it_u)
    {
        std::cout << *it_l << std::endl; // will only print 10
        it_l++;
    }
}

compare function for upper_bound / lower_bound

What function did you pass to the sort algorithm? You should be able to use the same one for upper_bound and lower_bound.

The easiest way to make the comparison work is to create a dummy object with the key field set to your search value. Then the comparison will always be between like objects.

Edit: If for some reason you can't obtain a dummy object with the proper comparison value, then you can create a comparison functor. The functor can provide three overloads for operator() :

struct MyClassLessThan
{
    bool operator() (const MyClass & left, const MyClass & right)
    {
        return left.key < right.key;
    }
    bool operator() (const MyClass & left, float right)
    {
        return left.key < right;
    }
    bool operator() (float left, const MyClass & right)
    {
        return left < right.key;
    }
};

As you can see, that's the long way to go about it.

lower bound upper bound giving same results

*a will be 4 in both cases, as the value pointed to by a would be 3.2 if that was inserted correctly into the container.

lower_bound and upper_bound will return the same iterator if the value passed is not present in the container, which is the case here.

The iterator returned by lower_bound is defined to be the lowest position where the element passed could reside it was in the container, higher_bound returns the highest position. They do not return anything related to the closest element present in the array.

In order to find the closest element, you know that the dereferenced result of lower_bound is greater than or equal to the value passed. The value before that, if any, must be less. You can make use of this in order to arrive at the closest value.

rationale for std::lower_bound and std::upper_bound?

If you have multiple elements in the range [first, last) whose value equals the value val you are searching for, then the range [l, u) where

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

is precisely the range of elements equal to val within the range [first, last). So l and u are the "lower bound" and "upper bound" for the equal range. It makes sense if you're accustomed to thinking in terms of half-open intervals.

(Note that std::equal_range will return both the lower and upper bound in a pair, in a single call.)

---

Related Topics