Это первая из серии статей об алгоритмах стандартной библиотеки шаблонов (STL). В этой первой статье будет рассмотрено подмножество неизменяемых алгоритмов - алгоритмов, которые выполняют задачи с элементами контейнера без внесения изменений в элементы. Функции в этой первой группе, которые я рассмотрю, включают for_each, count, count_if, min_element, max_element и minmax_element.
Функция for_each
Функция for_each используется для доступа к диапазону элементов в контейнере, чтобы выполнить некоторую задачу для каждого элемента. Классическим примером функции была печать каждого элемента в контейнере. Шаблон синтаксиса функции выглядит так:
for_each (начало диапазона, конец диапазона, функция);
Вот пример использования функции for_each для печати каждого элемента вектора:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
void buildVec(vector<int> &vec, int n) {
srand(time(0));
for (int i = 1; i <= n; i++) {
vec.push_back(rand() % 1000 + 1);
}
}
void printElement(int n) {
cout << n << " ";
}
int main()
{
vector<int> numbers;
buildVec(numbers, 20);
for_each(numbers.begin(), numbers.end(), printElement);
return 0;
}
Результат одного запуска этой программы:
928 722 270 403 832 495 100 728 993 75 442 376 482 169 368 563 978 610 432 374
Использование функции for_each для этой цели до некоторой степени было перехвачено циклом range for, особенно когда вы хотите получить доступ к каждому элементу в контейнере:
int main()
{
vector<int> numbers;
buildVec(numbers, 20);
for (const int number : numbers) {
cout << number << " ";
}
return 0;
}
Цикл range for использует итераторы под сценами точно так же, как их использует функция for_each.
Вот пример for_each, который отображает ключи и значения из контейнера map элементов:
void printNumber(pair<string, string> pr) {
cout << "Name: " << pr.first << ", number: "
<< pr.second << endl;
}
int main()
{
map<string, string> phoneList = {{"Jones", "2300"},
{"Smith", "2301"},
{"Brown", "2302"},
{"Green", "2303"}};
for_each(phoneList.begin(), phoneList.end(), printNumber);
return 0;
}
Результат этой программы:
Name: Brown, number: 2302 Name: Green, number: 2303 Name: Jones, number: 2300 Name: Smith, number: 2301
Поскольку многие варианты использования функции for_each заменены использованием цикла диапазона for, я продемонстрирую некоторые варианты использования for_each при изменении алгоритмов в следующей статье.
Функции count и count_if
Эти две функции подсчитывают количество указанных значений, найденных в контейнере. Вот шаблон синтаксиса для функции подсчета:
count (начало диапазона, конец диапазона, значение);
Функция возвращает количество вхождений value в контейнер. Вот пример использования вектора:
int main()
{
vector<int> numbers;
buildVec(numbers, 100);
for (const int number : numbers) {
cout << number << " ";
}
const int VALUE = 100;
cout << endl << endl;
int hundreds = count(numbers.begin(), numbers.end(), VALUE);
cout << "Number of 100 elements: " << hundreds << endl;
return 0;
}
Результат одного запуска этой программы:
4 93 27 2 72 87 84 9 33 68 9 67 89 10 47 5 4 75 68 11 47 1 44 64 59 44 55 87 59 99 97 76 62 42 6 63 33 38 15 29 48 77 20 4 66 100 48 66 82 67 14 61 87 80 25 69 71 90 62 1 84 18 36 11 15 51 40 87 94 31 3 34 11 62 25 74 65 38 42 48 23 91 26 13 6 44 33 51 48 34 82 100 30 93 5 39 78 68 13 9 Number of 100 elements: 2
Функция count_if подсчитывает элементы контейнера, соответствующие заданному критерию. Этот критерий может быть функциональным объектом или лямбда. Вот шаблон синтаксиса для count_if:
count_if (начало диапазона, остановка диапазона, функция);
В следующем примере подсчитывается количество элементов со значением выше 50 и отображаются результаты:
bool aboveFifty(int element) {
return element > 50;
}
int main()
{
vector<int> numbers;
buildVec(numbers, 100);
for (const int number : numbers) {
cout << number << " ";
}
const int VALUE = 100;
cout << endl << endl;
int aboveFiftyN = count_if(numbers.begin(), numbers.end(),
aboveFifty);
cout << "Number of elements above fifty: " << aboveFiftyN
<< endl;
return 0;
}
Вот еще один пример count_if с использованием лямбда-функции:
int main()
{
vector<int> numbers;
buildVec(numbers, 100);
int numOdds = count_if(numbers.begin(), numbers.end(),
[](int number) { return number % 2 != 0;});
cout << "Number of odd elements: " << numOdds << endl;
return 0;
}
Нахождение минимального и максимального значений в контейнере
Следующие две функции используются для поиска минимального и максимального элементов в контейнере. Первая функция min_element находит минимальное значение контейнера. Вот шаблон синтаксиса для этой функции:
min_element (начало диапазона, конец диапазона);
Функция возвращает итератор, а не значение, как показано в этом примере:
int main()
{
vector<int> numbers;
buildVec(numbers, 100);
for (const int number : numbers) {
cout << number << " ";
}
cout << endl << endl;
auto minValue = min_element(numbers.begin(), numbers.end());
cout << "The minimum value is: " << *minValue << endl;
return 0;
}
Функция max_element находит наибольшее значение в контейнере. Вот шаблон синтаксиса:
max_element (начало диапазона, конец диапазона);
Эта функция также возвращает итератор, как я демонстрирую ниже:
int main()
{
vector<int> numbers;
buildVec(numbers, 100);
for (const int number : numbers) {
cout << number << " ";
}
cout << endl << endl;
auto maxValue = max_element(numbers.begin(), numbers.end());
cout << "The minimum value is: " << *maxValue << endl;
return 0;
}
Третья функция в этой группе - это функция minmax_element. Эта функция возвращает pair, состоящее из наименьшего значения в контейнере в поле first и наибольшего значения в контейнере в поле second.
Шаблон синтаксиса для функции minmax_element:
minmax_element (начало диапазона, конец диапазона);
Вот пример использования функции minmax_element:
int main()
{
vector<int> numbers;
buildVec(numbers, 100);
for (const int number : numbers) {
cout << number << " ";
}
cout << endl << endl;
auto minMax = minmax_element(numbers.begin(), numbers.end());
cout << "The minimum element is: " << *(minMax.first) << endl;
cout << "The maximum element is: " << *(minMax.second)
<< endl;
return 0;
}
Результат одного запуска этой программы:
870 960 895 146 899 868 269 174 439 403 886 287 131 652 526 39 830 798 88 770 303 435 814 297 689 108 69 589 678 758 816 503 143 259 755 392 811 467 91 756 94 709 653 341 811 289 893 797 542 32 168 140 259 190 683 971 459 982 181 319 424 302 610 58 758 197 562 151 909 323 449 357 980 992 936 126 457 783 37 8 382 252 86 59 622 948 404 964 192 652 517 369 538 741 170 278 891 742 746 928 The minimum element is: 8 The maximum element is: 992
Обратите особое внимание на способ получения pair полей. Поскольку функция возвращает итератор, поля необходимо получить, поместив вызов поля в круглые скобки и затем применив оператор разыменования. Если не поместить вызов поля в круглые скобки, компилятор применит оператор разыменования только к имени pair, что является синтаксической ошибкой.
Алгоритмы, являющиеся функциями-членами
Большинство алгоритмов STL, как в этой статье, так и в функциях, которые я расскажу в следующих статьях, не всегда работают для каждого типа контейнера. Иногда алгоритм встраивается в контейнер как функция-член.
Возьмем, к примеру, функцию count. Если вы попытаетесь применить эту функцию к multimap, скажем, для подсчета количества ключей в мульти-карте, вы получите синтаксическую ошибку. Однако в классе multimap есть функция-член count, позволяющая это сделать. Вот пример:
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
multimap<string, string> words;
words.insert({"nail", "a finger or toe covering"});
words.insert({"nail", "a sharp metallic object"});
words.insert({"bark", "the noise made by a dog"});
words.insert({"bark", "the covering of a tree"});
int wordCount = words.count("bark");
cout << "Number of bark keys: " << wordCount << endl;
return 0;
}
Мораль этой истории заключается в том, что если вы пытались применить алгоритм к контейнеру в целом, и это не сработает, вы всегда должны проверять, найден ли алгоритм в функциях-членах контейнера, прежде чем пытаться написать свой собственный. Еще лучше сначала проверьте функции-члены, поскольку они обычно более эффективны, чем общий алгоритм.
Краткое описание функций в этой статье
Неизменяющие алгоритмы, которые я обсуждал в этой статье, используются либо для доступа к элементам контейнера (функция for_each), либо для возврата некоторой информации о контейнере (функции подсчета и функции минимума / максимума). В следующей статье я рассмотрю некоторые неизменяющиеся алгоритмы, которые используются для поиска в контейнере или для нахождения определенных значений в контейнере.
Спасибо, что прочитали эту статью, и пишите мне с комментариями и предложениями.
