|
Home · All Classes · Main Classes · Grouped Classes · Modules · Functions | |
<QtAlgorithms> - это заголовочный файл, предоставляющий родовые основанные на шаблонах алгоритмы. Далее...
<QtAlgorithms> - это заголовочный файл, предоставляющий родовые основанные на шаблонах алгоритмы.
С помощью <QtAlgorithms>, Qt предоставляет множество глобальных функций-шаблонов, которые работают с контейнерами и реализуют широко известные алгоритмы. Вы можете использовать эти алгоритмы с любым классом-контейнером, предоставляющим итераторы в стиле STL, включая классы QList, QLinkedList, QVector, QMap и QHash, входящие в Qt.
Эти функции были сделаны наподобие функций, доступных в заголовочном файле STL <algorithm>. Большинство из них имеют эквивалент в STL; например, qCopyBackward() является тем-же самым, что и алгоритм copy_backward() в STL.
Если STL доступно на всех нужных Вам платформах, Вы можете использовать алгоритмы STL вместо их аналогов в Qt. Единственной причиной, по которой Вы можете предпочесть использование алгоритмов STL - это то, что STL предоставляет множество и множество алгоритмов, в то время как Qt предоставляет только важнейшие из них, не делая попыток дублирования функциональности, заложенной в стандарт C++.
Большинство алгоритмов принимают в качестве параметров итераторы итераторы в стиле STL. Алгоритмы считаются родовыми в том смысле, что они не привязаны ни к какому конкретному классу-итератору; Вы можете использовать их с любыми итераторами, отвечающими некоторым требованиям.
Возьмем для примера алгоритм qFill(). В отличие от QVector, QList не имеет функции fill(), которая может использоваться для заполнения списка определенным значением. Если Вам нужны ее функциональные возможности, то можете использовать qFill():
QStringList list;
list << "one" << "two" << "three";
qFill(list.begin(), list.end(), "eleven");
// list: [ "eleven", "eleven", "eleven" ]
qFill() принимает итератор начала, итератор конца и значение. В нашем примере мы передаем list.begin() и list.end(), в качестве итераторов начала и конца, но вот так делать не следует:
qFill(list.begin() + 1, list.end(), "six");
// list: [ "eleven", "six", "six" ]
Разные алгоритмы предъявляют разные требования к итераторам, которые они принимают. Например, qFill() принимает два итератора ввода, что является минимальным требованием к типу итераторов. Требования определены для каждого алгоритма. Если передается итератор неверного типа (например, QList::ConstIterator передается в качестве итератора вывода), Вы обязательно получите ошибку компилятора, хотя и необязательно очень информативную.
Некоторые из алгоритмов имеют специальные требования к типам значений, хранящихся в контейнерах. Например, qEqual() требует, чтобы для типа значения был определен operator==(), который используется для сравнения элементов. Точно также, qDeleteAll() требует, чтобы значение имело тип неконстантного указателя (например, QWidget *). Требования к типу значения определены для каждого алгоритма, и компилятор выдаст ошибку, если эти требования не выполняются.
Родовые алгоритмы могут использоваться и в классах, отличных от тех, что предоставляются Qt и STL. Синтаксис итераторов в стиле STL сделан наподобие указателей C++, поэтому возможно использование простых массивов в качестве контейнеров и простых указателей в качестве итераторов. Распространенным является использование qBinaryFind() в совокупности с двумя статическими массивами: один из них содержит список ключей, а другой содержит список ассоциированных значений. Например, в следующем отрывке кода содержимое строки HTML (например, &) будет искаться в массиве name_table и, если вхождение будет найдено, возвращено соответствующее значение Unicode из массива value_table:
QChar resolveEntity(const QString &entity)
{
static const QLatin1String name_table[] = {
"AElig", "Aacute", ..., "zwnj"
};
static const ushort value_table[] = {
0x0061, 0x00c1, ..., 0x200c
};
int N = sizeof(name_table) / sizeof(name_table[0]);
const QLatin1String *name = qBinaryFind(name_table, name_table + N,
entity);
int index = name - name_table;
if (index == N)
return QChar();
return QChar(value_table[index]);
}
Такой код подходит только для продвинутых пользователей; в большинстве случаев, код на основе QMap или QHash будет работать точно также:
QChar resolveEntity(const QString &entity)
{
static QMap<QString, int> entityMap;
if (!entityMap) {
entityMap.insert("AElig", 0x0061);
entityMap.insert("Aacute", 0x00c1);
...
entityMap.insert("zwnj", 0x200c);
}
return QChar(entityMap.value(entity));
}
Алгоритмы предъявляют некоторые требования к типам итераторов, которые они принимают, и эти требования определены индивидуально для каждой функции. При несоответствии типа итератора, компилятор выдаст ошибку.
Итератор ввода - это итератор, который может использоваться для последовательного чтения данных из контейнера. Он должен поддерживать операторы: == и != для сравнения двух итераторов, унарный * для получения значения, хранящегося в элементе, и префикс ++ для перемещения к следующему элементу.
Все итераторы контейнеров всех типов Qt (const и не-const) являются итераторами ввода.
Итератор вывода - это итератор, который может использоваться для последовательной записи данных в контейнер или в поток вывода. Он должен поддерживать следующие операторы: унарный * для записи значения (т.е., *it = val) и префикс ++ для перемещения к следующему элементу.
Все неконстантные типы итераторов контейнеров Qt являются итераторами вывода.
Впереднаправленные итераторы - это итераторы удовлетворяющие требованиям, предъявляемым к итераторам ввода и к итераторам вывода.
Все неконтстантые типы итераторов контейнеров Qt являются впереднаправленными итераторами.
Двунаправленные итераторы - это итераторы, удовлетворяющие требованиям, предъявляемым к впереднаправленным итераторам, но, в добавок, поддерживающие префикс --, позволяющий им перемещаться к предыдущему элементу.
Все неконстантные типы итераторов контейнеров Qt являются двунаправленными итераторами.
Последняя категория, итераторы произвольного доступа, - это наиболее мощный тип итераторов. Итераторы этого типа удовлетворяют всем требованиям, предъявляемым к двунаправленным итераторам, и в добавок поддерживает следующие действия:
| i += n | перемещение итератора i на n позиций вперед |
| i -= n | перемещение итератора i на n позиций назад |
| i + n или n + i | возвращает итератор, позиционированный на элемент, расположенный на n позиций после итератора i |
| i - n | возвращает итератор, позиционированный на элемент, расположенный на n позиций перед итератором i |
| i - j | возвращает количество элементов, расположенных между итераторами i и j |
| i[n] | то-же самое, что и *(i + n) |
| i < j | возвращает true, если итератор j расположен позади итератора i |
Неконтстантные типы итераторов для QList, QLinkedList и QVector являются итераторами произвольного доступа.
См. также классы-контейнеры и <QtGlobal>.
Выполняет бинарный поиск в диапазоне [begin, end) в возвращает позицию найденного вхождения значения value. Если вхождения value не найдено, возвращает end.
Элементы в диапазоне [begin, end) должны быть отсортированы по возрастанию; см. qSort().
Если существует несколько вхождений искомого значения, то возвращается позиция любого из них. Если Вам нужно более гибкое управление, используйте qLowerBound() или qUpperBound().
Пример:
QVector<int> vect;
vect << 3 << 3 << 6 << 6 << 6 << 8;
QVector<int>::iterator i =
qBinaryFind(vect.begin(), vect.end(), 6);
// i == vect.begin() + 2 (или 3, или 4)
Данная функция требует, чтобы для типа элементов (в вышеприведенном примере это QString) был определен operator<().
Пример использования функции см. в подробном описании.
См. также qLowerBound(), qUpperBound() и итераторы произвольного доступа.
Копирует элементы из диапазона [begin1, end1) в диапазон [begin2, ...), сохраняя их порядок.
Элемент, расположенный в позиции begin1, копируется в позицию begin2; элемент, расположенный в позиции begin1 + 1, копируется в позицию begin2 + 1 и т.д.
Пример:
QStringList list;
list << "one" << "two" << "three";
QVector<QString> vect1(3);
qCopy(list.begin(), list.end(), vect1.begin());
// vect: [ "one", "two", "three" ]
QVector<QString> vect2(8);
qCopy(list.begin(), list.end(), vect2.begin() + 2);
// vect: [ "", "", "one", "two", "three", "", "", "" ]
См. также qCopyBackward(), итераторы ввода и итераторы вывода.
Копирует элементы из диапазона [begin1, end1) в диапазон [..., end2).
Элемент, расположенный в позиции end1 - 1, копируется в позицию end2 - 1; элемент, расположенный в позиции end1 - 2, копируется в позицию end2 - 2 и т.д.
Пример:
QStringList list;
list << "one" << "two" << "three";
QVector<QString> vect(5);
qCopyBackward(list.begin(), list.end(), vect.end());
// vect: [ "", "", "one", "two", "three" ]
См. также qCopy() и двунаправленные итераторы.
Присваивает параметру n количество вхождений значения value в диапазон [begin, end).
Пример:
QList<int> list;
list << 3 << 3 << 6 << 6 << 6 << 8;
int countOf6;
qCount(list.begin(), list.end(), 6, countOf6);
// countOf6 == 3
int countOf7;
qCount(list.begin(), list.end(), 7, countOf7);
// countOf7 == 0
Данная функция требует, чтобы для типа элементов (в вышеприведенном примере это int) был определен operator==().
См. также итераторы ввода.
С помощью оператора C++ delete удаляет все элементы из диапазона [begin, end). Элементы должны быть указателями (например, QWidget *).
Пример:
QList<Employee *> list;
list.append(new Employee("Blackpool", "Stephen"));
list.append(new Employee("Twist", "Oliver"));
qDeleteAll(list.begin(), list.end());
list.clear();
Обратите внимание на то, что qDeleteAll() не удаляет элементы из контейнера; он лишь вызывает для них delete. В вышеприведенном примере, мы вызываем clear() для удаления элементов из контейнера.
См. также впереднаправленные итераторы.
Данная перегруженная функция-член предоставлена для удобства. Ее поведение аналогично поведению вышеприведенной функции.
То-же самое, что и qDeleteAll(c.begin(), c.end()).
Сравнивает элементы из диапазона [begin1, end1) с элементами из диапазона [begin2, ...). Если все сравниваемые элементы эквивалентны, возвращает true; в противном случае возвращает false.
Пример:
QStringList list;
list << "one" << "two << "three";
QVector<QString> vect[3];
vect[0] = "one";
vect[1] = "two";
vect[2] = "three";
bool ret1 = qEqual(list.begin(), list.end(), vect.begin());
// ret1 == true
vect[2] = "seven";
bool rec2 = qEqual(list.begin(), list.end(), vect.begin());
// ret2 == false
Данная функция требует, чтобы для типа элементов (в вышеприведенном примере это QString) был определен operator==().
См. также итераторы ввода.
Заполняет диапазон [begin, end) значением value.
Пример:
QStringList list;
list << "one" << "two" << "three";
qFill(list.begin(), list.end(), "eleven");
// list: [ "eleven", "eleven", "eleven" ]
qFill(list.begin() + 1, list.end(), "six");
// list: [ "eleven", "six", "six" ]
См. также qCopy() и впереднаправленные итераторы.
Возвращает итератор, позиционированный на первое вхождение значения value в диапазон контейнера [begin, end). Если значение value не найдено, возвращает end.
Пример:
QStringList list;
list << "one" << "two" << "three";
QStringList::iterator i1 = qFind(list.begin(), list.end(), "two");
// i1 == list.begin() + 1
QStringList::iterator i2 = qFind(list.begin(), list.end(), "seventy");
// i2 == list.end()
Данная функция требует, чтобы для типа элементов (в вышеприведенном примере это QString) был определен operator==().
Если значения в диапазоне отсортированы по возрастанию, то, используя qLowerBound() или qBinaryFind() вместо qFind(), Вы можете получить результат быстрее.
См. также qBinaryFind() и итераторы ввода.
Выполняет бинарный поиск в диапазоне [begin, end) и возвращает позицию первого вхождения значения value. Если такое значение не найдено, возвращает позицию, в которой оно могло-бы быть вставлено.
Элементы в диапазоне [begin, end) должны быть отсортированы по возрастанию; см. qSort().
Пример:
QList<int> list;
list << 3 << 3 << 6 << 6 << 6 << 8;
QList<int>::iterator i = qLowerBound(list.begin(), list.end(), 5);
list.insert(i, 5);
// list: [ 3, 3, 5, 6, 6, 6, 8 ]
i = qLowerBound(list.begin(), list.end(), 12);
list.insert(i, 12);
// list: [ 3, 3, 5, 6, 6, 6, 8, 12 ]
Данная функция требует, чтобы для типа элементов (в вышеприведенном примере это int) был определен operator<().
qLowerBound() может использоваться совместно с qUpperBound() для перебора всех вхождений нужного значения:
QVector<int> vect;
vect << 3 << 3 << 6 << 6 << 6 << 8;
QVector<int>::iterator begin6 =
qLowerBound(vect.begin(), vect.end(), 6);
QVector<int>::iterator end6 =
qUpperBound(begin6, vect.end(), 6);
QVector<int>::iterator i = begin6;
while (i != end6) {
*i = 7;
++i;
}
// vect: [ 3, 3, 7, 7, 7, 8 ]
См. также qUpperBound() и qBinaryFind().
С помощью алгоритма сортировки кучи, сортирует по возрастанию элементы диапазона [begin, end).
Пример:
QList<int> list;
list << 33 << 12 << 68 << 6 << 12;
qSort(list.begin(), list.end());
// list: [ 6, 12, 12, 33, 68 ]
Алгоритм сортировки эффективен при больших наборах данных. Он выполняется за линейно-логарифмическое время, O(n log n).
Данная функция требует, чтобы для типа элементов (в вышеприведенном примере это int) был определен оператор operator<().
Если из двух элементов ни один не меньше другого, то они считаются эквивалентными, и порядок их после выполнения сортировки не определен.
См. также qStableSort() и двунаправленные итераторы.
Данная перегруженная функция-член предоставлена для удобства. Ее поведение аналогично поведению вышеприведенной функции.
Вместо оператора operator<(), для сравнения элементов, использует функцию lessThan.
Например, здесь показано, как отсортировать строки в QStringList по алфавиту без учета регистра:
bool caseInsensitiveLessThan(const QString &s1, const QString &s2)
{
return s1.toLower() < s2.toLower();
}
int doSomething()
{
QStringList list;
list << "AlPha" << "beTA" << "gamma" << "DELTA";
qSort(list.begin(), list.end(), caseInsensitiveLessThan);
// list: [ "AlPha", "beTA", "DELTA", "gamma" ]
}
Для сортировки значений в обратном порядке, в качестве параметра lessThan передайте qGreater<T>(). Например:
QList<int> list;
list << 33 << 12 << 68 << 6 << 12;
qSort(list.begin(), list.end(), qGreater<int>());
// list: [ 68, 33, 12, 12, 6 ]
Если из двух элементов ни один не "меньше, чем" другой, то они считаются эквивалентными. Относительный порядок таких элементов после выполнения сортировки не определен.
В качестве альтернативы к использованию qSort(), можно поместить элементы в QMap и в качестве ключа сортировки использовать ключ QMap. Зачастую, это более удобно, чем определение функции lessThan. Например, в следующем примере показано, как отсортировать список строк без учета регистра с помощью QMap:
QStringList list;
list << "AlPha" << "beTA" << "gamma" << "DELTA";
QMap<QString, QString> map;
foreach (QString str, list)
map.insert(str.toLower(), str);
list = map.values();
См. также QMap.
Данная перегруженная функция-член предоставлена для удобства. Ее поведение аналогично поведению вышеприведенной функции.
То-же самое, что и qSort(container.begin(), container.end());
Используя алгоритм сортировки кучи сортирует элементы диапазона [begin, end) в порядке возрастания.
Пример:
QList<int> list;
list << 33 << 12 << 68 << 6 << 12;
qStableSort(list.begin(), list.end());
// list: [ 6, 12, 12, 33, 68 ]
Алгоритм сортировки эффективен для больших наборов данных. Он выполняется за линейно-логарифмичесое время, O(n log n).
Данная функция требует, чтобы для типа элементов (в вышеприведенном примере это int) был определен operator<().
Если из двух элементов ни один не меньше другого, то они считаются эквивалентными. В этом случае, элемент, который стоял перед другим в начальном контейнере будет стоять раньше и после выполнения сортировки. Эта возможность полезна при сортировке видимых пользователем данных.
См. также qSort() и двунаправленные итераторы.
Данная перегруженная функция-член предоставлена для удобства. Ее поведение аналогично поведению вышеприведенной функции.
Для сравнения вместо оператора operator<() использует lessThan.
Например, здесь показано, как отсортировать по алфавиту без учета регистра строки в QStringList:
bool caseInsensitiveLessThan(const QString &s1, const QString &s2)
{
return s1.toLower() < s2.toLower();
}
int doSomething()
{
QStringList list;
list << "AlPha" << "beTA" << "gamma" << "DELTA";
qStableSort(list.begin(), list.end(), caseInsensitiveLessThan);
// list: [ "AlPha", "beTA", "DELTA", "gamma" ]
}
Для сортировки значений в обратном порядке, в качестве параметра lessThan передайте qGreater<T>(). Например:
QList<int> list;
list << 33 << 12 << 68 << 6 << 12;
qStableSort(list.begin(), list.end(), qGreater<int>());
// list: [ 68, 33, 12, 12, 6 ]
Если из двух элементов ни один не "меньше, чем" другой, то элементы считаются эквивалентными. В этом случае элемент, который стоял перед другим в начальном контейнере будет стоять раньше и после выполнения сортировки. Эта возможность полезна при сортировке видимых пользователем данных.
Данная перегруженная функция-член предоставлена для удобства. Ее поведение аналогично поведению вышеприведенной функции.
То-же самое, что и qStableSort(container.begin(), container.end());
Меняет местами значения переменных var1 и var2.
Пример:
double pi = 3.14;
double e = 2.71;
qSwap(pi, e);
// pi == 2.71, e == 3.14
Выполняет бинарный поиск в диапазоне [begin, end) и возвращает позицию последнего вхождения значения value. Если такое значение не найдено, то возвращает позицию, в которую значение могло-бы быть вставлено.
Элементы в диапазоне [begin, end) должны быть отсортированы по возрастанию; см. qSort().
Пример:
QList<int> list;
list << 3 << 3 << 6 << 6 << 6 << 8;
QList<int>::iterator i = qUpperBound(list.begin(), list.end(), 5);
list.insert(i, 5);
// list: [ 3, 3, 5, 6, 6, 6, 8 ]
i = qUpperBound(list.begin(), list.end(), 12);
list.insert(i, 12);
// list: [ 3, 3, 5, 6, 6, 6, 8, 12 ]
Данная функция требует, чтобы для типа значений (в вышеприведенном примере это int) был определен operator<().
qUpperBound() может использоваться совместно с qLowerBound() для перебора всех вхождений нужного значения:
QVector<int> vect;
vect << 3 << 3 << 6 << 6 << 6 << 8;
QVector<int>::iterator begin6 =
qLowerBound(vect.begin(), vect.end(), 6);
QVector<int>::iterator end6 =
qUpperBound(vect.begin(), vect.end(), 6);
QVector<int>::iterator i = begin6;
while (i != end6) {
*i = 7;
++i;
}
// vect: [ 3, 3, 7, 7, 7, 8 ]
См. также qLowerBound() и qBinaryFind().
| Copyright © 2005 Trolltech | Trademarks | Qt 4.1.0 |
