Я делаю разный софт на Go, Python и C++
0,0
рейтинг
6 сентября 2011 в 23:24

Разработка → Просто о Qt. Библиотека контейнеров из песочницы tutorial

Qt*
Привет, хабр!

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

Вступление


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

Одна из самых распространенных задач в программировании это организация обработки групп элементов. Программисты с ней очень много парятся. Ведь нужно все разложить по полочкам… Но в 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. Данная статья ориентирована на обучение начинающих программистов.
Илья @namespace
карма
22,7
рейтинг 0,0
Я делаю разный софт на Go, Python и C++
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (45)

  • 0
    QHash в Qt до сих пор ругается на double-ключ? :-)
    • +1
      Да, ругается. Пруф:
      • +1
        Отправилось случайно, сорри. Ответ — qhash.h:880: ошибка: call of overloaded 'qHash(const double&)' is ambiguous
    • +2
      Что то мне трудновато представить ситуацию, когда бы могли понадобится дабл или флоат ключи. Думаю и в STL без специального компаратора с допуском при сравнение, работать это будет крайне ненадежно.
      • 0
        Ха! Тогда почему для QMap есть?
        • 0
          Потому, что для мэпа, ключу достаточно, чтоб его можно было сравнивать и копировать, хотя то, что он не будет ругаться на double еще не значит, что его надо туда пихать. Для hash_map/QHash/etc нужна еще и функция хеширования, которую, понятное дело, не написали. Мало того, что очень специфическая вещь и мало кому (если вообще) понадобится, еще и не существует «логичной» реализации, которая бы подошла всем, или хотя бы большей части пользователей. Даже если оставить в стороне сомнительную идею делать ключами числа с плавающей точкой и все проблемы с этим связанные, то как высчитывать для хеш для вещественного числа в общем случае?
  • +1
    Я думаю, что начинающему программисту на C++ надо сначала освоить STL. Это в любом случае надо и полезно. Ну а переход на контейнеры QT делается тогда совсем легко.
    • +3
      Если человек начинает программирование с Qt, то тут без вариантов — Qt-контейнеры. Студия для начинающего будет, как мне кажется, сложноватой, а больше альтернатив и нет. Builder уже неактуален, DOS-варианты языка С++ даже рассматривать как-то неловко. Они со всех сторон неудобные, хотя еще преподаются.

      Вообще, Qt С++ замечательно занял нишу С++ Builder'а, и он для начинающего сишника будет хорошим выбором.
      • +2
        Совершенно не согласен.
        Мухи должны быть отдельно, а котлеты отдельно. Контейнеры STL нужно знать в первую очередь. Ведь может понадобиться программировать и без применения Qt.
        • +2
          Это даже представить себе трудно: начинаем изучать C++ c Qt, но при этом задействуем контейнеры STL. А контейнеры Qt что — побоку? Но их же нельзя игнорировать, они там всюду. И они ничем не хуже. Да и семантика у них почти такая же, начинающему эта разница неважна.

          Да и не очень правильная практика — изучать С++ с шаблонов. Пусть новички хотя бы хэллоуворды попишут, с синтаксисом свыкнутся, общеупотребительные шаблоны кода изучат. Шутка ли, — подавляющее большинство моих сокурсников (специальность ИВТ, квалификация — инженер-программист) об STL не знали к моменту выпуска, все какие-то велосипеды городили. А вы говорите, — STL в первую очередь…
          • +4
            >>об STL не знали к моменту выпуска

            беда… во всех книгах по С++ есть глава по STL, это получается что дальше первых глав они книги не читали, если вообще читали…
            нет слов, одни эмоций…
            • 0
              Ничего они не читали. Украл (купил)-сдал-забыл.

              Правда, не все, конечно.
              Правда, некоторые не разменивались на С++, а сразу сели за C# и далее убеждали, что там все сделано для программиста. Сборщик мусора тот же… Как вы поняли, я не очень высокого мнения о таком подходе, потому что сколько бы ни было удобств для программиста в языке, без понимания, как оно устроено и с чего все начиналось, код будет сплошным Г. Так что да, одни эмоции.
              • +1
                С++ не краеугольный камень программирование, практика показывает что большая часть моих знакомы программистов который пишут на Java, C#, Python, PHP знают плюсы на уровне «сдал и забыл». Так что не чего страшного что твой одногрупники не знают STL, главное что бы они хорошо разобрались в том языке который они для себя выбрали.
                • 0
                  Вообще это так, конечно. Заочно желаю своим одногрупникам писать хороший код и развиваться.
    • 0
      Наоборот не сложнее, а Qt учится проще и быстрее, чем pure C++
  • +2
    По мне так статья — это обычный пересказ Шлее. И где же QArray?
    • +1
      По мне так, полезнее было бы этот класс рассмотреть
      doc.qt.nokia.com/qt3d-snapshot/qarray.html
    • +1
      В любом случае, полезно. Книгу не нагуглить, да и не у всех она есть.
      • 0
        Ну хотелось бы на Хабре видеть что-то новое и интересное. А это лучше бы в вики выложить на русскоязычном комьюнити.
        • +1
          Есть и новое, есть и старое, есть и убогое). Кому-то будет полезно, не только хаброюзерам он и прочим пользователям интернета.
          • 0
            Поэтому и хочется видеть это где-нибудь здесь
            developer.qt.nokia.com/wiki
            • +1
              да там это тоже не нужно, как по мне, это жe не более чем кривой пересказ кусков Assistant еще и с ключевыми опечатками. Например:

              iowerBound() — Возвращает итератор,

              или

              при помощи метода containts() контейнера.


              Вообще капитанская какая-то статья.
              • 0
                > P.S. Данная статья ориентирована на обучение начинающих программистов.
                • 0
                  А опечатки то указанные тоже принципиально не исправляете? Чтобы «начинающие погромисты» окончательно запутались?
                  • +1
                    А я тут при чем? Статья не моя). Уверен, автор все поправит.
                    • +1
                      УПС :) Извините, обознался.
              • 0
                Спасибо. Исправил.
        • 0
          Начинание хорошее. Мы-то с вами уже выросли, для нас этот материал новым не будет. А вот есть люди, которые только ступили на эту дорогу, — им в самый раз.

          Хотите новое? А загляните в прошлые топики интересующих вас блогов. Не может же быть такого, что вы всё оттуда читали, — обязательно что-нибудь найдете.

          А вообще, меня жажда нового привела к изучению других языков программирования (Haskell), и это одна из лучших вещей, которая со мной случилась в этом году. Рекомендую!
    • +1
      Тоже заметил немного. А вообще смысл есть — многие до сих пор думают, что Qt только для GUI фреймворк.
      • +1
        Тогда лучше писать про сеть и бд. Честно говоря непонятно перечисление стандартных контейнеров.
        • +1
          + приметивы синхронизации и высокоуровневые API по работе с ними.
  • +2
    Спасибо, хорошая статья для начинающищ. Что я заметил:

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


    Шаблонный он или не шаблонный — это детали реализации. Разница в том, что QByteArray хранит байты, QVector — объекты. В QByteArray можно поместить произвольные данные, имеющие размер отличный от одного байта.

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


    QByteArray не имеет никакого отношения к начальному, промежуточному или финальному хранению данных — он предназначен для работы с бинарными данными. Хороший пример — принятые по сети данные или содержимое не текстового файла.

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


    Приведенный пример — канонический и длинный. На практике все используют макрос foreach:

    foreach( QString s, QList< QString >() << "a" << "b" << "c" )
    {
        qDebug() << s;
    }
    


    При создании объекта QMap нужно передать его размер в конструктор


    Конструктор QMap не принимает размер.

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


    В большинстве контейнерных классов переданный размер не ограничивает максимальное количество элементов.

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


    Основное назначение QSet — гарантировать, что в множестве нет повторяющихся элементов. Высокая скорость проверки «есть ли такой элемент в множестве» — это побочный эффект, так как QSet — это надстройка над QHash.
    • +1
      Вот просто интересно, а почему QList, а не QStringList? :)
      • 0
        Захотелось заодно показать конструирование через последовательность "<<" :). Насколько я понял, формат статьи — для новичков. QStringList, QVariantList и прочие готовые контейнеры — это на мой взгляд уже продвинутое использование. Если рассматривать эффективность обучения, то сразу их вываливать на голову слушателя череповато поседствиями — утонет в объеме предоставленной информации :(.
        • 0
          На самом деле, с QStringList operator<< тоже будет работать :) Хотя я, помнится, тоже когда не был в курсе отличий между QList и QStringList — просто не знал, что от инстанцированных шаблонов можно наследоваться.
          • 0
            Естественно будет, учитывая что QStringList наследуется от QList :)
            • 0
              Хабрапарсер коварен, съел (я так понимаю, и у вас тоже) параметры шаблона. В моих комментариях выше следует читать QList<QString> вместо QList :)
  • +2
    Расскажите о Q_DECLARE_METATYPE, поддержке информации о типах в Qt. Ведь там можно даже вызывать методы по имени, соединять сигналы/слоты по имени, добавлять свои типы в QVariant, создавать объекты по имени класса, проверять наличие метода в классе. Что позволяет например легко соединять в одном проекте Qt и Javascript. Вот это было бы интересно.
  • +4
    Какая-то бессмысленная статья, на кого она рассчитана? Если на совсем новичков, которые даже не знакомы с STL — то, они ничего не поймут. Если для людей, которые знакомы с STL — то почему здесь нет сравнения с STL, почему не указано, что практически все контейнеры Qt используют парадигму «ленивого копирования», в отличии от STL, какие у неё преимущества, недостатки.

    Статья выглядит как копипаст из какого-то обзорного учебника по Qt.
    • +1
      С учетом того, что инвайт выдал автору некий НЛО, статья, однозначно, полезна для хабра. Для кого из людей она полезна — описано выше)
  • 0
    Поправьте описание QQueue. В коде объявлен стек вместо очереди и консольный вывод, если не ошибаюсь, тоже немного другой будет.
    • 0
      Спасибо. Поправил. Это все злобный копипаст.
  • 0
    А вот этот самый вектор безопасно ли возвращать из функции? При передаче в функции он передается по ссылке или по значению?
    • 0
      man неявное разделение.
  • НЛО прилетело и опубликовало эту надпись здесь

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.