Функция 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++. Сравните их производительность на больших массивах данных (например, миллион элементов) и опишите разницу во времени выполнения.
Если у вас остались вопросы или есть замечания, оставьте комментарий ниже.
Если хотите всегда быть в курсе последних новостей в мире программирования и IT, подписываетесь на мой Telegram-канал, где я делюсь свежими статьями, новостями и полезными советами. Буду рад видеть вас среди подписчиков!
Читайте также
Обсуждение