=> Главная База Знаний Qt Последовательные контейнеры


Последовательные контейнеры

Последовательные контейнеры

Вектор QVector<T> представляет собой структуру данных, в которой элементы содержатся в соседних участках оперативной памяти. Вектор отличается от обычного массива С++ тем, что знает свой собственный размер и этот размер может быть изменен. Добавление элементов в конец вектора выполняется достаточно эффективно, но добавление элементов в начало вектора или вставка в его середину могут быть неэффективны.

Рис. 11.1. Вектор чисел двойной точности.

Если нам заранее известно необходимое количество его элементов, мы можем задать начальный размер при его определении и использовать оператор [ ] для заполнения его элементами; в противном случае мы должны либо затем изменить его размер, либо добавлять элементы в конец вектора. В приведенном ниже примере мы указываем начальный размер вектора:

QVector<double> vect(3);

vect[0] = 1.0;

vect[1] = 0.540302;

vect[2] = -0.416147;

Ниже та же самая задача решается путем объявления пустого вектора и применения функции append(), которая добавляет элементы в конец вектора:

QVector<double> vect;

vect.append(1.0);

vect.append(0.540302);

vect.append(-0.416147);

Вместо append() можно использовать оператор <<:

vect << 1.0 << 0.540302 << -0.416147;

Организовать цикл просмотра элементов вектора можно при помощи оператора [ ] и функции count():

double sum = 0.0;

for (int i = 0; i < vect.count(); ++i)

sum += vect[i];

Элементы вектора, которым не было присвоено какое-нибудь значение явным образом, инициализируются при помощи стандартного конструктора класса элемента. Основные типы и указатели инициализируются нулевым значением.

Вставка элементов в начало или в середину вектора QVector<T>, а также удаление элементов из этих позиций могут быть неэффективны для больших векторов. По этой причине Qt предлагает связанный список QLinkedList<T> — структуру данных, элементы которой располагаются не в соседних участках памяти. В отличие от векторов, связанные списки не поддерживают произвольный доступ к элементам, но обеспечивают «константное время» выполнения операций вставки и удаления.

Рис. 11.2. Связанный список значений типа double.

Связанные списки не обеспечивают оператор [ ], поэтому необходимо использовать итераторы для прохода по всем элементам. Итераторы также используются для указания позиции элементов. Например, в следующем фрагменте программного кода выполняется вставка строки «Tote Hosen» между «Clash» и «Ramones»:

QLinkedList<QString> list;

list.append("Clash");

list.append("Ramones");

QLinkedList<QString>::iterator i = list.find("Ramones");

list.insert(i, "Tote Hosen");

Более подробно итераторы будут рассмотрены позже в данном разделе.

Последовательный контейнер QList<T> является «массивом—списком», который сочетает в одном классе наиболее важные преимущества QVector<T> и QLinkedList<T>. Он поддерживает произвольный доступ, и его интерфейс основан на индексировании подобно применяемому векторами QVector. Вставка в конец или удаление последнего элемента списка QList<T> выполняется очень быстро, а вставка в середину выполняется быстро для списков, содержащих до одной тысячи элементов. Если не требуется вставлять элементы в середину больших списков и не нужно, чтобы элементы списка занимали последовательные адреса памяти, то QList<T> обычно будет наиболее подходящим контейнером общего назначения.

Класс QStringList является подклассом QList<QString>, который широко используется в программном интерфейсе Qt. Кроме наследуемых от базового класса функций он имеет несколько дополнительных функций, увеличивающих возможности класса по обработке строк. Класс QStringList будет обсуждаться в последнем разделе этой главы.

QStack<T> и QQueue<T> — еще два примера удобных подклассов: QStack<T> — это вектор, для работы с которым предусмотрены функции push(), pop() и top(). QQueue<T> — это список, для работы с которым предусмотрены функции enqueue(), dequeue() и head().

Во всех до сих пор рассмотренных контейнерах тип элемента T может являться базовым типом (например, int или double), указателем или классом, который имеет стандартный конструктор (т.е. конструктор без аргументов), конструктор копирования и оператор присваивания. К таким классам относятся QByteArray, QDateTime, QRegExp, QString и QVariant. Этим свойством не обладают классы Qt, которые наследуют QObject, поскольку последний не имеет конструктора копирования и оператора присваивания. На практике это не составляет проблему, потому что мы можем просто хранить в контейнере указатели на такие типы данных, а не сами объекты QObject.

Тип T также может быть контейнером; в этом случае следует иметь в виду, что необходимо разделять рядом стоящие угловые скобки пробелами, в противном случае компилятор будет сбит с толку, воспринимая >> как оператор. Например:

QList<QVector<double> > list;

Кроме только что упомянутых типов в качестве типа элементов контейнера может задаваться любой пользовательский класс, отвечающий описанным ранее критериям. Ниже дается пример такого класса:

01 class Movie

02 {

03 public:

04 Movie(const QString &title = "", int duration = 0);

05 void setTitle(const QString &title) { myTitle = title; }

06 QString title() const { return myTitle; }

07 void setDuration(int duration) { myDuration = duration; }

08 QString duration() const { return myDuration; }

09 private:

10 QString myTitle;

11 int myDuration;

12 };

Этот класс имеет конструктор, для которого необязательно указывать аргументы (хотя он может иметь до двух аргументов). Он также имеет конструктор копирования и оператор присваивания, которые обеспечиваются С++ по умолчанию. В этом классе достаточно обеспечить копирование между его членами, поэтому нам нет необходимости реализовывать свои собственные конструктор копирования и оператор присваивания.

Qt имеет две категории итераторов, используемых для прохода по элементам контейнера: итераторы в стиле Java и итераторы в стиле STL. Итераторами в стиле Java легче пользоваться, в то время как итераторы в стиле STL более мощные и могут использоваться совместно с алгоритмами Qt и STL.

С каждым классом—контейнером могут использоваться два типа итераторов в стиле Java: итератор, используемый только для чтения, и итератор, используемый как для чтения, так и для записи. Классами итераторов первого типа являются QVectorIterator<T>, QLinkedListIterator<T> и QListIterator<T>. Соответствующие итераторы чтения—записи имеют слово Mutable (изменчивый) в их названии (например, QMutableVectorIterator<T>). В дальнейшем мы основное внимание будем уделять итераторам списка QList; итераторы связанных списков и векторов имеют тот же самый программный интерфейс.

Рис. 11.3. Допустимые позиции итераторов в стиле Java.

Прежде всего следует иметь в виду, что итераторы в стиле Java не ссылаются непосредственно на элементы. Вместо этого они могут указывать на позицию перед первым элементом, после последнего элемента или между двумя элементами. Обычно организованный с их помощью цикл выглядит следующим образом:

QList<double> list;

QListIterator<double> i(list);

while (i.hasNext()) {

do_something(i.next());

}

Итератор инициализируется контейнером, для прохода по которому он будет использован. В этот момент итератор располагается непосредственно перед первым элементом. Вызов функции hasNext() возвращает true, если имеется элемент справа от итератора. Функция next() возвращает элемент, расположенный справа от итератора, и перемещает итератор в следующую допустимую позицию.

Проход в обратном направлении выполняется аналогично, с тем отличием, что сначала вызывается функция toBack() для размещения итератора после последнего элемента.

QListIterator<double> i(list);

i.toBack();

while (i.hasPrevious()) {

do_something(i.previous());

}

Функция hasPrevious() возвращает true, если имеется элемент слева от итератора; функция previous() возвращает элемент, расположенный слева от итератора, и перемещает итератор назад на одну позицию. Возможен другой взгляд на функции next() и previous(): они возвращают тот элемент, через который только что прошел итератор.

Рис. 11.4. Влияние функций previous() и next() на итераторы в стиле Java.

Допускающие запись итераторы (mutable iterators) имеют функции для вставки, модификации и удаления элементов в ходе просмотра контейнеров. В показанном ниже цикле из списка удаляются отрицательные числа:

QMutableListIterator<double> i(list);

while (i.hasNext()) {

if (i.next() < 0.0)

i.remove();

}

Функция remove() всегда работает с последним пройденным элементом. Она так же ведет себя при проходе элементов в обратном направлении:

QMutableListIterator<double> i(list);

i.toBack();

while (i.hasPrevious()) {

if (i.previous() < 0.0)

i.remove();

}

Аналогично допускающие запись итераторы в стиле Java имеют функцию setValue(), которая модифицирует последний пройденный элемент. Ниже показано, как можно заменить отрицательные числа их абсолютным значением:

QMutableListIterator<double> i(list);

while (i.hasNext()) {

int val = i.next();

if (val < 0.0)

i.setValue(-val);

}

Кроме того, можно вставлять элемент в текущую позицию итератора с помощью функции insert(). После этого итератор перемещается в позицию между новым элементом и следующим за ним.

Кроме итераторов в стиле Java каждый класс последовательных контейнеров C<T> имеет итераторы в стиле STL двух типов: С<Т>::iterator и C<T>::const_iterator. Они отличаются тем, что итератор const_iterator не позволяет модифицировать данные.

Функция контейнера begin() возвращает итератор в стиле STL, ссылающийся на первый элемент контейнера (например, list[0]), в то время как функция контейнера end() возвращает итератор, ссылающийся на элемент «после последнего элемента» (например, list[5] для списка размером 5). Если контейнер пустой, функции begin() и end() возвращают одинаковое значение. Это может использоваться для проверки наличия хотя бы одного элемента в контейнере, хотя для этой цели более удобно пользоваться функцией isEmpty().

Рис. 11.5. Допустимые позиции итераторов в стиле STL.

Синтаксис применения итераторов в стиле STL моделирует синтаксис применения указателей С++. Мы можем использовать операторы ++ и —— для перехода на следующий или предыдущий элемент, а также унарный оператор * для извлечения значения элемента из позиции текущего итератора. Для вектора vector<T> типы итераторов iterator и const_iterator определяются просто как typedef для Т * и const T *. (Так можно делать, поскольку QVector<T> хранит свои элементы в последовательных адресах памяти.)

В показанном ниже примере каждое значение в списке QList<double> заменяется своим абсолютным значением:

QList<double>::iterator i = list.begin();

while (i ! = list.end()) {

*i = qAbs(*i);

++i;

}

Несколько функций Qt возвращают контейнер. Если мы хотим в цикле обработать такое возвращенное значение функции, используя итератор в стиле STL, мы должны сделать копию контейнера и в цикле обрабатывать эту копию. Например, приводимый ниже программный код показывает, как правильно следует обрабатывать в цикле список типа QList<int>, возвращенный функцией QSplitter::sizes():

QList<int> list = splitter->sizes();

QList<int>::const_iterator i = list.begin();

while (i != list.end()) {

do_something(*i);

++i;

}

Ниже дается пример неправильного программного кода:

// Неправильный программный код

QList<int>::const_iterator i = splitter->sizes().begin();

while (i != splitter->sizes().end()) {

do_something(*i);

++i;

}

Это происходит из-за того, что функция QSplitter::sizes() возвращает новый список QList<int> по значению при каждом новом своем вызове. Если мы не сохраняем возвращенное функцией значение, С++ автоматически удалит его еще до начала итерации, оставляя нам «повисший» итератор. Дело еще усугубляется тем, что на каждом новом шаге цикла функция QSplitter::sizes() должна генерировать новую копию списка из-за вызова функции splitter->sizes().end(). Поэтому используйте общее правило: когда применяются итераторы в стиле STL, всегда следует обрабатывать в цикле копию экземпляра контейнера, возвращаемого по значению.

При использовании итераторов в стиле Java, предназначенных только для чтения, нам не надо создавать копию. Итератор обеспечит копию незаметно для нас, гарантируя всегда просмотр в цикле данных, только что возвращенных функцией. Например:

QListIterator<int> i(splitter->sizes());

while (i.hasNext()) {

do_something(i.next());

}

Подобное копирование контейнера может показаться неэффективным, но это не так из-за оптимизации посредством так называемого неявного совместного использования даннъис (implicit sharing). Это означает, что операция копирования Qt—контейнера выполняется почти так же быстро, как копирование одного указателя. Только если скопированная строка изменяется, тогда данные действительно копируются — и все это делается автоматически и незаметно для пользователя. Поэтому неявное совместное использование иногда называют «копированием при записи» (copy on write).

Привлекательность неявного совместного использования данных заключается в том, что эта оптимизация выполняется так, что мы можем не думать о ней; она просто работает сама по себе и не требует от нас какого-то дополнительного программного кода. В то же время неявное совместное использование данных способствует тому, что программист следует четкому стилю, возвращая все объекты по значению. Рассмотрим следующую функцию:

01 QVector<double> sineTable()

02 {

03 QVector<double> vect(360);

04 for (int i = 0; i <360; ++i)

05 vect[i] = sin(i / (2 * M_PI));

06 return vect;

07 }

Вызов этой функции выглядит следующим образом:

QVector<double> table = sineTable();

В отличие от этого подхода, STL склоняет нас к передаче вектора в виде неконстантной ссылки, чтобы избежать копирования, происходящего из-за возвращения функцией значения, хранимого в переменной:

01 using namespace std;

02 void sineTable(vector<double> &vect)

03 {

04 vect.resize(360);

05 for (int i = 0; i < 360; ++i)

06 vect[i] = sin(i / (2 * M_PI));

07 }

В результате вызов будет не столь простым и менее понятным:

vector<double> table;

sineTable(table);

В Qt применяется неявное совместное использование данных во всех ее контейнерах и во многих других классах, включая QByteArray, QBrush, QFont, QImage, QPixmap и QString. Это делает применение этих классов очень эффективным при передаче по значению, как аргументов функции, так и возвращаемых функциями значений.

Неявное совместное использование данных в Qt гарантирует, что данные не будут копироваться, если мы их не модифицируем. Чтобы получить максимальные выгоды от применения этой технологии, необходимо выработать в себе две новые привычки при программировании. Одна связана с использованием функции at() вместо оператора [ ] при доступе только для чтения к (неконстантному) вектору или списку. Поскольку при применении Qt—контейнеров нельзя сказать, оказывается ли [ ] с левой стороны оператора присваивания или нет, предполагается самое худшее и принудительно выполняется действительное копирование (deep сору), в то время как at() не допускается в левой части оператора присваивания.

Подобная проблема возникает при прохождении контейнера с помощью итераторов в стиле STL. Когда вызываются функции begin() или end() для неконстантного контейнера, Qt всегда принудительно выполняет действительное копирование при совместном использовании данных. Решение, позволяющее избавиться от этой неэффективности, состоит в применении по мере возможности const_iterator, constBegin() и constEnd().

В Qt предусмотрен еще один, последний метод прохода по элементам последовательного контейнера — оператор цикла foreach. Он выглядит следующим образом:

QLinkedList<Movie> list;

foreach (Movie movie, list) {

if (movie.title() == "Citizen Kane") {

cout << "Found Citizen Kane" << endl;

break;

}

}

Псевдоключевое слово foreach реализуется с помощью стандартного цикла for. На каждом шаге цикла переменная цикла (movie) устанавливается на новый элемент, начиная с первого элемента контейнера и затем двигаясь вперед. Цикл foreach автоматически использует копию контейнера при входе в цикл, и по этой причине модификации контейнера в ходе цикла не влияют на сам цикл.

Поддерживаются операторы цикла break и continue. Если тело цикла состоит из одного оператора, необязательно указывать скобки. Как и для оператора for, переменная цикла может определяться вне цикла, например:

QLinkedList<Movie> list;

Movie movie;

foreach (movie, list) {

if (movie.title() == "Citizen Kane") {

cout << "Found Citizen Kane" << endl;

break;

}

}

Определение переменной цикла вне цикла — единственная возможность для контейнеров, содержащих типы данных с запятой (например, QPair<QString, int>).

Неявное совместное использование данных работает автоматически и незаметно для пользователя, поэтому нам не надо в программном коде предусматривать специальные операторы для обеспечения этой оптимизации. Но поскольку хочется знать, как это работает, мы рассмотрим пример и увидим, что скрывается от нашего внимания. В этом примере используются строки типа QString — одного из многих неявно совместно используемых Qt—классов:

QString str1 = "Humpty";

QString str2 = str1;

Мы присваиваем переменной str1 значение «Humpty» (Humpty-Dumpty — Шалтай—Болтай) и переменную str2 приравниваем к переменной str1. К этому моменту оба объекта QString ссылаются на одну и ту же внутреннюю структуру данных в памяти. Кроме символьных данных эта структура данных имеет счетчик ссылок, показывающий, сколько строк QString ссылается на одну структуру данных. Поскольку обе переменные ссылаются на одни данные, счетчик ссылок будет иметь значение 2.

str2[0] = 'D';

Когда мы модифицируем переменную str2, выполняется действительное копирование данных, чтобы переменные str1 и str2 ссылались на разные структуры данных и их изменение приводило к изменению их собственных копий данных. Счетчик ссылок данных переменной str1 («Humpty») принимает значение 1, и счетчик ссылок данных переменной str2 («Dumpty») тоже принимает значение 1. Значение 1 счетчика ссылок означает, что данные не используются совместно.

str2.truncate(4);

Если мы снова модифицируем переменную str2, никакого копирования не будет происходить, поскольку счетчик ссылок данных переменной str2 имеет значение 1. Функция truncate() непосредственно обрабатывает значение переменной str2, возвращая в результате строку «Dump». Счетчик ссылок по-прежнему имеет значение 1.

str1 = str2;

Когда мы присваиваем строку str2 строке str1, счетчик ссылок для данных str1 снижается до 0 и приводит к тому, что теперь никакая строка типа QString не содержит значения «Humpty». Память освобождается. Обе строки QStrings теперь ссылаются на значение «Dump», счетчик ссылок которого теперь имеет значение 2.

Часто не пользуются возможностью совместного использования данных в многопоточных программах из-за условий гонок при доступе к счетчикам ссылок. В Qt этой проблемы не возникает. Классы—контейнеры используют инструкции ассемблера при реализации атомарных операций со счетчиками. Эта технология доступна пользователям Qt через применение классов QSharedData и QSharedDataPointer.