Αλγόριθμοι STL: Η δύναμη του <αλγόριθμου>

Κατακτήστε τους πιο σημαντικούς αλγόριθμους STL — από την αναζήτηση και την ταξινόμηση έως τη μετατροπή και τη συσσώρευση. Μάθετε πώς συνθέτουν οι αλγόριθμοι με επαναλήπτες για εκφραστικό, αποτελεσματικό κώδικα.

Η κεφαλίδα <αλγόριθμος>

Η κεφαλίδαπεριέχει πάνω από 100 γενικούς αλγόριθμους που λειτουργούν σε εύρη επαναληπτικών. Αυτοί οι αλγόριθμοι ενσωματώνουν δεκαετίες επιστήμης υπολογιστών — δοκιμασμένοι στη μάχη, βελτιστοποιημένοι και σωστές. Η χρήση τους αντί για χειρόγραφους βρόχους κάνει τον κώδικά σας πιο σύντομο, πιο εκφραστικό και συχνά πιο γρήγορο.

Οι αλγόριθμοι οργανώνονται σε κατηγορίες:

- Μη τροποποιητικό:find,count,search,all_of/any_of/none_of,equal,mismatch
- Τροποποίηση:copy,transform,fill,generate,replace,remove
- Ταξινόμηση και παραγγελία:sort,stable_sort,partial_sort,nth_element
- Δυαδική αναζήτηση:lower_bound,upper_bound,binary_search,equal_range
- Αριθμητικό (σε):accumulate,inner_product,partial_sum,iota

Κάθε αλγόριθμος παίρνει ως κύρια είσοδο μια περιοχή επαναλήπτη[first, last).

Μη τροποποιητικοί αλγόριθμοι

Οι αλγόριθμοι που δεν τροποποιούνται επιθεωρούν στοιχεία χωρίς να τα αλλάζουν. Είναι οι εργάτες της αναζήτησης και της επικύρωσης.

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
}

Τροποποίηση αλγορίθμων

Η τροποποίηση αλγορίθμων αλλάζει τις τιμές των στοιχείων ή αναδιατάσσει στοιχεία εντός μιας περιοχής.

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';
}

Αλγόριθμοι ταξινόμησης και ταξινόμησης

Το STL παρέχει αρκετούς αλγόριθμους ταξινόμησης με διαφορετικούς συμβιβασμούς. Τοstd::sortείναι το εργαλείο γενικής χρήσης (O(n log n) μέσος όρος, introsort), ενώ ταpartial_sortκαιnth_elementείναι πιο αποτελεσματικά όταν χρειάζεστε μόνο μερική παραγγελία.

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
}

Αριθμητικοί αλγόριθμοι (<numeric>)

Η κεφαλίδαπαρέχει αλγόριθμους για μαθηματικούς υπολογισμούς σε εύρη.

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';
}

Παγίδα

Τοstd::removeδεν αφαιρεί πραγματικά στοιχεία από ένα κοντέινερ. Μετακινεί τα "κρατημένα" στοιχεία στο μπροστινό μέρος και επιστρέφει έναν επαναλήπτη στο νέο λογικό τέλος. Το πραγματικό μέγεθος του κοντέινερ παραμένει αμετάβλητο — πρέπει να καλέσετε τοerase()για να αφαιρέσετε φυσικά τα υστερούντα στοιχεία:

Χειριστείτε αυτό το ιδίωμα με μία κλήση. Προτιμήστε αυτά όταν είναι διαθέσιμα.

Βέλτιστη πρακτική

Οι αλγόριθμοι λάμπουν όταν συντάσσονται. Αντί για σύνθετους βρόχους, αλγόριθμους αλυσίδας μαζί:

// 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; });

Αυτό το στυλ είναι σαφές, σωστό και συχνά ξεπερνά τους χειρόγραφους βρόχους επειδή οι υλοποιήσεις της βιβλιοθήκης χρησιμοποιούν SIMD, κώδικα χωρίς διακλάδωση και άλλες μικροβελτιστοποιήσεις.

Βασικά συμπεράσματα

Η κεφαλίδαπαρέχει 100+ γενικούς αλγόριθμους που λειτουργούν σε οποιοδήποτε εύρος επαναλήψεων
Τοstd::sortείναι O(n log n) introsort. Τοstd::stable_sortδιατηρεί τη σειρά ίσων στοιχείων
Τοstd::transformείναι ο λειτουργικός "χάρτης" — εφαρμόζει μια συνάρτηση σε κάθε στοιχείο
Τοstd::removeδεν διαγράφει — χρησιμοποιήστε το ιδίωμα αφαίρεσης-διαγραφής ή C++20std::erase_if
Τοstd::accumulate(από το) είναι η γενική λειτουργία αναδίπλωσης/μείωσης
Προτιμήστε τους αλγόριθμους έναντι των χειρόγραφων βρόχων — είναι πιο σαφείς, πιο ασφαλείς και συχνά πιο γρήγοροι

Κουίζ — Δοκιμάστε τις γνώσεις σας

(20 XP)

1. Τι επιστρέφει το`std::remove`;

2. Ποιον αλγόριθμο θα χρησιμοποιούσατε για να ελέγξετε εάν ΟΛΑ τα στοιχεία σε ένα εύρος ικανοποιούν ένα κατηγόρημα;

3. Ποια είναι η χρονική πολυπλοκότητα του`std::nth_element`;

Προηγούμενο

Iterators: Η κόλλα STL

Επόμενο

Λάμδας & Λειτουργικός Προγραμματισμός