H Standard Template Libray (STL) είναι βιβλιοθήκη της C++ που αποτελεί αναπόσπαστο τμήμα της stardard βιβλιοθήκης της γλώσσας. Αποτελείται από κλάσεις για προσωρινή αποθήκευση πληροφορίας σε ένα πρόγραμμα που ονομάζονται containers, κλάσεις για διάτρεξη των containers (ονομάζονται iterators) και αλγορίθμους. Οι αλγόριθμοι είναι συναρτήσεις που κατά κανόνα λειτουργούν με την βοήθεια των iterators πάνω στους διαθέσιμους containers.

Βασικό χαρακτηριστικό της STL είναι ότι οι κλάσεις (containers και iterators) και οι συναρτήσεις των αλγορίθμων είναι γενικευμένες, ώστε να μπορούν να εφαρμοστούν με ασφάλεια σε οποιονδήποτε τύπο δεδομένων. Για να το επιτύχουν αυτό, χρησιμοποιούν templates.

Στο παρακάτω διάγραμμα περιέχονται το σύνολο των containers που παρέχει η βιβλιοθήκη STL.

Οι containers της STL διακρίνονται στις εξής κατηγορίες:

• Sequence containers: Αποθηκεύουν τα δεδομένα σειριακά, οδηγώντας σε χρόνους αναζήτησης γραμμικούς στο μέγεθος του πλήθους των στοιχείων που είναι αποθηκευμένα. Παραδείγματα τέτοιων containers είναι
  • array: Πίνακας σταθερού μεγέθους το οποίο προσδιορίζεται κατά τη δήλωση του πίνακα.
  • vector: Πίνακας μεταβλητού μεγέθους. Παρέχει δυνατότητα εισαγωγής στοιχείων σε οποιαδήποτε θέση του πίνακα. Η εισαγωγή/διαγραφή στο/από το τέλος του πίνακα είναι πράξη σταθερού κόστους, ενώ η εισαγωγή σε ή η διαγραφή από ενδιάμεση θέση συνεπάγεται την αντιγραφή των αποθηκευμένων στοιχείων που βρίσκονται μετά από τη συγκεκριμένη εγγραφή κατά μία θέση και είναι ανάλογη του μήκους αυτού.
  • dequeue: Πρόκειται για την γνωστή διπλοουρά που επιτρέπει την γρήγορη ένθεση και διαγραφή από την αρχή και το τέλος της ουράς. Για την εισαγωτή ή διαγραφή από ενδιάμεση θέση απαιτείται η αντιγραφή των στοιχείων που βρίσκονται πριν ή μετά τη συγκεκριμένη θέση κατά μία θέση και όπως και στην κλάση vector είναι ανάλογη του μήκους αυτού.
  • list: Πρόκειται για την διπλά συνδεδεμένη λίστα. Η λίστα δίνει την δυνατότητα διάτρεξης της δομής και προς τις δύο κατευθύνσεις, την εισαγωγή σε συγκεκριμένη θέση ή την διαγραφή στοιχείου από συγκεκριμένη θέση (δες σε αντιδιαστολή τη forward_list). Το κόστος αναζήτησης είναι ανάλογο των στοιχείων που είναι αποθηκευμένα στη λίστα, ενώ το κόστος εισαγωγής στοιχείου και διαγραφής στοιχείου είναι σταθερό. Η επιπλέον ευελιξία που παρέχεται σε σχέση με την forward list, έχει ως κόστος την διαχείριση ενός επιπλέον δείκτη σε κάθε κόμβο της λίστας σε σχέση με την απλά συνδεδεμένη λίστα.
  • forward_list: Πρόκειται για την απλά συνδεδεμένη λίστα. Η λίστα δίνει την δυνατότητα διάτρεξης της δομής προς τη μία κατεύθυνση (από την αρχή προς το τέλος). Για την εισαγωγή και διαγραφή θα πρέπει οπωσδήποτε να γνωρίζουμε τον προηγούμενο κόμβο (θέση). Το κόστος αναζήτησης είναι ανάλογο των στοιχείων που είναι αποθηκευμένα στη λίστα, ενώ το κόστος εισαγωγής στοιχείου και διαγραφής στοιχείου είναι σταθερό.
• Container Adapters: Χρησιμοποιούν εσωτερικά ένα sequence container για να υλοποιήσουν την λειτουργικότητα τους. Οι βασικές κλάσεις είναι οι εξής:
  • stack: Υλοποιεί μία δομή Last-In-First-Out (LIFO) με την βοήθεια ενός vector ή deque.
  • queue: Υλοποιεί μία δομή First-In-First-Out (FIFO) με την βοήθεια ενός deque.
  • priority_queue: Υλοποιεί μία ουρά προτεραιότητας. Προκειμένου να επιτευχθεί η προτεραιότητα κατά την εισαγωγή και διαγραφή στοιχείου εφαρμόζεται ο αλγόριθμος make_heap για την επίτευξη σωρού με λογαριθμικό κόστος στο μέγεθος των αποθηκευμένων στοιχείων της δομής.
• Associative Containers: Πρόκειται για δομές που τα στοιχεία εισάγονται ταξινομημένα σε αύξουσα σειρά. Η αποθήκευση γίνεται σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.Red–black_tree) και ο χρόνος αναζήτησης, εισαγωγής και διαγραφής είναι λογαριθμικός στο μέγεθος των αποθηκευμένων στοιχείων. Διακρίνονται σε sets που είναι σύνολα από μοναδικά στοιχεία-κλειδιά και maps που είναι συνολά από απεικονίσεις μοναδικών στοιχείων-κλειδιών σε τιμές. Παραλλαγές των παραπάνω κλάσεων είναι τα multiset και multimap όπου δίνεται η επιπλέον δυνατότητα αποθήκευσης περισσότερων του ενός ίδιων κλειδιών στην υφιστάμενη δομή.
• Unordered Associative Containers: Δομές ανάλογες με τους Associative Containers με την διαφορά ότι η αποθήκευση δεν γίνεται σε ισοζυγισμένο δέντρο αναζητήσεως, αλλά σε πίνακα κατακερματισμού (Hash_table). Για τον λόγο αυτό, τα στοιχεία δεν αποθηκεύονται ταξινομημένα, αλλά με “τυχαία” σειρά. Η σειρά διάτρεξης τους αντιστοιχεί στη σειρά που τα κλειδιά είναι αποθηκευμένα στον πίνακα κατακερματισμού. Ο μέσος χρόνος αναζήτησης, εισαγωγής και διαγραφής είναι σταθερός στο μέγεθος των αποθηκευμένων στοιχείων, ενώ ο απαιτούμενος χώρος είναι περισσότερος (κατ' ελάχιστο διπλάσιος από τον αριθμό των αποθηκευμένων στοιχείων στην δομή). Οι κλάσεις unordered_set και unordered_map επιτρέπουν την αποθήκευση μοναδικών κλειδιών, ενώ οι δομές unordered_multiset και unordered_multimap επιτρέπουν την αποθήκευση περισσότερων του ενός ιδίων στοιχείων-κλειδιών στη δομή.

Μία κλάση τύπου iterator έχει την δυνατότητα διάτρεξης μιας άλλης κλάσης που αντιπροσωπεύει μία δομή δεδομένων (container). O iterator συνήθως γνωρίζει την εσωτερική δομή της κλάσης και πως να μετακινηθεί ανάμεσα στα στοιχεία της. Ο iterator περιέχει κατ'ελάχιστο ένα δείκτη προς το τρέχον στοιχείο προς διάτρεξη του container. Όλοι οι iterators ανεξάρτητα από τον τύπο τους υποστηρίζουν τις λειτουργίες:

• T::iterator it(other_it): copy-constructor
• it = other_it: copy-assignment
• iterator destructor
• ++it ή it++: μετακίνηση κατά μία θέση μέσα στον container και επιστροφή ενός iterator που δείχνει στην τρέχουσα θέση ή στην προηγούμενη θέση του container αντιστοίχως.

Οι κατηγορίες των iterator είναι οι εξής:

• Input Iterator: Πρόκειται για έναν iterator από τον οποίο μπορούμε να διαβάσουμε το στοιχείο της δομής στο οποίο δείχνει, δηλαδή για έναν iterator ανάγνωσης του περιεχόμενου της δομής. Όλοι οι διαθέσιμοι iterators είναι και Input Iterators. Παράδειγμα:

  for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++)
    cout << *it << " ";
  cout << endl;

• Output Iterator: Πρόκειται για έναν iterator μέσω του οποίου μπορούμε να γράψουμε στο τρέχον στοιχείο του container. Οι iterators που στον τύπο τους περιέχουν το συνθετικό const_ (const_iterator, const_reverse_iterator) δεν ανήκουν στη συγκεκριμένη κατηγορία. Παραδείγματα:

  for(vector<int>::iterator it=ints.begin(); it!=ints.end(); it++) {
    *it += 10;                         // we modify container here
    cout << *it << " ";
  }
 
  for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++) {
    // *it += 10;       // this is not allowed for a const_iterator (only input iterator)
    cout << *it << " ";
  }

• Bidirectional Iterator: Πρόκειται για iterators που εκτός των πράξεων ++it, it++ υποστηρίζουν και τις πράξεις --it, it--. Bidirectional Iterators είναι όλοι οι iterators με εξαίρεση εκείνούς που ανήκουν σε Unordered Associative Containers και οι iterators του container forward_list (απλά συνδεδεμένη λίστα). Παραδείγματα:

  for(vector<int>::iterator it=ints.cbegin(); it!=ints.cend(); it++) {
    cout << *it << " ";
  }
  cout << endl;
 
  vector<int>::iterator it = ints.cend(); // starting from the end of the container
  while(true) {
    --it1;                                // move to the previous element
    cout << *it1 << " ";
    if(it1 == ints.cbegin())              // stop when we reach the first element
      break;
  }
  cout << endl;

• Random Access Iterators: Πρόκειται για iterators που υποστηρίζουν την πράξη της πρόσθεσης και τις αφαίρεσης μεταξύ του iterator και ενός ακεραίου αριθμού (η πράξη είναι ανάλογη της αριθμητικής δεικτών). Οι iterators αυτής της κατηγορίας υποστηρίζονται από τους Sequence Containers array, vector και deque αλλά όχι από τους containers list και forward_list. Παράδειγμα:

  vector<int>::iterator it = ints.cend(); // starting from the end of the container
  while(true) {
    it -= 2;                              // move back by 2 elements
    cout << *it1 << " ";
    if(it1 <= ints.cbegin())              // stop when we reach or we have passed the first element
      break;
  }
  cout << endl;

Για όλους τους iterators είναι διαθέσιμη η συνάρτηση advance η οποία μετακινεί τον iterator κατά όσες θέσεις προσδιορίζει το δεύτερο όρισμα (μπορεί να πάρει και αρνητικές τιμές για Bidirectional και Random Access iterators). Η συνάρτηση λειτουργεί με χρήση του τελεστή ++, μετακινώντας τον iterator κατά μία θέση κάθε φορά, όσες φορές απαιτείται.

Εάν θέλουμε να υπολογίσουμε την απόσταση μεταξύ δύο iterators παρέχεται η συνάρτηση distance η οποία υπολογίζει την απόσταση από το πρώτο όρισμα (first) έως το δεύτερο όρισμα (last) μετακινώντας τον δείκτη από first έως last με χρήση του τελεστή ++. Η συνάρτηση υποθέτει ότι το first βρίσκεται πριν από το last.

H STL παρέχει τις συναρτήσεις begin και end για την εύρεση της αρχικής και της τελικής θέσης ενός container]]. Η συνάρτήσεις συνοψίζονται στον εξής κώδικα (κοινό ανεξαρτήτως του container).

template <class Container>
  auto begin (Container& cont) -> decltype (cont.begin());
template <class Container>
  auto begin (const Container& cont) -> decltype (cont.begin());

template <class Container>
  auto end (Container& cont) -> decltype (cont.end());
template <class Container>
  auto end (const Container& cont) -> decltype (cont.end());

Παράδειγμα χρήσης:

iterator_begin_end.cpp

#include <iostream>     // std::cout
#include <vector>       // std::vector, std::begin, std::end
 
int main () {
  int foo[] = {10,20,30,40,50};
  std::vector<int> bar;
 
  // iterate foo: inserting into bar
  for (auto it = std::begin(foo); it!=std::end(foo); ++it)
    bar.push_back(*it);
 
  // iterate bar: print contents:
  std::cout << "bar contains:";
  for (auto it = std::begin(bar); it!=std::end(bar); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
 
  return 0;
}

Τα παρακάτω παραδείγματα εφαρμόζονται σε container τύπου vector, όμως ο κώδικας της διάτρεξης είναι κοινός για όλους τους containers.

fw_iterate.cpp

#include <vector>
#include <iostream>
#define SIZE 10
using namespace std;
 
int main() {
  vector<int> ints;
  for(int i=0; i<10; i++)
    ints.push_back(SIZE-i);
 
  for(vector<int>::const_iterator it=ints.cbegin(); it!=ints.cend(); it++)
    cout << *it << " ";
  cout << endl;
}

Παρατήρηση: Η συναρτήσεις cbegin και begin επιστρέφουν ένα iterator που δείχνει στο πρώτο στοιχείο του container. Αντίστοιχα, οι συναρτήσεις cend και end επιστρέφουν ένα iterator που δείχνει μετά το τελευταίο στοιχείο του container. O iterator διατρέχει τα στοιχεία από την αρχή προς το τέλος του container.

bw_iterate.cpp

#include <vector>
#include <iostream>
#define SIZE 10
using namespace std;
 
int main() {
  vector<int> ints;
  for(int i=0; i<10; i++)
    ints.push_back(SIZE-i);
 
  for(vector<int>::const_reverse_iterator it=ints.crbegin(); it!=ints.crend(); it++)
    cout << *it << " ";
  cout << endl;
}

Παρατήρηση: Η συναρτήσεις crbegin και rbegin επιστρέφουν ένα reverse_iterator που δείχνει στο τελευταίο στοιχείο του container. Αντίστοιχα, οι συναρτήσεις crend και rend επιστρέφουν ένα reverse_iterator που δείχνει μετά το πρώτο στοιχείο του container. O reverse_iterator διατρέχει τα στοιχεία από το τέλος προς την αρχή του container.

fw_iterate_modify.cpp

#include <vector>
#include <iostream>
#define SIZE 10
using namespace std;
 
int main() {
  vector<int> ints;
  for(int i=0; i<10; i++)
    ints.push_back(SIZE-i);
 
  for(vector<int>::iterator it=ints.begin(); it!=ints.end(); it++) {
    *it += 10;                         // we modify container here
    cout << *it << " ";
  }
  cout << endl;
}

bw_iterate_modify.cpp

#include <vector>
#include <iostream>
#define SIZE 10
using namespace std;
 
int main() {
  vector<int> ints;
  for(int i=0; i<10; i++)
    ints.push_back(SIZE-i);
 
  for(vector<int>::reverse_iterator it=ints.rbegin(); it!=ints.rend(); it++) {
    *it += 10;                         // we modify container here
    cout << *it << " ";
  }
  cout << endl;
}

TODO