ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ Τμήμα Ηλεκτρονικών Μηχ. και Μηχ. Υπολογιστών ΛΟΓ 201: Τεχνολογία Λογισμικού ΙΙ http://www.softlab.ntua.gr/~nickie/TUC/log201/

Containers και iterators

Container: [ελλ.] κιβώτιο

n 1 box, bottle, etc. designed to contain something.

Iterator: [ελλ.] επαναλήπτης

Φανταστική λέξη που δε βρίσκεται σε λεξικό.

Οι παραπάνω λέξεις στα αγγλικά έχουν καθιερωθεί στην προγραμματιστική ορολογία, ενώ οι αντίστοιχες ελληνικές δεν είναι γνωστές με την ίδια έννοια.

Containers | Iterators

Containers

Δομές δεδομένων όπως:

• οι πίνακες (arrays),
• οι συνδεδεμένες λίστες (linked lists),
• τα σύνολα (sets),
• οι ουρές (queues),
• οι στοίβες (stacks),
• τα δένδρα (trees), κ.α.

ονομάζονται containers. Οι κλάσεις της C++ που υλοποιούν τέτοιες δομές ονομάζονται container classes. Γενικά, τα containers είναι αντικείμενα που περιέχουν άλλα αντικείμενα. Για να είναι χρήσιμα, παρέχουν μεθόδους για τη διαχείριση των περιεχομένων όπως:

• προσθήκη αντικειμένων,
• αφαίρεση αντικειμένων,
• εξέταση αντικειμένων, κ.λπ.

Γενίκευση των container classes ώστε να μπορούν να περιέχουν αντικείμενα διαφορετικών τύπων αποτελούν τα container templates. Κάθε στιγμιότυπο ενός τέτοιου template είναι μια container class για ένα συγκεκριμένο τύπο T και μπορεί να περιέχει αντικείμενα αυτού του τύπου.

Ένα σύντομο παράδειγμα χρήσης ενός container template με μορφή ουράς (απόσπασμα από το παράδειγμα της 28/3/2000) είναι το ακόλουθο:

   Queue<int> qi;

   qi.insert(7);
   qi.insert(5);
   qi.remove();
   cout << qi.head() << "\n";
   qi.insert(30);
   cout << qi.head() << "\n";

Iterators

Πολλές φορές παρουσιάζεται η ανάγκη να διατρέξουμε όλα τα περιεχόμενα ενός container. Για το σκοπό αυτό έχουν κατασκευάζονται αντικείμενα που ονομάζονται iterators. Κάθε iterator είναι ένα αντικείμενο που, κατά την κατασκευή του, συνδέεται με ένα αντικείμενο container. Στη συνέχεια, διευκολύνει ίσως την κατανόηση να θεωρεί κανείς αυτόν τον iterator σα να ήταν ένας δείκτης σε κάποιο αντικείμενο που περιέχεται μέσα στο container.

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

• int get ();
  Η πρώτη κλήση της get τοποθετεί τον iterator στο πρώτο αντικείμενο που περιέχεται στον container. Κάθε επόμενη κλήση τον μεταφέρει στο επόμενο, κάθε φορά, αντικείμενο. H μέθοδος get επιστρέφει 0 όταν εξαντληθούν τα αντικείμενα που περιέχονται στον container, διαφορετικά επιστρέφει μη μηδενική τιμή.
• T current ();
  Η μέθοδος αυτή επιστρέφει κάθε φορά το τρέχον αντικείμενο στο οποίο είναι τοποθετημένος ο iterator.

Ένα σύντομο παράδειγμα χρήσης ενός iterator για το container template με μορφή ουράς (απόσπασμα και πάλι από το παράδειγμα της 28/3/2000) είναι το ακόλουθο, στο οποίο εκτυπώνονται κατά σειρά όλα τα περιεχόμενα της ουράς.

   QueueIterator<int> i(qi);

   while (i.get())
      cout << i.current() << "\n";

Είναι φυσικά δυνατό να ενσωματώσει κανείς τη λειτουργικότητα των iterators (δηλαδή τις μεθόδους get και current) μέσα στους containers. Ο διαχωρισμός τους όμως σε διαφορετικά αντικείμενα προσφέρει τα εξής σημαντικά πλεονεκτήματα:

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