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

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

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

Η βιβλιοθήκη της C++ μπορεί να χωριστεί στις παρακάτω κατηγορίες:
  1. Γενικές λειτουργίες
  2. Λειτουργίες μετατροπής και αρχείων (iostreams)
  3. Αλγόριθμοι με τη χρήση ενός επαναλήπτη (iterator) πάνω σε έναν περιέχοντα (container). Οι λειτουργίες αυτές αποτελούν τη βιβλιοθήκη με το όνομα Standard Template Library (STL).
  4. Συμβατότητα με τη 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. Μερικές μέθοδοι που ορίζονται σε επαναλήπτες είναι οι παρακάτω: Για κάθε περιέχοντα ορίζονται μέθοδοι όπως (στην περίπτωση της διπλής ουράς):
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
χαρακτηρισμός "πλατιών" χαρακτήρων

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

Ασκήσεις

Άσκηση 7

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