1. Алгоритмы

Алгоритмы объявлены в <QtAlgorithms> и, как и контейнеры, реализуют уже имеющиеся в STL возможности.

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

В таблице 1 приведены типы итераторов, используемые различными алгоритмами. (Об итераторах см. в предыдущей статье этого цикла.)

Таблица 1. Типы итераторов

Обозначение	Описание
Итератор ввода (InputIterator)	Итератор, с помощью которого можно последовательно считывать данные из контейнера. Должен предоставлять операции сравнения == и !=, унарный оператор * для получения данных, а также префиксный инкремент ++ для перехода к следующей позиции.
Итератор вывода (OutputIterator)	Итератор, с помощью которого можно последовательно записывать данные в контейнер. Должен предоставлять унарный оператор * для записи данных и префиксный инкремент ++ для перехода к следующей позиции.
Прямой итератор (ForwardIterator)	Реализует возможности ввода и вывода.
Двунаправленный итератор (BidirectionalIterator)	ForwardIterator, дополнительно поддерживающий проход в обратном направлении при помощи префиксного декремента --.
Итератор с произвольным доступом (RandomAccessIterator)	BidirectionalIterator, реализующий все операции, в том числе переход на n элементов вперед или назад.

• Все итераторы являются итераторами ввода.
• Все не-const итераторы являются итераторами вывода, прямыми и двунаправленными.
• QList, QLinkedList и QVector – итераторы с произвольным доступом.

1.1. Сравнение контейнеров

Для сравнения элементов в контейнерах используется функция

bool qEqual (InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2);

Элементы в диапазоне [begin1, end1) (т.е. от begin1 до end1, исключая end1), последовательно сравниваются с элементами, начиная с позиции begin2.

Для сравнения используется operator==().

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

QLinkedList<int> a;

QVector<int> b;

 

a << 1 << 2 << 3;

b << 1 << 2 << 3;

 

qDebug() << qEqual (a.begin(), a.end(), b.begin());  // true

1.2. Заполнение контейнеров

qFill (begin, end, x) заносит значение x в элементы из диапазона [begin1, end1).

void qFill (ForwardIterator begin, ForwardIterator end, const T& x);

qFill (container, x) заносит значение x в диапазоне [container.begin(), container.end()).

void qFill (Container& container, const T& x);

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

QList<int> a, b;

 

a << 1 << 2 << 3;

b << 1 << 2 << 3;

 

qFill (a, 23);

qFill (b.begin() + 1, b.end(), 23);

 

qDebug() << a;  // (23, 23, 23)

qDebug() << b;  // ( 1, 23, 23)

qCopy(begin1, end1, begin2) последовательно копирует элементы в диапазоне [begin1, end1) в [begin2, ...).

OutputIterator qCopy (InputIterator begin1, InputIterator end1, OutputIterator begin2);

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

QList<int> a;

QVector<int> b (7);

 

a << 1 << 2 << 3;

 

qCopy (a.begin(), a.end(), b.begin());

qDebug() << b;  // (1, 2, 3, 0, 0, 0, 0)

qCopyBackward() отличается тем, что принимает итератор end (указывающий на последний элемент) для второго контейнера и копирует элементы, начиная с конца.

BidirectionalIterator2 qCopyBackward (BidirectionalIterator1 begin1,

                                      BidirectionalIterator1 end1,

                                      BidirectionalIterator2 end2);

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

QList<int> a;

QVector<int> b (7);

 

a << 1 << 2 << 3;

 

qCopyBackward (a.begin(), a.end(), b.end());

qDebug() << b;  // (0, 0, 0, 0, 1, 2, 3)

(Сравните с результатом работы qCopy().)

1.3. Удаление значений

qDeleteAll() вызывает delete для элементов контейнера (не путать с удалением элементов контейнера).

void qDeleteAll (ForwardIterator begin, ForwardIterator end);

void qDeleteAll (const Container& c);

Пример:

QList<Foo*> a;

 

// Создание объектов при помощи new:

a.append(new Foo(1));

a.append(new Foo(2));

a.append(new Foo(3));

 

// Вызов delete для всех объектов контейнера:

qDeleteAll (a);

 

// (В a по-прежнему содержится 3 элемента)

 

// Очистка контейнера:

a.clear();

 

// (В a содержится 0 элементов)

Итак, мы рассмотрели базовые операции с контейнерами. Теперь можно перейти к основным алгоритмам – сортировке и поиску.

1.4. Сортировка

Для сортировки в Qt используются два алгоритма со сложностью O(n log n): qSort() и qStableSort().

Элементы сравниваются при помощи заданного отношения предшествования, по умолчанию operator<(). Если для двух элементов a и b не выполняется ни a<b, ни b<a, то они считаются равными. В qSort() порядок следования равных элементов в отсортированном массиве будет произвольным, а в qStableSort() для них будет сохранен исходный порядок. Это полезно, например, когда сортировка ведется только по одному из полей, поэтому у элементов с равным значением этого поля не обязательно равны другие поля.

Функции qSort() и qStableSort() принимают в качестве аргументов итераторы, соответствующие первому элементу и элементу, следующему за последним. Если нужно отсортировать весь контейнер, то используется

qSort(container.begin(), container.end());

Для удобства имеется перегруженная версия:

qSort(container);

В качестве третьего аргумента можно указать свою функцию сравнения (как функтор, т.е. объект с перегруженным operator()).

Например, пусть требуется отсортировать комплексные числа по их абсолютному значению.

#include <QList>

#include <QtAlgorithms>

#include <complex>

#include <iostream>

 

template<typename T> bool absValueLt (const T& x, const T& y)

{

  return std::abs(x) < std::abs(y);

}

 

typedef std::complex<double> complex;

 

int main()

{

  QList<int> stack;

 

  QList<complex> values;

 

  values.append(complex(  1.0,  1.0));

  values.append(complex(  4.0,  0.0));

  values.append(complex(  1.0,  2.0));

  values.append(complex(-10.0,  2.0));

  values.append(complex(  1.0, -1.0));

  values.append(complex(  0.0,  0.0));

 

  qSort(values.begin(), values.end(), absValueLt<complex>);

 

  foreach (complex x, values)

    std::cout << x << std::endl;

 

  return 0;

}

Вывод программы:

(0,0)

(1,-1)

(1,1)

(1,2)

(4,0)

(-10,2)

Заметьте, что мы сначала добавили в список 1.0 + 1.0 i, а затем 1.0 − 1.0 i. Так как оба числа имеют абсолютное значение √2, то для алгоритма сортировки они эквивалентны, и порядок следования в отсортированном списке не важен. И действительно, в выводе программы сначала идет 1.0 − 1.0 i, а потом уже 1.0 + 1.0 i. Для сохранения порядка можно было бы использовать

qSort(values.begin(), values.end(), absValueLt<complex>);

Для сортировки по убыванию нужно передать функтор qGreater<T>(). По умолчанию используется qLess<T>():

QList<int> values;

values << 5 << 9 << 6 << 10 << 7 <<

3 << 8 << 2 << 1 << 4;

 

qSort (values.begin(), values.end(), qLess<int>());

qDebug() << values;  // (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

 

qSort (values.begin(), values.end(), qGreater<int>());

qDebug() << values;  // (10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

Таким образом можно сортировать QList<T> и QVector<T>.

Также функции сортировки можно использовать для контейнеров STL и даже для обычных массивов C++ – разницы нет, так как итераторы в стиле STL спроектированы по образцу указателей.

const int n = 10;

int* values = new int[n];  // как begin()

int* end = values + n;     // как end()

 

for (int* i = values; i != end; i++)

  (*i) = rand() % 10;

 

qStableSort (values, end);

1.5. Поиск

В Qt имеется простой линейный поиск qFind(), а также бинарный qBinaryFind(), который имеет логарифмическую сложность O(log n), но ожидает на входе отсортированный контейнер.

Как и в случае функций для сортировки, нужно передать итераторы, указывающие на первый элемент и элемент, следующий за последним. Для qBinaryFind() можно указать свою функцию сравнения. qFind() не использует порядок элементов и ищет просто при помощи operator==().

RandomAccessIterator qFind (RandomAccessIterator begin,

RandomAccessIterator end,

                            const T& x);

 

Container::const_iterator qFind (const Container& container, const T& x);

RandomAccessIterator qBinaryFind (RandomAccessIterator begin,

RandomAccessIterator end,

                                  const T& x);

 

RandomAccessIterator qBinaryFind (RandomAccessIterator begin,

RandomAccessIterator end,

                                  const T& x, LessThan lessThan);

 

Container::const_iterator qBinaryFind

(const Container& container, const T& x);

Если элемент найден, то возвращается указывающий на него итератор; в противном случае возвращается итератор end(). Функции возвращают первый найденный элемент. При этом qFind() линейно просматривает контейнер от начала к концу, поэтому дает первое совпадение с начала контейнера.

Рассмотрим какой-нибудь экзотический критерий поиска, для которого нужно специально определить operator==().

Пусть нам нужно выбрать из списка только такие элементы x, что x ≡ 11 (mod 23) (которые при делении на 23 дают остаток 11). Используем линейный поиск. Реализуем свой класс перегрузкой operator==():

template<typename T, T M> class ModInt

{

  T x_;

 

public:

  ModInt (const T& x) : x_(x) {}

  bool operator== (const ModInt<T,M>& y) const

  {

    return x_ % M == y.value() % M;

  }

  const T& value() const { return x_; }

};

 

int main()

{

  typedef ModInt<unsigned int,23> mod23;

 

  QList<mod23> values;

  values << 51 << 69 << 816 << 885 <<

   15 << 839 << 55 << 793 << 712 << 421;

 

  // Первый элемент, сравнимый с 11 по модулю 23:

  QList<mod23>::const_iterator result = qFind (values, mod23(11));

 

  if (result != values.constEnd())

    qDebug() << (*result).value();  // 816

 

  return 0;

}

Линейный поиск реализуется очень просто:

template <typename InputIterator, typename T> inline InputIterator

qFind(InputIterator first, InputIterator last, const T& x)

{

  while (first != last && !(*first == x))

    ++first;

  return first;

}

С линейным поиском также связан подсчет вхождений значения в контейнере:

void qCount (InputIterator begin, InputIterator end, const T& x, Size& n);

void qCount (const Container& container, const T& x, Size& n);

qCount прибавляет к числу по ссылке n количество вхождений.

QList<int> a;

 

a << 1 << 2 << 3 << 1 << 2 <<

3 << 1 << 2 << 3;

 

int n = 0;

 

qCount(a, 1, n);

 

// n = 0 + 3 = 3

 

qCount(a, 2, n);

 

 

// n = 3 + 3 = 6

Бинарный поиск нужен в том случае, когда содержимое контейнера не меняется, и его можно единожды отсортировать, после чего искать элементы.

Для того же примера можно определить свою функцию сравнения, отсортировать элементы и применить qBinaryFind():

template<typename T, T M> bool lessMod (const T& x, const T& y)

{

  return x % M < y % M;

  // Если отказаться от подобного шаблона,

  // то M можно передавать в конструкторе функтора.

}

 

int main()

{

  QList<unsigned int> values;

  values << 51 << 69 << 816 << 885 << 15

  << 839 << 55 << 793 << 712 << 421;

 

  qSort (values.begin(), values.end(), lessMod<unsigned int,23>);

 

  qDebug() << values;  // (69, 51, 421, 55, 793, 816, 885, 839, 15, 712)

 

  QList<unsigned int>::const_iterator result =

    qBinaryFind (values.constBegin(), values.constEnd(),

    11, lessMod<unsigned int,23>);

 

  if (result != values.constEnd())

    qDebug() << *result;  // 839

 

  return 0;

}

qLowerBound() и qUpperBound() также работают с отсортированными последовательностями. qLowerBound() возвращает итератор, указывающий на первый совпавший элемент, а qUpperBound() – на элемент, следующий за последним совпавшим.

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

Для полного понимания, надо еще ответить на другие вопросы.

1. А что произойдет, если искомое значение не содержится в обрабатываемом списке? Ответ: обе функции вернут элемент, содержащий значение больше, чем искомое значение. Например, если есть список {1, 5, 10, 15, 20}, то при искомом параметре 12 обе функции вернут итератор, указывающий на ячейку 15.

2. А что будет происходить, если искомый диапазон получится в одно значение, когда нет повторяющихся элементов, и в качестве искомого значения задано значение, точно соответствующее одному элементу? Например, что будет если искать значение 10 в вышеуказанном списке? Тогда qLowerBound() вернет итератор на ячейку 10, а функция qUpperBound()вернет итератор на ячейку 15.

Подробнее об этом написано в статье: Понимание работы функций qLowerBound() и qUpperBound() в Qt

Еще примеры:

QList<unsigned int>::const_iterator start =

  qLowerBound (values.constBegin(), values.constEnd(),

  11, lessMod<unsigned int,23>);

QList<unsigned int>::const_iterator end =

  qUpperBound (values.constBegin(), values.constEnd(),

  11, lessMod<unsigned int,23>);

В отсортированной последовательности (69, 51, 421, 55, 793, 816, 885, 839, 15, 712) start будет указывать на позицию со значением 793, а end – со значением 15. Эти границы можно использовать для прохода по всем совпавшим элементам:

while (start != end)

{

  qDebug() << *start;

  ++start;

}

// 793, 816, 885, 839

Если элемент не найден, то qLowerBound() и qUpperBound() возвратят один и тот же итератор, указывающий на позицию, в которой элемент должен находиться в соответствии с порядком сортировки.

Например, если в нашем списке искать 93 с функцией сравнения по модулю 23, то в качестве нижней и верхней границы мы получим итератор, указывающий на второй элемент. Значит, в соответствии с принятой функцией сравнения значение 93 должно находиться в этой позиции:

unsigned int x = 93;

 

QList<unsigned int>::iterator start =

  qLowerBound (values.begin(), values.end(), x, lessMod<unsigned int,23>);

 

QList<unsigned int>::iterator end =

  qUpperBound (values.begin(), values.end(), x, lessMod<unsigned int,23>);

 

qDebug() << values;  // (69,     51, 421, 55, 793, 816, 885, 839, 15, 712)

 

if (start == end)

  values.insert(start, x);

 

qDebug() << values;  // (69, 93, 51, 421, 55, 793, 816, 885, 839, 15, 712)

Варианты вызова:

RandomAccessIterator qLowerBound

(RandomAccessIterator begin, RandomAccessIterator end,

                                  const T& x);

 

RandomAccessIterator qLowerBound

(RandomAccessIterator begin, RandomAccessIterator end,

                                  const T& x, LessThan lessThan);

 

Container::const_iterator qLowerBound

(const Container& container, const T& x);

 

RandomAccessIterator qUpperBound

(RandomAccessIterator begin, RandomAccessIterator end,

                                  const T& x);

 

RandomAccessIterator qUpperBound

 (RandomAccessIterator begin, RandomAccessIterator end,

                                  const T& x, LessThan lessThan);

 

Container::const_iterator qUpperBound

(const Container& container, const T& x);