c++ STL equal_range lower_bound upper

c++ STL equal_range lower_bound upper_bound

用来得到容器中等于一个值的子序列。

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

注意返回值比较特殊，返回的是一个pair对。

使用这个算法之前要操作的空间必须是已经排序了的。而且排序还是根据equal_range里面的Compare函数。

For the function to yield the expected result, the elements in the range shall already be ordered according to the same criterion (operator< or comp).

Return value

A pair, where its member pair::first is an iterator to the lower bound of the subrange of equivalent values, andpair::second its upper bound. The values are the same as those that would be returned by functions lower_bound andupper_bound respectively.

返回的pair对中first指向相等元素序列的的第一个位置，而second指向上界。[i,j]代表符合comp的最大子区间。

equal_range是C++ STL中的一种二分查找的算法，试图在已排序的[first,last)中寻找value，它返回一对迭代器i和j，其中i是在不破坏次序的前提下，value可插入的第一个位置（亦即lower_bound），j则是在不破坏次序的前提下，value可插入的最后一个位置（亦即upper_bound），因此，[i,j)内的每个元素都等同于value，而且[i,j)是[first,last)之中符合此一性质的最大子区间

如果以稍许不同的角度来思考equal_range,我们可把它想成是[first,last)内"与value等同"之所有元素形成的区间A，由于[fist,last)有序（sorted），所以我们知道"与value等同"之所有元素一定都相邻，于是，算法lower_bound返回区间A的第一个迭代器，算法upper_bound返回区间A的最后一个元素的下一个位置，算法equal_range则是以pair的形式将两者都返回

即使[fist,last)并未含有"与value等同"之任何元素，以上叙述仍然合理，这种情况下，"与value等同"之所有元素形成的，其实是一个空区间，在不破坏次序的情况下，只有一个位置可以插入value，而equal_range所返回的pair，其第一和第二（都是迭代器）皆指向该位置。

/*
********************
用equal_range()探测一个有序的vector中的可以插入数字5的位置
*******************
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    vector<int> vec;
    for(int i=0;i<4;i++)
        vec.push_back(i);
    for(int i=5;i<10;i++)
        vec.push_back(5);
    vec.push_back(6);
    int val=5;
    pair<vector<int>::iterator,vector<int>::iterator> bounds;
    bounds=equal_range(vec.begin(),vec.end(),val);
    cout<<" The first place that "<<val<<"could be inserted is before"<<*bounds.first<<endl;
    cout<<"and the last place that it could be inserted is before"<<*bounds.second<<endl;
}

The first place that 5could be inserted is before5
and the last place that it could be inserted is before6
请按任意键继续. . .因为我们在bounds.first前加了*取值，输出的不是位置，而是当前位置的值了，可以看到是正确的。

上面的程序有一点问题，应该先sort，在equal_range

The behavior of this function template is equivalent to:

template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value )
{
  ForwardIterator it = lower_bound (first,last,value);
  return make_pair ( it, upper_bound(it,last,value) );
}

lower_bound用法如下：

// lower_bound/upper_bound example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
  vector<int>::iterator low,up;

  sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  low=lower_bound (v.begin(), v.end(), 20); //          ^
  up= upper_bound (v.begin(), v.end(), 20); //                   ^

  cout << "lower_bound at position " << int(low- v.begin()) << endl;
  cout << "upper_bound at position " << int(up - v.begin()) << endl;

  return 0;
}

lower_bound at position 3
upper_bound at position 6