Bug#196380: libstdc++5-3.3-doc: lower_bound is not well documented

[Phil Edwards <phil@jaj.com>]

On Fri, Jun 06, 2003 at 11:30:30PM +0600, Victor Porton wrote:
> Returns:
>     An iterator pointing to the first element "not less than" val.
> ]]
> 
> "Returns" clause does not consider the case when there are no elements "not
> less than" val in the iterators range.

Well, if you think about it a bit, simple logic will suggest an answer.
Write down 5 numbers in order.  Pick a sixth number smaller than all of
the previous five.  Which position can the sixth number go in to maintain
the order?


> It is my guess that in the case of no elements "not less than" val the
> returned value is "last" because "last" is the iterator value where one can
> insert without changing the ordering when there are no elements "not less
> than" val.

You seem to be confused; "not less than" does not mean "less than".

    % cat foo.cc
    
    #include <vector>
    #include <algorithm>
    #include <iostream>
    
    int main()
    {
        std::vector<int>  foo;
        foo.push_back(11);
        foo.push_back(12);
        foo.push_back(13);
        foo.push_back(14);
        foo.push_back(15);
        foo.push_back(16);
        foo.push_back(17);
    
        std::vector<int>::iterator i;
        i = std::lower_bound(foo.begin(), foo.end(), 3);
        foo.insert(i, 3);
    
        for (i=foo.begin(); i<foo.end(); ++i)
            std::cout << (*i) << ' ';
        std::cout << std::endl;
    }
    
    % g++ foo.cc
    % ./a.out
    3 11 12 13 14 15 16 17
    %

The first element in 'foo' that is "not less than 3" is the initial position;
11 is not less than 3.  So begin() is returned.


> Also existing short description of std::lower_bound says that returned
> iterator is pointing to an element.

No it doesn't.  You quoted it yourself:

    Finds the first position in which val could be inserted without changing
    the ordering.

Let's say that the code above passed 500 instead of 3.  Every element
of foo is less than 500.  There are no elements "not less than" (i.e.,
greater than or equal to) 500.  So end() is returned.  Calling

    foo.insert( foo.end(), 500 );

is perfectly valid, and is the only place to insert 500 that would not
change the ordering.

However, the Returns clause does specify "an element," which is wrong.
So we will need to fix that wording.


-- 
If ye love wealth greater than liberty, the tranquility of servitude greater
than the animating contest for freedom, go home and leave us in peace.  We seek
not your counsel, nor your arms.  Crouch down and lick the hand that feeds you;
and may posterity forget that ye were our countrymen.            - Samuel Adams