STL: стандартная библиотека шаблонов С

    Статьи , 25 декабря 2014 в 18:04

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

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

Первое знакомство

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

Коллекции

Для использования коллекции в своем коде используйте следующую директиву:

#include ,
где T — название коллекции

Итак, наиболее часто используются:

  • vector — коллекция элементов, сохраненных в массиве, изменяющегося по мере необходимости размера (обычно, увеличивающегося);
  • list — коллекция, хранящая элементы в виде двунаправленного связанного списка;
  • map — коллекция, сохраняющая пары вида , т.е. каждый элемент — это пара вида , при этом однозначная (каждому ключу соответствует единственное значение), где ключ — некоторая характеризующая значение величина, для которой применима операция сравнения; пары хранятся в отсортированном виде, что позволяет осуществлять быстрый поиск по ключу, но за это, естественно, придется заплатить: придется так реализовывать вставку, чтобы условие отсортированности не нарушилось;
  • set — это отсортированная коллекция одних только ключей, т.е. значений, для которых применима операция сравнения, при этом уникальных — каждый ключ может встретиться во множестве (от англ. set — множество) только один раз;
  • multimap — map , в котором отсутствует условие уникальности ключа, т.е. если вы произведете поиск по ключу, то получите не единственное значение, а набор элементов с одинаковым значением ключа; для использования в коде используется #include ;
  • multiset — коллекция с тем же отличием от set’а, что и multimap от map’а, т.е. с отсутствием условия уникальности ключа; для подключения: #include .

Строки

Любая серьезная библиотека имеет свои классы для представления строк. В STL строки представляются как в формате ASCII, так и Unicode:
string — коллекция однобайтных символов в формате ASCII;
wstring — коллекция двухбайтных символов в формате Unicode; включается командой #include .

Строковые потоки

strstream — используются для организации STL-строкового сохранения простых типов данных.
Разбор примеров начнем именно с этого класса.

Строковый поток — это буфер с нуль-терминатором в конце, поэтому при первой распечатке в конце строки оказывается мусор, т.е. получить реальный конец можно не посредством нуль-терминатора, а получив счетчик: pcount() . Затем “реальная часть” потока копируется в новую строку, и мы получаем распечатку уже без мусора.

Итераторы

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

Вот несколько формализованных определений итератора:

  • Итераторы обеспечивают доступ к элементам коллекции
  • Для каждого конкретного класса STL итераторы определяются отдельно внутри класса этой коллекции.

Существуют три типа итераторов:

  • (forward) iterator — для обхода коллекции от меньшего индекса к большему;
  • reverse iterator — для обхода коллекции от большего индекс к меньшему;
  • random access iterator — для обхода коллекции в любом направлении.

Вот пример использования итераторов для удаления половин элементов коллекции:

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

25 июня в 12:00 в 12:00, онлайн, беcплатно

Итерация вперед и аналогично назад происходит так:
for (iterator element = begin (); element

При использовании random access iterator, например, так:
for (iterator element = begin (); element

Методы коллекций

Основными методами, присутствующими почти во всех коллекциях являются следующие:

  • empty — определяет, пуста ли коллекция;
  • size — возвращает размер коллекции;
  • begin — возвращает прямой итератор, указывающий на начало коллекции;
  • end — возвращает прямой итератор, указывающий на конец коллекции, т.е. на несуществующий элемент, идущий после последнего;
  • rbegin — возвращает обратный итератор на начало коллекции;
  • rend — возвращает обратный итератор на конец коллекции;
  • clear — очищает коллекцию, т.е. удаляет все ее элементы;
  • erase — удаляет определенные элементы из коллекции;
  • capacity — возвращает вместимость коллекции, т.е. количество элементов, которое может вместить эта коллекция (фактически, сколько памяти под коллекцию выделено);

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

Vector

Самая часто используемая коллекция — это вектор. Очень удобно, что у этой коллекции есть такой же оператор operator [] , что и у обычного массива. Такой же оператор есть и у коллекций map , deque , string и wstring .

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

Алгоритмы

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

  • Методы перебора всех элементов коллекции и их обработки: count , count_if , find , find_if , adjacent_find , for_each , mismatch , equal , search copy , copy_backward , swap , iter_swap , swap_ranges , fill , fill_n , generate , generate_n , replace , replace_if , transform , remove , remove_if , remove_copy , remove_copy_if , unique , unique_copy , reverse , reverse_copy , rotate , rotate_copy , random_shuffle , partition , stable_partition
  • Методы сортировки коллекции: sort , stable_sort , partial_sort , partial_sort_copy , nth_element , binary_search , lower_bound , upper_bound , equal_range , merge , inplace_merge , includes , set_union , set_intersection , set_difference , set_symmetric_difference , make_heap , push_heap , pop_heap , sort_heap , min , max , min_element , max_element , lexographical_compare , next_permutation , prev_permutation
  • Методы выполнения определенных арифметических операций над членами коллекций: Accumulate , inner_product , partial_sum , adjacent_difference

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

Предикаты

Для многих алгоритмов STL можно задать условие, посредством которого алгоритм определит, что ему делать с тем или иным членом коллекции. Предикат — это функция, которая принимает несколько параметров и возвращает логическое значение (истина/ложь). Существует и набор стандартных предикатов.

Потокобезопасность

Важно понимать, что STL — не потокобезопасная библиотека. Но решить эту проблему очень просто: если два потока используют одну коллекцию, просто реализуйте критическую секцию и Mutex .

Заключение

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

STL: стандартная библиотека шаблонов С++

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

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

Первое знакомство

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

Коллекции

Для использования коллекции в своем коде используйте следующую директиву:

#include ,
где T — название коллекции

Итак, наиболее часто используются:

  • vector — коллекция элементов, сохраненных в массиве, изменяющегося по мере необходимости размера (обычно, увеличивающегося);
  • list — коллекция, хранящая элементы в виде двунаправленного связанного списка;
  • map — коллекция, сохраняющая пары вида , т.е. каждый элемент — это пара вида , при этом однозначная (каждому ключу соответствует единственное значение), где ключ — некоторая характеризующая значение величина, для которой применима операция сравнения; пары хранятся в отсортированном виде, что позволяет осуществлять быстрый поиск по ключу, но за это, естественно, придется заплатить: придется так реализовывать вставку, чтобы условие отсортированности не нарушилось;
  • set — это отсортированная коллекция одних только ключей, т.е. значений, для которых применима операция сравнения, при этом уникальных — каждый ключ может встретиться во множестве (от англ. set — множество) только один раз;
  • multimap — map , в котором отсутствует условие уникальности ключа, т.е. если вы произведете поиск по ключу, то получите не единственное значение, а набор элементов с одинаковым значением ключа; для использования в коде используется #include ;
  • multiset — коллекция с тем же отличием от set’а, что и multimap от map’а, т.е. с отсутствием условия уникальности ключа; для подключения: #include .

Строки

Любая серьезная библиотека имеет свои классы для представления строк. В STL строки представляются как в формате ASCII, так и Unicode:
string — коллекция однобайтных символов в формате ASCII;
wstring — коллекция двухбайтных символов в формате Unicode; включается командой #include .

Строковые потоки

strstream — используются для организации STL-строкового сохранения простых типов данных.
Разбор примеров начнем именно с этого класса.

Строковый поток — это буфер с нуль-терминатором в конце, поэтому при первой распечатке в конце строки оказывается мусор, т.е. получить реальный конец можно не посредством нуль-терминатора, а получив счетчик: pcount() . Затем «реальная часть» потока копируется в новую строку, и мы получаем распечатку уже без мусора.

Итераторы

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

Вот несколько формализованных определений итератора:

  • Итераторы обеспечивают доступ к элементам коллекции
  • Для каждого конкретного класса STL итераторы определяются отдельно внутри класса этой коллекции.

Существуют три типа итераторов:

  • (forward) iterator — для обхода коллекции от меньшего индекса к большему;
  • reverse iterator — для обхода коллекции от большего индекс к меньшему;
  • random access iterator — для обхода коллекции в любом направлении.

Вот пример использования итераторов для удаления половин элементов коллекции:

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

Итерация вперед и аналогично назад происходит так:
for (iterator element = begin (); element

При использовании random access iterator, например, так:
for (iterator element = begin (); element

Методы коллекций

Основными методами, присутствующими почти во всех коллекциях являются следующие:

  • empty — определяет, пуста ли коллекция;
  • size — возвращает размер коллекции;
  • begin — возвращает прямой итератор, указывающий на начало коллекции;
  • end — возвращает прямой итератор, указывающий на конец коллекции, т.е. на несуществующий элемент, идущий после последнего;
  • rbegin — возвращает обратный итератор на начало коллекции;
  • rend — возвращает обратный итератор на конец коллекции;
  • clear — очищает коллекцию, т.е. удаляет все ее элементы;
  • erase — удаляет определенные элементы из коллекции;
  • capacity — возвращает вместимость коллекции, т.е. количество элементов, которое может вместить эта коллекция (фактически, сколько памяти под коллекцию выделено);

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

Vector

Самая часто используемая коллекция — это вектор. Очень удобно, что у этой коллекции есть такой же оператор operator [] , что и у обычного массива. Такой же оператор есть и у коллекций map , deque , string и wstring .

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

Алгоритмы

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

  • Методы перебора всех элементов коллекции и их обработки: count , count_if , find , find_if , adjacent_find , for_each , mismatch , equal , search copy , copy_backward , swap , iter_swap , swap_ranges , fill , fill_n , generate , generate_n , replace , replace_if , transform , remove , remove_if , remove_copy , remove_copy_if , unique , unique_copy , reverse , reverse_copy , rotate , rotate_copy , random_shuffle , partition , stable_partition
  • Методы сортировки коллекции: sort , stable_sort , partial_sort , partial_sort_copy , nth_element , binary_search , lower_bound , upper_bound , equal_range , merge , inplace_merge , includes , set_union , set_intersection , set_difference , set_symmetric_difference , make_heap , push_heap , pop_heap , sort_heap , min , max , min_element , max_element , lexographical_compare , next_permutation , prev_permutation
  • Методы выполнения определенных арифметических операций над членами коллекций: Accumulate , inner_product , partial_sum , adjacent_difference

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

Предикаты

Для многих алгоритмов STL можно задать условие, посредством которого алгоритм определит, что ему делать с тем или иным членом коллекции. Предикат — это функция, которая принимает несколько параметров и возвращает логическое значение (истина/ложь). Существует и набор стандартных предикатов.

Потокобезопасность

Важно понимать, что STL — не потокобезопасная библиотека. Но решить эту проблему очень просто: если два потока используют одну коллекцию, просто реализуйте критическую секцию и Mutex .

Заключение

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

Книга «С++17 STL. Стандартная библиотека шаблонов»

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

Далее представлен отрывок «Лямбда-выражения».

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

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

Экземпляры структуры name_greeter, очевидно, содержат строку. Обратите внимание: тип этой структуры и объект не являются безымянными, в отличие от лямбда-выражений. С точки зрения замыканий можно утверждать, что они захватывают строку. Когда экземпляр-пример вызывается как функция без параметров, на экран выводится строка «Hello, John Doe», поскольку мы указали строку с таким именем.

Начиная с С++11 создавать подобные замыкания стало проще:

На этом все. Целая структура name_greeter заменяется небольшой конструкцией [] < /* сделать что-то */ >, которая на первый взгляд выглядит странно, но уже в следующем разделе мы рассмотрим все возможные случаи ее применения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, сначала рассмотрим все особенности, связанные с лямбда-выражениями (рис. 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 и копируем любую другую использованную переменную.

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

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

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

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

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

Добавляем полиморфизм путем оборачивания лямбда-выражений в std::function

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

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

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

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

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

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

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

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

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

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

4. В функции main мы создадим объекты классов deque, list и vector, каждый из которых будет хранить целые числа:

5. Сейчас воспользуемся функцией consumer для работы с нашими экземплярами контейнеров d, l и v: создадим для них объекты-потребители функций и поместим их в экземпляр vector. Эти объекты функций будут захватывать ссылку на один из объектов контейнера. Последние имеют разные типы, как и объекты функций. Тем не менее вектор хранит экземпляры типа std::function . Все объекты функций неявно оборачиваются в объекты типа std::function, которые затем сохраняются в векторе:

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

7. Все три контейнера теперь должны содержать одинаковые десять чисел. Выведем на экран их содержимое:

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

Для Хаброжителей скидка 25% по купону — С++17 STL

Лабораторная работа №8:
Стандартная библиотека шаблонов (STL)

Цель работы: изучить правила работы со стандартными шаблонами в С++.

Теоретические сведения

Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

Стандартная библиотека шаблонов до включения в стандарт C++ была сторонней разработкой, в начале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода/вывода (iostream), подраздел Си и др.).

Проект под названием STLPort, основанный на SGI STL, осуществляет постоянное обновление STL, iostream и строковых классов. Некоторые другие проекты также занимаются разработкой частных применений стандартной библиотеки для различных конструкторских задач. Каждый производитель компиляторов C++ обязательно поставляет какую-либо реализацию этой библиотеки, так как она является очень важной частью стандарта и широко используется. Архитектура STL была разработана Александром Степановым и Менгом Ли.

В библиотеке выделяют пять основных компонентов:

  • Контейнер (англ. container) — хранение набора объектов в памяти.
  • Итератор (англ. iterator) — обеспечение средств доступа к содержимому контейнера.
  • Алгоритм (англ. algorithm) — определение вычислительной процедуры.
  • Адаптер (англ. adaptor) — адаптация компонентов для обеспечения различного интерфейса.
  • Функциональный объект (англ. functor) — сокрытие функции в объекте для использования другими компонентами.

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

Контейнеры

Контейнеры библиотеки STL можно разделить на четыре категории: последовательные, ассоциативные, контейнеры-адаптеры и псевдоконтейнеры.

Последовательные контейнеры
vector C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за . Добавление-удаление элемента в конец vector занимает амортизированное время, та же операция в начале или середине vector — . Стандартная быстрая сортировка за . Поиск элемента перебором занимает . Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.
list Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из-за большего времени доступа к элементу. Доступ по индексу за . В любом месте контейнера вставка и удаление производятся очень быстро — за .
deque Дэк. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за . Реализован в виде двусвязанного списка линейных массивов. С другой стороны, в отличие от vector, дек не гарантирует расположение всех своих элементов в непрерывном участке памяти, что делает невозможным безопасное использование арифметики указателей для доступа к элементам контейнера.
Ассоциативные контейнеры
Set Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator Контейнеры-адаптеры
stack Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.
queue Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.
priority_queue Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.
Псевдоконтейнеры
bitset Служит для хранения битовых масок. Похож на vector фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.
basic_string Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности. Элементы должны быть простых (фундаментальных) типов данных. Определена конкатенация с помощью +.
valarray Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Определены операции над двумя valarray и над valarray и скаляром (поэлементные). Эти операции возможно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками SIMD.

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

Метод Описание Примечание
Конструктор копии Создает новый элемент, идентичный старому Используется при каждой вставке элемента в контейнер
Оператор присваивания Заменяет содержимое элемента копией исходного элемента Используется при каждой модификации элемента
Деструктор Разрушает элемент Используется при каждом удалении элемента
Конструктор по умолчанию Создает элемент без аргументов Применяется только для определенных операций
operator== Сравнивает два элемента Используется при выполнении operator== для двух контейнеров
operator

C();

Результат не используется Линейная После: a.size() == 0.
obj.begin() Постоянная
obj.end() Постоянная
obj1 == obj2 Обратимый в bool Линейная
obj1 != obj2 Обратимый в bool Линейная
obj.size() size_type Зависит от типа Не рекомендуется применять для проверки, пуст ли контейнер
obj.empty() Обратимый в bool Постоянная
obj1 obj2 Обратимый в bool Линейная
obj1 = obj2 Обратимый в bool Линейная
obj.swap(obj2) void Постоянная

Итераторы

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

Александр Степанов — РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

99 Пожалуйста дождитесь своей очереди, идёт подготовка вашей ссылки для скачивания.

Скачивание начинается. Если скачивание не началось автоматически, пожалуйста нажмите на эту ссылку.

Описание книги «РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)»

Описание и краткое содержание «РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)» читать бесплатно онлайн.

РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Стандартная Библиотека Шаблонов предоставляет набор хорошо сконструированных и согласованно работающих вместе обобщённых компонентов C++. Особая забота была проявлена для обеспечения того, чтобы все шаблонные алгоритмы работали не только со структурами данных в библиотеке, но также и с встроенными структурами данных C++. Например, все алгоритмы работают с обычными указателями. Ортогональный проект библиотеки позволяет программистам использовать библиотечные структуры данных со своими собственными алгоритмами, а библиотечные алгоритмы — со своими собственными структурами данных. Хорошо определённые семантические требования и требования сложности гарантируют, что компонент пользователя будет работать с библиотекой и что он будет работать эффективно. Эта гибкость обеспечивает широкую применимость библиотеки.

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

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

Библиотека содержит пять основных видов компонентов:

— алгоритм (algorithm): определяет вычислительную процедуру.

— контейнер (container): управляет набором объектов в памяти.

— итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.

— функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.

— адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

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

Следующее описание разъясняет структуру библиотеки. Если программные компоненты сведены в таблицу как трёхмерный массив, где одно измерение представляет различные типы данных (например, int, double), второе измерение представляет различные контейнеры (например, вектор, связный список, файл), а третье измерение представляет различные алгоритмы с контейнерами (например, поиск, сортировка, перемещение по кругу), если i, j и k — размеры измерений, тогда должно быть разработано i* j *k различных версий кода. При использовании шаблонных функций, которые берут параметрами типы данных, нам нужно только j * k версий. Далее, если заставим наши алгоритмы работать с различными контейнерами, то нам нужно просто j+k версий. Это значительно упрощает разработку программ, а также позволяет очень гибким способом использовать компоненты в библиотеке вместе с определяемыми пользователем компонентами. Пользователь может легко определить специализированный контейнерный класс и использовать для него библиотечную функцию сортировки. Для сортировки пользователь может выбрать какую-то другую функцию сравнения либо через обычный указатель на сравнивающую функцию, либо через функциональный объект (объект, для которого определён operator()), который сравнивает. Если пользователю необходимо выполнить передвижение через контейнер в обратном направлении, то используется адаптер reverse_iterator.

Библиотека расширяет основные средства C++ последовательным способом, так что программисту на C/C++ легко начать пользоваться библиотекой. Например, библиотека содержит шаблонную функцию merge (слияние). Когда пользователю нужно два массива a и b объединить в с, то это может быть выполнено так:

merge(a, a+1000, b, b+2000, c);

Когда пользователь хочет объединить вектор и список (оба — шаблонные классы в библиотеке) и поместить результат в заново распределённую неинициализированную память, то это может быть выполнено так:

Employee* с = allocate(a.size() + b.size(), (Employee*)0);

merge(a.begin(), a.end(), b.begin(), b.end(), raw_storage_iterator‹Employee*, Employee›(c));

где begin() и end() — функции-члены контейнеров, которые возвращают правильные типы итераторов или указателе-подобных объектов, позволяющие merge выполнить задание, а raw_storage_iterator — адаптер, который позволяет алгоритмам помещать результаты непосредственно в неинициализированную память, вызывая соответствующий конструктор копирования.

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

main(int argc, char** argv) <

if (argc!= 2) throw(«usage: remove_if_divides integern «);

remove_copy_if(istream_iterator‹int›(cin), istream_iterator‹int›(), ostream_iterator‹int›(cout, «n»), not1(bind2nd(modulus‹int›(), atoi(argv[1]))));

Вся работа выполняется алгоритмом remove_copy_if, который читает целые числа одно за другим, пока итератор ввода не становится равным end-of-stream (конец-потока) итератору, который создаётся конструктором без параметров. (Вообще все алгоритмы работают способом «отсюда досюда», используя два итератора, которые показывают начало и конец ввода.) Потом remove_copy_if записывает целые числа, которые выдерживают проверку, в выходной поток через итератор вывода, который связан с cout. В качестве предиката remove_copy_if использует функциональный объект, созданный из функционального объекта modulus‹int›, который берёт i и j и возвращает i % j как бинарный предикат, и превращает в унарный предикат, используя bind2nd, чтобы связать второй параметр с параметром командной строки atoi(argv[1]). Потом отрицание этого унарного предиката получается с помощью адаптера функции not1.

Несколько более реалистичный пример — фильтрующая программа, которая берёт файл и беспорядочно перетасовывает его строки.

main(int argc, char**) <

if (argc!= 1) throw(«usage: shufflen»);

copy(istream_iterator‹string›(cin), istream_iterator‹string›(), inserter(v, v.end()));

copy(v.begin(), v.end(), ostream_iterator‹string›(cout));

В этом примере copy перемещает строки из стандартного ввода в вектор, но так как вектор предварительно не размещён в памяти, используется итератор вставки, чтобы вставить в вектор строки одну за другой. (Эта методика позволяет всем функциям копирования работать в обычном режиме замены также, как в режиме вставки.) Потом random_shuffle перетасовывает вектор, а другой вызов copy копирует его в поток cout.

Для гарантии совместной работы различные компоненты библиотеки должны удовлетворять некоторым основным требованиям. Требования должны быть общими, насколько это возможно, так что вместо высказывания «класс X должен определить функцию-член operator++() «, мы говорим «для любого объекта x класса X определён ++x «. (Не определено, является ли оператор членом или глобальной функцией.) Требования установлены в терминах чётких выражений, которые определяют допустимые условия типов, удовлетворяющих требованиям. Для каждого набора требований имеется таблица, которая определяет начальный набор допустимых выражений и их семантику. Любой обобщённый алгоритм, который использует требования, должен быть написан в терминах допустимых выражений для своих формальных параметров.

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

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

Adblock
detector