STL 源代码剖析 算法 stl_algo.h -- equal_range
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了STL 源代码剖析 算法 stl_algo.h -- equal_range,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3543字,纯文字阅读大概需要6分钟。
内容图文
![STL 源代码剖析 算法 stl_algo.h -- equal_range](/upload/InfoBanner/zyjiaocheng/1101/13073097e2c24723947e7ae4b27e425e.jpg)
本文为senlie原创,转载请保留此地址: http://blog.csdn.net/zhengsenlie
equal_range(应用于有序区间)
--------------------------------------------------------------------------------------------------------------------------------------
描写叙述:利用二分查找找到一个区间,区间里的全部值都等于给定值,返回的是一个pair。
分别存储区间的上界迭代器和下界迭代器
源代码:
template <class ForwardIterator, class T> inline pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value) { return __equal_range(first, last, value, distance_type(first), iterator_category(first)); } // ForwardIterator 版本号 template <class ForwardIterator, class T, class Distance> pair<ForwardIterator, ForwardIterator> __equal_range(ForwardIterator first, ForwardIterator last, const T& value, Distance*, forward_iterator_tag) { Distance len = 0; distance(first, last, len); Distance half; ForwardIterator middle, left, right; while (len > 0) { // 奇怪? 为什么不直接用 lower_bound 、 upper_bound , 而是等找到值再用? // --> 我认为是效率方面的考虑。先找 value ,这时左右两个区间可能已经缩小了很多。 // 再利用 lower_bound 和 upper_bound 代价小非常多 half = len >> 1; middle = first; advance(middle, half); if (*middle < value) { first = middle; ++first; len = len - half - 1; } else if (value < *middle) len = half; else { left = lower_bound(first, middle, value); advance(first, len); right = upper_bound(++middle, first, value); return pair<ForwardIterator, ForwardIterator>(left, right); } } return pair<ForwardIterator, ForwardIterator>(first, first); } // RandomAccessIterator 版本号 template <class RandomAccessIterator, class T, class Distance> pair<RandomAccessIterator, RandomAccessIterator> __equal_range(RandomAccessIterator first, RandomAccessIterator last, const T& value, Distance*, random_access_iterator_tag) { Distance len = last - first; Distance half; RandomAccessIterator middle, left, right; while (len > 0) { half = len >> 1; middle = first + half; if (*middle < value) { first = middle + 1; len = len - half - 1; } else if (value < *middle) len = half; else { left = lower_bound(first, middle, value); right = upper_bound(++middle, first + len, value); return pair<RandomAccessIterator, RandomAccessIterator>(left, right); } } return pair<RandomAccessIterator, RandomAccessIterator>(first, first); }
演示样例:
int main() { int A[] = { 1, 2, 3, 3, 3, 5, 8 }; const int N = sizeof(A) / sizeof(int); for (int i = 2; i <= 4; ++i) { pair<int*, int*> result = equal_range(A, A + N, i); cout << endl; cout << "Searching for " << i << endl; cout << " First position where " << i << " could be inserted: " << result.first - A << endl; cout << " Last position where " << i << " could be inserted: " << result.second - A << endl; if (result.first < A + N) cout << " *result.first = " << *result.first << endl; if (result.second < A + N) cout << " *result.second = " << *result.second << endl; } }
/* The output is: Searching for 2 First position where 2 could be inserted: 1 Last position where 2 could be inserted: 2 *result.first = 2 *result.second = 3 Searching for 3 First position where 3 could be inserted: 2 Last position where 3 could be inserted: 5 *result.first = 3 *result.second = 5 Searching for 4 First position where 4 could be inserted: 5 Last position where 4 could be inserted: 5 *result.first = 5 *result.second = 5*/
原文:http://www.cnblogs.com/mengfanrong/p/5187087.html
内容总结
以上是互联网集市为您收集整理的STL 源代码剖析 算法 stl_algo.h -- equal_range全部内容,希望文章能够帮你解决STL 源代码剖析 算法 stl_algo.h -- equal_range所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。