C++. Сборник рецептов - Д. Стефенс

11.1. Подсчет количества элементов в контейнере

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

Подсчитать количество элементов в контейнере можно при помощи функции-члена size или функции distance, определенной в заголовочном файле <algorithm>, как это делается в примере 11.1.

Пример 11.1. Подсчет количества элементов в контейнере

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

int main() {

 vector<int> v;

 v.push_back(0);

 v.push_back(1);

 v.push_back(2);

 cout << v.size() << endl;

 cout << distance(v.begin(), v.end()) << endl;

}

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

3

3

Функция-член size, которая возвращает количество элементов стандартного контейнера, является наилучшим решением в тех случаях, когда доступен объект контейнера. В примере 11.1 я также продемонстрировал применение функции distance, потому что при написании обобщенного программного кода обычно имеешь дело только с парой итераторов. Работая с итераторами, вы часто не знаете тип контейнера и не имеете доступа к его функциям-членам.

Функция distance, как и большинство алгоритмов STL, в действительности является шаблонной функцией. Поскольку тип аргумента шаблона может автоматически выводиться компилятором по аргументам функции, вам не надо его передавать как параметр шаблона. Конечно, при желании можно явно указать тип параметра шаблона, как это сделано ниже.

cout << distance<vector<int>::iterator>(v.begin(), v.end()) << endl;

Производительность функции 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, называется предикатом. Рассмотрим, например, поиск самого большого элемента в наборе пользовательских типов (пример 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(). Какой из двух типов функторов лучше использовать? В большинстве случаев объект-функция более эффективен, потому что большинство компиляторов могут легко его реализовать в виде встроенной функции.

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

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