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

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, называется предикатом. Рассмотрим, например, поиск самого большого элемента в наборе пользовательских типов (пример 11.4).

Пример 11.4. Поиск максимального элемента для пользовательских типов

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

struct Chessplayer {

 ChessPlayer(const char* name, int rating)

  : name_(name), rating_(rating) { }

 const char* name_;

 int rating_;

};

struct IsWeakerPlayer {

 bool operator()(const ChessPlayer& x, const ChessPlayer& y) {

 return x.rating_ < y.rating_;

};

int main() {

 ChessPlayer kasparov("Garry Kasparov", 2805);

 ChessPlayer anand("Viswanathan Anand", 2788);

 ChessPlayer topalov("Veselin Topalov", 2788);

 vector<ChessPlayer> v;

 v.push_back(kasparov);

 v.push_back(anand);

 v.push_hack(topalov);

 cout << "the best player is ";

 cout << max_element(v.begin(), v.end(), IsWeakerPlayer())->name_;

 cout << endl;

}

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

the best player is Garry Kasparov (лучший игрок - Гарри Каспаров)

Функторы

Многие STL-алгоритмы в качестве параметров используют определенные пользователем объекты-функции и указатели на функции. И те и другие называются функторами (functors). Иногда в литературе термин «объект-функция» используется как синоним термина «функтор», однако я использую термин «объект-функция» для обозначения только экземпляров класса или структур, которые перегружают operator(). Какой из двух типов функторов лучше использовать? В большинстве случаев объект-функция более эффективен, потому что большинство компиляторов могут легко его реализовать в виде встроенной функции.

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

Наконец, объекты-функции могут определяться внутри другой функции или класса. Указатели на функции приходится объявлять в области видимости пространства имен.

В примере 11.4 я показал, как в функции max_element можно использовать пользовательский предикат. Этот предикат является объектом-функцией IsWeakerPlayer.

Альтернативой пользовательскому предикату, показанному в примере 11.4, является перегрузка оператора operator< для структуры ChessPlayer. Это хорошо работает в определенных случаях, но предполагает, что самой важной является сортировка игроков по рейтингу. Может оказаться, что более распространенной является сортировка по именам. Поскольку в данном случае выбор метода сортировки может быть произвольным, я предпочитаю не определять оператор operator<.