Curs STL

de Alex Vasiluță

Ce este STL?

• STL = Standard Template Library
• O colecție de structuri de date
• De exemplu: std::vector, std::queue, std::map, std::priority_queue, etc

De ce?

• Ce faceți voi acum e C cu cin/cout.
• Utilizează cel mai puternic lucru din C++, templates.
• Nu mai trebuie să pierdem timp pe implementarea structurilor de date
• Simplifică mult viața

NOTĂ: std:: reprezintă namespace-ul în care se află la început containerele STL. Putem să omitem utilizarea sa dacă punem using namespace std; la începutul programului.

Înainte să începem

În exemplele de cod voi utiliza keyword-ul auto. El deduce automat tipul bazat pe ce valoare îi dai, dar nu poate fi schimbat.

De exemplu, pot face auto x = ceva(); și el va lua tipul rezultatului funcției ceva(). Însă, nu pot declara auto x; deoarece nu are de unde să preia tipul.

Structuri simple de date

• std::vector
• std::deque
• std::queue
• std::stack
• std::string
• std::tuple
• std::pair

std::vector

• Cea mai simplă structură de date
• Un array de lungime dinamică
• Indexat de la 0

Declarare

vector<int> v;

• Trebuie specificat tipul de date între brackets
  • Informațiile dintre brackets => specializare

Utilizare

Adăugare element la final

v.push_back(x); // Adaugă x la finalul vectorului

Eliminare elementul de la final

v.pop_back();

Accesare element

// Afișează elementul de la poziția x
// (fiind indexat de la 0, al x+1 -lea element)
cout << v[x] << endl;

Redimensionare

v.resize(x); // Mărește dimensiunea la x elemente (v.size() = x)

Rezervare spațiu

v.reserve(x); // Rezervă x elemente în vector, pentru a minimiza numărul de realocări

Iterare vector

Varianta simplă

for(auto i : v)
    cout << i << " ";

Varianta cu iteratori

for(auto i = v.begin(); i != v.end(); ++i)
    cout << *i << " ";

std::deque

• Seamănă mult cu std::vector, dar poți să inserezi/ștergi și din față, și din spate

• Pe lângă ce are vector-ul, oferă încă două funcții: push_front() și pop_front()

  • Ele se comportă la fel ca push_back() și pop_back(), dar inserează la început

Declarare

deque<int> v;

Accesare

// La fel ca std::vector, dar avem și
v.front(); // echivalent cu v[0]

Ștergere

// La fel ca std::vector, dar avem și
v.pop_front(); // șterge în mod eficient primul element

Adăugare

// La fel ca std:;vector, dar avem și
v.push_front(x); // Adaugă x la început într-un mod eficient

std::deque vs std::vector

• Avantaje std::deque
  • Nu este nevoie de realocare când redimensionează vectorul
  • Putem adăuga la început
• Dezavantaje std::deque
  • De obicei, mai lent decât std::vector

std::queue

• FIFO (First In, First Out)

Declarare

queue<int> q;

Adăugare

q.push(x); // Adaugă valoarea x la final

Accesare

q.front(); // Elementul din față
q.back(); // Elementul din spate

Eliminare

q.pop(); // Scoate elementul din față

std::stack

• LIFO (Last In, First Out)

Declarare

stack<int> st;

Adăugare

st.push(x); // Adaugă valoarea x la final

Accesare

st.top(); // Elementul de sus

Eliminare

st.pop(); // Scoate elementul de sus

std::string

• Abstracție peste șirurile de caractere
• Simplifică mult viața

Definire

string s1;
string s2 = "ana are mere";

Adăugare

s1 += "test";
// sau
s1.append("test");

Căutare

s1 = "test aaa asdf";
s1.find("aaa"); // returnează 5
s1.find("nu exista"); // returnează -1

Subsecvență

s1 = "ana are mere bune";
s1.substr(4, 4); // returnează un string cu valoarea "are "

Obținere copie a șirului intern de caractere

s1.c_str();

Comparare stringuri

string s1 = "ana", s2 = "ion", s3 = "popescu";
s1.compare(s2); // -1, "ana" este înaintea lui "ion" în dicționar
s1.compare(s1); // 0, "ana" este identic cu "ana"
s3.compare(s1); // 1, "popescu" este după "ana" în dicționar

citire/afișare

string s;
cin >> s; // Citește un șir de lungime arbitrară
getline(cin, s); // Citește o linie întreagă
getline(cin, s, '#'); // Citește până la delimitatorul '#'
cout << s; // Afișează s

Concatenare

string s = "a1", s1 = "a2";
string s2 = s + " " + s1;
cout << s2; // "a1 a2"

std::tuple

• Un set de elemente de lungime fixă
• Lungimea și tipurile de date sunt cunoscute la compilare

Declarare

tuple<int, int, int, double> t;

sau

auto t = make_tuple(1, 2, 3, 4.5);

Accesare

int x = get<0>(t), y = get<1>(t), z = get<2>(t);
double w = get<3>(t);

sau

int x, y;
double w;
tie(x, y, ignore, w) = t; // nu ne pasă de al treilea element

Modificare

get<2>(t) = 3;

Fun

int x = 3, y = 4, z = 1;
auto tp = tie(x, y, z);
get<2>(tp) = 5;
cout << z; // 5

std::pair

• ține o pereche de elemente
• este un caz specific al std::tuple, cu două elemente
  • => toate chestiile specifice std::tuple sunt disponibile la pair, dar are și altele în plus

Declarare

pair<int, double> p;

sau

auto p = make_pair(2, 5.3);

Accesare

// p.first - primul element din pereche
// p.second - al doilea element din pereche
cout << p.first << " " << p.second;

Modificare

p.first = 2;
p.second = 3.5;

sau

p = make_pair(2, 3.5);

Caracteristici comune

• Structurile STL cu număr variabil de elemente au câteva funcții în comun:

  • .size() - câte elemente sunt în structură
  • .empty() - spune dacă structura este goală
  • Câteva structuri au o funcție .clear() care elimina toate elementele din ea

• Containerele pot fi comparate cu operatorii standard (==, !=, >=, etc)

  • Operatorii compară valorile structurii
  • Merg doar pe 2 containere cu aceeași specializare

• De asemenea, aproape fiecare structură implementează proprii săi iteratori

Iteratorii

• Iteratorii sunt structuri care pot fi utilizate să identifice și traverseze elementele unui container STL
• Ei sunt implementați numai la structurile cu acces aleatoriu (toate mai puțin queue, stack și priority_queue)

Glosar iteratori

• range
  • un interval de elemente de tip [start, end).
• iterator de îneput
  • iterator care marchează începutul unui range
• iterator past-the-end
  • iterator care marchează finalul unui range. Deși uneori poate, nu este ok să fie accesat direct.
  • Exemplu: rezultatul pentru .end()

Cum obțin un iterator?

• .begin() - iterator la primul element din structură
• .end() - iterator past-the-end pentru structură.

Ce pot face cu un iterator?

• Să parcurgi structura

  • Fiecare iterator permite să îl incrementezi (++it) să se ducă mai departe.
  • Putem folosi și it++, dar de obicei este mai lent.

• Să îl pui drept parametru la o funcție

  • Multe funcții din <algorithm> care merg pe range-uri cer un iterator de început și un iterator "past-the-end".
    • De exemplu, funcția sort() cere doi iteratori: unul care marchează începutul și elementul de după sfârșit (cum ar fi begin() și end()).
  • Structurile std::vector și std::deque oferă și funcțiile .erase() și .insert()
    • Funcția .insert() adaugă un element înaintea elementului iteratorului.
    • Funcția .erase() poate primi un singur argument, elementul care să fie șters, sau două argumente, range-ul pe care să îl șteargă.

Fun fact: Un pointer respectă cerințele interne pentru un iterator. De aceea, putem face sort(v+1, v+n+1); pentru vectori non-STL!

Exemplu cu câteva din chestiile învățate astăzi

vector<int> v;
v.resize(3);
v[0] = 3;
v[2] = 1;
v[1] = 2;

// v[] = {3, 2, 1}
sort(v.begin(), v.begin() + 2); // sortează primele 2 elemente
// v[] = {2, 3, 1}
reverse(v.begin(), v.end()); // inversează vectorul

// v[] = {1, 3, 2}
for (auto it = v.begin(); it != v.end(); ++it)
    cout << *it << " "; // afișează toate elementele vectorului
cout << endl;

v.erase(v.begin());
v.insert(v.begin(), 15);
for (auto i : v)
    cout << i << " "; // 15 3 2
cout << endl;

cout << v.size() << " " << v.empty() << endl; // 3 0
v.clear();                                    // Șterge toate elementele din vector
cout << v.empty() << endl;                    // 1

Structuri complexe de date

• std::set

• std::map

• std::unordered_map, std::unordered_set

• Fiecare din acestea are o variantă multi, dar personal nu am simțit vreodată nevoia lor

std::set

• un container asociativ care ține o mulțime de valori

Declarare

set<int> vals;

Inserare

// returnează un pair cu:
//  - un iterator la elementul inserat
//  - un bool care spune dacă a avut loc inserarea (true) sau dacă exista deja (false)
vals.insert(2);

Căutare

auto it = vals.find(2);
if(it == vals.end())
{
    cout << "Nu am găsit valoarea `2` în set\n";
} else
{
    cout << "Am găsit `2` în set\n";
}
// sau
int cnt = vals.count(2);
if(cnt == 1) // cnt e fie 0, fie 1 din cauza naturii structurii
{
    cout << "Am găsit valoarea `2` în set\n";
} else
{
    cout << "N-am găsit valoarea `2` în set\n";
}

Ștergere

vals.erase(2); // returnează numărul de elemente șterse

std::map

• un container asociativ
  • => o cheie chei corespunde unei singure valori

Declarare

map<int, int> m;
map<pair<int, int>, int> mp;

Adăugare + Modificare

m[2] = 3;
mp[make_pair(3, 4)] = -1;

Ștergere

mp.erase(make_pair(3, 4)); // Returnează numărul de elemente șterse

Lower bound/Upper bound

cout << distance(m.lower_bound(3), m.upper_bound(8)) << " elemente cu chei între 3 și 8 în map";

std::unordered_set, std::unordered_map

• Variantele unordered la std::set și std::map funcționează practic la fel, dar au câteva limitări care fac mai dificil lucrul cu containere STL drept keys (cum ar fi std::pair)
• Nu garantează că atunci când iterezi prin elemente, ele sunt plasate în ordine descrescătoare
• Nu au funcțiile de căutare binară
• Uneori sunt mai rapide decât variantele normale, dar nu e garantat (depinde de caz)

Întrebări?

Temă

• Problema #9 (sortare) de pe https://kilonova.ro

Vă mulțumesc!