STL

Standard Template Library (STL)

• Σχέση της C με την C++
  • standard βιβλιοθήκες
• STL
• STL containers
  • iterators
• initializer list
• pair
• vector
• string
• list
• priority_queue
• set
• map
• unordered_map
• multiset, multimap και unordered_multimap
• Σύνοψη των λειτουργιών των container
• algorithm
  • sort()
  • min() και max()
  • lower_bound(), upper_bound(), equal_range() και binary_search()
• Πλεονεκτήματα και μειονεκτήματα των containers της STL

Σχέση της C με την C++

Θα ξεκινήσουμε αυτήν την παράγραφο με μια εισαγωγή σχετικά με την σχέση μεταξύ C και C++. Μπορούμε άτυπα να χωρίσουμε την C++ σε δύο μέρη, τα οποία θα ονομάζουμε συναρτησιακό και αντικειμενοστραφές μέρος. Στους διαγωνισμούς ασχολούμαστε μόνο με το συναρτησιακό μέρος. Ο όρος «συναρτησιακός προγραμματισμός» προκύπτει από την χρήση συναρτήσεων και τελεστών (που είναι και αυτοί συναρτήσεις) σχεδόν σε κάθε γραμμή των προγραμμάτων μας.

Η σχέση που συνδέει τις δύο γλώσσες C και C++ είναι σχέση εξέλιξης, διότι η C++ είναι ουσιαστικά η μετεξέλιξη της C. Δηλαδή, η C++ προέκυψε από την συναρτησιακή γλώσσα προγραμματισμού C με προσθήκη του αντικειμενοστραφούς μέρους. Η γλώσσα C φυσικά υπάρχει αυτούσια και χρησιμοποιείται ευρέως, ενώ μάλιστα ό,τι ξέρεις από το συναρτησιακό μέρος της C++ ισχύει κανονικά και στην γλώσσα C, με ελάχιστες εξαιρέσεις. Επομένως μέχρι στιγμής γνωρίζεις να προγραμματίζεις με δύο γλώσσες, την C και την C++! Αλήθεια, δοκίμασε να γράψεις ένα πρόγραμμα σε C!

standard βιβλιοθήκες

Όπως ξέρουμε η γλώσσα C++ (και η C) περιέχει ελάχιστες εντολές. Η λειτουργικότητα και το πλήθος των δυνατοτήτων της εξασφαλίζεται μέσω των βιβλιοθηκών που περιέχουν έτοιμες συναρτήσεις. Τέτοιες βιβλιοθήκες μπορούν να δημιουργηθούν από τον καθένα, με βάση τις ήδη υπάρχουσες. Για να τις χρησιμοποιήσει ένας άλλος προγραμματιστής πρέπει να τις προμηθευτεί και να τις εγκαταστήσει στο προγραμματιστικό του περιβάλλον. Για να υπάρχει όμως ένα κοινό πλαίσιο αναφοράς και δυνατοτήτων, η C και η C++ συνοδεύονται πάντα από τις standard βιβλιοθήκες τους.

Καθώς όμως η C++ είναι η μετεξέλιξη της C και το συναρτησιακό κομμάτι της C++ ταυτίζεται με την γλώσσα C, μπορούμε να χρησιμοποιήσουμε σε ένα πρόγραμμα C++ και τις βιβλιοθήκες της C! Σε κάθε λοιπόν προγραμματιστικό περιβάλλον C++ είναι διαθέσιμες οι standard βιβλιοθήκες της C και της C++. Αυτό όμως δεν ισχύει ανάποδα, δηλαδή σε προγραμματιστικό περιβάλλον C είναι διαθέσιμες μόνο οι βιβλιοθήκες της C. Για να συμπεριλάβουμε μια βιβλιοθήκη χρησιμοποιούμε την εντολή #include. Για να συμπεριλάβουμε μια βιβλιοθήκη της c πρέπει να βάλουμε ένα μικρό c μπροστά από το όνομα της:

#include <cstdio> //βιβλιοθήκη stdio
#include <cmath>  //βιβλιοθήκη math

Για να συμπεριλάβουμε μια βιβλιοθήκη της C++ χρησιμοποιούμε την ίδια σύνταξη, χωρίς όμως το μικρό c.

#include <algorithm>
#include <iostream>
using namespace std;

Πρόσεξε ότι μαζί με τις δηλώσεις των βιβλιοθηκών γράψαμε και την εντολή using namespace std; Όλο το περιεχόμενο των βιβλιοθηκών της C++ βρίσκεται δηλωμένο μέσα στο namespace std. Αυτό γίνεται για διάφορους λόγους που ξεφεύγουν από τους σκοπούς αυτού του βιβλίου. Με την εντολή αυτή δηλώνουμε ότι θα χρησιμοποιούμε σε όλο μας το πρόγραμμα τα περιεχόμενα των βιβλιοθηκών της C++ που δηλώσαμε. Οι standard βιβλιοθήκες των C και C++ είναι αχανείς. Εμείς όμως θα χρησιμοποιούμε ένα μικρό μέρος αυτών. Σου προτείνω να ανατρέξεις στο εγχειρίδιο της standard βιβλιοθήκης της C++ για να εντοπίσεις μόνος σου τις βιβλιοθήκες που είναι χρήσιμες για εσένα.

STL

H standard βιβλιοθήκη της C++ ονομάζεται STL, συντομογραφία για το standard template library. Καθώς το επιπλέον μέρος που διαθέτει η C++ αλλά όχι η C είναι ο αντικειμενοστραφής προγραμματισμός, είναι λογικό η STL να περιέχει στοιχεία αντικειμενοστραφούς προγραμματισμού. Αυτός είναι και ο λόγος που δεν μπορούμε να την χρησιμοποιήσουμε σε προγράμματα της C και τελικά, η STL γίνεται ο λόγος για τον οποίον χρησιμοποιούμε C++ και όχι C στους διαγωνισμούς. Αρκετά όμως με την C, ας επανέλθουμε στο θέμα μας. Η STL μας παρέχει έτοιμες υλοποιημένες συναρτήσεις, με βασικότερη την συνάρτηση sort() που ταξινομεί πίνακες με βέλτιστη πολυπλοκότητα. Οι υπόλοιπες συναρτήσεις που περιέχει είναι απλές και εύκολες για να τις υλοποιήσουμε μόνοι μας, είναι απλά συντομεύσεις και δεν θα αναλυθούν. Θα αναφερθούν μόνο οι συναρτήσεις swap(), min(), max(), prev(), next(), των οποίων η χρήση θα προτιμάται έναντι δικού μας κώδικα. Εκτός όμως από συναρτήσεις, η STL παρέχει και έτοιμες δομές δεδομένων, η γνώση των οποίων είναι απαραίτητη. Έτσι κλείνει η εισαγωγή περί standard βιβλιοθηκών και ξεκινάει το ζουμί αυτού του άρθρου.

STL containers

Τα containers είναι κλάσεις σχεδιασμένες για να αποθηκεύουν δεδομένα. Για απλότητα μπορείς να θεωρήσεις ότι μια κλάση είναι ένα κατασκευαστικό σχέδιο, ένα καλούπι. Με βάση λοιπόν μια κλάση μπορούμε να φτιάξουμε ένα αντικείμενο. Για παράδειγμα, χρησιμοποιώντας την κλάση vector, θα φτιάξουμε ένα αντικείμενο τύπου vector, δηλαδή έναν πίνακα.

#include <vector> //περιλαμβάνουμε την αντίστοιχη βιβλιοθήκη
using namespace std; //απαραίτητο

vector<int> pinakas;

Θα λέμε ότι ο pinakas είναι ένα αντικείμενο τύπου vector, ή πιο απλά ο pinakas είναι ένα vector. Θα μελετήσουμε τα vector διεξοδικά στην συνέχεια αυτού του άρθρου. Ο κάθε τύπος container απαιτεί διαφορετικές παραμέτρους για να δημιουργηθεί. Όπως βλέπουμε παραπάνω, ο vector χρειάζεται τον τύπο δεδομένων που θα κρατάει (int). Οι παράμετροι δηλώνονται εντός των <> και αν είναι περισσότεροι του ενός χωρίζονται με κόμματα.

Κάτι ακόμα που είναι σημαντικό και πρέπει να προσέξουμε είναι ότι δεν ορίσαμε το μέγεθος του πίνακα! Αυτό δεν είναι λάθος γιατί το vector και όλα τα υπόλοιπα containers με τα οποία θα ασχοληθούμε είναι δυναμικά, δηλαδή το μέγεθός τους αυξομειώνεται αυτόματα για να χωράνε όλα τα στοιχεία τους.

Τα containers έχουν σχεδιαστεί ώστε οι κοινές λειτουργίες τους να έχουν το ίδιο όνομα. Έτσι σε όλα τα container υπάρχει η λειτουργία size() που επιστρέφει το μέγεθος του container, δηλαδή τον αριθμό των στοιχείων που περιέχει. Για να χρησιμοποιήσουμε μια λειτουργία του container χρησιμοποιούμε τον τελεστή . όπως στο παράδειγμα:

#include <set>
#include <vector>
#include <cstdio>

using namespace std;

set<int> empty;
vector<long double> full={90.009,12.32,8.65,20000.0}; //αρχικοποίηση

int main()
{
    printf("%d %d\n",empty.size(),full.size()); // τυπώνει 0 4
    empty = {1,2,3,4,5}; //εκχώρηση
    printf("%d\n",empty.size()); // τυπώνει 5
}

Όπως βλέπουμε από το παραπάνω παράδειγμα, μπορούμε να αρχικοποιήσουμε ένα container χρησιμοποιώντας initializer lists. Το εκπληκτικό όμως είναι ότι μπορούμε να εκχωρήσουμε κατευθείαν δεδομένα στο container με τον τελεστή =, κάτι που απαγορευόταν στους απλούς πίνακες.

Κάθε container περιλαμβάνει την λειτουργία empty(), που επιστρέφει true αν το container είναι άδειο (δηλαδή έχει μέγεθος 0). Επίσης, κάθε container περιλαμβάνει την λειτουργία clear(), που διαγράφει όλα τα αποθηκευμένα στοιχεία, erase() που διαγράφει συγκεκριμένα στοιχεία και insert() ή push_front/push_back() για την εισαγωγή στοιχείων.

iterators

Σε κάποια containers επιτρέπεται η απευθείας πρόσβαση σε στοιχείο με τον ίδιο ακριβώς τρόπο που γίνεται και στους απλούς πίνακες. Για ορισμένες λειτουργίες όμως, ή για containers που δεν επιτρέπουν την άμεση προσπέλαση υπάρχει ένας τύπος δεδομένων που ονομάζεται iterator και αποθηκεύει την θέση ενός στοιχείου σε ένα container. Το iterator είναι το ανάλογο ενός δείκτη στον μηχανισμό των απλών πινάκων. Για να δηλώνουμε ένα iterator θα χρησιμοποιούμε το keyword auto. Με την χρήση του auto απαιτείται ωστόσο η κατευθείαν αρχικοποίηση της μεταβλητής αλλιώς το πρόγραμμα δεν μεταγλωττίζεται. Κάθε container διαθέτει τις λειτουργίες begin() και end(). Η begin() επιστρέφει ένα iterator για το πρώτο στοιχείο του container, ενώ η end() για το υποθετικό στοιχείο που βρίσκεται μετά το τελευταίο.

auto first=myvector.begin(), after_end=myvector.end();

Η μεταβλητή first είναι ένα iterator που δείχνει στο πρώτο στοιχείο και όχι το πρώτο στοιχείο. Για να πάρουμε την τιμή του πρώτου στοιχείου θα κάνουμε dereference τον iterator first:

printf("%d",*first);

Προσοχή: απαγορεύεται να κάνουμε dereference το iterator after_end, επειδή πολύ απλά δεν δείχνει σε κάποιο υπαρκτό στοιχείο. Επίσης μερικά containers δεν επιτρέπουν την τροποποίηση στοιχείου μέσω των iterators! Αυτό σημαίνει ότι το παρακάτω δεν επιτρέπεται για όλα τα container:

*first = 5; // compilation error αν δεν επιτρέπεται η τροποποίηση

Τα iterators είναι φτιαγμένα με βάση τους δείκτες. Έτσι μπορούμε ακόμα να προχωρήσουμε ένα iterator ώστε να δείχνει στο επόμενο στοιχείο με τον τελεστή ++. Ομοίως μπορούμε να χρησιμοποιήσουμε τον τελεστή –:

first++;
++first;
first--;
--first;

Για την θέση του ++ και του – ισχύουν οι γνωστοί κανόνες. Αν πάλι θέλουμε να πάρουμε ένα iterator που δείχνει στο επόμενο ή στο προηγούμενο στοιχείο, χωρίς όμως να προχωρήσουμε το iterator που έχουμε χρησιμοποιούμε τις συναρτήσεις prev() και next().

printf("%d %d\n",*next(first),*prev(last));
// τυπώνει το 2ο και το τελευταίο στοιχείο του container

Το γεγονός ότι η λειτουργία end() επιστρέφει ένα μη έγκυρο iterator αποτελεί μια πολύ συχνή αιτία σφαλμάτων όταν δουλεύουμε με την STL. Θα δούμε όμως παρακάτω ότι τα containers είναι πλήρως εναρμονισμένα με τους υλοποιημένους αλγόριθμους σε μορφή συναρτήσεων που περιέχει η STL. Για να προσπελάσουμε κάθε στοιχείο ενός container, αρκεί να ορίσουμε έναν iterator με την τιμή begin() και να τον προχωράμε βήμα βήμα μέχρι να πετύχουμε το στοιχείο end(). Αυτό γίνεται εύκολα με ένα loop

for (auto it=myvector.begin(); it!=myvector.end(); it++)
    printf("%d",*it);

Το παραπάνω μπορεί να γραφτεί και πιο σύντομα:

for (auto it:myvector)
    printf("%d",it);

Στην πρώτη περίπτωση όμως το it είναι ένας iterator, επομένως απαιτείται η χρήση του τελεστή * για να παίρνουμε την τιμή στου στοιχείου μέσα στο loop. Στην δεύτερη περίπτωση, το it είναι μια μεταβλητή στην οποία εκχωρούνται διαδοχικά τα στοιχεία του myvector, οπότε δεν βάζουμε τελεστή *.

Το vector επιτρέπει την τροποποίηση των στοιχείων του, οπότε θα μπορούσαμε να χρησιμοποιήσουμε τον iterator για να εκχωρήσουμε μία άλλη τιμή στην θέση στην οποία δείχνει.

for (auto it=myvector.begin(); it!=myvector.end(); it++)
{
    printf("%d",*it);
    *it=0;
}

Αυτό όμως δεν δουλεύει στην δεύτερη περίπτωση, γιατί όπως είπαμε στην μεταβλητή it εκχωρούνται διαδοχικά όλα τα στοιχεία του myvector. Δηλαδή η μεταβλητή it είναι ένα αντίγραφο του εκάστοτε στοιχείου, οπότε μια εκχώρηση θα επηρέαζε μόνο την it και όχι τα στοιχεία του myvector. Αν θέλουμε να επηρεάζονται και τα στοιχεία του myvector θα χρησιμοποιήσουμε μια αναφορά:

for (auto &it:myvector)
{
    printf("%d\n",it);
    it=0;
}
// το myvector έχει μηδενιστεί

initializer list

Αυτή είναι μια βοηθητική δομή δεδομένων που χρησιμοποιείται στην C++11 και νεότερες εκδόσεις. Για να δηλώσουμε μια initializer list χρησιμοποιούμε {} και μέσα σε αυτές βάζουμε στοιχεία χωρισμένα με κόμμα. Μπορούμε μάλιστα να εκχωρήσουμε μια initializer list σε μεταβλητή εύκολα ως εξής:

auto initlist = {1,3,5,7,11};

Η initializer list δεν έχει μεθόδους. Είναι όπως είπαμε βοηθητική δομή που χρησιμεύει για την αρχικοποίηση άλλων δομών, για παράδειγμα ενός πίνακα. Τα container της STL είναι σχεδιασμένα για να δέχονται initializer lists και έτσι ο κώδικάς μας γίνεται απλούστερος. Η χρήση και η σπουδαιότητα της δομής αυτής θα φανεί άμεσα, στις επόμενες δομές δεδομένων.

pair

Η πιο απλή δεδομένων που υπάρχει στην STL είναι το pair. Ουσιαστικά είναι ένα ζευγάρι μεταβλητών οποιουδήποτε τύπου. Για να τα χρησιμοποιήσουμε πρέπει να συμπεριλάβουμε το αρχείο vector ή το αρχείο algorithm. Για την δήλωσή τους απαιτούνται ως παράμετροι οι τύποι των δύο μεταβλητών, ενώ μπορούμε να τα αρχικοποιήσουμε με δύο τρόπους.

pair<long long,char> pair1 = {23232121212121,'f'}; //initializer list
pair<int,int> pair2(5,10);

Για να προσπελάσουμε (εγγράψουμε ή αναγνώσουμε) το πρώτο στοιχείο χρησιμοποιούμε το πεδίο first του pair, ενώ για το δεύτερο το second. Προσοχή, τα first και second δεν είναι λειτουργίες και για αυτό δεν συντάσσονται με παρενθέσεις.

pair1.first=0;
pair1.second='a';

Μπορούμε να συγκρίνουμε δύο pairs που έχουν μεταβλητές του ίδιου τύπου με τους τελεστές ==, !=, <, <=, > , >=. Κατά την σύγκριση αρχικά λαμβάνονται υπόψη μόνο τα πεδία first. Αν τα δύο πεδία είναι ίσα, τότε συγκρίνονται τα πεδία second, αλλιώς επιστρέφεται το αποτέλεσμα της σύγκρισης για τα πεδία first.

vector

Το vector (στα ελληνικά διάνυσμα) είναι ουσιαστικά ένας πίνακας. Χρησιμοποιείται με τον ίδιο τρόπο που χρησιμοποιούνται και οι απλοί πίνακες της C++, έχει τα ίδια μειονεκτήματα και πλεονεκτήματα με αυτούς. Η διαφορά έγκειται στο δυναμικό τους μέγεθος. Τα vectors ορίζονται χωρίς να δοθεί μέγεθος, αλλά μόνο ο τύπος δεδομένων που αποθηκεύουν. Για να εισαχθεί ένα στοιχείο στο τέλος του vector χρησιμοποιείται η εντολή push_back(). Ισχύουν (όπως και σε κάθε άλλο container που θα δούμε παρακάτω) όλοι οι γενικοί κανόνες που είπαμε πριν. Ακολουθεί ένα παράδειγμα με την χρήση τους:

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

vector<pair<int,int>> pinakas2d;
int n;

int main()
{
    printf("Give n, number of points in plane >> ");
    scanf("%d",&n);
    for (int x,y, i=0; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        pinakas2d.push_back({x,y});
    }
    printf("Which is the central point? (Type a number from 0 to %d) >>",n-1);
    int center;
    do scanf("%d",&center);
    while (center<0 || center>=n);

    int x0=pinakas2d[center].first;
    int y0=pinakas2d[center].second;
    // 1ος τρόπος
    for (int i=0; i<n; i++)
        printf("Distnce from point %d to point %d is: %.2lf\n",i,center,
        hypot(pinakas2d[i].first-x0,pinakas2d[i].second-y0));

    printf("\n");
    //2ος τρόπος
    int i=0;
    for (auto &it:pinakas2d) //χρησιμοποιούμε & για ταχύτητα, δεν γίνεται διαδοχική εκχώρηση των pairs στο it.
    {
        printf("Distnce from point %d to point %d is: %.2lf\n",i,center,
        hypot(it.first-x0,it.second-y0));
        i++;
    }
}

string

Το string είναι μια εύχρηστη δομή που μας επιτρέπει να αποθηκεύουμε κείμενο. Χρησιμοποιεί δομή vector για να αποθηκεύει τους χαρακτήρες, οπότε ισχύουν όλα όσα ξέρουμε για τα vector. Ταυτόχρονα προσφέρει τις χρήσιμες μεθόδους replace(), που αντικαθιστά μέρος του string με ένα άλλο, find() που εκτελεί γραμμική αναζήτηση για εύρεση substring και substring() που επιστρέφει ένα μέρος του string ως καινούριο string. Επίσης, οι λογικοί τελεστές ==, !=, >, <, >=, <= μπορούν να επιδράσουν σε αυτά και να συγκρίνουν λεξικογραφικά δύο strings, ενώ οι τελεστές + , = και += για να ενώσουν δύο string, και να κάνουν απλή εκχώρηση και προσθετική εκχώρηση αντίστοιχα.

list

Η λίστα υποστηρίζει όλες τις λειτουργίες που υποστηρίζει και το vector. Έτσι, υπάρχουν οι ίδιες μέθοδοι και χρησιμοποιούνται με τον ίδιο τρόπο, ενώ οι εξαιρέσεις είναι ελάχιστες. Η λίστα περιέχει περισσότερες μεθόδους, τις οποίες μπορείτε να μελετήσετε αναλυτικά στο documentation της STL.

H διαφορά της με το vector όμως είναι η πολυπλοκότητα με την οποία δουλεύει κάθε μέθοδος. Αυτό είναι άμεση συνέπεια του τρόπου με τον οποίο αποθηκεύονται τα δεδομένα στις δύο αυτές δομές. Για παράδειγμα, σε ένα vector η προσπέλαση τυχαίου στοιχείο κοστίζει O(1) ενώ σε μία λίστα O(n), όπου n είναι το πλήθος των στοιχείων της λίστας.

Επιπλέον, η list δεν σχετίζεται καθόλου με την initializer list. Η list είναι ένα κανονικό και πλήρως λειτουργικό container της STL, σε αντίθεση με την initializer list που δεν έχει μεθόδους και είναι βοηθητικό container.

priority_queue

Η ουρά προτεραιότητας είναι μια δομή δεδομένων όμοια με την ουρά. Σε μία ουρά τα δεδομένα εισάγονται πάντα στο τέλος και εξάγονται πάντα από την αρχή (κανόνας FIFO-first in first out). Η ουρά υπάρχει έτοιμη υλοποιημένη στην STL, όμως πάντα μπορούμε να χρησιμοποιούμε list αντί για queue, καθώς η λίστα υποστηρίζει τις ίδιες και περισσότερες δυνατότητες από την ουρά.

Η priority_queue όμως δεν μπορεί να αντικατασταθεί από μία λίστα. Σε μία priority_queue έχουμε πρόσβαση μόνο στο πρώτο στοιχείο. Επομένως η ουρά προτεραιότητας υποστηρίζει τρεις βασικές μεθόδους, top() η οποία μας δίνει πρόσβαση στο πρώτο στοιχείο, pop() η οποία διαγράφει το πρώτο στοιχείο και φυσικά push() η οποία εισάγει ένα στοιχείο στην ουρά.

Η ουρά προτεραιότητας λειτουργεί με τον απλό κανόνα ότι το πρώτο στοιχείο είναι πάντα το μεγαλύτερο στην ουρά. Έτσι, όταν κάνουμε push η ουρά αναδιατάσσει τα στοιχεία της ώστε το μεγαλύτερο να βρίσκεται στην αρχή. Προσοχή όμως, τα δεδομένα στην ουρά προτεραιότητας δεν βρίσκονται ταξινομημένα και δεν υπάρχει τρόπος να αποκτήσουμε πρόσβαση σε τυχαίο στοιχείο, αν δεν διαγράψουμε πρώτα όλα τα μεγαλύτερα του.

Σε μία ουρά προτεραιότητας σε χρονική πολυπλοκότητα η λειτουργία top() κοστίζει Ο(1), ενώ οι λειτουργίες pop() και push() κοστίζουν O(logn), όπου n το πλήθος των στοιχείων που περιέχει η ουρά.

set

Το set, όπως και η ουρά προτεραιότητας και το map που θα δούμε στη συνέχεια είναι δενδρικές δομές δεδομένων. Σε αντίθεση με τους πίνακες και τις λίστες οι δενδρικές δομές δεδομένων αναδιατάσσουν αυτόματα την σειρά των στοιχείων έτσι ώστε να πετυχαίνεται η βέλτιστη πολυπλοκότητα για τις διάφορες μεθόδους. Το set διέπεται από τους δύο απλούς κανόνες:

1. Τα στοιχεία είναι ταξινομημένα στο set σε αύξουσα σειρά.
2. Δεν υπάρχουν διπλά στοιχεία (δηλαδή στοιχεία που θεωρούνται ίσα).

Το set δεν επιτρέπει άμεση προσπέλαση τυχαίου στοιχείου, παρά μόνο του πρώτου και του τελευταίου. Επιτρέπεται όμως η διάσχιση διαδοχικών στοιχείων, όπως ακριβώς και με μια λίστα. Σε ένα set, υπάρχουν οι βασικές μέθοδοι που ειπώθηκαν στην αρχή. Χαρακτηριστική όμως είναι η μέθοδος find(), που βρίσκει ένα στοιχείο με χρονική πολυπλοκότητα O(logn). Επιπλέον οι μέθοδοι insert() και erase() κοστίζουν Ο(logn) εάν δεν τους δοθεί iterator ως όρισμα, διότι θα πρέπει να κληθεί πρώτα η find για να βρεθεί η σωστή θέση στην οποία θα γίνει εισαγωγή του νέου στοιχείου, ή να βρεθεί το στοιχείο που θα διαγραφεί.

map

Το map είναι μια δομή που θυμίζει κλασσικό πίνακα, με την διαφορά ότι το index που δίνουμε δεν είναι απαραίτητα τύπου int και μάλιστα φραγμένο σε ένα κλειστό διάστημα αριθμών. Μπορούμε κάλλιστα να δημιουργήσουμε map που δέχεται σαν index floats (μην το κάνετε ποτέ, λόγω σφαλμάτων ακρίβειας στα floats) ή ακόμα και strings! Για να χρησιμοποιήσουμε map, πρέπει να συμπεριλάβουμε στο πρόγραμμά μας την βιβλιοθήκη <map> και κατά την δήλωση να δώσουμε τον τύπο που θα έχουν τα index και τον τύπο δεδομένων που θα αποθηκεύει το map.

#include <map>
#include <string>
using namespace std;

map<string,int> mymap;

Για να αποκτήσουμε πρόσβαση σε ένα στοιχείο, χρησιμοποιούμε τον τελεστή [], δηλαδή όπως ακριβώς κάνουμε προσπέλαση στοιχείου σε πίνακα! Η μόνη διαφορά είναι στην περίπτωση που το index που δίνουμε δεν αντιστοιχεί σε κανένα στοιχείο. Θυμηθείτε ότι το map είναι δυναμικό container, που σημαίνει ότι το μέγεθός του αυξομειώνεται αυτόματα. Αν χρησιμοποιήσουμε το παραπάνω κομμάτι κώδικα θα δηλωθεί ένα κενό map. Σε αυτήν την περίπτωση λοιπόν, όποιο index και αν δώσουμε δεν θα αντιστοιχεί σε κανένα στοιχείο. Κάθε φορά που γίνεται αυτό, δημιουργείται καινούριο στοιχείο. Αν δεν δοθεί αρχική τιμή, το στοιχείο αρχικοποιείται αυτόματα στην default τιμή (0 για int, float κλπ, κενό string για string).

#include <map>
using namespace std;

map<int,int> mymap;

int main()
{
    mymap[35] = 10;
    mymap[35]++;
    mymap[19]++;
    printf("%d %d",mymap[19],mymap[35]); // τυπώνει 1 11
}

Ας δούμε ακόμα ένα παράδειγμα:

ΛΑΘΟΣ

#include <map>
using namespace std;

map<int,int> mymap;

int main()
{
    if (mymap[10]==0) printf("mymap[10] exists and has a value of 0");
}

Σε αυτήν την περίπτωση η τιμή mymap[10] δεν υπάρχει, όμως δημιουργείται αυτόματα εκείνη τη στιγμή, αρχικοποιείται με 0 και έτσι τυπώνεται το μήνυμα! Για να το αποφύγουμε αυτό θα χρησιμοποιήσουμε τη μέθοδο find(). H μέθοδος find() επιστρέφει έναν iterator στο στοιχείο του οποίου το index δίνουμε προς εύρεση, αλλιώς αν το στοιχείο δεν υπάρχει επιστρέφεται το map.end().

ΣΩΣΤΟ

#include <map>
using namespace std;

map<int,int> mymap;

int main()
{
    if (mymap.find(10) != mymap.end() && mymap[10]==0) printf("mymap[10] exists and has a value of 0");
}

Καθώς το map είναι ουσιαστικά ένα set που δέχεται pairs, οι μέθοδοι [], erase() και find() κοστίζουν O(logn).

unordered_map

Το container αυτό υπάρχει μόνο στις εκδόσεις c++11 και νεότερες. Κάνει την ίδια περίπου δουλειά με το map, με την διαφορά ότι αποθηκεύει τα δεδομένα του με διαφορετικό τρόπο. Όπως δηλώνει και το όνομα του, τα στοιχεία του δεν είναι ταξινομημένα. Έτσι μια διάσχιση ξεκινώντας από το begin() και τελειώνοντας στο end() θα μας δώσει όλα τα στοιχεία του, όμως με κάποια τυχαία σειρά.

Το πλεονέκτημα αυτής της δομής είναι ότι οι μέθοδοι [], erase() και find() κοστίζουν Ο(1). Πως γίνεται αυτό; Το unordered map είναι ουσιαστικά μία υλοποίηση του hash_table. Κάθε κλειδί (index) αντιστοιχίζεται σε έναν αριθμό ενός κλειστού διαστήματος [0,x]. Έτσι τα δεδομένα μπορούν να αποθηκευτούν σε έναν πίνακα. Με την χρήση της ίδιας συνάρτησης αντιστοίχισης (που τρέχει σε O(1)) μπορεί να ελεγχθεί αν υπάρχει κάποιο index, ή να βρεθεί η θέση ενός στοιχείου στο hash_table.

multiset, multimap και unordered_multimap

Τα τρία container set, map και unordered_map δεν επιτρέπουν την ύπαρξη διπλών στοιχείων. Στην περίπτωση των map και unordered_map, δεν επιτρέπεται να υπάρχουν δύο στοιχεία που έχουν το ίδιο index. Τα multiset, multimap και unordered_multimap είναι τα αντίστοιχα container που άρουν όμως αυτόν τον περιορισμό. Προσοχή: στα containers multimap και unordered_multimap δεν υπάρχει η μέθοδος [].

Σύνοψη των λειτουργιών των container

algorithm

Η STL εκτός από containers περιλαμβάνει και έτοιμους υλοποιημένους αλγόριθμους με την μορφή συναρτήσεων, στη βιβλιοθήκη algorithm. Αν και η algorithm περιλαμβάνει πληθώρα συναρτήσεων, οι περισσότερες είναι πολύ απλές, οπότε δεν συμφέρει να μάθουμε τον τρόπο με τον οποίο συντάσσονται, αλλά καλύτερα θα χρησιμοποιούμε τον δικό μας κώδικα. Ωστόσο, σε αυτήν την παράγραφο θα αναφέρουμε μερικές αξιοσημείωτες συναρτήσεις καθώς και τον τρόπο λειτουργίας τους.

sort()

Η sort() είναι η πιο σημαντική συνάρτηση της βιβλιοθήκης algorithm. Ταξινομεί n στοιχεία ενός container με χρονική πολυπλοκότητα O(nlogn), δηλαδή με την βέλτιστη πολυπλοκότητα για συγκριτική ταξινόμηση. Συντάσσεται με 2 τρόπους:

1. sort(iterator start, iterator stop)
2. sort(iterator start, iterator stop, bool(*)() compare)

Στην πρώτη μορφή, η sort δέχεται δύο iterators, για το πρώτο στοιχείο που θα ταξινομηθεί και για το πρώτο στοιχείο που δεν θα ταξινομηθεί. Η ταξινόμηση γίνεται σε αύξουσα σειρά και η sort() για να συγκρίνει δύο στοιχεία χρησιμοποιεί τον τελεστή <. Στην δεύτερη μορφή, το κριτήριο της ταξινόμησης δεν είναι ο τελεστής < αλλά μια συνάρτηση compare() την οποία υλοποιούμε εμείς. Η compare πρέπει υποχρεωτικά να επιστρέφει bool, να δέχεται δύο μεταβλητές ίδιου τύπου με αυτές που ταξινομούνται και να επιστρέφει true αν το πρώτο στοιχείο πρέπει να τοποθετηθεί οπωσδήποτε πριν από το δεύτερο.

Ας εξηγήσουμε λίγο καλύτερα τι σημαίνει αυτό. Έστω ότι θέλουμε να φτιάξουμε μια συνάρτηση compare() τέτοια ώστε τα στοιχεία να ταξινομηθούν σε φθίνουσα σειρά. Τότε η συνάρτηση compare() θα είναι η εξής:

ΣΩΣΤΟ

bool compare(int a, int b)    {return a>b;}

Αν όμως κάναμε το παρακάτω λάθος:

ΛΑΘΟΣ

bool compare(int a, int b)    {return a>=b;}

τότε το πρόγραμμα θα εμφάνιζε runtime error. Διότι όταν δύο στοιχεία είναι ίδια τότε το a δεν πρέπει να μπει οπωσδήποτε πριν το b άρα η compare πρέπει να επιστρέφει false. Σε αυτήν την περίπτωση η πρώτη συνάρτηση επιστρέφει false, ενώ η δεύτερη true.

Κάτι ακόμα που πρέπει να σημειώσουμε είναι ότι η sort() μπορεί να χρησιμοποιηθεί και για να ταξινομήσει απλούς πίνακες της C++, και όχι μόνο containers της STL. Αντί για iterators, δίνουμε δείκτες για το πρώτο στοιχείο που θα ταξινομηθεί και δεν θα ταξινομηθεί, και μετατρέπονται αυτόματα σε iterators. Ακολουθεί ένα παράδειγμα ταξινόμησης πίνακα και vector σε φθίνουσα σειρά.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(int a, int b)    {return a>b;}

int main()
{
    int pin[10] = {3,1,6,7,2,1,9,8,5,4};
    vector<int> vec(pin,pin+10);
    sort(pin,pin+10,compare);
    sort(vec.begin(),vec.end(),compare);
    for (int i=0; i<10; i++) printf("%d ",pin[i]);
    printf("\n");
    for (auto it:vec) printf("%d ",it);
}

Τέλος, σε περιπτώσεις που θέλουμε να πραγματοποιήσουμε ταξινόμηση με διατήρηση της σχετικής θέσης των ίσων στοιχείων, υπάρχει η συνάρτηση stable_sort(), με ακριβώς την ίδια σύνταξη.

min() και max()

Αυτές οι συναρτήσεις επιστρέφουν το ελάχιστο και το μέγιστο στοιχείο αντίστοιχα. Συντάσσονται με δύο τρόπους:

1. min(x,y) και max(x,y)
2. min(initializer_list il) και max(initializer_list il) Στην πρώτη περίπτωση δίνουμε δύο στοιχεία ίδιου τύπου, ενώ στην δεύτερη δίνουμε μία initializer_list, όσων στοιχείων θέλουμε.

Επίσης η συνάρτηση minmax() συντάσσεται με τον ίδιο τρόπο και επιστρέφει ένα pair με το μικρότερο και μεγαλύτερο στοιχείο.

Επιπλέον, οι συναρτήσεις min_element() και max_element() συντάσσονται ως: min/max_element(iterator start, iterator stop) και επιστρέφουν ένα iterator με τη θέση του μικρότερου/μεγαλύτερου στοιχείου στο διάστημα [[start,stop)], δηλαδή το διάστημα που ξεκινάει από τη θέση start και τελειώνει πριν τη θέση stop.

lower_bound(), upper_bound(), equal_range() και binary_search()

Συντάσσονται όλες με τον ίδιο τρόπο: χρειάζονται δύο iterators start και stop και μια τιμή x. Το container ή ο πίνακας στον οποίον επιδρούν πρέπει να είναι υποχρεωτικά ταξινομημένος. Αν η δομή είναι ταξινομημένη με διαφορετικό τρόπο από το default, τότε χρειάζονται ακόμα ένα όρισμα, έναν δείκτη για την συνάρτηση με την οποία έγινε η ταξινόμηση (όπως με το sort()). Οι συναρτήσεις εκτελούν δυαδική αναζήτηση και επιστρέφουν:

• Η lower_bound() ένα iterator για το πρώτο στοιχείο >= από x
• H upper_bound() ένα iterator για το πρώτο στοιχείο > από x
• Η equal_range() ένα pair με τις τιμές που επιστρέφουν οι lower_bound() και upper_bound()
• H binary_search() ένα bool, true αν βρέθηκε το στοιχείο x, αλλιώς false

Όλες οι συναρτήσεις έχουν πολυπλοκότητα O(n), όπου n είναι ο αριθμός των στοιχείων ανάμεσα στο start και στο stop.

Πλεονεκτήματα και μειονεκτήματα των containers της STL

Πράγματι η STL είναι ο λόγος που χρησιμοποιούμε την C++ και όχι την C στους διαγωνισμούς. Από αυτήν θα χρησιμοποιήσουμε έτοιμους αλγόριθμους και container, ορισμένα από τα οποία θα ήταν εξαιρετικά δύσκολο και χρονοβόρο να τα υλοποιήσουμε μόνοι μας την ώρα του διαγωνισμού. Ορισμένα από αυτά μάλιστα απαιτούν και πολύ προχωρημένες γνώσεις για την υλοποίηση τους. Σε άλλες περιπτώσεις χρησιμοποιούμε την STL για λόγους ευκολίας. Ωστόσο τα μειονεκτήματα της STL είναι δυο:

• Το πρόγραμμα γίνεται πιο αργό (σε χρόνο εκτέλεσης)
• Είναι εύκολο να κάνουμε λάθη

Από τα παραπάνω συμπεραίνουμε ότι πρέπει να χρησιμοποιούμε την STL με φειδώ. Δηλαδή να την αποφεύγουμε για απλές εφαρμογές που μπορούμε να υλοποιήσουμε εύκολα με το συναρτησιακό κομμάτι της C++, αλλά να την χρησιμοποιούμε για να κερδίζουμε χρόνο και να παρακάμπτουμε την υλοποίηση δύσκολων αλγορίθμων και δομών δεδομένων.

Σχόλια