1[/
2    Copyright 2010 Neil Groves
3    Distributed under the Boost Software License, Version 1.0.
4    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5/]
6[section:search search]
7
8[heading Prototype]
9
10``
11template<class ForwardRange1, class ForwardRange2>
12typename range_iterator<ForwardRange1>::type
13search(ForwardRange1& rng1, const ForwardRange2& rng2);
14
15template<class ForwardRange1, class ForwardRange2>
16typename range_iterator<const ForwardRange1>::type
17search(const ForwardRange1& rng1, const ForwardRange2& rng2);
18
19template<
20    class ForwardRange1,
21    class ForwardRange2,
22    class BinaryPredicate
23    >
24typename range_iterator<ForwardRange1>::type,
25search(ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
26
27template<
28    class ForwardRange1,
29    class ForwardRange2,
30    class BinaryPredicate
31    >
32typename range_iterator<const ForwardRange1>::type
33search(const ForwardRange1& rng1, ForwardRange2& rng2, BinaryPredicate pred);
34
35
36template<
37    range_return_value re,
38    class ForwardRange1,
39    class ForwardRange2
40    >
41typename range_return<ForwardRange1, re>::type
42search(ForwardRange1& rng1, const ForwardRange2& rng2);
43
44template<
45    range_return_value re,
46    class ForwardRange1,
47    class ForwardRange2
48    >
49typename range_return<const ForwardRange1, re>::type
50search(const ForwardRange1& rng1, const ForwardRange2& rng2);
51
52template<
53    range_return_value re,
54    class ForwardRange1,
55    class ForwardRange2,
56    class BinaryPredicate
57    >
58typename range_return<ForwardRange1, re>::type,
59search(ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
60
61template<
62    range_return_value re,
63    class ForwardRange1,
64    class ForwardRange2,
65    class BinaryPredicate
66    >
67typename range_return<const ForwardRange1, re>::type
68search(const ForwardRange1& rng1, const ForwardRange2& rng2, BinaryPredicate pred);
69``
70
71[heading Description]
72
73The versions of `search` that return an iterator, return an iterator to the start of the first subsequence in `rng1` that is equal to the subsequence `rng2`. The `end(rng1)` is returned if no such subsequence exists in `rng1`.
74Equality is determined by `operator==` for non-predicate versions of `search`, and by satisfying `pred` in the predicate versions.
75
76The versions of `search` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
77
78[heading Definition]
79
80Defined in the header file `boost/range/algorithm/search.hpp`
81
82[heading Requirements]
83
84[*For the non-predicate versions:]
85
86* `ForwardRange1` is a model of the __forward_range__ Concept.
87* `ForwardRange2` is a model of the __forward_range__ Concept.
88* `ForwardRange1`'s value type is a model of the `EqualityComparableConcept`.
89* `ForwardRange2`'s value type is a model of the `EqualityComparableConcept`.
90* `ForwardRange1`s value type can be compared for equality with `ForwardRange2`'s value type.
91
92[*For the predicate versions:]
93
94* `ForwardRange1` is a model of the __forward_range__ Concept.
95* `ForwardRange2` is a model of the __forward_range__ Concept.
96* `BinaryPredicate` is a model of the `BinaryPredicateConcept`.
97* `ForwardRange1`'s value type is convertible to `BinaryPredicate`'s first argument type.
98* `ForwardRange2`'s value type is convertible to `BinaryPredicate`'s second argument type.
99
100[heading Complexity]
101
102Average complexity is Linear. Worst-case complexity is quadratic.
103
104[endsect]
105
106
107