 |
Другие контейнероподобные классы
|
|
|
|
Контейнерные классы
Введение
Библиотека Qt предоставляет набор контейнерных классов общего назначения основанных на шаблонах. Эти классы могут использоваться для хранения элементов определенного типа. Например, если вам необходим массив изменяемого размера, содержащий QString, используйте QVector<QString>.
Эти контейнерные классы разработаны для легкого, безопасного и простого использования вместо контейнеров STL. Если вы не знакомы с STL, или предпочитаете работать "только с Qt", то можете использовать эти классы вместо классов STL.
Контейнерные классы - классы с неявным совместным использованием данных, они реентерабельны, и они оптимизированы для быстрой работы, низкого потребления памяти и минимального увеличения кода (inline), результат в меньшем исполняемом файле. Кроме того, они потоко-безопасны в ситуациях, где они используются, как контейнеры только для чтения, всеми потоками используемыми для доступа к ним.
Для обхода элементов, хранящихся в контейнере, вы можете использовать один из двух типов итераторов: итераторы в стиле Java и итераторы в стиле STL. Итераторы в стиле Java легче использовать и они предоставляют высокоуровневую функциональность, тогда как итераторы в стиле STL немного более эффективны и могут быть использованы вместе с базовыми алгоритмами Qt и STL.
Qt также предоставляет конструкцию foreach, которая позволяет очень легко перебрать все элементы, хранящиеся в контейнере.
Контейнерные классы
Qt предоставляет следующие последовательные контейнеры: QList, QLinkedList, QVector, QStack и QQueue. В большинстве приложений лучше всего использовать QList. Класс реализован в виде списка-массива, что позволяет быстро добавлять в начало и в конец. Если вам нужен настоящий связанный список, то используйте QLinkedList; если вы хотите размещать записи в памяти рядом, обратите внимание на QVector. QStack и QQueue - вспомогательные классы, предоставляющие семантику FIFO и LIFO.
|
|
|
Qt также предоставляет такие ассоциативные контейнеры: QMap, QMultiMap, QHash, QMultiHash и QSet. "Multi" контейнеры поддерживают ассоциирование нескольких значений с одним ключом. "Hash" контейнеры предоставляют быстрый доступ с использованием хэш-функции для бинарного поиска в отсортированном наборе.
В качестве частных случаев, классы QCache и QContiguousCache предоставляют эффективный просмотр с хэшированием объектов в ограниченном хранилище кэша.
| Класс | Резюме |
| QList<T> | Это - безусловно наиболее часто используемый контейнерный класс. Он хранит список значений заданного типа (T), доступ к которым осуществляется по индексу. Внутри, QList реализован используя массив, гарантирующий быстрый доступ к элементам по индексу. Элементы могут быть добавлены в любой из двух концов списка используя QList::append() и QList::prepend(), или они могут быть вставлены в середину используя QList::insert(). QList наиболее оптимизированный, чем другие классы-контейнеры, чтобы развертываться в настолько маленький код насколько это возможно в исполняемом файле. QStringList унаследован от QList<QString>. |
| QLinkedList<T> | Подобен QList, за исключением того, что он используется итераторами для доступа к элементам чаще, чем целочисленные индексы. Он также обеспечивает лучшую эффективность, чем QList, когда вставляются элементы в середину большого списка, и имеет хорошую семантику итераторов. (Итераторы, указывающие на элемент в QLinkedList, остаются действительными, до тех пор пока существует элемент, в то время, как итераторы QList могут стать недействительными после вставки или удаления.) |
| QVector<T> | Хранит массив значений заданного типа в смежных ячейках памяти. Вставка значений в начало или в середину вектора может происходить довольно медленно, потому что это может сопровождаться перемещением большого количества элементов в памяти на одну позицию. |
| QStack<T> | Это вспомогательный подкласс QVector, реализующий семантику "последним пришел, первым ушел" (LIFO). Он добавляет к уже присутствующим в QVector следующие функции: push(), pop() и top(). |
| QQueue<T> | Это вспомогательный подкласс QList, реализующий семантику "первым пришел, первым ушел" (FIFO). Он добавляет к уже присутствующим в QList следующие функции: enqueue(), dequeue() и head(). |
| QSet<T> | Предоставляет однозначное математическое множество с возможностью быстрого просмотра. |
| QMap<Key, T> | Предоставляет словарь (ассоциативное множество), который хранит соответствия ключей типа Key и значений типа T. Как правило каждый ключ связан с единственным значением. QMap хранит данные, упорядоченные по ключу; если порядок не имеет значения, то класс QHash работает быстрее. |
| QMultiMap<Key, T> | Это вспомогательный подкласс от QMap, который предоставляет удобный интерфейс для многосвязного словаря, т.е. словаря, где с одним ключом может быть связано множество значений. |
| QHash<Key, T> | Имеет почти такой же API, как и QMap, но предоставляет значительно более быстрый поиск. QHash хранит свои данные в произвольном порядке. |
| QMultiHash<Key, T> | Это вспомогательный подкласс от QHash, который предоставляет удобный интерфейс для многосвязной хэш-таблицы. |
Контейнеры могут быть вложенными. Например, вполне возможно использовать QMap<QString, QList<int> >, где типом ключа является QString, а типом значения - QList<int>. Единственный нюанс - это то, что вы должны оставить пространство между закрывающими угловыми скобками (>); иначе, компилятор C++ воспримет два символа > как оператор сдвига вправо (>>) и сообщит об ошибке.
|
|
|
Контейнеры определены в индивидуальных заголовочных файлах с тем же именем, что и контейнер (например, <QLinkedList>). Для удобства, контейнеры объявлены в <QtContainerFwd>.
Значения, хранящиеся в различных контейнерах, могут быть любого присваиваемого типа данных. Для этого тип должен предоставлять конструктор по умолчанию, конструктор копирования и оператор присваивания. Это охватывает большинство типов данных, которые вы, вероятно, захотите поместить в контейнер, включая базовые типы, такие как int и double, типы указателей и типы данных Qt, такие как QString, QDate и QTime, но не охватывает типы QObject или любые из подклассов QObject (QWidget, QDialog, QTimer, и т.д.). Если вы попытаетесь создать экземпляр QList<QWidget>, компилятор сообщит, что конструктор копирования и операторы присваивания QWidget запрещены. Если вы хотите поместить эти виды объектов в контейнер, то поместите указатели на них, например, так QList<QWidget *>
|
|
|
Вот пример пользовательского типа данных, который отвечает требованием присваиваемого типа данных:
class Employee
{
public:
Employee() {}
Employee(const Employee &other);
Employee &operator=(const Employee &other);
private:
QString myName;
QDate myDateOfBirth;
};
Если вы не предоставляете конструктор копирования или оператор присваивания, C++ предоставляет реализацию по умолчанию, которая выполняет копирование объекта почленно. Определение класса в вышеприведенном примере достаточно. Также, если вы не предоставляете никаких конструкторов, то C++ предоставляет конструктор по умолчанию, который инициализирует члены класса используя их конструкторы по умолчанию. Следующий тип данных может быть помещен в контейнер, несмотря на то, что он не предоставляет явно никаких конструкторов и оператора присваивания:
struct Movie
{
int id;
QString title;
QDate releaseDate;
};
Некоторые контейнеры предъявляют дополнительные требования к типам данных, которые они могут хранить. Например, тип Key контейнера QMap<Key, T> должен предоставить operator<(). Такие особые требования документированы в подробном описании классов. В некоторых случаях, определенные функции предъявляют специальные требования; они указаны в описаниях функций. Если эти требования не выполняются, компилятор всегда будет генерировать ошибку
Контейнеры Qt предоставляют operator<<() и operator>>(), и, поэтому, они могут быть легко прочитаны и записаны используя QDataStream. Это означает, что типы данных, помещаемых в контейнер, также должны поддерживать operator<<() и operator>>(). Предоставление такой поддержки просто; вот как мы могли бы сделать ее для структуры Movie приведенной выше:
|
|
|
QDataStream &operator<<(QDataStream &out, const Movie &movie)
{
out << (quint32)movie.id << movie.title
<< movie.releaseDate;
return out;
}
QDataStream &operator>>(QDataStream &in, Movie &movie)
{
quint32 id;
QDate date;
in >> id >> movie.title >> date;
movie.id = (int)id;
movie.releaseDate = date;
return in;
}
Документация некоторых функций классов-контейнеров ссылается на значения конструируемые по умолчанию; например, QVector автоматически инициализирует свои элементы значениями по умолчанию, а QMap::value() возвращает значение по умолчанию, если указанный ключ отсутствует в словаре. Для большинства типов значений это просто означает, что они созданы используя конструктор по умолчанию (например, пустая строка для QString). Но для примитивных типов, подобных int и double, как и для типов указателей, язык C++ не предусматривает никакой инициализации; в этих случаях, контейнеры Qt автоматически инициализируют значения нулем.
Классы-итераторы
Итераторы предоставляют одинаковые средства доступа к элементам контейнера. Классы контейнеров Qt предоставляют два типа итераторов: итераторы в стиле Java и итераторы в стиле STL. Итераторы обоих типов становятся недействительными, когда данные в контейнере модифицированы или отделены от неявно разделяемых копий ожидаемого для вызова неконстантной функции-члена.
Итераторы в стиле Java
Итераторы в стиле Java являются новыми в Qt 4 и являются стандартными, используемыми в приложениях Qt. Они более удобны в использовании, чем итераторы в стиле STL, но они немного менее эффективны. Их API сделан по образцу классов-итераторов Java.
Для каждого класса-контейнера определено два типа итераторов в стиле Java: один из них предоставляет доступ только для чтения, а другой предоставляет доступ для чтения-записи.
| Контейнеры | Итераторы только для чтения | Итераторы для чтения-записи |
| QList<T>, QQueue<T> | QListIterator<T> | QMutableListIterator<T> |
| QLinkedList<T> | QLinkedListIterator<T> | QMutableLinkedListIterator<T> |
| QVector<T>, QStack<T> | QVectorIterator<T> | QMutableVectorIterator<T> |
| QSet<T> | QSetIterator<T> | QMutableSetIterator<T> |
| QMap<Key, T>, QMultiMap<Key, T> | QMapIterator<Key, T> | QMutableMapIterator<Key, T> |
| QHash<Key, T>, QMultiHash<Key, T> | QHashIterator<Key, T> | QMutableHashIterator<Key, T> |
В этом обсуждении мы сконцентрируемся на QList и QMap. Типы итераторов для QLinkedList, QVector и QSet имеют точно такой же интерфейс, что и итераторы QList; аналогично, типы итераторов для QHash имеют тот же интерфейс, что и итераторы QMap.
В отличие от итераторов в стиле STL (рассматриваемых ниже), итераторы в стиле Java указывают на ячейку памяти между элементами, а не на сами элементы. Поэтому они указывают либо на начало контейнера (перед первым элементом), либо на конец контейнера (после последнего элемента), либо между двумя элементами. На диаграмме ниже красными стрелками показаны возможные позиции итератора в списке, содержащем четыре элемента:
|
|
|
Вот типичный пример цикла для перебора всех элементов QList<QString> по порядку и вывода их в консоль:
QList<QString> list;
list << "A" << "B" << "C" << "D";
QListIterator<QString> i(list);
while (i.hasNext())
qDebug() << i.next();
Он работает следующим образом: чтобы перебрать элементы, QList помещается в конструктор QListIterator. В этот момент итератор позиционирован на начало первого элемента в списке (перед элементом "A"). Потом мы вызываем hasNext() для проверки, существует ли какой-либо элемент после позиции итератора. Если есть, то мы вызываем next(), чтобы перепрыгнуть через него. Функция next() возвращает элемент, через который перепрыгнул итератор. Для QList<QString> - это элемент типа QString.
Вот как перебрать элементы QList в обратном порядке:
QListIterator<QString> i(list);
i.toBack();
while (i.hasPrevious())
qDebug() << i.previous();
Этот код симметричен перебору в прямом порядке, за исключения того, что мы начинаем с вызова toBack() для перемещения итератора на позицию, после последнего элемента в списке.
Диаграмма, приведенная ниже, показывает эффект от вызовов функций итератора next() и previous():
В следующей таблице подводится итог API QListIterator:
| Функция | Поведение |
| toFront() | Перемещает итератор в начало списка (перед первым элементом) |
| toBack() | Перемещает итератор в конец списка (после последнего элемента) |
| hasNext() | Возвращает true, если итератор не в конце списка |
| next() | Возвращает следующий элемент и перемещает итератор на одну позицию вперед |
| peekNext() | Возвращает следующий элемент без перемещения итератора |
| hasPrevious() | Возвращает true, если итератор не в начале списка |
| previous() | Возвращает предыдущий элемент и перемещает итератор на одну позицию назад |
| peekPrevious() | Возвращает предыдущий элемент без перемещения итератора |
QListIterator не предоставляет функций для вставки или удаления элементов перебираемого списка. Для того, чтобы сделать это, вы должны использовать QMutableListIterator. Вот пример, где мы удаляем все элементы с нечетными значениями из QList<int> используя QMutableListIterator:
QMutableListIterator<int> i(list);
while (i.hasNext()) {
if (i.next() % 2!= 0)
i.remove();
}
Вызов next() осуществляется в каждой итерации цикла. Он перепрыгивает через следующий элемент в списке. Функция remove() удаляет последний элемент, через который мы перепрыгнули в списке. Вызов remove() не делает итератор недействительным, и он остается пригодным для дальнейшего использования. Это работает точно также и при переборе элементов в обратном порядке:
QMutableListIterator<int> i(list);
i.toBack();
while (i.hasPrevious()) {
if (i.previous() % 2!= 0)
i.remove();
}
Если вы желаете лишь изменить значение существующего элемента, то можете использовать функцию setValue(). В коде ниже, мы заменяем любое значение большее чем 128, на 128:
QMutableListIterator<int> i(list);
while (i.hasNext()) {
if (i.next() > 128)
i.setValue(128);
}
Точно также, как и remove(), setValue() работает с последнем элементом, который мы перепрыгнули. Если вы перебираете элементы в прямом направлении, то это элемент, расположенный прямо перед итератором, если вы перебираете элементы в обратном порядке, то это элемент, расположенный сразу за итератором.
Функция next() возвращает неконстантную ссылку на элемент списка. Для простых операций нам даже не требуется setValue():
QMutableListIterator<int> i(list);
while (i.hasNext())
i.next() *= 2;
Как было сказано выше, итераторы классов QLinkedList, QVector и QSet имеют совершенно такой же API как и у QList. Теперь обратимся к QMapIterator, который несколько отличен, так как служит для перебора пар (ключ, значение).
Как и QListIterator, QMapIterator предоставляет toFront(), toBack(), hasNext(), next(), peekNext(), hasPrevious(), previous() и peekPrevious(). Компоненты ключ и значение могут быть получены вызовом key() и value() для объекта, возвращенного next(), peekNext(), previous() или peekPrevious().
В следующем примере удаляются все пары (столица, государство), в которых название столицы оканчивается на "City":
QMap<QString, QString> map;
map.insert("Paris", "France");
map.insert("Guatemala City", "Guatemala");
map.insert("Mexico City", "Mexico");
map.insert("Moscow", "Russia");
...
QMutableMapIterator<QString, QString> i(map);
while (i.hasNext()) {
if (i.next().key().endsWith("City"))
i.remove();
}
QMapIterator также предоставляет функции key() и value(), которые работают напрямую с итератором и возвращают ключ и значение последнего элемента, который перепрыгнул итератор. Например, в следующем коде производится копирование содержимого QMap в QHash:
QMap<int, QWidget *> map;
QHash<int, QWidget *> hash;
QMapIterator<int, QWidget *> i(map);
while (i.hasNext()) {
i.next();
hash.insert(i.key(), i.value());
}
Если мы хотим перебрать все элементы, содержащие одно и то же значение, то мы можем использовать findNext() или findPrevious(). Вот пример, где мы удаляем все элементы с заданным значением:
QMutableMapIterator<int, QWidget *> i(map);
while (i.findNext(widget))
i.remove();
Итераторы в стиле STL
Итераторы в стиле STL стали доступны, начиная с версии Qt 2.0. Они совместимы с базовыми алгоритмами Qt и STL и оптимизированы по скорости.
Для каждого контейнерного класса есть два типа итераторов в стиле STL: один из них предоставляет доступ только для чтения, а другой - доступ для чтения-записи. Итераторы только для чтения должны использоваться везде, где это только возможно, так как они быстрее, чем итераторы для чтения-записи.
| Контейнеры | Итераторы только для чтения | Итераторы для чтения-записи |
| QList<T>, QQueue<T> | QList<T>::const_iterator | QList<T>::iterator |
| QLinkedList<T> | QLinkedList<T>::const_iterator | QLinkedList<T>::iterator |
| QVector<T>, QStack<T> | QVector<T>::const_iterator | QVector<T>::iterator |
| QSet<T> | QSet<T>::const_iterator | QSet<T>::iterator |
| QMap<Key, T>, QMultiMap<Key, T> | QMap<Key, T>::const_iterator | QMap<Key, T>::iterator |
| QHash<Key, T>, QMultiHash<Key, T> | QHash<Key, T>::const_iterator | QHash<Key, T>::iterator |
API итераторов в стиле STL сделан по образцу указателей в массиве. Например, оператор ++ перемещает итератор к следующему элементу, а оператор * возвращает элемент, на который позиционирован итератор. Фактически, для QVector и QStack, хранящих свои элементы в смежных ячейках памяти, тип iterator - это всего лишь typedef для T *, а тип const_iterator - всего лишь typedef для const T *.
В этом обсуждении мы сконцентрируемся на QList и QMap. Типы итераторов для QLinkedList, QVector и QSet имеют точно такой же интерфейс, что и итераторы QList; аналогично, типы итераторов для QHash имеют тот же интерфейс, что и итераторы QMap.
Вот типичный пример цикла для перебора всех элементов QList<QString> по порядку и конвертирования их в нижний регистр:
QList<QString> list;
list << "A" << "B" << "C" << "D";
QList<QString>::iterator i;
for (i = list.begin(); i!= list.end(); ++i)
*i = (*i).toLower();
В отличие от итераторов в стиле Java, итераторы в стиле STL указывают непосредственно на элемент. Функция контейнера begin() возвращает итератор, указывающий на первый элемент контейнера. Функция контейнера end() возвращает итератор, указывающий на воображаемый элемент, находящийся в позиции, следующей за последним элементом контейнера. end() обозначает несуществующую позицию; он никогда не должен разыменовываться. Обычно, он используется, как условие выхода из цикла. Если список пуст, то begin() равен end(), поэтому цикл никогда не выполнится.
На диаграмме ниже красными стрелками показаны возможные позиции итератора в списке, содержащем четыре элемента:
При переборе элементов в обратном порядке с помощью итераторов в стиле STL, требуется, чтобы оператор декремента использовался перед обращения к элементу. Вот требуемый цикл while:
QList<QString> list;
list << "A" << "B" << "C" << "D";
QList<QString>::iterator i = list.end();
while (i!= list.begin()) {
--i;
*i = (*i).toLower();
}
В этих фрагментах кода, мы использовали унарный оператор * для восстановления значения элемента (типа QString), хранящегося в некоторой позиции итератора, а затем для него вызывали QString::toLower(). Большинство компиляторов C++ (но не все) также позволяют писать i->toLower()().
Для доступа к элементам только для чтения, можно использовать const_iterator, constBegin() и constEnd(). Например:
QList<QString>::const_iterator i;
for (i = list.constBegin(); i!= list.constEnd(); ++i)
qDebug() << *i;
В следующей таблице подводится итог API итераторов в стиле STL:
| Выражение | Поведение |
| *i | Возвращает текущий элемент |
| ++i | Перемещает итератор к следующему элементу |
| i += n | Перемещает итератор вперед на n элементов |
| --i | Перемещает итератор на один элемент назад |
| i -= n | Перемещает итератор назад на n элементов |
| i - j | Возвращает количество элементов, находящихся между итераторами i и j |
Оба оператора ++ и -- могут использоваться и как префиксные (++i, --i) и как постфиксные (i++, i--) операторы. Префиксная версия изменяет итератор, и возвращает ссылку на измененный итератор; постфиксная версия, берет копию итератора перед его изменением, и возвращает эту копию. В выражениях, в которых возвращаемое значение игнорируется, мы рекомендуем использовать префиксную версию (++i, --i), так как она несколько быстрее.
Для неконстантных итераторов, возвращаемое значение унарного оператора * может быть использовано с левой стороны от оператора присваивания.
Для QMap и QHash, оператор * возвращает компонент значения элемента. Если вы хотите извлечь ключ, вызовите key() для итератора. Для симметрии, типы итераторов предоставляют также функцию value(), извлекающую значение. Например, здесь показано, как мы можем напечатать все элементы в QMap в консоль:
QMap<int, int> map;
...
QMap<int, int>::const_iterator i;
for (i = map.constBegin(); i!= map.constEnd(); ++i)
qDebug() << i.key() << ":" << i.value();
Благодаря неявному совместному использованию данных, использование значений контейнера весьма недорого. API Qt содержит множество функций, возвращающих QList или QStringList со значениями (например, QSplitter::sizes()). Если вы хотите перебрать эти значения с помощью итератора в стиле STL, то вы всегда должны иметь копию контейнера и перебирать ее элементы. Например:
// ПРАВИЛЬНО
const QList<int> sizes = splitter->sizes();
QList<int>::const_iterator i;
for (i = sizes.begin(); i!= sizes.end(); ++i)
...
// НЕПРАВИЛЬНО
QList<int>::const_iterator i;
for (i = splitter->sizes().begin();
i!= splitter->sizes().end(); ++i)
...
Эта проблема не должна возникать при использовании функций, которые возвращают константный или неконстантный указатель на контейнер.
Неявное совместное использование данных имеет и другое влияние на использование итераторов в стиле STL: вы не должны делать копии контейнера, если для него активны неконстантные итераторы. Итераторы в стиле Java не страдают таким ограничением.
Конструкция foreach
Если вы хотите перебрать все элементы контейнера по порядку, то можете использовать конструкцию Qt foreach. Данная конструкция - это дополнение Qt к языку C++, реализованное с помощью средств препроцессора.
Ее синтаксис: foreach (переменная, контейнер) оператор. В следующем примере показано использование конструкции foreach для перебора всех элементов контейнера QLinkedList<QString>:
QLinkedList<QString> list;
...
QString str;
foreach (str, list)
qDebug() << str;
Код с конструкцией foreach значительно короче, чем аналогичный код, который использует итераторы:
QLinkedList<QString> list;
...
QLinkedListIterator<QString> i(list);
while (i.hasNext())
qDebug() << i.next();
За исключением типа данных, содержащего запятую (например, QPair<int, int>), переменная, используемая для перебора элементов контейнера может быть определена внутри выражения foreach:
QLinkedList<QString> list;
...
foreach (const QString &str, list)
qDebug() << str;
И подобно любому циклу C++, вы можете заключить тело цикла foreach в фигурные скобки и использовать break для прерывания цикла:
QLinkedList<QString> list;
...
foreach (const QString &str, list) {
if (str.isEmpty())
break;
qDebug() << str;
}
При использовании с QMap и QHash, foreach предоставляет доступ к парам значений (key, value). Если вы хотите перебрать и ключи и значения, то можете использовать итераторы (которые быстрее) или написать код, подобный следующему:
QMap<QString, int> map;
...
foreach (const QString &str, map.keys())
qDebug() << str << ":" << map.value(str);
Для многосвязных карт:
QMultiMap<QString, int> map;
...
foreach (const QString &str, map.uniqueKeys()) {
foreach (int i, map.values(str))
qDebug() << str << ":" << i;
}
При входе в цикл foreach, Qt автоматически делает копию контейнера. Если вы измените контейнер во время выполнения цикла, то в цикле это не даст эффекта. (Если вы не изменяли контейнер, копирование все еще имеет место, но, благодаря неявному совместному использованию данных копирование контейнера осуществляется очень быстро.)
Поскольку для каждой итерации создаётся копия контейнера, то использование неконстантной ссылки на перменную не позволит изменять исходный контейнер. Изменения подействуют только на копию, что, вероятно, отличается от ваших ожиданий.
В дополнение к foreach, Qt также предоставляет псевдоключевое слово forever, для бесконечного цикла:
forever {
...
}
Если вас беспокоит засорение пространства имен, то вы можете отключить использование этих макросов, добавив в.pro-файл следующую строку:
CONFIG += no_keywords
Другие контейнероподобные классы
Qt включает три класса-шаблона, которые в некотором отношении напоминают контейнеры. Эти классы не предоставляют итераторов и не могут использоваться в конструкции foreach.
- QVarLengthArray<T, Prealloc> предоставляет низкоуровневый массив переменной длины. Он может использоваться вместо QVector в тех местах, где скорость особенно важна.
- QCache<Key, T> предоставляет кэш для хранения объектов некоторого типа T, ассоциированных с ключами типа Key.
- QContiguousCache<T> предоставляет эффективный способ кэширования данных, доступ к которым обычно получают непрерывным способом.
- QPair<T1, T2> хранит пары элементов.
Дополнительные нешаблонные типы, которые дополняют шаблонные контейнеры Qt, это - QBitArray, QByteArray, QString и QStringList.
Алгоритмическая сложность
Алгоритмическая сложность заключаются в том, насколько быстро (или медленно) работает каждая из функций по мере того, как количество элементов в контейнере увеличивается. Например, вставка элемента в середину QLinkedList - чрезвычайно быстрая операция независимо от количества элементов хранящихся в QLinkedList. С другой стороны, вставка элемента в середину QVector, потенциально очень дорога, если QVector содержит много элементов, потому что половину элементов придется передвинуть на одну позицию в памяти.
Чтобы описать алгоритмическую сложность мы используем следующую терминологию, основанную на нотации "большого O":
- Постоянное время: O(1). Функция, как говорят, выполняется за постоянное время, если она требует одного и того же времени независимо от того, сколько элементов присутствует в контейнере. Одним из примеров является QLinkedList::insert().
- Логарифмическое время: O(log n). Функция, которая выполняется за логарифмическое время - это функция, время выполнения которой пропорционально логарифму от количества элементов в контейнере. Одним из примеров является qBinaryFind().
- Линейное время: O(n). Функция, выполняющаяся линейно, будет выполнятся по времени прямо пропорционально количеству элементов, хранящихся в контейнере. Одним из примеров является QVector::insert().
- Линейно-логарифмическое время: O(n log n). Функция, выполняющаяся за линейно-логарифмическое время, является ассимптотически медленее, чем линейная функция, но быстрее, чем квадратичная функция.
- Квадратичное время: O(n?). Квадратично-временная функция выполняется по времени пропорционально квадрату количества элементов, хранящихся в контейнере.
В следующей таблице приведён итог алгоритмической сложности последовательных контейнерных классов Qt:
| Индексный перебор | Вставка | Предшествующая вставка. | Последующая вставка | |
| QLinkedList<T> | O(n) | O(1) | O(1) | O(1) |
| QList<T> | O(1) | O(n) | Сред. O(1) | Сред. O(1) |
| QVector<T> | O(1) | O(n) | O(n) | Сред. O(1) |
В этой таблице, "Сред." обозначает "усредненное поведение" (amortized behavior). Например, "Сред. O(1)" обозначает, что, если вы вызовите функцию единожды, то можете получить поведение O(n), но если вы вызовете её множество раз (например, n раз), усредненная величина будет равна O(1).
В следующей таблице приведён итог алгоритмической сложности ассоциативных контейнеров и наборов Qt:
Перебор ключей
Вставка
