Ορισμός πίνακα με μήκος που καθορίζεται από το input

Question

Έστω ότι θέλω να δημιουργήσω έναν πίνακα με μέγεθος n. Και ζητάω από τον χρήστη να διαλέξει ουσιαστικά αυτό το n. Για ποιο λόγο δεν είναι σωστό το παρακάτω;

int n;
cin >> n; 
int array[n];

Και γιατί θα πρέπει να κάνω κάτι σαν κι αυτό;

int n;
cin >> n;
int *array = new int[n];

Comments

Σχετική ανάρτηση στο StackOverflow: c++ memory allocated at compile time

Answer 1

Disclaimer: Τη χρονική στιγμή που έγινε η ερώτηση, στο μάθημα progintro δεν έχουμε ακόμη φτάσει στα arrays.

---

Και τα δύο παραπάνω είναι σωστά στη C++. (Edit: Δες στο τέλος για μια ακριβέστερη απάντηση.) Η διαφορά τους είναι ότι το πρώτο δημιουργεί το array ως τοπική μεταβλητή μέσα στη συνάρτηση όπου βρίσκεται αυτός ο κώδικας (δηλαδή στη στοίβα), ενώ το δεύτερο το δημιουργεί ως δυναμική μεταβλητή (δηλαδή στο heap) και βάζει ένα δείκτη να δείχνει σε αυτό.

Ο λόγος που το δεύτερο είναι προτιμότερο είναι γιατί, αν η τιμή του n είναι μεγάλη, το array δε θα χωράει στη στοίβα και το πρόγραμμά σας θα τερματιστεί με κάποιο μήνυμα σφάλματος. Όμως, στο δεύτερο πρέπει ο προγραμματιστής να αποδεσμεύσει το χώρο του array, όταν δεν το χρειάζεται πια, κάνοντας delete [] array;. Αυτό είναι ένα μειονέκτημα αυτής της επιλογής.

Συμβουλή για τις ασκήσεις στον grader που προϋποθέτουν κάτι σαν το παραπάνω (να οριστεί ένας πίνακας με μήκος που καθορίζεται από το input): προτιμήστε μία από τις παρακάτω δύο επιλογές:

1. Χρησιμοποιήστε global array. Θα χρειαστεί να δείτε στην εκφώνηση της άσκησης ποιο είναι το μέγιστο μήκος του πίνακα (π.χ. 1000000 εδώ).

   int array[1000000];
       
   PROGRAM {
     int N = READ_INT();
     int i;
     FOR(i, 0 to N-1) array[i] = READ_INT();
     // whatever...
   }
   

   ή χωρίς το pzhelp και λίγο καλύτερα:

   #define MAXN 1000000
   int array[MAXN];
       
   int main() {
     int N;
     cin >> N;
     for (int i = 0; i < N; ++i) cin >> array[i];
     // whatever...
   }
   

2. Χρησιμοποιήστε vector (όχι για το progintro, το μαθαίνουμε στο 2ο εξάμηνο):

   #include <vector>
   using namespace std;
   
   int main() {
     int N;
     cin >> N;
     vector<int> array(N);
     for (int i = 0; i < N; ++i) cin >> array[i];
     // whatever...
   }
   

---

Edit: Τα arrays μεταβλητού μήκους δεν υποστηρίζονται από το standard της ISO C++. Δείτε μια σχετική συζήτηση στο SO. Όμως, υπάρχουν στη C99 και, μάλλον γι' αυτό, υποστηρίζονται από τον GNU C++ compiler και από τον clang++. Γι' αυτό στην αρχή του post γράφω ότι και τα δύο είναι σωστά στη C++. Αν θέλουμε να είμαστε αυστηροί, το πρώτο δεν είναι σωστό σύμφωνα με το ISO standard.

Answer 2

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

Η δήλωση int a[N]; μέσα σε μία συνάρτηση (εδώ, μέσα στην main) θα δεσμεύσει έναν πίνακα N θέσεων στο stack. Αντίθετα, η δήλωση int *array = new int[N]; θα δεσμεύσει μόνο μία θέση στο stack, για τον pointer array, και ο πίνακας Ν θέσεων θα δεσμευθεί στο heap όπου γενικά είμαστε πιο άνετοι από χώρο.

Οπότε αν το N είναι αρκετά μεγάλο, ο πίνακας δεν θα μπορέσει να αποθηκευθεί και το πρόγραμμα θα σκάσει κατά την εκτέλεση. (Τυπικά το stack θα μεγαλώσει πολύ προσπαθώντας να δεσμεύσει τον πίνακα, θα φτάσει σε περιοχή που δεν πρέπει να είναι και θα χτυπήσει ένα ωραίο segmentation fault)

Για αυτό είναι μια καλή πρακτική να δεσμεύετε πίνακες με τον 2ο τρόπο, αν θέλετε να το κάνετε μέσα σε συναρτήσεις.

Answer 3

Επειδή ο ορισμός πίνακα κατά την δήλωση μπορεί να σου ορίσει μόνο στατικούς πίνακες (και όχι δυναμικά μεταβαλλόμενου μεγέθους) οπότε απαιτεί να είναι σταθερά αυτό που είναι μέσα στην αγκύλη, πχ 42, ή 42 * 42, ή ακόμη και 17 + 42 + a όπου το a είναι ορισμένη σταθερά.

Στην πραγματικότητα, το int *array = new int[n]; που γράφεις δεν είναι μία, αλλά δύο λειτουργίες, μία δήλωση ενός δείκτη int *array; και μία ανάθεση array = new int[n]; που είναι χωριστή εντολή. Βέβαια, δεν ξέρω αν και πόσο έχετε μιλήσει μέχρι τώρα για δυναμικούς πίνακες και δείκτες, θα τα δείτε πολύ αναλυτικά αργότερα στο εξάμηνο αν όχι ακόμη.

Σε αυτό που αναφέρεις, το n δεν είναι σταθερά και επομένως δεν είναι έγκυρο αυτό που γράφεις.

Answer 4

Ουσιαστικά υπάρχουν δύο τρόποι που το πρόγραμμα σου κατανέμει (allocate) την μνήμη.

Ο ένας είναι στατικός (στατική κατανομή μνήμης), δηλαδή όταν κάνεις compile το πρόγραμμα, αυτό βλέπει ότι έχεις κατανείμει τον ακέραιο n και ενημερώνει την μνήμη ότι θα χρειαστεί ένα μπλόκ μεγέθους int. Το "μέρος" που αποθηκεύονται αυτά λέγεται σωρός (stack).

Ο δεύτερος είναι δυναμικός (δυναμική κατανομή μνήμης). Αυτός χρησιμοποιείται όταν δεν ξέρεις τα μεγέθη κατά το compile-time, όπως πχ στην εκτέλεση του προγράμματος σου που την τιμή του αριθμού n την θέτει ο χρήστης κατά την εκτέλεση. Το "μέρος" που αποθηκεύονται αυτά λέγεται στοίβα (heap).

Στην περίπτωση σου, το πρόβλημα είναι ότι όταν κάνεις compile, ο compiler δεν ξέρει πόσο χώρο να κατανείμει στην μεταβλητή σου, οπότε υπό κανονικές συνθήκες δεν θα έπρεπε να τρέξει (ο gcc έχει κάποια extensions και το υποστηρίζει αυτό).
Αν τρέξεις με το argument -pedantic (που σου βγάζει όλα τα warning σύμφωνα με το ISO πρότυπο της C++) θα σου εμφανίσει και το αντίστοιχο warning.

Για δυναμική μνήμη θα μιλήσετε και αργότερα στο μάθημα, αν δεν το έχετε κάνει ηδη.

Answer 5

Στη C++ πρέπει το μέγεθος ενός πίνακα να είναι σταθερό -- ήτοι, ήδη καθορισμένο την ώρα που θα μεταγλωττιστεί το πρόγραμμα. Γι'αυτό στην περίπτωσή σου οφείλεις να καταφύγεις στη δυναμική παραχώρηση μνήμης, με τον τρόπο που περιγράφεις.

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

#include <vector>
std::vector<int> v; // Δήλωση του διανύσματος
cin >> size; 
vec.resize(size) // Καθορισμός μεγέθους του

και π.χ. με το v[k] μπορείς να έχεις πρόσβαση στο σχετικό στοιχείο (αρκεί 0 <= k <= size-1)

(Σε περίπτωση που προτιμήσεις τα vectors, παραπέμπω στο σχετικό documentation.)