MyTetra Share
Делитесь знаниями!
Понимание работы функций qLowerBound() и qUpperBound() в Qt
21.01.2020
12:19
Автор: Xintrea
Текстовые метки: qt, контейнер, алгоритм, итератор, обход, поиск, сортировка, позиция, qLowerBound, qUpperBound
Раздел: Компьютер - Программирование - Язык C++ - Библиотека Qt - Принципы написания кода

В разных источниках по-разному описана работа функций 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.


Так же в этом разделе:
 
MyTetra Share v.0.52
Яндекс индекс цитирования