QT: работаем с библиотекой контейнеров Tulip

Библиотека Tulip – встроенный в QT (модуль QtCore) аналог STL (Standard Template Library, стандартная библиотека шаблонов языка C++).

В основе библиотеки лежат 3 понятия:

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

Работать с этими возможностями очень легко, в заметке мы рассмотрим несколько типовых примеров.

1. Контейнерные классы (контейнеры):

Последовательные (упорядоченные коллекции, в которых каждый элемент занимает определенную позицию):

QVector<T> — вектор;

QList<T> — список;

QLinkedList<T> — двусвязный список;

QStack<T> — стек;

QQueue<T> — очередь.

Ассоциативные (коллекции, в которых позиция элемента зависит от его значения):

QSet<T> — множество;

QMap<K,T> — словарь, хранящий соответствия ключей типа K и значений типа T (значения хранятся упорядоченными по ключу);

QMultiMap<K,T> — мультисловарь, может связывать с одним ключом множество значений;

QHash<K,T> — хэш, набор пар "ключ-значение", данные хранятся в произвольном порядке;

QMultiHash<K,T> — мультихэш, может связывать с одним ключом хэша множество значений.

Здесь

• <T> - обозначение типа данных (например, QString, int)
• <K> - тип данных ключа, по которому упорядочиваются данные (только для указанных типов контейнеров).

Пример 1. Добавление строк и целых чисел в вектор

QVector <QString> vs;

vs.append("Item1");

vs += "Item2";

qDebug() << vs;

QVector <int> vi;

vi.push_back(1);

vi += 2;    

qDebug() << vi;

Замечание. Здесь и далее предполагается, что в проект включены соответствующие заголовки QT, например, для показанного выше кода требуется

#include <QVector>

#include <QDebug>

Пример 2. Формирование списка строк и обмен местами первого элемента с последним.

    QList <QString> list;

    cout << "Enter the strings, 0 is the end of input" << endl;

    QTextStream qtcin(stdin);

    QString s;

    for (;;) {

        s = qtcin.readLine();

        //qtcin >> s; //если чтение до пробела

        if (s.compare("0")==0) break;

        list << s;

    }

    list.swap(0,list.size()-1);

    qDebug() << list;

Пример 3. Заполнение простого телефонного справочника

QMap <QString, QString> phoneBook;

phoneBook["Masha"] = "+79131234567";

phoneBook["Vasya"] = "+79537654321";

QMap <QString, QString>::iterator it = phoneBook.begin();

for (;it!= phoneBook.end(); ++it) qDebug() << "Name=" << it.key()

 << " Phone=" << it.value();

Пример 4. Объединение, пересечение и разность 2 числовых множеств

 QSet <int> set1;

 QSet <int> set2;

 set1 << 1 << 2 << 3;

 set2 << 2 << 3 << 4;

 QSet <int> setUnion = set1;

 setUnion.unite (set2);

 qDebug() << "Union = " << setUnion.toList();

 QSet <int> setIntersect = set1;

 setIntersect.intersect(set2);

 qDebug() << "Intersection = " << setIntersect.toList();

 QSet <int> setSubtract = set1;

 setSubtract.subtract(set2);

 qDebug() << "Subtraction = " << setSubtract.toList();

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

Пример 5. Сканирование списка строк с помощью итератора

QList <QString> list;

list << " Item1 " << " Item2 " << " Item3 ";

QListIterator <QString> it(list);

while(it.hasNext()) {

 ui->textEdit->setText(ui->textEdit->toPlainText()+"\n"+it.next());

}

Если необходимо производить изменения в процессе прохождения итератором элементов, то для этого следует воспользоваться изменяющимися (mutable) итераторами. Их классы называются аналогично, но с добавлением "Mutable": QMutableListIterator, QMutableHashIterator, QMutableLinkedListIterator, QMutableMapIterator и QmutableVector-Iterator. Метод remove() удаляет текущий элемент, а insert() производит вставку элемента в текущую позицию. При помощи метода setValue() можно присвоить элементу другое значение.

Пример 6. Замена значения элемента в списке

QList <QString> list;

list << "Item1" << "Item2" << "Item3";

QMutableListIterator <QString> it(list);

while (it.hasNext()) if (it.next()=="Item3") it.setValue("3Item");

qDebug() << list;

В QT также работают итераторы в стиле STL:

QVector <QString> vec;

vec << "Item1" << "Item2" << "Item3"; 

Пример 7. Прямой проход по вектору строк.

QVector<QString>::iterator it = vec.begin();

for (; it != vec.end(); ++it) {

 qDebug() << "Element:" << *it;

}

Пример 8. Обратный проход по вектору строк.

QVector<QString>::iterator it = vec.end();

for (;it != vec.begin();) {

 --it;

 qDebug() << "Element:" << *it;

}

3. Алгоритмы определены в заголовочном файле QtAlgorithms и представляют собой операции, применяемые к контейнерам, такие как сортировка, поиск, преобразование данных и т.д. Следует отметить, что алгоритмы реализованы не в виде методов контейнерных классов, а в виде шаблонных функций, что позволяет использовать их как для любого контейнерного класса Tulip, так и для обычных массивов. Например, для копирования элементов из одного массива в другой можно задействовать алгоритм qCopy().

Пример 9. Копирование массива строк с помощью алгоритма

QString values[] = {"Xandria", "Therion", "Nightwish", "Haggard"};

const int n = sizeof(values) / sizeof(QString);

QString copyOfValues[n];

qCopy (values, values + n, copyOfValues);

Пример 10. Сортировка списка строк с помощью алгоритма

 QList<QString> list;

 list << "gamma" << "beta" << "alpha";

 qSort(list);

 qDebug() << "Sorted list=" << list;

Пример 11. Поиск в списке строк значения с помощью алгоритма

 QList<QString> list;

 list << "alpha" << "beta" << "gamma";

 QList<QString>::iterator it =

  qFind(list.begin(), list.end(), "gamma");

 if (it != list.end()) {

  qDebug() << "Found=" << *it;

 }

 else {

  qDebug() << "Not Found";

}

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

 QList<QString> list;

 list << "gamma" << "alpha" << "beta" << "gamma";

 bool found = false;

 QList<QString>::iterator it = list.begin();

 do {

  it = qFind(it, list.end(), "gamma");

  if (it != list.end()) {

   qDebug() << "Found=" << *it << " at " << (it.i-list.begin().i);

   found = true;

   ++it;

  }

 } while (it != list.end());

 if (!found) {

  qDebug() << "Not Found";

 }

Для перебора всех элементов контейнера удобен также специально введённый в QT цикл foreach:

Пример 12. Цикл foreach

QList <QString> list;

list << "alpha" << "beta" << "gamma";

foreach (QString item, list) {

    qDebug() << "Item = " << item << endl;

}

QT делает копию контейнера при входе в foreach, поэтому данный цикл не предназначен для изменения контейнера.

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

Вариант 1.

1. Объединение двух упорядоченных линейных списков в один список, не нарушающее упорядоченности элементов

2. Подсчёт количества элементов стека, у которых равные «соседи» (следующий и предыдущий элементы).

Вариант 2.

1. Найти среднее арифметическое всех элементов непустого списка L (тип элементов - int).

2. Найти минимальный элемент в стеке.

Вариант 3.

1. Удалить из списка все отрицательные элементы.

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

Вариант 4.

1. Сделать копию стека St1 без отрицательных элементов. Результат – стек St2.

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

Вариант 5.

1. Удвоить каждое вхождение элемента Е в списке.

2. Сформировать очередь Queue, включив в нее по одному разу элементы, которые входят в одну из очередей Queue1 и Queue2.

Вариант 6.

1. Построить из одной очереди Queue две новых: Queue1 из положительных элементов и Queue2 – из остальных элементов очереди (тип элементов очереди – double).

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

Вариант 7.

1. Определить среднее арифметическое элементов очереди Queue (тип элементов - int) между первым и последним вхождением элемента Е, если элемент Е входит в очередь не менее двух раз.

2. Сформировать стек St, включив в него по одному разу элементы, которые входят хотя бы в один из стеков St1 или St2.

Вариант 8.

1. Переставить в обратном порядке все элементы в списке между первым и последним вхождением элемента Е, если элемент Е входит в список не менее двух раз.

2. в очереди, содержащей не менее двух элементов, определить количество элементов, у которых одинаковые «соседи» (следующий и предыдущий элементы)

Вариант 9.

1. Определить, есть ли в стеке St1 элементы, которые не входят в стек St2

2. Найти в очереди целых чисел минимальный по значению элемент.

Вариант 10.

1. Найти максимальный элемент в стеке.

2. Реализовать добавление в линейный односвязный список нового элемента L за каждым вхождением элемента Е, если такой элемент есть в списке.

Пример реализации задания.

Задача 1. Найти количество вхождений минимального элемента в целочисленный список.

#include <QCoreApplication>

#include <QVector>

#include <QtAlgorithms>

#include <QDebug>

#include <iostream>

using namespace std;

int cnt_min (QVector <int> list) {

 qSort(list);

 int cnt = 0, min = list.at(0);

 QVectorIterator <int> it(list);

 while(it.hasNext() && it.peekNext()==min) { cnt++; it.next(); }

 return cnt;

}

int main() {

 QVector <int> list;

 list << -5 << 5 << -1 << -5 << 3 << 3 << -5;

 qDebug() << cnt_min(list);

 return 0;

}

Задача 2. Удалить из очереди строк элементы короче 4 символов.

#include <QCoreApplication>

#include <QQueue>

#include <QtAlgorithms>

#include <QDebug>

#include <iostream>

using namespace std;

QQueue <QString> delete_ (QQueue <QString> q,int len) {

 QQueue <QString> q2;

 while (!q.isEmpty()) {

  QString qs=q.dequeue();

  if (qs.size()>=len) q2.enqueue(qs);

 }    

 return q2;

}

int main() {

 QQueue <QString> queue;

 queue << "It's" << "my" << "life" << "la-la" << "," << "hello";

 QQueue <QString> queue2 = delete_(queue,4);

 qDebug() << queue2;

 return 0;

}

Статья не исчерпывает всех возможностей Tulip, например, в этой заметке есть пример на удобный список строк QStringList, являющийся потомком QList.

16.03.2016, 23:30; рейтинг: 8179