Топ контрибуторов
loading
loading
Знаете ли Вы, что

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

Лента обновлений
ссылка Oct 22 23:24
Комментарий от alexcei88:
В вопросе переменная s даже не выводиться, а выводитьс...
ссылка Oct 22 17:46
Комментарий от AlexFurm:
Это UB, так можно вызывать только статические функции ч...
ссылка Oct 22 17:43
Комментарий от AlexFurm:
Любые битовые операции с signed это UB
ссылка Oct 21 20:30
Комментарий от yoori:
Любой вариант скомпилируется если компилировать не в конеч...
ссылка Oct 21 16:53
Добавлен вопрос в тест QA (Quality Assurance)
Статистика

Тестов: 153, вопросов: 8596. Пройдено: 443368 / 2177510.

Qt. Контейнеры. Foreach. Алгоритмическая сложность. Часть 3

head tail Статья
категория
C++
дата28.09.2012
авторSemenovMS
голосов2

     Конструкция foreach

Если вы хотите перебрать все элементы контейнера по порядку, то можете использовать конструкцию Qt foreach. Данная конструкция - это дополнение Qt к языку C++, реализованное с помощью средств препроцессора.

Ее синтаксис:: foreach (переменная, контейнер) оператор. В следующем примере показано использование конструкции foreach для перебора всех элементов контейнера QLinkedList<QString>:

 QLinkedList<QString> list;

 ...

 QString str;

 foreach (str, list)

     qDebug() << str;

Код с конструкцией foreach значительно короче, чем аналогичный код, который использует итераторы:

 QLinkedList<QString> list;

 ...

 QLinkedListIterator<QString> i(list);

 while (i.hasNext())

     qDebug() << i.next();

За исключением типа данных, содержащего запятую (например, QPair<int, int>), переменная, используемая для перебора элементов контейнера может быть определена внутри выражения foreach:

 QLinkedList<QString> list;

 ...

 foreach (QString str, list)

     qDebug() << str;

И подобно любому циклу C++, вы можете заключить тело цикла foreach в фигурные скобки и использовать break для прерывания цикла:

 QLinkedList<QString> list;

 ...

 foreach (QString str, list) {

     if (str.isEmpty())

         break;

     qDebug() << str;

 }

При использовании с QMap и QHash, foreach предоставляет доступ к парам значений (key, value). Если вы хотите перебрать и ключи и значения, то можете использовать итераторы (которые быстрее) или написать код, подобный следующему:

 QMap<QString, int> map;

 ...

 foreach (QString str, map.keys())

     qDebug() << str << ":" << map.value(str);

Длямногосвязныхкарт:

 QMultiMap<QString, int> map;

 ...

 foreach (QString str, map.uniqueKeys()) {

     foreach (int i, map.values(str))

         qDebug() << str << ":" << i;

 }

При входе в цикл foreach, Qt автоматически делает копию контейнера. Если вы измените контейнер во время выполнения цикла, то в цикле этого не будет заметно. (Если вы не изменяли контейнер, копирование все еще имеет место, но, благодаря неявному совместному использованию данных, копирование контейнера осуществляется очень быстро.)

В дополнение к foreach, Qt также предоставляет псевдоключевое слово forever, для бесконечного цикла:

 forever {

     ...

 }

Если вас беспокоит засорение пространства имен, то вы можете отключить использование этих макросов, добавив в .pro-файл следующую строку:

 CONFIG += no_keywords

     Другие контейнероподобные классы

Qt включает три класса-шаблона, которые в некотором отношении напоминают контейнеры. Эти классы не предоставляют итераторов и не могут использоваться в конструкции foreach.

QVarLengthArray<T, Prealloc> предоставляет низкоуровневый массив переменной длины. Он может использоваться вместо QVector в тех местах, где скорость особенно важна.

QCache<Key, T> предоставляет кэш для хранения объектов некоторого типа T, ассоциированных с ключами типа Key.

QPair<T1, T2> хранит пары элементов.

Дополнительные нешаблонные типы, которые дополняют шаблонные контейнеры Qt, это - QBitArray, QByteArray, QString и QStringList.

     Алгоритмическая сложность

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

Чтобы описать алгоритмическую сложность мы используем следующую терминологию, основанную на нотации "большого O":

Постоянное время: O(1). Функция, как говорят, выполняется за постоянное время, если она требует одного и того же времени независимо от того, сколько элементов присутствует в контейнере. Одним из примеров является QLinkedList::insert().

Логарифмическое время: O(log n). Функция, которая выполняется за логарифмическое время - это функция, время выполнения которой пропорционально логарифму от количества элементов в контейнере. Одним из примеров является qBinaryFind().

Линейное время: O(n). Функция, выполняющаяся линейно, будет выполнятся по времени прямо пропорционально количеству элементов, хранящихся в контейнере. Одним из примеров является QVector::insert().

Линейно-логарифмическое время: O(n log n). Функция, выполняющаяся за линейно-логарифмическое время является ассимптотически медленее, чем линейная функция, но быстрее, чем квадратичная функция.

Квадратичное время: O(n²). Квадратично-временная функция выполняется по времени пропорционально квадрату количества элементов, хранящихся в контейнере.

В следующей таблице приведён итог алгоритмической сложности последовательных контейнерных классов Qt:


Индексный перебор

Вставка

Предшествующая вставка.

Последующая вставка

QLinkedList<T>

O(n)

O(1)

O(1)

O(1)

QList<T>

O(1)

O(n)

Сред. O(1)

Сред. O(1)

QVector<T>

O(1)

O(n)

O(n)

Сред. O(1)

В этой таблице, "Сред." обозначает "усредненное поведение" (amortized behavior). Например, "Сред. O(1)" обозначает, что, если вы вызовите функцию единожды, то можете получить поведение O(n), но если вы вызовете её множество раз (например, n раз), усредненная величина будет равна O(1).

В следующей таблице приведён итог алгоритмической сложности ассоциативных контейнеров и наборов Qt:


Перебор ключей

Вставка

Среднее

Худший случай

Среднее

Худший случай

QMap<Key, T>

O(log n)

O(log n)

O(log n)

O(log n)

QHash<Key, T>

Сред. O(1)

O(n)

Сред. O(1)

O(n)

QSet<Key>

Сред. O(1)

O(n)

Сред. O(1)

O(n)

В QVector, QHash и QSet, время выполнения усредняется до O(log n). Оно может быть сведено к O(1) с помощью вызова QVector::reserve(), QHash::reserve() или QSet::reserve(), с ожидаемым количеством элементов, до вставки элементов. В следующем разделе этот вопрос обсуждается более глубоко.

Стратегии увеличения размера

QVector<T>, QString и QByteArray хранят свои элементы в памяти непрерывно; QList<T> содержит массив указателей на элементы в хранилище, чтобы обеспечить быстрый доступ по индексу (если T не тип-указатель или базовый тип имеет размер указателя, в этом случае само значение хранится в массиве); QHash<Key, T> хранит хэш-таблицу, размер которой пропорционален количеству элементов в хэше. Во избежание перераспределения данных каждый раз при добавлении элемента в конец контейнера, эти классы обычно резервируют больше памяти, чем требуется.

Рассмотрим следующий код, который собирает QString из другого QString:

 QString onlyLetters(const QString &in)

 {

     QString out;

     for (int j = 0; j < in.size(); ++j) {

         if (in[j].isLetter())

             out += in[j];

     }

     return out;

 }

Мы собираем строку out динамически, добавляя в конец по одному символу за раз. Давайте предположим, что мы добавляем 15000 символов в строку QString. Тогда следующие 18 перераспределений данных (из возможных 15000) произойдут, когда QString исчерпает место под 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, 12276, 14324, 16372 символа. В конце концов QString будет иметь 16372 символов Unicode, из которых 15000 будут заняты.

Значения выше могут показаться немного странными, но здесь есть принцип размещения:

QString размещает по 4 символа за раз, пока не достигнет размера 20.

От 20 до 4084, он каждый раз удваивает свой размер. Точнее, он увеличивается до следующего числа, кратного степени двойки, минус 12. (Некоторые менеджеры памяти работают хуже, когда требуется точное увеличение в два раза, потому что они используют несколько байт на каждый блок для подсчета.)

От 4084 и выше, он увеличивается блоками по 2048 символов (4096 байт). Это имеет смысл, потому что современные операционные системы не копируют данные целиком, когда переразмещают буфер; физические страницы памяти просто переупорядочиваются, и только данные первой и последней страниц действительно нуждаются в копировании.

QByteArray и QList<T> используют более или менее похожие алгоритмы, как и QString.

QVector<T> также использует этот алгоритм для типов данных, которые могут быть перемещены в памяти используя memcpy() (включая базовые типы C++, типы указателей и общие классы Qt), но для типов данных, которые могут быть перемещены только с помощью вызовов конструкторов копирования и деструкторов, использует другой алгоритм. Так как цена переразмещения в этом случае становится выше, QVector<T> уменьшает количество переразмещений, всегда удваивая память, когда исчерпает место.

QHash<Key, T> - это совершенно другой случай. Внутренняя хэш-таблица QHash каждый раз увеличивается кратно степени двойки, элементы, переразмещеные в новой области памяти, вычисляются, как qHash(key) % QHash::capacity() (количество областей памяти). Это замечание также справедливо для QSet<T> и для QCache<Key, T>.

Для большинства приложений, алгоритм увеличения размера по умолчанию, предоставляемый Qt, выполняется этот трюк. Если вам требуется большая управляемость, то QVector<T>, QHash<Key, T>, QSet<T>, QString и QByteArray предоставляют три функции, которые позволяют контролировать и задавать столько памяти, сколько вам нужно для размещения элементов:

capacity() возвращает количество элементов, для которых выделена память (для QHash и QSet - это количество участков памяти в хэш-таблице).

reserve(size) явно предварительно выделяет память для size элементов.

squeeze() освобождает любую память не требующуюся для хранения элементов.

Если вы приблизительно знаете сколько элементов вы разместите в контейнере, то вы можете начать с вызова reserve(), а затем, заполнив контейнер, вы можете вызвать squeeze() чтобы освободить дополнительно выделенную память.

Если Вам понравилась статья, проголосуйте за нее

Голосов: 2  loading...
partigiano   ingwarsmith