Iterators/ro

Containere și iteratori

Generalități

Qt are clase pentru a înlocui clasele C + + STL. Containerele Qt sunt clase șablon și pot conține orice alte clase mutabile. Aceste clase container au fost concepute pentru a fi mai compacte, mai sigure și mai ușor de folosit decât containerele STL. Ele sunt partajate implicit [doc.qt.nokia.com] și pot fi apelate din mai multe threaduri. Există o largă gamă de containere, incluzând aici liste, stive, cozi, vectori asociativi și liste hash. Aceste clase conțin iteratori compatibili cu STL, cât și iteratori inspirați din Java. Iteratorii sunt obiecte care sunt utilizate pentru a se deplasa în cadrul unui container și pentru a obține acces la datele păstrate în el. Qt mai oferă de asemenea și cuvântul cheie foreach care face foarte facilă iterarea prin elementele conținute de o clasă container. Qt oferă următoarele containere secvenţiale:

1. QList [doc.qt.nokia.com]
2. QLinkedList [doc.qt.nokia.com]
3. QVector [doc.qt.nokia.com]
4. QStack [doc.qt.nokia.com]
5. QQueue [doc.qt.nokia.com]

Pentru majoritatea aplicaţiilor QList este cel mai recomdat. Dacă aveți nevoide de o listă înlănțuită utlizați QLinkedList; dacă doriți ca elementele să ocupe locuri consecutive în memorie se utilizează QVector. QStack şi QQueue oferă containeri cu semantică LIFO și FIFO.

Qt oferă de asemenea și containere asociative:

1. QMap [doc.qt.nokia.com]
2. QMultiMap [doc.qt.nokia.com]
3. QHash [doc.qt.nokia.com]
4. QMultiHash [doc.qt.nokia.com]
5. QSet [doc.qt.nokia.com]

Containerele multi furnizează suport pentru valori asociate mai multor chei. Containerele hash furnizează căutări mai rapide utilizând funcții hash în loc de căutări binare pe un set gata sortat. Containerele pot fi imbricate. De exemplu este perfect posibil să folosim un QMap<QString,QList<int> >, unde cheia este QString, iar valoarea este de tip QList<int> .

Inserarea de elemente într-un QList

Există mai multe metode de a adăuga elemente într-un QList. Putem folosi operatorul <<, sau putem folosi una dintre metodele :

• void QList::prepend ( const QList<T> & value ) – pentru a adăuga valoarea value la începutul unei listei.
• void QList::append ( const QList<T> & value ) – pentru a adăuga valoarea value la sfârșitul unei listei.
• void QList::insert ( int i, const T & value ) – pentru a insera la poziția i valoarea value.

Un exemplu de aplicare al acestor metode îl aveți mai jos :

1. QList<QString> lista;
2. lista << "Romania";
3. qDebug() << lista;
4. lista.append("Franta");
5. qDebug() << lista;
6. lista.prepend("Italia");
7. qDebug() << lista;
8. lista.insert(1, "Olanda");
9. qDebug() << lista;
10. lista.insert(4, "Grecia");
11. qDebug() << lista;

După fiecare operație efectuată asupra listei, afișăm conținutul listei și vom avea :

1. ("Romania")
2. ("Romania", "Franta")  
3. ("Italia", "Romania", "Franta")
4. ("Italia", "Olanda", "Romania", "Franta")
5. ("Italia", "Olanda", "Romania", "Franta", "Grecia")

Folosirea iteratorilor într-un QList

Pentru a accesa elementele din cadrul unei liste avem la dispoziție 3 variante. Putem folosi

• iteratorul inspirat din Java
• iteratorul inspirat din STL sau
• cuvântul cheie foreach.

Un exemplu de folosire al iteratorului inspirat din Java este mai jos :

1. QListIterator<QString> i(lista);
2. while(i.hasNext()) qDebug() << i.next();

În exemplul de mai sus se iterează de la începutul listei până la sfârșitul ei, dar la fel de bine această iterație se putea face de la sfârșitul listei până la începtul ei precum în exemplul următor :

1. QListIterator<QString> i(lista);
2. i.toBack();
3. while(i.hasPrevious())qDebug() << i.previous();

Aceleași operații de iterație se pot face cu iteratorii inspirați din STL. Putem fie itera de la începutul listei până la sfârșitul ei precum în exemplu următor :

1. QList<QString>::iterator i;
2. for(i = list.begin(); i != list.end(); ++i)qDebug() << (*i);

, fie de la sfârșitul listei până la începutul acesteia :

1. QList<QString>::iterator i = list.end();
2. while(i != list.begin()) {  --i; qDebug() << (*i); }

Dacă doriți să iterați peste toate elementele conținute de o listă puteți folosi cuvântul cheie propriu frameworkului Qt foreach. El reprezintă un adaos la limbajul C++ și este implementat folosind preprocesorul. Sintaxa sa este* foreach(variabilă,container)*. Un exemplu de folosire îl găsiți mai jos :

1. foreach(QString unElement,list) { qDebug() << unElement;  }

Complexitatea algoritmică

Din punctul de vedere al complexității algoritmice, ne preocupă rapiditatea în execuție a funcțiilor specifice diferitelor clase container. De exemplu inserarea unui element la mijlocul unui QLinkedList este o operație extrem de rapidă, indiferent de numărul de element conținute de această clasă. În schimb inserarea aceluiași element la mijlocul unui QVector este extrem de lent, mai ales în cazul în care QVector conține mai multe elemente, din moment ce jumătate dintre elemente trebuie mutate o poziție. Atunci când ne alegem un container este recomandat să ținem cont de complexitatea algoritmică a diferitelor operații. În următorul tabel se facel un bilanț al complexității algoritmice a claselor de tip container secvențial.

Tabelul 1. Bilant al complexitatii algoritmice a claselor de tip container secvential

Tabelul 1. Bilanț al complexității algoritmice a claselor de tip container secvențial

Dar sunt anumite situații în care trebuie să folosim clase de tip container asociativ. În acest caz consultăm un tabel al bilanțurilor complexității algoritmice al acestor clase.

Tabelul 2. Bilant al complexitatii algoritmice a claselor de tip container secvential

Tabelul 2. Bilanț al complexității algoritmice a claselor de tip container asociativ