Iterators: Η κόλλα STL

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

The Iterator Abstraction

Οι επαναληπτικοί είναι η κόλλα μεταξύ δοχείων STL και αλγορίθμων. Αντί να γράφει N αλγόριθμους για M κοντέινερ (N*M υλοποιήσεις), το STL ορίζει μια κοινή διεπαφή επαναλήπτη. Κάθε κοντέινερ παρέχει επαναλήπτες και κάθε αλγόριθμος λειτουργεί σε εύρη επαναληπτικών — δίνοντας N+M υλοποιήσεις που λειτουργούν μαζί.

Ένας επαναλήπτης είναι ένα αντικείμενο που:
1. Δείχνει ένα στοιχείο σε μια ακολουθία
2. Μπορεί να αποαναφερθεί (*it) για πρόσβαση στο στοιχείο
3. Μπορεί να αυξηθεί (++it) για να μετακινηθεί στο επόμενο στοιχείο
4. Μπορεί να συγκριθεί (it != end) για να ανιχνεύσει το τέλος της ακολουθίας

Διαφορετικές κατηγορίες επαναλήψεων υποστηρίζουν διαφορετικά σύνολα πράξεων, σχηματίζοντας μια ιεραρχία από το πιο αδύναμο προς το ισχυρότερο.

Κατηγορίες Iterator

Οι κατηγορίες επαναλήψεων C++ σχηματίζουν μια ιεραρχία (κάθε επίπεδο περιλαμβάνει τις δυνατότητες όλων των επιπέδων παρακάτω):

| Κατηγορία | Λειτουργίες | Παράδειγμα Εμπορευματοκιβωτίων |
|---|---|---|
| Είσοδος | Ανάγνωση, ένα πέρασμα προς τα εμπρός (++,*,==) |istream_iterator|
| Έξοδος | Εγγραφή, με ένα πέρασμα προς τα εμπρός (++,*=) |ostream_iterator,back_inserter|
| Εμπρός | Ανάγνωση/εγγραφή, πολλαπλή μετάβαση προς τα εμπρός |forward_list,unordered_set|
| Αμφίδρομη | Εμπρός + πίσω (--) |list,set,map|
| Τυχαία πρόσβαση | Αμφίδρομα + άλματα (+n,-n,[],<) |deque|
| Συνεχής (C++17) | Τα στοιχεία τυχαίας πρόσβασης + βρίσκονται δίπλα στη μνήμη |vector,array,string|

Οι αλγόριθμοι δηλώνουν την ελάχιστη κατηγορία που απαιτούν. Τοstd::sortχρειάζεται επαναλήπτες τυχαίας πρόσβασης, επομένως λειτουργεί με τοvectorαλλά όχι με τοlist(το οποίο παρέχει τη δική του λειτουργία μέλουςsort()).

Η σύμβαση έναρξης/λήξης

Κάθε κοντέινερ STL παρέχειbegin()καιend()— ένα μισάνοιχτο εύρος[begin, end)όπου τοendδείχνει ένα μετά το τελευταίο στοιχείο. Οι δωρεάν λειτουργίεςstd::begin()καιstd::end()λειτουργούν με κοντέινερ, συστοιχίες C και οποιονδήποτε τύπο παρέχει μέλη.begin()και.end().

begin_end.cpp

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

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

    // Member functions
    auto first = vec.begin();   // points to 5
    auto last  = vec.end();     // points past 2

    // Free functions — preferred for generic code
    auto first2 = std::begin(vec);
    auto last2  = std::end(vec);

    // Works with C-arrays too
    int arr[] = {10, 20, 30};
    std::sort(std::begin(arr), std::end(arr));

    // const iterators — read-only access
    auto cit = vec.cbegin();     // const_iterator
    // *cit = 99;                // ERROR: cannot modify through const_iterator

    // Reverse iterators — iterate backward
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << ' ';  // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
    }
    std::cout << '\n';
}

Iterator Utilities: next, prev, advance, distance

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

iterator_utils.cpp

#include <iterator>
#include <vector>
#include <list>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // std::next — returns iterator n positions forward (default 1)
    auto it = std::next(vec.begin(), 2);   // points to 30
    std::cout << *it << '\n';              // 30

    // std::prev — returns iterator n positions backward
    auto it2 = std::prev(vec.end());       // points to 50
    std::cout << *it2 << '\n';             // 50

    // std::advance — modifies iterator in place (no return)
    auto it3 = vec.begin();
    std::advance(it3, 3);                  // now points to 40
    std::cout << *it3 << '\n';             // 40

    // std::distance — number of increments from first to last
    auto d = std::distance(vec.begin(), vec.end());  // 5
    std::cout << "Distance: " << d << '\n';

    // These work with non-random-access iterators too
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = std::next(lst.begin(), 2);  // O(n) for list, O(1) for vector
    std::cout << *lit << '\n';             // 3

    auto ld = std::distance(lst.begin(), lst.end());  // O(n) for list
    std::cout << "List distance: " << ld << '\n';     // 5
}

Εισαγωγή Iterators και Stream Iterators

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

insert_stream_iterators.cpp

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

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

    // back_inserter — calls push_back on each assignment
    std::copy(src.begin(), src.end(), std::back_inserter(dst));
    // dst: {1, 2, 3, 4, 5}

    // front_inserter — calls push_front (works with deque, list)
    // inserter — calls insert at a given position

    // ostream_iterator — write to an output stream
    std::copy(dst.begin(), dst.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << '\n';  // 1, 2, 3, 4, 5,

    // istream_iterator — read from an input stream
    std::istringstream iss("10 20 30 40");
    std::vector<int> from_stream(
        std::istream_iterator<int>(iss),
        std::istream_iterator<int>()   // end-of-stream sentinel
    );
    // from_stream: {10, 20, 30, 40}
}

Παγίδα

Η αύξηση ενός επαναλήπτη μετά τοend()ή η μείωση του παρελθόντος τουbegin()είναι απροσδιόριστη συμπεριφορά. Το ίδιο ισχύει και για την αποσύνδεση τουend()— είναι φρουρός, όχι έγκυρο στοιχείο.

Ένα συνηθισμένο λάθος είναι να γράψετε τοit + 1χωρίς να ελέγξετε εάν τοitβρίσκεται ήδη στο τέλος ή κοντά στο τέλος:

auto it = vec.end();
++it;    // UB — past-the-end
*it;     // UB — dereferencing end()

Always check iterator validity before operations. Use std::next and std::prev με ελέγχους απόστασης ή χρησιμοποιήστε βάσει εύρους για βρόχους που χειρίζονται τα όρια αυτόματα.

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

Όταν γράφετε γενικές συναρτήσεις που λειτουργούν σε ακολουθίες:

1. Αποδεχτείτε ζεύγη επαναλήπτη (ή εύρη σε C++20) αντί για συγκεκριμένα κοντέινερ
2. Χρησιμοποιήστεtypenameήautoγια τον τύπο επαναλήπτη
3. Χρησιμοποιήστεstd::distanceαντί για αφαίρεση (που απαιτεί τυχαία πρόσβαση)
4. Χρησιμοποιήστεstd::next/std::prevαντί για αριθμητική+/-
5. Στο C++20, προτιμήστε έννοιες για να περιορίσετε τις απαιτήσεις επαναλήπτη:

template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }

Αυτό διασφαλίζει ότι ο κώδικάς σας λειτουργεί με την ευρύτερη γκάμα κοντέινερ.

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

Οι επαναλήπτες αποσυνδέουν δοχεία από αλγόριθμους — η βασική αρχή σχεδιασμού του STL
Υπάρχουν έξι κατηγορίες επαναλήψεων: είσοδος, έξοδος, προώθηση, αμφίδρομη, τυχαία πρόσβαση, συνεχής
Χρησιμοποιήστε δωρεάν συναρτήσειςstd::begin()/std::end()για γενικό κώδικα που λειτουργεί με κοντέινερ και πίνακες C
Ταstd::next,std::prev,std::advance,std::distanceλειτουργούν σε όλες τις κατηγορίες επαναλήψεων
Εισαγάγετε επαναλήπτες (back_inserter,front_inserter,inserter) αφήστε τους αλγόριθμους να αναπτύξουν κοντέινερ
Ποτέ μην αναιρείτε τοend()ή μην το προσαυξάνετε — και τα δύο είναι απροσδιόριστη συμπεριφορά

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

(15 XP)

1. Ποια κατηγορία επαναλήπτη απαιτεί το`std::sort`;

2. Τι δημιουργεί το`std::back_inserter(vec)`;

3. Ποια είναι η χρονική πολυπλοκότητα του`std::distance(first, last)`σε ένα`std::list`;

Προηγούμενο

Προσαρμογείς Εμπορευματοκιβωτίων & Ειδικά Εμπορευματοκιβώτια

Επόμενο

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