Pull to refresh

Просто о Qt. Библиотека контейнеров

Reading time 7 min
Views 152K
Привет, хабр!

Сегодня я хотел бы рассказать о интересной и полезной фиче. Имя ее — Библиотека контейнеров. Это не одна, а целая группа полезных фич. А их назначение — организация и обработка групп элементов. Звучит интересно, да? Сейчас рассмотрим поближе — добро пожаловать под кат.

Вступление


Хочу сказать одну вещь — статья ориентирована на начинающих программистов. Продолжаем.

Одна из самых распространенных задач в программировании это организация обработки групп элементов. Программисты с ней очень много парятся. Ведь нужно все разложить по полочкам… Но в Qt есть замечательный помощник — Библиотека контейнеров. Этот помощник находится в модуле QtCore — значит нам не надо никаких дополнительных инклюдов. И так, поехали!

Вектор QVector


Вектор — структура данных очень похожая на обычный массив. Однако использование класса вектора предоставляет некоторые преимущества по сравнению с простым массивом. Например можно узнать количество элементов внутри вектора (его размер), или динамически расширять его. Еще этот контейнер экономнее чем другие виды контейнеров. Для добавления элементов в конец последовательного контейнера можно воспользоватся методом push_back(). К элементам вектора можно обратится как посредством оператора индексации [], так и при помощи итератора. Например:

QVector<int> vec;
vec.push_back(10); // добавляем в конец вектора элемент
vec.push_back(20);
vec.push_back(30);
qDebug() << vec;

Будет выведено — QVector(10,20,30).

Массив байтов QByteArray


Этот контейнер очень похож на QVector, но разница заключается в том, что это не шаблонный класс, и в нем допускается хранение только элементов, имеющих размер один байт. Объекты типа QByteArray можно использовать везде, где требуется промежуточное хранение данных. Количество элементов массива можно задать в конструкторе, а доступ к ним получать при помощи оператора [].

QByteArray arr(3);
arr[0] = arr[1] = 0xFF;
arr[2] = 0x0;

К данным объектов класса QByteArray можно также применить операцию сжатия и обратное преобразование. Это достигается при помощи двух глобальных функций qCompress() и qUncompress(). Просто сожмем и разожмем данные:

QByteArray a = "Some text...";
QByteArray aCompressed = qCompress(a);
qDebug << qUncompress(aCompressed);

Будет выведено Some text....

Массив битов QBitArray


Этот класс управляет битовым (или булевым) массивом. Каждое из сохраняемых значений занимает только один бит, не расходуя лишней памяти. Этот тип используется для хранения большого количества переменных типа bool.
QBitArray arr(3);
arr[0] = arr[1] = true;
arr[2] = false;


Списки QList и QLinkedList


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

Списки реализует шаблонный класс QList. В общем виде данный класс представляет собой массив указателей на элементы.

Специфические операции для работы со списками:
  • move() — Перемещает элемент с одной позиции на другую.
  • removeFirst() — Выполняет удаление первого элемента списка.
  • removeLast() — Выполняет удаление последнего элемента списка.
  • swap() — Меняет местами два элемента списка на указанных позициях.
  • takeAt() — Возвращает элемент на указанной позиции и удаляет его из списка.
  • takeFirst() — Возвращает первый элемент и удаляет его из списка.
  • takeLast() — Возвращает последний элемент и удаляет его из списка.
  • toSet() — Возвращает контейнер QSet с данными содержащимися в списке.
  • toStdList() — Возвращает стандартный список STL std::List с элементами из списка.
  • toVector() — Возвращает вектор QVector с данными содержащимися в списке.

Если вы не собираетесь менять значения элементов, то, из соображения эффективности, не рекомендуется использовать оператор []. Вместо него юзайте метод at(), так как он возвращает константную ссылку на элемент.

Одна из самых распространенных операций — обход списка для последовательного получения значений каждого элемента списка. Например:
QList<int> list;
list << 10 << 20 << 30;

QValueList<int>::iterator it = list.begin(); // создаем итератор и переводим его в начало списка
while (it != list.end()) {
     qDebug() << "Element:" << *it;
     ++it;
}


В консоли будет отображено:
Element:10
Element:20
Element:30

Если вы работаете с большими списками и/или вам часто надо вставлять элементы, то эффективнее будет использовать двусвязные списки QLinkedList. Хотя этот контейнер прожорливие чем QList, зато операции вставки и удаления сводятся к переопределению четырех указателей, независимо от позиции удаляемого или вставляемого элемента.

Стек QStack


Стек реализует структуру данных, работающую по принципу Last In First Out — последним пришел, первым ушел. То есть из стека первым удаляется элемент, который был вставлен позже всех остальных.

Класс QStack представляет собой реализацию стековой структуры. Этот класс унаследован от QVector. Процесс помещения элементов в стек обычно называется проталкиванием (pushing), а извлечение из него верхнего элемента — выталкиванием (poping). Каждая операция проталкивания увеличивает размер стека на 1, а каждая операция выталкивания — уменьшает на 1. Для этих операций в классе QStack определены функции push() и pop(). Метод top() возвращает ссылку на верхний элемент. Пример использования стека:
QStack<QString> stk;
stk.push("Era");                      // наполняем стек добавляя в него новые элементы
stk.push("Corvus Corax");
stk.push("Gathering");

while (!stk.empty()) {
   qDebug() << "Element:" << stk.pop();
}


В консоли будет:
Element:«Gathering»
Element:«Corvus Corax»
Element:«Era»

Очередь QQueue


Очередь реализует структуру данных, работающую по принципу — первым пришел, первым ушел. Реализована очередь в классе QQueue, который унаследованный от QList.

Следующий пример демонстрирует пример использования очереди:
QQueue<QString> que;
que.enqueue("Era");
que.enqueue("Corvus Corax");
que.enqueue("Gathering");

while (!que.empty()) {
   qDebug() << "Element:" << que.dequeue();
}


В консоли будет:
Element:«Era»
Element:«Corvus Corax»
Element:«Gathering»

Словари QMap, QMultiMap


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

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

При создании объекта QMap нужно передать его размер в конструктор. Этот размер не является, как это принято в других контейнерных классах, размером ограничивающим максимальное количество элементов, а представляет собой количество позиций. Количество позиций должно быть больше чем количество элементов, ожидаемых для хранения, иначе поиск элементов в словаря будет проводится недостаточно эффективно. Желательно чтобы это значение относилось к разряду простых чисел, так как в этом случае размещение элементов будет более удобным.

Некоторые методы:
  • iowerBound() — Возвращает на первый элемент с заданным ключом.
  • toStdMap() — Возвращает словарь STL с элементами нашего словаря.
  • upperBound() — Возвращает на последний элемент с заданным ключом.

Одним из самых частых способов обращения к элементам словаря является использование ключа в операторе []. Но можно обойтись и без него, так как ключ и значение можно получить через метод итератора key() и value(), например:
QMap<QString,QString> mapPhonebook;
mapPhonebook["Piggy"] = "+380 93 785 11 11";
mapPhonebook["Kermit"] = "+7 85 123 65 56";
mapPhonebook["Gonzo"] = "+49 73 631 32 21";

QMap<QString,QString>::iterator it = mapPhonebook.begin();
for(;it != mapPhonebook.end(); ++it)
{
   qDebug() << "Name:" << it.key() << "Phone:" << it.value();
}


В консоли будет:
Name:Gonzo Phone: +49 73 631 32 21
Name:Kermit Phone: +7 85 123 65 562 21
Name:Piggy Phone: +380 93 785 11 11

Хэши QHash и QMultiHash



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

Так же как и в случае с QMap, следует обязательно соблюдать осторожность при использовании оператора индексации [], так как задание ключа, для которого элемент не существует, приведет к тому, что элемент будет создан. Поэтому важно всегда проверять наличие элемента, привязанного к ключу при помощи метода containts() контейнера.

Если вы намереваетесь разместить в QHash объекты собственных классов, то вам необходимо будет реализовать оператор сравнения == и специализированную функцию qHash() для вашего класса. Вот пример реализации оператора сравнения:
inline bool operator==(const MyClass& mc1, const MyClass& mc2)
{
     return (mc1.firstName() == mc2.firstName()
                 && mc1.secondName() == mc2.secondName()
                );
}


Функция qHash() должна возвращать число, которое должно быть уникальным для каждого находящегося в хэше элемента. Например:
inline uint qHash(const MyClass& mc)
{
     return qHash(mc.firstName()) ^ qHash(mc.secondName());
}


Класс QMultiHash унаследован от QHash. Он позволяет размещать значения с одинаковыми ключами и, в целом, похож на QMultiMap, но учитывает специфику своего родительского класса.

Множество QSet


Как заметил немецкий математик Георг Кантор, «Множество — это есть многое, мысленно подразумеваемое нами как единое». Это единое, в контексте Tulip, есть не что иное, как контейнер QSet, который записывает элементы в некотором порядке и предоставляет возможность очень быстрого просмотра значений и выполнения с ними операций, характерных для множеств, таких как объединение, пересечение и разность. Необходимым условием есть то, что ключи должны быть разными. Контейнер QSet можно использовать в качестве неупорядоченного списка для быстрого поиска данных.

Операции которые можно проводить с множествами: объединение, пересечение, разность.

Создадим два множества и запишем в них элементы:
QSet<QString> set1;
QSet<QString> set2;
set1 << "Lorem" << "Ipsum" << "Dolor";
set2 << "Sit" << "Amet" << "Lorem";


Произведем операцию объединения этих двух множеств, а для того чтобы элементы множеств остались неизменными, введем промежуточное множество setResult:
QSet<QString> setResult = set1;
setResult.unite(set2);
qDebug() << "Объединение = " << setResult.toList();


На экране появится следующее:

Объединение = («Lorem»,«Ipsum»,«Dolor»,«Sit»,«Amet»)


Таким же образом выполняются операции пересечения — intersect() и разности — subtract().

Итоги


Сегодня читатель должен был научится работать с разного рода контейнерами Qt. Сегодня я рассказал лишь малую долю всей картины. Впереди еще Алгоритмы, Регулярные Выражения, QVariant, и многое другое. Может я и про них напишу).

Литература

  1. 1. Макc Шлее. Qt 4.5 — Профессиональное программирование на С++
  2. 2. Qt Reference Documentation


P.S. Данная статья ориентирована на обучение начинающих программистов.
Tags:
Hubs:
+20
Comments 45
Comments Comments 45

Articles