Algoritmi STL: Puterea <algoritmului>

Stăpânește cei mai importanți algoritmi STL — de la căutare și sortare până la transformare și acumulare. Aflați cum compun algoritmii cu iteratoare pentru un cod expresiv și eficient.

Antetul <algoritmului>

Antetulconține peste 100 de algoritmi generici care funcționează pe intervale de iteratoare. Acești algoritmi întruchipează zeci de ani de informatică – testați în luptă, optimizați și corecti. Folosirea lor în loc de bucle scrise de mână face codul dvs. mai scurt, mai expresiv și adesea mai rapid.

Algoritmii sunt organizați pe categorii:

- Nemodificabil:find,count,search,all_of/any_of/none_of,equal,mismatch
- Modificare:copy,transform,fill,generate,replace,remove
- Sortare și comandare:sort,stable_sort,partial_sort,nth_element
- Căutare binară:lower_bound,upper_bound,binary_search,equal_range
- Numeric (în):accumulate,inner_product,partial_sum,iota

Fiecare algoritm ia ca intrare primară un interval de iterator[first, last).

Algoritmi nemodificatori

Algoritmii care nu se modifică inspectează elementele fără a le modifica. Ei sunt calii de muncă ai interogării și validării.

non_modifying.cpp

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

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    // find — returns iterator to first match (or end)
    auto it = std::find(nums.begin(), nums.end(), 5);
    if (it != nums.end()) {
        std::cout << "Found 5 at index " << std::distance(nums.begin(), it) << '\n';
    }

    // find_if — with a predicate
    auto even = std::find_if(nums.begin(), nums.end(),
                             [](int x) { return x % 2 == 0; });
    std::cout << "First even: " << *even << '\n';  // 4

    // count / count_if
    int fives = std::count(nums.begin(), nums.end(), 5);
    int odds  = std::count_if(nums.begin(), nums.end(),
                              [](int x) { return x % 2 != 0; });
    std::cout << "Fives: " << fives << ", Odds: " << odds << '\n';

    // all_of / any_of / none_of
    bool all_positive = std::all_of(nums.begin(), nums.end(),
                                    [](int x) { return x > 0; });
    bool has_negative = std::any_of(nums.begin(), nums.end(),
                                    [](int x) { return x < 0; });
    std::cout << std::boolalpha;
    std::cout << "All positive: " << all_positive << '\n';  // true
    std::cout << "Has negative: " << has_negative << '\n';  // false

    // equal — compare two ranges
    std::vector<int> nums2 = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    bool same = std::equal(nums.begin(), nums.end(), nums2.begin());
    std::cout << "Equal: " << same << '\n';  // true
}

Modificarea algoritmilor

Modificarea algoritmilor modifică valorile elementelor sau rearanjează elementele într-un interval.

modifying_algorithms.cpp

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};

    // transform — apply a function to each element
    std::vector<int> squared;
    std::transform(src.begin(), src.end(), std::back_inserter(squared),
                   [](int x) { return x * x; });
    // squared: {1, 4, 9, 16, 25}

    // transform with two input ranges (binary transform)
    std::vector<int> b = {10, 20, 30, 40, 50};
    std::vector<int> sums;
    std::transform(src.begin(), src.end(), b.begin(),
                   std::back_inserter(sums),
                   [](int a, int b) { return a + b; });
    // sums: {11, 22, 33, 44, 55}

    // fill and generate
    std::vector<int> zeros(10);
    std::fill(zeros.begin(), zeros.end(), 42);  // all 42s

    int counter = 0;
    std::generate(zeros.begin(), zeros.end(),
                  [&counter]() { return counter++; });
    // zeros: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    // remove-erase idiom (pre-C++20)
    std::vector<int> data = {1, 2, 3, 2, 4, 2, 5};
    auto new_end = std::remove(data.begin(), data.end(), 2);
    data.erase(new_end, data.end());  // actually shrinks the vector
    // data: {1, 3, 4, 5}

    // C++20: simpler
    std::erase(data, 3);
    // data: {1, 4, 5}

    // replace
    std::replace(data.begin(), data.end(), 4, 99);
    // data: {1, 99, 5}

    for (int x : data) std::cout << x << ' ';
    std::cout << '\n';
}

Algoritmi de sortare și ordonare

STL oferă mai mulți algoritmi de sortare cu diferite compromisuri.std::sorteste calul de lucru de uz general (O(n log n) medie, introsort), în timp cepartial_sortșinth_elementsunt mai eficiente atunci când aveți nevoie doar de o comandă parțială.

sorting.cpp

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

struct Student {
    std::string name;
    double gpa;
};

int main() {
    std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // sort — O(n log n), not stable
    std::sort(nums.begin(), nums.end());
    // nums: {1, 2, 3, 4, 5, 6, 7, 8, 9}

    // sort descending with comparator
    std::sort(nums.begin(), nums.end(), std::greater<int>{});
    // nums: {9, 8, 7, 6, 5, 4, 3, 2, 1}

    // stable_sort — preserves relative order of equal elements
    std::vector<Student> students = {
        {"Alice", 3.8}, {"Bob", 3.5}, {"Charlie", 3.8}, {"Diana", 3.5}
    };
    std::stable_sort(students.begin(), students.end(),
                     [](const Student& a, const Student& b) {
                         return a.gpa > b.gpa;  // descending GPA
                     });
    // Alice before Charlie (both 3.8) — relative order preserved

    // partial_sort — sort only the first k elements
    std::vector<int> data = {5, 2, 8, 1, 9, 3};
    std::partial_sort(data.begin(), data.begin() + 3, data.end());
    // First 3 are sorted: {1, 2, 3, ...rest unspecified}

    // nth_element — partition so the nth element is in its sorted position
    std::vector<int> vals = {5, 2, 8, 1, 9, 3, 7};
    std::nth_element(vals.begin(), vals.begin() + 3, vals.end());
    // vals[3] == 5 (the median), left side <= 5, right side >= 5

    // lower_bound / upper_bound — binary search on sorted data
    std::vector<int> sorted = {1, 2, 4, 4, 4, 7, 9};
    auto lo = std::lower_bound(sorted.begin(), sorted.end(), 4);  // first 4
    auto hi = std::upper_bound(sorted.begin(), sorted.end(), 4);  // past last 4
    std::cout << "Count of 4s: " << std::distance(lo, hi) << '\n';  // 3
}

Algoritmi numerici (<numerici>)

Antetuloferă algoritmi pentru calcule matematice pe intervale.

numeric_algorithms.cpp

#include <numeric>
#include <vector>
#include <iostream>
#include <functional>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};

    // accumulate — fold/reduce with initial value
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    std::cout << "Sum: " << sum << '\n';  // 15

    // accumulate with custom operation (product)
    int product = std::accumulate(nums.begin(), nums.end(), 1,
                                  std::multiplies<int>{});
    std::cout << "Product: " << product << '\n';  // 120

    // inner_product — dot product
    std::vector<int> weights = {2, 3, 1, 4, 2};
    int dot = std::inner_product(nums.begin(), nums.end(),
                                 weights.begin(), 0);
    std::cout << "Dot product: " << dot << '\n';  // 1*2 + 2*3 + 3*1 + 4*4 + 5*2 = 37

    // partial_sum — running total
    std::vector<int> running;
    std::partial_sum(nums.begin(), nums.end(), std::back_inserter(running));
    // running: {1, 3, 6, 10, 15}

    // iota — fill with incrementing values
    std::vector<int> seq(10);
    std::iota(seq.begin(), seq.end(), 1);  // {1, 2, 3, ..., 10}

    // C++17: reduce (parallel-friendly version of accumulate)
    // int sum2 = std::reduce(nums.begin(), nums.end());  // same as accumulate for +

    for (int x : running) std::cout << x << ' ';
    std::cout << '\n';
}

Capcană

std::removenu elimină de fapt elemente dintr-un container. Mută elementele „păstrate” în față și returnează un iterator la noul capăt logic. Mărimea reală a containerului este neschimbată - trebuie să apelațierase()pentru a elimina fizic elementele de sfârșit:

std::vector<int> v = {1, 2, 3, 2, 4};
auto new_end = std::remove(v.begin(), v.end(), 2);
// v is now: {1, 3, 4, ?, ?} with size still 5
v.erase(new_end, v.end()); // NOW size is 3

In C++20, std::erase(container, value) and std::erase_if(container, predicat) gestionează această expresie într-un singur apel. Preferați acestea atunci când sunt disponibile.

Bună practică

Algoritmii strălucesc atunci când sunt compuși. În loc de bucle complexe, algoritmi în lanț sunt împreună:

// Get sorted unique elements
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

// Copy only even numbers, squared, to output
std::vector<int> result;
std::copy_if(v.begin(), v.end(), std::back_inserter(result),
             [](int x) { return x % 2 == 0; });
std::transform(result.begin(), result.end(), result.begin(),
               [](int x) { return x * x; });

Acest stil este clar, corect și adesea depășește buclele scrise de mână, deoarece implementările bibliotecii folosesc SIMD, cod fără ramuri și alte micro-optimizări.

Idei cheie

Antetuloferă peste 100 de algoritmi generici care funcționează pe orice interval de iterator
std::sorteste O(n log n) introsort;std::stable_sortpăstrează ordinea elementelor egale
std::transformeste „harta” funcțională — aplică o funcție fiecărui element
std::removenu șterge — utilizați expresia de ștergere-eliminare sau C++20std::erase_if
std::accumulate(de la) este operația generală de pliere/reducere
Preferați algoritmii decât buclele scrise de mână - sunt mai clare, mai sigure și adesea mai rapide

Test — Verifică-ți cunoștințele

(20 XP)

1. Ce returnează`std::remove`?

2. Ce algoritm ați folosi pentru a verifica dacă TOATE elementele dintr-un interval satisfac un predicat?

3. Care este complexitatea de timp a`std::nth_element`?

Iterators: The STL Glue

Următor

Lambda și programare funcțională