Recover Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttp://yahoo.com/
advanced search

Valid RSS

Computing › Stl › Algorithms › Binarysearch ›

equal_range

Returns the range of elements equal to a given value
+ View version details
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. Page Comments

Definition

The equal_range() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class ForwardIterator, class Type >
   pair<ForwardIterator, ForwardIterator> equal_range(
      ForwardIterator first,
      ForwardIterator last, 
      const Type& val
   );
template < class ForwardIterator, class Type, class Predicate >
   pair<ForwardIterator, ForwardIterator> equal_range(
      ForwardIterator first,
      ForwardIterator last, 
      const Type& val, 
      Predicate comp
   );

Parameters:
Parameter Description
first A forward iterator addressing the position of the first element in the range to be searched
last A forward iterator addressing the position one past the final element in the range to be searched
val The value in the ordered range that needs to be equivalent to the value of the element addressed by the first component of the pair returned and that needs to be less than the value of the element addressed by the second component of that pair returns
comp User-defined predicate function object that is true when the left-hand argument is less than the right-hand argument. The user-defined predicate function should return false when its arguments are equivalent

Description

Equal_range function get the lower bound and the upper bound of a range where a new value can be inserted without misordering the elements between fi rst and last.

The first version uses operator< for comparison, and the second uses the function object comp.

Return Value

Returns a pair of forward iterators that specify a subrange, contained within the range searched, in which all of the elements are equivalent to val in the sense defined by the binary predicate used (either comp or the default, less-than).

Complexity

The complexity is logarithmic in the distance between first and last.

References

Example:

Example - equal_range algorithm
Problem
This program illustrates the use of the STL equal_range() algorithm (default version) to find the lower bound and upper bound locations of a given target value in a vector of integers sorted in ascending order.
Workings
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
  int a[] = {2, 3, 5, 6, 7, 7, 7,  8, 9, 10};
  vector<int> v(a, a+10);
  cout <<"\nHere are the contents of v:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";
 
  pair<vector<int>::iterator, vector<int>::iterator> bounds;
 
  bounds = equal_range(v.begin(), v.end(), 3);
  if (bounds.first != v.end())
    cout <<"\nLower bound of 3 in v = "<<*bounds.first;
  if (bounds.first != v.end())
    cout <<"\nUpper bound of 3 in v = "<<*bounds.second;
 
  bounds = equal_range(v.begin(), v.end(), 4);
  if (bounds.first != v.end())
    cout <<"\nLower bound of 4 in v = "<<*bounds.first;
  if (bounds.first != v.end())
    cout <<"\nUpper bound of 4 in v = "<<*bounds.second;
 
  bounds = equal_range(v.begin(), v.end(), 5);
  if (bounds.first != v.end())
    cout <<"\nLower bound of 5 in v = "<<*bounds.first;
  if (bounds.first != v.end())
    cout <<"\nUpper bound of 5 in v = "<<*bounds.second;
 
  bounds = equal_range(v.begin(), v.end(), 7);
  if (bounds.first != v.end())
    cout <<"\nLower bound of 7 in v = "<<*bounds.first;
  cout <<"\nThis is the first of the three 7's, since the value "
         "before this 7 is "<<*(bounds.first-1)<<".";
  if (bounds.first != v.end())
    cout <<"\nUpper bound of 7 in v = "<<*bounds.second;
 
  bounds = equal_range(v.begin(), v.end(), 0);
  if (bounds.first != v.end())
    cout <<"\nLower bound of 0 in v = "<<*bounds.first;
  if (bounds.first != v.end())
    cout <<"\nUpper bound of 0 in v = "<<*bounds.second;
 
  bounds = equal_range(v.begin(), v.end(), 15);
  if (bounds.first != v.end())
    cout <<"\nLower bound of 15 in v = "<<*bounds.first;
  if (bounds.first != v.end())
    cout <<"\nUpper bound of 15 in v = "<<*bounds.second;
  cout <<"\nNote that both the lower and upper bound locations "
         "\nof 15 are the end (one-past-the-last) vector position.";
 
  return 0;
}
Solution
Output:

Here are the contents of v:
2 3 5 6 7 7 7 8 9 10

Lower bound of 3 in v = 3
Upper bound of 3 in v = 5

Lower bound of 4 in v = 5
Upper bound of 4 in v = 5

Lower bound of 5 in v = 5
Upper bound of 5 in v = 6

Lower bound of 7 in v = 7
This is the first of the three 7's, since the value before this 7 is 6.
Upper bound of 7 in v = 8

Lower bound of 0 in v = 2 Upper bound of 0 in v = 2

Note that both the lower and upper bound locations of 15 are the end (one-past-the-last) vector position.
References

See Also

Last Modified: 2012-01-07 18:55:52     Page Rendered: 2012-05-22 04:53:15
 

Page Comments

 
 Format Excel Equations

  You must login to leave a messge