reference resources: Execution policy: cppreference com
1, find series functions (single element sequential search)
This algorithm provides an algorithm for finding objects in a range, which is defined in the <algorithm> header file.
Points to the first iterator that satisfies the condition, or last if such an element cannot be found.
Reference from:< https://zh.cppreference.com/w/cpp/algorithm/find>
1. find searches for elements equal to value.
// The first element in the range [first, last) that meets a specific criterion template< class InputIt, class T > constexpr InputIt find( InputIt first, InputIt last, const T& value );
template< class ExecutionPolicy, class ForwardIt, class T > ForwardIt find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, const T& value );
2. find_ The element for which the if search predicate p returns true
Parameter Description: p - a unary predicate that returns true if it is a required element.
template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if( InputIt first, InputIt last,
UnaryPredicate p );
// Specify execution policy
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryPredicate p );
3. find_if_not searches for elements for which the predicate q returns false.
Parameter Description: q - a unary predicate that returns false if it is a required element.
template< class InputIt, class UnaryPredicate >
constexpr InputIt find_if_not( InputIt first, InputIt last,
UnaryPredicate q );
// Specify execution policy
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt find_if_not( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
UnaryPredicate q );
test case
int main()
{
vector<int>vec{ 3,6,10,8,7,9,1,5,2,4 }; // vector_int
int val = 7;
test1:// find
auto ret1 = find(vec.begin(), vec.end(), val); // lookup
if (ret1 != vec.end()) // If found, output
{
cout << " vec[" << distance(vec.begin(), ret1) << "] == " << val << endl;
}
// Output: vec[4] == 7
test2:// find_if
auto ret2 = find_if(vec.begin(), vec.end(),
[val](int v) {return v == val; }); // Find elements equal to val
if (ret2 != vec.end())
{
cout << " vec[" << distance(vec.begin(), ret2) << "] == " << val << endl;
}
// Output: vec[4] == 7
test3:// find_if_not
auto ret3 = find_if_not(vec.begin(), vec.end(),
[val](int v) {return v != val; }); // Find the number that does not satisfy (V! = Val)
// That is, v==val
if (ret3 != vec.end())
{
cout << " vec[" << distance(vec.begin(), ret3) << "] == " << val << endl;
}
// Output: vec[4] == 7
return 0;
}
1, Binary search series functions (single element binary search)
Note: the basis of binary search is that the given range is orderly arranged.
1. lower_bound binary search greater than or equal to
Returns an iterator that points to the first element in the range [first, last) that is not less than (i.e., greater than or equal to) value, or last if such an element is not found.
// Compare elements with operator< template< class ForwardIt, class T > constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
// Using the given comparison function comp template< class ForwardIt, class T, class Compare > constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
2. upper_bound binary search greater than
Returns an iterator pointing to the first element greater than value in the range [first, last), or last if such an element is not found. The binary implementation is adopted, so the order must be guaranteed before calling.
// Compare elements with operator< template< class ForwardIt, class T > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
// Using the given comparison function comp template< class ForwardIt, class T, class Compare > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
3. equal_range binary search equivalent interval
Returns the range containing all elements equivalent to value in the range [first, last).
std::pair with a pair of iterators defining the required range. The first iterator points to the first element not less than value, and the second iterator points to the first element greater than value.
If no element is less than value, last is returned as the first element. Similarly, if no element is greater than value, last is returned as the second element.
// Compare elements with operator<
template< class ForwardIt, class T >
constexpr std::pair<ForwardIt,ForwardIt>
equal_range( ForwardIt first, ForwardIt last,
const T& value );
// Using the given comparison function comp
template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt,ForwardIt>
equal_range( ForwardIt first, ForwardIt last,
const T& value, Compare comp );
4. binary_search Binary to find whether the element value exists
Check whether the element equivalent to value appears in the range [first, last).
true if an element equal to value is found, otherwise false.
// Compare elements with operator< template< class ForwardIt, class T > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );
// Using the given comparison function comp template< class ForwardIt, class T, class Compare > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
test case
int main()
{
vector<int>vec{ 3,6,10,8,7,9,1,5,2,4 }; // vector_int
sort(vec.begin(), vec.end(), less<int>()); // Sort {1 10｝
int val = 7;
test1:// lower_bound is greater than or equal to
auto ret1 = lower_bound(vec.begin(), vec.end(), val); // Find, greater than or equal to
if (ret1 != vec.end()) // If found, output
{
cout << "( vec[" << distance(vec.begin(), ret1) << "] == " << *ret1
<< " ) >= " << val << endl;
}
// Output: (vec[6] = = 7) >= 7
test2:// upper_bound greater than
auto ret2 = upper_bound(vec.begin(), vec.end(), val); // Find, greater than
if (ret2 != vec.end())
{
cout << "( vec[" << distance(vec.begin(), ret2) << "] == " << *ret2
<< " ) > " << val << endl;
}
// Output: (vec[7] = = 8) > 7
test3:// equal_range
vector<int> vecs{ 1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7 };
int vals = 4;
auto ret3 = equal_range(vecs.begin(), vecs.end(), vals); // Lookup, equivalence interval
for(auto i = ret3.first; i != ret3.second; i++)
{
cout << " vec[" << distance(vec.begin(), ret2) << "] == " << *i << "\n";
}
/* Output:
vec[7] == 4
vec[7] == 4
vec[7] == 4
*/
return 0;
}
3, Subsequence search
The first occurrence of the element subsequence [s_first, s_last) in the search range [first, last - (s_last - s_first)).
Points to the iterator in the range [first, last - (s\u last - s\u first)), starting with the first subsequence [s\u first, s\u last). If this subsequence is not found, last is returned
Reference from< https://zh.cppreference.com/w/cpp/algorithm/search>
1. use operator== to compare
// Elements are compared with operator==
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// Specify execution policy
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
2. compare with the given binary predicate p
// Elements are compared with the given binary predicate p
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// Specify execution policy
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
3. search the sequence [first, last) for the pattern specified in the searcher constructor
Note: this function returns searcher The result of operator (), that is, the iterator pointing to the substring position found, or last if not found
// Search the sequence [first, last) for the pattern specified in the searcher constructor. Execute the
// return searcher(first, last).first;
template<class ForwardIt, class Searcher>
constexpr ForwardIt search( ForwardIt first, ForwardIt last,
const Searcher& searcher );
test case
int main()
{
string str = { "It was Christmas Eve, a cold dark evening."
"There was coming a little poor girl."
"She was so cold and hungry."
"But she had to stay on the street."
"She had to sell the matches." }; // string
// search
string sub = "a little poor girl";
auto res = search(str.begin(), str.end(), sub.begin(),sub.end()); // lookup
if (res != str.end()) // Output the sentence and its subsequent contents
{
int start = distance(str.begin(), res);
int end = distance(res, str.end());
cout << str.substr(start, end) << endl;
}
return 0;
}