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 επιτρέπουν την αποθήκευση περισσότερων του ενός ιδίων στοιχείων-κλειδιών στη δομή.

Κατά την ένθεση ενός στοιχείου σε ένα container, δημιουργείται πάντοτε ένα αντίγραφο του στοιχείου σε αυτόν. Για παράδειγμα, για την ένθεση στοιχείων της παρακάτω κλάσης Student μέσα σε ένα list τα στοιχεία θα αντιγραφούν εντός του vector ως εξής:

Student.hpp

#ifndef _STUDENT_HPP_
#define _STUDENT_HPP_
#include<cstring>
#include<iostream>
 
class Student {
public:
  char *name;
  int aem;
 
public:
  Student();
  Student(const char *name, int aem);
  Student(const Student& );
  ~Student();
  friend std::ostream& operator<<(std::ostream& out, const Student & st);
  bool operator>(const Student& st) const;
  Student& operator=(const Student& st);
};
 
Student::Student(const char *name, int aem) {
  this->name = new char [strlen(name) + 1];
  strcpy(this->name, name);
  this->aem = aem;
  std::cerr << "Argu Construct : " << *this << std::endl;
}
 
Student::Student(const Student& st) {
  name = new char [strlen(st.name) + 1];
  strcpy(name, st.name);
  aem = st.aem;
  std::cerr << "Copy Construct : " << *this << std::endl;
}
 
Student::Student() {
  this->name = nullptr;
  this->aem = 0;
}
 
Student::~Student() {
  if(name != nullptr) {
    std::cerr << "Destruct: " << *this << std::endl;
    delete []name;
  }
}
 
Student& Student::operator=(const Student& st) {
  if(name != nullptr)
    delete name;
  name = new char [strlen(st.name) + 1];
  strcpy(name, st.name);
  aem = st.aem;
  std::cerr << "Copy : " << *this << std::endl;
  return *this;
}
 
std::ostream& operator<<(std::ostream& out, const Student& st) {
  if(st.name != nullptr)
    out << st.name << " " << st.aem;
  return out;
}
 
bool Student::operator>(const Student& st) const {
  if(aem > st.aem)
    return true;
  return false;
}
#endif

student_list.cpp

#include <iostream>     // std::cout
#include <algorithm>    // std::copy
#include <list>       // std::list
#include <array>        // std::array
#include "Student.hpp"
 
int main () {
  Student students[] = { Student("Peter_Pan", 1234), Student("Tinker_Bell", 1235), 
                          Student("Captain_Hook", 1236), Student("Roger_Rabbit", 1237),
                          Student("Pink_Panther", 1238)                               };
 
  std::cerr << "----- Init list -----" << std::endl;
  std::list<Student> mylist;
  for(int i=0; i<5; i++) {
    mylist.push_back(students[i]);
    //mylist.insert(mylist.end(),students[i]);                         // equivalent with push_back
    //mylist.emplace_back(students[i].name, students[i].aem);
    //mylist.emplace(mylist.end(), students[i].name, students[i].aem); // equivalent with emplece_back
  }
 
  std::cerr << "-------------------------\n";
  std::cerr << "mylist contains:";
  for (std::list<Student>::iterator it = mylist.begin(); it!=mylist.end(); ++it)
    std::cerr << ' ' << *it;
  std::cerr << std::endl;
  std::cerr << "-------------------------\n";
 
  return 0;
} 

Το παραπάνω πρόγραμμα εκτυπώνει τα εξής:

Argu Construct : Peter_Pan 1234
Argu Construct : Tinker_Bell 1235
Argu Construct : Captain_Hook 1236
Argu Construct : Roger_Rabbit 1237
Argu Construct : Pink_Panther 1238
----- Init list -----
Copy Construct : Peter_Pan 1234
Copy Construct : Tinker_Bell 1235
Copy Construct : Captain_Hook 1236
Copy Construct : Roger_Rabbit 1237
Copy Construct : Pink_Panther 1238
-------------------------
mylist contains: Peter_Pan 1234 Tinker_Bell 1235 Captain_Hook 1236 Roger_Rabbit 1237 Pink_Panther 1238
-------------------------
Destruct: Peter_Pan 1234
Destruct: Tinker_Bell 1235
Destruct: Captain_Hook 1236
Destruct: Roger_Rabbit 1237
Destruct: Pink_Panther 1238
Destruct: Pink_Panther 1238
Destruct: Roger_Rabbit 1237
Destruct: Captain_Hook 1236
Destruct: Tinker_Bell 1235
Destruct: Peter_Pan 1234

Κατά την εισαγωγή ενός στοιχείου μέσω των συναρτήσεων insert, insert_back, emplace, emplace_back δημιουργείται ένα νέο αντικείμενο μέσω στον container. Η δημιουργία του αντικείμένου γίνεται είτε μέσω του copy-constructor (μέθοδοι insert, insert_back) ή μέσω του κατασκευαστή που λαμβάνει τα ορίσματα που περνιούνται στις μεθόδους emplace και emplace_back.

Όταν στην STL προσδιορίζεται ένα εύρος στοιχείων εντός ενός container μεταξύ των υποτιθέμενων θέσεων start και stop (προσδιορίζονται πάντοτε από iterators) το διάστημα το οποιό υπολογίζεται είναι από start (συμπεριλαμβανομένου) έως και stop (μη συμπεριλαμβανομένου)

Με εξαίρεση την κλάση std::array που το μέγεθος των πινάκων που δημιουργεί είναι σταθερό οι υπόλοιποι containers μπορούν να μεταβάλλουν το αριθμό των στοιχείων που αποθηκεύουν. Για την εισαγωγή ενός στοιχείου σε έναν container υπάρχει η συνάρτηση μέλους insert. Για sequence containers η insert λαμβάνει ως πρώτο όρισμα έναν iterator που δηλώνει τη θέση εισαγωγής