[ новости /+++ | форум | теги | ]

                       Standard C++ Library
             Copyright 1998, Rogue Wave Software, Inc.


NAME
     equal_range

      - Find the largest subrange in a collection  into  which  a
     given  value  can be inserted without violating the ordering
     of the collection.



SYNOPSIS
     #include <algorithm>
     template <class ForwardIterator, class T>
     pair<ForwardIterator, ForwardIterator>
      equal_range(ForwardIterator first, ForwardIterator last,
                 const T& value);

     template <class ForwardIterator, class T, class Compare>
      pair<ForwardIterator, ForwardIterator>
       equal_range(ForwardIterator first, ForwardIterator last,
                  const T& value, Compare comp);



DESCRIPTION
     The equal_range algorithm performs a  binary  search  on  an
     ordered  container  to determine where the element value can
     be inserted without violating the container's ordering.  The
     library  includes  two  versions of the algorithm. The first
     version uses the less than operator (operator <)  to  search
     for the valid insertion range, and assumes that the sequence
     was sorted using the less than operator. The second  version
     allows you to specify a function object of type Compare, and
     assumes that Compare was  the  function  used  to  sort  the
     sequence. The function object must be a binary predicate.

     equal_range returns a pair  of  iterators,  i  and  j,  that
     define  a  range containing elements equivalent to value, in
     other words, the first and last valid insertion  points  for
     value.  If value is not an element in the container, i and j
     are equal. Otherwise, i points  to  the  first  element  not
     "less" than value, and j points to the first element greater
     than value. In the second version, "less" is defined by  the
     comparison object. Formally, equal_range returns a sub-range
     [i, j) such that value can be inserted  at  any  iterator  k
     within  the  range.  Depending upon the version of the algo-
     rithm used, k must satisfy one of the following conditions:
     !(*k <  value)  &&  !(value  <  *k)

      or

     comp(*k,value) == false && comp(value, *k) == false

     The range [first,last) is assumed to be sorted. Type T  must
     be LessThanComparable.



COMPLEXITY
     equal_range performs at most 2 * log(last - first) + 1  com-
     parisons.



EXAMPLE
     //
     // eqlrange.cpp
     //
      #include <vector>
      #include <algorithm>
      #include <functional>
      #include <iostream>
     using namespace std;
     int main()
      {
       typedef vector<int>::iterator iterator;
       int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};
        //
        // Set up a vector
        //
       vector<int> v1(d1+0, d1 + 11);
        //
        // Try equal_range variants
        //
       pair<iterator,iterator> p1 =
            equal_range(v1.begin(),v1.end(),3);
        // p1 = (v1.begin() + 4,v1.begin() + 5)
       pair<iterator,iterator> p2 =
            equal_range(v1.begin(),v1.end(),2,less<int>());
        // p2 = (v1.begin() + 4,v1.begin() + 5)
        // Output results
       cout << endl  << "The equal range for 3 is: "
             << "( " << *p1.first << " , "
             << *p1.second << " ) " << endl << endl;
       cout << endl << "The equal range for 2 is: "
             << "( " << *p2.first << " , "
             << *p2.second << " ) " << endl;

       return 0;
      }

     Program Output



     The equal range for 3 is: ( 3 , 4 )
     The equal range for 2 is: ( 2 , 3 )



WARNINGS
     If your compiler does not support default  template  parame-
     ters,  then you always need to supply the Allocator template
     argument. For instance, you have to write:

     vector<int,allocator<int> >

     instead of:

     vector<int>

     If your compiler does not support namespaces,  then  you  do
     not need the using declaration for std.



SEE ALSO
     binary_function, lower_bound, upper_bound

Партнёры:

Хостинг: