Функция find в C++: поиск элемента
Дорогие читатели, рад вас видеть! В этой статье разберем, как работает функция find
из файла algorithm
.
Как использовать find
Функция find
принимает 3 параметра:
Функция find
будет последовательно идти по массиву с начала до конца, пока не найдет элемент, который равен значению для поиска. Если значение не будет найдено, то find
вернет указатель на конец массива. Вот пример использования данной функции:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[3] = {1, 2, 3};
auto pointer = find(arr, arr + 3, 2);
if (pointer == end(arr)) {
cout << "элемент не найден" << endl;
} else {
cout << "позиция: " << pointer - begin(arr) << " значение: " << *pointer << endl;
}
return 0;
}
Результат выполнения программы:
позиция: 1 значение: 2

find
можно применять не ко всему массиву, а только к его части. В этом случае нужно просто передать указатели на интересующую часть массива. Важно помнить, что при поиске указатель на конец массива не учитывается.
Как реализовать find самому
Для того чтобы лучше понять как работает find
, давайте реализуем свою версию этой функции для массива чисел:
#include <iostream>
using namespace std;
int* find(int* start, int* end, int value) {
while (start != end) {
if (*start == value) return start;
start++;
}
return end;
}
int main() {
int arr[3] = {1, 2, 3};
auto pointer = find(arr, arr + 3, 2);
cout << "позиция: " << pointer - arr << ", значение: " << *pointer << endl;
return 0;
}
Вывод данной программы:
позиция: 1, значение: 2
Давайте разберемся что функция find
делает:
- Мы запускаем цикл while до тех пор, пока указатель
start
не равен указателюend
. - Если значение, на которое указывает
start
равно значению, которое мы ищем, то можно радоваться, мы нашли то что искали. - Иначе двинемся дальше увеличивая указатель.
- Если мы так и не нашли
value
, то возвращаемend
.
Поскольку с указателями можно производить арифметические операции, мы можем получить позицию искомого значения, просто вычтя
start
из найденного указателя:pointer - arr
.
Поздравляю! Вы реализовали свою версию функции find
, аналогичной той, что предоставляется в стандартной библиотеке C++.
Как использовать find с vector, set и другими контейнерами
Так как find
проходит массив линейно, анализируя каждый элемент, мы можем использовать итераторы для обхода любого контейнера в C++. Давайте посмотрим, как использовать find
с vector
:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> vec {1, 2, 3};
auto it = find(vec.begin(), vec.end(), 2);
cout << "позиция: " << it - vec.begin() << " значение: " << *it << endl;
return 0;
}
Вывод данной программы:
позиция: 1 значение: 2
Вывод программы снова не поменялся, однако мы теперь используем .begin()
и .end()
для того, чтобы указать границы поиска для find
.
Поскольку все контейнеры позволяют нам использовать итераторы, мы можем применять find
не только к векторам, но и к спискам, множествам и т.д. Вот пример с множествами:
set<int> s {1, 2, 3};
auto it = find(s.begin(), s.end(), 2);
cout << "значение: " << *it << endl;
Стоит отметить, что мы не можем определить позицию найденного элемента в
set
, так как множества не гарантируют порядок хранения элементов.
Вывод данной программы:
значение: 2
Таким образом, функция find
совместима с различными контейнерами в C++.
Пример программы с использованием find
Для того, чтобы закрепить изученный материал, давайте напишем простую программу. Программа будет спрашивать нас, что мы хотим сделать. У нас будет 4 варианта:
- Показать все числа, которые сейчас находятся в массиве.
- Добавить число в конец массива.
- Найти число в массиве.
- Выйти из программы.
Для поиска мы будем использовать функцию find
:
#include <iostream>
#include <algorithm>
using namespace std;
// Отображение списка чисел
void displayList(const int numbers[], const int& size) {
cout << "Текущие числа в списке: ";
for (int i = 0; i < size; i++) {
cout << numbers[i] << " ";
}
cout << endl;
}
int main() {
const int MAX_SIZE = 100;
int numbers[MAX_SIZE] = {1, 2, 3, 4, 5};
int currentSize = 5;
while (true) {
// Отображение меню для пользователя
cout << "\nМеню:\n";
cout << "1. Показать числа\n";
cout << "2. Добавить число\n";
cout << "3. Найти число\n";
cout << "4. Выйти\n";
cout << "Введите ваш выбор: ";
int choice;
cin >> choice;
switch (choice) {
case 1:
displayList(numbers, currentSize);
break;
case 2:
{
if (currentSize < MAX_SIZE) {
int newNum;
cout << "Введите число для добавления: ";
cin >> newNum;
numbers[currentSize] = newNum;
currentSize++;
cout << "Число добавлено.\n";
} else {
cout << "Список полон.\n";
}
}
break;
case 3:
{
displayList(numbers, currentSize);
int num;
cout << "Введите число для поиска: ";
cin >> num;
int* result = find(numbers, numbers + currentSize, num);
if (result != numbers + currentSize) {
cout << "Число " << num << " найдено в списке!" << endl;
} else {
cout << "Число " << num << " не найдено в списке." << endl;
}
}
break;
case 4:
cout << "До свидания!\n";
return 0;
default:
cout << "Неверный выбор. Пожалуйста, выберите снова.\n";
break;
}
}
return 0;
}
Теперь давайте запустим данную программу:
Меню:
1. Показать числа
2. Добавить число
3. Найти число
4. Выйти
Введите ваш выбор: 1
Текущие числа в списке: 1 2 3 4 5
Меню:
1. Показать числа
2. Добавить число
3. Найти число
4. Выйти
Введите ваш выбор: 3
Текущие числа в списке: 1 2 3 4 5
Введите число для поиска: 8
Число 8 не найдено в списке.
Меню:
1. Показать числа
2. Добавить число
3. Найти число
4. Выйти
Введите ваш выбор: 2
Введите число для добавления: 8
Число добавлено.
Меню:
1. Показать числа
2. Добавить число
3. Найти число
4. Выйти
Введите ваш выбор: 3
Текущие числа в списке: 1 2 3 4 5 8
Введите число для поиска: 8
Число 8 найдено в списке!
Меню:
1. Показать числа
2. Добавить число
3. Найти число
4. Выйти
Введите ваш выбор: 4
До свидания!
Упражнения
- Реализация
find
для строки:
Напишите программу, где вы реализуете функциюfind
, похожую на ту, что описана в статье, но для работы со строками (типstd::string
). Ваша функция должна искать заданный символ в строке и возвращать итератор к этому символу. Если символ не найден, возвращайте итератор к концу строки. - Использование
find
с разными контейнерами:
Напишите программу, которая демонстрирует использование встроенной функцииfind
с различными контейнерами C++ (например,std::list
,std::deque
). Для каждого контейнера выводите позицию найденного элемента и его значение. - Сравнение производительности:
Реализуйте две версии функцииfind
: одну, которую вы написали сами, и другую из стандартной библиотеки C++. Сравните их производительность на больших массивах данных (например, миллион элементов) и опишите разницу во времени выполнения.
Если у вас остались вопросы или есть замечания, оставьте комментарий ниже.
Обсуждение