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

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

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

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

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

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

Ктулху съел часть контента этой статьи... но, кажется, Красная Армия исправила это (27.02.2021)

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> - тип данных ключа, по которому упорядочиваются данные (только для указанных типов контейнеров).

Общие операторы и методы всех контейнеров

Оператор, метод Описание
== и != Операторы сравнения, равно и не равно
= Оператор присваивания
[] Оператор индексации. Исключение составляют только классы QSet <T> и QLinkedList <T>, в них этот оператор не определен
begin() и constBegin() Методы, возвращающие итераторы, установленные на начало последовательности элементов контейнера. Для класса QSet <T> возвращаются только константные итераторы
end() и constEnd() Методы, возвращающие константные итераторы, установленные на конец последовательности элементов контейнера
clear() Удаление всех элементов контейнера
insert() Операция вставки элементов в контейнер
remove() Операция удаления элементов из контейнера
size() и count() Оба метода идентичны — возвращают количество элементов контейнера, но применение первого предпочтительно, т. к. соответствует STL
value() Возвращает значение элемента контейнера. В QSet <T> этот метод не определен
empty() и isEmpty() Возвращают true, если контейнер не содержит ни одного элемента. Оба метода идентичны, но применение первого предпочтительно, т. к. соответствует STL

Здесь и далее предполагается, что методы могут иметь различные перегрузки, а конкретные классы, конечно, содержат и уникальные для них методы.

Общие методы последовательных контейнеров

Оператор/метод Описание
+ Объединяет элементы двух контейнеров
+= Добавляет элемент в контейнер (то же, что и <<)
<< Добавляет элемент в контейнер
at() Возвращает указанный элемент
back() и last() Возвращают ссылку на последний элемент. Эти методы предпо-лагают, что контейнер не пуст. Оба метода back() и last() идентичны, но применение первого предпочтительнее, т. к. он соответствует STL
contains() Проверяет, содержится ли переданный в качестве параметра элемент в контейнере
erase() Удаляет элемент, расположенный на позиции итератора, передаваемого в качестве параметра
front() и first() Возвращают ссылку на первый элемент контейнера. Методы предполагают, что контейнер не пуст. Оба метода front() и first() идентичны, но применение первого более предпочтительно, т. к. он соответствует STL
indexOf() Возвращает позицию первого совпадения найденного в контейнере элемента, в соответствии с переданным в метод значением. Внимание: в контейнере QLinkedList этот метод отсутствует
lastIndexOf() Возвращает позицию последнего совпадения найденного в контейнере элемента, в соответствии с переданным в метод значением. Внимание: в контейнере QLinkedList этот метод отсутствует
mid() Возвращает контейнер, содержащий копии элементов, задаваемых начальной позицией и количеством
pop_back() Удаляет последний элемент контейнера
pop_front() Удаляет первый элемент контейнера
push_back() и append() Методы добавляют один элемент в конец контейнера. Оба метода идентичны, но применение первого предпочтительно, т. к. он соответствует STL
push_front() и prepend() Методы добавляют один элемент в начало контейнера. Оба ме-тода идентичны, но применение первого предпочтительно, т. к. он соответствует STL
replace() Заменяет элемент, находящийся на заданной позиции, значением, переданным как второй параметр

Некоторые методы контейнера QVector <T>

Метод Описание
data() Возвращает указатель на данные вектора (т. е. на обычный массив)
fill() Присваивает одно и то же значение всем элементам вектора
reserve() Резервирует память для количества элементов, в соответствии с переданным значением
resize() Устанавливает размер вектора в соответствии с переданным значением
toList() Возвращает объект QList с элементами, содержащимися в векторе
toStdVector() Возвращает объект std::vector с элементами, содержащимися в векторе

Пример 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>

Некоторые методы контейнера QList <T>

Метод Описание
move() Перемещает элемент с одной позиции на другую
removeFirst() Удаляет первый элемент списка
removeLast() Удаляет последний элемент списка
swap() Меняет местами два элемента на указанных позициях
takeAt() Возвращает элемент на указанной позиции и удаляет его
takeFirst() Удаляет первый элемент и возвращает его
takeLast() Удаляет последний элемент и возвращает его
toSet() Возвращает контейнер QSet <T> с данными, содержащимися в объекте QList <T>
toStdList() Возвращает стандартный список STL std::list <T> с элементами, содержащимися в объекте QList <T>
toVector() Возвращает объект вектора QVector <T> с элементами, содержащимися в объекте QList <T>

Пример 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;

Общие методы ассоциативных контейнеров

Метод Описание
contains() Возвращает значение true, если контейнер содержит элемент с заданным ключом. Иначе возвращается значение false
erase() Удаляет элемент из контейнера в соответствии с переданным итератором
find() Осуществляет поиск элемента по значению. В случае успеха возвращает итератор, указывающий на этот элемент, а в случае неудачи итератор указывает на метод end()
insertMulti() Вставляет в контейнер новый элемент. Если элемент уже присутствует в контейнере, то создается новый элемент. Данный метод отсутствует в классе QSet <T>
insert() Вставляет в контейнер новый элемент. Если элемент уже присутствует в контейнере, он замещается новым элементом. Данный метод отсутствует в классе QSet <T>
key() Возвращает первый ключ в соответствии с переданным в этот метод значением. Данный метод отсутствует в классе QSet <T>
keys() Возвращает список всех ключей, находящихся в контейнере. Данный метод отсутствует в классе QSet <T>
take() Удаляет элемент из контейнера в соответствии с переданным ключом и возвращает копию его значения. Данный метод отсутствует в классе QSet <T>
unite() Добавляет элементы одного контейнера в другой
values() Возвращает список всех значений, находящихся в контейнере

Пример 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();

Некоторые методы контейнера QSet <T>

Метод Описание
intersect() Удаляет элементы множества, не присутствующие в переданном множестве (пересечение множеств)
reserve() Задает размер хэш-таблицы множества
squeeze() Уменьшает объем внутренней хэш-таблицы для экономии памяти
subtract() Удаляет элементы множества, присутствующие в переданном множестве (разность множеств)
toList() Возвращает объект типа QList <T>, содержащий элементы множества QSet <T>
unite() Объединяет элементы двух множеств

Пример 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. Итераторы позволяют перемещаться по элементам контейнера, абстрагируясь от структуры данных.

Методы QListIterator, QLinkedListIterator, QVectorIterator, QHashIterator, QMapIterator , QSetIterator

Метод Описание
toFront() Перемещает итератор на начало списка
toBack() Перемещает итератор на конец списка
hasNext() Возвращает значение true, если итератор не находится в конце списка
next() Возвращает значение следующего элемента списка и перемещает итератор на следующую позицию
peekNext() Просто возвращает следующее значение без изменения позиции итератора
hasPrevious() Возвращает значение true, если итератор не находится в начале списка
previous() Возвращает значение предыдущего элемента списка и перемещает итератор на предыдущую позицию
peekPrevious() Возвращает предыдущее значение без изменения позиции итератора
findNext(const T&) Поиск заданного элемента в прямом направлении
findPrevious(const& T) Поиск заданного элемента в обратном направлении

Пример 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);

Некоторые алгоритмы QT

Алгоритм Описание
qBinaryFind() Двоичный поиск заданных значений
qCopy() Копирование элементов, начиная с первого
qCopyBackward() Копирование элементов, начиная с последнего
qCount() Подсчет элементов контейнера
qDeleteAll() Удаление всех элементов. Необходимо, чтобы элементы контейнера не были константными указателями
qEqual() Сравнение. Необходимо, чтобы для размещенных объектов был определен оператор ==
qFill() Присваивает всем элементам контейнера заданное значение
qFind() Поиск заданных значений
qLowerBound() Нахождение первого элемента со значением, большим либо равным заданного
qUpperBound() Нахождение первого элемента со значением, строго большим заданного
qSort() Сортировка элементов
qStableSort() Сортировка элементов с сохранением порядка следования равных элементов
qSwap() Перемена двух значений местами

Пример 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, поэтому данный цикл не предназначен для изменения контейнера.

Примеры реализации задач на контейнеры QT

Задача 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;
}

Задача 3. Возможна также реализация задач в виде виджета, работающего со списком строк QStringList. Класс QStringList удобен, прежде всего, потому, что имеет дополнительные методы для фильтрации данных и легко взаимодействует со стандартными компонентами QT, "понимающими" строки QString. Показанный ниже виджет создан на основе класса QWidget без создания формы (интерфейс спроектирован логически в конструкторе виджета).

Файл widget.h
#ifndef WIDGET_H
#define WIDGET_H

#include <QWidget>
#include <QtWidgets>
class Widget : public QWidget {
    Q_OBJECT
private:
    QVBoxLayout *layout;
    QTextEdit *textEdit;
    QMenuBar *menuBar;
    QMenu *fileMenu;
    QAction *newAction,*doAction,*exitAction;
private slots:
    void newFile(void);
    void doFile(void);
    void exitFile(void);
public:
    Widget(QApplication *a=0,QWidget *parent = 0);
    ~Widget();
};
#endif // WIDGET_H
Файл widget.cpp
#include "widget.h"

Widget::Widget(QApplication *a,QWidget *parent) : QWidget(parent) {
 this->menuBar = new QMenuBar(this);
 this->fileMenu = new QMenu(tr("&Файл"));
 this->menuBar->addMenu(this->fileMenu);
 this->newAction = new QAction(tr("&Новый"),this->fileMenu);
 this->doAction = new QAction(tr("&Выполнить"),this->fileMenu);
 this->exitAction = new QAction(tr("В&ыход"),this->fileMenu);
 this->fileMenu->addActions(
  QList <QAction *> () << this->newAction << this->doAction << this->exitAction
 );
 QObject::connect(this->newAction,SIGNAL(triggered()),
  this,SLOT(newFile()));
 QObject::connect(this->doAction,SIGNAL(triggered()),
  this,SLOT(doFile()));
 QObject::connect(this->exitAction,SIGNAL(triggered()),
  this,SLOT(exitFile()));
 this->textEdit = new QTextEdit(this);
 this->layout = new QVBoxLayout(this);
 this->layout->setMargin(5);
 this->layout->addWidget(this->textEdit);
 this->layout->setMenuBar(this->menuBar);
 this->setLayout(this->layout);
 this->setWindowTitle("Мой виджет");
 this->setMinimumSize(320,240);
 this->resize(640,480);
 this->setGeometry(QStyle::alignedRect(
   Qt::LeftToRight,Qt::AlignCenter,this->size(),
   a->desktop()->availableGeometry()));
}

Widget::~Widget() { }

void Widget::newFile(void) { this->textEdit->clear(); }

void Widget::doFile(void) {
 QString String = this->textEdit->toPlainText();
 QStringList list = String.split("\n");
 //обработка QStringList
 QRegExp regExp("^(?!\\s*$).+");
 list = list.filter(regExp); //убрали строки только из разделителей
 list.replaceInStrings(QRegularExpression("\\s+")," ");
  //убрали лишние разделители между словами
 list.replaceInStrings(QRegularExpression("^\\s+|\\s+$"),"");
  //убрали лишние разделители в начале или конце строк
 this->textEdit->clear();
 this->textEdit->append(list.join("\n"));
}

void Widget::exitFile(void) { QApplication::quit(); }
Файл main.cpp
#include "widget.h"
#include <QApplication>

int main(int argc, char *argv[]) {
 QApplication a(argc, argv);
 Widget w(&a);
 w.show();
 return a.exec();
}

Задача 4. Работа с другими контейнерами может быть организована аналогично, изменится только наполнение метода doFile(). Например, в показанном ниже коде вводимые пользователем строки вида "ключ:значение", где "ключ" – целое число, а "значение" – строка, записываются в мультихэш (ассоциативный массив, в котором одному ключу может соответствовать несколько значений).

Код вставляется перед оператором this->textEdit->clear();

QMultiHash <int,QString> hash; //Ключ - число, значения - строки
 QStringList::iterator it = list.begin();
 int key=0; //Ключ для элементов, которым его не дал пользователь
 for (;it!=list.end();++it) { //Пройти по списку элементов "ключ:значение"
  QStringList item = (*it).split(":",QString::SkipEmptyParts);
   //разбить элемент по разделителю ":"
  if (item.size()<2) hash.insertMulti(key++,item.at(0));
  else hash.insertMulti(item.at(0).toInt(),item.at(1));
   //Добавили в хэш ключ (наш или заданный пользователем) и значение
  qDebug() << "Element: " << (*it);
 }
 //Вывести в консоль отладки мультихэш
 QMultiHash<int,QString>::iterator i = hash.begin();
 for (;i!=hash.end();++i)
     qDebug() << "Key=" << i.key() << "Value=" << i.value();

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

QList <QString> lst=hash.values(0);

Задача 5. Пример выгрузки контейнера в файл и загрузки из файла.

Для простоты создано консольное приложение, в котором показано создание и чтение бинарного файла с содержимым двух списков. При конфигурации QT по умолчанию, файл создастся в папке build-… проекта. В файле проекта .pro добавлена строка

QT       -= gui

Код файла main.cpp (единственный файл проекта):

#include <QFile>
#include <QDataStream>
#include <QList>
#include <QDebug>

int main() {
 //Пишем 2 списка в файл
 QList <QString> stringList;
 QList <int> intList;
 stringList << "one" << "two" << "three";
 intList << 1 << 2 << 3;
 QFile f("data.dat");
 if (f.open(QIODevice::WriteOnly)) {
  QDataStream stream(&f);
  stream << stringList << intList;
  if (stream.status()!=QDataStream::Ok) {
      qDebug() << "File write error"; return 1;
  }
  else {
      qDebug() << "File writed successfully";
  }
 }
 else {
  qDebug() << "File open error for writing"; return 2;
 }
 //Читаем из файла то, что записали
 f.close();
 stringList.clear(); intList.clear();
 if (f.open(QIODevice::ReadOnly)) {
  QDataStream stream(&f);
  stream >> stringList >> intList;
  if (stream.status()!=QDataStream::Ok) {
      qDebug() << "File read error"; return 3;
  }
  else {
      qDebug() << "File read successfully";
      qDebug() << stringList << "\n" << intList;
  }
 }
 else {
  qDebug() << "File open error for reading"; return 4;
 }
 return 0;
}

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

16.03.2016, 23:30 [9839 просмотров]


теги: учебное c++ список qt