Содержание


Программирование с Qt

Часть 4. Алгоритмы. Флаги и биты

Comments

Серия контента:

Этот контент является частью # из серии # статей: Программирование с Qt

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Программирование с Qt

Следите за выходом новых статей этой серии.

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() – на элемент, следующий за последним совпавшим.

Для примера выше

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);

2. Безопасная работа с флагами

В самой первой статье мы уже упоминали флаги в связи с Q_FLAGS. Этот макрос просто делает набор флагов доступным для метаобъектной системы. Для улучшения работы с флагами имеются другие средства.

Если в перечислении использовать целые значения по степеням двойки, то им будут соответствовать единицы в отдельных разрядах. На этом и основываются флаги. При их объявлении лучше использовать макросы Q_DECLARE_FLAGS и Q_DECLARE_OPERATORS_FOR_FLAGS:

class Foo
{
public:
  enum Option
  {
    Alpha   = 0x1,   // 00001
    Beta    = 0x2,   // 00010
    Gamma   = 0x4,   // 00100
    Delta   = 0x8,   // 01000
    Epsilon = 0x10   // 10000
  };
  Q_DECLARE_FLAGS(Options, Option)
  // ...
};

Q_DECLARE_OPERATORS_FOR_FLAGS(Foo::Options)

Макрос Q_DECLARE_FLAGS(Options, Option) раскрывается в

typedef QFlags<Option> Options;

Здесь Option – имя перечисления, а Options – имя набора флагов. Обратите внимание на принятый стиль именования: перечислению Foobar соответствует набор флагов Foobars.

Макрос Q_DECLARE_OPERATORS_FOR_FLAGS раскрывается в перегрузку оператора | для флагов данного набора, так, чтобы объекты Foo::Options были замкнуты по объединению через |.

Теперь мы можем использовать тип Foo::Options. Для него объявлены конструкторы из значений Foo::Option и допускается создание пустого набора флагов в виде Foo::Options(). Мы можем комбинировать флаги через |, но, в отличие от случая обычных флагов, произвольное целое число не допускается:

void test (Foo::Options flag)
{
  if (flag.testFlag(Foo::Alpha))
    qDebug() << "Alpha";
  if (flag.testFlag(Foo::Beta))
    qDebug() << "Beta";
}

int main()
{
  test (Foo::Alpha | Foo::Beta);
  test (0x1);  // ошибка!

  return 0;
}

Метод testFlag() в примере выше проверяет, установлен ли определенный флаг. Также доступно исключающее ИЛИ, побитовое НЕ, побитовое ИЛИ:

Foo::Options f1(Foo::Alpha | Foo::Beta);   // 00011
Foo::Options f2(~f1);                      // 11100
Foo::Options f3(Foo::Alpha | Foo::Gamma);  // 00101
Foo::Options f4(f1^f3);                    // 00110

Такие флаги используются в программном интерфейсе Qt и могут пригодиться вам при создании собственных интерфейсов.

3. Массивы битов

Массив битов представляется классом QBitArray. Например, чтобы создать массив из 100 битов, инициализированных значением true, можно использовать

QBitArray ba(100, true);

По умолчанию второй аргумент равен false.

Число элементов массива можно получить при помощи метода size(). Элементы индексируются, начиная с 0.

Размер можно изменить при помощи resize(n). Если n > size(), то в конец добавляются нулевые биты; если n < size(), то биты в конце будут отброшены.

truncate(n) просто отбрасывает конечные биты, чтобы в массиве осталось n битов. При n <= size() ничего не происходит.

ba.resize(200);
ba.truncate(23);

ba.clear() работает как ba.truncate(0). Если размер массива равен 0, то isEmpty() возвращает true:

QBitArray(0).isEmpty();  // true
QBitArray(1).isEmpty();  // false
QBitArray(2).isEmpty();  // false

Чтобы заново заполнить массив, можно использовать метод fill():

ba.fill(false, 93);  // изменить размер до 93
                     // и установить для всех битов false

ba.fill(true, 23, 46);  // установить true в диапазоне [23, 46)
                        // (исключая 46); границы диапазона
                        // должны быть верными (от 0 до size())

По умолчанию второй аргумент fill() принимает специальное значение -1, означающее, что размер не должен меняться.

Для считывания и установки битов используются методы testBit() и setBit():

ba.setBit(0, false);
ba.setBit(1, true);
ba.setBit(2, false);

qDebug() << ba.testBit(0) << ba.testBit(1) << ba.testBit(2);  // false true false

Вместо setBit(i, true) можно просто писать setBit(i). Вместо setBit(i, false)clearBit(i):

ba.clearBit(0);
ba.setBit(1);
ba.clearBit(2);
toggleBit(i) переключает i-й бит, т.е. меняет true на false и false на true.
ba.toggleBit(0);  // было false, стало true
ba.toggleBit(1);  // было true, стало false
ba.toggleBit(2);  // было false, стало true

Оператор [] перегружен и работает, как и для обычного массива. При этом для const-массива возвращается bool, а для не-const – специальный тип QBitRef, допускающий присваивание:

ba[0] = false;
ba[1] = true;
ba[2] = false;

Также можно использовать ba.at(i), но на самом деле at() и const-метод operator[] объявлены как встроенные (inline) и непосредственно отображаются в testBit().

Использование QBitRef может быть связано с дополнительными затратами, поэтому лучше использовать setBit().

Если нужно посчитать число нулей или единиц в массиве, используйте count():

ba.count(true);   // число единиц
ba.count();       // то же самое

ba.count(false);  // число нулей

Для двух битовых массивов можно использовать операции сравнения == и !=.

Также имеются бинарные операторы &, |, ^ – соответственно побитовое И, ИЛИ, исключающее ИЛИ. Унарный ~ инвертирует биты (побитовое НЕ). Также есть операторы &=, |=, ^=, изменяющие первый операнд.

QBitArray a(4);
QBitArray b(4);

a.setBit(0,true);
a.setBit(1,false);
a.setBit(2,true);
a.setBit(3,true);
// a := [1,0,1,1]

b.setBit(0,false);
b.setBit(1,false);
b.setBit(2,false);
b.setBit(3,true);
// b := [0,0,0,1]

a & b;  // [0,0,0,1]
a | b;  // [1,0,1,1]
a ^ b;  // [1,0,1,0]
~a;     // [0,1,0,0]

Очевидно, для массивов разного размера == всегда дает false, а != всегда дает true. Бинарные операторы действуют таким образом, что недостающие биты меньшего массива заполняются нулями:

QBitArray a(2);
QBitArray b(4);

a.setBit(0,true);
a.setBit(1,false);
// a := [1,0]

b.setBit(0,false);
b.setBit(1,false);
b.setBit(2,false);
b.setBit(3,true);
// b := [0,0,0,1]

a & b;  // [0,0,0,0]
a | b;  // [1,0,0,1]
a ^ b;  // [1,0,0,1]

Заключение

  1. В <QtAlgorithms> можно найти основной набор операций с контейнерами: сравнение содержимого, заполнение и копирование контейнеров; сортировку и поиск. Соответствующие функции <QtAlgorithms> являются универсальными, так как работают с итераторами.
  2. Если вам нужно использовать свой набор флагов, то следует, как обычно, создать перечисление со степенями двойки, но затем задействовать макросы Q_DECLARE_FLAGS и Q_DECLARE_OPERATORS_FOR_FLAGS. Вы получите более удобный и безопасный код.
  3. Для работы с массивами битов имеется класс QBitArray.

В следующей статье мы рассмотрим работу со строками и регулярными выражениями.


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=496771
ArticleTitle=Программирование с Qt: Часть 4. Алгоритмы. Флаги и биты
publish-date=06172010