Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Biblioteca C++ standard (Standard Template Library)

Ce conţine această bibliotecă ?
1) Biblioteca C standard.
Exemplul de mai jos afişează primele n pătrate perfecte, începând cu 0, 1, 4, ...

#include<stdio.h>
  int main()
  {
    int a[1001], n, i ;
    printf("\n n =  ") ;
    scanf("%d",  &n) ;
    for (i=0 ; i<n ; i++)
       a[i] = i * i ;
  
    for (i=0 ; i<n ; i++)
       printf("%d  ", a[i]) ;
    return 0 ;
  }

2) Componente de bază pentru operaţiile de intrare/ieşire specifice C++

3) Biblioteca de şabloane standard

Biblioteca C standard este inclusă în biblioteca C++ standard. Header-ele standard C sunt redenumite în stilul header-elor standard C++, adică în locul vechilor denumiri <stdio.h>, <stdlib.h>, <math.h> sunt introduse <cstdio>, <cstdlib>, <cmath>. Sunt acceptate totuşi şi vechile forme, aşa cum am arătat în exemplul de mai sus.

Header-ele sunt în număr de 51. Dintre acestea, 18 sunt cele preexistente din header-ele standard C (prenum <cstdio>, <cstdlib>, <cmath>). Între celelalte, 13 fişiere constituie Biblioteca de şabloane standard:

  algorithm
  deque
  functional
  iterator
  vector
  list
  map
  memory
  numeric
  queue
  set
  stack
  utility

Trebuie să includeţi la compilare conţinutul unui header standard, numindu-l într-o directivă include, ca mai jos:

#include<algorithm> // include toti  algoritmii STL
using namespace std ;

Directiva using face vizibile în program toate numele din heade-ele incluse.

În continuare, vom considera că limbajul C standard este cunoscut, aşa că vom ilustra prin exemple utilizarea unora din headere-ele menţionate mai sus.

1. Generare vector cu valori aleatoare

#include<iostream>
#include<vector>
using namespace std ;
vector <int> v;
int n;

void GenerareNumere(int  n)
  {
        int i, k;
        srand(time(0)) ;
        cout<<" n = " ;
        cin>>n ;
        for (i=1 ; i<=n ; i++)
        {
              k = 1 + rand() % 100 ; // generare numar intre 1 si 100
              v.push_back(k) ;
        }
  }

void AfisareVector()
  {
        unsigned int i ;
        for (i=0; i<v.size() ; i++)
              cout<<v[i]<<" " ;
  }
int main()
  {
        GenerareNumere(n) ;
        AfisareVector() ;
        return 0 ;
  }

2. Ordonarea crescătoare a unui şir de numere
Sortăm un vector de n numere întregi generate aleator. Complexitatea funcţiei sort din STL este O(n log n)

#include<iostream>
#include<algorithm>
using namespace std ;
int v[10001] ;
int n ;

void GenerareNumere()
  {
     int i, k;
     srand(time(0)) ;
     cout<<" n = " ;
     cin>>n ;
     for (i=0 ; i<n ; i++)
     {
       k = 1 + rand() % 100 ; // generare numar intre 1 si 100
       v[i] = k ;
     }
  }
  
void Sortare()
  {
        sort(v , v + n) ;
  }
  void AfisareVector()
  {
        int i ;
        for (i=0; i<n ; i++)
              cout<<v[i]<<" " ;
  }
  int main()
  {
        GenerareNumere() ;
        cout<<"\n\n Vectorul initial :\n " ;
        AfisareVector() ;
        Sortare() ;
        cout<<"\n\n Vectorul dupa sortare :\n " ;
        AfisareVector() ;
        return 0 ;
  }

3. Sortarea descrescătoare a unui vector
Sortarea descrescătoare utilizând funcţia sort. Se aplică functorul greater<int>() care utilizează operatorul > folosit pentru tipul int.

#include<iostream>
using namespace std ;
int main()
{
  int a[] = {100, 30, 50, 10, 4, 20, 5, 12} ;

  sort( a, a+8, greater<int>() ) ;
  for (int i=0 ; i<8 ; i++)
  cout<<a[i]<<" " ;
  return 0 ;
}

4. Sortarea punctelor din plan
Se consideră n puncte în planul xOy, puncte de coordonate întregi. Se cere sortarea celor n puncte, mai întâi după absisă şi apoi, dacă abscisele sunt egale, după ordonată. Datele se citesc din fişierul puncte.in, mai întâi n, numărul de puncte, apoi cele n puncte date prin coordonatele (x, y) în plan. Complexitatea este O(n log n).

Exemplu:
puncte.in
6
2 4
-1 -1
7 1
2 -3
-1 -3
2 8

Sursa:

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

using namespace std ;

struct Punct
{
  int x, y ;
  friend bool operator <(Punct p1, Punct p2)
  {
    if (p1.x != p2.x) return p1.x < p2.x ;
    else return p1.y < p2.y ;
  }
};

vector <Punct> v ;

int main()
{
  int i, n ;
  Punct p ;
  // citire puncte din fisier
  ifstream f("puncte.in") ;
  f>>n ;
  for (i=0 ; i<n ; i++)
  {
    f>>p.x>>p.y ;
    v.push_back(p) ;
  }
  f.close() ;

  // sortare puncte
  sort( v.begin() , v.end() , less<Punct>() ) ;

  for (i=0 ; i<n ; i++)
    cout<<v[i].x<<" "<<v[i].y<<"\n" ;

  return 0 ;
}

5. Căutarea binară
Pentru căutare binară se pot folosi două funcţii: lower_bound şi upper_bound.
Funcţia lower_bound găseşte prima poziţie în care o valoare x poate fi inserată într-un vector astfel încât să nu strice relaţia de ordine. Returnează cel mai din dreapta iterator i cu proprietatea că a[i] < x şi x <= a[i+1].

Funcţia upper_bound găseşte ultima poziţie în care o valoare x poate fi inserată într-un vector astfel încât să nu strice relaţia de ordine. Returnează cel mai din dreapta iterator i cu proprietatea că a[i] <= x şi x < a[i+1].

Complexitatea căutării binare în aceste două cazuri este O(log n)

#include<iostream>

using namespace std ;

int main()
{
  int a[] = { 2 , 3 , 5, 5, 5, 8 , 10 } ;
  int *p ;
  p = lower_bound(a , a+7 , 5) ;
  cout<<"\n Pozitia gasita : "<<p-a ; // se afiseaza 2
  cout<<" ; valoarea curenta :" <<*p<<"\n" ; // se afiseaza 5

  p = upper_bound(a , a+7 , 5) ;
  cout<<"\n Pozitia gasita : "<<p-a ; // se afiseaza 5
  cout<<" ; valoarea curenta :" <<*p<<"\n" ; // se afiseaza 8

  p = upper_bound(a , a+7 , 6) ;
  cout<<"\n Pozitia gasita : "<<p-a ; // se afiseaza 5
  cout<<" ; valoarea curenta :" <<*p<<"\n" ; // se afiseaza 8

  return 0 ;
}

6. Generarea lexicografică a permutărilor mulţimii {1,2,…,N}
Funcţia next_permutation furnizează următoarea permutare din punct de vedere lexicografic (dacă aceasta există) şi returnează 1, sau, dacă este ultima permutare, funcţia returnează 0.

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

using namespace std;

int main () 
{
  int N;
  vector<int> v;
  cout<<" N = " ;
  cin >> N;
  for (int i = 1; i <= N; ++i)
    v.push_back(i);
  do 
  {
    for (int i = 0; i < N; ++i)
    cout << v[i] << ' ';
    cout << '\n';
  } 
  while (next_permutation(v.begin(), v.end()));

return 0 ;
}

7. Utilizarea tipului mulţime (set)
O aplicaţie simplă şi uşor de înţeles, fără explicaţii:

#include<iostream>
#include<set>

using namespace std ;

int main()
{
  set <string> s;
  s.insert("Ionescu Nelu");
  s.insert("Popescu Ana");
  s.insert("Sirbu Theodor");
  s.insert("Popa Alina");
  s.insert("Zaharia Ion");
  s.insert("Barack Obama");
  cout << (s.find("Barack Obama") != s.end()); //afiseaza 1=true 
  cout << (s.find("Popa George") != s.end()); //afiseaza 0=false
  return 0 ;
}

8. Tipul map
Aplicaţie: agenda telefonica. Se introduc in agenda numele si telefonul persoanelor şi apoi se interogheaza : care este numarul de telefon al unor persoane?
Complexitatea operaţiilor de inserare si interogare pe map : O(log n)

Se citesc din fişier n linii. O linie incepe cu 1 sau cu 2. Dacă este 1, atunci se introduce un nou nume în agendă, iar dacă este 2 se întreabă care este numărul de telefon al nuei persoane. Dacă persoana nu există, nu se afişează nimic.

Fişierul carte_telefon.txt
8
1 Vasilache 0235-333444
1 Ionescu 0232-123456
1 Popescu 0744-333333
1 Caragea 1743-1909090
1 Barbu 0235-7878787
2 Vasilache
2 Ionescu
2 Popovici

#include<iostream>
#include<fstream>
#include<map>

using namespace std ;

map <string, string> carte;

int main()
{
  int i, n, op ;
  char nume[40], nrtel[15] ;

  ifstream fin("carte_telefon.txt") ;
  fin>>n ;
  for (i=0 ; i<n ; i++)
  {
    fin>>op ;
    if (op == 1)
    {
       fin>>nume>>nrtel ;
       carte[nume] = nrtel ;
    }
    else
    {
       fin>>nume ;
       cout<<"Nume cautat :"<<nume<<" ;telefonul :"<<carte[nume]<<"\n";
    }
  }
  return 0 ;
}
9. Utilizarea stivei – conversia în baza 2 a unui număr natural
#include<iostream>
#include<stack>

using namespace std ;

int main()
{
  stack <int> stiva ;
  int n ;
  cout<<" n = " ;
  cin>>n ;
  while (n > 0)
  {
    stiva.push( n % 2 ) ;
    n /= 2 ;
  }
  cout<<"Numarul in baza 2 : " ;
  while (!stiva.empty())
  {
    cout<<stiva.top() ;
    stiva.pop() ;
  }
  return 0 ;
}
10. Coadase verifică dacă un număr este egal cu oglinditul său.
#include<iostream>
#include<queue>
using namespace std ;
int main()
{
  int n, k ;
  queue <int> coada;

  cout<<" n = " ; cin>>n;

  k = n ;
  while (k > 0)
  {
    coada.push(k%10) ;
    k /= 10 ;
  }

  k = 0 ;
  while (!coada.empty())
  {
    k = k * 10 + coada.front() ;
    coada.pop() ;
  }

  if (n == k) cout<<"oglindit" ;
  else cout<<"neoglindit" ;

  return 0 ;
}

11. Coada de priorităţi

Coada de priorităţi este o structură de date care permite, ca şi coada, operaţiile de inserare şi extragere. Şi pentru că uneori dorim ca datele depuse în coadă să fie ordonate - crescător sau descrescător - după un anumit criteriu, coada de priorităţi asigură faptul că operaţiile de introducere şi extragere se realizează în timp logaritmic. Dacă s-ar fi utilizat o coadă, atunci operaţia de introducere ar fi avut complexitatea liniară, iar operaţie de extragere timp constant.

O primă aplicaţie va introduce în coada de priorităţi 10 numere întregi aleatoare, coada de priorităţi le memorează astfel încât prima valoare extrasă este cea mai mare dintre valorile depuse (deci coada de priorităţi este organizată ca un max-heap).

#include<iostream>
#include <queue>
#include<ctime>
#include<cstdlib>

using namespace std;

priority_queue <int> q;

int main()
{
	int i, x;
	srand(time(0));
	for (i = 1; i <= 20; i++)
	{
		x = rand() % 50;
		q.push(x);
	}
	
	while (!q.empty())
	{
		x = q.top();
		cout << x << " ";
		q.pop();
	}
	
	return 0;
}

O a doua aplicaţie are la bază o coadă care memorează o structură. Elementele depuse în coada de priorităţi vor putea fi extrase în ordinea descrescătoare a costului. Această modalitate de utilizare a unei cozi de priorităţi este uneori utilă, de exemplu la implementarea algoritmilor de distanţe minime (de cost minim) precum algoritmul lui Lee, algoritmul lui Dijstra. Vom depune din nou 10 valori triplete de forma (x, y, cost), urmând ca extragerea elementelor să se realizeze în ordinea descrescătoare a costului. Pentru uşurinţă, x, y şi costul se generează aleator. Este necesară implementarea unei funcţii de comparare, practic o redefinire a operatorului <.

#include<queue>
#include<algorithm>
#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

struct Coord {
    int x, y, cost;
    bool operator < (const Coord& e) const 
	{
        return cost > e.cost;
    }
};

priority_queue <Coord> q;

int main()
{
	Coord w;
	int i;
	srand(time(0));
	for (i = 1; i <= 10; i++)
	{
		w.x = rand() % 10;
		w.y = rand() % 10;
		w.cost = 1 + rand() % 50;
		q.push(w);
	}

	while (!q.empty())
	{
		w = q.top();
		cout << w.x << " " << w.y << " " << w.cost << "\n";
		q.pop();
	}

	return 0;
}

12. Parcurgerea în lăţime a unui graf neorientat reprezentat prin liste de adiacenţă

Listele sunt memorate cu ajutorul vectorilor, iar coada utilizată în BFS este gestionată cu o coadă. Datele de citesc din fişierul graf.in în forma:
n – numărul de vârfuri
m – numărul de muchii
x1  y1 – muchii date prin extremităţile lor
x2  y2
….
xm  ym

Exemplu:
graf.in
6
7
1 2
1 3
1 4
2 5
3 5
4 5
6 5

Programul sursă:
#include<fstream>
#include<iostream>
#include<vector>
#include<queue>

using namespace std ;

vector<int> L[201] ;
queue<int> coada ;
unsigned int n, viz[201] ;

void Citire()
{
  unsigned int i, x, y, m ;
  ifstream f("graf.in") ;
  f >> n >> m ;

  for (i = 1 ; i <= m ; i++)
  {
    f>>x>>y ;
    L[x].push_back(y) ;
    L[y].push_back(x) ;
  }
}

void AfisareListe()
{
  unsigned int i, j ;
  for (i=1 ; i<=n ; i++)
  {
    for (j=0 ; j < L[i].size() ; j++)
    cout<<L[i][j]<<" " ;
    cout<<"\n" ;
  }
}

void BFSListeAdiacenta(int nod_start)
{
  unsigned int i, k, j ;
  for(i=1 ; i<=n ; i++)
  viz[i] = 0 ;
  coada.push(nod_start) ;
  viz[nod_start] = 1 ;

  while (!coada.empty())
  {
    k = coada.front() ;
    cout<<k<<" " ;
    coada.pop() ;
    for(i=0 ; i<L[k].size() ; i++)
    {
      j = L[k][i] ;
      if (viz[j] == 0)
      {
        coada.push(j) ;
        viz[j] = 1 ;
      }
    }
  }
}

int main()
{
  Citire() ;
  AfisareListe() ;
  cout<<"\n\n Parcurgerea BFS(6) : " ;
  BFSListeAdiacenta(6) ;
  return 0 ;
}

Bibliografie :

Constantin Gălăţan – Introducere în Standard Template Library, Editura All, 2008
http://www.cplusplus.com
http://infoarena.ro/stl

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =