Книга по C++, которую вы держите в руках, научит вас максимально эффективно использовать C++17. В ней представлены примеры написания кода, основанные на языке С++ и его стандартной библиотеке шаблонов (Standard Template Library, STL). Поскольку в рассматриваемых здесь примерах STL применяется по максимуму, об этой библиотеке стоит сказать подробнее.

С++ — мощный язык. Он позволяет скрывать сложные решения за простыми высокоуровневыми интерфейсами, но в то же время дает возможность писать низкоуровневый код, для которого важны высокая производительность и незначительное потребление ресурсов. Комитет ISO по стандартизации C++ старательно работает над улучшением стандарта С++.

Сегодняшний С++ (сам язык и библиотека шаблонов) предоставляет средства для работы со сложными структурами данных и алгоритмами, предлагает возможность управления ресурсами с помощью автоматических указателей, а также поддерживает лямбда-выражения, константные выражения, переносимые средства управления потоками для параллельного (конкурентного) программирования, регулярные выражения, генераторы случайных чисел, исключения, шаблоны с переменным количеством аргументов (эта часть языка C++, отвечающая за шаблонные типы, является полной по Тьюрингу!), определенные пользователями литералы, переносимые средства работы с файловой системой и многое другое. Такое количество возможностей делает С++ универсальным языком, который идеально подходит для реализации высококачественного и высокопроизводительного программного обеспечения, применимого в различных отраслях.

Однако многие разработчики С++ охотно изучают сам язык, а библиотеку STL переводят на задний план. Применение языка C++ без поддержки стандартной библиотеки зачастую приводит к тому, что программы выглядят так, будто написаны с использованием классов, а не с учетом современных подходов. Это печально, ведь подобное применение языка не дает задействовать всю его мощь.

В четвертом издании своей книги The C++ Programming Language («Язык программирования С++»), включающем сведения в том числе о С++11, Бьярн Страуструп (Bjarne Stroustrup) пишет: «Пожалуйста, помните, что эти возможности языка и стандартной библиотеки призваны поддержать приемы программирования, позволяющие разрабатывать качественное ПО. Для решения какой-то конкретной задачи их нужно использовать в комбинации друг с другом — как кирпичики из одного набора, — а не отдельно и изолированно друг от друга».

Именно этому посвящена настоящая книга и все приведенные в ней примеры. Они максимально приближены к реальной жизни, причем без ориентации на какие-либо внешние библиотеки — только на STL. Данное обстоятельство значительно упрощает работу, избавляя от утомительной настройки среды. Я очень надеюсь, что представленные здесь примеры привнесут вдохновение в вашу работу с языком С++. Возможно, вы обнаружите, что некоторые из них являются отличными стандартными кирпичиками для решения задач более высокого уровня. 

Глава 1 «Новые возможности С++17» посвящена новому функционалу, привнесенному стандартом С++17 в сам язык С++. В следующих главах мы уже сконцентрируемся на функционале STL.

Глава 2 «Контейнеры STL» содержит объяснение, как были улучшены разнообразные контейнеры структур данных, предоставляемые STL. После рассмотрения всей коллекции контейнеров мы более детально изучим новые дополнения к ним.

Глава 3 «Итераторы» дает описание итераторов, которые представляют собой очень важную абстракцию и служат «клеем» между алгоритмами STL и контейнерами в моменты их совместного использования. Мы разберем всю концепцию итераторов с нуля, чтобы узнать, как лучше всего применять их в наших программах.

Глава 4 «Лямбда-выражения» посвящена лямбда-выражениям, позволяющим задействовать некоторые интересные приемы программирования. Лямбда-выражения, чьему появлению в стандарте С++11 способствовали чистые функциональные языки программирования, в С++14 и С++17 получили новые возможности.

Глава 5 «Основы работы с алгоритмами STL» знакомит со стандартными алгоритмами STL и способами их применения. Эти алгоритмы легки в использовании, имеют высокую производительность, хорошо протестированы и универсальны. Научившись работать с ними, можно концентрироваться на решениях конкретных задач, а не тратить время на изобретение велосипеда.

Глава 6 «Сложные случаи использования алгоритмов STL» показывает, как объединять простые алгоритмы STL для создания более сложных без необходимости писать один и тот же код несколько раз. В рамках этой главы мы будем строго придерживаться принципов STL.

Глава 7 «Строки, классы потоков и регулярные выражения» содержит подробный обзор классов STL, необходимых для работы со строками, обобщенными потоками ввода/вывода и регулярными выражениями. Мы детально разберем каждый из этих элементов STL.

Глава 8 «Вспомогательные классы» рассказывает, как с помощью STL генерировать случайные числа, измерять время, управлять динамической памятью, изящно сообщать об ошибках, а также о многом другом. Мы рассмотрим очень полезные и переносимые вспомогательные классы, предоставляемые STL для решения подобных задач, и разберем новые классы, появившиеся в С++17.

Глава 9 «Параллелизм и конкуренция» демонстрирует существующие расширения С++, позволяющие реализовать параллелизм и конкуренцию, — эти темы стали очень важны с тех пор, как мы вступили в эру многоядерных процессоров. В С++11 и С++17 появились возможности, значительно облегчающие реализацию программ, работающих на нескольких ядрах и выполняющих задачи одновременно. В рамках данной главы мы и рассмотрим упомянутые концепции.

Глава 10 «Файловая система» показывает: несмотря на то что в STL всегда предоставлялась поддержка чтения отдельных файлов и управления ими, в С++17 появилось много новых, не зависящих от операционной системы способов работы с файловыми путями и просмотра каталогов. В рамках главы мы научимся пользоваться этим инструментарием.

Все примеры этой книги максимально просты и автономны. Их нетрудно скомпилировать и запустить, но, в зависимости от того, какими операционной системой и компилятором вы пользуетесь, эти действия могут различаться. Рассмотрим, как скомпилировать и запустить любой из примеров и на что нужно обратить особое внимание.

Эта книга не для вас, если раньше вы не писали программы на С++ и не компилировали их. Однако при условии, что вы уже имеете базовые сведения об этом языке, она идеально подойдет в качестве руководства по С++.

Кроме того, книга будет вам полезна, если вы узнали себя в одном из следующих описаний:

□ вы изучили основы С++, но теперь не знаете, что делать дальше, поскольку разница между вашими знаниями и знаниями профессионала — разработчика на С++ все еще велика;

□ вы хорошо знаете С++, но плохо ориентируетесь в STL;

□ вы знаете С++ по одному из старых стандартов, C++98, C++11 или C++14. Как бы давно вы ни использовали С++ в последний раз, книга познакомит вас со множеством новых возможностей STL. 

В издании вы найдете несколько заголовков, встречающихся чаще других («Как это делается» и «Как это работает»). В этих разделах даны четкие инструкции, как работать с примером.

В книге информация разного рода оформлена различными способами. Рассмотрим несколько вариантов оформления и их значение.

Код в тексте, имена баз данных, каталогов и файлов, а также расширения файлов, пути к файлам, ненастоящие (dummy) URL, пользовательский ввод и имена пользователей Twitter выделяются так: «Следующий шаг — редактирование файла build.properties».

Блок кода выглядит следующим образом:

Файлы с примерами кода для книги можно скачать по адресу https://github.com/PacktPublishing/Cpp17-STL-Cookbook. Для этого выполните следующие шаги.

1. Перейдите по указанному выше адресу.

2. Нажмите кнопку Clone or Download (Клонировать или скачать).

3. На открывшейся панели выберите ссылку Download ZIP (Скачать Zip).

В этой главе:

□ применение структурированных привязок (декомпозиции) для распаковки набора возвращаемых значений;

□ ограничение области видимости переменных в выражениях if и switch;

□ новые правила инициализатора с фигурными скобками;

□ разрешение конструктору автоматически вывести полученный тип класса шаблона;

□ упрощение принятия решений во время компиляции с помощью constexpr-if;

□ подключение библиотек, перечисленных в заголовочных файлах, с использованием встраиваемых переменных;

□ реализация вспомогательных функций с помощью выражений свертки.

Функциональность языка C++ значительно расширилась с выходом C++11, C++14 и недавней версии C++17. На текущий момент он совсем не похож на себя образца десятилетней давности. Стандарт С++ упорядочивает не только язык, но и STL.

В этой книге на большом количестве примеров показаны наилучшие способы использования возможностей STL. Но для начала в текущей главе мы сконцентрируемся на самых важных особенностях языка. Изучив их, вы сможете писать легко читаемый, удобный в сопровождении и выразительный код.

Мы рассмотрим, как получить доступ к отдельным элементам пар, кортежей и структур с помощью структурированных привязок и ограничить область видимости переменных благодаря новым возможностям по инициализации переменных внутри выражений if и switch. Синтаксические двусмысленности, появившиеся в C++11 из-за нового синтаксиса инициализатора с фигурными скобками, который выглядит так же, как синтаксис списков инициализаторов, были исправлены в новых правилах инициализатора с фигурными скобками. Точный тип экземпляра шаблонного класса может быть определен по аргументам, переданным его конструктору, а если разные специализации шаблонного класса выполняются в разном коде, то это легко выразить с помощью constexpr-if. Обработка переменного количества параметров в шаблонных функциях значительно упростилась благодаря новым выражениям свертки. Наконец, стало гораздо удобнее определять доступные глобально статические объекты в библиотеках, указанных в заголовочных файлах, благодаря новой возможности объявлять встраиваемые переменные, что ранее было выполнимо только для функций.

Отдельные примеры данной главы могут оказаться более интересными для тех, кто реализует библиотеки, нежели для тех, кто пишет приложения. Для полноты картины мы рассмотрим несколько свойств, но вам не обязательно разбираться со всеми примерами главы прямо сейчас, чтобы понять остальной материал этой книги. 

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

Максимальное ограничение области видимости переменных считается хорошим тоном. Иногда, однако, переменная должна получить какое-то значение, а потом нужно его проверить на соответствие тому или иному условию, чтобы продолжить выполнение программы. Для этих целей в С++17 была введена инициализация переменных в выражениях if и switch.

В C++11 появился новый синтаксис инициализатора с фигурными скобками {}. Он предназначен как для агрегатной инициализации, так и для вызова обычного конструктора. К сожалению, когда вы объединяли данный синтаксис с типом переменных auto, был высок шанс выразить не то, что вам нужно. В C++17 появился улучшенный набор правил инициализатора. В следующем примере вы увидите, как грамотно инициализировать переменные в С++17 и какой синтаксис при этом использовать.

Многие классы C++ обычно специализируются по типам, о чем легко догадаться по типам переменных, которые пользователь задействует при вызовах конструктора. Тем не менее до С++17 эти возможности не были стандартизированы. С++17 позволяет компилятору автоматически вывести типы шаблонов из вызовов конструктора.

 В коде, содержащем шаблоны, зачастую необходимо по-разному выполнять определенные действия в зависимости от типа, для которого конкретный шаблон был специализирован. В С++17 появились выражения constexpr-if, позволяющие значительно упростить написание кода в таких ситуациях.

 Несмотря на то, что в C++ всегда была возможность определить отдельные функции как встраиваемые, C++17 дополнительно позволяет определять встраиваемые переменные. Это значительно упрощает реализацию библиотек, размещенных в заголовочных файлах, для чего раньше приходилось искать обходные пути.

Как это делается

В этом примере мы создаем класс-пример, который может служить членом типичной библиотеки, размещенной в заголовочном файле. Мы хотим предоставить доступ к статическому полю класса через глобально доступный элемент класса и сделать это с помощью ключевого слова inline, что до появления C++17 было невозможно.

1. Класс process_monitor должен содержать статический член и быть доступным глобально сам по себе, что приведет (при включении его в несколько единиц трансляции) к появлению символов, определенных дважды:

// foo_lib.hpp

class process_monitor {

public:

  static const std::string standard_string

    {"some static globally available string"};

};

process_monitor global_process_monitor;

2. Теперь при попытке включить данный код в несколько файлов с расширением .cpp, а затем скомпилировать и связать их произойдет сбой на этапе связывания. Чтобы это исправить, добавим ключевое слово inline:

// foo_lib.hpp

class process_monitor {

public:

  static const inline std::string standard_string

    {"some static globally available string"};

};

inline process_monitor global_process_monitor;

Вуаля! Все работает!

Как это работает

Программы, написанные на C++, зачастую состоят из нескольких исходных файлов C++ (они имеют расширения .cpp или .cc). Они отдельно компилируются в модули/объектные файлы (обычно с расширениями .o). На последнем этапе все эти модули/объектные файлы компонуются в один исполняемый файл или разделяемую/статическую библиотеку.

На этапе связывания ошибкой считается ситуация, когда компоновщик встречает вхождение одного конкретного символа несколько раз. Предположим, у нас есть функция с сигнатурой int foo();. Если в двух модулях определены одинаковые функции, то какую из них считать правильной? Компоновщик не может просто подбросить монетку. Точнее, может, но вряд ли хоть один программист сочтет такое поведение приемлемым.

Традиционный способ создания функций, доступных глобально, состоит в объявлении их в заголовочном файле, впоследствии включенном в любой модуль С++, в котором их нужно вызвать. Эти функции будут определяться в отдельных файлах модулей. Далее они связываются с теми модулями, которые должны использовать эти функции. Данный принцип также называется правилом одного определения (one definition rule, ODR). Взгляните на рис. 1.1, чтобы лучше понять это правило.

Однако будь это единственный способ решения задачи, нельзя было бы создавать библиотеки, размещенные в заголовочных файлах. Такие библиотеки очень удобны, поскольку их можно включить в любой файл программы С++ с помощью директивы #include, и они мгновенно станут доступны. Для использования же библиотек, размещенных не в заголовочных файлах, программист также должен адаптировать сценарии сборки так, чтобы компоновщик связал модули библиотек и файлы своих модулей. Это неудобно, особенно для библиотек, содержащих только очень короткие функции.

В таких случаях можно применить ключевое слово inline — оно позволяет в порядке исключения разрешить повторяющиеся определения одного символа в разных модулях. Если компоновщик находит несколько символов с одинаковой сигнатурой, но они объявлены встраиваемыми, то он выберет первый и будет считать, что остальные символы имеют такое же определение. На программиста возложена ответственность за то, чтобы все одинаковые встраиваемые символы были определены абсолютно идентично.

Что касается нашего примера, компоновщик найдет символ process_monitor::standard_string в каждом модуле, который включает файл foo_lib.hpp. Без ключевого слова inline он не будет знать, какой символ выбрать, так что прекратит работу и сообщит об ошибке. Это же верно и для символа global_process_monitor. Как же выбрать правильный символ?

При объявлении обоих символов с помощью ключевого слова inline компоновщик просто примет первое вхождение символа и отбросит остальные.

До появления C++17 единственным явным способом сделать это было предоставление символа с помощью дополнительного файла модуля C++, что заставляло пользователей библиотеки включать данный файл на этапе компоновки.

Ключевое слово inline по традиции выполняет и другую задачу. Оно указывает компилятору, что он может избавиться от вызова функции, взяв ее реализацию и поместив в то место, из которого функция вызывается. Таким образом, вызывающий код содержит на один вызов функции меньше — считается, что такой код работает быстрее. Если функция очень короткая, то полученный ассемблерный код также будет короче (предполагается, что количество инструкций, которые выполняют вызов функции, сохранение и восстановление стека и т.д., превышает количество строк с полезной нагрузкой). Если же встраиваемая функция очень длинная, то размер бинарного файла увеличится, а это не ускоряет работу программы. Поэтому компилятор будет использовать ключевое слово inline как подсказку и может избавиться от вызовов функций, встраивая их тело. Он даже может встроить отдельные функции, которые программист не объявлял встраиваемыми.

Дополнительная информация

Одним из способов решения такой задачи до появления C++17 было создание функции static, которая возвращает ссылку на объект static:

class foo {

public:

  static std::string& standard_string() {

    static std::string s {"some standard string"};

    return s;

  }

};

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

Проблему можно решить еще одним способом: сделав класс foo шаблонным и воспользовавшись преимуществами шаблонов.

В C++17 оба варианта становятся неактуальны. 

 Начиная с C++11, в языке появились пакеты параметров для шаблонов с переменным количеством аргументов. Такие пакеты позволяют реализовывать функции, принимающие переменное количество параметров. Иногда эти параметры объединяются в одно выражение, чтобы на его основе можно было получить результат работы функции. Решение этой задачи значительно упростилось с выходом C++17, где появились выражения свертки.

Как это делается

Реализуем функцию, которая принимает переменное количество параметров и возвращает их сумму.

1. Сначала определим ее сигнатуру:

template <typename Ts>

auto sum(Ts ts);

2. Теперь у нас есть пакет параметров ts, функция должна распаковать все параметры и просуммировать их с помощью выражения свертки. Допустим, мы хотим воспользоваться каким-нибудь оператором (в нашем случае +) вместе с ..., чтобы применить его ко всем значениям пакета параметров. Для этого нужно взять выражение в скобки:

template <typename Ts>

auto sum(Ts ts)

{

  return (ts + ...);

}

3. Теперь можно вызвать функцию следующим образом:

int the_sum {sum(1, 2, 3, 4, 5)}; // Значение: 15

4. Она работает не только с целочисленными типами; можно вызвать ее для любого типа, реализующего оператор +, например std::string:

std::string a {"Hello "};

std::string b {"World"};

std::cout << sum(a, b) << '\n'; // Вывод: Hello World

Как это работает

Только что мы написали код, в котором с помощью простой рекурсии бинарный оператор (+) применяется к заданным параметрам. Как правило, это называется сверткой. В C++17 появились выражения свертки, которые помогают выразить ту же идею и при этом писать меньше кода.

Подобное выражение называется унарной сверткой. C++17 позволяет применять к пакетам параметров свертки следующие бинарные операторы: +, –, *, /, %, ^, &, |,

=, <, >, <<, >>, +=, –=, *=, /=, %=, ^=, &=, |=, <<=, >>=, ==, !=, <=, >=, &&, ||, ,, .*, –>*.

Кстати, в нашем примере кода неважно, какую использовать конструкцию, (ts + …) или (… + ts);. Они обе работают так, как нужно. Однако между ними есть разница, которая может иметь значение в других случаях: если многоточие … находится с правой стороны оператора, то такое выражение называется правой сверткой. Если же оно находится с левой стороны, то это левая свертка.

В нашем примере с суммой левая унарная свертка разворачивается в конструкцию 1+(2+(3+(4+5))), а правая унарная свертка развернется в (((1+2)+3)+4)+5. В зависимости от того, какой оператор используется, могут проявиться нюансы. При добавлении новых чисел ничего не меняется.

Дополнительная информация

Если кто-то вызовет функцию sum() и не передаст в нее аргументы, то пакет параметров произвольной длины не будет содержать значений, которые могут быть свернуты. Для большинства операторов такая ситуация считается ошибкой (но для некоторых — нет, вы увидите это чуть позже). Далее нужно решить, генерировать ошибку или же вернуть конкретное значение. Очевидным решением будет вернуть значение 0.

Это делается так:

template <typename ... Ts>

auto sum(Ts ... ts)

{

  return (ts + ... + 0);

}

Таким образом, вызов sum() возвращает значение 0, а вызов sum(1, 2, 3) — значение (1+(2+(3+0))). Подобные свертки с начальным значением называются бинарными.

Кроме того, обе конструкции, (ts + ... + 0) и (0 + ... + ts), работают как полагается, но такая бинарная свертка становится правой или левой соответственно. Взгляните на рис. 1.2.

При использовании бинарных сверток для решения такой задачи, когда аргументы отсутствуют, очень важны нейтральные элементы — в нашем случае сложение любого числа с нулем ничего не меняет, что делает 0 нейтральным элементом. Поэтому можно добавить 0 к любому выражению свертки с помощью операторов + или –. Если пакет параметров пуст, это приведет к возврату функцией значения 0. С математической точки зрения это правильно. С точки зрения реализации нужно определить, что именно является правильным в зависимости от наших требований.

Тот же принцип применяется и к умножению. Здесь нейтральным элементом станет 1:

template <typename Ts>

auto product(Ts ts)

{

  return (ts * ... * 1);

}

Результат вызова product(2, 3) равен 6, а результат вызова product() без параметров равен 1.

В логических операторах И (&&) и ИЛИ (||) появились встроенные нейтральные элементы. Свертка пустого пакета параметров с оператором && заменяется на true, а свертка пустого пакета с оператором || — на false.

Еще один оператор, для которого определено значение по умолчанию, когда он используется для пустых пакетов параметров, — это оператор «запятая» (,), заменяемый на void().

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

Соотнесение диапазонов и отдельных элементов

Как насчет функции, которая определяет, содержит ли диапазон хотя бы одно из значений, передаваемых в пакете параметров с переменной длиной:

template <typename R, typename ... Ts>

auto matches(const R& range, Ts ... ts)

{

  return (std::count(std::begin(range), std::end(range), ts) + ...);

}

Вспомогательная функция использует функцию std::count из библиотеки STL. Она принимает три параметра: первые два представляют собой начальный и конечный итераторы того или иного итерабельного промежутка, а третий параметр — это значение, с которым будут сравниваться все элементы промежутка. Метод std::count возвращает количество всех элементов внутри диапазона, равных третьему параметру.

В нашем выражении свертки мы всегда передаем в функцию std::countначальный и конечный итераторы одного диапазона параметров. Однако в качестве третьего параметра мы всякий раз отправляем один параметр из пакета. В конечном счете функция складывает все результаты и возвращает их вызывающей стороне.

Ее можно использовать следующим образом:

std::vector<int> v {1, 2, 3, 4, 5};

matches(v, 2, 5);                  // возвращает 2

matches(v, 100, 200);              // возвращает 0

matches("abcdefg", 'x', 'y', 'z'); // возвращает 0

matches("abcdefg", 'a', 'd', 'f'); // возвращает 3

Как видите, вспомогательная функция matches довольно гибкая — ее можно вызвать для векторов или даже строк. Она также будет работать для списка инициализаторов, контейнеров std::list, std::array, std::set и прочих!

Проверка успешности вставки нескольких элементов в множество

Напишем вспомогательную функцию, которая добавляет произвольное количество параметров в контейнер std::set и возвращает булево значение, показывающее, успешно ли прошла операция:

template <typename T, typename ... Ts>

bool insert_all(T &set, Ts ... ts)

{

  return (set.insert(ts).second && ...);

}

Как же это работает? Функция insert контейнера std::set имеет следующую сигнатуру:

std::pair<iterator, bool> insert(const value_type& value);

Документация гласит, что при попытке вставить элемент функция insert вернет пару из iterator и переменной bool. Если вставка пройдет успешно, значение переменной будет равно true. Итератор же в этом случае укажет на новый элемент множества, а в противном случае — на существующий элемент, который помешал вставке.

Наша вспомогательная функция после вставки обращается к полю .second. Оно содержит переменную bool, которая показывает, была ли вставка успешной. Если все полученные пары имеют значение true, то все вставки прошли успешно. Свертка объединяет все результаты вставки с помощью оператора && и возвращает результат.

Контейнер можно использовать следующим образом:

std::set<int> my_set {1, 2, 3};

insert_all(my_set, 4, 5, 6); // Возвращает true

insert_all(my_set, 7, 8, 2); // Возвращает false, поскольку 2 уже присутствует

Обратите внимание: если мы попробуем вставить, например, три элемента, но в процессе окажется, что второй элемент вставить нельзя, свертка && ... досрочно прекратит работать и оставшиеся элементы не будут добавлены:

std::set<int> my_set {1, 2, 3};

insert_all(my_set, 4, 2, 5); // Возвращает false

// теперь множество содержит значения {1, 2, 3, 4}, без 5!

Проверка попадания всех параметров в заданный диапазон

Поскольку можно убедиться, что одна из переменных находится в конкретном диапазоне, можно сделать то же самое для нескольких переменных с помощью выражений свертки:

template <typename T, typename Ts>

bool within(T min, T max, Ts ts)

{

  return ((min <= ts && ts <= max) && ...);

}

Выражение (min <= ts && ts <= max) определяет, находится ли каждый элемент пакета параметров в диапазоне между min и max (включаяmin и max). Мы выбрали оператор &&, чтобы свести все результаты булева типа к одному, который имеет значение true только в том случае, если все отдельные результаты имеют такое же значение.

Это работает следующим образом:

within( 10, 20, 1, 15, 30);     // --> false

within( 10, 20, 11, 12, 13);    // --> true

within(5.0, 5.5, 5.1, 5.2, 5.3) // --> true

Что интересно: эта функция очень гибкая, поскольку единственным требованием, которое она предъявляет к типам, служит возможность сравнения экземпляров с помощью оператора <=. Это требование выполняется, например, типом std::string:

std::string aaa {"aaa"};

std::string bcd {"bcd"};

std::string def {"def"};

std::string zzz {"zzz"};

within(aaa, zzz, bcd, def); // --> true

within(aaa, def, bcd, zzz); // --> false

Отправка нескольких элементов в вектор

Кроме того, вы можете написать вспомогательную функцию, которая не обобщает никаких результатов, но обрабатывает несколько действий одного вида. Такими действиями могут быть вставки элементов в контейнер std::vector, поскольку они не возвращают никаких результатов (функция std::vector::insert() сообщает об ошибке, генерируя исключения):

template <typename T, typename ... Ts>

void insert_all(std::vector<T> &vec, Ts ... ts)

{

  (vec.push_back(ts), ...);

}

int main()

{

  std::vector<int> v {1, 2, 3};

  insert_all(v, 4, 5, 6);

}

Обратите внимание: мы используем оператор «запятая» (,), чтобы распаковать пакет параметров в отдельные вызовы vec.push_back(...), не выполняя свертку для самого результата. Эта функция также хорошо работает в отношении пустого пакета параметров, поскольку оператор «запятая» имеет неявный нейтральный элемент, void(), который означает «ничего не делать». 

В этой главе:

□ использование идиомы erase-remove для контейнера std::vector;

□ удаление элементов из неотсортированного контейнера std::vector за время O(1);

□ получение доступа к экземплярам класса std::vector быстрым или безопасным способом;

□ поддержка экземпляров класса std::vector в отсортированном состоянии;

□ вставка элементов в контейнер std::map: эффективно и в соответствии с условиями;

□ исследование новой семантики подсказок для вставки элементов с помощью метода std::map::insert;

□ эффективное изменение ключей элементов std::map;

□ применение контейнера std::unordered_map для пользовательских типов;

□ отбор повторно встречающихся слов из пользовательского ввода и вывод их на экран в алфавитном порядке с помощью контейнера std::set;

□ реализация простого ОПН-калькулятора с использованием контейнера std::stack;

□ подсчет частоты встречаемости слов с применением контейнера std::map;

□ реализация вспомогательного инструмента для поиска очень длинных предложений в текстах с помощью std::multimap;

□ реализация личного списка текущих дел с помощью std::priority_queue.

В стандартной библиотеке С++ появилось большое количество стандартных контейнеров. Контейнер всегда содержит набор данных или объектов. Достоинство контейнеров в том, что их можно применять практически для всех объектов, поэтому нужно только выбрать правильные контейнеры для конкретного приложения. STL предоставляет стеки, автоматически увеличивающиеся векторы, ассоциативные массивы и т.д. Таким образом, можно сконцентрироваться на нашем приложении и не изобретать велосипед. В целом каждому программисту С++ не повредит знакомство со всеми контейнерами.

Все контейнеры, предоставляемые STL, можно разделить на такие категории, которые подробнее рассматриваются в следующем разделе:

□ непрерывные хранилища;

□ списки;

□ деревья поиска;

□ хеш-таблицы;

□ адаптеры контейнеров.

Многие программисты-новички узнают о существовании класса std::vector, который в основном работает как автоматически увеличивающийся массив, и останавливаются на этом. Далее они лишь ищут в документации сведения о том, как решать конкретные задачи, например удалять элементы. Такого рода использование контейнеров STL не задействует и сотой доли их возможностей в создании чистого, удобного в сопровождении и быстрого кода.

Текущий раздел посвящен вопросу удаления элементов из середины объекта вектора. Если элемент исчезает из вектора и при этом он находился между другими элементами, то все элементы, стоящие справа от него, должны сместиться на одну позицию влево (в результате время выполнения операции составляет O(n)). Многие начинающие программисты будут решать задачу с помощью цикла, ведь это так просто. К сожалению, при этом они, скорее всего, упустят потенциальные возможности оптимизации. В конечном счете цикл, написанный вручную, не быстрее и не читабельнее, чем способ решения задачи средствами STL, которые мы еще рассмотрим далее.

Как это делается

В этом примере мы наполним объект класса std::vector целыми числами, а затем выбросим из него конкретные элементы. При этом мы воспользуемся корректным способом удаления нескольких элементов из вектора.

1. Конечно, прежде чем начинать что-то делать, включим некоторые заголовочные файлы:

#include <iostream>

#include <vector>

#include <algorithm>

2. Далее мы объявляем, что будем использовать пространство имен std, чтобы поменьше печатать:

using namespace std;

3. Теперь создадим вектор, состоящий из целых чисел, и заполним его некими числами:

int main()

{

  vector<int> v {1, 2, 3, 2, 5, 2, 6, 2, 4, 8};

4. Удалим некоторые элементы. Что именно? В нашем примере много значений 2, удалим их:

  const auto new_end (remove(begin(v), end(v), 2));

5. Что интересно, это был лишь первый шаг. Вектор все еще имеет прежний размер. Мы укоротим его по-настоящему, написав такую строку:

  v. erase(new_end, end(v));

6. Остановимся и выведем на экран содержимое вектора, а затем продолжим:

  for (auto i : v) {

    cout << i << ", ";

  }

  cout << '\n';

7. Теперь удалим целый класс элементов, а не конкретные значения. Для этого сначала определим функцию-предикат, которая принимает число в качестве параметра и возвращает значение true, если переданное число нечетное:

  const auto odd ([](int i) { return i % 2 != 0; });

8. Используем функцию remove_if, передавая ей значения с помощью функции-предиката. Вместо удаления элементов за два шага теперь делаем это за один:

  v. erase(remove_if(begin(v), end(v), odd), end(v));

9. Мы удалили все нечетные элементы, но емкость вектора все еще соответствует старым десяти элементам. На последнем шаге мы сократим эту емкость до реального размера вектора. Обратите внимание: это может привести к тому, что код обслуживания вектора выделит новый фрагмент памяти, который будет иметь соответствующий размер, и переместит все элементы из старого фрагмента в новый:

  v.shrink_to_fit();

10. Теперь выведем на экран содержимое вектора после второго раунда удаления элементов и закончим с примером:

  for (auto i : v) {

    cout << i << ", ";

  }

  cout << '\n';

}

11. Скомпилировав и запустив программу, вы увидите следующие строки, показывающие результат выполнения операций по удалению элементов:

$ ./main

1, 3, 5, 6, 4, 8,

6, 4, 8,

Как это работает 

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

Код, удаляющий все значения 2 из вектора, выглядел так:

const auto new_end (remove(begin(v), end(v), 2));

v.erase(new_end, end(v));

Функции std::begin и std::end принимают в качестве параметра экземпляр вектора и соответственно возвращают итераторы, которые указывают на первый элемент и на позицию, находящуюся после последнего элемента, как показано на рис. 2.1.

После того как мы передадим их и значение 2 функции std::remove, она переместит все значения, кроме 2, вперед точно так же, как если бы мы сделали это вручную с помощью цикла. С первого взгляда рисунок может показаться непонятным. На шаге 2 все еще можно найти значение 2, а сам вектор должен был стать короче, поскольку содержал четыре таких значения. Вместо этого значения 4 и 8, присутствовавшие в оригинальном массиве, встречаются дважды. Что происходит?

Рассмотрим только элементы, находящиеся в рамках диапазона от итератора begin, показанного на рис. 2.1, до итератора new_end. Элемент, на который указывает итератор new_end, является первым элементом за пределами диапазона, поэтому он не включается. Сконцентрировавшись на заданном участке (в нем содержатся элементы от 1 до 8 включительно), мы понимаем, что перед нами корректный диапазон, из которого удалены все значения 2.

Здесь вступает в дело функция erase: мы должны указать вектору, что все элементы между итераторами new_end и end больше к нему не относятся. Вектор легко с этим справится, поскольку может просто перевести конечный итератор в позицию, обозначенную new_end. Обратите внимание: итератор new_end является возвращаемым значением вызова std::remove, следовательно, можно просто им воспользоваться.

 Заметьте: вектор выполнил больше манипуляций, нежели просто передвинул внутренний указатель. Если бы вектор состоял из более сложных объектов, то ему пришлось бы вызвать деструкторы для всех удаляемых элементов.

В конечном счете вектор выглядит так, как показано в шаге 3: считается, что его размер уменьшился. Старые элементы, лежащие вне диапазона, все еще находятся в памяти.

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

В шаге 8 мы определили функцию-предикат и использовали ее вместе с функцией std::remove_if. Это работает, поскольку независимо от того, какой итератор вернет функция, его можно будет безопасно применить в функции вектора erase. Если мы не найдем нечетных элементов, то функция std::remove_if не выполнит никаких действий и вернет конечный итератор. Далее вызов наподобие v.erase(end, end); также ни к чему не приведет.

Дополнительная информация

Функция std::remove работает и для других контейнеров. При ее вызове для std::array обратите внимание, что массив не поддерживает вызов функции erase из второго шага, поскольку вы не можете изменять его размер автоматически. Несмотря на то что функция std::remove, по сути, лишь перемещает элементы и не удаляет их, она пригодна для структур данных наподобие массивов, которые не могут изменять размер. При работе с массивом можно переписать значения после конечного итератора некоторыми граничными значениями, например '\0' для строк.

Удаление элементов из середины вектора занимает O(n) времени. При этом образовавшийся промежуток должен быть заполнен: все элементы, стоящие после него, перемещаются на одну позицию влево.

Такое перемещение с сохранением порядка может оказаться затратным по времени, если перемещаемые элементы сложны и/или велики и содержат много объектов. Если порядок сохранять не требуется, можно оптимизировать процесс, как показано в этом разделе.

Как это делается

В этом примере мы заполним экземпляр класса std::vector некими числами, а затем реализуем функцию быстрого удаления, которая удаляет любой элемент из вектора за время O(1).

1. Сначала включим необходимые заголовочные файлы:

#include <iostream>

#include <vector>

#include <algorithm>

2. Далее определим функцию main, где создадим вектор, заполненный числами:

int main()

{

  std::vector<int> v {123, 456, 789, 100, 200};

3. Очередной шаг заключается в том, чтобы удалить значение с индексом 2 (отсчет начинается с нуля, следовательно, это будет третье число, 789). Функция, которую мы будем использовать для данной задачи, еще не реализована. Мы сделаем это спустя несколько шагов. Затем выведем содержимое вектора:

  quick_remove_at(v, 2);

  for (int i : v) {

    std::cout << i << ", ";

  }

  std::cout << '\n';

4. Теперь удалим еще один элемент. Это будет значение 123. Предположим, что не знаем его индекс. Как следствие, нужно вызвать функцию std::find, которая принимает диапазон (наш вектор) и значение, а затем ищет позицию значения. После этого она возвращает итератор, указывающий на значение 123. Мы используем его для той же функции quick_remove_at, но на сей раз применим перегруженную версию предыдущей, которая принимает в качестве параметров итераторы. Данная функция также не реализована.

quick_remove_at(v, std::find(std::begin(v), std::end(v), 123));

  for (int i : v) {

    std::cout << i << ", ";

  }

  std::cout << '\n';

}

5. Нам осталось реализовать только две функции quick_remove_at. Этим и займемся. (Обратите внимание: они должны быть как минимум объявлены до функции main. Так что просто определим их там.)

Обе функции принимают ссылку на вектор, содержащий значения некоторого типа (в нашем случае это int), так что мы не решаем за пользователя, какой тип вектора он задействует. Для нас это будет вектор, содержащий значения типа T. Первая функция quick_remove_at принимает значения индекса, которые представляют собой числа, вследствие чего ее интерфейс выглядит следующим образом:

template <typename T>

void quick_remove_at(std::vector<T> &v, std::size_t idx)

{

6. Сейчас перейдем к самому главному — быстрому удалению элементов. При этом нужно постараться не перемещать слишком большого количества оставшихся элементов. Во-первых, просто возьмем значение последнего элемента вектора и запишем его на место элемента, который должен быть удален. Во-вторых, отбросим последний элемент. Вот и все, только два шага. Мы добавим в этот код небольшую проверку безопасности. Если значение индекса очевидным образом выходит за пределы вектора, мы не станем ничего делать. В противном случае код будет давать сбой для пустого вектора.

  if (idx < v.size()) {

    v[idx] = std::move(v.back());

    v.pop_back();

  }

}

7. Другая реализация метода quick_remove_at работает аналогично. Вместо того чтобы принимать численный индекс, она принимает итератор для вектора std::vector<T>. Получить такой обобщенный тип несложно, поскольку для контейнеров STL уже определены подобные типы.

template <typename T>

void quick_remove_at(std::vector<T> &v,

                     typename std::vector<T>::iterator it)

{

8. Теперь получим доступ к значению, на которое указывает итератор. Как и в другой функции, перепишем его с помощью последнего элемента вектора. Поскольку мы работаем не с числовым индексом, а с итератором, следует выполнять более аккуратную проверку на безопасность. Если итератор указывает на специальную конечную позицию, то разыменовывать его нельзя.

  if (it != std::end(v)) {

9. Внутри этого блока if делаем то же самое, что и раньше: переписываем значение удаляемого элемента с последней позиции, а затем отбрасываем последний элемент вектора:

    *it = std::move(v.back());

    v.pop_back();

  }

}

10. Вот и все. Компиляция и запуск программы дадут следующий результат:

$ ./main

123, 456, 200, 100,

100, 456, 200,

Как это работает

Функция quick_remove_at довольно быстро удаляет элементы и затрагивает не слишком много других элементов. Это относительно хитроумно. По сути, она ставит последний элемент вектора на место удаляемого элемента. Несмотря на то, что последний элемент не связан с выбранным элементом, он находится в особой позиции: удаление последнего элемента занимает мало времени! Вам нужно лишь сократить размер вектора на одну позицию, и на этом все. На данном шаге элементы не перемещаются. Представить происходящее поможет рис. 2.2.

Оба шага в коде примера выглядят следующим образом:

v.at(idx) = std::move(v.back());

v.pop_back();

В версии с итераторами шаги выглядят примерно так же:

*it = std::move(v.back());

v.pop_back();

По логике, мы меняем местами выбранный и последний элементы. Но в коде мы не делаем этого, а лишь перемещаем последний элемент на место выбранного. Почему? Если бы мы действительно меняли местами элементы, нам пришлось бы сохранить выбранный элемент во временной переменной, переместить последний элемент на место выбранного, а затем сохранить временное значение в последней позиции. Это выглядит бессмысленно, поскольку мы все равно будем удалять последний элемент.

Ладно, значит, менять элементы местами бесполезно, и односторонняя перезапись нам больше подходит. Убедившись в этом, мы можем решить, что такое действие можно выполнить просто с помощью операции *it = v.back();, верно? Да, совершенно верно. Но представьте хранение на каждой позиции очень больших строк или даже другого вектора или ассоциативного массива — в такой ситуации эта небольшая операция присваивания приведет к очень затратной операции копирования. Вызов std::move, вставленный посередине (между = и v.back()), ускоряет выполнение кода. В случае со строками элемент вектора указывает на большую строку в куче. Нам не нужно ее копировать. Вместо этого при перемещении строки адрес исходной строки меняется на адрес места назначения. Исходный элемент остается прежним, но сам по себе он бесполезен, что нас устраивает, поскольку мы все равно его удаляем. 

 Контейнер std::vector, возможно, является наиболее широко используемым контейнером STL, поскольку хранит данные аналогично массивам, но работать с ним гораздо удобнее. Однако неверное обращение к элементам вектора может быть опасным. Если вектор содержит 100 элементов, а наш код пытается получить доступ к элементу с индексом 123, то это, очевидно, плохо. Такая программа в лучшем случае даст сбой, поскольку подобное поведение явно указывает на ошибку в коде! Если программа не дает сбой, то мы наверняка заметим ее странное поведение, что куда хуже, чем аварийно завершившая программа. Опытный программист может добавить проверки перед непосредственным обращением к элементу вектора по индексу. Такие проверки не повышают читабельность кода, и многие разработчики не знают, что контейнер std::vector уже поддерживает подобные встроенные проверки!

Массивы и векторы не сортируются самостоятельно. Если нам потребуется такая возможность, мы всегда можем воспользоваться структурами данных, которые предоставляют ее автоматически. Контейнер std::vector идеально подходит для нашего случая, ведь добавлять в него новые элементы в порядке сортировки несложно и удобно.

Иногда нужно заполнить ассоциативный массив парами «ключ — значение», и при выполнении данной задачи можно столкнуться с двумя ситуациями.

1.  Заданный ключ не существует. В этом случае создается новая пара «ключ — значение».

2.  Заданный ключ уже существует. В такой ситуации берем существующий элемент и модифицируем его.

 Поиск элементов в контейнере std::map занимает время O(log(n)). То же касается вставки новых элементов, поскольку позицию, на которую нужно добавить новый элемент, тоже необходимо найти. Простая вставка М новых элементов займет время O(M * log(n)).

Чтобы операция была более эффективной, функция вставки контейнера std::map принимает необязательный параметр, представляющий собой подсказку для вставки. Это, по сути, итератор, который указывает на место, близкое к будущей позиции вставляемого элемента. Если подсказка корректна, то амортизированное время вставки составит O(1).

Как это делается

В этом примере мы вставим несколько элементов в контейнер std::map и используем подсказки для вставки, чтобы снизить количество операций поиска.

1. Мы преобразуем строки в числа, поэтому включим заголовочные файлы для std::map и std::string:

#include <iostream>

#include <map>

#include <string>

2. Далее создаем ассоциативный массив, в котором содержатся некие символы:

int main()

{

  std::map<std::string, size_t> m {{"b", 1}, {"c", 2}, {"d", 3}};

3. Теперь вставим несколько элементов и для каждого из них используем подсказку для вставки. Поскольку изначально ее у нас нет, выполним первую операцию вставки, указывая на конечный итератор ассоциативного массива:

  auto insert_it (std::end(m));

4. Вставим элементы в порядке, обратном алфавитному, используя имеющуюся у нас подсказку для вставки, а затем повторно инициализируем ее значением, которое возвращает функция insert. Следующий элемент будет вставлен прямо перед подсказкой:

  for (const auto &s : {"z", "y", "x", "w"}) {

    insert_it = m.insert(insert_it, {s, 1});

  }

5. Чтобы продемонстрировать, как не нужно решать задачу, вставим строку, которая окажется с левого края ассоциативного массива, но зададим для нее неправильную подсказку, указывающую на крайнюю правую позицию ассоциативного массива — end:

  m.insert(std::end(m), {"a", 1});

6. Наконец, просто выведем на экран полученный результат.

  for (const auto & [key, value] : m) {

    std::cout << "\"" << key << "\": " << value << ", ";

  }

  std::cout << '\n';

}

7. Скомпилировав и запустив программу, мы получим следующий результат. Очевидно, ошибочная подсказка при вставке ничего не испортила, поскольку порядок ассоциативного массива все еще правильный:

"a": 1, "b": 1, "c": 2, "d": 3, "w": 1, "x": 1, "y": 1, "z": 1,

Как это работает

Единственное отличие от обычной вставки в этом примере заключается в том, что мы используем дополнительный итератор-подсказку. Кроме того, мы говорили о правильных и неправильных подсказках.

Правильная подсказка будет указывать на существующий элемент, чье значение превышает значение вставляемого элемента, чтобы новый элемент занял позицию прямо перед ней. Если с подсказкой, предоставленной пользователем, это невозможно сделать, то функция insert откатится к неоптимизированной версии, которая выполнится за время O(log(n)).

Во время первой вставки у нас есть итератор, указывающий на конечный элемент ассоциативного массива, поскольку у нас нет более удачной стартовой позиции. После вставки в дерево символа z нам станет известно, что прямо перед ним будет вставлен символ y, и это вполне сгодится на роль правильной подсказки. То же применимо и к символу x, если мы будем вставлять его в дерево после добавления символа y, и т.д. Именно поэтому вы можете использовать итератор, который был возвращен последней операцией вставки, для выполнения следующей вставки.

 Важно знать, что до появления С++11 подсказки для вставки считались правильными, если указывали на позицию, которая стоит перед вновь вставленным элементом.

Дополнительная информация

Что интересно, неправильная подсказка не нарушает порядок элементов в ассоциативном массиве. Как же тогда это вообще работает и что же означает выражение «амортизированное время вставки равно O(1)»?

Контейнер std::map обычно реализуется с применением бинарного дерева поиска. При вставке в данное дерево новый ключ сравнивается с ключами других узлов, начиная с вершины. Если ключ меньше или больше, чем ключ текущего узла, то алгоритм поиска смещается влево или вправо и опускается вниз на один узел. Выполняя такие операции, поисковый алгоритм остановится в точке, где глубина текущего дерева максимальна, и поместит туда новый узел и его ключ. Вполне возможно, что данный шаг нарушит баланс дерева, поэтому после вставки будет выполнен алгоритм перебалансировки.

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

Если же подсказка ошибочна, то функция вставки попросту проигнорирует ее и начнет работу с выполнения алгоритма поиска. В итоге она отработает корректно, но, очевидно, медленнее. 

Поскольку структура данных std::map соотносит ключи со значениями таким образом, что ключи всегда уникальны и отсортированы, очень важно исключить для пользователей возможность изменить ключи узлов, которые уже вставлены в контейнер. Чтобы пользователи не могли изменять ключи элементов идеально отсортированных узлов ассоциативного массива, к типу ключа добавляется слово const.

Такого рода ограничение разумно, поскольку пользователю будет сложнее неправильно задействовать контейнер std::map. Но что же делать, если нам вдруг действительно понадобится изменить ключи некоторых элементов ассоциативного массива?

До появления С++17 нам приходилось удалять элементы, для которых нужно изменить ключ, а затем вставлять их снова. Недостаток такого подхода состоит в выполнении бесполезных выделений и высвобождений памяти, что плохо с точки зрения производительности.

Начиная с С++17 можно удалить и снова вставить элементы ассоциативного массива без повторного выделения памяти. Далее мы увидим, как это работает.

 Использование контейнера std::unordered_map вместо std::map подразумевает дополнительную степень свободы при выборе типа ключа. Контейнер std::map требует наличия между ключами естественного порядка. Таким образом элементы можно отсортировать. Но если мы хотим, например, использовать в качестве ключа математический вектор? Мы не можем сказать, что вектор (0, 1) меньше или больше вектора (1, 0). Они просто указывают в разных направлениях. Это верно для контейнера std::unordered_map, поскольку мы станем различать элементы не по их величине, а по значениям их хеша. Единственное, что нужно сделать, — реализовать хеш-функцию для нашего собственного типа, а также оператор ==, который будет проверять идентичность двух объектов. В данном разделе мы рассмотрим пример такой реализации.

 Контейнер std::set довольно странный. Принцип его работы похож на принцип работы контейнера std::map. Однако std::set содержит только ключи в качестве значений, а не пары «ключ — значение». Поэтому он не очень подходит для соотношения значения одного типа со значениями другого. Поскольку способы применения этого контейнера не вполне очевидны, многие разработчики даже не знают о его существовании. Они часто начинают реализовывать похожие механизмы самостоятельно, хотя в некоторых ситуациях контейнер std::set оказался бы отличным подспорьем.

В этом разделе будет показано, как применить контейнер std::set, на примере, в котором мы получаем потенциально большое количество разных элементов. Мы отфильтруем их и выведем на экран уникальные элементы.

 Класс std::stack — класс-адаптер, который позволяет помещать в себя объекты, словно в реальную стопку объектов, а также получать их. В текущем разделе на основе этой структуры данных мы создадим калькулятор, применяющий обратную польскую нотацию, ОПН (reverse polish notation, RPN).

ОПН — это нотация, которая может служить для записи математических выражений таким образом, чтобы их было проще анализировать. В ОПН выражение 1 + 2 выглядит как 1 2 +. Сначала идут операнды, а затем — оператор. Еще один пример: выражение (1 + 2) * 3 в ОПН выглядит как 1 2 + 3 *, оно уже показывает, почему подобные выражения проще анализировать, и нам не нужны скобки, чтобы определить подвыражения (рис. 2.4).

Контейнер std::map очень полезен в тех случаях, когда нужно разбить данные на категории и собрать соответствующую статистику. Прикрепляя изменяемые объекты к каждому ключу, который представляет собой категорию объектов, вы легко можете реализовать, к примеру, гистограмму, показывающую частоту встречаемости слов. Этим мы и займемся.

Когда большое количество элементов нужно сохранить в упорядоченном виде, а ключи могут встречаться несколько раз, пригодится контейнер std::multimap.

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

Как это делается

В этом примере мы считаем данные, введенные пользователем, из стандартного потока ввода, и разобьем их на предложения (а не на слова, как делали раньше). Далее поместим все предложения в контейнер std::multimap в паре с переменной, в которой записана их длина. После этого выведем пользователю все предложения, отсортировав их по длине.

1. Как обычно, включим все необходимые заголовочные файлы. Контейнер std::multimap поставляется оттуда же, откуда и контейнер std::map:

#include <iostream>

#include <iterator>

#include <map>

#include <algorithm>

2. Мы будем применять множество функций из пространства имен std, поэтому объявим о его (автоматическом) использовании:

using namespace std;

3. При токенизации строк путем извлечения их содержимого, стоящего между точками, получим предложения текста, окруженные пробелами, символами перехода на новую строку и т.д. Это нежелательным образом увеличивает их размер, так что отбросим лишние символы с помощью вспомогательной функции, которую сейчас определим:

string filter_ws(const string &s)

{

  const char *ws {" \r\n\t"};

  const auto a (s.find_first_not_of(ws));

  const auto b (s.find_last_not_of(ws));

  if (a == string::npos) {

    return {};

  }

  return s.substr(a, b - a + 1);

}

4. Функция определения длины предложения станет принимать гигантскую строку, содержащую весь текст, и возвращать контейнер std::multimap, в котором будут соотнесены предложения и их длины:

multimap<size_t, string> get_sentence_stats(const string &content)

{

5. Начнем с объявления структуры multimap, которая станет возвращаемым значением, а также нескольких итераторов. Поскольку мы создадим цикл, нам понадобится конечный итератор. Далее воспользуемся двумя итераторами, чтобы указать на две соседние точки (знаки препинания) внутри текста. Все находящееся между ними будем считать предложением.

  multimap<size_t, string> ret;

  const auto end_it (end(content));

  auto it1 (begin(content));

  auto it2 (find(it1, end_it, '.'));

6. Итератор it2 всегда будет указывать на одну точку дальше, чем итератор it1. До тех пор, пока итератор it1 не достигнет конца текста, все будет в порядке. Второе условное выражение проверяет, действительно ли итератор it2 указывает на позицию, стоящую на несколько символов дальше. Если это не так, то у нас не осталось непрочитанных символов.

  while (it1 != end_it && distance(it1, it2) > 0) {

7. Создаем строку из всех символов между итераторами, после чего удаляем лишние пробельные символы из ее начала и конца, чтобы определить точную длину предложения:

    string s {filter_ws({it1, it2})};

8. Возможно, приложение не содержит ничего, кроме пробельных символов. В этом случае просто отбрасываем его. В противном случае установим его длину, определив количество слов. Это делается легко, поскольку все слова разделены одним пробелом[2]. Затем сохраняем количество слов и само предложение в контейнер multimap:

    if (s.length() > 0) {

      const auto words (count(begin(s), end(s), ' ') + 1);

      ret.emplace(make_pair(words, move(s)));

    }[3]

9. На следующей итерации цикла мы переводим ведущий итератор it2 на символ точки в следующем предложении. Догоняющий итератор it1 переводим на следующий символ относительно предыдущей позиции ведущего итератора:

    it1 = next(it2, 1);[4]

    it2 = find(it1, end_it, '.');

  }

10. После завершения работы цикла контейнер будет содержать все предложения, объединенные в пары с количеством слов, содержащихся в них. Наконец можно вернуть полученный результат:

  return ret;

}

11. Теперь воспользуемся вновь добавленной функцией. Сначала укажем std::cin не пропускать пробельные символы, поскольку нам нужны предложения с пробелами как единое целое. Чтобы считать весь файл, инициализируем std::string на основе итераторов потока ввода, которые инкапсулируют std::cin:

int main()

{

  cin.unsetf(ios::skipws);

  string content {istream_iterator<char>{cin}, {}};

12. Поскольку нужен полученный контейнер multimap лишь для того, чтобы вывести на экран результат, помещаем вызов функции get_sentence_stats непосредственно в цикл и передаем ему нашу строку. В теле цикла выведем элементы построчно:

  for (const auto & [word_count, sentence]

      : get_sentence_stats(content)) {

    cout << word_count << " words: " << sentence << ".\n";

  }

}

13. После компиляции кода мы можем дать приложению команду использовать содержимое любого текстового файла. Текст-пример Lorem Ipsum даст следующий результат. Вывод на экран довольно велик для длинных текстов с большим количеством предложений: сначала выводятся самые короткие предложения, а затем — самые длинные. В результате мы сразу видим самые длинные предложения, поскольку обычно по умолчанию на экране отображается нижняя часть вывода:

$ cat lorem_ipsum.txt | ./sentence_length[5]

...

10 words: Nam quam nunc, blandit vel, luctus pulvinar,

hendrerit id, lorem.

10 words: Sed consequat, leo eget bibendum sodales,

augue velit cursus nunc,.

12 words: Cum sociis natoque penatibus et magnis dis

parturient montes, nascetur ridiculus mus.

17 words: Maecenas tempus, tellus eget condimentum rhoncus,

sem quam semper libero, sit amet adipiscing sem neque sed ipsum.

Как это работает

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

const auto end_it (end(content));

auto it1 (begin(content)); // (1) Начало строки

auto it2 (find(it1, end_it, '.')); // (1) Первая точка '.'

while (it1 != end_it && std::distance(it1, it2) > 0) {

  string sentence {it1, it2};

  // Что-то делаем со строкой предложения...

  it1 = std::next(it2, 1);      // Один символ справа от текущей точки '.'

  it2 = find(it1, end_it, '.'); // Следующая точка или конец строки

}

Взглянем на код, имея при этом в виду следующий рисунок, на котором приведены три предложения (рис. 2.5).

Итераторы it1 и it2 всегда перемещаются вперед по строке вместе. Таким образом, они всегда указывают на начало и конец одного и того же предложения. Алгоритм std::find заметно облегчает нам жизнь, поскольку работает по принципу «начинаем с текущей позиции, а затем возвращаем итератор, указывающий на следующий символ точки. Если такого итератора нет, то возвращаем конечный итератор».

После извлечения строки с предложением определим, сколько слов в ней содержится, а затем вставим ее в контейнер multimap. Мы используем количество слов в качестве ключа для элементов массива, а саму строку — как объект, связанный с данным ключом. Мы не можем воспользоваться контейнером std::map, так как предложений одинаковой длины может быть довольно много. Но это не проблема, поскольку мы задействуем контейнер std::multimap, который легко справляется с совпадающими ключами. Данный контейнер хранит ключи в упорядоченном виде, что позволяет нам вывести предложения в порядке возрастания их длины.

Дополнительная информация

После того как мы считали весь файл в одну большую строку, мы проходим по ней и создаем копию каждого предложения. Однако это не обязательно, ведь можно воспользоваться std::string_view; данный вопрос мы рассмотрим далее в книге.

Еще один способ получить строки между двумя соседними точками — задействовать класс std::regex_iterator, который мы также рассмотрим несколько позже.

 Класс std::priority_queue — еще один класс-адаптер для контейнеров, как и std::stack. Он является оболочкой для другой структуры данных (по умолчанию это std::vector) и предоставляет для нее интерфейс очереди. Т.е. элементы можно помещать туда и выталкивать оттуда пошагово. Все, что было помещено туда раньше, раньше очередь и покинет. Обычно данный принцип обозначается как FIFO (first in, first out — «первый вошел — первый вышел»). Он полностью противоположен принципу работы стека, где последний помещенный элемент будет вытолкнут первым.

Несмотря на то что мы описали, как работает контейнер std::queue, в текущем разделе будет показана работа контейнера std::priority_queue. Он особенный, поскольку не только имеет характеристики FIFO, но и объединяет их с приоритетами. Иными словами, содержимое, по сути, разбивается на подочереди, работающие по принципу FIFO, которые упорядочены в соответствии с указанным для них приоритетом.

В этой главе:

□ построение собственного итерабельного диапазона данных;

□ обеспечение совместимости ваших итераторов с категориями итераторов STL;

□ использование оболочек для итераторов для заполнения обобщенных структур данных;

□ реализация алгоритмов с помощью итераторов;

□ перебор (итерирование) в обратную сторону с применением обратных адаптеров для итераторов;

□ завершение перебора диапазонов данных с использованием ограничителей;

□ автоматическая проверка кода итератора с помощью проверяемых итераторов;

□ создание собственного адаптера для итераторов-упаковщиков. 

Итераторы — крайне важная концепция языка С++. Библиотека STL создавалась максимально гибкой и обобщенной, а итераторы способствуют этому. К сожалению, иногда применять их несколько утомительно, и многие новички избегают их и возвращаются к стилю программирования, свойственному языку С. Программист, который избегает использования итераторов, по сути, отказывается от половины потенциала библиотеки STL. В данной главе мы рассмотрим итераторы, постаравшись разобраться в их достоинствах и недостатках. Надеюсь, показанные примеры помогут вам понять основные принципы работы с итераторами.

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

□ Один алгоритм, который работает с массивом, проверяя его размер и суммируя все его члены, выглядит так:

int sum {0};

for (size_t i {0}; i < array_size; ++i) { sum += array[i]; }

□ Другой алгоритм, который работает со связанным списком и итерирует по нему до конца, выглядит следующим образом:

int sum {0};

while (list_node != nullptr) {

  sum += list_node->value; list_node = list_node->next;

}

Оба алгоритма суммируют целые числа, но какая часть введенных нами символов непосредственно связана с решением задачи? Работает ли какой-нибудь из этих алгоритмов с другими видами структур данных, например с std::map, или нужно реализовывать еще одну версию алгоритма суммирования? Отсутствие итераторов приведет к нелепым решениям.

Только с помощью итераторов можно реализовать этот алгоритм в обобщенном виде:

int sum {0};

for (int i : array_or_vector_or_map_or_list) { sum += i; }

Это красивое и короткое выражение, названное «основанный на диапазоне цикл for», существует еще со времен С++11. Оно представляет собой лишь синтаксический сахар, который развертывается в нечто похожее на следующий код:

{

  auto &&  range = array_or_vector_or_map_or_list;

  auto  begin = std::begin( range);

  auto  end = std::end( range);

  for ( ;  begin !=  end; ++ begin) {

    int i = * begin;

    sum += i;

  }

}

Такие циклы хорошо знакомы всем, кто уже работал с итераторами, но кажутся черной магией для тех, кто еще этого не делал. Представьте, что наш вектор, содержащий целые числа, выглядит следующим образом (рис. 3.1).

Команда std::begin(vector) аналогична команде vector.begin(), она возвращает итератор, который указывает на первый элемент (1). Команда std::end(vector) аналогична команде vector.end(), она возвращает итератор, указывающий на элемент, стоящий за последним элементом (5).

На каждой итерации цикл проверяет, равен ли начальный итератор конечному. Если это не так, то мы разыменовываем начальный итератор и получаем доступ к числовому значению, на которое он указывает. Далее выполняем операцию инкремента для итератора, повторяем сравнение с конечным итератором и т.д. В этот момент полезно прочесть код цикла снова, представляя, что итераторы — обычные указатели, взятые из языка С. Фактически такие указатели тоже являются итераторами.

Категории итераторов

Существует несколько категорий итераторов, каждая из которых имеет разные ограничения. Их несложно запомнить, однако имейте в виду: возможности, требуемые одной категорией, унаследованы из другой, более мощной. Вся суть категорий итераторов заключается в том, что если при реализации алгоритма вы знаете, с каким именно итератором будете работать, то сможете реализовать оптимизированную версию. Таким образом, программисту достаточно просто выразить свое намерение, а компилятор выберет оптимальную реализацию для поставленной задачи.

Рассмотрим их в правильном порядке (рис. 3.2).

Итераторы ввода

Могут быть разыменованы только для того, чтобы прочесть значение, на которое указывают. При их инкрементировании последнее значение, на которое они указывают, становится недействительным во время данной операции, а значит, вы не можете итерировать по такому диапазону данных несколько раз. Примером итератора этой категории является std::istream_iterator.

Однонаправленные итераторы

Аналогичны итераторам ввода, но отличаются тем, что по диапазонам данных, которые они представляют, вы можете проитерировать несколько раз. В качестве примера такого итератора приведем std::forward_list. По такому списку можно проитерировать только вперед, но не назад, однако это можно сделать требуемое количество раз.

Двунаправленные итераторы

Как следует из названия, их можно инкрементировать и декрементировать, что позволяет итерировать вперед и назад. Эту возможность, например, поддерживают итераторы для контейнеров std::list, std::set и std::map.

Итераторы с произвольным доступом

Позволяют перескакивать через несколько значений сразу вместо того, чтобы двигаться пошагово. Примером таких итераторов являются итераторы для контейнеров std::vector и std::deque.

Непрерывные итераторы

Соответствуют всем указанным выше требованиям, но при этом необходимо, чтобы данные, по которым выполняется итерирование, находились в непрерывной памяти, как, например, в массиве std::vector.

Итераторы вывода

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

Изменяемые итераторы

Если итератор является итератором вывода, а также состоит в какой-то другой категории, то называется изменяемым. С его помощью можно считывать и записывать данные. При получении из неконстантного экземпляра контейнера итератор, как правило, будет состоять именно в этой категории. 

 Мы уже знаем, что итераторы в некоторой степени представляют собой стандартный интерфейс для выполнения перебора во всех видах контейнеров. Нужно только реализовать оператор префиксного инкремента ++, оператор разыменования * и оператор сравнения объектов ==, и получится примитивный итератор, подходящий для работы с циклом for, основанным на диапазоне, который появился в C++11.

Чтобы немного освоиться с итераторами, рассмотрим пример реализации одного из них, который просто генерирует диапазон чисел при переборе. Он не дополняется структурой-контейнером. Числа генерируются непосредственно при переборе.

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

Проблема заключается в том, что многие алгоритмы STL пытаются больше узнать об итераторах, с которыми должны работать. Разные категории итераторов имеют разные возможности, и поэтому существует несколько вариантов реализации одного алгоритма. Например, обычные числа из одного вектора в другой можно скопировать с помощью быстрого вызова memcpy. Если мы копируем данные из списка или в него, то такой вызов сделать нельзя и элементы нужно копировать по одному. Авторы алгоритмов STL хорошо продумали подобную автоматическую оптимизацию. Чтобы помочь им, мы укажем некоторую информацию о наших итераторах. В этом разделе показано, как достичь той же цели.

Как это делается

В этом примере мы реализуем примитивный итератор, считающий числа, и используем его вместе с алгоритмом STL, с которым он изначально не будет компилироваться. Затем сделаем все, чтобы итератор стал совместим с STL.

1. Сначала, как обычно, включим некоторые заголовочные файлы:

#include <iostream>

#include <algorithm>

2. Далее реализуем примитивный итератор для подсчета чисел, как было показано в предыдущем разделе. При переборе он генерирует обычные увеличивающиеся целые числа. Диапазон данных num_range выступает в роли удобного донора начального и конечного итераторов:

class num_iterator

{

  int i;

public:

  explicit num_iterator(int position = 0) : i{position} {}

  int operator*() const { return i; }

  num_iterator& operator++() {

    ++i;

    return *this;

  }

  bool operator!=(const num_iterator &other) const {

    return i != other.i;

  }

  bool operator==(const num_iterator &other) const {

    return !(*this != other);

  }

};

class num_range {

  int a;

  int b;

public:

  num_range(int from, int to)

      : a{from}, b{to}

  {}

  num_iterator begin() const { return num_iterator{a}; }

  num_iterator end() const { return num_iterator{b}; }

};

3. Чтобы избавиться от префикса пространства имен std:: и поддерживать код читабельным, объявим об использовании пространства имен std:

using namespace std;

4. Теперь просто создадим диапазон данных, содержащий числа от 100 до 109. Обратите внимание: конечный итератор стоит в позиции 110. Это значит, что 110 — первое число, которое находится за пределами диапазона (именно поэтому он начинается со значения 100 и заканчивается значением 109):

int main()

{

  num_range r {100, 110};

5. Теперь воспользуемся им для std::minmax_element. Алгоритм возвращает объект типа std::pair с двумя членами: итератором, указывающим на минимальное значение, и другим итератором, указывающим на максимальное значение. В нашем примере этими значениями будут 100 и 109, поскольку именно с их помощью мы создавали диапазон данных:

  auto [min_it, max_it] (minmax_element(begin(r), end(r)));

  cout << *min_it << " - " << *max_it << '\n';

}

6. Компиляция этого кода приведет к следующему сообщению об ошибке (рис. 3.3). Вы увидите ошибку, связанную с std::iterator_traits. Подробнее об этом вы узнаете позже. Может случиться так, что вы увидите другую ошибку, если применяете другие компиляторы и/или реализацию библиотеки STL; а возможно даже, что ошибок не будет. Сообщение об ошибке, показанное на рис. 3.3, появляется при использовании компилятора clang version 5.0.0 (trunk 299766).

7. Для исправления ситуации активизируем возможности типажей итераторов для нашего класса итератора. Сразу после определения num_iterator укажем следующую спецификацию шаблона структуры для типа std::iterator_traits. Она сообщает STL, что наш итератор num_iterator является однонаправленным и итерирует по целочисленным значениям:

namespace std {

  template <>

  struct iterator_traits<num_iterator> {

    using iterator_category = std::forward_iterator_tag;

    using value_type = int;

  };

}

8. Скомпилируем код снова; мы видим, что он работает! Результат работы функций min/max выглядит следующим образом:

100 — 109

Как это работает

Одним алгоритмам STL нужно знать характеристики типа итератора, применяемого вместе с ними, другим — тип элементов, среди которых выполняется перебор. От этого зависят варианты реализации алгоритмов.

Однако все алгоритмы STL будут получать эту информацию о типе с помощью std::iterator_traits<my_iterator>, предполагая, что итератор имеет тип my_iterator. Этот класс типажа содержит до пяти разных определений членов.

□ difference_type — значение какого типа мы получим в результате выполнения конструкции it1 — it2?

□ value_type — какой тип имеет элемент, к которому мы получаем доступ с помощью *it (обратите внимание: для чистых итераторов вывода этот тип будет void)?

□ pointer — к какому типу должен относиться указатель, чтобы иметь возможность указывать на элемент?

□ reference — какой тип должна иметь ссылка, чтобы она могла работать как полагается?

□ iterator_category: к какой категории принадлежит итератор?

Определения типов pointer, reference и difference_type не нужны для нашего итератора num_iterator, поскольку он не итерирует по реальным значениям памяти (мы просто возвращаем значения int, но они не доступны на постоянной основе, как это было бы в случае использования массива). Поэтому лучше не определять их, поскольку если алгоритм зависит от доступности элементов диапазона в памяти, то при работе с нашим итератором он может генерировать ошибки.

Дополнительная информация

До появления C++17 поощрялось наследование итераторами типа std::iterator<...>, что автоматически заполняет наш класс всеми описаниями типов. Этот механизм все еще работает, но, начиная с С++17, больше не рекомендуется. 

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

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

Итераторы обычно итерируют, переходя с одного элемента контейнера на другой. Но не обязательно использовать итераторы только для того, чтобы итерировать по структурам данных. Они вполне подходят для реализации алгоритмов, в таком случае будут высчитывать следующее значение при инкрементировании (++it) и возвращать это значение при разыменовании (*it).

В данном разделе мы рассмотрим этот принцип, реализовав функцию, выводящую на экран последовательность чисел Фибоначчи с помощью итераторов. Такая функция рекурсивно определяется следующим образом: F(n) = F(n-1)+F(n-2). Она начинается со стартовых значений F(0) = 0 и F(1) = 1. Это приводит к появлению такой последовательности чисел:

□  F(0) = 0;

□  F(1) = 1;

□  F(2) = F(1)+F(0) = 1;

□  F(3) = F(2)+F(1) = 2;

□  F(4) = F(3)+F(2) = 3;

□  F(5) = F(4)+F(3) = 5;

□  F(6) = F(5)+F(4) = 8;

□  ... и т.д.

Иногда может быть полезно итерировать по диапазону данных не вперед, а назад. Основанный на диапазонах цикл for, а также все алгоритмы STL обычно итерируют по диапазонам данных, инкрементируя итераторы, однако перебор (итерирование) в обратную сторону требует выполнения операции декремента. Конечно, можно обернуть итераторы в слой, преобразующий операцию инкремента в операцию декремента. Но складывается впечатление, что у нас получится множество стереотипного кода на каждый тип, для которого мы собираемся поддерживать эту возможность.

Библиотека STL предоставляет полезный обратный адаптер для итератора, позволяющего задействовать итераторы подобным образом.

Как это делается

В этом примере мы будем разными способами применять обратные итераторы, чтобы показать варианты их использования.

1. Как обычно, включим некоторые заголовочные файлы:

#include <iostream>

#include <list>

#include <iterator>

2. Далее объявляем об использовании пространства имен std с целью сэкономить немного времени:

using namespace std;

3. Чтобы у нас появился объект, по которому мы сможем итерировать, создадим список, содержащий целые числа:

int main()

{

  list<int> l {1, 2, 3, 4, 5};

4. Теперь выведем эти числа на экран в обратном порядке. Для этого проитерируем по списку благодаря функциям rbegin и rend класса std::list и выведем данные значения с помощью стандартного потока вывода, используя удобный адаптер ostream_iterator:

  copy(l.rbegin(), l.rend(), ostream_iterator<int>{cout, ", "});

  cout << '\n';

5. Если контейнер не предоставляет функций rbegin и rend, но хотя бы выдает двунаправленные итераторы, то поможет функция std::make_reverse_iterator. Она принимает обычные итераторы и преобразует их в обратные:

  copy(make_reverse_iterator(end(l)),

       make_reverse_iterator(begin(l)),

       ostream_iterator<int>{cout, ", "});

  cout << '\n';

}

6. Компиляция и запуск программы дадут следующий результат:

5, 4, 3, 2, 1,

5, 4, 3, 2, 1,

Как это работает

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

Обратный итератор содержит обычный итератор и подражает его интерфейсу, но изменяет операцию инкремента на операцию декремента.

Еще одна деталь связана с позициями начала и конца. Взглянем на рис. 3.4, на котором показана стандартная последовательность чисел, хранящаяся в итерабельном диапазоне данных. Если она содержит числа от 1 до 5, то начальный итератор должен указывать на элемент 1, а конечный итератор — на элемент, стоящий сразу после 5.

При определении обратных итераторов итератор rbegin должен указывать на элемент 5, а итератор rend — на элемент, стоящий сразу перед1. Переверните книгу вверх ногами — и убедитесь в том, что это имеет смысл.

Если мы хотим, чтобы наши собственные классы-контейнеры поддерживали обратный перебор, то не нужно реализовывать все эти детали самостоятельно, можно просто обернуть обычные итераторы в обратные с помощью вспомогательной функции std::make_reverse_iterator, и она сделает всю работу за нас. 

Как алгоритмы STL, так и основанные на диапазонах циклы for предполагают, что начальная и конечная позиции для перебора известны заранее. В некоторых ситуациях, однако, нельзя узнать конечную позицию до того, как она будет достигнута при переборе.

Самый простой пример такой ситуации — это перебор в стиле С простых строк, длина которых во время выполнения неизвестна. Код, итерирующий по таким строкам, обычно выглядит следующим образом:

 Хотя итераторы очень полезны и предоставляют общие интерфейсы, есть шанс использовать их неправильно, как и указатели. При работе с указателями код нужно писать так, чтобы никогда не разыменовывать их в те моменты, когда они указывают на некорректные точки в памяти. То же верно и для итераторов, но для них предусмотрено множество правил, которые позволяют определить, корректен ли итератор. С этими правилами можно ознакомиться, изучив документацию к STL, но вероятность написания кода с ошибками не исчезнет.

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

К счастью, спасение есть! Реализация GNU STL имеет режим отладки, а компиляторы GNU C++ и LLVM clang C++ поддерживают дополнительные библиотеки, пригодные для создания сверхчувствительных и избыточных бинарных файлов, которые будут мгновенно сообщать о большинстве ошибок. Их легко использовать, и они очень полезны, что мы и продемонстрируем в этом разделе. Стандартная библиотека Microsoft Visual C++ также предоставляет возможность проведения дополнительных проверок.

Как это делается

В этом примере мы напишем программу, которая намеренно получает доступ к некорректному итератору.

1. Сначала включим заголовочные файлы:

#include <iostream>

#include <vector>

2. Теперь создадим вектор, содержащий целые числа, и получим итератор, указывающий на первый элемент, — значение 1. Мы применим функцию shrink_to_fit() для вектора с целью убедиться, что его емкость действительно равна 3, поскольку данная реализация может выделять фрагмент памяти больше необходимого, чтобы благодаря этому небольшому резерву будущие операции вставки проходили быстрее:

int main()

{

  std::vector<int> v {1, 2, 3};

  v.shrink_to_fit();

  const auto it (std::begin(v));

3. Далее выведем на экран разыменованный итератор, что совершенно корректно:

  std::cout << *it << '\n';

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

  v.push_back(123);

5. Теперь снова выведем на экран значение 1 из вектора с помощью данного итератора. Это кончится плохо. Почему? Когда вектор переместил все свои значения в новый фрагмент памяти и удалил старый, он не сообщил итератору о текущем изменении. Т.е. итератор все еще указывает на старую позицию, и мы точно не знаем, что с тех пор произошло.

  std::cout << *it << '\n'; // плохо плохо плохо!

}

6. Компиляция и запуск программы приводят к идеальному выполнению. Приложение не дает сбой, но данные, которые оно выводит на экран при разыменовании некорректного указателя, выглядят совершенно случайными. В таком виде программу оставлять нельзя, но к этому моменту никто не сообщит нам о данной ошибке, если мы не заметим ее сами (рис. 3.5).

7. Ситуацию спасут флаги отладки! Реализация GNU STL поддерживает макрос препроцессора _GLIBCXX_DEBUG, который активизирует много функций для проверки достоверности STL. Это замедляет выполнение программы, но зато помогает находить ошибки. Можно активизировать макрос, добавив флаг -D_GLIBCXX_DEBUG в командную строку компилятора или определив его в начале файла кода, поместив его до директив include. Как видите, он завершает работу приложения, после чего запускаются разные средства очистки. Скомпилируем код с флагом для активизации проверяемых итераторов (в компиляторе Microsoft Visual C++ выглядит как /D_ITERATOR_DEBUG_LEVEL=1) (рис. 3.6).

8. Реализация STL для LLVM/clang тоже имеет флаги отладки, но они нужны для отладки самой STL, а не пользовательского кода. Для последнего можно активизировать различные средства очистки. Скомпилируем код для clang с помощью флагов -fsanitize=address-fsanitize=undefined и посмотрим, что произойдет (рис. 3.7).

Ого! Перед нами очень точное описание того, что именно пошло не так. Если бы мы не обрезали этот скриншот, то он занял бы несколько страниц книги. Обратите внимание: это характерно не только для clang, но и для GCC.

 Если вы видите ошибки во время выполнения программы из-за того, что отсутствует какая-то библиотека, то значит, ваш компилятор не поставляется с библиотеками libasan и libubsan. Попробуйте установить их с помощью вашего менеджера пакетов или чего-то аналогичного.

Как это работает

Как видите, нам ничего не нужно менять в программе, чтобы включить эту функциональность для кода, генерирующего ошибки. Мы, по сути, получили ее бесплатно, просто добавив некоторые флаги компилятора в командную строку при компиляции программы.

Эта возможность реализуется средствами очистки. Обычно это дополнительный модуль компилятора и библиотека, работающая во время выполнения программы. При активизации средства очистки компилятор добавит дополнительную информацию и код в бинарный файл, который представляет собой нашу программу. Во время выполнения библиотеки средства очистки, связанные с бинарным файлом программы, например, заменяют функции malloc и free, чтобы проанализировать, как программа работает с получаемой памятью.

Средства очистки помогают обнаруживать различные баги. Перечислю лишь несколько полезных примеров.

□ Выход за пределы диапазона: ошибка случается, когда мы получаем доступ к элементу массива, вектора или аналогичного контейнера, лежащему за пределами корректной области памяти.

□ Использование после освобождения: ошибка происходит, если мы обращаемся к памяти кучи после того, как она была освобождена (что мы и сделали в данном разделе).

□ Переполнение переменной типа int: ошибка появляется, если целочисленная переменная переполняется в результате подсчета значений, которые в нее не помещаются. Для целых чисел со знаком это приведет к неопределенному поведению.

□ Выравнивание указателя: в некоторых архитектурах невозможно обратиться к памяти, если блоки памяти выровнены неаккуратно.

Средства очистки могут обнаруживать и многие другие ошибки.

Вы не всегда можете активизировать все доступные средства очистки, поскольку это замедляет программу. Однако хорошим тоном является их полная активизация в блочных и интеграционных тестах.

Дополнительная информация

Существует множество средств очистки для разных категорий ошибок, и все они еще разрабатываются. Мы можем и должны информировать других пользователей о том, как они могут улучшить свои тесты. На домашних страницах проектов GCC и LLVM в разделе документации перечислены доступные средства очистки:

□ https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html;

□ http://clang.llvm.org/docs/index.html (найдите в содержании раздел Sanitizers (Средства очистки)).

Каждый программист должен знать о тестировании с использованием средств очистки и всегда уметь его выполнять. К сожалению, в пугающе большом количестве компаний этого не происходит, несмотря даже на то, что код с ошибками — самая главная точка входа для вредоносного ПО и компьютерных вирусов.

Заняв должность разработчика в новой для вас компании, сразу убедитесь, что в вашей команде используются все доступные средства очистки. Если это не так, то у вас есть уникальный шанс исправить важные и незаметные ошибки в свой первый рабочий день!

Работа с разными языками программирования требует использования различных стилей программирования. Это неудивительно, поскольку каждый язык программирования был разработан для решения конкретных задач.

Существует особый стиль программирования — чистое функциональное программирование. Он значительно отличается от императивного, к которому привыкли программисты, работающие на С и С++. Несмотря на то, что этот стиль значительно отличается от других, во многих ситуациях он позволяет писать очень элегантный код.

Один из примеров проявления данной элегантности — реализация формул, например скалярного произведения. Если даны два математических вектора, то нахождение их скалярного произведения означает попарное умножение чисел на одинаковых позициях вектора, а затем суммирование этих умноженных значений. Скалярное произведение векторов (a,b,c)*(d,e,f) равно (a*e+b*e+c*f)[6]. Конечно, это можно сделать и с помощью языков C и C++. Код выглядел бы следующим образом:

std::vector<double> a {1.0, 2.0, 3.0};

std::vector<double> b {4.0, 5.0, 6.0};

double sum {0};

for (size_t i {0}; i < a.size(); ++i) {

  sum += a[i] * b[i];

}

// sum = 32.0

Как же выглядит аналогичный код в языках, которые считаются более элегантными?

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

Python не является чистым функциональным языком, но в некоторой степени использует аналогичные шаблоны, что видно в следующем примере (рис. 3.9).

В библиотеке STL вы можете найти специальный алгоритм: std::inner_product, тоже решающий эту конкретную задачу в одну строку. Но идея заключается в том, что во многих языках программирования такой код можно писать динамически одной строкой, не подключая конкретные функции библиотек, которые решают именно эту задачу.

Не погружаясь в объяснения синтаксиса других языков, выделим важную деталь, которая является общей в обоих примерах, — магическую функцию zip. Что она делает? Принимает два вектора a и b и преобразует их в смешанный вектор. Например, при вызове этой функции векторы [a1, a2, a3] и [b1, b2, b3] будут выглядеть как [(a1,b1), (a2,b2), (a3,b3)]. Посмотрите на него внимательно; он работает почти так же, как и ускорители упаковки!

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

Код на языке C++ нельзя сделать таким же элегантным, как код на языке Haskell или Python, но в этом разделе мы поговорим о способах реализации подобных возможностей с помощью итераторов путем добавления итератора-упаковщика. Определить скалярное произведение двух векторов можно более элегантно, задействуя конкретные библиотеки, но данный вопрос не относится к теме нашей книги. Однако я пытаюсь показать, насколько библиотеки, основанные на итераторах, могут помочь при написании выразительного кода, предоставляя очень обобщенные модули.

Как это делается

В этом примере мы воссоздадим функцию zip, известную из языков Haskell и Python. Она будет работать только для векторов, содержащих значения типа double, чтобы не отвлекаться от механики итераторов.

1. Сначала включим некоторые заголовочные файлы:

#include <iostream>

#include <vector>

#include <numeric>

2. Далее определим класс zip_iterator. При переборе диапазонов данных zip_iterator мы будем получать на каждом этапе пару значений из двух контейнеров. Это значит, что мы итерируем по двум контейнерам одновременно:

class zip_iterator {

3. Итератор-упаковщик должен сохранять два итератора, по одному для каждого контейнера:

  using it_type = std::vector<double>::iterator;

  it_type it1;

  it_type it2;

4. Конструктор просто сохраняет итераторы обоих контейнеров, по которым нужно проитерировать:

public:

  zip_iterator(it_type iterator1, it_type iterator2)

    : it1{iterator1}, it2{iterator2}

  {}

5. Инкрементирование итератора-упаковщика означает инкрементирование обоих итераторов-членов:

  zip_iterator& operator++() {

    ++it1;

    ++it2;

    return *this;

  }

6. Два итератора-упаковщика считаются неравными, если оба их итератора-члена не равны своим коллегам из другого итератора-упаковщика. Обычно вы можете использовать логическое ИЛИ (||) вместо логического И (&&), но представьте, что диапазоны данных имеют неравную длину. В таких случаях нельзя соотнести оба конечных итератора одновременно. Таким образом, можно прервать выполнение цикла при достижении первого конечного итератора в одном из диапазонов данных:

  bool operator!=(const zip_iterator& o) const {

    return it1 != o.it1 && it2 != o.it2;

  }

7. Оператор сравнения равенства реализуется с помощью другого оператора, изменяя результат его работы на противоположный:

  bool operator==(const zip_iterator& o) const {

    return !operator!=(o);

  }

8. Разыменование итератора-упаковщика открывает доступ к обоим контейнерам в одной и той же позиции:

  std::pair<double, double> operator*() const {

    return {*it1, *it2};

  }

};

9. Мы рассмотрели код итератора. Нужно сделать итератор совместимым с алгоритмами STL, поэтому следует определить стереотипный код для типажа. По сути, он говорит, что данный итератор является обычным однонаправленным и при разыменовании возвращает пары значений типа double. Несмотря на то, что мы не использовали в текущем примере difference_type, для некоторых реализаций STL это может понадобиться для успешной компиляции кода:

namespace std {

  template <>

  struct iterator_traits<zip_iterator> {

    using iterator_category = std::forward_iterator_tag;

    using value_type = std::pair<double, double>;

    using difference_type = long int;

  };

}

10. Следующий шаг — определение класса диапазона данных, функции begin и end которого возвращают итераторы-упаковщики:

class zipper {

  using vec_type = std::vector<double>;

  vec_type &vec1;

  vec_type &vec2;

11. Он должен сослаться на два существующих контейнера, чтобы создать итераторы-упаковщики:

public:

  zipper(vec_type &va, vec_type &vb)

    : vec1{va}, vec2{vb}

  {}

12. Функции begin и end просто передают пары начальных и конечных указателей, чтобы создать с их помощью экземпляры итераторов-упаковщиков:

  zip_iterator begin() const {

    return {std::begin(vec1), std::begin(vec2)};

  }

  zip_iterator end() const {

    return {std::end(vec1), std::end(vec2)};

  }

};

13. Как и в примерах кода на языках Haskell и Python, определяем два вектора, содержащих значения типа double. Кроме того, указываем, что используем пространство имен std внутри функции main по умолчанию:

int main()

{

  using namespace std;

  vector<double> a {1.0, 2.0, 3.0};

  vector<double> b {4.0, 5.0, 6.0};

14. Объект класса zipper объединяет их в один диапазон данных, напоминающий вектор, где можно увидеть пары значений векторов a и b:

  zipper zipped {a, b};

15. Используем метод std::accumulate, чтобы сложить все элементы диапазона данных. Сделать это напрямую нельзя, поскольку в результате мы сложим экземпляры типа std::pair<double, double>, для которых концепция суммирования не определена. Поэтому зададим вспомогательное лямбда-выражение, которое принимает пару, перемножает ее члены и складывает результат со значением переменной-аккумулятора. Функция std::accumulate хорошо работает с лямбда-выражениями со следующей сигнатурой:

  const auto add_product ([](double sum, const auto &p) {

    return sum + p.first * p.second;

  });

16. Теперь передадим его функции std::accumulate, а также пару итераторов для упаковываемых диапазонов и стартовое значение 0.0 для переменной-аккумулятора, которая, в конечном счете, будет содержать сумму произведений:

  const auto dot_product (accumulate(

    begin(zipped), end(zipped), 0.0, add_product));

17. Выведем на экран полученный результат:

  cout << dot_product << '\n';

}

18. Компиляция и запуск программы дадут правильный результат:

32

Дополнительная информация

Да, нам пришлось написать много строк, чтобы добавить в код немного синтаксического сахара, и он все еще не так элегантен, как версия кода на Haskell. Большим недостатком является тот факт, что наш итератор-упаковщик жестко закодирован — он работает только для векторов, содержащих переменные типа double.

С помощью шаблонов и типажей типов такой итератор может стать более обобщенным. Таким образом, он сможет работать со списками, векторами, двусторонними очередями и ассоциативными массивами, даже если они специализированы для совершенно других типов элементов контейнера.

Нельзя недооценивать объем работы, которую нужно выполнить, чтобы сделать эти классы обобщенными. К счастью, такие библиотеки уже существуют. Одной из популярных библиотек, не входящих в STL, является Boost (zip_iterator). Ее легко использовать для самых разных классов.

Кстати, если хотите узнать о наиболее элегантном способе определения скалярного произведения в C++ и вам не особо нужна концепция итераторов-упаковщиков, то обратите внимание на std::valarray. Взгляните сами:

#include <iostream>

#include <valarray>

int main()

{

  std::valarray<double> a {1.0, 2.0, 3.0};

  std::valarray<double> b {4.0, 5.0, 6.0};

  std::cout << (a * b).sum() << '\n';

}

Библиотека ranges. Это очень интересная библиотека для языка C++, которая поддерживает упаковщики и все прочие виды волшебных адаптеров итераторов, фильтров и т.д. Ее создатели вдохновлялись библиотекой Boost ranges, и какое-то время казалось, что она может попасть в C++17, но, к сожалению, придется ждать следующего стандарта. Библиотека значительно улучшит возможности написания выразительного и быстрого кода на C++ путем создания сложных механизмов из универсальных и простых блоков кода. В документации к ней можно найти очень простые примеры.

1. Определение суммы квадратов всех чисел от 1 до 10:

const int sum = accumulate(view::ints(1)

                      | view::transform([](int i){return i*i;})

                      | view::take(10), 0);

2. Фильтрация всех четных чисел из вектора чисел и преобразование остальных чисел в строки:

std::vector<int> v {1,2,3,4,5,6,7,8,9,10};

auto rng = v | view::remove_if([](int i){return i % 2 == 1;})

             | view::transform([](int i){return std::to_string(i);});

// rng == {"2"s,"4"s,"6"s,"8"s,"10"s};

Если вы заинтересовались и не можете дождаться выхода следующего стандарта С++, то обратитесь к документации для ranges, которая находится по адресу https://ericniebler.github.io/range-v3/.

В этой главе:

□ динамическое определение функций с помощью лямбда-выражений;

□ добавление полиморфизма путем оборачивания лямбда-выражений в конструкцию std::function;

□ создание функций с помощью конкатенации;

□ создание сложных предикатов с помощью логической конъюнкции;

□ вызов нескольких функций с одними и теми же входными данными;

□ реализация transform_if с применением std::accumulate и лямбда-выражений;

□ генерация декартова произведения на основе любых входных данных во время компиляции.

 Одной из важных новых функций C++11 были лямбда-выражения. В C++14 и C++17 они получили новые возможности, и это сделало их еще мощнее. Но что же такое лямбда-выражение?

Лямбда-выражения или лямбда-функции создают замыкания. Замыкание — очень обобщенный термин для безымянных объектов, которые можно вызывать как функции. Чтобы предоставить подобную возможность в С++, такой объект должен реализовывать оператор вызова функции (), с параметрами или без. Создание аналогичного объекта без лямбда-выражений до появления С++11 выглядело бы так:

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

Синтаксис лямбда-выражений выглядел новым в С++11, и к С++17 он несколько изменился. В этом разделе мы увидим, как сейчас выглядят лямбда-выражения и что они означают.

Как это делается

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

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

#include <iostream>

#include <string>

2. В данном примере все действие происходит в функции main. Мы определим два объекта функций, которые не принимают параметры, и вернем целочисленные константы со значениями 1 и 2. Обратите внимание: выражение return окружено фигурными скобками {}, как это делается в обычных функциях, а круглые скобки (), указывающие на функцию без параметров, являются необязательными, мы не указываем их во втором лямбда-выражении. Но квадратные скобки [] должны присутствовать:

int main()

{

  auto just_one ( [](){ return 1; } );

  auto just_two ( []  { return 2; } );

3. Теперь можно вызвать оба объекта функций, просто написав имя переменных, которые в них сохранены, и добавив скобки. В этой строке их не отличить от обычных функций:

  std::cout << just_one() << ", " << just_two() << '\n';

4. Забудем о них и определим еще один объект функции, который называется plus, — он принимает два параметра и возвращает их сумму:

  auto plus ( [](auto l, auto r) { return l + r; } );

5. Использовать такой объект довольно просто, в этом плане он похож на любую другую бинарную функцию. Мы указали, что его параметры имеют тип auto, вследствие чего объект будет работать со всеми типами данных, для которых определен оператор +, например со строками.

  std::cout << plus(1, 2) << '\n';

  std::cout << plus(std::string{"a"}, "b") << '\n';

6. Не нужно сохранять лямбда-выражение в переменной, чтобы использовать его. Мы также можем определить его в том месте, где это необходимо, а затем разместить параметры для данного выражения в круглых скобках сразу после него (1, 2):

  std::cout

    << [](auto l, auto r){ return l + r; }(1, 2)

    << '\n';

7. Далее определим замыкание, которое содержит целочисленный счетчик. При каждом вызове значение этого счетчика будет увеличиваться на 1 и возвращать новое значение. Для указания на то, что замыкание содержит внутренний счетчик, разместим в скобках выражение count = 0 — оно указывает, что переменная count инициализирована целочисленным значением 0. Чтобы позволить ему изменять собственные переменные, мы используем ключевое слово mutable, поскольку в противном случае компилятор не разрешит это сделать:

  auto counter (

    [count = 0] () mutable { return ++count; }

  );

8. Теперь вызовем объект функции пять раз и выведем возвращаемые им значения с целью увидеть, что значение счетчика увеличивается:

  for (size_t i {0}; i < 5; ++i) {

    std::cout << counter() << ", ";

  }

  std::cout << '\n';

9. Мы также можем взять существующие переменные и захватить их по ссылке вместо того, чтобы создавать копию значения для замыкания. Таким образом, значение переменной станет увеличиваться в замыкании и при этом будет доступно за его пределами. Для этого мы поместим в скобках конструкцию &a, где символ & означает, что мы сохраняем ссылку на переменную, но не копию:

  int a {0};

  auto incrementer ( [&a] { ++a; } );

10. Если это работает, то можно вызвать данный объект функции несколько раз, а затем пронаблюдать, действительно ли меняется значение переменной a:

  incrementer();

  incrementer();

  incrementer();

  std::cout

    << "Value of 'a' after 3 incrementer() calls: "

    << a << '\n';

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

  auto plus_ten ( [=] (int x) { return plus(10, x);});

    std::cout << plus_ten(5) << '\n';

}

12. Перед компиляцией и запуском программы пройдем по коду еще раз и попробуем предугадать, какие именно значения выведем в терминале. Затем запустим программу и взглянем на реальные выходные данные:

1, 2

3

ab 3

1, 2, 3, 4, 5,

Value of a after 3 incrementer() calls: 3

15

Как это работает

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

Итак, сначала рассмотрим все особенности, связанные с лямбда-выражениями (рис. 4.1).

Как правило, можно опустить большую часть этих параметров, чтобы сэкономить немного времени. Самым коротким лямбда-выражением является выражение []{}. Оно не принимает никаких параметров, ничего не захватывает и, по сути, ничего не делает.

Что же значит остальная часть?

Список для захвата

Определяет, что именно мы захватываем и выполняем ли захват вообще. Есть несколько способов сделать это. Рассмотрим два «ленивых» варианта.

1. Если мы напишем [=](){...}, то захватим каждую внешнюю переменную, на которую ссылается замыкание, по значению; т.е. эти значения будут скопированы.

2. Запись [&](){...} означает следующее: все внешние объекты, на которые ссылается замыкание, захватываются только по ссылке, что не приводит к копированию.

Конечно, можно установить настройки захвата для каждой переменной отдельно. Запись [a, &b](){...} означает, что переменную a мы захватываем по значению, а переменную b — по ссылке. Для этого потребуется напечатать больше текста, но, как правило, данный способ безопаснее, поскольку мы не можем случайно захватить что-то ненужное из-за пределов замыкания.

В текущем примере мы определили лямбда-выражение следующим образом: [count=0](){...}. В этом особом случае мы не захватываем никаких переменных из-за пределов замыкания, только определили новую переменную с именем count. Тип данной переменной определяется на основе значения, которым мы ее инициализировали, а именно 0, так что она имеет тип int.

Кроме того, можно захватить одни переменные по значению, а другие — по ссылке, например:

□ [a, &b](){...} — копируем a и берем ссылку на b;

□ [&, a](){...} — копируем a и применяем ссылку на любую другую переданную переменную;

□ [=, &b, i{22}, this](){...} — получаем ссылку на b, копируем значение this, инициализируем новую переменную i значением 22 и копируем любую другую использованную переменную.

 Если вы попытаетесь захватить переменную-член некоторого объекта, то не сможете сделать это с помощью конструкции [member_a](){...}. Вместо этого нужно определить либо this, либо *this.

mutable (необязательный)

Если объект функции должен иметь возможность модифицировать получаемые им переменные путем копирования ([=]), то его следует определить как mutable. Это же касается вызова неконстантных методов захваченных объектов.

constexpr (необязательный)

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

Если мы не указываем явно, что лямбда-выражения являются constexpr, но эти выражения соответствуют всем требуемым критериям, то они все равно будут считаться constexpr, только неявно. Если нужно, чтобы лямбда-выражение было constexpr, то лучше явно задавать его таковым, поскольку иначе в случае наших неверных действий компилятор начнет генерировать ошибки.

exception attr (необязательный)

Здесь определяется, может ли объект функции генерировать исключения, если при вызове столкнется с ошибкой.

return type (необязательный)

При необходимости иметь полный контроль над возвращаемым типом, вероятно, не нужно, чтобы компилятор определял его автоматически. В таких случаях можно просто использовать конструкцию [] () -> Foo {}, которая укажет компилятору, что мы всегда будем возвращать объекты типа Foo. 

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

Для реализации задачи можно поместить несколько объектов функции-наблюдателя в вектор, все они будут принимать в качестве параметра переменную типа int, которая представляет наблюдаемое значение. Мы не знаем, что именно станут делать данные функции при вызове, но нам это и неинтересно.

Какой тип будут иметь объекты функций, помещенные в вектор? Нам подойдет тип std::vector<void (*)(int)>, если мы захватываем указатели на функции, имеющие сигнатуры наподобие void f(int);. Данный тип сработает с любым лямбда-выражением, которое захватывает нечто, имеющее совершенно другой тип в сравнении с обычной функцией, поскольку это не просто указатель на функцию, а объект, объединяющий некий объем данных с функцией! Подумайте о временах до появления С++11, когда лямбда-выражений не существовало. Классы и структуры были естественным способом связывания данных с функциями, и при изменении типов членов класса получится совершенно другой класс. Это естественно, что вектор не может хранить значения разных типов, используя одно имя типа.

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

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

Многие проблемы можно решить, не полагаясь исключительно на собственный код. Например, взглянем на то, как решается задача поиска уникальных слов в тексте на языке программирования Haskell. В первой строке определяется функция unique_words, а во второй показывается ее использование на примере строки (рис. 4.2).

Ого! Программа получилась действительно короткой. Не вдаваясь особо в синтаксис языка Haskell, взглянем на то, что делает код. Определяется функция unique_words, в которой к входным данным применяется набор функций. Сначала все символы преобразуются в строчные с помощью map toLower. Таким образом, слова наподобие FOO и foo могут считаться одним словом. Далее функция words разбивает предложение на отдельные слова. Например, из строки "foo bar baz" мы получим массив ["foo", "bar", "baz"]. Следующий шаг — сортировка нового списка слов. В результате последовательность слов ["a", "b", "a"] будет выглядеть как ["a", "a", "b"]. Теперь в дело вступает функция group. Она группирует последовательные слова в списки, т.е. конструкция ["a", "a", "b"] получит вид [["a", "a"], ["b"]]. Задача практически выполнена, и теперь нужно сосчитать, сколько получилось групп одинаковых слов. В этом поможет функция length.

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

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

Как это делается

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

1. Сначала включим несколько заголовочных файлов:

#include <iostream>

#include <functional>

2. Далее реализуем вспомогательную функцию concat, которая принимает множество параметров. Таковыми выступят функции наподобие f, g и h, а результатом будет еще один объект функции, применяющий функции f(g(h(...))) для любых входных данных.

template <typename T, typename ...Ts>

auto concat(T t, Ts ...ts)

{

3. Теперь задача усложняется. Когда пользователь предоставит функции f, g и h, мы оценим это выражение как f(concat(g, h)), которое будет распаковано в f(g(concat(h))), на чем рекурсия остановится, и мы получим выражение f(g(h(...))). Данная цепочка вызовов функций, представляющая конкатенацию пользовательских функций, захватывается лямбда-выражением, которое затем может принять какие-то параметры p и передать в вызов f(g(h(p))). Мы будем возвращать это лямбда-выражение. Конструкция if constexpr проверяет, находимся ли мы на шаге рекурсии, требующем сконкатенировать более чем одну функцию:

  if constexpr (sizeof...(ts) > 0) {

    return [=](auto ...parameters) {

      return t(concat(ts...)(parameters...));

    };

  }

4. Еще одна ветвь конструкции if constexpr будет выбрана компилятором в том случае, если достигнут конец рекурсии. В таких ситуациях просто возвращаем функцию, t, поскольку она является единственным оставшимся параметром:

  else {

    return t;

  }

}

5. Теперь применим нашу новую функцию конкатенации, передав в нее несколько функций. Начнем с функции main, где определим два дешевых объекта функций:

int main()

{

  auto twice ([] (int i) { return i * 2; });

  auto thrice ([] (int i) { return i * 3; });

6. Выполним конкатенацию. Объединим два объекта функций умножения с помощью функции STL std::plus<int>, которая принимает два параметра и возвращает их сумму. Таким образом, получим функцию, выполняющую вызов twice(thrice(plus(a, b ))).

  auto combined (

    concat(twice, thrice, std::plus<int>{})

  );

7. Воспользуемся тем, что получилось. Функция combined теперь выглядит как обычная, и компилятор может объединять эти функции без особых задержек:

  std::cout << combined(2, 3) << '\n';

}

8. Компиляция и запуск программы дадут следующий результат, и он не будет неожиданным, поскольку 2*3*(2+3) равно 30:

$ ./concatenation

30

Как это работает

Самой сложной частью этого раздела является функция concat. Она выглядит очень мудреной, поскольку разворачивает набор параметров ts в другое лямбда-выражение, которое рекурсивно снова вызывает функцию concat, теперь уже с меньшим количеством параметров:

template <typename T, typename Ts>

auto concat(T t, Ts ts)

{

  if constexpr (sizeof...(ts) > 0) {

    return [=](auto ...parameters) {

      return t(concat(ts...)(parameters...));

    };

  } else {

    return [=](auto ...parameters) {

      return t(parameters...);

    };

  }

}

Напишем более простую версию этой функции, которая объединяет ровно три функции:

template <typename F, typename G, typename H>

auto concat(F f, G g, H h)

{

  return [=](auto ... params) {

    return f(g(h(params...)));

  };

}

Эта функция выглядит аналогично, но уже не так сложна. Мы возвращаем лямбда-выражение, которое захватывает f, g и h. Оно принимает произвольно большое количество параметров и просто перенаправляет их по цепочке вызовов f, g и h. Если мы пользуемся конструкцией auto combined(concat(f,g,h)), а затем вызываем данный объект функции с двумя параметрами, например combined(2,3), то 2, 3 представлены набором параметров из предыдущей функции concat.

Повторный взгляд на гораздо более сложную обобщенную функцию concat позволяет увидеть следующее: единственное, что мы действительно делаем по-другому, — выполняем конкатенацию f(g(h(params...))). Вместо этого мы пишем выражение f(concat(g,h))(params...), которое будет преобразовано в конструкцию f(g(concat(h)))(params...) при следующем рекурсивном вызове, а затем — в конструкцию f(g(h(params...))). 

При фильтрации данных с помощью обобщенного кода мы определяем предикаты, которые указывают, какие именно данные нужны. Иногда предикаты являются комбинациями нескольких «собратьев».

При фильтрации строк, например, можно реализовать предикат, который возвращает значение true, если входная строка начинается со слова "foo". Еще один предикат должен возвращать значение true, если входная строка заканчивается словом "bar".

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

 Существует множество задач, чьи решения требуют написания повторяющегося кода. Большую его часть можно легко заменить лямбда-выражениями, и очень просто создать вспомогательную функцию, которая будет оборачивать подобные повторяющиеся задачи.

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

Большинство разработчиков, применяющих std::copy_if и std::transform, могли задаваться вопросом, почему не существует функции std::transform_if. Функция std::copy_if копирует элементы из исходного диапазона по месту назначения, но опускает элементы, не соответствующие определенной пользователем функции-предикату. Функция std::transform безусловно копирует все элементы из исходного диапазона по месту назначения, но при этом преобразует их в процессе. Это происходит с помощью функции, которая определена пользователем и может выполнять как нечто простое (например, умножение чисел), так и полные преобразования к другим типам.

Эти функции существуют достаточно давно, но функции std::transform_ifвсе еще нет. Ее можно легко создать, реализовав функцию, которая итерирует по диапазонам данных и копирует все элементы, соответствующие предикату, выполняя в процессе их преобразование. Однако мы воспользуемся случаем и разберем решение данной задачи с точки зрения лямбда-выражений.

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

Декартово произведение — математическая операция. Она обозначается как A x B, что означает «декартово произведение множества А на множество В». Результатом будет одно множество, содержащее пары всех комбинаций элементов из множеств А и В. Операция, по сути, означает комбинирование каждого элемента из множества А с каждым элементом множества В. Эта операция показана на рис. 4.3.

Согласно схеме, если A = (x,y,z), а B = (1,2,3), то декартово произведение этих множеств будет равно (x,1), (x,2), (x,3), (y,1), (y,2) и т.д.

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

В этом разделе мы реализуем декартово произведение, не используя циклы, но применяя лямбда-выражения и распаковку набора параметров.

Как это делается

В примере мы реализуем объект функции, принимающий функцию f и набор параметров. Объект создаст декартово произведение набора параметров, отфильтрует избыточные части и вызовет для каждой пары функцию f.

1. Включим только тот заголовочный файл STL, который нужен для печати:

#include <iostream>

2. Затем определим простую вспомогательную функцию, которая выводит на экран пару значений, и начнем реализовывать функцию main:

static void print(int x, int y)

{

  std::cout << "(" << x << ", " << y << ")\n";

}

int main()

{

3. Теперь начинается сложная часть. Сначала реализуем вспомогательную функцию для функции cartesian, которую напишем на следующем шаге. Данная функция принимает параметр f, являющийся функцией вывода на экран. Другие ее параметры — это x и набор параметров rest. Они содержат реальные элементы, для которых мы будем искать декартово произведение. Взглянем на выражение f(x,rest): для x=1 и rest=2,3,4 мы получим вызовы f(1,2); f(1,3); f(1,4);. Проверка (x < rest) нужна для избавления от избыточности в сгенерированных парах. Мы рассмотрим этот вопрос более подробно позднее.

  constexpr auto call_cart (

    [=](auto f, auto x, auto ...rest) constexpr {

      (void)std::initializer_list<int>{

        (((x < rest)

          ? (void)f(x, rest)

          : (void)0)

        ,0)...

      };

    });

4. Функция cartesian — самая сложная часть кода всего примера. Она принимает набор параметров xs и возвращает захватывающий его объект функции. Полученный объект функции принимает объект функции f.

Для набора параметров xs=1,2,3 внутреннее лямбда-выражение сгенерирует следующие вызовы: call_cart(f,1,1,2,3); call_cart(f,2,1,2,3); call_cart(f,3,1,2,3);. Из этого набора вызовов можно сгенерировать все необходимые пары произведения.

Обратите внимание: мы дважды используем нотацию ... для распаковки набора параметров xs, что на первый взгляд может показаться странным. Первое включение конструкции ... распаковывает весь набор параметров xs в вызов call_cart. Второе включение приводит к нескольким вызовам функции call_cart, имеющим разные вторые параметры.

  constexpr auto cartesian ([=](auto ...xs) constexpr {

    return [=] (auto f) constexpr {

      (void)std::initializer_list<int> {

        ((void)call_cart(f, xs, xs...), 0)...

      };

    };

  });

5. Теперь сгенерируем декартово произведение для численного множества 1, 2, 3 и выведем полученные пары на экран. Если не учитывать избыточные пары, то мы должны получить следующий результат: (1,2), (2,3) и (1,3). Другие комбинации невозможны при условии, что не важен порядок и не нужны одинаковые числа в паре. Т.е. не нужны пары вроде (1,1), а пары (1,2) и (2,1) считаются одинаковыми.

Сначала сгенерируем объект функции, который содержит все возможные пары и принимает функцию print. Далее используем его, чтобы позволить вызывать данную функцию для всех этих пар. Объявляем переменную print_cart с модификатором constexpr; это позволит гарантировать, что хранимый ею объект функции (и все сгенерированные пары) будет создаваться во время компиляции:

  constexpr auto print_cart(cartesian(1,2,3));

  print_cart(print);

}

6. Компиляция и запуск программы дадут следующий ожидаемый результат. Можно убрать условие (x < xs) из функции call_cart, чтобы увидеть полное декартово произведение, содержащее избыточные пары и пары с одинаковыми номерами:

$ ./cartesian_product

(1, 2)

(1, 3)

(2, 3)

Как это работает

Мы создали еще одну очень сложную конструкцию с помощью лямбда-выражений. Но после того, как разберемся с ней, нас больше не запутают никакие другие лямбда-выражения!

Взглянем на нее более внимательно. Нам следует получить представление о том, что должно произойти (рис. 4.4).

Работа проходит в три шага.

1. Берем наше множество 1, 2, 3 и создаем на его основе три новых. Первая часть каждого из этих множеств — один элемент множества, а вторая — все множества.

2. Объединяем первый элемент с каждым элементом множества и получаем все пары.

3. Из полученных пар выбираем те, которые не являются избыточными (например, пары (1,2) и (2,1) избыточны) и не содержат одинаковых чисел (как, скажем, (1,1)).

Теперь вернемся к реализации:

constexpr auto cartesian ([=](auto ...xs) constexpr {

  return [=](auto f) constexpr {

    (void)std::initializer_list<int> {

      ((void)call_cart(f, xs, xs...), 0)...

    };

  };

});

Внутреннее выражение, call_cart(xs, xs...), явно представляет собой разделение множества (1,2,3) на эти новые множества наподобие 1, [1,2,3]. Полное выражение, ((void)call_cart(f,xs, xs...),0)..., имеющее снаружи дополнительную конструкцию ..., выполняет такое разделение для каждого значения множества, так что мы также получаем множества 2, [1,2,3] и 3, [1,2,3].

Шаги 2 и 3 выполняются с помощью call_cart:

auto call_cart ([](auto f, auto x, auto ...rest) constexpr {

  (void)std::initializer_list<int>{

    (((x < rest)

       ? (void)f(x, rest)

       : (void)0)

    ,0)...

  }

});

Параметр x всегда содержит одно значение, взятое из множества, а rest включает все множество. Опустим условие (x < rest). Здесь выражение f(x, rest) и распакованный набор параметров ... генерируют вызовы функции f(1, 1), f(1, 2) и т.д., что приводит к появлению пар на экране. Это был шаг 2.

Шаг 3 достигается за счет фильтрации всех пар, к которым применяется условие

(x < rest)

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

В этой главе:

□ копирование элементов из одних контейнеров в другие;

□ сортировка контейнеров;

□ удаление конкретных элементов из контейнеров;

□ преобразование содержимого контейнеров;

□ поиск элементов в упорядоченных и неупорядоченных векторах;

□ ограничение допустимых значений вектора конкретным численным диапазоном с помощью std::clamp;

□ определение шаблонов в строках с помощью std::search и выбор оптимальной реализации;

□ выборка данных из крупных векторов;

□ создание перестановок во входных последовательностях;

□ реализация инструмента для слияния словарей. 

Библиотека STL содержит не только структуры данных, но и алгоритмы. В то время как структуры помогают хранить и поддерживать данные разными способами для различных целей, алгоритмы позволяют выполнять конкретные преобразования данных в этих структурах.

Рассмотрим стандартную задачу, например сложение элементов вектора. Это можно без труда сделать с помощью цикла, в котором мы суммируем все элементы вектора и поместим их в переменную-аккумулятор sum:

Большинство важных структур данных STL поддерживают итераторы. Это значит, что вы как минимум сможете получить итераторы с помощью функций begin() и end(), которые указывают на полезные данные и позволяют итерировать по ним. Перебор всегда выглядит одинаково, независимо от того, по какой структуре данных выполняется.

Можно получить итераторы для векторов, списков, двунаправленных очередей, ассоциативных массивов и т.д. С помощью адаптеров итераторов мы можем получить итераторы для файлов, а также стандартных потоков ввода и вывода. Более того, как вы видели в предыдущей главе, можно даже обернуть интерфейсы итераторов вокруг алгоритмов. Теперь, когда итераторы помогают нам получить доступ ко всему, можно объединить их с алгоритмами STL, которые принимают итераторы в качестве параметров.

На примере алгоритма std::copy можно легко понять, как итераторы помогают абстрагировать природу разных структур данных. Он просто копирует элементы из одного набора итераторов в итератор вывода. При использовании подобных алгоритмов не нужно знать о природе структуры данных, с которой мы работаем.

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

Поскольку данную задачу уже когда-то решили, программисты не должны снова тратить на нее время; разве что для обучения.