Μετάβαση στο περιεχόμενο
Topos Uranos
Ελληνικά

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

Περίληψη

Ως εδώ κάθε δεδομένο του κύκλου μαθημάτων ζούσε στη δική του μεταβλητή, με το δικό του όνομα· όμως πολλά δεδομένα του ίδιου τύπου, όπως οι θερμοκρασίες μιας εβδομάδας, δεν μπορούν να διατρεχθούν με βρόχο αν το καθένα έχει διαφορετικό όνομα. Αυτό το μάθημα παρουσιάζει την πρώτη δομή δεδομένων του κύκλου, την ακολουθία με δείκτες: στοιχεία του ίδιου τύπου, σε διαδοχικές θέσεις της μνήμης, αριθμημένες από το μηδέν. Στη σύγχρονη C++ γράφεται με το std::array, του οποίου το μέγεθος καθορίζεται κατά τη μεταγλώττιση. Μελετώνται η δήλωσή του, ο τύπος std::size_t των δεικτών και οι δύο διασχίσεις, με δείκτη και με το for εύρους. Θεσπίζεται ο κανόνας που διέπει όλη την ενότητα: ένας δείκτης είναι έγκυρος αν βρίσκεται μεταξύ 0 και του μεγέθους μείον ένα, και σε κάθε πρόσβαση μέσα σε βρόχο η εγκυρότητα αυτή αιτιολογείται με την αναλλοίωτη. Δείχνεται τι συμβαίνει όταν δεν τηρείται, πράγμα που είναι απροσδιόριστη συμπεριφορά, και συγκρίνεται το [] με την ελεγχόμενη πρόσβαση .at(). Τέλος, παρουσιάζονται οι πίνακες της C, για να διαβάζουμε ξένο κώδικα.

Μαθησιακοί στόχοι

  1. Να δηλώνουμε, να αρχικοποιούμε και να διατρέχουμε ένα std::array με δείκτες και με το for εύρους.
  2. Να αιτιολογούμε, μέσω της αναλλοίωτης του βρόχου, ότι ένας δείκτης βρίσκεται μέσα στα όρια σε κάθε πρόσβαση.
  3. Να διακρίνουμε την πρόσβαση με [], που το πρότυπο δεν ελέγχει, από την πρόσβαση με .at(), που ελέγχεται πάντα, και να εξηγούμε πότε ενδείκνυται η καθεμία.
  4. Να διαβάζουμε κώδικα με πίνακες της C και να εξηγούμε τα μειονεκτήματά τους σε σύγκριση με το std::array.

Η ακολουθία με δείκτες

Πολλά δεδομένα, ένα μόνο όνομα

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

Μια ακολουθία με δείκτες είναι ακριβώς αυτό: ένα σύνολο nn στοιχείων του ίδιου τύπου, αποθηκευμένων το ένα πίσω από το άλλο σε διαδοχικά κελιά της μνήμης, που προσδιορίζονται από τη θέση τους, η οποία λέγεται δείκτης. Τα μαθηματικά γνωρίζουν το αντικείμενο: μια πεπερασμένη ακολουθία (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1}), όπου το aia_i δηλώνει το στοιχείο της θέσης ii, ή ένα διάνυσμα, όπως εκείνα του κύκλου μαθημάτων Άλγεβρα και γεωμετρία I. Στη C++ γράφεται a[i], και ο δείκτης μπορεί να είναι οποιαδήποτε ακέραια έκφραση: 2, i, i + 1.

Γιατί από το μηδέν

Στη C++, όπως στις περισσότερες σύγχρονες γλώσσες, το πρώτο στοιχείο έχει δείκτη 0, και το τελευταίο δείκτη n−1n - 1. Ο λόγος δεν είναι μια αυθαίρετη σύμβαση, αλλά ο τρόπος με τον οποίο βρίσκεται ένα στοιχείο: αν η ακολουθία αρχίζει σε κάποια διεύθυνση μνήμης και κάθε στοιχείο καταλαμβάνει ss byte, το στοιχείο με δείκτη ii βρίσκεται στην αρχική διεύθυνση συν i⋅si \cdot s. Ο δείκτης είναι επομένως μια μετατόπιση: το πλήθος των στοιχείων που πρέπει να προσπεράσουμε ξεκινώντας από το πρώτο. Το πρώτο απέχει μηδέν άλματα από τον εαυτό του.

Από αυτό προκύπτει ο ορισμός που διέπει όλη αυτή την ενότητα: σε μια ακολουθία nn στοιχείων, ένας δείκτης ii είναι έγκυρος αν και μόνο αν 0≤i<n0 \leq i < n. Η δεξιά ανισότητα είναι γνήσια, και είναι η πηγή του πιο συχνού σφάλματος με ακολουθίες, του σφάλματος κατά ένα: να γράψουμε i≤ni \leq n εκεί όπου έπρεπε να γραφτεί i<ni < n, ή να αρχίσουμε από το 1 εκεί όπου έπρεπε να αρχίσουμε από το 0. Ένας δείκτης ίσος με nn δεν προσδιορίζει το τελευταίο στοιχείο, αλλά το κελί που ακολουθεί την ακολουθία, το οποίο δεν της ανήκει.