STL之std::set、std::map的lower_bound和upper_bound函数使用说明
由于在使用std::map时感觉lower_bound和upper_bound函数了解不多,这里整理并记录下相关用法及功能。
STL的map、multimap、set、multiset都有三个比较特殊的函数,lower_bound、upper_bound、equal_range。
原型如下:
iterator lower_bound (const value_type& val) const; iterator upper_bound (const value_type& val) const; pair<iterator,iterator> equal_range (const value_type& val) const;
上面三个函数是相关联的,equal_range返回两个迭代器,第一个迭代器是lower_bound的返回值,第二个迭代器是upper_bound的返回值。(注意是使用相同val值调用的情况下。)
从msdn及c++标准来看,lower_bound、upper_bound两个函数用于记录允许元素重复出现的数据集中给定关键字val在当前集合中区间范围。
对诸如set、map这种关键字唯一的集合而言,lower_bound、upper_bound返回迭代器是相同,关键字val在集合中不存在,二者返回结果一样,都是按照集合实例化时给定的Compare比较,不在val之前的第一个元素(亦即之后或者等于,如果按照默认的比较类型less,函数返回的是≥val的最小的元素);如果关键在val在集合中存在,lower_bound返回val关键字本身的迭代器,upper_bound返回关键字val下一个元素迭代器。
对multiset、multimap这类关键字不唯一的集合而言。按照关键字后面一个关键字在集合中出现的次数可分为:关键字val出现在集合中,但是是唯一的,这种情况和set、map情况类似;关键字val出现在集合中,出现多次,这种情况下lower_bound返回第一个出现关键字val对应的迭代器,upper_bound返回位于关键字val对应位置后第一个不是val的位置的迭代器;关键字val不在集合中,这种情况下与set、map一致。
综合一下(按照默认集合升序排序的情况下),lower_bound、upper_bound函数不管在什么情况下,以下条件均成立。
Iterator(val) ≤ Iterator(lower_bound)≤Iterator(upper_bound)
也就是lower_bound、upper_bound构成的上下限的区间总是表示一个有效的迭代器区间(equal_range返回值),该迭代区间的长度表示关键字val在集合中出现的次数。
如果二者返回值相等,表示关键字val在集合中未出现。(例外情况,集合中的所有元素均≥关键字val,返回集合的iterator::end)
如果迭代器区间长度是1,表示关键字val在集合中仅出现1次。
迭代器区间长度大于1,则表示关键字val出现多次,并且一定不是set和map这种关键字唯一的集合。
示例代码:
// g++ -o setLowerUpperBoundTest setLowerUpperBoundTest.cpp #include <set>
#include <iostream> using namespace std ; typedef set<int> SET_INT; int main()
{
SET_INT s1;
SET_INT::iterator i;
cout << "s1.insert(5)" << endl;
s1.insert();
cout << "s1.insert(10)" << endl;
s1.insert();
cout << "s1.insert(15)" << endl;
s1.insert();
cout << "s1.insert(20)" << endl;
s1.insert();
cout << "s1.insert(25)" << endl;
s1.insert(); cout << "s1 -- starting at s1.lower_bound(12)" << endl;
// prints: 15,20,25
for (i=s1.lower_bound();i!=s1.end();i++)
cout << "s1 has " << *i << " in its set." << endl; cout << "s1 -- starting at s1.lower_bound(15)" << endl;
// prints: 15,20,25
for (i=s1.lower_bound();i!=s1.end();i++)
cout << "s1 has " << *i << " in its set." << endl; cout << "s1 -- starting at s1.upper_bound(12)" << endl;
// prints: 15,20,25
for (i=s1.upper_bound();i!=s1.end();i++)
cout << "s1 has " << *i << " in its set." << endl; cout << "s1 -- starting at s1.upper_bound(15)" << endl;
// prints: 20,25
for (i=s1.upper_bound();i!=s1.end();i++)
cout << "s1 has " << *i << " in its set." << endl; cout << "s1 -- s1.equal_range(12)" << endl;
// does not print anything
for (i=s1.equal_range().first;i!=s1.equal_range().second;i++)
cout << "s1 has " << *i << " in its set." << endl; cout << "s1 -- s1.equal_range(15)" << endl;
// prints: 15
for (i=s1.equal_range().first;i!=s1.equal_range().second;i++)
cout << "s1 has " << *i << " in its set." << endl;
}
/* Output in windows
s1.insert(5)
s1.insert(10)
s1.insert(15)
s1.insert(20)
s1.insert(25)
s1 -- starting at s1.lower_bound(12)
s1 has 15 in its set.
s1 has 20 in its set.
s1 has 25 in its set.
s1 -- starting at s1.lower_bound(15)
s1 has 15 in its set.
s1 has 20 in its set.
s1 has 25 in its set.
s1 -- starting at s1.upper_bound(12)
s1 has 15 in its set.
s1 has 20 in its set.
s1 has 25 in its set.
s1 -- starting at s1.upper_bound(15)
s1 has 20 in its set.
s1 has 25 in its set.
s1 -- s1.equal_range(12)
s1 -- s1.equal_range(15)
s1 has 15 in its set.
*/
上述代码正好验证并说明了lower_bound、upper_bound、equal_range三个函数的功能的功能,以及本文中的解释。
最新文章
- Android Permission 访问权限大全(转)
- [转]Design Pattern Interview Questions - Part 1
- jQuery给标签写入内容
- Android开发中遇到的小问题 一
- 在python3.5下安装scrapy包
- Loadrunner中参数化实战(8)-Unique+Each occurrence
- IOS开发—数据库的使用
- Eclipse项目内存溢出解决方案
- oracle积累继续
- 从sockaddr中取得Ip地址和端口号
- Summation of primes
- hash应用以及vector的使用简介:POJ 3349 Snowflake Snow Snowflakes
- cURL安装和使用笔记
- HibernateReview Day2&ndash;Hibernate体系结构
- Caused by: org.springframework.beans.factory.BeanCreationException
- vue 追书神器
- SpringBoot 之Thymeleaf模板.
- nginx 拦截 swagger 登录
- JS事件(四)坐标位置
- gravity 和 layout_gravity
热门文章
- Swift下的基于UIView的位置属性扩展
- Java之——Web项目中DLL文件动态加载方法
- Spring使用内存数据库
- wcf 中客户端调用之死 感悟 wcf与原来的webservice2.0 的客户端调用区别(wcf调用完不关闭的话那就把web服务搞死了)
- Linux安装ElasticSearch-2.2.0-分词器插件(Mmseg)
- 高效的MySQL分页——利用子查询分页
- MongoDB学习笔记(10)-- 排序
- JQuery EasyUI Combobox的onChange事件
- PNG怎么转换成32位的BMP保持透明
- 10分钟轻松设置出 A+ 评分的 HTTP/2 网站