Chinaunix首页 | 论坛 | 博客
  • 博客访问: 358234
  • 博文数量: 135
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1106
  • 用 户 组: 普通用户
  • 注册时间: 2013-03-20 09:56
文章分类

全部博文(135)

文章存档

2017年(3)

2016年(18)

2015年(69)

2014年(39)

2013年(6)

我的朋友

分类: C/C++

2014-09-24 12:25:59

转载自:http://blog.chinaunix.net/uid-24185908-id-3049839.html
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,其第一和第二(都是迭代器)皆指向该位 置。
  1. // map::equal_elements
  2. #include <iostream>
  3. #include <map>
  4. using namespace std;

  5. int main ()
  6. {
  7.   map<char,int> mymap;
  8.   pair<map<char,int>::iterator,map<char,int>::iterator> ret;

  9.   mymap['a']=10;
  10.   mymap['b']=20;
  11.   mymap['c']=30;

  12.   ret = mymap.equal_range('b');

  13.   cout << "lower bound points to: ";
  14.   cout << ret.first->first << " => " << ret.first->second << endl;

  15.   cout << "upper bound points to: ";
  16.   cout << ret.second->first << " => " << ret.second->second << endl;

  17.   return 0;
  18. }
运行结果:
  1. lower bound points to: 'b' => 20
  2. upper bound points to: 'c' => 30
阅读(679) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~