Найти все на C++: практическое руководство

Разработчикам на C++ часто приходится находить множественные вхождения элементов в контейнерах.

Со std::find() находится первое совпадение, но для получения всех совпадений требуется другой подход.

На актуальных практических примерах изучим, как в C++ реализуется и применяется функциональность find_all.

find_all, или Его не существует

Сначала ключевой момент: в отличие от findall() в Python, на C++ нет встроенной функции std::find_all. Но эта функциональность создается здесь из компонентов стандартной библиотеки. Рассмотрим наиболее практичные подходы.

Метод 1: использование copy_if вместе с back_inserter

Вот чистый подход, он хорош для большинства сценариев:

#include <algorithm>
#include <vector>

template<typename Container, typename T>
std::vector<typename Container::iterator> find_all(Container& cont, const T& value) {
    std::vector<typename Container::iterator> result;
    auto it = cont.begin();
    while ((it = std::find(it, cont.end(), value)) != cont.end()) {
        result.push_back(it);
        ++it;
    }
    return result;
}

Посмотрим на него в деле:

std::vector<int> numbers = {1, 2, 3, 2, 4, 2, 5};
auto found = find_all(numbers, 2);

for (auto it : found) {
    std::cout << "Found 2 at position: " << std::distance(numbers.begin(), it) << '\n';
}

Метод 2: функция-генератор

Применяется с большими наборами данных, где результаты обрабатываются по одному:

#include <optional>
#include <functional>

template<typename Container, typename T>
auto make_finder(Container& cont, const T& value) {
    return [it = cont.begin(), end = cont.end(), &value]() mutable 
        -> std::optional<typename Container::iterator> {
        if (it == end) return std::nullopt;
        it = std::find(it, end, value);
        if (it == end) return std::nullopt;
        return std::optional{it++};
    };
}

Пример:

std::vector<int> numbers = {1, 2, 3, 2, 4, 2, 5};
auto next_match = make_finder(numbers, 2);

while (auto it = next_match()) {
    std::cout << "Found at: " << std::distance(numbers.begin(), *it) << '\n';
}

Реальный сценарий: анализ лог-файла

Вот практический пример, где важно найти все вхождения, это анализ лог-файлов для паттернов ошибок:

#include <string>
#include <fstream>

struct LogEntry {
    std::string timestamp;
    std::string message;
    bool operator==(const std::string& error_type) const {
        return message.find(error_type) != std::string::npos;
    }
};

std::vector<LogEntry> analyze_error_patterns(const std::vector<LogEntry>& logs, 
                                           const std::string& error_type) {
    std::vector<LogEntry> matching_errors;
    std::copy_if(logs.begin(), logs.end(), 
                 std::back_inserter(matching_errors),
                 [&](const LogEntry& entry) { return entry == error_type; });
    return matching_errors;
}

Применение:

std::vector<LogEntry> logs = {
    {"2024-01-01 10:00:01", "Connection timeout"},
    {"2024-01-01 10:00:02", "Process started"},
    {"2024-01-01 10:00:03", "Connection timeout"},
    {"2024-01-01 10:00:04", "Process completed"}
};

auto timeout_errors = analyze_error_patterns(logs, "timeout");

Найти все пользовательскими предикатами

Иногда нужны критерии соответствия посложнее, вот как расширяется это решение:

template<typename Container, typename Pred>
std::vector<typename Container::iterator> find_all_if(Container& cont, Pred pred) {
    std::vector<typename Container::iterator> result;
    auto it = cont.begin();
    while ((it = std::find_if(it, cont.end(), pred)) != cont.end()) {
        result.push_back(it);
        ++it;
    }
    return result;
}

Пример с пользовательским сопоставлением:

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8};
auto even_numbers = find_all_if(numbers, [](int n) { return n % 2 == 0; });

for (auto it : even_numbers) {
    std::cout << *it << " is at position " << std::distance(numbers.begin(), it) << '\n';
}

Производительность

При работе с большими наборами данных учитывается:

1. Использование памяти. В первом методе сохраняются все итераторы, в подходе же генератора используется постоянная память.
2. Временна́я сложность. У обоих подходов она O(n), но в методе генератора при необходимости возможно раннее завершение.
3. Для очень больших контейнеров используйте параллельные алгоритмы:

#include <execution>

template<typename Container, typename T>
std::vector<typename Container::iterator> parallel_find_all(Container& cont, const T& value) {
    std::vector<typename Container::iterator> result;
    std::mutex result_mutex;
    
    std::for_each(std::execution::par, cont.begin(), cont.end(),
        [&](auto& element) {
            if (element == value) {
                std::lock_guard<std::mutex> lock(result_mutex);
                result.push_back(std::find(cont.begin(), cont.end(), element));
            }
        });
    
    std::sort(result.begin(), result.end());
    return result;
}

Типичные ошибки и как их избежать

1. Инвалидация итератора. Не изменяйте контейнер, пока у вас имеются итераторы:

// Не делайте этого
auto found = find_all(vec, 2);
vec.push_back(2);  // Осуществляется инвалидация всех итераторов в «found»

2. Используйте индексы вместо итераторов с контейнерами неслучайного доступа:

// Не делайте этого с «std::list»
std::list<int> lst = {1, 2, 3, 2};
size_t index = 0;
// Со списками это неэффективно
while (index < lst.size()) {
    // ...
}

Помните, что при использовании этих методов разные контейнерные типы отличаются нюансами производительности. Выбирайте подход, оптимальный для конкретного сценария и контейнерного типа.

Показанные здесь методы пригодны для любого стандартного контейнерного типа и адаптируются для пользовательских контейнеров, которыми предоставляются стандартные интерфейсы итераторов.

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

• C++: полное руководство по разделению строк
• C++: полное руководство по «приведению вверх»
• C++: полное руководство по операторам Switch со строками

Читайте нас в Telegram, VK и Дзен

---

Перевод статьи ryan: A Practical Guide to find all in C++