Примеры использования QSet и QMap

Классы Qt

Стандартные алгоритмы

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

Пример. Сортировка элементов типа vector.

vector<int> nums;

…

Выполняем сортировку первых пяти элементов (при условии, что они существуют) в естественном для int порядке, т.е. по возрастанию.

sort (nums.begin(), nums.begin()+5);

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

bool cmpfunc (int i,int j) { return (j<i); }

sort (nums.begin()+5, nums.end(), cmpfunc);

Классы контейнеры Qt по составу и программному интерфейсу в значительной степени повторяют классы STL, позволяют выполнять преобразования контейнеров Qt в STL и обратно для обеспечения совместимости с уже написанными приложениями и библиотеками. Основное отличие Qt от STL заключается в том, что Qt не является жестко стандартизованной библиотекой, следовательно может активно изменяться от версии к версии как в части интерфейса так и реализации. Основной аргумент в использовании контейнеров Qt заключается в том, что производитель позиционирует их как более эффективные, чем STL. Для работы с контейнерами предусмотрено два стиля – стиль Java и стиль STL. Все основные принципы использования STL также применимы к Qt. Классы контейнеры относятся к группе классов Generic Containers.

1. QList<T> - Класс хранит список значений данного типа (T), доступ к которым возможен по индексу. Внутренне QList реализован как массив, что обеспечивает быстрый доступ к элементу по индексу. Элементы могут добавляться либо в конец списка, используя QList::append() и QList::prepend(), или могут быть вставлены в середину с использованием QList::insert(). В отличии от других классов контейнеров, QList оптимизирован по производительности и реализован наиболее компактно. Класс QStringList наследует QList<QString>.

2. QLinkedList<T> - Класс подобен QList, за исключением того, что для обращения к элементу используются итераторы, а не индекс. Обеспечивает лучшую производительность, чем QList при вставке в середину большого списка и более строгую работу с итераторами. (Итератор-указатель на элемент списка QLinkedList остается актуальным до тех пор, пока элемент существует, в то время как итератор в списке QList может стать ошибочным в случае добавления или удаления элементов.)

3. QVector<T> - Класс сохраняет массив значений заданного типа, выравнивая размещение в памяти. Вставка в начало или в середину вектора может быть достаточно медленной, т.к. это приводит к перемещению большого числа элементов в памяти.

4. QStack<T> - Класс стека реализован на основе вектора QVector и обеспечивает принцип "last in, first out" (LIFO).

5. QQueue<T> - Класс очереди реализован на основе списка QList и обеспечивает принцип "first in, first out" (FIFO) semantics.

6. QSet<T> - Обеспечивает формирование математического множества без повторений элементов и их быстрый поиск. Класс основан на QHash, что принципиально отличает его от класса std::set. Значения QSet, извлекаемые с помощью итератора не являются сортированными. Также следует помнить о расходе памяти при использовании методов, основанных на хэш-таблицах.

7. QMap<Key, T> -Обеспечивает возможность формирования словаря (ассоциативный массив), который отображает значения ключей типа Key на значения типа T. Обычно каждый ключ ассоциирован с одним значением. QMap сохраняет данные в порядке следования ключей Key. Если необходим другой порядок, следует использовать класс QHash.

8. QMultiMap<Key, T> - Потомок QMap, обеспечивающий интерфейс формирования ассоциативного массива, в котором один ключ может быть ассоциирован с несколькими значениями.

9. QHash<Key, T> - Класс почти аналогичен QMap, однако реализует быстрый поиск ключей (по хэш-функции). QHash хранит данные в произвольном порядке.

10. QMultiHash<Key, T> - потомок QHash, обеспечивающий интерфейс для хранения нескольких значений для одного ключа.

Пример использования списка:

QList<QString> list;

list << "A" << "B" << "C" << "D";

QList<QString>::iterator i;

for (i = list.begin(); i!= list.end(); ++i)

*i = (*i).toLower();

Дополнительные алгоритмы обработки данных в контейнерах реализованы в функциях, декларированных в файле заголовков <QtAlgorithms>.

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

#include <QtCore/QCoreApplication>

#include <QSet>

#include <QTextStream>

#include <QTime>

const int MAX_WORDS = 20;

const int MAX_CHARS = 2;

//*****************************************************************************

// Пример использования QSet с типом на основе стандартного

/// класс, нечувствительный к регистру

class InsensitiveString: public QString

{

public:

/// Функция сравнения. Специцикаторы const являются обязательными!

/// Используется только в том случае, если хэш-значения совпали,

/// поэтому сравнивается равенство значений.

bool operator== (const InsensitiveString & other) const

{

return this->toLower() == other.toLower();

};

};

/// Определяем хэш-функцию для типа InsensitiveString

uint qHash(const InsensitiveString & var)

{ // приводим к нижнему регистру и к стандартной qHash(const QString&)

return qHash(var.toLower());

};

void test_qset()

{

// используем стандартный поток вывода для вывода текста в консоль

QTextStream out(stdout);

out<<"********************"<<__FUNCTION__<<"********************"<<endl;

// объявляем множество

QSet <InsensitiveString> st;

InsensitiveString str;

// заносим случайно сгенерированные значения

for(int i=0; i<MAX_WORDS; i++){

str.clear();

for(int j=0; j<MAX_CHARS; j++)

str.append(QChar((qrand()%('z'-'A')) + 'A'));

st.insert(str);

};

// формируем новые строки и проверяем, входят ли

for(int i=0; i<MAX_WORDS; i++){

str.clear();

for(int j=0; j<MAX_CHARS; j++)

str.append(QChar((qrand()%('z'-'A')) + 'A'));

// проверяем, есть ли уже такие значения во множестве

// и выводим результат

if(st.find(str)!= st.end()){

out<<"Val " << str << " exist" << endl;

} else

out<<"Val " << str << " not exist" << endl;

};

// выводим все элементы множества. Обратите внимание, что элементы

// не сортированы!!!

QSetIterator<InsensitiveString> i(st);

while (i.hasNext())

out << i.next() << endl;

};

//*****************************************************************************

// Пример использования QSet с новым типом

#include <qHash>

/// класс, определяющий новый тип

class RawData

{

public:

/// конструктор по умолчанию инициализирует случайным образом значение

RawData(){ m_val = qrand()%10 - 5; };

/// функция получения значения. Спецификатор const здесь необходим!

int val() const { return m_val;};

/// Фунция сравнения. Специцикаторы const являются обязательными!

/// Используется только в том случае, если хэш-значения совпали,

/// поэтому сравнивается равенство значений.

bool operator== (const RawData & other) const

{

return this->m_val == other.m_val;

};

protected:

int m_val;

};

/// Определяем новую хэш-функцию, позволяющую работать с новым типом

uint qHash(const RawData & var)

{

// поскольку значение простое, воспользуемся стандартной хэш-функцией

// для целого типа

return qHash(var.val());

};

void test_qset2()

{

// используем стандартный поток вывода для вывода текста в консоль

QTextStream out(stdout);

out<<"********************"<<__FUNCTION__<<"********************"<<endl;

// определяем множество и заполняем его

QSet <RawData> st;

for(int i=0; i<MAX_WORDS; i++){

RawData data;

st.insert(data);

};

// создаем новые элементы и проверяем, есть ли такие же

for(int i=0; i<MAX_WORDS; i++){

RawData data;

if(st.find(data)!= st.end()){

out<<"Val " << data.val() << " exist" << endl;

} else

out<<"Val " << data.val() << " not exist" << endl;

};

// выводим все элементы множества.

// Значения не сортированы!!!

QSetIterator<RawData> i(st);

while (i.hasNext())

out << i.next().val() << endl;

};

//*****************************************************************************

// Пример использования QMap с типом на основе стандартного

#include <QMap>

/// класс, нечувствительный к регистру

class InsensitiveString2: public QString

{

public:

// переопределяем функцию сравнения. Поскольку будем использовать QMap,

// которая использует дерево, необходимо переопределить operator<

bool operator< (const InsensitiveString2 & other) const

{

return this->toLower() < other.toLower();

};

};

void test_qmap()

{

// используем стандартный поток вывода для вывода текста в консоль

QTextStream out(stdout);

out<<"********************"<<__FUNCTION__<<"********************"<<endl;

// объявляем map, имеющий ключ типа InsensitiveString2 и фиктивное значение

QMap <InsensitiveString2, int> st;

InsensitiveString2 str;

// заносим случайно сгенерированные ключи с одинаковыми значениями

for(int i=0; i<MAX_WORDS; i++){

str.clear();

for(int j=0; j<MAX_CHARS; j++)

str.append(QChar((qrand()%('z'-'A')) + 'A'));

st.insert(str, 0);

};

// формируем новые строки и проверяем, входят ли

for(int i=0; i<MAX_WORDS; i++){

str.clear();

for(int j=0; j<MAX_CHARS; j++)

str.append(QChar((qrand()%('z'-'A')) + 'A'));

// проверяем, есть ли уже такие значения во множестве

// и выводим результат

if(st.find(str)!= st.end()){

out<<"Val " << str << " exist" << endl;

} else

out<<"Val " << str << " not exist" << endl;

};

// выводим все элементы map.

// Здесь все элементы выводятся в порядке сортировки

// (по возрастанию, игнорируя регистр)

QMapIterator <InsensitiveString2, int> iter(st);

while (iter.hasNext()){

iter.next();

out << iter.key() << endl;

};

};

//*****************************************************************************

// Пример использования QMap с новым типом

/// класс, определяющий новый тип

class RawData2

{

public:

/// конструктор по умолчанию инициализирует случайным образом значение

RawData2(){ m_val = qrand()%10 - 5; };

/// функция получения значения. Спецификатор const здесь необходим!

int val() const { return m_val;};

/// Фунция сравнения. Специцикаторы const являются обязательными!

/// Поскольку используем QMap, то operator<

bool operator< (const RawData2 & other) const

{

return this->m_val < other.m_val;

};

protected:

int m_val;

};

void test_qmap2()

{

// используем стандартный поток вывода для вывода текста в консоль

QTextStream out(stdout);

out<<"********************"<<__FUNCTION__<<"********************"<<endl;

// объявляем map, имеющий ключ типа InsensitiveString2, int

// и заполняем парами ключ-фиктивное значение (не используемое)

QMap <RawData2, int> st;

for(int i=0; i<MAX_WORDS; i++){

RawData2 data;

st.insert(data,0);

};

// создаем новые элементы и проверяем, есть ли такие же

for(int i=0; i<MAX_WORDS; i++){

RawData2 data;

// проверяем, есть ли уже такие значения во множестве

// и выводим результат

if(st.find(data)!= st.end()){

out<<"Val " << data.val() << " exist" << endl;

} else

out<<"Val " << data.val() << " not exist" << endl;

};

// выводим все элементы map.

// Здесь все элементы выводятся в порядке сортировки

QMapIterator <RawData2, int> iter(st);

while (iter.hasNext()){

iter.next();

out << iter.key().val() << endl;

};

};

//*****************************************************************************

int main(int argc, char *argv[])

{

// инициализируем генератор псевдослучайных чисел текущим временем

QTime time;

qsrand(time.secsTo(QTime::currentTime()));

test_qset();

test_qset2();

test_qmap();

test_qmap2();

// ждем, пока пользователь нажмет Enter

QTextStream(stdin).readLine();

return 0;

}

Файл проекта для создания консольного Qt-приложения выглядит следующим образом:

TEMPLATE = app

TARGET =

DEPENDPATH +=.

INCLUDEPATH +=.

CONFIG += console

SOURCES += qt_containters.cpp

При использовании Qt остается возможность выбора классов контейнеров из библиотеки STL или из комплекта Qt. Если создается библиотека, где использование классов контейнеров необходимо в интерфейсных функциях, лучше выбрать контейнеры STL, реализация которых обязательна для всех версий C++. В остальных случаях выбор за разработчиком.

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

Дополнительно см.

· Плаугер П., Степанов А., Ли М., Массер Д. STL - стандартная библиотека шаблонов C++. BHV-Санкт-Петербург, 2004

· Дэвид Р. Мюссер, Жилмер Дж. Дердж, Атул Сейни. C++ и STL. Справочное руководство (2-е издание). Вильямс, 2010.

· Макс Шлее - Qt 4.5. Профессиональное программирование на C++. Издательство: БХВ-Петербург, 2010 г.–т, 896 стр.,– ISBN 978-5-9775-0398-3

Дата добавления: 2014-11-25