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

это по-другому.

  {

    auto found_cologne (find(begin(c), end(c), city{"Cologne", 1060000}));

    print_city(found_cologne);

  }

9. Не зная численности населения города, а также не задействуя оператор ==, можно выполнить поиск только путем сравнения названия с содержимым вектора. Функция std::find_if принимает объект функции-предиката вместо конкретного значения. Таким образом можно выполнить поиск элемента для города Кельна, зная только его название:

  {

    auto found_cologne (find_if(begin(c), end(c),

      [] (const auto &item) {

        return item.name == "Cologne";

    }));

    print_city(found_cologne);

  }

10. Чтобы сделать операцию поиска чуть более выразительной, можно реализовать конструктор предикатов. Объект функции population_higher_than принимает численность населения и возвращает функцию, которая сообщает, превышает ли данная численность захваченное значение. Воспользуемся им, чтобы найти в нашем небольшом диапазоне данных немецкий город, в котором проживает более двух миллионов человек. Внутри нашего вектора таким городом является только Берлин.

  {

    auto population_more_than ([](unsigned i) {

      return [=] (const city &item) {

        return item.population > i;

      };

    });

    auto found_large (find_if(begin(c), end(c),

      population_more_than(2000000)));

    print_city(found_large);

  }

11. Использованные нами функции поиска проходят по контейнерам линейно. Поэтому они имеют коэффициент сложности O(n). В STL также содержатся функции бинарного поиска, которые работают за время O(log(n)). Сгенерируем новый диапазон данных, включающий лишь целочисленные значения, и напишем для него еще одну функцию print:

  const vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  auto print_int (opt_print(v));

12. Функция std::binary_search возвращает булевы значения и просто уведомляет о нахождении элемента, но при этом его не возвращает. Важно, чтобы контейнер, для которого мы выполняем поиск, был упорядочен, поскольку в противном случае бинарный поиск не будет выполнен корректно.

  bool contains_7 {binary_search(begin(v), end(v), 7)};

  cout << contains_7 << 'n';

13. Чтобы получить искомые элементы, нужно задействовать другие функции STL. Одной из них является функция std::equal_range. Она возвращает не один итератор для искомого элемента, а сразу пару. Первый итератор указывает на первый элемент, чье значение не меньше искомого, второй — на первый элемент, значение которого больше искомого. В нашем диапазоне данных, содержащем числа от 1 до 10, первый итератор указывает на значение 7, поскольку это первый элемент, чье значение не меньше 7. Второй итератор — на значение 8, так как это первый элемент, значение которого больше 7. При наличии в нашем диапазоне нескольких элементов 7 оба итератора представляли бы собой поддиапазон элементов.

  auto [lower_it, upper_it] (

    equal_range(begin(v), end(v), 7));

  print_int(lower_it);

  print_int(upper_it);

14. Если нужно получить только один итератор, то можно воспользоваться функциями std::lower_bound или std::upper_bound. Первая возвращает итератор на первый элемент, чье значение не меньше искомого, вторая — на первый элемент, чье значение больше искомого:

  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 <typename Iterator, typename T>

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

Во многих приложениях мы получаем из некоторого источника численные данные. Прежде чем у нас