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