equal_range用法

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 
 6 int main ()
 7 {
 8   map<char,int> mymap;
 9   pair<map<char,int>::iterator,map<char,int>::iterator> ret;
10 
11   mymap['a']=10;
12   mymap['b']=20;
13   mymap['c']=30;
14 
15   ret = mymap.equal_range('b');
16 
17   cout << "lower bound points to: ";
18   cout << ret.first->first << " => " << ret.first->second << endl;
19 
20   cout << "upper bound points to: ";
21   cout << ret.second->first << " => " << ret.second->second << endl;
22 
23   return 0;
24 }

原文链接: https://www.cnblogs.com/fnlingnzb-learner/p/6005169.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍