STL list HowTo - Revizia istoricului

Bmbogdan: Reveniri la ultima modificare de către 93.174.93.222 (discuţie); revenire la ultima versiune de către 81.180.68.6

2009-10-12T10:03:05Z

Reveniri la ultima modificare de către 93.174.93.222 (discuţie); revenire la ultima versiune de către 81.180.68.6

93.174.93.222: /* Ce este STL */

2009-10-12T08:52:41Z

‎Ce este STL

81.180.68.6: /* Fiţuică */

2008-03-26T16:41:46Z

‎Fiţuică

81.180.68.6: /* Fiţuică */

2008-03-26T16:41:24Z

‎Fiţuică

81.180.68.6: /* Fiţuică */

2008-03-26T16:41:14Z

‎Fiţuică

Lc la 28 decembrie 2005 20:09

2005-12-28T20:09:21Z

Lc la 28 decembrie 2005 17:53

2005-12-28T17:53:54Z

Pagină nouă

STL list HowTo

=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ţ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ă=

#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()=

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=

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=

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=

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=

Î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=

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=

Î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

=În concluzie...=

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!

@@ Linia 391: / Linia 391: @@
                                  // 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 functor123
+                                 // start si end conform conditiei specificate in functor
 =În concluzie...=

@@ Linia 391: / Linia 391: @@
                                  // 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
+                                 // start si end conform conditiei specificate in functor123
 =În concluzie...=

@@ Linia 392: / Linia 392: @@
   stable_partition(start, end, functor); // rearanjeaza elementele listei intre pozitiile
                                  // start si end conform conditiei specificate in functor
 =În concluzie...=

← Versiunea anterioară		Versiunea de la data 28 decembrie 2005 20:09
Linia 359:		Linia 359:
	linux		linux
	rocks		rocks
		+
		+	=Fiţuică=
		+
		+	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

@@ Linia 1: / Linia 1: @@
 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=
 =Iniţializare=