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

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

Γραμμές και στήλες

Ένας δισδιάστατος πίνακας με $m$ γραμμές και $n$ στήλες είναι μια συλλογή $m \cdot n$ δεδομένων του ίδιου τύπου, καθένα από τα οποία προσδιορίζεται με δύο δείκτες: τον δείκτη της γραμμής του, $i$, με $0 \leq i < m$, και τον δείκτη της στήλης του, $j$, με $0 \leq j < n$. Τα μαθηματικά τον ονομάζουν πίνακα και γράφουν $a_{ij}$· ο κύκλος μαθημάτων «Άλγεβρα και γεωμετρία II» μελετά τους πίνακες και τις πράξεις τους, και αυτό το μάθημα γράφει μερικές από αυτές ως προγράμματα. Η σειρά των δεικτών δεν δέχεται εξαιρέσεις: πρώτα η γραμμή, έπειτα η στήλη. Η σύγχυσή τους είναι το συχνότερο σφάλμα με δισδιάστατους πίνακες, και ο μεταγλωττιστής δεν μπορεί να το επισημάνει, γιατί και οι δύο δείκτες είναι του ίδιου τύπου.

Το μάθημα Διανύσματα παρουσίασε την ακολουθία μεταβλητού μεγέθους. Αν αυτό ισχύει, ένας δισδιάστατος πίνακας είναι μια ακολουθία γραμμών, και κάθε γραμμή είναι με τη σειρά της μια ακολουθία: ένα διάνυσμα του οποίου τα στοιχεία είναι διανύσματα, std::vector<std::vector<int>>.

#include <print>#include <vector>​int main(){    std::vector<std::vector<int>> table{{1, 2, 3}, {4, 5, 6}};    std::println("{}", table);    std::println("Γραμμές {}, στήλες {}", table.size(), table[0].size());    std::println("Γραμμή 1: {}· γραμμή 1, στήλη 2: {}", table[1], table[1][2]);    table[0][1] = 20;    for (const std::vector<int>& row : table) {        for (const int value : row) {            std::print("{:>4}", value);        }        std::println("");    }    const std::vector<std::vector<int>> zeros(3, std::vector<int>(4));    std::println("{}", zeros);}

[[1, 2, 3], [4, 5, 6]]Γραμμές 2, στήλες 3Γραμμή 1: [4, 5, 6]· γραμμή 1, στήλη 2: 6   1  20   3   4   5   6[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Η γραμμή 6 του προγράμματος γράφει τον πίνακα ως λίστα γραμμών, την καθεμία μέσα στα άγκιστρά της, και η μορφοποίηση εύρους τον τυπώνει με τον ίδιο τρόπο, με αγκύλες. Το table.size() είναι το πλήθος των γραμμών, και το table[0].size() το μήκος της πρώτης, που σε έναν σωστά σχηματισμένο πίνακα είναι το πλήθος των στηλών. Το table[1] είναι ολόκληρη η γραμμή 1, ένα std::vector<int>, και το table[1][2] το στοιχείο 2 αυτής της γραμμής: ο διπλός δείκτης δεν είναι νέα πράξη, αλλά δύο διαδοχικές προσβάσεις, από τις οποίες η πρώτη επιλέγει τη γραμμή και η δεύτερη, μέσα σε αυτήν, τη στήλη. Οι γραμμές 11 έως 16 του προγράμματος γράφουν τον πίνακα ως ορθογώνιο σχήμα με δύο εμφωλευμένους βρόχους for εύρους· η γραμμή του πίνακα λαμβάνεται με σταθερή αναφορά, ώστε να μην αντιγράφεται σε κάθε γύρο. Η γραμμή 17 δημιουργεί έναν πίνακα 3 επί 4 γεμάτο μηδενικά: με παρενθέσεις, όπως στο μάθημα Διανύσματα, ζητούνται 3 αντίγραφα μιας γραμμής τεσσάρων μηδενικών.

Γραμμές διαφορετικού μήκους

Τίποτα δεν υποχρεώνει τις γραμμές ενός διανύσματος διανυσμάτων να έχουν το ίδιο μήκος: η καθεμία είναι ένα ανεξάρτητο διάνυσμα. Μερικές φορές αυτό ακριβώς θέλουμε, όπως στο τρίγωνο του Πασκάλ· αλλά σε έναν δισδιάστατο πίνακα, ορθογώνιο εξ ορισμού, μια κοντύτερη γραμμή είναι σφάλμα των δεδομένων, και το πρόγραμμα που χρησιμοποιεί το table[0].size() ως πλήθος στηλών διαβάζει έξω από αυτήν. Ένας πίνακας που έρχεται απ’ έξω πρέπει, επομένως, να ελέγχεται.

#include <print>#include <vector>​// Προσυνθήκη: καμία.// Μετασυνθήκη: επιστρέφει true αν ο table έχει τουλάχιστον μία γραμμή και όλες οι// γραμμές του έχουν το μήκος της πρώτης.bool isRectangular(const std::vector<std::vector<int>>& table){    if (table.empty()) {        return false;    }    for (const std::vector<int>& row : table) {        if (row.size() != table[0].size()) {            return false;        }    }    return true;}​int main(){    const std::vector<std::vector<int>> pascal{{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}};    const std::vector<std::vector<int>> grid{{1, 2, 3}, {4, 5, 6}};    std::println("{} {}", pascal, isRectangular(pascal));    std::println("{} {}", grid, isRectangular(grid));}

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]] false[[1, 2, 3], [4, 5, 6]] true

Η συνάρτηση αποκλείει τον πίνακα χωρίς γραμμές, στον οποίο το table[0] δεν υπάρχει. Οι συναρτήσεις αυτού του μαθήματος που διαβάζουν το table[0].size() απαιτούν στην προσυνθήκη τους έναν πίνακα ορθογώνιο και μη κενό, και η isRectangular επιτρέπει να εξασφαλιστεί.

Ο πίνακας πινάκων

Όταν οι διαστάσεις είναι γνωστές κατά τη μεταγλώττιση (μια σκακιέρα, ένα μαγικό τετράγωνο), ο δισδιάστατος πίνακας μπορεί να είναι ένας std::array από std::array: το std::array<std::array<int, 3>, 3> διαβάζεται από μέσα προς τα έξω, «3 γραμμές των 3 ακεραίων». Ως παράδειγμα χρησιμεύει το μαγικό τετράγωνο τάξης 3, του οποίου οι γραμμές, οι στήλες και οι διαγώνιοι έχουν άθροισμα 15.

#include <array>#include <print>​int main(){    constexpr std::array<std::array<int, 3>, 3> magic{{        {2, 7, 6},        {9, 5, 1},        {4, 3, 8},    }};    std::println("{}", magic);    std::println("Κέντρο {}, {} byte", magic[1][1], sizeof(magic));}

[[2, 7, 6], [9, 5, 1], [4, 3, 8]]Κέντρο 5, 36 byte

Τα άγκιστρα είναι τρία σε κάθε άκρο. Ο std::array έχει ένα μόνο μέλος, έναν πίνακα της C, οπότε το εξωτερικό άγκιστρο είναι του std::array, το δεύτερο αυτού του εσωτερικού πίνακα, και μόνο το τρίτο κάθε γραμμής. Με δύο άγκιστρα, η πρώτη γραμμή λαμβάνεται ως αρχικοποιητής του εσωτερικού πίνακα, και η δεύτερη δεν έχει πια τι να αρχικοποιήσει.

#include <array>#include <print>​int main(){    const std::array<std::array<int, 3>, 2> table{{1, 2, 3}, {4, 5, 6}};    std::println("{}", table);}

main.cpp: In function ‘int main()’:main.cpp:6:71: error: too many initializers for ‘const std::array<std::array<int, 3>, 2>’    6 |     const std::array<std::array<int, 3>, 2> table{{1, 2, 3}, {4, 5, 6}};      |                                                                       ^

Too many initializers: περισσεύει η λίστα {4, 5, 6}. Η επίπεδη λίστα, {1, 2, 3, 4, 5, 6}, μεταγλωττίζεται κι αυτή και γεμίζει τις γραμμές με τη σειρά, αλλά κρύβει το σχήμα του πίνακα· ο κύκλος μαθημάτων γράφει τα τρία άγκιστρα.

Τα 36 byte του sizeof είναι αυτά εννέα int των 4 byte (το συνηθισμένο μέγεθος, που το πρότυπο δεν εγγυάται), χωρίς τίποτε άλλο: ο πίνακας πινάκων αποθηκεύει τις γραμμές τη μία μετά την άλλη σε ένα μόνο μπλοκ μνήμης. Το διάνυσμα διανυσμάτων, αντίθετα, ζητά ένα μπλοκ ανά γραμμή, εκτός από το μπλοκ των γραμμών, και αυτά τα μπλοκ δεν είναι κατ’ ανάγκην συνεχόμενα. Η επιλογή ακολουθεί, επομένως, τον κανόνα των μαθημάτων Πίνακες σταθερού μεγέθους και Διανύσματα.

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