C++ – lower_bound == upper_bound

cmathnaming-conventionsstl

What does lower_bound mean. If I had to guess I would answer that this function returns the iterator at the last element that is less than the value asked for. But I see that lower_bound is almost the same as upper_bound. The only difference is strict inequality in the case of upper_bound. Is there a true lower bound selection function in stl that agrees with the normal definition of lower bound.

EDIT: It was too many negations in the docs which made me confused. The problem was that I got the same iterator. I solved it by subtracting 1 from lower_bound return value. I use it for interpolation:

    float operator()(double f)
        {
        SpectrumPoint* l=std::lower_bound(beginGet(),endGet(),(SpectrumPoint){float(f),0.0f}
            ,SpectrumPoint::CompareFreqLessThan);
        if(l>beginGet())
            {--l;}

        SpectrumPoint* u=std::lower_bound(beginGet(),endGet(),(SpectrumPoint){float(f),0.0f}
            ,SpectrumPoint::CompareFreqLessThan);

        if(u==endGet())
            {u=beginGet();}

        if(l==u)
            {
            if(u==endGet())
                {return u->amp;}
            return l->amp;
            }

        double f_min=l->freq;
        double A_min=l->amp;
        double f_max=u->freq;
        double A_max=u->amp;

        double delta_f=f_max-f_min;
        double delta_A=A_max-A_min;

        return A_min + delta_A*(f-f_min)/delta_f;
        }

I am sorry for this confusion 🙁

Best Answer

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);
}

Related Solutions

C++ – Returning the greatest key strictly less than the given key in a C++ Map

Yeah, lower_bound can be used for that, i've seen it before and used it like that.

map_type::iterator it = map.lower_bound(2.3);
if(it != map.begin()) {
    --it;
    // it now points at the right element
}

Would actually return the greatest, yet smaller (if it != map.begin() was true) one. If it was at .begin, then there is no smaller key. Nice idea from the comments is to return .end if there is no element that's less and pack this stuff into a function:

template<typename Map> typename Map::const_iterator 
greatest_less(Map const& m, typename Map::key_type const& k) {
    typename Map::const_iterator it = m.lower_bound(k);
    if(it != m.begin()) {
        return --it;
    }
    return m.end();
}

template<typename Map> typename Map::iterator 
greatest_less(Map & m, typename Map::key_type const& k) {
    typename Map::iterator it = m.lower_bound(k);
    if(it != m.begin()) {
        return --it;
    }
    return m.end();
}

The template should work for std::set too.

C++ – How to use lower_bound to insert value into sorted vector

From your example, you're using a vector of pointers: std::vector<A*>. Hence, you need to define a comparison for pointers which you pass in to std::lower_bound:

bool less_A_pointer (const A* lhs, const A* rhs)
{
    return (lhs->key < rhs->key);
}

auto it = std::lower_bound(vec.begin(), vec.end(), element, less_A_pointer);
//...

Of course, the question is why are you using pointers in the first place - just store A objects unless you really need to. If you do need to store pointers, look into std::shared_ptr which will handle this for you:

std::vector<std::shared_ptr<A>> v;
std::shared_ptr<A> element(new A(...));
auto it = std::lower_bound(v.begin(), v.end(), element); //Will work properly

You can also use a lambda instead of having to write a free function:

auto it = std::lower_bound(v.begin(), v.end(), 
                          [](const A* lhs, const A* rhs)
                          { return lhs->key < rhs->key; });

Best Answer

Related Solutions

C++ – Returning the greatest key strictly less than the given key in a C++ Map

C++ – How to use lower_bound to insert value into sorted vector

Related Topic