Common STL search algorithm

The advice in effective STL is to use algorithms instead of handwriting loops. Find not loop traversal, here summarized under the common STL search algorithm;

There are three kinds of search, namely, point, line and plane:
Point is to find the target for a single element;
A line is an interval;
The face is to find the target set;

For each category of search, the default comparison function is equal, in order to meet the richer needs, the algorithm also provides a custom comparison function version;

Single element lookup

Find () compares equal lookups

Find () finds a single element from a given interval, and defines:

template <class InputIterator, class T>

InputIterator find (InputIterator first, InputIterator last, const T& val);

For example, look up 30 from myvector:

int myints[] = { 10, 20, 30, 40 };

std::vector<int> myvector (myints,myints+4);

it = find (myvector.begin(), myvector.end(), 30);

if (it != myvector.end())

    std::cout << "Element found in myvector: " << *it << 'n';

else

    std::cout << "Element not found in myvectorn";

Find_if () custom comparison function

STD ::find_if(): find the first element from the given interval that satisfies the comparison function;
For example, look for the first element divisible by 30 from myvector:

bool cmpFunction (int i) {

  return ((i%30)==0);

}

it = std::find_if (myvector.begin(), myvector.end(), cmpFunction);

std::cout << "first:" <<  *it <<std::endl;

Count () counts the number of occurrences of the element

STD ::count() : the number of occurrences of an element in a statistical interval;
STD :count_if() : a custom comparison function version of count()

Search_n () queries for the repeated locations of individual elements

Search_n (): find is used to query a single element, and search_n is used to find elements that appear n times in the interval.

Example: query the location of 30 consecutive occurrences in myvector:

int myints[]={10,20,30,30,20,10,10,20};

std::vector<int> myvector (myints,myints+8);

it = std::search_n (myvector.begin(), myvector.end(), 2, 30);

Search_n () supports custom comparison functions;

Adjacent_find () query range of repeating elements in position

Adjacent_find () query interval of repeating elements in position, and the algorithm supports custom comparison functions;

Query for element boundaries in lower_bound() ordered interval

Lower_bound () is used to find the value of the first element in a sorted interval that is not less than the given element:
Example: find a lower bound in container v that is not less than 20:

int myints[] = {10,20,30,30,20,10,10,20};

std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

std::vector<int>::iterator low,up;

low=std::lower_bound (v.begin(), v.end(), 20); 

std::cout << "lower_bound at position " << (low- v.begin()) << 'n';

A similar algorithm has upper_bound(), which finds the value of the first element in an ordered interval that is greater than a given element.
And equal_range(), which looks for the upper and lower bounds of the ordered interval; (returns lower_bound() and upper_bound() once);

Binary search of binary_search() ordered interval

Binary_search () is used to find whether an element is in an ordered interval using a binary search. Note that the return value of this algorithm is bool,
Instead of subscript position, its internal algorithm logic and lower_bound () are similar, and the behavior is shown as:

template <class ForwardIterator, class T>

  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)

{

  first = std::lower_bound(first,last,val);

  return (first!=last && !(val<*first));

}

Example: find the existence of 3 from the ordered interval v:

int myints[] = {1,2,3,4,5,4,3,2,1};

std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

std::sort (v.begin(), v.end());

if (std::binary_search (v.begin(), v.end(), 3))

    std::cout << "found!n"; else std::cout << "not found.n";

Min_element () finds the smallest element

Min_element () finds the minimum in a given interval;

int myints[] = {3,7,2,5,6,4,9};

std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << 'n';

Similar algorithms are: max_element() to find the maximum value;

Search ()

Search () finds where the subinterval first appears

Find () is used to find a single element, and search() is used to find a subinterval.
Example: find the location where a subinterval [20,30] occurs from a myvector:

  int needle1[] = {20,30};

  it = std::search (myvector.begin(), myvector.end(), needle1, needle1+2);

  if (it!=myvector.end())

    std::cout << "needle1 found at position " << (it-myvector.begin()) << 'n';

Search supports custom comparison functions;
Example: query a subinterval in a given interval where each element is 1 less than the target interval;

bool cmpFunction (int i, int j) {

  return (i-j==1);

}

int myints[] = {1,2,3,4,5,1,2,3,4,5};

std::vector<int> haystack (myints,myints+10);

int needle2[] = {1,2,3};

// using predicate comparison:

it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, cmpFunction);

Find_end () looks for the last location of the subinterval

Search () is used to find the first occurrence of the subinterval, while find_end() is used to find the last occurrence of the subinterval:
Find_end () supports custom comparison functions;

Equal () determines whether the two intervals are equal

Equal () is used to determine whether two intervals are equal. The algorithm supports a custom comparison function.

Mismatch () queries for the first occurrence of different positions in two intervals;

Mismatch () queries for two intervals where different positions appear first. This algorithm also supports custom comparison functions.

Collection to find

Find_first_of looks for any element in the collection

Find_first_of () is used to find any element in a given collection:
Example: find the location where A,B, and C appear from haystack:

  int mychars[] = {'a','b','c','A','B','C'};

  std::vector<char> haystack (mychars,mychars+6);

  int needle[] = {'C','B','A'};

  // using default comparison:

  it = find_first_of (haystack.begin(), haystack.end(), needle, needle+3);

Find_first_of supports custom comparison functions;

The above is all the content of this article, I hope you can enjoy it.