. Первая возвращает итератор на первый элемент, чье значение не меньше искомого, вторая — на первый элемент, чье значение больше искомого:
print_int(lower_bound(begin(v), end(v), 7));
print_int(upper_bound(begin(v), end(v), 7));
}
15. Скомпилируем и запустим программу для подтверждения того, что наши предположения и результат ее работы совпадают:
$ ./finding_items
{Cologne, 1060000}
{Cologne, 1060000}
{Berlin, 3502000}
1
7
8
7
8
Как это работает
В этом примере мы использовали следующие алгоритмы поиска (табл. 5.3).
Все описанные функции в качестве необязательного дополнительного аргумента принимают пользовательские функции сравнения. Таким образом, операцию поиска можно изменять, что мы и сделали в этом примере.
Рассмотрим более подробно принцип работы
std::equal_range
. Представьте, что у нас есть вектор, v = {0,1,2,3,4,5,6,7,7,7,8}
и мы вызываем метод equal_range(begin(v),end(v),7);
, чтобы выполнить бинарный поиск значения 7
. Функция equal_range возвращает пару итераторов, указывающих на нижнюю и верхнюю границы; они указывают на диапазон {7,7,7}
, поскольку в векторе содержится именно столько значений 7
. Для большей ясности взгляните на рис. 5.1.Сначала функция
equal_range
использует типичный подход к выполнению бинарного поиска до тех пор, пока не встретит элементы, чье значение не меньше, чем искомое. Далее выполнение разбивается на вызовы методов lower_bound
и upper_bound
, чтобы объединить их возвращаемые значения в пару и затем вернуть эту пару вызывающей стороне.Для получения функции бинарного поиска, которая просто возвращает первый элемент, соответствующий требованиям, мы могли бы реализовать следующее:
template
Iterator standard_binary_search(Iterator it, Iterator end_it, T value)
{
const auto potential_match (lower_bound(it, end_it, value));
if (potential_match != end_it && value == *potential_match) {
return potential_match;
}
return end_it;
}
Эта функция использует вызов
std::lower_bound
, чтобы найти первый элемент, чье значение не меньше, чем value
. Полученный результат potential_match
может соответствовать одному из трех сценариев.□ Ни один элемент не соответствует нашему условию. В таком случае значение
potential_match
будет идентично end_it
.□ Первый найденный элемент, соответствующий условию, больше искомого значения. В этом случае мы должны указать, что не нашли элемент, вернув
end_it
.□ Элемент, на который указывает
potential_match
, равен искомому значению. Поэтому он является не только потенциальным, но и реальным совпадением, и его можно вернуть.
Если наш тип
T
не поддерживает оператор ==
, то должен поддерживать хотя бы оператор <
для выполнения бинарного поиска. Далее можно переписать сравнение как !(value < *potential_match) && !(*potential_match < value)
. Если найденный элемент не меньше и не больше искомого, то он должен быть равен искомому.Одной из потенциальных причин, по которой STL не предоставляет такую функцию, является отсутствие информации о том, что делать, если обнаружено несколько совпадений, как было показано на рис. 5.1, где вектор содержит несколько значений
7
.
Обратите внимание: структуры данных наподобие
std::map
, std::set
и т.д. имеют собственные функции find
. Они работают быстрее, чем более обобщенные алгоритмы, поскольку тесно связаны с реализациями структур данных.Ограничиваем допустимые значения вектора конкретным численным диапазоном с помощью std::clamp
Во многих приложениях мы получаем из некоторого источника численные данные. Прежде чем у нас получится построить для них график или обработать их как-то иначе, может понадобиться нормализовать их, поскольку значения, сгенерированные случайным образом, чаще всего заметно отличаются друг от друга.
Обычно это значит, что нужно выполнить вызов
std::transform
для структуры данных, которая содержит случайные значения, а также вызвать простую функцию масштабирования. Но если мы не знаем, насколько большими или маленькими являются значения, то нужно сначала пройти по данным, чтобы найти правильные измерения для функции масштабирования.Библиотека STL содержит полезные функции, которые можно применить для решения данной задачи:
std::minmax_element
и std::clamp
. Эти функции можно использовать в совокупности с некоторыми лямбда-выражениями.
Как это делается
В этом примере мы нормализуем значения вектора из примера диапазона чисел двумя способами, использовав методы
std::minmax_element
и std::clamp
.
1. Как и всегда, сначала включим следующие заголовочные файлы и объявим об использовании пространства имен
std
:
#include
#include
#include
#include
using namespace std;
2. Реализуем функцию, принимающую минимальное и максимальное значения диапазона, а также новый максимум, что позволит проецировать значения из старого диапазона в более мелкий. Объект функции принимает подобные значения и возвращает другой объект функции, который выполняет именно такое преобразование. Для простоты этим значением будет
0
, поэтому независимо от того, какое смещение имели старые данные, нормализованные значения всегда будут соответствовать порядку нуля. Для повышения читабельности проигнорируем такой факт: значения max
и min
могут быть одинаковыми, что приведет к делению на ноль.
static auto norm (int min, int max, int new_max)
{
const double diff (max - min);
return [=] (int val) {
return int((val - min) / diff * new_max);
};
}
3. Еще один конструктор объектов функций с именем
clampval
возвращает объект функции, который захватывает значения max
и min
и вызывает функцию std::clamp
, чтобы поместить получаемые значения в заданный диапазон:
static auto clampval (int min, int max)
{
return [=] (int val) -> int {
return clamp(val, min, max);
};
}
4. Данные, которые мы будем нормализовывать, представляют собой вектор, содержащий разнообразные значения. Они могут быть, например, данными о температуре, высоте ландшафта или стоимости акций, изменяющимися с течением времени:
int main()
{
vector v {0, 1000, 5, 250, 300, 800, 900, 321};
5. Чтобы нормализовать эти данные, нужно иметь наивысшее и наименьшее значения. Здесь поможет функция
std::minmax_element
. Она возвращает пару итераторов, указывающих именно на эти два значения:
const auto [min_it, max_it] (
minmax_element(begin(v), end(v)));
6. Скопируем все значения из первого вектора во второй. Создадим экземпляр второго вектора и подготовим его к тому, чтобы он принял столько новых элементов, сколько содержится в первом векторе: