В этой секции, мы будем использовать бинарный поиск, для реализации "static const" map. Структура данных полностью хранится в памяти и состоит из пары "фамилия, имя", которые отсортированы по фамилии. По сравнению с использованием QMap или QHash, этот подход экономит память и имеет смысл в высоко оптимизированных приложениях или библиотеках.
Сначала, мы определяем структуру для имен, а так же операторы сравнения для поиска вхождения фамилий:
>struct Entry {
> const char *familyName;
> const char *givenName;
>};
>
>bool operator<(const Entry &entry, const QString &family)
>{
> return entry.familyName < family;
>}
>
>bool operator<(const QString &family, const Entry &entry)
>{
> return family < entry.familyName;
>}
Затем объявляем наши данные:
>static const int NumEntries = 4;
>static const Entry entries[NumEntries] = {
> { "Deitel", "Harvey" },
> { "Deitel", "Paul" },
> { "Jobs", "Steve" },
> { "Torvalds", "Linus" }
>};
>static const Entry * const end = entries + NumEntries;
Указатель end отмечает конец массива.
>bool contains(const QString &family)
>{
> return qBinaryFind(entries, end, family) != end;
>}
Теперь, когда все на месте, реализация contains() тривиальна. Так как C++ указатели отвечают критериям STL итераторов произвольного доступа, мы можем использовать их в связке с qBinaryFind().
>QString givenName(const QString &family)
>{
> const Entry *i = qBinaryFind(entries, end, family);
> if (i == end)
> return "";
> return i->givenName;
>}
Функция givenName() возвращает имя человека с данной фамилией. Например, если мы передаем в качестве аргумента "Torvalds", мы получаем "Linus"; если мы передаем "Deitel", функция возвращает "Harvey" или "Paul".
>QStringList givenNames(const QString &family)
>{
> const Entry *i = qLowerBound(entries, end, family);
> const Entry *j = qUpperBound(entries, end, family);
> QStringList result;
> while (i != j)
> result += (i++)->givenName + (" " + family);
> return result;
>}
Функция givenNames() возвращает список людей, принадлежащих определенной семье. Здесь показано использование qLowerBound() и qUpperBound().
