Алгоритмы STL , которые недооценивают новички (transform, accumulate, partition)

Введение

Многие разработчики, начав работу с STL, ограничиваются std::sort и std::find, а остальную логику пишут руками в виде циклов for. Между тем заголовок <algorithm> (и смежный <numeric>) содержит десятки готовых, тестированных и часто более эффективных операций. В этой статье разберём три недооценённых алгоритма: transform, accumulate и partition.

Концепция

• std::transform применяет функцию к каждому элементу диапазона и записывает результат в другой диапазон (или в тот же самый). Это аналог map из функциональных языков.
• std::accumulate (из <numeric>) сворачивает диапазон в одно значение с помощью бинарной операции — аналог reduce/fold.
• std::partition переставляет элементы диапазона так, что все элементы, удовлетворяющие предикату, оказываются перед всеми, не удовлетворяющими — без полной сортировки, что быстрее, если порядок внутри групп не важен.

Пример кода

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
#include <string>

struct Employee {
    std::string name;
    double salary;
    bool isManager;
};

int main() {
    std::vector<Employee> employees = {
        {"Alice", 5000, true},
        {"Bob", 3000, false},
        {"Carol", 3500, false},
        {"Dave", 6000, true},
        {"Eve", 2800, false}
    };

    // 1. transform: получить вектор имён
    std::vector<std::string> names;
    names.reserve(employees.size());
    std::transform(employees.begin(), employees.end(), std::back_inserter(names),
                    [](const Employee& e) { return e.name; });

    std::cout << "Names: ";
    for (const auto& n : names) std::cout << n << " ";
    std::cout << "n";

    // transform с применением "на месте": индексация зарплат (повышение на 10%)
    std::vector<double> raisedSalaries(employees.size());
    std::transform(employees.begin(), employees.end(), raisedSalaries.begin(),
                    [](const Employee& e) { return e.salary * 1.10; });

    // 2. accumulate: суммарный фонд оплаты труда
    double totalPayroll = std::accumulate(
        employees.begin(), employees.end(), 0.0,
        [](double sum, const Employee& e) { return sum + e.salary; });
    std::cout << "Total payroll: " << totalPayroll << "n";

    // accumulate для построения строки (не только чисел!)
    std::string joinedNames = std::accumulate(
        names.begin(), names.end(), std::string{},
        [](std::string acc, const std::string& name) {
            return acc.empty() ? name : acc + ", " + name;
        });
    std::cout << "Joined: " << joinedNames << "n";

    // 3. partition: разделить менеджеров и обычных сотрудников
    auto boundary = std::partition(employees.begin(), employees.end(),
                                    [](const Employee& e) { return e.isManager; });

    std::cout << "Managers: ";
    for (auto it = employees.begin(); it != boundary; ++it) {
        std::cout << it->name << " ";
    }
    std::cout << "nStaff: ";
    for (auto it = boundary; it != employees.end(); ++it) {
        std::cout << it->name << " ";
    }
    std::cout << "n";

    return 0;
}

Пояснения к коду

std::transform с std::back_inserter позволяет не задумываться о выделении памяти под результат — итератор сам вызывает push_back. Второй вызов transform пишет напрямую в заранее созданный вектор того же размера — это быстрее, если размер результата заранее известен.

std::accumulate принимает начальное значение и бинарный оператор; важно, что начальное значение задаёт тип аккумулятора — если передать 0 (int) вместо 0.0 для суммирования double, результат незаметно обрежется до целого. Второй пример показывает, что accumulate работает не только с числами: с std::string как аккумулятором он реализует склейку через запятую без отдельной написанной вручную функции join.

std::partition возвращает итератор-границу между группами, не делая полной сортировки (O(n) против O(n log n) у std::sort по предикату) и не гарантируя порядок внутри групп. Если нужен стабильный порядок внутри групп, используйте std::stable_partition.

Подводные камни и советы

1. transform не меняет размер диапазона — итератор назначения должен указывать на существующую область памяти достаточного размера, либо нужно использовать вставляющий итератор (back_inserter, inserter). 2. Тип начального значения в accumulate важен: всегда явно указывайте тип, соответствующий ожидаемому результату (0.0 вместо 0 для дробных чисел). 3. partition не сортирует — после него группы не упорядочены внутри себя; для упорядоченного разделения используйте stable_partition, а для разделения с подсчётом — std::count_if отдельно. 4. Не пишите вручную циклы for, если есть готовый алгоритм — это не только короче, но и часто эффективнее (учитывая внутренние оптимизации реализации STL) и сразу сообщает читающему код намерение через название функции.

================================================================================