记两个std接口equal_range，set_difference

1.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，其第一和第二（都是迭代器）皆指向该位置。

说白了，equal_range就是在一个排序的容器内查找并返回找到的值的区间

// map::equal_elements
#include <iostream>
#include <map>
using namespace std;

int main ()
{
  map<char,int> mymap;
  pair<map<char,int>::iterator,map<char,int>::iterator> ret;

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

  ret = mymap.equal_range('b');

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

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

  return 0;
}

有些容器内无equal_range方法如vector，则可用std::equal_range方法

    pair<vector<int>::iterator, vector<int>::iterator> ret;
    vector<int> vec_i = { 1, 1, 2, 3, 4 };
    ret = std::equal_range(vec_i.begin(),vec_i.end(),1);

2.set_difference

算法set_difference可以用来求两个集合的差集，此处的集合可以为std::set，也可以是std::multiset，但是不可以是hash_set以及hash_multiset。为什么呢？因为set_difference要求两个区间必须是有序的（从小到大排列），std::set和std::multiset为有序序列，而hash_set以及hash_multiset为无序序列。

算法set_difference可构造区间S1,S2的差集（出现于S1但不出现于S2的元素），即S1-S2;返回值为指向输出区间的尾端。
由于区间S1，S2内的每个元素都不需唯一，因此，如果某个值在S1中出现m次，在S2中出现n次，那么该值在输出区间中出现的次数为max(m-n,0)，且全部来自S1。
set_difference为稳定操作，即输出区间内的每个元素的相对顺序都和S1内的相对顺序相同。

一定谨记：两个区间必须是有序区间（从小到大）

相似的还有set_union(取两集合并集)、set_intersection(取两集合交集)、set_difference(取两集合差集)，参数基本都一样

int main(void)
{
    int iarr1[]={1,2,3,3,6,7,4,5};
    int iarr2[]={1,4,3,10,9};
    std::sort(begin(iarr1),end(iarr1));
    std::sort(begin(iarr2),end(iarr2));
    vector<int> ivec(10);  
    auto iter=set_difference(begin(iarr1),end(iarr1),begin(iarr2),end(iarr2),ivec.begin());    //ivec为：2,3,5,6,7
    ivec.resize(iter-ivec.begin());//重新确定ivec大小
    return 0;
}

注意，这里1,2参数和3,4参数换位置了ivec结果就不一样了，现在的结果是iarr1里有而iarr2中没有的元素。

另外需要注意的是，类似于这样要在新容器里生成新的元素的方法，一定要申请空间后再调用，不然std的类似方法是不会帮你申请空间的

原文链接: https://www.cnblogs.com/wangshaowei/p/10469833.html

欢迎关注

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

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/391642

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

记两个std接口equal_range，set_difference

相关推荐