|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Контейнеры в Qt
Время создания: 27.11.2017 13:28
Автор: Алексей Бешенов
Текстовые метки: Qt, контейнеры, QList, QLinkedList, QVector, QMap, QHash, QMutableListIterator, итераторы
Раздел: Компьютер - Программирование - Язык C++ (Си++) - Библиотека Qt - Принципы написания кода
Запись: xintrea/mytetra_syncro/master/base/1511778497uy42jzhc3p/text.html на raw.github.com
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Qt предоставляет свои реализации строк, контейнеров и алгоритмов в качестве упрощенной кроссплатформенной альтернативы для STL Как и в STL, контейнеры Qt используют шаблоны C++ и позволяют хранить элементы нужного типа. Например, QLinkedList<T> – шаблон связного списка; если требуется связный список целых чисел, то используется QLinkedList<int>. Для контейнеров применяется неявное разделение памяти. Передача контейнеров в виде аргументов и их возврат не связаны с затратами, так как копия будет создаваться лишь при необходимости изменения одного из объектов: QList<T> list1; QList<T> list2;
list1 << a << b << c; // элементы a, b, c заносятся в list1
list2 = list1; // содержимое списков совпадает
list2[0] = d; // теперь list1 копируется; // list2 изменен, но не list1 По возможности, лучше передавать const-ссылки, так как в этом случае изменений гарантированно не будет. У всех контейнеров есть некоторые общие методы: int size() const; // число элементов void clear(); // удалить все элементы bool isEmpty() const; // true, если size() == 0 Также везде перегружены операторы сравнения == и !=. Подразумевается, что для типа элементов будет перегружен оператор ==. Контейнеры с последовательным хранением элементов сравниваются с учетом порядка, остальные контейнеры порядок не учитывают. 2. Контейнеры с последовательным хранением элементов Для начала рассмотрим контейнеры QList<T>, QVector<T> и QLinkedList<T>. Для добавления элементов к такому контейнеру либо для объединения контейнеров можно использовать операторы +, +=, <<: QList<int> xs, ys, zs, us; // (Работает аналогично для QVector и QLinkedList.)
xs << 1 << 2 << 3; // xs = (1,2,3)
ys += 1; ys += 2; ys += 3; // ys = (1,2,3)
zs = xs + ys; // zs = (1,2,3,1,2,3)
us << xs << ys << zs; // us = (1,2,3,1,2,3,1,2,3,1,2,3) В этих контейнерах выделяются первый и последний элементы. Ссылки на них можно получить при помощи first() и last(): T& first(); const T& first() const;
T& last(); const T& last() const; (Для совместимости с STL поддерживаются также имена методов front() и back().) Прежде чем вызывать эти методы, убедитесь, что контейнер не пустой. Также можно сверить значение первого или последнего элемента: bool startsWith (const T& val) const; bool endsWith (const T& val) const; Поиск элементов: bool contains (const T& val) const; // содержится ли val в контейнере? int count (const T& val) const; // количество вхождений Добавление и удаление: void prepend (const T& val); // добавить val в начало void push_front (const T& val); // то же самое
void append (const T& val); // добавить val в конец void push_back (const T& val); // то же самое
void pop_front(); // удалить первый элемент void pop_back(); // удалить последний элемент Для вставки и удаления используются итераторы. Пока мы только перечислим соответствующие методы, но если вы не знаете, что такое итераторы и как они работают, то подробные объяснения содержатся в последнем разделе. iterator insert (iterator before, const T& val); // вставить перед позицией before, // вернуть итератор, указывающий на вставленное значение
iterator erase (iterator pos); // удалить элемент в позиции pos, // вернуть итератор, указывающий на следующий элемент
iterator erase (iterator begin, iterator end); // удалить элементы в интервале [begin, end) (исключая end), // вернуть итератор, указывающий на end Далее будут рассмотрены различия между QList<T>, QVector<T> и QLinkedList<T>. 2.1. Контейнеры с доступом по индексу QList<T> и QVector<T> используют доступ по индексу за постоянное время O(1). Как и в массивах C++, элементы нумеруются с 0. Доступ по индексу: const T& at (int i) const; T& operator[] (int i); const T& operator[] (int i) const; T value (int i) const; T value (int i, const T& defaultValue) const; Замена значения по индексу: void replace (int i, const T& val) При обращении к элементам по индексу проверяйте, что индекс лежит в интервале [0, size()). Поиск индекса: int indexOf (const T& val, int from = 0) const; // индекс первого вхождения val, начиная с from; // -1, если элемент не найден
int lastIndexOf (const T& val, int from = -1) const; // индекс последнего вхождения val, начиная с from // (поиск в обратном порядке, при from = -1 – с конца); // -1, если элемент не найден Вставка в данной позиции: void insert (int i, const T& val); Если нужно копировать n элементов из середины, начиная с позиции pos, то используется mid (pos,n). При n = -1 элементы копируются до конца: QList<T> mid (int pos, int length = -1) const; QVector<T> mid (int pos, int length = -1) const; QList<T> – наиболее часто используемый контейнер. Вставка элементов в середину списка осуществляется за O(n). Для вставки за постоянное время в Qt имеется связный список QLinkedList. Амортизированное время вставки элементов в начало и в конец – O(1). Особые методы QList<T>:
Пример работы со списком:
QVector<T> – это обычный динамический массив. Его имеет смысл использовать, если элементы должны храниться в одном участке памяти. При использовании вектора можно получить указатель на данные и обращаться с ними как с обычным массивом:
Конечно, указатели действуют только до тех пор, пока содержимое не будет перемещено в памяти. При создании вектора можно указать размер и инициализирующее значение:
Если потом потребуется снова инициализировать вектор, то используется fill():
Помимо числа элементов size(), у вектора имеется емкость – общий зарезервированный объем.
Число элементов меняется при помощи resize():
Емкость меняется при помощи reserve():
Емкость можно устанавливать, если заранее известно максимальное число элементов. Если емкости не хватит для увеличения размера на некотором этапе, то это лишь затронет быстродействие. Неиспользуемая память освобождается при помощи squeeze():
Как и reserve(), этот метод может потребоваться в редких случаях при оптимизации кода. Удаление и вставка в векторе:
Пример работы с вектором:
QLinkedList<T> – связный список. Он отличается от QList<T> тем, что при работе для доступа к элементам нужно использовать итераторы. При этом вставка элементов в середину происходит за постоянное время O(1) и не приводит к порче итератора, указывающего на некоторый другой элемент. Доступ по индексу осуществляется за O(n). Специфические методы QList<T>:
Пример работы со связным списком:
Стек (LIFO) QStack<T> реализован через наследование от QVector<T> с добавлением следующих методов:
Прежде чем брать элемент, убедитесь, что стек не пустой (!stack.isEmpty()). Пример работы со стеком:
Очередь (FIFO) QQueue<T> реализована через наследование от QList<T> с добавлением следующих методов:
Прежде чем брать элемент, убедитесь, что очередь не пустая (!queue.isEmpty()). Пример работы с очередью:
4. Контейнеры с доступом по ключу QHash<K,T> – хэш-таблица, отображающая ключи типа K в значения типа T. Амортизированное время поиска и вставки – O(1). Если требуется структура, в которой элементы хранятся отсортированными по ключу, используйте QMap<K,T>. Добавление элементов: QHash<K,T>::iterator QHash::insert (const K& key, const T& val); QHash<K,T>::iterator QHash::insertMulti (const K& key, const T& val); insert (key, val) привязывает значение val за ключом key. Если такой ключ уже есть, то значение замещается. Если нужно хранить несколько значений для одного ключа, используйте insertMulti (key, val). Кроме того, у QHash<K,T> имеется специальный дочерний класс QMultiHash<K,T>. Если нужно целиком вставить содержимое другой хэш-таблицы, используйте unite(): QHash<K,T>& QHash::unite (const QHash<K,T>& other); Если текущая хэш-таблица уже содержит определенный ключ, то в результирующей таблице он будет дублироваться. Доступ к значениям по ключу: const T QHash::value (const K& key) const; T& QHash::operator[] (const K& key); const T QHash::operator[] (const K& key) const;
T QHash::take (const K& key); // получить значение и удалить
QList<T> QHash::values() const; // все значения QList<T> QHash::values (const K& key) const; Можно также извлечь ключи по значениям, но хэш-таблица не оптимизирована для работы в этом направлении, поэтому время поиска будет линейным. const K QHash::key (const T& val) const; const K QHash::key (const T& val, const K& defaultKey) const;
QList<K> QHash::keys() const; // все ключи QList<K> QHash::keys (const T& val) const; QList<K> QHash::uniqueKeys() const; // без повторений Если ключ не найден, то возвращается значение по умолчанию K(). Также можно использовать метод const T QHash::value (const K& key, const T& defaultValue) const; – он возвращает defaultValue, если ключа нет. Поиск элементов: bool QHash::contains (const K& key) const; // есть ли ключ key? int QHash::count (const K& key) const; // число вхождений
QHash<K,T>::iterator QHash::find (const K& key); QHash<K,T>::const_iterator QHash::find (const K& key) const; QHash<K,T>::const_iterator QHash::constFind (const K& key) const; Если ключу соответствует несколько значений, то возвращается итератор, указывающий на последний добавленный элемент; если этот итератор инкрементировать, то можно получить другие значения. Если элемент не найден, то возвращается итератор end(). Удаление по итератору и по ключу: QHash<K,T>::iterator QHash::erase (QHash<K,T>::iterator pos); // возвращаемый итератор указывает на следующий элемент
int QHash::remove (const K& key); // возвращает число удаленных элементов Пример работы с хэш-таблицей: QHash<QString,QString> hash;
hash.insert("02-16", "Cremation Wednesday"); hash.insert("02-23", "The Feast of St Monty Python"); hash.insert("02-29", "Quaternary Prolapse begins"); hash.insert("04-01", "The Feast of Saint Eris"); hash.insertMulti("04-01", "Bob's Birthday");
hash.remove("02-29"); // удалит запись // 02-29 => Quaternary Prolapse begins
hash.value("04-01", "slack"); // "Bob's Birthday" hash.value("01-01", "slack"); // "slack" hash.key("The Feast of St Monty Python"); // "02-23" QMultiHash<K,T> наследует QHash<K,T> и ориентирован на структуры, в которых одному ключу может соответствовать несколько значений. Метод QHash<K,T>::iterator QMultiHash::insert (const K& key, const T& val); всегда добавляет новый элемент, даже если ключ повторяется. Чтобы заменить имеющееся значение при повторении ключей, нужно вызывать QHash<K,T>::iterator replace (const K& key, const T& val); Также добавляются методы для поиска и удаления элементов, принимающие, помимо ключа, соответствующее значение: bool contains (const K& key, const T& val) const; int count (const K& key, const T& val) const;
QHash<K,T>::iterator QMultiHash::find (const K& key, const T& val); QHash<K,T>::const_iterator QMultiHash::find (const K& key, const T& val) const; QHash<K,T>::const_iterator QMultiHash::constFind (const K& key, const T& val) const;
int QMultiHash::remove (const K& key, const T& val); Для слияния хэш-таблиц перегружены операторы + и +=: QMultiHash QMultiHash::operator+ (const QMultiHash& other) const; QMultiHash& QMultiHash::operator+= (const QMultiHash& other); QMap<K,T> – ассоциативный массив, отображающий ключи типа K в значения типа T. Элементы сортируются по ключу (для чего требуется перегрузка operator<()), и проход по QMap всегда дает содержимое в отсортированном порядке. Поиск и вставка осуществляются за логарифмическое время O(log n). Если элементы не нужно сортировать по ключам, то используйте QHash<K,T>. Интерфейс QMap<K,T> практически совпадает с QHash<K,T>. Имеются дополнительные функции для поиска элементов по ключам: QHash<K,T>::iterator QHash::lowerBound (const K& key); QHash<K,T>::const_iterator QHash::lowerBound (const K& key) const; QHash<K,T>::iterator QHash::upperBound (const K& key); QHash<K,T>::const_iterator QHash::QHaupperBound (const K& key) const; lowerBound(key) возвращает итератор, указывающий на первый элемент с ключом key. Если такого ключа нет, то возвращается итератор, указывающий на ближайший элемент с большим ключом. upperBound(key) возвращает итератор, указывающий на последний элемент с ключом key. Если такого ключа нет, то возвращается итератор, указывающий на ближайший элемент с большим ключом. Таким образом, все элементы с данным ключом лежат в интервале [lowerBound, upperBound]. Пример: QMultiMap<QString,QString> map;
map.insert("02-16", "Cremation Wednesday"); map.insert("02-23", "The Feast of St Monty Python"); map.insert("02-29", "Quaternary Prolapse begins"); map.insert("04-01", "The Feast of Saint Eris"); map.insert("04-01", "Bob's Birthday");
map.lowerBound("02-16"); // указывает на ("02-16", "Cremation Wednesday") map.lowerBound("02-17"); // указывает на ("02-23", "The Feast of St Monty Python") map.lowerBound("05-23"); // указывает на end()
QMap<QString,QString>::const_iterator lb = map.lowerBound("04-01"); QMap<QString,QString>::const_iterator ub = map.upperBound("04-01");
while (lb != ub) { qDebug() << lb.value(); lb++; } // Выводит // "Bob's Birthday" // "The Feast of Saint Eris" QMultiMap<K,T> наследует QMap<K,T> и ориентирован на структуры, в которых одному ключу может соответствовать несколько значений. Интерфейс QMultiMap<K,T> практически полностью соответствует QMultiHash<K,T>. QSet<T> – неупорядоченное множество, основанное на хэш-таблице. Множество позволяет быстро получать и добавлять значения:
Особый интерес представляют операции объединения, пересечения и разности:
Для тех же целей перегружены операторы:
Пример работы с множествами:
Итераторы – объекты для унифицированного доступа к элементам контейнера. Вы должны быть знакомы с итераторами, если имеете хороший опыт программирования на C++ с использованием STL, либо на Java. В Qt есть как итераторы в стиле STL, так и итераторы в стиле Java. Первые немного эффективнее, но со вторыми удобнее работать. Итераторы в стиле STL эффективно реализованы (по сути, это синтаксический «сахар» для указателей), и через них работают алгоритмы <QtAlgorithms>. В каждом контейнере есть два типа итераторов: const_iterator с доступом только для чтения и iterator с доступом для чтения и записи (таблица 1). Таблица 1. Итераторы в стиле STL
Операции с итераторами записываются так же, как и для указателей. Для QVector<T> итераторы могут непосредственно сводиться к указателям:
Операции над итераторами в стиле STL перечислены в таблице 2. Переход на произвольное число элементов вперед и назад, сравнение итераторов и подсчет числа элементов между ними поддерживаются только итераторами с произвольным доступом – QList и QVector. У других итераторов доступен только переход на одну позицию вперед или назад. Ссылка может быть как константной, так и с возможностью изменения значения, в зависимости от типа итератора (const_iterator или iterator). Таблица 2. Операции над итераторами в стиле STL
В дополнение к указанным префиксным записям ++i и --i, доступны также постфиксные i++ и i--, но обычно возвращаемые значения игнорируются. Поэтому префиксный вариант эффективнее, так как в постфиксном варианте итератор копируется перед изменением, и возвращается ссылка на копию. Метод контейнера begin() возвращает итератор, указывающий на первый элемент контейнера; end() возвращает итератор, указывающий на позицию после последнего элемента. end() разыменовывать нельзя. constBegin() и constEnd() делают то же самое, но возвращают const-итераторы.
Таким образом, проход по элементам выглядит следующим образом:
Здесь *i разыменовывает итератор. Для контейнера над объектами некоторого класса Foo с методом Foo::bar() можно было бы положиться на сходство итераторов с указателями и писать код в таком духе:
Но это будет работать не всегда. Нужно явно указывать разыменование. Рисунок 1. Итератор в стиле STL Для iterator разыменованному итератору можно присваивать новые значения. Если элементы контейнера не изменяются, то используется const_iterator. Для QMap и QHash разыменование итератора дает значение. Чтобы получить ключ, используйте метод итератора key(). Значение можно получить при помощи value().
Если вы изменяете не только элементы контейнера, но и сам контейнер (добавляете или удаляете из него элементы), то нужно быть внимательным, чтобы не допустить ошибок. Например, требуется удалить из списка чисел элементы, превышающие 10. Используем метод erase:
Он удаляет элемент, на который указывает итератор i, и возвращает итератор, указывающий на следующий элемент, либо end(), если удаленный элемент – последний. Можно попробовать сделать так:
Это неправильный код! Сначала будет удалено значение 12, а erase(i) вернет итератор, указывающий на значение 20, но затем итератор будет инкрементирован, и мы пропустим 20. В самом конце списка мы вообще перейдем через end(). Правильное решение:
Итерация в прямом и обратном направлении – не симметричные операции. Сравните следующий код:
В STL имеются еще два типа итераторов, reverse_iterator и const_reverse_iterator. В Qt их нет. Синтаксис STL-итераторов может быть неудобным или служить источником ошибок.
Так как в Qt используется неявное разделение данных, то в API можно встретить методы, возвращающие контейнеры по значению – это не приводит к большим затратам. Но это служит источником ошибок при работе с итераторами в стиле STL. Если у нас есть метод
то следующий код неправильный:
– здесь begin() и end() вызывается для разных объектов! Также неявное разделение приводит к тому, что контейнер нельзя копировать, если на нем действуют итераторы с доступом для записи. Например:
Неявное разделение должно означать, что копирование не приводит к дублированию данных до тех пор, пока этого не требуется. По логике вещей, при изменении содержимого list1 должна создаваться глубокая копия list2, чтобы второй контейнер не затрагивался. Но если это производится через STL-итератор, то просто меняется содержимое обоих контейнеров. Эту проблему, как и проблему асимметричности прохода в прямом и обратном направлениях, решают итераторы в стиле Java. Итераторы в стиле Java немного уступают в эффективности итераторам в стиле STL, однако более удобны для программиста. Аналогично, для каждого класса (таблица 3) есть итератор с доступом только для чтения (например, QListIterator<T>) и итератор с доступом для чтения и записи (соответственно, QMutableListIterator<T>). Таблица 3. Итераторы в стиле Java
QListIterator<T> имеет более короткое имя, чем QMutableListIterator<T>, потому что чаще используются итераторы с доступом только для чтения. Сравните с QList<int>::const_iterator и QList<int>::iterator – в STL короче записывается имя итератора с доступом для записи. В отличие от итераторов в стиле STL, итераторы в стиле Java указывают не на сами элементы, а на позицию до первого элемента, между двумя элементами, либо за последним элементом. Метод previous() возвращает ссылку на предыдущий элемент, а next() – на следующий:
Рисунок 2. Итератор в стиле Java Определить, есть ли элемент до или после итератора, позволяют методы hasPrevious() и hasNext().
Таким образом, типичный проход по списку выглядит так:
Здесь конструктору итератора передается список. В самом начале он указывает на точку перед его первым элементом. Вызов next() в цикле переводит итератор на следующую позицию – после первого элемента и перед вторым, и т.д. Если проход нужно осуществить в обратном порядке, то при помощи метода toBack() итератор нужно перевести в позицию за последним элементом, а затем использовать previous():
Операции над итераторами в стиле Java перечислены в таблице 4. Таблица 4. Операции над итераторами в стиле Java
У итератора с доступом для записи есть дополнительные методы:
insert (x) вставляет x в текущую позицию и переводит итератор в позицию после нового элемента. remove() удаляет последний элемент, через который перешел итератор, т.е. предыдущий, если вызывался next(), и следующий, если вызывался previous(). setValue (x) устанавливает значение x для последнего элемента, через который перешел итератор. Вернемся к примеру с удалением элементов из списка:
Код выглядит более просто и компактно, чем в случае с QList<int>::iterator, так как удаление элемента не портит итератор. То же самое можно сделать через обход от конца к началу:
Все итераторы имеют одинаковый интерфейс, но соответствующие методы QMapIterator и QHashIterator возвращают объект Item, для которого key() дает ключ, а value() – значение.
key() возвращает ссылку на ключ последнего элемента, через который прошел итератор, а value() – ссылку на его значение.
(Аналогично для итератора с доступом для записи, но ссылка на значение будет T&, а не const T&)
Для поиска значений используются findNext() и findPrevious().
findNext(x) ищет значение, начиная с текущей позиции итератора и до конца контейнера. Если значение найдено, то итератор устанавливается после соответствующего элемента и возвращается true. Если значение не найдено, то итератор устанавливается за последний элемент контейнера и возвращается false. findPrevious(x) ищет значение, начиная с текущей позиции итератора и до начала контейнера. Если значение найдено, то итератор устанавливается до соответствующего элемента и возвращается true. Если значение не найдено, то итератор устанавливается до первого элемента контейнера и возвращается false. В QMap и QHash поиск производится по значению (поиск по ключу реализован самими контейнерами). Вы могли уже убедиться, что с итераторами в стиле Java работать удобнее. Единственный их недостаток – они дают больший исполняемый код. Поэтому при необходимости оптимизации по скорости работы и размеру исполняемых файлов можно остановиться на STL-итераторах. Для прохода по всем элементам контейнера в Qt имеется ключевое слово foreach.
В foreach на каждом шаге числу x будет присваиваться значение очередного элемента списка. При этом возможные изменения x не будут затрагивать содержимое списка. (Для изменения содержимого используйте итераторы.) Но имейте в виду, что внутри foreach реализован через препроцессор C++, поэтому следующий код не сработает:
Запятая всегда разделяет аргументы макроса, поэтому не может разделять аргументы шаблона, служащего аргументом макроса. Правильный вариант:
Также в Qt имеется ключевое слово forever, которое соответствует бесконечному циклу for(;;). Если в настройках указать CONFIG += no_keywords, то вместо ключевых слов foreach и forever можно использовать макросы Q_FOREACH и Q_FOREVER. В Qt имеются следующие контейнеры с последовательным хранением элементов:
Среди них наиболее часто используется QList<T>. QVector<T> необходим для хранения данных в непрерывном массиве, а QLinkedList<T> оптимизирован для частой вставки элементов в середину. Кроме того:
Для хранения пар «ключ-значение» имеются:
Отличие состоит в том, что элементы QMap содержатся в отсортированном виде. QMultiHash и QMultiMap – дочерние классы, интерфейс которых ориентирован на структуры с несколькими значениями для одного ключа. Для унифицированного доступа используются итераторы. Итераторы в стиле Java более удобны, но итераторы в стиле STL работают более эффективно. В следующей статье мы рассмотрим алгоритмы <QtAlgorithms>, а также работу с флагами и массивами битов. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так же в этом разделе:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|