STL (Standard Template Library)

Ένα σημαντικό πλεονέκτημα της C++ έναντι άλλων γλωσσών είναι ότι παρέχει πλήθος δομικών στοιχείων για ανάπτυξη κώδικα. Αυτά τα στοιχεία συμπεριλαμβάνονται στη βιβλιοθήκη STL. H STL περιέχει τρεις βασικές συνιστώσες:
  • Containers (περιέχοντες): δομές για αποθήκευση και διαχείριση δεδομένων, υποκατάστατα των πινάκων αλλά με περισσότερες δυνατότητες. Μεταξύ άλλων έχουμε containers που περιλαμβάνουν αυτόματη ταξινόμηση (set, map) ή ταχύτατη ανάκτηση δεδομένων με ακέραιο δείκτη (vector).
  • Iterators (επαναλήπτες): ένα είδος δείκτη για τις θέσεις των στοιχείων ενός container. Έχουν την ίδια μορφή για όλα τα containers.
  • Αλγόριθμους: υλοποιούν τμήματα κώδικα όπως ταξινόμηση, αναζήτηση ή αντικατάσταση στοιχείου.

Pairs
Με τα pairs μπορούμε να δημιουργήσουμε ζευγάρια δυο διαφορετικών τύπων δεδομένων. Η δημιουργία ενός ζεύγους γίνεται με τη χρήση της εντολής make_pair.


Vectors
Τα vectors είναι μια δομή δεδμένων η οποία έχει όλες τις ιδιότητες ενός δυναμικού πίνακα χωρίς προκαθορισμένο μέγεθος. Χρήσιμες συναρτήσεις:
  • push_back - Εισάγει ένα στοιχείο στο τέλος της δομής και εκχωρεί αυτόματα μνήμη
  • pop_back - Διαγράφει το τελευταίο στοιχείο του vector
  • erase - Σβήνει ένα ή μια σειρά στοιχείων από το vector
  • clear - Διαγράφονται όλα τα στοιχεία του vector
  • front - Παραπέμπει στο πρώτο στοιχείο του vector
  • back - Παραπέμπει στο τελευταίο στοιχείο του vector
  • size - Επιστρέφει το πλήθος των στοιχείων που υπάρχουν στο vector
  • empty - Επιστρέφει true αν το vector δεν έχει κανένα στοιχείο
  • assign - Αρχικοποίηση του vector με συγκεκριμένο μέγεθος και τιμές στοιχείων


Lists
Οι λίστες είναι δομές δεδομένων οι οποίες επιτρέπουν την εισαγωγή/εξαγωγή στοιχείων και από τα δύο άκρα. Χρήσιμες επιπρόσθετες συναρτήσεις από τα vectors:
  • sort - Ταξινομεί τα στοιχεία
  • push_front - Εισάγει ένα στοιχείο στην αρχή
  • pop_front - Διαγράφει το πρώτο στοιχείο
  • remove - Διαγράφει ένα στοιχείο με συγκεκριμένη τιμή
  • advance (it,n) - Η θέση του iterator αλλάζει κατά n θέσεις
  • unique - Αφαιρεί τις επαναλαμβανόμενες τιμές


Stacks
Οι στοίβες είναι μια δομή τύπου LIFO (Last-In-First-Out), το τελευταίο στοιχείο που θα προστεθεί στην στοίβα θα αφαιρεθεί πρώτο. Χρήσιμες συναρτήσεις:
  • push(item) - Με τη συνάρτηση push γίνεται εισαγωγή ενός στοιχείου στην κορυφη της στοίβας
  • pop() - Με τη συνάρτηση pop γίνεται εξαγωγή ενός στοιχείου από την κορυφή της στοίβας
  • top() - Η συνάρτηση top επιστρέφει το στοιχείο που βρίσκεται στην κορυφή της στοίβας, χωρίς να το αφαιρέσει
  • empty() - Η συνάρτηση empty επιστρέφει true αν η στοίβα είναι άδεια, αλλιώς επιστρέφει false
  • size() - Η συνάρτηση size επιστρέφει το πλήθος των στοιχείων της στοίβας


Queues - Priority Queues
Είναι μια δομή τύπου FIFO(First In First Out), το πρώτο στοιχείο που εισέρχεται θα είναι το πρώτο που θα αφαιρεθεί. Η ουρά προτεραιότητας (priority queue), επιτρέπει την εξαγωγή δεδομένων με βάση κάποιας προτεραιότητας.
  • push(item) - Εισαγωγή στοιχείου στην ουρά. Συγκεκριμένα εισάγει το αντικείμενο item στο πίσω μέρος της ουράς. Στην ουρά προτεραιότητας το στοιχείο τοποθετείται μέσα στην ουρά με βάση την προτεραιότητα που έχει
  • front() - Επιστρέφει το πρώτο στοιχείο της ουράς χωρίς να το αφαιρέσει
  • pop() - Διαγράφει/αφαιρεί το στοιχείο που βρίσκεται στην αρχική/μπροστινή θέση μιας μη άδειας ουράς
  • back() - Επιστρέφει το τελευταίο στοιχείο της ουράς χωρίς να το αφαιρέσει
  • top() - Επιστρέφει το στοιχείο με την μεγαλύτερη προτεραιότητα (για ουρές προτεραιότητας) χωρίς να το αφαιρέσει
  • empty() - Επιστρέφει true αν η ουρά είναι άδεια και false διαφορετικά
  • size() - Επιστρέφει το πλήθος των στοιχείων της ουράς


Set / Multiset
Αποθηκεύει μοναδικά αντικείμενα, τα οποία είναι οργανωμένα σε ένα δυαδικό δέντρο.
  • insert(a) - Εισάγει το στοιχείο a
  • erase(a) - Διαγράφει το στοιχείο a
  • clear() - Διαγράφει όλα τα στοιχεία του s
  • count(a) - Επιστρέφει το πλήθος των στοιχείων με τιμή a
  • find(a) - Επιστρέφει iterator στη θέση του στοιχείου a ή αν δεν βρεθεί επιστρέφει end()


Map / Multimap
Με τα map και multimap αποθηκεύουμε ζεύγη στοιχείων στα οποία το πρώτο μέλος (first), έχει το ρόλο του κλειδιού (key) και το δεύτερο μέλος (second) είναι η αντίστοιχη τιμή του. Το multimap μπορεί να δεχτεί περισσότερα από ένα ζεύγη με το ίδιο κλειδί ενώ το map δεν επιτρέπει να εισάγουμε κλειδί που ήδη υπάρχει.



Αλγόριθμοι
Θα χρησιμοποιήσουμε τη βιβλιοθήκη <algorithm> η οποία περιέχει αλγόριθμους που μπορούν να μας βοηθήσουν να λύσουμε προβλήματα γρηγορότερα αφού εξοικονομούμε χρόνο στο γράψιμο κώδικα.

Αναζήτηση
  • binary_search(v.begin,v.end(),value) - Δυαδική αναζήτηση σε vector
  • binary_search(array, array + N, value) - Δυαδική αναζήτηση σε array
  • min(var1, var2) - Eπιστρέφει τη μικρότερη τιμή
  • max(var1, var2) - Eπιστρέφει τη μεγαλύτερη τιμή

Ταξινόμηση
  • sort(v.begin(),v.end()) - Ταξινόμηση vector
  • sort(array, array + N) ; - Ταξινόμηση πίνακα
  • sort(v.begin(),v.end(),smaller) - Tαξινόμηση vector με χρήση comparator