Iterators/bg

Български English

[toc align_right="yes" depth="1"]

Написано от: Girish Ramakrishnan, ForwardBias Technologies

Общ преглед

Контейнерните класове в Qt ("QVector":http://doc.qt.io/qt-4.8/qvector.html, "QList":http://doc.qt.io/qt-4.8/qlist.html, "QHash":http://doc.qt.io/qt-4.8/qhash.html и т.н.) поддържат два вида итератори: В стил STL и в стил Java. Тази статия се задълбава в имплементацията на тези итератори. За въведение в контейнерните класове на Qt, прочетете "документацията":http://doc.qt.io/qt-4.8/containers.html за тях.

Итератори в стил STL

Итераторите в стил STL са страшно ефективни и бързи, защото те се държат общи линии като указатели. QVector<T>::iterator е просто typedef на T * и е указател към елемент в масив, който QVector използва. Операторите , - и т.н. са просто аритметика с указатели и използването на оператора * върху итератора е просто обръщение към стойността.

За контейнери като QList, итератора е указател към вътрешната за QList структура Node. Достатъчно е да кажем, че аритметичните операции и взимането на стойност са много бързи, тъй като те работят дъректно с данните.

Контейнерите в Qt са скрито споделени - когато копирате обект, само указател към данните се копира. Когато даден обект се модифицира, първо се създава ново кипие на данните, така че да не се засегнат другите мест, където той се използва. Процеса на създаването на копия на данните се нарича отделяне ( detach )

Тъй като, концептуално итераторите в стил STL са просто указатели, те модифицират данните директно. Като последствие от това, неконстантните итератори отделят данните, когато се създават, използвайки Container::begin(), така че другите споделени инстанции да де бъдат модифицирани. За да итерирате през контейнер, без да го модифицирате, трябва да използвате константни итератори.

Имплементацията на итератори в стил STL води до някои програмни грешки и клопки: Първи проблем:. Всяка операция, която променя структурата на вътрешните данни най-вероятно ще направи съществуващите итератори невалидни. На пример, QVector::append() може да накара QVector да създаде на ново вътрешният си масив и така всеки съществуващ вече итератор, ще стане не валиден указател. Дали итератор ще стане не валиден или не, зависи от контейнерния клас и имплементационните детайли. На пример, итератора на QMap остава валиден дори след премахване на елемент, стига да не е този, към който сочи. Същото важи и за QHash::erase(), която не прехешира, за разлика от QHash::remove(). Като цяло, правилото е да не използвате итератор след промяна на контейнера.

За пример:

QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QVector<int>::const_iterator it = vector1.constBegin();
vector1 << 5 << 6 << 7 << 8; // променяме vector1
qDebug() << *it; // опаа! невалиден указател

Втори проблем. Създаването на копие на контейнерен клас, когато има активен неконстантен итератор, може да има неочаквани странични ефекти.

QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QVector<int>::iterator it = vector1.begin();
QVector<int> vector2 = vector1; // vector2 вече споделя данни с vector1
*it = 10;
// не само vector1, но и vector2 също е модифициран!

Контйнерните класове в Qt са скрито споделени и следователно vector2 и vector1 споделят едни и същи данни. Итератора работи с тези данни директно (поради това, че итератора е просто указател). Това е противно на интуицията и природата на типовете, базирани на стойност, които гарантират, че стойностите никога не се променят зад гърба им.

h1. Итератори в стил Джава

Основната цел на итераторите в стил Джава(освен стила на писане) е да решат проблемите на тези в стил STL. Вътрешно те използват STL итераторите. Така, че за целите на тази статия, е безопасно да предположим, че итераторите в стил Джава също съдържат указатели, но све пак успяват да предотвратят проблемите на STL-ските.

Решение на първия проблем. Константните (не-промянеруеми) итератори в стил Джава решават първия проблем като държат в себе си локално копие на контейнера. Вътрешно, те са имплементирани чрез използване на итератори в стил STL, създадени върху това копие. Чрез поддържането на копие, за константният итератор в стил Джава е в безопасност от промени в оригиналния обект, тъй като Qt ще отдели данните, когато койнтейнера се модифицира. Това означава, че вие можете да продължите да обхождате дори след като оригиналния обект е станал невалиден. За да илюстрираме:

QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QVectorIterator<int> it(vector1); // 'it' вече съдържа копие на vector1
vector1 << 5 << 6 << 7 << 8; // vector1 се отделя и локалното копие в QVectorIterator остава непокътнато
qDebug() << it.value(); // безопасно, ще покаже 1

Решение на втория проблем. Неконстантните итератори в стил Джава решават втория проблем като правят контейнера несподелеруем. Несподелеруемия контейнер е такъв, който не споделя данните си дори с нови обекти, които създават негово копие. За да илюстрираме:

QVector v1;
v1 << 1 << 2 << 2;
QVector v2 = v1; // v1 и v2 споделят едни и същи данни заради скритото споделяне
v1.setSharable(false); // маркираме v1 като несподелеруем (вътрешно API) и кара контейнера дасе отдели (т.е да си направи реално копие)
QVector v3 = v1; // v3 получава свое собствено копие на данните тъй като v1 е 'несподелеруем'

Благодарение на това, вторият проблем е избегнат - писането чрез използване на итератор на един обект не презаписва данните в някой друг обект.

QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QMutableVectorIterator it(vector1); // итератора държи указател към данните във vector1 и го прави несподелеруем
QVector<int> vector2 = vector1; // тъй като vector1 е несподелеруем, vector2 получава свое собствено копие
it.setValue(10); // само vector1 се модифицира

h1. QT_STRICT_ITERATORS

По подразбиране, понякога е възможно да се приравни неконстантен итератор на константен. Мислете за итератора като typedef на някакъв тип указател, C+ позволява приравняването на неконстантни указатели към константни. За пример:

QMap<QString, QString> map;
QMap<QString, QString>::const_iterator it = map.find("girish"); // кода се компилира и работи добре, но find() връща неконстантен QMap::iterator, който отделя данните!