Curs STL

de Alex Vasiluță

Ce este STL?

De ce?

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

Utilizare

/// Declarare
// Trebuie specificat tipul de date între brackets
// Informațiile dintre brackets => *specializare*
vector<int> v;

/// 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

Utilizare

/// 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

std::queue

Utilizare

/// 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ță

queue image

std::stack

Utilizare

/// 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

stack image

std::string

Utilizare

/// 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

Utilizare

/// 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;

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

std::pair

Utilizare

/// 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

Iteratorii

Glosar iteratori

Cum obțin un iterator?

Ce pot face cu un iterator?

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

Utilizare

/// 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

/// 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

Aplicații