首页 > 代码库 > STL 源码剖析 算法 stl_algo.h -- search_n
STL 源码剖析 算法 stl_algo.h -- search_n
本文为senlie原创,转载请保留此地址:http://blog.csdn.net/zhengsenlie
search_n
----------------------------------------------------------------------------------------
描述:在序列[first, last) 所涵盖的区间中,查找"连续 count 个符合条件之元素"所形成的子序列,
并返回迭代器 last
思路:
1.首先找出 value 第一次出现点
2.该出现点的后面是否连续出现 count - 1 个 value
3.如果是,找到了,如果不是,在当前元素后的区间重新找 value 的出现点
图6-6k
template <class ForwardIterator, class Integer, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value) { if (count <= 0) return first; else { first = find(first, last, value); // 首先找出 value 第一次出现点 while (first != last) { // 这里的条件写成 last - first < n 是不是好些? Integer n = count - 1; // value 还应该出现 n 次 ForwardIterator i = first; ++i; while (i != last && n != 0 && *i == value) { ++i; --n; } if (n == 0) // 找到了 return first; else // 没找到,重新从 i 开始找 first = find(i, last, value); } return last; } }
示例:
bool eq_nosign(int x, int y) { return abs(x) == abs(y); } void lookup(int* first, int* last, size_t count, int val) { cout << "Searching for a sequence of " << count << " '" << val << "'" << (count != 1 ? "s: " : ": "); int* result = search_n(first, last, count, val); if (result == last) cout << "Not found" << endl; else cout << "Index = " << result - first << endl; } void lookup_nosign(int* first, int* last, size_t count, int val) { cout << "Searching for a (sign-insensitive) sequence of " << count << " '" << val << "'" << (count != 1 ? "s: " : ": "); int* result = search_n(first, last, count, val, eq_nosign); if (result == last) cout << "Not found" << endl; else cout << "Index = " << result - first << endl; } int main() { const int N = 10; int A[N] = {1, 2, 1, 1, 3, -3, 1, 1, 1, 1}; lookup(A, A+N, 1, 4); lookup(A, A+N, 0, 4); lookup(A, A+N, 1, 1); lookup(A, A+N, 2, 1); lookup(A, A+N, 3, 1); lookup(A, A+N, 4, 1); lookup(A, A+N, 1, 3); lookup(A, A+N, 2, 3); lookup_nosign(A, A+N, 1, 3); lookup_nosign(A, A+N, 2, 3); } /* The output is Searching for a sequence of 1 '4': Not found Searching for a sequence of 0 '4's: Index = 0 Searching for a sequence of 1 '1': Index = 0 Searching for a sequence of 2 '1's: Index = 2 Searching for a sequence of 3 '1's: Index = 6 Searching for a sequence of 4 '1's: Index = 6 Searching for a sequence of 1 '3': Index = 4 Searching for a sequence of 2 '3's: Not found Searching for a (sign-insensitive) sequence of 1 '3': Index = 4 Searching for a (sign-insensitive) sequence of 2 '3's: Index = 4 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。