Типичные алгоритмы поиска STL могут решить задачу обоими способами, поэтому было бы неплохо познакомиться с ними и узнать их характеристики. Данный раздел посвящен алгоритмам
std::find
(простой линейный поиск), std::equal_range
(бинарный поиск) и их вариациям.
Как это делается
В этом примере мы используем алгоритмы линейного и бинарного поиска на небольшом диапазоне данных.
1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен
std
:
#include
#include
#include
#include
#include
using namespace std;
2. Наш диапазон данных будет состоять из структур типа
city
, в которых хранится название города и количество проживающих в нем человек:
struct city {
string name;
unsigned population;
};
3. Алгоритмы поиска должны уметь сравнивать элементы друг с другом, поэтому перегружаем оператор
==
для экземпляров типа city
:
bool operator==(const city &a, const city &b) {
return a.name == b.name && a.population == b.population;
}
4. Кроме того, мы хотим выводить на экран экземпляры типа
city
, поэтому перегрузим оператор потока <<
:
ostream& operator<<(ostream &os, const city &city) {
return os << "{" << city.name << ", "
<< city.population << "}";
}
5. Поисковые функции, как правило, возвращают итераторы. Последние указывают на элемент, если таковой был найден, или же на конечный итератор заданного контейнера. В последнем случае нам нельзя получить доступ к такому итератору. Поскольку мы собираемся вывести на экран результаты поиска, реализуем функцию, которая возвращает другой объект функции, инкапсулирующий конечный итератор структуры данных. При использовании этого объекта функции для вывода объектов на экран он сравнит свой итератор-аргумент с конечным итератором, а затем выведет на экран либо сам элемент, либо строку
.
template
static auto opt_print (const C &container)
{
return [end_it (end(container))] (const auto &item) {
if (item != end_it) {
cout << *item << '\n';
} else {
cout << "\n";
}
};
}
6. Начнем с рассмотрения примера вектора, содержащего названия немецких городов:
int main()
{
const vector c {
{"Aachen", 246000},
{"Berlin", 3502000},
{"Braunschweig", 251000},
{"Cologne", 1060000}
};
7. С помощью этой вспомогательной функции создадим функцию, выводящую на экран экземпляры типа
city
и принимающую конечный итератор нашего вектора c
:
auto print_city (opt_print(c));
8. Используем алгоритм
std::find
для поиска элемента вектора, он сохранит элемент для города Кельна. Поначалу эта операция поиска выглядит бессмысленной, поскольку мы получаем именно тот элемент, который искали. Но ранее мы не знали его позицию в векторе, а функция find
возвращает нам и ее. Однако мы могли бы, например, создать такой перегруженный оператор ==
для структуры city
, который сравнивал бы только названия городов, не зная численности населения. Но это был бы пример плохого стиля программирования. На следующем шаге мы сделаем это по-другому.
{
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 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