C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц
C++17 STL Стандартная библиотека шаблонов читать книгу онлайн
С++ — объектно-ориентированный язык программирования, без которого сегодня немыслима промышленная разработка ПО. В этой замечательной книге описана работа с контейнерами, алгоритмами, вспомогательными классами, лямбда-выражениями и другими интересными инструментами, которыми богат современный С++. Освоив материал, вы сможете коренным образом пересмотреть привычный подход к программированию.
Преимущество издания — в подробном описании стандартной библиотеки шаблонов С++, STL. Ее свежая версия была выпущена в 2017 году. В книге вы найдете более 90 максимально реалистичных примеров, которые демонстрируют всю мощь STL. Многие из них станут базовыми кирпичиками для решения более универсальных задач.
Вооружившись этой книгой, вы сможете эффективно использовать С++17 для создания высококачественного и высокопроизводительного ПО, применимого в различных отраслях.
{
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
Во многих приложениях мы получаем из некоторого источника численные данные. Прежде чем у нас
