STL - partea I

STL este un set de clase care vine cu câteva structuri de date precum vector, map, set, stack, queue si deque. Este bine să le utilizăm, deoarece acestea sunt eficientizate, în majoritatea cazurilor reprezentând cea mai bună soluție.

<vector>

Vectorul este o alternativă foarte comodă la un array clasic, deoarece acesta are implementată alocarea dinamică și alte funcționalități.

• (constructor)

  1. vector();
  2. explicit vector( const Allocator& alloc );
  3. explicit vector( size_type count,
                      const T& value = T(),
                      const Allocator& alloc = Allocator() );
  

  1. Inițializează un vector gol.
  2. Inițializează un vector cu elementele specificate.
  3. Inițializează un vector cu n elemente cu valoarea x.

  Exemplu

  std::vector<int> v1;
  std::vector<int> v2 { 1, 2, 3 };
  std::vector<int> v3 (5, 0);
  

• at

  constexpr reference at( size_type pos );
  constexpr const_reference at( size_type pos ) const;
  

  Returnează o referință la elementul de la pos, dacă este în limita vectorului. Dacă nu, aruncă o excepție.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  data.at(1) = 9;
  
  std::cout << data[1];
  // Se afișează: 9
  

  - ### front

  constexpr reference front();
  constexpr const_reference front() const;
  

  Returnează o referință la primul element din vector.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  std::cout << data.front();
  // Se afișează: 1
  

  - ### back

  constexpr reference back();
  constexpr const_reference back() const;
  

  Returnează o referință la ultimul element din vector.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  std::cout << data.back();
  // Se afișează: 6
  

  - ### empty

  bool empty() const noexcept;
  

  Returnează false dacă vectorul are elemente și true dacă nu are.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  std::cout << data.empty();
  // Se afișează: false
  

  - ### size

  size_type size() const noexcept;
  

  Returnează numărul de elemente dintr-un vector.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  std::cout << data.size();
  // Se afișează: 6
  

  - ### clear

  void clear() noexcept;
  

  Șterge toate elementele din vector.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  
  data.clear();
  std::cout << data.size();
  // Se afișează: 0
  

  - ### insert

  iterator insert( const_iterator pos, const T& value );
  

  Inserează value înainte de poziția pos.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  
  auto it = data.begin();
  data.insert(it, 10);
  
  std::cout << data[0];
  // Se afișează: 10
  

  Pentru mai multe, a se consulta documentația. - ### erase

  1. iterator erase( const_iterator pos );
  2. iterator erase( const_iterator first, const_iterator last );
  

  1. Șterge elemetul de la poziția pos. 2. Șterge elementele dintre pozițiile first și last.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  
  auto bg = data.begin();
  auto ed = data.end();
  data.erase(bg, ed);
  
  std::cout << data.size();
  // Se afișează: 0
  

  - ### push_back

  void push_back( const T& value );
  void push_back( T&& value );
  

  Adaugă value la finalul vectorului.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  
  data.push_back(7);
  std::cout << data[6];
  // Se afișează: 7
  

  - ### pop_back

  void pop_back();
  

  Elimină ultimul element al vectorului.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  
  data.pop_back();
  std::cout << data.size();
  // Se afișează: 5
  

  - ### resize

  void resize( size_type count );
  void resize( size_type count, const value_type& value );
  

  Schimbă mărimea vectorului la count. Dacă mărimea inițială este mai mare, se șterg ultimele elemente. Dacă mărimea inițială este mai mică se inserează valori default în pozițiile noi, sau value dacă este transmisă.

  Exemplu

  std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
  
  data.resize(10, 0);
  std::cout << data[8];
  // Se afișează: 0
  

Iteratori

Iteratorii sunt folosiți pentru a arăta către locuri din memorie ale containerelor din STL și prezintă posibilitatea de a itera prin elemente. Un exemplu de iterator este un pointer, dar în STL, aceștia sunt mai complecși de atât. Aceștia reduc complexitatea și timpul de execuție al programelor. Vom vorbi mai în detaliu despre ei cursul viitor.

Funcții din STL

• begin

  constexpr iterator begin() noexcept;
  

  Returnează un iterator către primul element al containerului.

• end

  constexpr iterator end() noexcept;
  

  Returnează un iterator către ultimul element al containerului.

Exemplu

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v { 1, 2, 4, 8, 16 };
    std::vector<int> e;

    // declararea unui iterator
    std::vector<int>::iterator it = v.begin();

    if (!v.empty()) {
        std::cout << *v.begin() << '\n';
    }

    if (e.begin() == e.end()) {
        std::cout << "Vector e is empty";
    }    

    return 0;  
}
// Se afișează: 1
//              Vector e is empty

Sortarea

Pentru sortarea vectorilor se folosește funcția sort inclusă în <algorithm>.

template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );

Aceasta parcurge elementele dintre iteratorii first si last și le sortează după regula comp, care este o funcție proprie de sortare, ce returnează un bool.

Exemplu

#include <iostream>
#include <vector>
#include <algorithm>

bool cmp(const int &a, const int &b) {
    return a < b;
}

int main() {
    std::vector<int> data = { 1, 6, 4, 5, 5, 6 };

    std::sort(data.begin(), data.end(), cmp);

    for (int x : data) {
        std::cout << x << ' ';
    }
    return 0;
}
// Se afișează: 1 4 5 5 6 6

Lambda expressions

Lambdaurile sunt o modalitate convenabilă de a declara funții local, doar acolo unde sunt necesare.

Anatomie

Anatomia unei funții lambda este foarte similară cu cea a unei funcții.

Exemplu

std::sort(x, x + n,
// Lambda expression begins
    [](float a, float b) {
        return a < b;
    } 
// End of lambda expression
);

1. capture clause - aici se specifică ce variabile din afara funcții lambda vor fi folosite. Acestea pot fi pasate prin valoare sau prin referință, utilizând &, urmat de numele variabilei. Dacă dorim toate variabilele să fie incluse prin valoare putem utiliza doar un =, respectiv &, prin referință. Cu toate acestea, nu este o practică bună să trimitem toate variabile exterioare unui lambda.

   Exemplu

   [&a, b] - a este trimis prin referință
   
   [&, b] - toate variabilele sunt trimise prin referință, 
           în afară de b care e transmis prin valoare
   
   [=, &b] - toate variabilele sunt trimise prin valoare, 
           în afară de b care este transmis prin referință
   

2. parameter list - aici se specifică ce parametri îi vor fi pasați funcției lambda

3. mutable specification

4. exception-specification

5. trailing-return-type - aici se specifică tipul de date returnat

6. lambda body - aici se scrie funcționalitatea

Utilitate

Lamdaurile sunt foarte utile în general, atunci când nu vrem să poluăm codul cu funcții. Un exemplu foarte bun este în cazul sortărilor, când vrem să sortăm același lucru dupa mai multe criterii diferite. Exemplu

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v;
    std::vector<int> idx;

    // sortează v descrescător
    std::sort(v.begin(), v.end(), [](const int &a, const int &b) {
        return a > b;
    });

    // sortează v crescător
    std::sort(v.begin(), v.end(), [](const int &a, const int &b) {
        return a < b;
    });

    // sortează indicii lui idx după v[idx]
    std::sort(idx.begin(), idx.end(), [=, &v](const int &a, const int &b) {
        return v[a] < v[b]; 
    });

    return 0;

}

Se observă că în acest fel evităm declararea multor funții cmp pe care le-am folosi poate o singură dată.

Interfețe funcționale

Interfețele funcționale pot categorisi funcțiile. Fiecare interfață funcțională are o singură metodă abstractă, numită metodă funcțională pentru acea interfață funcțională, la care sunt potriviți sau adaptați parametrii expresiei lambda și tipurile de returnare.

Parcurgerea

Iteratorii sunt foarte utili la a parcurge în ordine elementele dintr-un conatiner STL.

template< class InputIt, class UnaryFunction >
constexpr UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );

Funcția for_each iterează printre elementele dintre iteratorul first și last, luând ca parametru funcția f, pentru a manipula elementele prin care iterează. Funcția f ia ca parametru referința elementului curent iterat.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    std::for_each(v.begin() + 5, v.end(), [](int &v) {
        v = 2;
    });

    std::for_each(v.begin(), v.end(), [](int &v) {
        std::cout << v << ' ';
    });

    return 0;
}
// Se afișează: 1 2 3 4 5 2 2 2 2 2

auto

auto se folosește pentru a inițializa variabile. Acesta îi spune compilatorului să stabilească sau să deducă tipul de date din context. Acesta nu este un tip de date separat sau special, ci doar un placeholder.

Este comună folosirea acestuia mai ales în situații când numele tipului de date folosit este complicat, greu de scris, ascuns sub mai multe niveluri de abstractizare. De asemenea, acesta se poate folosi chiar și pentru a salva un lambda. Cu toate acestea, utilizarea sa excesivă poate crea confuzie sau chiar erori, de aceea este necesară o convenție de denumire a variabilelor riguroasă.

Exemplu

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    auto a = 3; // int
    auto it = v.begin(); // iterator 
    auto lambdaFunc = [](int &v) {
        v = 2;
    }; // lambda

    std::for_each(v.begin() + 5, v.end(), lambdaFunc);

    std::for_each(v.begin(), v.end(), [](int &v) {
        std::cout << v << ' ';
    });

    return 0;
}