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

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 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.