|
|||||||
Время создания: 21.01.2020 12:19
Автор: Xintrea
Текстовые метки: qt, контейнер, алгоритм, итератор, обход, поиск, сортировка, позиция, qLowerBound, qUpperBound
Раздел: Компьютер - Программирование - Язык C++ (Си++) - Библиотека Qt - Принципы написания кода
Запись: xintrea/mytetra_syncro/master/base/1579598390rgkxma29ee/text.html на raw.github.com
|
|||||||
|
|||||||
В разных источниках по-разному описана работа функций qLowerBound() и qUpperBound(), используемых для нахождения элемента с помощью алгоритма бинарного дерева. Здесь приведены примеры, демонстрирующие что делают данные функции. Первое, что нужно знать: данные алгоритмы работают только с отсортированными последовательностями. Если последовательность будет неотсортирована, результат будет неопределен. В последовательности допустимы повторяющиеся элементы. Второе что нужно знать, это то, что данные алгоритмы выполняют поиск с помощью бинарного дерева. То есть, вычислительная сложность нахождения элемента O(log n), что гораздо лучше линейного поиска O(n). И самое главное, что нужно понимать. qLowerBound() и qUpperBound() - это не функции-антагонисты, одна из которых находит элемент со значением меньше заданного, а вторая - больше чем задано. Точное назначение этих функций написано в следующих определениях: qLowerBound() - Нахождение элемента со значением, больше либо равно заданному qUpperBound() - Нахождение элемента со значением, больше заданному Вот так, наименование qLowerBound() не говорит о том, что будет произведен поиск со значением меньше заданного. Если этой особенности не знать, на этом можно споткнуться. Функции qLowerBound() и qUpperBound() сделаны, в частности, для того, чтобы находить границы повторяющихся значений в контейнерах. Чтобы понимать, что могут возвращать эти функции, можно рассмотреть следующий код (функция lessThan() даже не нужна, потому что для типа целых положительных и так существует оператор <, но когда будет разрабатываться сравнение других типов, можно по-быстрому сделать такую функцию по приведенному образу и подобию): bool lessThan(const unsigned int &a, const unsigned int &b) { return a < b; } ...
QList<unsigned int> values; values << 1 << 12 << 32 << 51 << 64 << 81 << 88 << 91 << 98; qDebug() << values; unsigned int valueForFindPos=70; qDebug() << "Value for find pos: "<< valueForFindPos; QList<unsigned int>::const_iterator result = qLowerBound (values.begin(), values.end(), valueForFindPos, lessThan); if (result == values.constEnd()) qDebug() << "Found end of list"; else qDebug() << "Found element: " << *result; В этой программе происходит попытка поиска несуществующего значения 70. Вывод этой программы будет следующий: (1, 12, 32, 51, 64, 81, 88, 91, 98) Value for find pos: 70 Found element: 81 Если же заменить qLowerBound() на qUpperBound(), то вывод не изменится. Результаты данных функций будут различны только в том случае, если будет точно найден сравниваемый элемент. Для qLowerBound() и значения 51 результат будет следующим: (1, 12, 32, 51, 64, 81, 88, 91, 98) Value for find pos: 51 Found element: 51 А для qUpperBound() и значения 51 результат будет следующим: (1, 12, 32, 51, 64, 81, 88, 91, 98) Value for find pos: 51 Found element: 64 Если же в данной последовательности будет несколько значений 51, то qLowerBound() вернет итератор на первую левую ячейку со значением 51, а функция qUpperBound() вернет итератор на ячейку, следующую за самой правой ячейкой со значением 51, то есть на ячейку со значением 64. |
|||||||
Так же в этом разделе:
|
|||||||
![]() |
|||||||
|
|||||||
|