Дана стаття розкриває алгоритм std::find_if (std::find з предикатом) з бібліотеки STL C++.
Даний алгоритм оголошується наступним чином:
template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator begin, InputIterator end, UnaryPredicate pred) ;
Алгоритм find_if виконує пошук елемента у проміжку [begin,end). Елемент вважається знайденим коли предикат pred повертає бульове значення true, в такому разі шаблонна функція повертає ітератор, який вказує на даний елемент в послідовності. Якщо під час тестування елементів предикат не повернув значення true, функція повертає ітератор end.
Це дозволяє організувати пошук за власним оператором. Це може бути не строгий пошук через оператор "==", а пошук приблизного значення через оператори порівняння ">" і "<" і інші.
В якості предиката може виступати як функція так і функціональний об'єкт.
Приклади
Приклад #1
Розглянемо приклад використання алгоритму find_if у якості функції для пошуку значень з певним допустимим відхиленням. В якості предиката буде виступати функція.
#include <iostream> /* об'єкт cout */
#include <algorithm> /* корисні алгоритми */
using namespace std ; /* друкуємо без std */
/* унарний предикат призначений для алгоритму find_if */
/* повертає значення true, якщо переданий йому аргумент
** міститься у проміжку [0.5, 0.75] */
bool custom_pred (float el)
{ return (el>=0.5f && el<=0.75) ; }
/* головна функція програми */
int main (int argc, char** argv)
{
/* створюємо масив дійсних чисел для експериментів
** і визначаємо кількість елементів у ньому */
float fArray [] = {0.3f, 1.1f, 0.1f, 0.34f, 0.4999f, 0.6f, 0.76f, 0.9f} ;
int fLen = sizeof(fArray)/sizeof(fLen) ;
/* виконуємо пошук з предикатом */
float* ptr = find_if (fArray, fArray+fLen, custom_pred) ;
/* перевіряємо результат і виводимо відповідне повідомлення */
if (ptr>=fArray && ptr<fArray+fLen)
{ cout << "Елемент знайдено: " << *ptr << endl ; }
else
{ cout << "Елемент не знайдено." << endl ; }
return 0 ;
}
Після компілювання і виконання даної програми можна отримати приблизно наступний результат:
Приклад #2
Розглянемо використання алгоритму в парі з функціональним об'єктом. Перевага використання функціонального об'єкта полягає у більшій гнучкості - ми можемо, на відміну від попереднього прикладу, зміщувати допустимі межі пошуку, вказуючи їх у самому примірнику функціонального об'єкта. Через це програма стає гнучкішою, з меншою кількістю коду - для кожного проміжку не потрібно створювати окрему функцію-предикат. Це особливо стосується шаблонних функціональних об'єктів.
#include <math.h> /* математичні функції */
#include <iostream> /* об'єкт cout */
#include <algorithm> /* корисні алгоритми */
using namespace std ; /* друкуємо без std */
/* клас призначений для алгоритму find_if */
template <typename T>
class custom_pred_class
{
public :
/* перевантажуємо оператор дужок, через що
** конкретні об'єкти даного класу стають функціональними */
bool operator () (T el)
{ return (lo_limit<=el && el<=hi_limit) ; }
/* дозволяє змінювати відхилення пошуку */
void set_limits (T low, T high)
{
lo_limit = low ;
hi_limit = high ;
}
/* дозволяє встановити ліміти через конкретне значення
** і його допустиме відхилення */
void set_value_limit (T value, T deviation)
{
deviation *= deviation<0 ? (-1) : 1 ;
lo_limit = value - deviation ;
hi_limit = value + deviation ;
}
/* дозволяє дізнаватись допустиме відхилення */
void get_limits (T& low, T& high)
{
low = lo_limit ;
high = hi_limit ;
}
T get_low_limit () { return lo_limit ; }
T get_high_limit () { return hi_limit ; }
/* конструктори */
/* конструктор встановлює допустиме відхилення */
custom_pred_class (T lowest_lim, T highest_lim)
: lo_limit (lowest_lim),
hi_limit (highest_lim)
{} ;
private:
T lo_limit ;
T hi_limit ;
} ;
/* головна функція програми */
int main (int argc, char** argv)
{
/* створюємо масив дійсних чисел для експериментів
** і визначаємо кількість елементів у ньому */
float fArray [] = {0.3f, 1.1f, 0.1f, 0.34f, 0.4999f, 0.6f, 0.76f, 0.9f} ;
int fLen = sizeof(fArray)/sizeof(fLen) ;
/* виводимо послідовність на екран */
cout << "Послідовність, в якій виконується пошук:" << endl ;
for (unsigned int iter=0; iter<fLen; ++iter)
{ cout << fArray[iter] << "; " ; }
cout << endl ;
custom_pred_class<float> comp (0.29f, 0.31f) ;
cout << "Виконую пошук з відхиленням [" << comp.get_low_limit ()
<< ", " << comp.get_high_limit () << "]" << endl ;
/* виконуємо пошук з предикатом */
float* ptr = find_if (fArray, fArray+fLen, comp) ;
/* перевіряємо результат і виводимо відповідне повідомлення */
if (ptr>=fArray && ptr<fArray+fLen)
{ cout << "Елемент знайдено: " << *ptr << endl ; }
else
{ cout << "Елемент не знайдено." << endl ; }
/* встановлюємо новий проміжок */
comp.set_value_limit (1.0f, 0.11f) ;
cout << "Виконую пошук з відхиленням [" << comp.get_low_limit ()
<< ", " << comp.get_high_limit () << "]" << endl ;
/* виконуємо пошук з предикатом */
ptr = find_if (fArray, fArray+fLen, comp) ;
/* перевіряємо результат і виводимо відповідне повідомлення */
if (ptr>=fArray && ptr<fArray+fLen)
{ cout << "Елемент знайдено: " << *ptr << endl ; }
else
{ cout << "Елемент не знайдено." << endl ; }
return 0 ;
}
Після виконання даного коду можна отримати наступне:
Резюме
Даний алгоритм, звичано, має набагато більші можливості через використання функціональних об'єктів і унарних предикатів - можливо створити предикати для довільних типів. Прикладом також можуть стати послідовності рядків символів, на подобі об'єктів класу string, плюс предикат редакційної відстані Левенштейна. Даний алгоритм обмежений тільки фантазією користувача.