C++17 STL Стандартная библиотека шаблонов

Сначала функция 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);

  };

}