Category: algorithms | Component type: function |
template <class ForwardIterator, class Integer, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value); template <class ForwardIterator, class Integer, class T, class BinaryPredicate> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value, BinaryPredicate binary_pred);
The first version of search returns the first iterator i in the range [first, last - count) [2] such that, for every iterator j in the range [i, i + count), *j == value. The second version returns the first iterator i in the range [first, last - count) such that, for every iterator j in the range [i, i + count), binary_pred(*j, value) is true.
(The C++ standard permits the complexity to be O(n (last - first)), but this is unnecessarily lax. There is no reason for search_n to examine any element more than once.)
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
[1] Note that count is permitted to be zero: a subsequence of zero elements is well defined. If you call search_n with count equal to zero, then the search will always succeed: no matter what value is, every range contains a subrange of zero consecutive elements that are equal to value. When search_n is called with count equal to zero, the return value is always first.
[2] The reason that this range is [first, last - count), rather than just [first, last), is that we are looking for a subsequence whose length is count; an iterator i can't be the beginning of such a subsequence unless last - count is greater than or equal to count. Note the implication of this: you may call search_n with arguments such that last - first is less than count, but such a search will always fail.