C++. Сборник рецептов

Производительность функции distance зависит от типа используемого итератора. Время ее выполнения будет постоянным, если итератор ввода является итератором с произвольным доступом; в противном случае время ее работы будет линейным. (Концепция итератора рассматривается в рецепте 7.1.)

Смотри также

Рецепт 15.1.

11.2. Поиск наибольшего или наименьшего значения в контейнере

Проблема

Требуется найти максимальное или минимальное значение в контейнере.

Решение

Пример 11.2 показывает, как можно находить максимальные и минимальные элементы контейнера с помощью функций max_element и min_element, определенных в заголовочном файле <algorithm>. Эти функции возвращают итераторы,. которые ссылаются на первый элемент, имеющий самое большое или самое маленькое значение соответственно.

Пример 11.2. Поиск минимального или максимального элемента контейнера

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int getMaxInt(vector<int>& v) {
 return *max_element(v.begin(), v.end());
}
int getMinInt(vector<int>& v) {
 return *min_element(v.begin(), v.end());
}
int main() {
 vector<int> v;
 for (int i=10; i < 20; ++i) v.push_back(i);
 cout << 'min integer = ' << getMinInt(v) << endl;
 cout << 'max integer = ' << getMaxInt(v) << endl;
}

Программа примера 11.2 выдает следующий результат.

min integer = 10
max integer =19

Обсуждение

Вероятно, вы заметили, что выполняется разыменование значения, возвращаемого функциями min_element и max_element. Это делается по той причине, что указанные функции возвращают итераторы, а не сами значения, поэтому результат должен быть разыменован. Возможно, вы посчитаете, что такая операция разыменования создает небольшое неудобство, однако это позволяет избежать лишнего копирования возвращаемого значения. Это может быть особенно важно, когда копирование возвращаемого значения обходится дорого (например, если это большая строка).

Обобщенные алгоритмы стандартной библиотеки, несомненно, достаточно полезны, однако более важно уметь самому писать свои собственные обобщенные функции получения минимального и максимального значения, находящегося в контейнере. Допустим, вам нужно иметь одну функцию, которая возвращает минимальные и максимальные значения, модифицируя переданные ей по ссылке параметры вместо возвращения пары значений или какой-нибудь другой структуры. В примере 11.3 продемонстрировано, как это можно сделать.

Пример 11.3. Обобщенная функция, возвращающая минимальное и максимальное значения

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
template<class Iter_T, class Value_T>
void computeMinAndMax(Iter_T first, Iter_T last, Value_T& min, Value_T& max) {
 min = *min_element(first, last);
 max = *max_element(first, last);
}
int main() {
 vector<int> v;
 for (int i=10; i < 20; ++i) v.push_back(i);
 int min = -1;
 int max = -1;
 computeMinAndMax(v.begin(), v.end(), min, max);
 cout << 'min integer = ' << min << endl;
 cout << 'max integer = ' << max << endl;
}

В примере 11.3 я написал шаблон функции computeMinAndMax, которая принимает два параметра шаблона: один — это тип итератора, другой — тип минимальных и максимальных значений. Поскольку оба параметра шаблона являются также параметрами функции, компилятор C++ может догадаться, какие два отдельных типа (Iter_T и Value_T) используются, как это я продемонстрировал в рецепте 11.1. Это позволяет мне не указывать явно тип параметров шаблона, как это сделано ниже.

compute_min_max<vector<int>::iterator, int>(...)

При выполнении функций min_element и max_element используется оператор operator< для сравнения значений, на которые ссылаются итераторы. Это значит, что, если итератор ссылается на тип, который не поддерживает этот тип сравнения, компилятор выдаст сообщение об ошибке. Однако функции min_element и max_element можно также использовать с функтором сравнения, определенным пользователем, т.е. с указателем на функцию или с объектом-функцией.

Для функций min_element и max_element необходим специальный функтор, принимающий два значения (они имеют тип объектов, на которые ссылается итератор) и возвращающий значение типа Boolean, показывающее, является ли первое значение меньше, чем второе. Функтор, который возвращает значение типа Boolean, называется предикатом. Рассмотрим, например, поиск самого большого элемента в наборе пользовательских типов