C++ Codes
C++ > Visual C++ 5.0 Standard C++ Library sample source codes

The lower bound algorithm returns the first location in the sequence that value

The lower bound algorithm returns the first location in the sequence that value


lower_bound
	
 
Header
<algorithm>

template<class ForwardIterator, class T> inline 
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value)

The lower_bound algorithm returns the first location in the sequence that value can be inserted such that the order of the sequence is maintained. lower_bound returns an iterator positioned at the location that value can be inserted in the range [first..last), or returns last if no such position exists. lower_bound assumes the range [first..last) is sorted using operator<.

template<class ForwardIterator, class T, class Compare> inline 
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)

The lower_bound algorithm returns the first location in the sequence that value can be inserted such that the order of the sequence is maintained. lower_bound returns an iterator positioned at the location that value can be inserted in the range [first..last), or returns last if no such position exists. This version assumes the range [first..last) is sorted sequentially using the compare function.


Samples
Sample for Non-Predicate Version

// disable warning C4786: symbol greater than 255 character,
// okay to ignore this warning
#pragma warning(disable: 4786)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;


void main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of int
    typedef vector<int > IntVector ;

    //Define an iterator for template class vector of strings
    typedef IntVector::iterator IntVectorIt ;

    IntVector Numbers(VECTOR_SIZE) ;

    IntVectorIt start, end, it, location ;

    // Initialize vector Numbers
    Numbers[0] = 4 ;
    Numbers[1] = 10;
    Numbers[2] = 10 ;
    Numbers[3] = 30 ;
    Numbers[4] = 69 ;
    Numbers[5] = 70 ;
    Numbers[6] = 96 ;
    Numbers[7] = 100;

    start = Numbers.begin() ;   // location of first
                                // element of Numbers

    end = Numbers.end() ;       // one past the location
                                // last element of Numbers

    // print content of Numbers
    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // return the first location at which 10 can be inserted
    // in Numbers
    location = lower_bound(start, end, 10) ;

    cout << "First location element 10 can be inserted in Numbers is: "
        << location - start << endl ;
}

Program Output

Numbers { 4 10 10 30 69 70 96 100  }

First location element 10 can be inserted in Numbers is: 1

Sample for Predicate Version

// disable warning C4786: symbol greater than 255 character,
// okay to ignore this warning
#pragma warning(disable: 4786)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;


void main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of int
    typedef vector<int > IntVector ;

    //Define an iterator for template class vector of strings
    typedef IntVector::iterator IntVectorIt ;

    IntVector Numbers(VECTOR_SIZE) ;

    IntVectorIt start, end, it, location ;

    // Initialize vector Numbers
    Numbers[0] = 4 ;
    Numbers[1] = 10;
    Numbers[2] = 70 ;
    Numbers[3] = 10 ;
    Numbers[4] = 30 ;
    Numbers[5] = 69 ;
    Numbers[6] = 96 ;
    Numbers[7] = 100;

    start = Numbers.begin() ;   // location of first
                                // element of Numbers

    end = Numbers.end() ;       // one past the location
                                // last element of Numbers

    //sort Numbers using the function object less<int>()
    //lower_bound assumes that Numbers is sorted
    //using the "compare" (less<int>() in this case)
    //function
    sort(start, end, less<int>()) ;

    // print content of Numbers
    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // return the first location at which 10 can be inserted
    // in Numbers
    location = lower_bound(start, end, 10, less<int>()) ;

    cout << "First location element 10 can be inserted in Numbers is: "
        << location - start << endl ;
}

Program Output

Numbers { 4 10 10 30 69 70 96 100  }

First location element 10 can be inserted in Numbers is: 1