lower_bound == upper_bound

Question

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 :-(

Answer 1

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