В этой статье я представлю еще один набор неизменяющих алгоритмов, имеющихся в стандартной библиотеке шаблонов C ++. Этот набор функций - это функции, которые вы можете использовать для поиска данных или для поиска данных в контейнере. Прежде чем начать, я должен упомянуть, что эти функции предназначены для использования с несортированными данными. Подробнее о том, какие функции использовать с отсортированными данными, я расскажу в другой статье.
Функция поиска
Функция find используется, чтобы определить, существует ли указанное значение в контейнере. Функция возвращает итератор к найденному значению, если значение находится в контейнере, и функция возвращает end, если значение не найдено в контейнере.
Вот шаблон синтаксиса для функции find:
find (начало диапазона, конец диапазона, значение);
Вот пример программы, использующей функцию find:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
void buildVec(vector<int> &vec, int n) {
srand(time(0));
for (int i = 1; i <= n; i++) {
vec.push_back(rand() % 100 + 1);
}
}
void printVec(vector<int> vec) {
int i = 0;
for (const int n : vec) {
cout << n << " ";
if (++i % 10 == 0) {
cout << endl;
}
}
}
int main () {
vector<int> numbers;
buildVec(numbers, 50);
printVec(numbers);
cout << endl;
int value;
for (int i = 1; i <= 2; i++) {
cout << "Value to find: ";
cin >> value;
auto position = find(numbers.begin(), numbers.end(), value);
if (position != numbers.end()) {
cout << "Found " << value << "." << endl;
}
else {
cout << value << " not in numbers." << endl;
}
}
return 0;
}
Вот результат одного запуска этой программы:
57 4 86 1 39 47 67 37 12 30 86 6 94 48 23 72 82 31 82 52 65 29 60 68 48 18 29 2 97 74 87 23 68 61 45 10 85 55 94 72 34 61 44 45 43 5 12 15 24 54 Value to find: 3 3 not in numbers. Value to find: 82 Found 82.
Функция find_if
Функция find_if используется для поиска значения на основе функции предиката, которая может быть лямбда-функцией или адаптером функции. Вот шаблон синтаксиса для этой функции:
find_if (начало диапазона, конец диапазона, функция);
В моем первом примере будет использоваться функция предиката для определения значения, найденного функцией. Я создаю функцию greaterThan98, которая возвращает результат сравнения своего аргумента со значением 98. Вот программа:
bool greaterThan98(int n) {
return n > 98;
}
int main () {
vector<int> numbers;
buildVec(numbers, 50);
printVec(numbers);
cout << endl << endl;
auto found = find_if(numbers.begin(), numbers.end(),
greaterThan98);
if (found != numbers.end()){
cout << "found value greater than 98" << endl;
}
else {
cout << "did not find value greater than 98";
}
return 0;
}
Вот результат двух запусков программы:
89 4 17 84 93 97 99 14 83 7 7 76 89 61 85 64 41 18 13 67 46 44 83 68 93 93 19 76 41 73 96 86 60 12 36 56 100 54 28 98 70 51 46 85 36 86 20 18 13 85 found value greater than 98 64 73 77 52 53 7 49 23 34 74 6 89 96 10 17 24 31 14 51 47 58 58 76 64 82 1 95 69 4 78 81 11 94 27 12 63 46 42 42 12 63 87 6 51 72 71 64 6 72 8 did not find value greater than 98
Вместо этого вы можете использовать функциональный адаптер вместе со скоросшивателем. Объяснение предыстории этого выходит за рамки данной статьи, поэтому перейдите сюда для объяснения. Теперь, чтобы понять (надеюсь), как работают связыватели, вот предыдущая программа, использующая объект функции greater<int>() со связывателем для привязки значения 98 к функции:
int main () {
using namespace std::placeholders;
vector<int> numbers;
buildVec(numbers, 50);
printVec(numbers);
cout << endl;
auto found = find_if(numbers.begin(), numbers.end(),
bind(greater<int>(),_1, 98));
if (found != numbers.end()){
cout << "found value greater than 98" << endl;
}
else {
cout << "did not find value greater than 98";
}
return 0;
}
Результат этой программы такой же, как и результат выше, хотя, конечно, с другими номерами.
Также обратите внимание, что я использовал выражение using внутри main. Это упрощает вызов bind внутри вызова функции. В противном случае мне пришлось бы написать:
auto found = find_if(numbers.begin(), numbers.end(),
bind(greater<int>(),std::placeholders::_1, 98));
Функция find_if_not
Последняя функция в семействе find - find_if_not. Эта функция возвращает первый элемент контейнера, не соответствующий указанному критерию. Вот шаблон синтаксиса для этой функции:
find_if_not (начало диапазона, конец диапазона, функция);
В приведенном ниже примере я передаю лямбда-функцию в качестве третьего аргумента. Эта функция проверяет, больше ли значение или равно 10. Функция find_if_not вернет первое значение, не соответствующее этому критерию. Вот программа:
int main () {
vector<int> numbers;
buildVec(numbers, 50);
printVec(numbers);
cout << endl;
auto found = find_if_not(numbers.begin(), numbers.end(),
[](int element) { return element >= 10;});
if (found != numbers.end()){
cout << "found value less than 10: " << *found << endl;
}
else {
cout << "did not find value less than 10";
}
return 0;
}
Вот результат одного запуска этой программы:
17 60 44 24 56 10 68 95 76 20 55 21 34 87 46 32 62 9 5 3 12 79 34 44 51 96 6 29 62 95 40 86 95 8 89 67 72 10 8 34 8 59 23 27 16 68 98 74 62 71 found value less than 10: 9
Наконец, эти find функции лучше всего подходят для последовательных контейнеров, таких как массивы и векторы. У ассоциативных и неупорядоченных контейнеров есть свои собственные функции поиска, доступные как функции-члены с гораздо большей эффективностью, чем вы можете получить с помощью функций, которые я здесь описываю.
Использование функций поиска
Функции find используются для поиска отдельных значений в контейнере. Следующий набор функций, search функций, используется для поиска последовательностей значений в контейнере.
Первая функция в этой группе - search. Эта функция принимает четыре аргумента: начальный диапазон поиска, конечный диапазон поиска, начальный диапазон для поиска и конечный диапазон для поиска. Вот шаблон синтаксиса для функции search:
search (search-range-start, search-range-end, sequence-range-start, sequence-range-end);
Функция search возвращает итератор к первому элементу, в котором найдено совпадение, и, если совпадение не найдено, функция возвращает итератор до конца.
Вот пример использования функции search для поиска последовательности значений в векторе. Эта программа ищет последовательность 98, 99 в наборе из 50 случайно сгенерированных чисел. Вот код:
int main () {
vector<int> numbers;
buildVec(numbers, 50);
sort(numbers.begin(), numbers.end());
printVec(numbers);
cout << endl;
vector<int> highVals = {98, 99};
auto found = search(numbers.begin(), numbers.end(),
highVals.begin(), highVals.end());
if (found != numbers.end()) {
cout << "Found sequence starting with: " << *found << endl;
}
else {
cout << "Didn't find sequence." << endl;
}
return 0;
}
Вот два запуска программы:
1 1 1 3 7 8 9 11 13 15 17 18 19 20 22 26 27 33 33 33 43 45 46 47 48 50 51 61 63 63 64 66 69 73 73 75 80 80 81 82| 83 84 86 86 88 90 91 96 99 99 Didn't find sequence. 1 1 2 2 3 4 5 10 14 17 19 28 31 33 34 39 41 44 47 50 50 51 53 55 58 59 60 62 63 67 68 68 70 72 75 77 80 80 80 82 84 85 94 94 94 95 98 99 99 99 Found sequence starting with: 98
Другая функция в этой группе - search_n. Эта функция ищет указанное число одинаковых значений, например, три 100 подряд или 2 87 подряд.
Вот шаблон синтаксиса для функции search_n:
search_n (начало диапазона, конец диапазона, счетчик последовательности, значение);
Возвращаемое значение search_n - это итератор, указывающий на первое найденное значение в последовательности, и если последовательность не найдена, функция возвращает итератор до конца.
Вот программа, демонстрирующая, как работает функция search_n:
int main () {
vector<int> numbers;
buildVec(numbers, 50);
sort(numbers.begin(), numbers.end());
printVec(numbers);
cout << endl;
int seqCount, searchVal;
cout << "What value? ";
cin >> searchVal;
cout << "How many in a row? ";
cin >> seqCount;
auto found = search_n(numbers.begin(), numbers.end(),
seqCount, searchVal);
if (found != numbers.end()) {
cout << "Found at position: "
<< int(found - numbers.begin()) << endl;
}
else {
cout << "Did not find that sequence count in the container."
<< endl;
}
return 0;
}
Вот несколько запусков программы:
1 3 5 6 10 11 12 12 12 13 13 15 22 30 32 33 35 35 38 40 42 45 49 50 53 53 54 59 59 60 61 61 69 69 71 73 73 77 79 80 80 82 84 85 87 91 91 92 94 99 What value? 91 How many in a row? 2 Found at position: 45 2 3 5 5 5 6 7 8 8 13 14 16 16 18 25 28 32 32 33 36 39 44 44 44 48 48 50 56 65 65 66 72 73 74 76 77 77 79 82 86 89 93 95 97 97 97 98 99 100 100 What value? 5 How many in a row? 3 Found at position: 2
Вы можете видеть, что я определяю позицию, в которой находится первый элемент в последовательности, путем вычитания позиции begin из позиции, в которой было найдено первое значение, с помощью этой арифметики:
int(found — numbers.begin())
Необязательный способ вызова функции search_n - предоставить функцию предиката в качестве критерия для определения совпадения. Шаблон синтаксиса для этой версии функции:
search_n (начало диапазона, конец диапазона, счетчик последовательности, значение, функция-предиката);
Вот пример поиска указанной последовательности значений, превышающих указанное значение:
int main () {
vector<int> numbers;
buildVec(numbers, 50);
sort(numbers.begin(), numbers.end());
printVec(numbers);
cout << endl;
int seqCount, searchVal;
cout << "Greater than what value? ";
cin >> searchVal;
cout << "How many in a row? ";
cin >> seqCount;
auto found = search_n(numbers.begin(), numbers.end(),
seqCount, searchVal, greater<int>());
if (found != numbers.end()) {
cout << "Found at position: "
<< int(found - numbers.begin()) << endl;
}
else {
cout << "Did not find that sequence count in the container."
<< endl;
}
return 0;
}
Вот результат одного запуска этой программы:
1 1 3 6 15 16 20 24 24 26 27 34 35 39 41 44 44 46 48 48 48 49 50 51 51 55 57 57 57 57 63 65 67 67 67 68 69 72 72 73 74 75 76 78 85 87 87 90 91 98 Greater than what value? 85 How many in a row? 2 Found at position: 45
Еще больше алгоритмов поиска значений
В STL есть еще один набор алгоритмов для поиска значений и поисковых последовательностей. Я представлю эти функции в моей следующей статье как части 3 этой серии, посвященной неизменяемым алгоритмам.
Спасибо, что прочитали эту статью, и пишите мне с комментариями и предложениями.
