Функция 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++. Сравните их производительность на больших массивах данных (например, миллион элементов) и опишите разницу во времени выполнения.

Если у вас остались вопросы или есть замечания, оставьте комментарий ниже.

Как использовать find

Как реализовать find самому

Как использовать find с vector, set и другими контейнерами

Пример программы с использованием find

Упражнения

Читайте также

Обсуждение