Versiunea de la data 12 octombrie 2009 11:52 (modificare) 93.174.93.222 (Discuție) (→‎Ce este STL) ← Diferența anterioară		Versiunea curentă din 12 octombrie 2009 13:03 (modificare) (anulare) Bmbogdan (Discuție | contribuții) m (Reveniri la ultima modificare de către 93.174.93.222 (discuţie); revenire la ultima versiune de către 81.180.68.6)
Linia 1:		Linia 1:
	STL list HowTo		STL list HowTo
−	hqpJlJ  <a href="http://npfnvwdqipty.com/">npfnvwdqipty</a>, [url=http://aoahltywajab.com/]aoahltywajab[/url], [link=http://wrzldyvuqunf.com/]wrzldyvuqunf[/link], http://nejcwlduurhb.com/	+	=Ce este STL=
		+
		+	STL este una dintre cele mai interesante unelte pe care le are la dispoziţie
		+	un programator C++. Constă într-o serie de containere precum
		+	liste, vectori, seturi (sets), maps şi o serie de algoritmi care operează pe
		+	aceste containere. Scopul bibliotecii este de a
		+	standardiza aceste containere şi aceşti algoritmi, astfel încât programatorul nu trebuie să
		+	le reinventeze de fiecare dată când are nevoie de aşa ceva.
		+
		+	Biblioteca STL este parte integrală a limbajului C++ şi a fost standardizată în prima versiune
		+	a standardului ISO C++ (1998).
		+
		+	Unul din cele mai folosite tipuri de containere în C/C++ este lista înlănţuită.
		+	Micul tutorial care urmează descrie modul de folosire a acestui tip de container.
	=Iniţializare=		=Iniţializare=

---

Versiunea curentă din 12 octombrie 2009 13:03

STL list HowTo

Ce este STL[modificare]

STL este una dintre cele mai interesante unelte pe care le are la dispoziţie un programator C++. Constă într-o serie de containere precum liste, vectori, seturi (sets), maps şi o serie de algoritmi care operează pe aceste containere. Scopul bibliotecii este de a standardiza aceste containere şi aceşti algoritmi, astfel încât programatorul nu trebuie să le reinventeze de fiecare dată când are nevoie de aşa ceva.

Biblioteca STL este parte integrală a limbajului C++ şi a fost standardizată în prima versiune a standardului ISO C++ (1998).

Unul din cele mai folosite tipuri de containere în C/C++ este lista înlănţuită. Micul tutorial care urmează descrie modul de folosire a acestui tip de container.

Iniţializare[modificare]

Iniţializarea unei liste folosind STL arată în felul următor:

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

int main (void) {
       list<string> Messages;

       return 0;
}

Simplu spunând list<string> mylist; am definit o listă de strings pe care am denumit-o mylist. Compilarea se face în felul următor:

# g++ test.cpp -o test

string poartă şi numele de value type al listei. Acesta este tipul de variabilă din containerul list. Să începem prin introducerea unor elemente în listă.

Inserarea de elemente în listă[modificare]

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

int main (void) {
       list<string> mylist;
       mylist.push_back("Info: Program started");
       mylist.push_back("Warning: No customer records found");
       mylist.push_front("Error: Out of memory");
       mylist.push_back("Info: Processing customer list");

       return 0;
}

Am adăugat astfel patru elemente de tip string în listă. Funcţia push_back() adaugă elementul la sfârşitul listei, în timp ce push_front() adaugă elementul la începutul listei.

Funcţia empty()[modificare]

Este important să ştim dacă o listă conţine sau nu elemente. Aceasta se face folosind funcţia empty():

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

int main (void) {
       list<string> mylist;
       mylist.push_back("Info: Program started");
       mylist.push_back("Warning: No customer records found");
       mylist.push_front("Error: Out of memory");
       mylist.push_back("Info: Processing customer list");

       if (!mylist.empty())
	      printList(mylist);

       return 0;
}

Detaliăm în continuare funcţia locală printList() care are ca scop tipărirea pe ecran a elementelor a mesajelor conţinute în listă.

Procesarea elementelor listei folosind instrucţiunea for[modificare]

void printList(list<string> &mylist) {
        list<string>::iterator iterator;

        for (iterator = mylist.begin(); iterator != mylist.end(); ++iterator) {
              // dereference iterator
              string msg = *iterator;
              cout << msg << endl;
        }
}

Accesarea elementelor listei se face folosind un iterator. Acesta poate fi văzut în mod simplu ca un pointer la un element al listei. Dereferenţierea lui rezultă întru-un obiect de tip value type al listei, în cazul nostru un string. Iteratorul este iniţializat la primul element al listei, şi incrementat pentru a parcurge lista până se ajunge la ultimul element. Toată logica de incrementare este definită intern în operatorul ++ şi este invizibilă utilizatorului.

Funcţia end() returnează un element aflat după valoarea de sfârşit a listei. Acest element nu poate fi dereferenţiat. Să vedem în continuare o altă versiune a funcţie locale printList().

Procesarea elementelor listei folosind algoritmul for_each[modificare]

void printString(string& str) {
       cout << str << endl;
}

void printList(list<string> &mylist) {
       for_each(mylist.begin(), mylist.end(), printString);
}

Folosim în acest exemplu algoritmul generic for_each. Trebuie să furnizăm poziţia de început şi poziţia de sfârşit a intervalului de iterare şi un pointer la o funcţie care primeşte un singur argument de tipul value type al listei şi returnează void. Acesta din urmă poate fi în mod mai general un obiect funcţie (function object) sau functor.

Observăm cum programul începe să se împartă în două secţiuni, una de control (funcţia printList() cu algoritmul generic for_each) şi una de suport (funcţia printString()).

Numărarea elementelor listei folosind algoritmul count_if[modificare]

Ca şi for_each, count_if primeşte poziţiile de început şi de sfârşit a intervalului de iterare şi în cazul general un functor care să determine dacă un element specific al listei este luat în calcul sau nu în cadrul operaţiei de numărare:

// support section
bool isInfoMessage(string& str) {
       return (str.substring(0, 4) == "Info");
}
 
void printString(string& str) {
       cout << str << endl;
}

// control section
void printList(list<string> &mylist) {
       int infos = 0;
       infos = count_if (mylist.begin(), mylist.end(), isInfoMessage);
       cout << infos << " information messages" << endl << endl;

       for_each(mylist.begin(), mylist.end(), printString);
}

Funcţiile insert(), erase() şi algoritmul find_if[modificare]

În mod similar putem folosi algoritmul generic find_if:

list<string>::iterator info_it;
info_it = find_if(mylist.begin(), mylist.end(), isInfoMessage);
cout << *info_it << endl;

find_if returnează un iterator la primul element găsit în intervalul de iteraţie care respectă condiţia specificată în isInfoMessage(). Putem în continuare să adăugăm în listă un nou element după acesta folosind funcţia insert():

list<string>::iterator new_msg;
new_msg = mylist.insert(info_it, "Some new message");

sau în mod similar putem să-l eliminăm din listă folosind funcţia erase():

mylist.erase(info_it);

O metodă mai elegantă de eliminare de elemente din listă este oferită de algoritmul remove_if.

Algoritmul remove_if[modificare]

remove_if este un algoritm generic care combinat cu funcţia erase() poate fi folosit pentru eliminarea globală din listă a unei serii de elemente. Un mic exemplu de implementare a unei funcţii care elimină toate mesajele "Info" din listă folosind algoritmul remove_if este după cum urmează:

void purgeList(list<string> &mylist) {
       list<string>::iterator new_end;
       new_end = remove_if(mylist.begin(), mylist.end(), isInfoMessage);

       mylist.erase(new_end, mylist.end());
}

remove_if elimină din listă toate elementele care îndeplinesc condiţia isInfoMessage(), însă nu distruge iteratorii listei pentru aceste elemente, astfel încât distanţa dintre begin() şi end() rămâne neschimbată. Pentru eliminarea complectă a acestor elemente folosim iteratorul new_end returnat de remove_if şi în mod explicit funcţia erase().

Codul C++ demo pentru tot ce s-a discutat până acum este listat în continuare:

#include <iostream>
#include <string>
#include <list>
using namespace std;

// support section
bool isInfoMessage(const string &str) {
   return str.substr(0,4) == "Info";
}

void printString(const string& str) {
       cout << str << endl;
}

// control section
void purgeList(list<string> &mylist) {
       list<string>::iterator new_end;
       new_end = remove_if(mylist.begin(), mylist.end(), isInfoMessage);

       mylist.erase(new_end, mylist.end());
}

void printList(list<string> &mylist) {
       int infos = 0;
       infos = count_if(mylist.begin(), mylist.end(), isInfoMessage);
       cout << infos << " information messages" << endl << endl;
       for_each(mylist.begin(), mylist.end(), printString);
}

int main (void) {
       list<string> mylist;
       mylist.push_back("Info: Program started");
       mylist.push_back("Warning: No customer records found");
       mylist.push_front("Error: Out of memory");
       mylist.push_back("Info: Processing customer list");

       if (!mylist.empty()) {
           // print list
           cout << "*** before purge ***" << endl;
           printList(mylist);
 
	
           // play around
           cout << "*** play around ***" << endl;
           // find a info element
           list<string>::iterator info_it;
           info_it = find_if(mylist.begin(), mylist.end(), isInfoMessage);
           cout << *info_it << endl;
           // add a new element after this one
           list<string>::iterator new_msg;
           new_msg = mylist.insert(info_it, "Some new message here");
           cout << *new_msg << endl;
           printList(mylist);
           // remove the element we just added
           mylist.erase(new_msg);
           printList(mylist);
 
	       
           // remove Info messages
           purgeList(mylist);
 

           // print list
           cout << "*** after purge ***" << endl;
           printList(mylist);
     }

     return 0;
}

Partiţionarea unei liste folosind funcţia splice() şi algoritmul stable_partition[modificare]

În încheiere un exemplu ceva mai complicat folosind algorimul stable_partition şi funcţia splice() pentru împărţirea argumentelor pasate unui program pe linia de comandă în flaguri şi nume de fişiere. Observaţi absenţa instrucţiunilor for şi folosirea exclusivă a algoritmilor STL şi a functorilor.

Programul începe prin crearea unei liste cu argumentele pasate pe linia de comandă când programul este rulat. Algoritmul stable_partition rearanjează elementele unei liste astfel încât elementele care nu respectă o anumită condiţie preced pe cele care respectă condiţia respectivă. Aceasta ne permite în cazul nostru să punem flagurile de program înaintea numelor de fişiere în lista de argumente.

Funcţia splice() este folosită pentru împărţirea listei de argumente în două liste folosind o condiţie evaluată pentru fiecare element al listei originale.

Programul este prezentat în continuare:

#include <iostream>
#include <string>
#include <list>
using namespace std;

// suport section
void printList(string &str) {
	cout << str << endl;
}

bool isFlag(string &str) {
	return str.substr(0, 1) == "-";
}

bool isFile(string &str) {
	return !isFlag(str);
}

// control section
int main(int argc, char **argv) {
	list<string> arguments;
	list<string>::iterator start_of_files;
	list<string> flags;
	list<string> files;

	for (int i = 1; i < argc; i++)
		arguments.push_back(argv[i]);
 		
	if (arguments.empty()) {
		cout << "No arguments" << endl;
		return 0;
	}
 
	int number_of_files =
		count_if(arguments.begin(), arguments.end(), isFile);
 			
	for_each(arguments.begin(), arguments.end(), printList);
 	
	start_of_files =
		stable_partition(arguments.begin(), arguments.end(), isFlag);
 	
	flags.splice(flags.begin(), arguments, arguments.begin(), start_of_files);
	files.splice(files.begin(), arguments, arguments.begin(), arguments.end());
 	
	cout << "***final argument list***" << endl;		
	for_each(arguments.begin(), arguments.end(), printList);
	cout << "***flag list***" << endl;		
	for_each(flags.begin(), flags.end(), printList);
	cout << "***file list - " << number_of_files << " files" << endl;		
	for_each(files.begin(), files.end(), printList);
 	
	return 0;
}

Compilarea se face simplu cu:

# g++ -o splice splice.cpp

iar la rulare obţinem

# ./splice -w linux -o rocks
-w
linux
-o
rocks
***final argument list***
***flag list***
-w
-o
***file list - 2 files
linux
rocks

Fiţuică[modificare]

list<string> mylist; // creaza o lista de elemente string
mylist.push_front("first string"); // adauga "first string" la inceputul listei
mylist.push_back("last string"); // adauga "last string" la sfarsitul listei
if (mylist.empty()) // test daca lista este goala
int list_size = mylist.size(); // numarul de elemente din lista
string &front = mylist.front(); // referinta la primul string din lista
string &back = maylist.back(); // referinta la ultimul string din lista
list<string>::iterator start = mylist.begin(); // iterator la inceputul listei
list<string>::iterator end = mylist.end(); // iterator la sfarsitul listei
string some_string = *some_iterator; // dereferentierea unui iterator este un string
mylist.insert(position, "some string"); // insereaza "some string" in lista dupa
                                        // pozitia specificata de iteratorul position
mylist.erase(position); // sterge stringul de la pozitia position din lista
mylist.clear(); // sterge toate stringurile din lista

Algoritmi:

for_each(start, end, functor); // aplica functia functor tuturor elementelor listei
                               // intre pozitia start si end (end exclusiv!)
int cnt = count_if(start, end, functor); // numara stringurile din lista intre
                                         // pozitia start si end care respecta
                                         // conditia specificata in functia functor
list<string>::iterator position = find_if(start, end, functor);
                               // gaseste primul string din lista intre pozitiile start
                               // si end care respecta conditia specificata in functor
list<string>::iterator new_end = remove_if(start, end, functor);
                               // sterge din lista toate elementel intre pozitiile start
                               // si end care respecta conditia specificata in functor
stable_partition(start, end, functor); // rearanjeaza elementele listei intre pozitiile
                               // start si end conform conditiei specificate in functor

În concluzie...[modificare]

Pe lângă faptul că ne scuteşte de reinventarea unor containere clasice de fiecare dată când avem nevoie de ele, STL impune o manieră de programare caracterizată de absenţa buclelor de program (precum for şi while) prin introducerea conceptului de functor sau function object. Aceasta duce la organizarea automată a codului programului în secţiuni de control (zonele în care apelăm algoritmii) şi secţiuni de suport asociate secţiunilor de control (definirea functorilor).

Central pentru înţelegerea bibliotecii STL este conceptul de iterator. Este folosit pentru accesarea elementelor din containere, iar fiecare algoritm primeşte astfel de iteratori ca parametrii. Iterarorii definesc intervalul de iterare în container, iterarea din exemplele date în acest articol făcându-se numai într-o singură direcţie. STL ne furnizează însă şi alte tipuri de iteratori de exemplu bidirectional, read-only, write-only, random, etc.

Pentru o folosire adecvată a acestei biblioteci este necesară o studiere atentă a diferitelor tipuri de iteratori şi ce iteratori sunt disponibili pentru fiecare container în parte. Evident acest articol nu se vrea mai mult decât o introducere!