sum
:
vector v {100, 400, 200 /*, ... */ };
int sum {0};
for (int i : v) { sum += i; }
cout << sum << '\n';
Поскольку эта задача является стандартной, для ее решения предусмотрен алгоритм STL:
cout << accumulate(begin(v), end(v), 0) << '\n';
В таком случае при создании вручную цикл занимает не намного больше места и прочесть его не сложнее, чем одну строку, в которой говорится, что она делает:
accumulate
. Во многих ситуациях, однако, может возникнуть неловкий момент: приходится читать состоящий из десятка строк цикл только затем, чтобы узнать, что он решает стандартную задачу Х
, вместо того чтобы увидеть одну строку кода, в которой используется стандартный алгоритм, чье имя явно указывает на то, какую задачу он решает, например accumulate
, copy
, move
, transform
или shuffle
.Основная идея заключается в том, чтобы предоставить множество алгоритмов, которые программисты могут использовать в повседневных задачах, не реализуя каждый раз повторно. Таким образом, разработчики могут просто применить готовый алгоритм и сконцентрироваться на решении новых задач вместо того, чтобы тратить время на проблемы, уже решенные средствами STL. Еще одно преимущество — корректность. При реализации одного и того же решения снова и снова возникает вероятность того, что в одной из попыток может появиться небольшая ошибка. В результате вы можете оказаться в неприятной ситуации, если коллега укажет на ошибку в коде во время обзора, а ведь вы вместо того, чтобы писать свой код, могли воспользоваться стандартным алгоритмом.
Еще одним важным качеством алгоритмов STL является эффективность. Многие из них предоставляют несколько специализированных реализаций одного алгоритма, по-разному решающих задачу, в зависимости от типа итератора, для которого они используются. Например, обнулить элементы вектора, содержащего целые числа, можно с помощью алгоритма
std::fill
. Поскольку итератор вектора может указать компилятору, что итерирует по непрерывной памяти, он может выбрать ту реализацию алгоритма std::fill
, которая задает процедуру C memset
. Если программист изменяет тип контейнера с vector
на list
, то алгоритм STL больше не может использовать процедуру memset
и должен итерировать по списку, чтобы обнулять элементы по одному. В том случае, если программист сам задействует процедуру memset
, алгоритм обнуления сможет работать только с векторами и массивами, поскольку другие структуры не хранят данные во фрагментах непрерывной памяти. В большинстве случаев не стоит изобретать велосипед, поскольку авторы библиотеки STL уже реализовали эти идеи и вам ничто не мешает воспользоваться их трудом.Подытожим. Алгоритмы STL предоставляют такие преимущества.
□Легкость сопровождения: по названию алгоритма сразу понятно, что именно он делает. Явные циклы зачастую труднее прочесть, и им нужно знать о том, какие именно структуры данных будут применяться, в отличие от стандартных алгоритмов.
□Правильность: библиотеку STL создавали и анализировали профессионалы, она используется и тестируется многими программистами, и вам, скорее всего, не удастся достичь той же степени правильности, если вы будете самостоятельно реализовывать сложные фрагменты алгоритмов.
□Эффективность: по умолчанию алгоритмы STL эффективны как минимум настолько же, насколько эффективны циклы, написанные вручную.
Большинство алгоритмов работают с итераторами. Принципы работы итераторов мы уже рассмотрели в главе 3. В настоящей главе сконцентрируемся на использовании алгоритмов STL для решения конкретных задач, чтобы понять, какие возможности они предоставляют. Разбор всех алгоритмов превратит эту книгу в очень скучный справочный материал по С++, а подобное руководство уже доступно для широкого круга читателей.
Самый лучший способ стать мастером STL заключается в том, чтобы всегда иметь справочный материал по С++ под рукой или хотя бы в закладках браузера. При решении какой-нибудь задачи каждый программист должен задуматься: «Существует ли в STL алгоритм для решения моей задачи?» — прежде чем писать код самостоятельно.
Хорошая и полная справка по C++ доступна по адресу http://en.cppreference.com/w/. Кроме того, этот материал можно скачать для чтения в режиме офлайн.
На собеседованиях хорошее знание алгоритмов STL зачастую считается показателем глубоких знаний языка С++.
Копируем элементы из одних контейнеров в другие
Большинство важных структур данных STL поддерживают итераторы. Это значит, что вы как минимум сможете получить итераторы с помощью функций
begin()
и end()
, которые указывают на полезные данные и позволяют итерировать по ним. Перебор всегда выглядит одинаково, независимо от того, по какой структуре данных выполняется.Можно получить итераторы для векторов, списков, двунаправленных очередей, ассоциативных массивов и т.д. С помощью адаптеров итераторов мы можем получить итераторы для файлов, а также стандартных потоков ввода и вывода. Более того, как вы видели в предыдущей главе, можно даже обернуть интерфейсы итераторов вокруг алгоритмов. Теперь, когда итераторы помогают нам получить доступ ко всему, можно объединить их с алгоритмами STL, которые принимают итераторы в качестве параметров.
На примере алгоритма
std::copy
можно легко понять, как итераторы помогают абстрагировать природу разных структур данных. Он просто копирует элементы из одного набора итераторов в итератор вывода. При использовании подобных алгоритмов не нужно знать о природе структуры данных, с которой мы работаем.
Как это делается
В этом примере мы разберем разные варианты алгоритма
std::copy
.
1. Сначала включим заголовочные файлы для всех структур данных, которые будем использовать. Кроме того, объявим, что задействуем пространство имен
std
:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
2. Далее будем использовать пары, содержащие целое число и строку. Чтобы красиво вывести их на экран, нужно перегрузить оператор потока
<<
:
namespace std {
ostream& operator<<(ostream &os, const pair&p)
{
return os << "(" << p.first << ", " << p.second << ")";
}
}
3. В функции
main
заполним вектор пар «число — строка» некоторыми значениями по умолчанию. Кроме того, объявим переменную map, связывающую численные и строковые значения:
int main()
{
vector> v {
{1, "one"}, {2, "two"}, {3, "three"},
{4, "four"}, {5, "five"}};
map m;
4. Теперь воспользуемся алгоритмом
std::copy_n
, чтобы скопировать три пары из вектора в ассоциативный массив. Поскольку векторы и ассоциативные массивы значительно отличаются друг от друга, нужно выполнить преобразование элементов вектора с помощью параметра адаптера insert_iterator
. Его предоставляет функция std::inserter
. Пожалуйста, всегда помните о том, что использование алгоритмов наподобие std::copy_n
в комбинации с итераторами вставки — наиболее обобщенный способ скопировать/вставить элементы в другие структуры данных, хотя и не самый быстрый. Зачастую эффективнее всего для вставки элементов применять функции-члены конкретных структур данных.
copy_n(begin(v), 3, inserter(m, begin(m)));
5. Выведем содержимое ассоциативного массива. На протяжении книги мы часто выводили на экран содержимое контейнера с помощью функции