Υλοποίηση με έτοιμες βιβλιοθήκες

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Η βιβλιοθήκη της C++

Η βιβλιοθήκη της C++ μπορεί να χωριστεί στις παρακάτω κατηγορίες:

Γενικές λειτουργίες
Λειτουργίες μετατροπής και αρχείων (iostreams)
Αλγόριθμοι με τη χρήση ενός επαναλήπτη (iterator) πάνω σε έναν περιέχοντα (container). Οι λειτουργίες αυτές αποτελούν τη βιβλιοθήκη με το όνομα Standard Template Library (STL).
Συμβατότητα με τη C

Οι τρεις πρώτες κατηγορίες της βιβλιοθήκης ορίζονται σε επικεφαλίδες χωρίς το επίθεμα .h. Για να μην υπάρχει πιθανότητα τα ονόματα που ορίζονται στις επικεφαλίδες να ταυτίζονται με ονόματα που ορίζει ο χρήστης, τα ονόματα που ορίζουν οι επικεφαλίδες αυτές βρίσκονται απομονωμένα σε έναν ξεχωριστό χώρο ονομάτων (namespace) με το πρόθεμα "std::". Για να τα χρησιμοποιήσουμε στο πρόγραμμά μας χωρίς το πρόθεμα αυτό μπορούμε μετά τις επικεφαλίδες να δηλώσουμε:

using namespace std;

Στις επόμενες ενότητες περιγράφουμε συνοπτικά μόνο τις γενικές λειτουργίες της βιβλιοθήκης και με περισσότερες λεπτομέρειες τις λειτουργίες της STL.

Γενικές λειτουργίες

Η γενικές λειτουργίες της βιβλιοθήκης της C++ είναι οι παρακάτω:

bitset

κλάση προτύπων (ως προς το μέγιστο πληθάριθμο του συνόλου) που επεξεργάζεται σύνολο από bit

complex

κλάση προτύπων (ως προς τον τύπου των δύο στοιχείων) μιγαδικών αριθμών. Εξειδικεύσεις της κλάσης είναι μιγαδικοί αριθμοί float, double και long double.

exception

συναρτήσεις χειρισμού διακοπών

limits

ιδιότητες αριθμητικών τιμών

locale

προσαρμογή του προγράμματος σε τοπικά χαρακτηριστικά. Περιλαμβάνονται πρότυπες κλάσεις που ορίζουν:

τον τρόπο μετατροπής μεταξύ χαρακτήρων
τη σειρά ταξινόμησης
το χαρακτηρισμό χαρακτήρων
τη μετατροπή νομισματικών τιμών
τη μετατροπή αριθμητικών τιμών
τη μετατροπή τιμών που παριστάνουν χρόνο
τη μετατροπή μηνυμάτων προς το χρήστη

stdexcept

κλάσεις για αναφορά διακοπών

string

πρότυπη κλάση που ορίζει σειρές αντικειμένων μεταβλητού μήκους. Εξειδίκευση της κλάσης αυτής είναι οι συμβολοσειρές.

valarray

πρότυπη (ως προς το περιεχόμενο του πίνακα) κλάση που επιτρέπει το μαζικό χειρισμό πινάκων

Παράδειγμα χρήσης μιγαδικών αριθμών

Το παρακάτω παράδειγμα αθροίζει δύο μιγαδικούς αριθμούς:

#include <complex>
#include <iostream>

using namespace std;

main()
{
        complex <double> a, b, c;

        cin >> a >> b;
        c = a + b;
        cout << c << "\n";
}

Είσοδος:

(4,2)
(1,10)

Αποτέλεσμα:

(5,12)

Παράδειγμα χρήσης συμβολοσειρών

Το παρακάτω παράδειγμα αθροίζει δύο συμβολοσειρές:

#include <string>
#include <iostream>

using namespace std ;

void main()
{
   string result;
   string s1="hello";
   string s2=", world";

   cout << "s1 is " << s1 << "\n";
   cout << "s2 is " << s2 << "\n";

   result=s1+s2;
   cout << "s1+s2 is " << result << "\n";
}

Αποτέλεσμα:

s1 is hello
s2 is , world
s1+s2 is hello, world

Λειτουργίες μετατροπής και αρχείων

Οι επικεφαλίδες iostreams υποστηρίζουν τη μετατροπή μεταξύ κειμένων και της εσωτερική μορφή παράστασης των τύπων καθώς και είσοδο και έξοδο από και σε εξωτερικά αρχεία. Ορίζονται οι παρακάτω επικεφαλίδες:

fstream: πρότυπες κλάσεις iostreams για το χειρισμό εξωτερικών αρχείων
iomanip: δήλωση χειριστών iostreams
ios: βασική κλάση προτύπων iostreams
iosfwd: δήλωση προτύπων κλάσεων iostreams πριν από τον ορισμό τους
iostream: δήλωση των βασικών αντικειμένων iostreams
istream: πρότυπη κλάση που εξάγει στοιχεία
ostream: πρότυπη κλάση που εισάγει στοιχεία
sstream: πρότυπες κλάσεις iostreams που αναφέρονται σε συμβολοσειρές
streambuf: πρότυπες κλάσεις που προσφέρουν ενταμιευτές σε κλάσεις iostreams
strstream: κλάσεις iostreams που λειτουργούν σε στοιχεία που βρίσκονται στη μνήμη

Περιέχοντες και επαναλήπτες στην STL

Η STL ορίζει μια σειρά από περιέχοντες (containers) όπως την ουρά, τη στοίβα, την απεικόνιση και τον πίνακα. Πάνω στους περιέχοντες αυτούς επιτρέπει την εκτέλεση αλγορίθμων, όπως την εύρεση ενός στοιχείου, η ένωση δύο περιεχόντων, η ταξινόμηση, κ.λπ.

Στην STL ορίζονται οι παρακάτω πρότυποι (ως προς τα στοιχεία που περιέχουν) περιέχοντες:

list: διπλά συνδεδεμένη λίστα
queue: ουρά
deque: ουρά με πρόσβαση και στις δύο άκρες
map: απεικόνιση (π.χ. από συμβολοσειρές σε ακέραιους)
set: απεικόνιση με μοναδικά στοιχεία στο πεδίο τιμών
stack: στοίβα
vector: πίνακας

Η πρόσβαση των στοιχείων ενός περιέχοντα από τους αλγορίθμους γίνεται μέσω επαναληπτών (iterators). Οι επαναλήπτες - ανάλογα με τη δομή των δεδομένων του περιέχοντα - μπορούν να επιτρέπουν την παρακάτω ιεραρχία κινήσεων:

Τυχαία προσπέλαση
Κίνηση προς τις δύο κατευθύνσεις
Κίνηση προς τα εμπρός, ή ανάποδη κίνηση

Επίσης, μπορούν να επιτρέπουν την παρακάτω ιεραρχία πρόσβασης στα δεδομένα που δείχνουν:

Είσοδο και έξοδο
Μόνο είσοδο, ή μόνο έξοδο

Η κλάση των επαναληπτών ορίζεται στην επικεφαλίδα iterator. Μερικές μέθοδοι που ορίζονται σε επαναλήπτες είναι οι παρακάτω:

advance
distance
==, !=, <, >, >=, <=
+, -
++, --

Για κάθε περιέχοντα ορίζονται μέθοδοι όπως (στην περίπτωση της διπλής ουράς):

assign: ανάθεση τιμής
at: αναφορά σε στοιχείο
back: το τελευταίο στοιχείο
begin: επαναλήπτης που δείχνει στην αρχή της δομής
clear: διαγραφή όλων των στοιχείων
empty: αληθές αν η δομή είναι άδεια
end: επαναλήπτης που δείχνει στο τέλος της δομής
erase: διαγραφή σειράς στοιχείων
front: το πρώτο στοιχείο
insert: προσθήκη στοιχείου
operator[]: πρόσβαση σε στοιχείο
pop_back: αφαίρεση στοιχείου από το τέλος
pop_front: αφαίρεση στοιχείου από την αρχή
push_back: προσθήκη στοιχείου στο τέλος
push_front: προσθήκη στοιχείου στην αρχή
rbegin: ανάστροφος επαναλήπτης που δείχνει στην αρχή της δομής
rend: ανάστροφος επαναλήπτης που δείχνει στο τέλος της δομής
resize: καθορισμός του αριθμού των στοιχείων
size: αριθμός των στοιχείων
swap: εναλλαγή δύο στοιχείων μεταξύ τους

Παράδειγμα 1: ουρές

Το παρακάτω παράδειγμα ορίζει μια διπλή ουρά ακεραίων, προσθέτει 5 στοιχεία και τα τυπώνει:

#include <iostream>
#include <deque>

using namespace std;

typedef deque <int>  INTDEQUE;

void main()
{

        // Create A and fill it with elements 1,2,3,4 and 5
        // using push_back function
        INTDEQUE  A;

        A.push_back(1);
        A.push_back(2);
        A.push_back(3);
        A.push_back(4);
        A.push_back(5);

        // Print the contents of A using iterator
        // and functions begin() and end()
        INTDEQUE::iterator pi;

        for (pi = A.begin();  pi != A.end(); pi++)
                cout << *pi << " ";
        cout << "\n";
}

Παράδειγμα 2: απεικόνιση

Το παρακάτω παράδειγμα τυπώνει πόσες φορές εμφανίστηκε κάθε λέξη στην είσοδο του προγράμματος:

#include <map>
#include <iostream>
#include <string>

using namespace std;

typedef map <string, int> smap_t;

int
main()
{
        string s;
        smap_t m;                       // Our map

        while (!cin.eof()) {
                cin >> s;
                m[s]++;                 // Use overloaded [] operator
        };

        smap_t::iterator i;             // Iterator for printing the results
        for (i = m.begin(); i != m.end(); i++)
                cout << i->first << " " << i->second << endl;
        return (0);
}

Πρόσθετες λειτουργίες στην STL

Επικεφαλίδα algorithm

Στην επικεφαλίδα algorithm ορίζονται μέθοδοι που ενεργούν πάνω σε περιέχοντες:

adjacent_find: βρίσκει δύο ίσα στοιχεία σε διπλανές θέσεις
binary_search: δυαδική ανίχνευση
copy: αντιγραφή περιοχής
copy_backward: αντίστροφη αντιγραφή περιοχής
count: μέτρημα
count_if: μέτρημα υπό συνθήκη
equal: σύγκριση περιοχών
equal_range: σύγκριση περιοχών με συγκεκριμένη ακρίβεια
fill: πλήρωση περιοχής με τιμή
fill_n: πλήρωση αριθμού στοιχείων με τιμή
find: εύρεση στοιχείου
find_end: εύρεση στοιχείου από το τέλος
find_first_of: εύρεση στοιχείου ίσου με κάποιο μέλος από σύνολο στοιχείων
find_if: εύρεση στοιχείου που να ικανοποιεί συνθήκη
for_each: εκτέλεση συνάρτησης για όλα τα στοιχεία σε περιοχή
generate: πλήρωση περιοχής με αποτέλεσμα συνάρτησης
generate_n: πλήρωση αριθμού στοιχείων με αποτέλεσμα συνάρτησης
includes: έλεγχος αν μια περιοχή εμπεριέχει μια άλλη
inplace_merge: σύζευξη δεδομένων στον ίδιο περιέχοντα
iter_swap: εναλλαγή δύο τιμών
lexicographical_compare: σύγκριση δύο περιοχών α, β για α < β
lower_bound: εύρεση μιας ελάχιστης τιμής σε περιοχή σε σχέση με μιαν άλλη τιμή
make_heap: μετατροπή περιοχής σε σωρό (heap) (δυαδικό δένδρο στο οποίο τα παιδιά έχουν τιμή μικρότερη ή ίση από αυτή των γονέων τους).
max: το μέγιστο από δύο στοιχεία
max_element: εύρεση του μέγιστου στοιχείου σε περιοχή
merge: σύζευξη δύο περιοχών σε τρίτη
min: το ελάχιστο από δύο στοιχεία
min_element: εύρεση του ελαχίστου στοιχείου σε περιοχή
mismatch: εύρεση του πρώτου διαφορετικού στοιχείου ανάμεσα σε δύο περιοχές
next_permutation: υπολογισμός της επόμενης μετάθεσης σε μια περιοχή
nth_element: θέτει ένα στοιχείο στη θέση που θα έπρεπε να έχει αν η περιοχή ήταν ταξινομημένη
partial_sort: ταξινομεί τα πρώτα στοιχεία μιας περιοχής
partial_sort_copy: ταξινομεί τα πρώτα στοιχεία μιας περιοχής σε μιαν άλλη
partition: χωρίζει μια περιοχή στα δύο με βάση μια συνάρτηση και επιστρέφει το σημείο που είναι ο χωρισμός
pop_heap: αφαίρεση στοιχείου από σωρό
prev_permutation: υπολογισμός της προηγούμενης μετάθεσης σε μια περιοχή
push_heap: προσθήκη στοιχείου από σωρό
random_shuffle: ανακατεύει μια περιοχή
remove: αφαιρεί στοιχεία ίσα με μια τιμή
remove_copy: αφαιρεί στοιχεία ίσα με μια τιμή μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
remove_copy_if: αφαιρεί στοιχεία για τα οποία μια συνάρτηση είναι αληθής μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
remove_if: αφαιρεί στοιχεία για τα οποία μια συνάρτηση είναι αληθής
replace: αλλάζει τιμή σε στοιχεία ίσα με μια τιμή
replace_copy: αλλάζει τιμή σε στοιχεία ίσα με μια τιμή μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
replace_copy_if: αλλάζει τιμή σε στοιχεία για τα οποία μια συνάρτηση είναι αληθής μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
replace_if: αλλάζει τιμή σε στοιχεία για τα οποία μια συνάρτηση είναι αληθής
reverse: αντιστρέφει τη σειρά σε μια περιοχή
reverse_copy: αντιστρέφει τη σειρά σε μια περιοχή μεταφέροντάς την σε μιαν άλλη περιοχή
rotate: περιστρέφει τη σειρά των στοιχείων σε μια περιοχή
rotate_copy: περιστρέφει τη σειρά των στοιχείων σε μια περιοχή μεταφέροντάς την σε μιαν άλλη περιοχή
search: εύρεση σειράς στοιχείων σε μια περιοχή ίσης με στοιχεία μιας άλλης
search_n: εύρεση σειράς στοιχείων σε μια περιοχή ίσης με αριθμό στοιχείων μιας άλλης
set_difference: θέτει μια περιοχή ίση με τη διαφορά των στοιχείων δύο άλλων περιοχών (διαφορά συνόλων)
set_intersection: θέτει μια περιοχή ίση με την τομή των στοιχείων δύο άλλων περιοχών (τομή συνόλων)
set_symmetric_difference: θέτει μια περιοχή ίση με τα μη κοινά των στοιχείων δύο άλλων περιοχών
set_union: θέτει μια περιοχή ίση με την ένωση των στοιχείων δύο άλλων περιοχών (ένωση συνόλων)
sort: ταξινομεί μια περιοχή
sort_heap: ταξινομεί έναν σωρό
stable_partition: χωρίζει μια περιοχή στα δύο με βάση μια συνάρτηση και επιστρέφει το σημείο που είναι ο χωρισμός. Ο χωρισμός γίνεται χωρίς να αλλάξει η σχετική σειρά των στοιχείων.
stable_sort: ταξινομεί μια περιοχή. Η ταξινόμηση γίνεται χωρίς να αλλάξει η σχετική σειρά των στοιχείων που είναι μεταξύ τους ίσα.
swap: αντιστρέφει μεταξύ τους δύο στοιχεία
swap_ranges: αντιστρέφει μεταξύ τους δύο περιοχές
transform: εφαρμόζει έναν τελεστή σε μια περιοχή ή μεταξύ δύο περιοχών
unique: αφαιρεί τα όμοια στοιχεία από μια περιοχή
unique_copy: αφαιρεί τα όμοια στοιχεία από μια περιοχή μεταφέροντάς την σε μιαν άλλη περιοχή
upper_bound: εύρεση μιας μέγιστης τιμής σε περιοχή σε σχέση με μια άλλη τιμή

Επικεφαλίδα numeric

Στην επικεφαλίδα algorithm ορίζονται αριθμητικές μέθοδοι που ενεργούν πάνω σε περιέχοντες:

accumulate: υπολογίζει ένα σύνολο πάνω σε μια περιοχή
adjacent_difference: υπολογίζει τις διαφορές τιμών μεταξύ στοιχείων μιας περιοχής
inner_product: υπολογίζει ένα εσωτερικό γινόμενο μεταξύ δύο περιοχών
partial_sum: υπολογίζει ένα μερικό άθροισμα τιμών μιας περιοχής σε μιαν άλλη

Άλλες επικεφαλίδες

Ακόμα στην STL ορίζονται οι παρακάτω επικεφαλίδες:

utility: πρότυπη κλάση που ορίζει διάταξη σε ζεύγη τιμών
functional: κλάση που επιτρέπει συναρτησιακό προγραμματισμό
memory: ορίζει την κλάση allocator η οποία κατανέμει τη μνήμη σε όλους τους περιέχοντες. Ο επανακαθορισμός της επιτρέπει την υλοποίηση άλλων στρατηγικών καταμερισμού και πρόσβασης στη μνήμη.

Συμβατότητα με τη C

Ακόμα παρέχονται επικεφαλίδες που παρέχουν υπηρεσίες όμοιες με τις αντίστοιχες της γλώσσας C. Καλό είναι οι επικεφαλίδες αυτές να χρησιμοποιούνται μόνο όταν απαιτείται συμβατότητα με κληρονομημένο (legacy) (παλιό) κώδικα.

cassert: απόδειξη ιδιοτήτων κατά την εκτέλεση συναρτήσεων
cctype: χαρακτηρισμός χαρακτήρων
cerrno: πρόσβαση στα λάθη από την εκτέλεση συναρτήσεων της βιβλιοθήκης
cfloat: ιδιότητες αριθμών κινητής υποδιαστολής
ciso646: ορισμός λέξεων που επιτρέπουν τον προγραμματισμό σε συστήματα με τις κωδικοσελίδες ISO 646 (δεν αφορά την Ελλάδα)
climits: ιδιότητες των ακεραίων
clocale: προσαρμογή του προγράμματος σε τοπικά χαρακτηριστικά
cmath: μαθηματικές συναρτήσεις
csetjmp: αδόμητη μετάβαση ελέγχου μεταξύ συναρτήσεων
csignal: έλεγχος διακοπών
cstdarg: πρόσβαση σε ορίσματα με μεταβλητό αριθμό παραμέτρων
cstddef: ορισμός χρησίμων τύπων
cstdio: είσοδος και έξοδος όμοια με τη C
cstdlib: πρόσβαση στις αντίστοιχες συναρτήσεις της C
cstring: επεξεργασία συμβολοσειρών της C
ctime: χρήση ώρας και ημερομηνίας
cwchar: επεξεργασία "πλατιών" χαρακτήρων
cwctype: χαρακτηρισμός "πλατιών" χαρακτήρων

Βιβλιογραφία

Standard Template Library Programmer's Guide http://www.sgi.com/Technology/STL/ (http://www.sgi.com/Technology/STL/)
Microsoft Developer Network Library Visual Studio Documentation - Visual C++ - Reference - C/C++ Language and C++ Libraries - Standard C++ Library Reference

Matthew H. Austern. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1998.

Ασκήσεις

Άσκηση 7

Με βάση τον περιέχοντα της STL queue και μονοτονικά αυξανόμενη μεταβλητή να υλοποιηθεί πρόγραμμα το οποίο να υλοποιεί ουρά εξυπηρέτησης πελατών ως εξής:
1. Όταν εισάγεται ο χαρακτήρας I (In) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του νέου πελάτη.
2. Όταν εισάγεται ο χαρακτήρας O (Out) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του επόμενου πελάτη που θα εξυπηρετηθεί.
Παράδειγμα:
```
I
1
I
2
I
3
O
1
I
4
O
2
...
```

Περιεχόμενα