Σύνθετα δεδομένα: σύνθεση και προκλήσεις

Όσα πέτυχε η ενότητα

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

Πίνακες σταθερού μεγέθους

Το μάθημα Πίνακες σταθερού μεγέθους παρουσίασε τον std::array, την ακολουθία σταθερού μεγέθους, της οποίας οι δείκτες μετρούν από το μηδέν επειδή είναι μετατοπίσεις. Καθιέρωσε ότι ο δείκτης $i$ είναι έγκυρος αν και μόνο αν $0 \leq i < n$, ότι κάθε πρόσβαση με [] απαιτεί να αποδειχθεί αυτό με την αναλλοίωτη του βρόχου, και ότι η πρόσβαση εκτός ορίων είναι απροσδιόριστη συμπεριφορά, την οποία η .at() μετατρέπει σε καθορισμένη διακοπή· εισήγαγε τον std::size_t και δίδαξε την ανάγνωση των πινάκων της C.

Διανύσματα

Το μάθημα Διανύσματα παρουσίασε την ακολουθία που μεγαλώνει με push_back και καθόρισε πότε χρειάζεται να αποθηκευτεί μια σειρά: αν κάποια απόφαση για ένα δεδομένο εξαρτάται από μεταγενέστερα δεδομένα. Καθιέρωσε τις κανονικές διασχίσεις (συσσώρευση, φιλτράρισμα, μετασχηματισμός) με τις αναλλοίωτές τους και τις συντομεύσεις τους στη βιβλιοθήκη (std::ranges::count, std::ranges::max, std::ranges::fold_left), τον κανόνα μεταβίβασης ενός διανύσματος, και τη διαφορά ανάμεσα σε μέγεθος και χωρητικότητα, από την οποία προκύπτουν το κατά μέσο όρο σταθερό κόστος του push_back και η ακύρωση των αναφορών όταν το διάνυσμα μετακομίζει.

Το κόστος ενός αλγορίθμου

Το μάθημα Το κόστος ενός αλγορίθμου πρόσθεσε το δεύτερο ερώτημα: να καταμετράμε την κυρίαρχη πράξη στη χειρότερη περίπτωση, να κατατάσσουμε κατά τάξη αύξησης, να προβλέπουμε το αποτέλεσμα του διπλασιασμού του $n$ και να μετράμε με το std::chrono::steady_clock, με βελτιστοποίηση, χωρίς ανιχνευτές, επαναλαμβάνοντας και παίρνοντας τη διάμεσο.

Αναζήτηση και ταξινόμηση

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

Δισδιάστατοι πίνακες

Το μάθημα Δισδιάστατοι πίνακες διέσχισε τους δισδιάστατους πίνακες κατά γραμμές και κατά στήλες, υπολόγισε τον ανάστροφο και το γινόμενο πινάκων, με το κυβικό του κόστος, μέτρησε γειτονικά κελιά χωρίς να βγει από τα άκρα και αποθήκευσε έναν δισδιάστατο πίνακα σε ένα μονοδιάστατο διάνυσμα με τον δείκτη $i \cdot \mathit{columns} + j$.

Εγγραφές

Το μάθημα Εγγραφές αντικατέστησε τα παράλληλα διανύσματα με το struct, με αρχική τιμή σε κάθε πεδίο· δίδαξε πώς μεταβιβάζονται και πώς επιστρέφονται εγγραφές, πώς ταξινομούνται και πώς αναζητούνται κατά ένα πεδίο με μια προβολή, πώς ταξινομούνται με πολλά κριτήρια με τη std::ranges::stable_sort και πώς μοντελοποιείται ένα πρόβλημα με εγγραφές που περιέχουν εγγραφές και διανύσματα.