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


Оглавление (нажмите, чтобы открыть):

The C++ Standard Template Library (STL)

The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as lists, stacks, arrays, etc. It is a library of container classes, algorithms, and iterators. It is a generalized library and so, its components are parameterized. A working knowledge of template classes is a prerequisite for working with STL.

STL has four components

Algorithms

The header algorithm defines a collection of functions especially designed to be used on ranges of elements.They act on containers and provide means for various operations for the contents of the containers.

Containers or container classes store objects and data. There are in total seven standard “first-class” container classes and three container adaptor classes and only seven header files that provide access to these containers or container adaptors.

  • Sequence Containers: implement data structures which can be accessed in a sequential manner.
    • vector
    • list
    • deque
    • arrays
    • forward_list( Introduced in C++11)
  • Container Adaptors : prov >O(log n) complexity).
    • set
    • multiset
    • map
    • multimap
  • Unordered Associative Containers : implement unordered data structures that can be quickly searched
    • unordered_set (Introduced in C++11)
    • unordered_multiset (Introduced in C++11)
    • unordered_map (Introduced in C++11)
    • unordered_multimap (Introduced in C++11)

Functions

The STL includes classes that overload the function call operator. Instances of such classes are called function objects or functors. Functors allow the working of the associated function to be customized with the help of parameters to be passed.

Iterators

As the name suggests, iterators are used for working upon a sequence of values. They are the major feature that allow generality in STL.

Utility Library

References:

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

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

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

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

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

Контейнеры

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

Контейнер Описание
Последовательные контейнеры
vector C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за . Добавление-удаление элемента в конец vector занимает амортизированное время, та же операция в начале или середине vector — . Стандартная быстрая сортировка за . Поиск элемента перебором занимает . Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения элементов в виде битов, однако она не поддерживает всех возможностей работы с итераторами.
list Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из-за большего времени доступа к элементу. Доступ по индексу за . В любом месте контейнера вставка и удаление производятся очень быстро — за .
deque Дэк. Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за . Реализован в виде двусвязанного списка линейных массивов. С другой стороны, в отличие от vector, дек не гарантирует расположение всех своих элементов в непрерывном участке памяти, что делает невозможным безопасное использование арифметики указателей для доступа к элементам контейнера.
Ассоциативные контейнеры
set Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.
multiset То же что и set, но позволяет хранить повторяющиеся элементы.
map Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator , либо требуется предоставить функцию-компаратор.
multimap То же что и map, но позволяет хранить несколько одинаковых ключей.
Контейнеры-адаптеры
stack Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.
queue Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.
priority_queue Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.
Псевдоконтейнеры
bitset Служит для хранения битовых масок. Похож на vector фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.
basic_string Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности. Элементы должны быть POD’ами. Определена конкатенация с помощью +.
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++ определяет пять категорий итераторов, описанных в следующей таблице:

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

C++17 STL. Стандартная библиотека шаблонов — С++ — объектно-ориентированный язык программирования, без которого сегодня немыслима промышленная разработка ПО. В этой замечательной книге описана работа с контейнерами, алгоритмами, вспомогательными классами, лямбда-выражениями и другими интересными инструментами, которыми богат современный С++.

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

Скачать книгу C++17 STL. Стандартная библиотека шаблонов (10,02 МБ):

Компьютерные технологии (архив 2012г.)

Лекция 4 — Стандартная библиотека С++. Standard Template Library (STL). Класс vector.

Стандартная библиотека С++. Standard Template Library (STL).

Последовательные контейнеры (Sequence containers).

Исходники в Linux лежат — /usr/include/c++/версия/

Container class templates

array — Array >(class template ) vector — Vector (class template ) deque — Double ended queue (class template ) forward_list — Forward list (class template ) list — List (class template )

Методы последовательных контейнеров

Оцените новость / программу!
4,3 из 5, всего оценок — 6
Headers
Members array vector deque forward_list list
constructor implicit vector deque forward_list list
destructor implicit

list

operator= implicit operator= operator= operator= operator=
iterators begin begin begin begin begin before_begin begin
end end end end end end
rbegin rbegin rbegin rbegin rbegin
rend rend rend rend rend
const iterators begin cbegin cbegin cbegin cbegin cbefore_begin cbegin
cend cend cend cend cend cend
crbegin crbegin crbegin crbegin crbegin
crend crend crend crend crend
capacity size size size size size
max_size max_size max_size max_size max_size max_size
empty empty empty empty empty empty
resize resize resize resize resize
shrink_to_fit shrink_to_fit shrink_to_fit
capacity capacity
reserve reserve
element access front front front front front front
back back back back back
operator[] operator[] operator[] operator[]
at at at at
modifiers assign assign assign assign assign
emplace emplace emplace emplace_after emplace
insert insert insert insert_after insert
erase erase erase erase_after erase
emplace_back emplace_back emplace_back emplace_back
push_back push_back push_back push_back
pop_back pop_back pop_back pop_back
emplace_front emplace_front emplace_front emplace_front
push_front push_front push_front push_front
pop_front pop_front pop_front pop_front
clear clear clear clear clear
swap swap swap swap swap swap
list operations splice splice_after splice
remove remove remove
remove_if remove_if remove_if
unique unique unique
merge merge merge
sort sort sort
reverse reverse reverse
observers get_allocator get_allocator get_allocator get_allocator get_allocator
data data data

vector

«безопасный», динамический массив

Операции c вектором:

  • добавить/удалить элемент О(1)*;
  • добавить/удалить элемент в «середину» O(n);
  • поиск элемента O(n);
  • произвольный доступ ДА.

§1 Обзор стандартной библиотеки языка C++ (STD)

Стандартная библиотека C++

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

Александр Александрович Степанов

при этом обычное “расширение” в имени заголовочных файлов ( «.h» ) отбрасывается.
Примечание. На первом уроке в 10 классе мы акцентировали ваше внимание на том, что полной совместимости между языками C и C++ не существует. В современном стандарте языка C++ появилось много вещей, которые не будут работать в языке Си, равно как и многие вещи принятые в Си перестали работать в С++. Например (далеко неполный список):

Таким образом, использовать библиотеки языка Си вы можете, но писать совместимый код на современном С++ не получится. В языке Си не существуют классы динамических контейнеров, которые освобождают память в автоматическом режиме. Динамические массивы в Си нужно создавать “вручную” с помощью библиотечных функций malloc , free и realloc . (В C++ поддерживаются функции работы с памятью из стандартной библиотеки Си, но их использование не рекомендуется). В продолжении нашего курса мы практически не обращаемся к библиотеке языка Си (за исключением cmath и ctime ).

Основные компоненты STD:
    Language support library (языковая поддержка) Diagnostics library (исключения) General utilities library (утилиты) Strings library (строки) Localization library (локализация) Containers library (контейнеры) Iterators library (итераторы) Algorithms library (алгоритмы) Numerics library (числа) Input/output library (ввод/вывод) Regular expressions library (регулярные выражения) Atomic operations library (атомарные операции) Thread support library (многопоточность)

Часть STD, рассматриваемая как STL

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

В STL выделяют пять основных компонентов:
    Контейнер (container) Итератор (iterator) Алгоритм (algorithm) Адаптер (adaptor) Функциональный объект (functor)

Контейнеры

Контейнеры — это специализированные классы, предназначенные для хранения коллекции однотипных объектов и обеспечения доступа к этим объектам. Контейнер – это структура данных похожая на массив. Контейнер управляет выделяемой для его элементов памятью и предоставляет функции-члены для доступа к ним, либо непосредственно, либо через итераторы. Конструкторы контейнеров имеют дополнительный специальный аргумент allocator (распределитель). Аллокатор инкапсулирует (т. е. скрывает) реализацию выделения и освобождения памяти. Аллокатором по умолчанию является шаблон std::allocator (если не определен пользовательский распределитель). В качестве инструментов выделения и освобождения памяти этот аллокатор использует стандартные операции new и delete . Для различных контейнеров имеются как общие, так и специфичные операции, применимые только для данного вида коллекции объектов. Разные контейнеры обеспечивают различную эффективность тех или иных операций. Выбор оптимального контейнера для конкретного случая зависит не только от предоставляемой функциональности, но и от его эффективности при различных рабочих нагрузках. Контейнеры подразделяются на следующие виды:

    Последовательные контейнерыАссоциативные контейнерыКонтейнеры-адаптерыПсевдоконтейнеры
Последовательные контейнеры

В последовательных контейнерах элементы располагаются последовательно, один за другим. Позиция зависит от времени и места вставки, но не связана со значением элемента. Каждый элемент контейнера имеет свой индекс (за исключением контейнера list ); как и в массивах, отсчет начинается с «0» . Но, в отличие от C-массивов, имеющих фиксированный размер, последовательные контейнеры – динамические массивы (за исключением контейнера array ). К последовательным контейнерам относятся классы:

    arrayvectordeque list forward_list

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

Ассоциативные контейнеры

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

Класс set (множество) представляет собой упорядоченный контейнер, соответствующий математическому понятию множества. set хранит упорядоченное множество уникальных ключей (или просто – значений).
Класс map (словарь) реализует упорядоченный ассоциативный массив пар элементов, состоящих из уникальных ключей и соответствующих им значений. Контейнеры multiset и multimap допускают существование нескольких ключей с одинаковым значением.
Помимо упорядоченных ассоциативных контейнеров, имеются неупорядоченные структуры данных (хеш-массивы) с возможностью быстрого поиска:

    unordered_set unordered_map unordered_multiset unordered_multimap
Контейнеры-адаптеры

Контейнеры-адаптеры (container adaptor) — это обёртки над другими контейнерами, предоставляющие особые наборы операций. Оборачиваемый контейнер может быть задан как дополнительный параметр шаблона. Если параметр не задан, будет использоваться, специфический для адаптера, контейнер по умолчанию. К контейнерам-адаптерам относятся:

    stackqueue priority_queue

Контейнер stack (стек) реализует структуру данных в которой элементы добавляются и удаляются в вершине стека (т. е. с одного конца). Массив элементов, организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Контейнер queue (очередь) реализует структуру данных в которой добавление элемента возможно только в конец очереди, а выборка — из начала очереди, при этом выбранный элемент из очереди удаляется.
Контейнер priority_queue (очередь с приоритетами) поддерживает операции, аналогичные классу stack, но вставка элементов предполагает их неявную сортировку, так что операция извлечения элемента извлекает всегда минимальный (или максимальный, если определена соответствующая функция сравнения) элемент коллекции.

Псевдо-контейнеры

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

Интеллектуальные указатели

В контейнерах, для хранения элементов, используется семантика передачи объектов по значению. Другими словами, при добавлении, контейнер получает копию элемента. Следовательно, может возникнуть перерасход памяти. Если создание копии нежелательно, то используют контейнер указателей на элементы. Присвоение элементов реализуется с помощью операции присваивания, а их уничтожение происходит с использованием деструктора. Но в этом таится опасность. Например, не совпадают время жизни объекта и время жизни указателя на этот объект, возникают утечки памяти. Чтобы избежать таких проблем используются интеллектуальные (умные) указатели. “Интеллектуальными” они называются так потому, что позволяют избежать, выше упомянутых, проблем. Однако, они не дают 100% гарантии, что не появятся подобные проблемы в результате непродуманности алгоритма. Существует два основных типа умных указателей:

    shared_ptr unique_ptr

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

Библиотека STL (Standart Template Library)

Written on 01 Января 2007 . Posted in Visual C++

ОГЛАВЛЕНИЕ

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

Пробуем

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

Создаем проект Win 32 Console с именем StlStep2 как Hello Word. И пишем код.

Ну как ? Много нового? Все новое. Вместе с VC++ поставляються и все необходимые файлы для работы с STL при этом есть некоторые особенности, например, Вы заметили, что при объявлении vector не использовалось расширение *.h. Его можно не использовать, но кроме того его и нет. Данный файл идет без расширения.

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

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


Пространство имен

Пространство имен namespace это новый элемент языка и для работы с STL мы обязаны принять его во внимание. Этот элемент создан для программ созданых из многих файлов, в которых есть опасность конфликта имен.

Объявляется пространство имен командой namespace:

Для использования рабочей области применяется команда using namespace:

Посмотрим ? Создавайте проект Win32 Console, как Hello Word с именем TestNameSpace. И код. Объявляем различные области.

А вот так они используются.

Запустите посмотрите результат. Все работает как часы.

Шаблоны функций — основа STL

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

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

Для типа int и double. Что делается классически . Пишутся две функции. Например так:

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

Шаблон начинается словом template, после описания фигурные скобки:

Обратите внимание на return. Это именно шаблон функции, а не шаблон класса.

Шаблоны классов

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

Ну, а теперь с шаблоном .

Ну как . Впечатляет . Обратите внимание на Funct cI(25); именно здесь задается тип класса. Это немного непревычно.

Компоненты STL

В STL большое количество шаблонов, как классов так и функций. Мы можем их использовать с ООП или без него. Вообщем как хотим. Но в STL есть 3 основные компоненты.

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

  1. Входные
  2. Выходные
  3. Однонаправленные
  4. Двунаправленные
  5. Произвольного доступа

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

  • vector — линейный массив
  • list — двухсвязанный список
  • deque — очередь с двухсторонгим доступом
  • set — ассоциативный массив уникальных ключей
  • multiset — ассоциативный массив с возможность дублирования ключей
  • map — ассоциативный массив с уникальными ключами и значениями
  • multimap — ассоциативный массив с возможность дублирования ключей и значений
  • stack — структура данных типа стек
  • queue — структура данных типа очередь

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

Знакомимся с вектором

Вектор (vector) напоминает нам массив, только он способен расти до произвольного размера, поддерживает информацию о размере. Как и массив к вектору можно обратить воспользовавшись операцией индексирования []. Вот характеристики:

  • Доступ к данных с одинаковой скоростью
  • Вставка приводит к перемещению элементов
  • При расширении данные копируються в другой блок

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

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

Объявить рабочую область:

После этого вектор необходимо объявить, это можно сделать двумя способами.

В первом случае указывается пустой вектор, а во втором начальный размер.

Можно получать информацию о параметрах вектора:

  • size() — сколько данных храниться
  • capacity() — сколько может храниться до изменения размера
  • max_size() — максимальный размер обычно равен наиболее большому доступному блоку памяти

А вот результат:

Как видите Size показывает сколько сейчас лежит в векторе чисел. В то время как capacity возвращает инициализированный размер, то есть тот размер, до которого можно добавлять данные без инициализации. Вас не удивило, что размер доступной памяти не изменился . Это размер доступного блока, а не всей памяти поэтому он и не изменился.

Дальше о векторе

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

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

Можно получить первый и последний элемент вектора, для этого есть функции front() и back().

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

Можно поместить число в конец вектора воспользовавшись функцией push_back():

Можно удалить последний элемент с сокращением размера:

Для удаления используеться функция erase():

Изменяет размер вектора функция resize():

Применение алгоритмов к вектору

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

После чего можно сортировать, как весь вектор, так и отдельные его части, что очень приятно.

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

Наш класс в векторе

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

  • Конструктор по умолчанию
  • Конструктор копий
  • Деструктор

Давайте реализуем и попробуем.

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

Списки

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

Теперь список можно объявлять.

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

Количество элементов определяем функцией size():

Можно проверить список на пустоту.

Для вставки можно использовать три метода Insert(), push_back(), push_front().

Из списка можно удалять элементы равные определенному значению.

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

Понимание итератора

Вы должны воспринимать итератор на данный момент, как указатель C++. В общем случае это одно и тоже. Давайте посмотрим как применить алгоритм find к массиву C. Массив это и есть набор указателей вроде как.

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

Вы уже видели, как используются подобные функции типа begin() и end() для получения начала и конца итераторов. Главный вопрос почему не пользоваться указателями . Не получится. Представим массив из структур.

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

Только так вы можете идти от одной структуры к другой. И теперь самое главное. ЭТО МОЖНО ТОЛЬКО ЕСЛИ СТРУКТУРЫ РАСПОЛОЖЕНЫ ЛИНЕЙНО, то есть одна за другой. Тут же мы получим ограничение на то, что блок памяти должен быть непрерывный. Это очень не удобно и ограничивает размер при наличии памяти. Выход только один ЗАВЕСТИ ОТДЕЛЬНЫЙ МАССИВ С ИТЕРАТОРАМИ(указателями). В нем будут линейно храниться указатели на элементы. Ну и что скажете Вы ? Все равно нужен линейный блок памяти. Нужет только структуры могут быть по размеру очень большими. Даже в моем примере на место данной структуры можно поместить массу указателей. И теперь размер ограничивается непрерывной памятью для указателей. Это намного больше, кроме того сами структуры могут быть рассортированны по всей памяти.

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

Некоторые преимущества класса set

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

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

Но сначала. Возможно, я немного повторю Артема если скажу: set или, говоря языком математики, множество, представляет собой объект, контролирующий произвольной длины последовательность уникальных элементов какого-либо типа. В общем, классический подход ко множеству такой: set используется для хранения неповторяющихся (уникальных) ключей, либо для проверки, есть ли элемент в наборе данных.

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

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

Но вот в чем возникла загвоздочка: в любой функции по опреденению не может быть повторяющихся абсцисс (то есть иксов с разными игреками). Что делать? Писать проверочку ручками (да и сортировать вдобавок!) — брала тоска. Выход я нашел такой (привожу пример, конечно же, сильно упрощенный):

1. Создайте проект Win32 Console Application (пустой). Назовем, например, set_test.

2. В нем создайте два файла: заголовок (set_test.h) и cpp-шник (соответственно, set_test.cpp). Хотя можете, конечно, хранить все в одном: проект маленький.

3. В заголовке (set_test.h) напишите:

Что сие значит? Во-первых, почему именно оператор «меньше». Эта прелесть (set) осуществляет все свои сравнения (по крайней мере, при попытке добавить элемент) именно через оператор «меньше». Как узнать, какой оператор перегружать? А вы попробуйте откомпилить проект (когда мы его закончим) без его перегрузки. Выскочит соответствующий error. 🙂 .

Во-вторых, почему именно такая перегрузка. Ну, мне же нужно повторяющиеся иксы откинуть. И вдобавок по их значениям рассортировать. Вот я и заставляю беднягу-компа сравнивать вместо двух классов два икса. поделом. 🙂

Но закончим с проектом. Пишем cpp-шник:

Итак, что означает фраза

Во-первых, вызвывается конструктор stl_point(x, y) — в созданный экземпляр класса сразу же кидаются икс с игреком (см. конструктор). Далее. Возвращаемое значение сразу же кидается в set_exact и не запоминается больше нигде:

Метод insert объекта set возвращает простенький объект типа pair:

Как видите, pair чем-то подобен моей точке: все, что содержит — это два элемента любого (возможно, одинакового) типа — под загадочными именами first и second. 🙂 Наш же insert в случае удачи возвращает pair(it, true), иначе — pair(it, false). Ну, что такое загадочное it — никогда не интересовался. Наверное, на воткнутый элемент итератор. А вот второй элемент, second, — правда ведь на определенную мысль наталкивает?

Итак, смотрим что там, у second’а внутри. Если элемент воткнулся — радуемся. Нет — гм. Ну я печалиться не буду :)) Компилим проект. Запускаем. Попробуйте ввести элементы с одинаковыми иксами. И наоборот — с одинаковыми игреками. Да и вообще — потестьте :))

Теперь усложняем проект. Смотрите, чем поменялся main:

Руководство по стандартной библиотеке шаблонов (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 объединить в с , то это может быть выполнено так:

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

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


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

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

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

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

Требования

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

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

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

Основные компоненты

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

Операторы (Operators)

Чтобы избежать избыточных определений operator!= из operator== и operator> , , >= из operator , библиотека обеспечивает следующее:

Пара (Pair)

Библиотека включает шаблоны для разнородных пар значений.

Библиотека обеспечивает соответствующую шаблонную функцию make_pair , чтобы упростить конструкцию пар. Вместо выражения, например:

Итераторы

Итераторы — это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы — это объекты, которые имеют operator* , возвращающий значение некоторого класса или встроенного типа T , называемого значимым типом ( value type ) итератора. Для каждого типа итератора X , для которого определено равенство, имеется соответствующий знаковый целочисленный тип, называемый типом расстояния ( distanсe type ) итератора.

Так как итераторы — обобщение указателей, их семантика — обобщение семантики указателей в C++. Это гарантирует, что каждая шаблонная функция, которая использует итераторы, работает с обычными указателями. Есть пять категорий итераторов в зависимости от операций, определённых для них: ввода ( input iterators ), вывода ( output iterators ), последовательные ( forward iterators ), двунаправленные ( bidirectional iterators ) и произвольного доступа ( random access iterators .) Последовательные итераторы удовлетворяют всем требованиям итераторов ввода и вывода и могут использоваться всякий раз, когда определяется тот или другой вид. Двунаправленные итераторы удовлетворяют всем требованиям последовательных итераторов и могут использоваться всякий раз, когда определяется последовательный итератор. Итераторы произвольного доступа удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда определяется двунаправленный итератор. Имеется дополнительный атрибут, который могли бы иметь последовательные, двунаправленные и произвольного доступа итераторы, то есть они могут быть модифицируемые ( mutable ) или постоянные ( constant ) в зависимости от того, ведёт ли себя результат operator* как ссылка или как ссылка на константу. Постоянные итераторы не удовлетворяют требованиям итераторов вывода.

Таблица 1. Отношения среди категорий итераторов
Произвольного доступа Двунаправленные Последовательные Ввода
Вывода

Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными ( past-the-end ) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми ( dereferenceable ). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные ( singular ) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x; ), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение — присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.

Итератор j называется доступным ( reachable ) из итератора i , если и только если имеется конечная последовательность применений operator++ к i , которая делает i==j . Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i , или i доступен из j , или оба доступны ( i == j ).

Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон — это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) — пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i , и до элемента, но не включая его, указываемого j . Диапазон [i,j) допустим, если и только если j доступен из i . Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.

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

В следующих разделах мы принимаем: a и b — значения X , n — значение типа расстояния Distance , u, tmp и m — идентификаторы, r и s — леводопустимые (lvalues) значения X , t — значение значимого типа T .

Итераторы ввода (Input iterators)

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

Таблица 2. Требования итератора ввода
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после
X(a) X(a) — копия a .
примечание: предполагается деструктор.
X u(a);
X u = a;
после: u — копия a .
u = a X& после: u — копия a .
a == b обратимый в bool если a — копия b , тогда a == b возвращает true .
== — это отношение эквивалентности в области действия == .
a != b обратимый в bool !(a == b)
*a обратимый в T до: a — разыменовываемое.
если a — копия b , то *a эквивалентно *b .
++r X& до: r — разыменовываемое.
после: r — разыменовываемое или r — законечное.
void r++ void void ++r
*r++ Т < X tmp = r;
++r;
return tmp; >
ПРИМЕЧАНИЕ
Для итераторов ввода нет никаких требований на тип или значение r++ кроме требования, чтобы *r++ работал соответственным образом. В частности, r == s не подразумевает, что ++r == ++s . (Равенство не гарантирует свойство замены или ссылочной прозрачности.) Что касается ++r , то нет больше никаких требований на значения любых копий r за исключением того, что они могут быть безопасно уничтожены или присвоены. После выполнения ++r не требуется, чтобы были копии (предыдущего) r в области == . Алгоритмы с итераторами ввода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными ( single pass ) алгоритмами. Не требуется, чтобы значимый тип T был леводопустимым типом (lvalue type) . Эти алгоритмы могут использоваться с входными потоками как источниками входных данных через класс istream_iterator .

Итераторы вывода (Output iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора вывода, если справедливы следующие выражения:

Таблица 3. Требования итератора вывода
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после
X(a) *a = t эквивалентно *X(a) = t .
примечание: предполагается деструктор.
X u(a);
X u = a;
*a = t результат не используется
++r X&
r++ Х или Х&
ПРИМЕЧАНИЕ
Единственное допустимое использование operator* — на левой стороне выражения присваивания. Присваивание через то же самое значение итератора происходит только однажды . Алгоритмы с итераторами вывода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными ( single pass ) алгоритмами. Равенство и неравенство не обязательно определены. Алгоритмы, которые берут итераторы вывода, могут использоваться с выходными потоками для помещения в них данных через класс ostream_iterator , также как с итераторами вставки и вставляющими указателями. В частности, следующие два условия должны соблюдаться: во-первых, через любое значение итератора должно выполняться присваивание до его увеличения (то есть, для итератора вывода i недопустима последовательность кода i++; i++; ); во-вторых, любое значение итератора вывода может иметь только одну активную копию в любое данное время (например, недопустима последовательность кода i = j; *++i = a; *j = b; ).

Последовательные итераторы (Forward iterators)

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

Таблица 4. Требования последовательного итератора
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после
X u; примечание: u может иметь исключительное значение.
примечание: предполагается деструктор.
X() примечание: X() может быть исключительным.
X(a); a == X(a)
X u(a);
X u = a;
X u; u = a; после: u == a .
a == b обратимый в bool == — это отношение эквивалентности.
a != b обратимый в bool !(a == b)
r = a X& . после: r == a .
*a обратимый в T до: a — разыменовываемое.
a == b подразумевает *a == *b .
Если X — модифицируемый, то *a = t — допустимо.
++r X& до: r — разыменовываемое.
после: r — разыменовываемое или r — законечное.
r == s и r — разыменовываемое подразумевает ++r == ++s .
&r == &++r .
r++ X < X tmp = r;
++ r;
return tmp; >
ПРИМЕЧАНИЕ
Тот факт, что r == s подразумевает ++r == ++s (что неверно для итераторов ввода и вывода) и что удалено ограничение на число присваиваний через итератор (которое применяется к итераторам вывода), позволяет использование многопроходных однонаправленных алгоритмов с последовательными итераторами.

Двунаправленные итераторы (Bidirectional iterators)

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

Таблица 5. Требования двунаправленного итератора (в дополнение к последовательному итератору)
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после
—r X& до: существует s такое, что r == ++s .
после: s — разыменовываемое.
—(++r) == r .
—r == —s подразумевает r == s .
&r == &—r .
r— X < X tmp = r;
—r;
return tmp; >
ПРИМЕЧАНИЕ
Двунаправленные итераторы позволяют алгоритмам перемещать итераторы назад также, как вперёд.

Итераторы произвольного доступа (Random access iterators)

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

Таблица 6: Требования итератора произвольного доступа (в дополнение к двунаправленному итератору)
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после
r += n X& < Distance m = n;
if(m >= 0)
while(m—) ++r;
else
while(m++) —r;
return r; >
a + n
n + a
X < X tmp = a;
return tmp += n; >
a + n == n + a .
r -= n X& return r += -n;
a — n X < X tmp = a;
return tmp -= n; >
b — a Distance до: существует значение n типа Distance такое,
что a + n = b .
b == a + (b — a) .
a[n] обратимый в T *(a + n)
a обратимый в bool b — a > 0 — это отношение полного упорядочения
a > b обратимый в bool b > — это отношение полного упорядочения, противоположное .
a >= b обратимый в bool !(a
a обратимый в bool !(a > b)

Теги итераторов (Iterator tags)

Чтобы осуществлять алгоритмы только в терминах итераторов, часто бывает необходимо вывести тип значения и тип расстояния из итератора. Для решения этой задачи требуется, чтобы для итератора i любой категории, отличной от итератора вывода, выражение value_type(i) возвращало (T*)(0) , а выражение distance_type(i) возвращало (Distance*)(0) . Для итераторов вывода эти выражения не требуются.

Примеры использования тегов итераторов

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

Тогда, если мы хотим осуществить обобщённую функцию reverse , мы пишем следующее:

где _reverse определена следующим образом:

Если имеется дополнительный тип указателя _huge такой, что разность двух указателей _huge имеет тип long long , мы определяем:

Часто желательно для шаблонной функции выяснить, какова наиболее специфичная категория её итераторного аргумента, так чтобы функция могла выбирать наиболее эффективный алгоритм во время компиляции. Чтобы облегчить это, библиотека вводит классы тегов категорий ( category tag ), которые используются как теги времени компиляции для выбора алгоритма. Это следущие теги: input_iterator_tag , output_iterator_tag , forward_iterator_tag , bidirectional_iterator_tag и random_access_iterator_tag . Каждый итератор i должен иметь выражение iterator_category(i) , определённое для него, которое возвращает тег наиболее специфичной категории, который описывает его поведение. Например, мы определяем, что все типы указателей находятся в категории итераторов произвольного доступа:

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

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

Примитивы, определённые в библиотеке

Чтобы упростить задачу определения iterator_category , value_type и distance_type для определяемых пользователем итераторов, библиотека обеспечивает следующие предопределённые классы и функции:

Если пользователь хочет определить двунаправленный итератор для некоторой структуры данных, содержащей double , и такой, чтобы работал с большой (large) моделью памяти компьютера, то это может быть сделано таким определением:

Тогда нет необходимости определять iterator_category , value_type , и distance_type в MyIterator .

Операции с итераторами (Iterator operations)

Так как только итераторы произвольного доступа обеспечивают + и — операторы, библиотека предоставляет две шаблонные функции advance и distance . Эти функции используют + и — для итераторов произвольного доступа (и имеют, поэтому, сложность постоянного времени для них); для итераторов ввода, последовательных и двунаправленных итераторов функции используют ++ , чтобы обеспечить реализацию со сложностью линейного времени. advance берет отрицательный параметр n только для итераторов произвольного доступа и двунаправленных итераторов. advance увеличивает (или уменьшает для отрицательного n ) итераторную ссылку i на n . distance увеличивает n на число единиц, сколько требуется, чтобы дойти от first до last .

distance должна быть функцией 3-х параметров, сохраняющей результат в ссылке вместо возвращения результата, потому что тип расстояния не может быть выведен из встроенных итераторных типов, таких как int* .

Функциональные объекты

Функциональные объекты — это объекты, для которых определён operator() . Они важны для эффективного использования библиотеки. В местах, где ожидается передача указателя на функцию алгоритмическому шаблону, интерфейс установлен на приём объекта с определённым operator() . Это не только заставляет алгоритмические шаблоны работать с указателями на функции, но также позволяет им работать с произвольными функциональными объектами. Использование функциональных объектов вместе с функциональными шаблонами увеличивает выразительную мощность библиотеки также, как делает результирующий код более эффективным. Например, если мы хотим поэлементно сложить два вектора a и b , содержащие double , и поместить результат в a , мы можем сделать зто так:

Если мы хотим отрицать каждый элемент a , мы можем сделать это так:

Соответствующие функции вставят сложение и отрицание.

Чтобы позволить адаптерам и другим компонентам манипулировать функциональными объектами, которые используют один или два параметра, требуется, чтобы они соответственно обеспечили определение типов (typedefs) argument_type и result_type для функциональных объектов, которые используют один параметр, и first_argument_type , second_argument_type и result_type для функциональных объектов, которые используют два параметра.

Базовые классы (Base)

Следующие классы предоставляются, чтобы упростить определение типов (typedefs) параметров и результата:

Арифметические операции (Arithmetic operations)

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

Сравнения (Comparisons)

Библиотека обеспечивает базовые классы функциональных объектов для всех операторов сравнения языка

Логические операции (Logical operations)


Распределители

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

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

Требования распределителей (Allocator requirements)

В следующей таблице мы предполагаем, что X — класс распределителей для объектов типа T , a — значение X , n имеет тип X::size_type , p имеет тип X::pointer , r имеет тип X::reference и s имеет тип X::const_reference .

Все операции c распределителями, как ожидается, сводятся к постоянному времени.

Таблица 7. Требования распределителей
выражение возвращаемый тип утверждение/примечание состояние до/после
X::value_type Т
X::reference леводопустимое значение T (lvalue of T )
X::const_reference const lvalue of T
X::pointer указатель на тип T результатом operator* для значений X::pointer является reference .
X::const_pointer указатель на тип const T результат operator* для значений X::const_pointer — const_reference ;
это — тот же самый тип указателя, как X::pointer , в частности, sizeof(X::const_pointer) == sizeof(X::pointer) .
X:: size_type беззнаковый целочисленный тип тип, который может представлять размер самого большого объекта в модели памяти.
X::difference_type знаковый целочисленный тип тип, который может представлять разность между двумя любыми указателями в модели памяти.
X a; примечание: предполагается деструктор.
a.address(r) указатель *(a.address(r)) == r .
a.const_address(s) const_pointer *(a.address(s)) == s .
a.allocate(n) X::pointer память распределяется для n объектов типа T , но объекты не создаются. allocate может вызывать соответствующее исключение.
a.deallocate(p) результат не используется все объекты в области, указываемой p , должны быть уничтожены до этого запроса.
construct(p, a) void после: *p == a .
destroy(p) void значение, указываемое p , уничтожается.
a.init_page_size() X::size_type возвращённое значение — оптимальное значение для начального размера буфера данного типа. Предполагается, что если k возвращено функцией init_page_size , t — время конструирования для T , и u — время, которое требуется для выполнения allocate(k) , тогда k * t будет намного больше, чем u .
a.max_size() X::size_type наибольшее положительное значение X::difference_type

pointer относится к категории модифицируемых итераторов произвольного доступа, ссылающихся на T . const_pointer относится к категории постоянных итераторов произвольного доступа, ссылающихся на T . Имеется определённое преобразование из pointer в const_pointer .

Для любого шаблона распределителя Alloc имеется определение для типа void . У Alloc определены только конструктор, деструктор и Alloc ::pointer . Преобразования определены из любого Alloc ::pointer в Alloc ::pointer и обратно, так что для любого p будет p == Alloc ::pointer(Alloc ::pointer(p)) .

Распределитель по умолчанию (The default allocator)

Предполагается, что в дополнение к allocator поставщики библиотеки обеспечивают распределители для всех моделей памяти.

Контейнеры

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

В следующей таблице мы полагаем, что X — контейнерный класс, содержащий объекты типа T , a и b — значения X , u — идентификатор, r — значение X& .

Таблица 8. Требования контейнеров
выражение возвращаемый тип семантика исполнения утверждение/примечание состояние до/после сложность
X::value_type Т время компиляции
X::reference время компиляции
X::const_refe
rence
время компиляции
X::pointer тип указателя, указывающий на X::reference указатель на T в модели памяти, используемой контейнером время компиляции
X::iterator тип итератора, указывающий на X::reference итератор любой категории, кроме итератора вывода. время компиляции
X::const_iter
ator
тип итератора, указывающий на X::
const_reference
постоянный итератор любой категории, кроме итератора вывода. время компиляции
X::difference
_type
знаковый целочисленный тип идентичен типу расстояния X::iterator и X::const_iterator время компиляции
X::size_type беззнаковый целочисленный тип size_type может представлять любое неотрицательное значение difference_type время компиляции
X u; после: u.size() == 0 . постоянная
X() X().size() == 0 . постоянная
X(a) a == X(a) . линейная
X u(a);
X u == a;
X u; u = a; после: u == a . линейная
(&a)->

X()

результат не используется после: a.size() == 0 .
примечание: деструктор применяется к каждому элементу a , и вся память возвращается.
линейная
a.begin() iterator;
const_iterator для постоянного a
постоянная
a.end() iterator;
const_iterator для постоянного a
постоянная
a == b обратимый в bool a.size() ==
b.size() &&
equal(a.begin(),
a.end(),
b.begin())
== — это отношение эквивалентности.
примечание: eqial определяется в разделе алгоритмов.
линейная
a != b обратимый в bool !(a == b) линейная
r = a X& if(&r != &a) <
(&r)-> X::

X();
new (&r) X(a);
return r; >

после: r == a . линейнaя
a.size() size_type size_type n = 0;
distance
(a.begin(),
a.end(), n);
return n;
постоянная
a.max_size() size_type size() самого большого возможного контейнера. постоянная
a.empty() обратимый в bool a.size() == 0 постоянная
a обратимый в bool lexicographical
_compare
(a.begin(), a.end(),
b.begin(), b.end())
до: определён для значений T .
— отношение полного упорядочения.
lexicographical
_compare определяется в разделе алгоритмов.
линейная
a > b обратимый в bool b линейнaя
a обратимый в bool !(a > b) линейная
a >= b обратимый в bool !(a линейная
a.swap(b) void swap(a, b) постоянная

Функция-член size() возвращает число элементов в контейнере. Её семантика определяется правилами конструкторов, вставок и удалений.

begin() возвращает итератор, ссылающийся на первый элемент в контейнере. end() возвращает итератор, который является законечным.

Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым) и удовлетворяет следующим дополнительным требованиям:

Таблица 9. Требования обратимых контейнеров (в дополнение к контейнерам)
выражение возвращаемый тип семантика исполнения сложность
X::reverse
_iterator
reverse_iterator
для итератора произвольного доступа.
reverse_bidirectional_iterator
для двунаправленного итератора
время компиляции
X::const_r
everse_ite
rator
reverse_iterator
для итератора произвольного доступа.
reverse_bidirectional_iterator
для двунаправленного итератора.
время компиляции
a.rbegin() reverse_iterator;
const_reverse_iter
ator для постоянного a
reverse_iterator(end()) постоянная
a.rend() reverse_iterator;
const_reverse_iter
ator для постоянного a
reverse_iterator(begin()) постоянная

Последовательности (Sequences)

Последовательность — это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).

В следующих двух таблицах X — последовательный класс, a — значение X , i и j удовлетворяют требованиям итераторов ввода, [i, j) — допустимый диапазон, n — значение X::size_type , p — допустимый итератор для a , q — разыменовываемый итератор для a , [ql, q2) — допустимый диапазон в a , t — значение X::value_type .

Сложности выражений зависят от последовательностей.

Таблица 10. Требования последовательностей (в дополнение к контейнерам)
выражение возвращаемый тип утверждение/примечание состояние до/после
X(n, t)
X a(n, t);
после: size() == n .
создаёт последовательность с n копиями t .
X(i, j)
X a(i, j);
после: size() == расстоянию между i и j .
создаёт последовательность, равную диапазону [i, j) .
a.insert(p, t) iterator вставляет копию t перед p .
возвращаемое значение указывает на вставленную копию.
a.insert(p, n, t) результат не используется вставляет n копий t перед p .
a.insert(p, i, j) результат не используется вставляет копии элементов из диапазона [i, j) перед p .
a.erase(q) результат не используется удаляет элемент, указываемый q .
a.erase(ql, q2) результат не используется удаляет элементы в диапазоне [ql, q2) .

vector (вектор), list (список) и deque (двусторонняя очередь) выдвигают программисту различные предложения сложности и должны использоваться соответственно. vectоr — тип последовательности, которая используется по умолчанию. list нужно использовать, когда имеются частые вставки и удаления из середины последовательности, deque — структура данных для выбора, когда большинство вставок и удалений происходит в начале или в конце последовательности.

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

Таблица 11. Необязательные операции последовательностей
выражение возвращаемый тип семантика исполнения контейнер
a.front() reference;
const_reference для постоянного a
*a.begin() vector, list, deque
a.back() reference;
const_reference для постоянного a
*a.(—end()) vector, list, deque
a.push_front(t) void a.insert(a.begin(), t) list, deque
a.push_back(t) void a.insert(a.end(), t) vector, list, deque
a.pop_front () void a.erase(a.begin()) list, deque
a.pop_back () void a.erase(— a.end()) vector, list, deque
a[n] reference;
const_reference для постоянного a
*(a.begin() + n) vector, deque

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

Вектор (Vector)

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

iterator — это итератор произвольного доступа, ссылающийся на T . Точный тип зависит от исполнения и определяется в Allocator .

const_iterator — это постоянный итератор произвольного доступа, ссылающийся на const T . Точный тип зависит от исполнения и определяется в Allocator . Гарантируется, что имеется конструктор для const_iterator из iterator .

size_type — беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator .

difference_type — знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator .

Конструктор template vector(InputIterator first, InputIterator last) делает только N вызовов конструктора копирования T (где N — расстояние между first и last ) и никаких перераспределений, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Он делает, самое большее, 2N вызовов конструктора копирования T и logN перераспределений, если они — только итераторы ввода, так как невозможно определить расстояние между first и last и затем сделать копирование.

Функция-член capacity (ёмкость) возвращает размер распределённой памяти в векторе. Функция-член reserve — директива, которая сообщает vector (вектору) запланированноe изменение размера, так чтобы он мог соответственно управлять распределением памяти. Это не изменяет размер последовательности и занимает, самое большее, линейное время от размера последовательности. Перераспределение в этом случае происходит тогда и только тогда, когда текущая ёмкость меньше, чем параметр reserve . После reserve ёмкость ( capacity ) больше или равна параметру reserve , если происходит перераспределение; а иначе равна предыдущему значению capacity . Перераспределение делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Гарантируется, что нет никакого перераспределения во время вставок, которые происходят после того, как reserve выполняется, до времени, когда размер вектора достигает размера, указанного reserve .

insert (вставка) вызывает перераспределение, если новый размер больше, чем старая ёмкость. Если никакого перераспределения не происходит, все итераторы и ссылки перед точкой вставки остаются справедливыми. Вставка единственного элемента в вектор линейна относительно расстояния от точки вставки до конца вектора. Амортизированная сложность во время жизни вектора, вставляющего единственный элемент в свой конец, постоянна. Вставка множественных элементов в вектор с единственным вызовом вставляющей функции-члена линейна относительно суммы числа элементов плюс расстояние до конца вектора. Другими словами, намного быстрее вставить много элементов в середину вектора сразу, чем делать вставку по одному элементу. Шаблонная вставляющая функция-член предраспределяет достаточно памяти для вставки, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Иначе функция вставляет элементы один за другим и не должна использоваться для вставки в середину векторов.

erase (стирание) делает недействительными все итераторы и ссылки после пункта стирания. Деструктор T вызывается столько раз, каково число стёртых элементов, а оператор присваивания T вызывается столько раз, каково число элементов в векторе после стёртых элементов.

Чтобы оптимизировать распределение места, даётся определение для bool .

reference — класс, который имитирует поведение ссылок отдельного бита в vector bool > .

Ожидается, что каждое исполнение обеспечит определение vector bool > для всех поддерживаемых моделей памяти.


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

Список (List)

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

iterator — двунаправленный итератор, ссылающийся на T . Точный тип зависит от исполнения и определяется в Allocator .

const_iterator — постоянный двунаправленный итератор, ссылающийся на const T . Точный тип зависит от исполнения и определяется в Allocator . Гарантируется, что имеется конструктор для const_iterator из iterator .

size_type — беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator .

difference_type — знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator .

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

erase делает недействительными только итераторы и ссылки для стёртых элементов. Стирание единственного элемента — операция постоянного времени с единственным вызовом деструктора T . Стирание диапазона в списке занимает линейное время от размера диапазона, а число вызовов деструктора типа T точно равно размеру диапазона.

Так как списки позволяют быструю вставку и стирание в середине списка, то некоторые операции определяются специально для них:

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

void splice(iterator position, list & x) вставляет содержимое x перед position , и x становится пустым. Требуется постоянное время. Результат не определён, если &x == this .

void splice(iterator position, list & x, iterator i) вставляет элемент, указываемый i , из списка x перед position и удаляет элемент из x . Требуется постоянное время. i — допустимый разыменовываемый итератор списка x . Результат не изменяется, если position == i или position == ++i .

void splice(iterator position, list & x, iterator first, iterator last) вставляет элементы из диапазона [first, last) перед position и удаляет элементы из x . Требуется постоянное время, если &x == this ; иначе требуется линейное время. [first, last) — допустимый диапазон в x . Результат не определён, если position — итератор в диапазоне [first, last) .

remove стирает все элементы в списке, указанном итератором списка i , для которого выполняются следующие условия: *i == value , pred(*i) == true . remove устойчиво, то есть относительный порядок элементов, которые не удалены, тот же самый, как их относительный порядок в первоначальном списке. Соответствующий предикат применяется точно size() раз.

unique стирает все, кроме первого элемента, из каждой последовательной группы равных элементов в списке. Соответствующий бинарный предикат применяется точно size() — 1 раз.

merge сливает список аргумента со списком (предполагается, что оба сортированы). Слияние устойчиво, то есть для равных элементов в двух списках элементы списка всегда предшествуют элементам из списка аргумента. x пуст после слияния. Выполняется, самое большее, size() + x.size() — 1 сравнений.

reverse переставляет элементы в списке в обратном порядке. Операция линейного времени.

sort сортирует список согласно operator или сравнивающему функциональному объекту. Она устойчива, то есть относительный порядок равных элементов сохраняется. Выполняется приблизительно NlogN сравнений, где N равно size() .

Двусторонняя очередь (Deque)

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

iterator — итератор произвольного доступа, ссылающийся на T . Точный тип зависит от исполнения и определяется в Allocator .

const_iterator — постоянный итератор произвольного доступа, ссылающийся на const T . Точный тип зависит от исполнения и определяется в Allocator . Гарантируется, что имеется конструктор для const_iterator из iterator .

size_type — беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator .

difference_type — знаковый целочисленный тип. Точный зависит от исполнения и определяется в Allocator .

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

erase (стирание) в середине двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. erase и pop (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.

Ассоциативные контейнеры (Associative containers)

Ассоциативные контейнеры обеспечивают быстрый поиск данных, основанных на ключах. Библиотека предоставляет четыре основных вида ассоциативных контейнеров: set (множество), multiset (множество с дубликатами), map (словарь) и multimap (словарь с дубликатами).

Все они берут в качестве параметров Key (ключ) и упорядочивающее отношение Compare , которое вызывает полное упорядочение по элементам Key . Кроме того, map и multimap ассоциируют произвольный тип T с Key . Объект типа Compare называется сравнивающим объектом ( comparison object ) контейнера.

В этом разделе, когда мы говорим о равенстве ключей, мы подразумеваем отношение эквивалентности, обусловленное сравнением и не ( not ) operator== для ключей. То есть считается, что два ключа k1 и k2 являются равными, если для сравнивающего объекта comp истинно comp(k1, k2) == false && comp(k2, k1) == false .

Ассоциативный контейнер поддерживает уникальные ключи ( unique keys ), если он может содержать, самое большее, один элемент для каждого значения ключа. Иначе он поддерживает равные ключи ( equal keys ). set и map поддерживают уникальные ключи. multiset и multimap поддерживают равные ключи.

Для set и multiset значимый тип — тот же самый, что и тип ключа. Для map и multimap он равен pair .

iterator ассоциативного контейнера относится к категории двунаправленного итератора. insert не влияет на действительность итераторов и ссылок контейнера, а erase делает недействительными только итераторы и ссылки на стёртые элементы.

В следующей таблице обозначается: X — класс ассоциативного контейнера, a — значение X , a_uniq — значение X , когда X поддерживает уникальные ключи, a a_eq — значение X , когда X поддерживает многократные ключи, i и j удовлетворяют требованиям итераторов ввода и указывают на элементы value_type , [i, j) — допустимый диапазон, p — допустимый итератор для a , q — разыменовываемый итератор для a , [q1, q2) — допустимый диапазон в a , t — значение X::value_type и k — значение X::key_type .

Таблица 12. Требования ассоциативных контейнеров (в дополнение к контейнерам)
выражение возвращаемый тип утверждение/примечание состояние до/после сложность
X::key_type Key время компиляции
X::key_compare Compare по умолчанию less . время компиляции
X::value_compare тип бинарного предиката то же, что key_compare для set и multiset ;
отношение упорядочения пар, вызванное первым компонентом (т.е. Key ), для map и multimap .
время компиляции
X(c)
X a(c);
создает пустой контейнер;
использует с как объект сравнения.
постоянная
X()
X a;
создает пустой контейнер;
использует Compare() как объект сравнения.
постоянная
X(i,j,c)
X a(i,j,c);
cоздает пустой контейнер и вставляет в него элементы из диапазона [i, j) ;
использует с как объект сравнения.
вообще NlogN ( N — расстояние от i до j );
линейная, если [i, j) отсортирован value_comp()
X(i,j)
X a(i,j);
то же, что выше, но использует Compare() как объект сравнения. то же, что выше
a.key_comp() X::key_compare возвращает объект сравнения, из которого а был создан. постоянная
a.value_comp() X::value_compare возвращает объект value_compare , созданный из объекта сравнения. постоянная
a_uniq.insert(t) pair вставляет t , если и только если в контейнере нет элемента с ключом, равным ключу t . Компонент bool возвращенной пары показывает, происходит ли вставка, а компонент пары iterator указывает на элемент с ключом, равным ключу t . логарифмическая
a_eq.insert(t) iterator вставляет t и возвращает итератор, указывающий на вновь вставленный элемент. логарифмическая
a.insert(p, t) iterator вставляет t , если и только если в контейнерах с уникальными ключами нет элемента с ключом, равным ключу t ; всегда вставляет t в контейнеры с дубликатами.
всегда возвращает итератор, указывающий на элемент с ключом, равным ключу t . итератор p — подсказка, указывающая, где вставка должна начать поиск.
вообще логарифмическая, но сводится к постоянной, если t вставлен прямо перед p .
a.insert(i, j) результат не используется вставляет в контейнер элементы из диапазона [i, j) ; вообще Nlog(size()+N) ( N — расстояние от i до j );
линейная, если [i, j) отсортирован согласно value_comp()
a.erase(k) size_type стирает все элементы в контейнере с ключом, равным k .
возвращает число уничтоженных элементов.
log(size()) + count(k)
a.erase(q) результат не используется стирает элемент, указанный q . сводится к постоянной
a.erase(ql, q2) результат не используется стирает все элементы в диапазоне [ql, q2) . log(size())+ N , где N — расстояние от ql до q2 .
a.find(k) iterator;
const_iterator для константы a
возвращает итератор, указывающий на элемент с ключом, равным k , или a.end() , если такой элемент не найден. логарифмическая
a.count(k) size_type возвращает число элементов с ключом, равным k . log(size()) + count(k)
a.lower_bound(k) iterator;
const_iterator для константы a
возвращает итератор, указывающий на первый элемент с ключом не меньше, чем k . логарифмическая
a.upper_bound(k) iterator;
const_iterator для константы a
возвращает итератор, указывающий на первый элемент с ключом больше, чем k . логарифмическая
a.equal_range(k) pair ;
pair для константы a
эквивалент make_pair(lower_boud(k), upper_bound (k)) . логарифмическая

Основным свойством итераторов ассоциативных контейнеров является то, что они выполняют итерации через контейнеры в порядке неубывания ключей, где неубывание определено сравнением, которое использовалось для их создания. Для любых двух разыменованных итераторов i и j таких, что расстояние от i до j является положительным, value_comp (*j, *i) == false . Для ассоциативных контейнеров с уникальными ключами выдерживается более сильное условие value_comp (*i, *j) == true .

Множество (Set)

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

iterator — постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator .

сonst_iterator — тот же самый тип, что и iterator.

size_type — целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator .

difference_type — целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator .

Множество с дубликатами (Multiset)

multiset — это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.

iterator — постоянный двунаправленный итератор, указывающий на const value_type . Точный тип зависит от реализации и определяется в Allocator .

сonst_iterator — тот же самый тип, что и iterator .

size_type — целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator .

difference_type — целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator .

Словарь (Map)

map — ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск значений другого типа T , связанных с ключами.

iterator — двунаправленный итератор, указывающий на value_type . Точный тип зависит от реализации и определяется в Allocator .

const_iterator — постоянный двунаправленный итератор, указывающий на const value_type . Точный тип зависит от реализации и определяется в Allocator . Гарантируется, что имеется конструктор для const_iterator из iterator .

size_type — целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator .

difference_type — целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator .

В дополнение к стандартному набору методов ассоциативных контейнеров, map обеспечивает операцию Allocator ::reference operator[](const key_type&) . Для словаря m и ключа k запись m[k] семантически эквивалентна (*((m.insert(make_pair(k, T()))).first)).second .

Словарь с дубликатами (Multimар)

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

iterator — двунаправленный итератор, указывающий на value_type . Точный тип зависит от реализации и определяется в Allocator .

const_iterator — постоянный двунаправленный итератор, указывающий на value_type . Точный тип зависит от реализации и определяется в Allocator . Гарантируется, что имеется конструктор для const_iterator из iterator .

size_type — целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator .

difference_type — целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator .

Итераторы потоков

Чтобы шаблоны алгоритмов могли работать непосредственно с потоками ввода-вывода, предусмотрены соответствующие шаблонные классы, подобные итераторам. Например,

читает файл, содержащий числа с плавающей запятой, из cin и печатает частичные суммы в cout .

Итератор входного потока (Istream Iterator)

istream_iterator читает (используя operator>> ) последовательные элементы из входного потока, для которого он был создан. После своего создания итератор каждый раз при использовании ++ читает и сохраняет значение T . Если достигнут конец потока ( operator void* () в потоке возвращает false ), итератор становится равным значению end-of-stream ( конец-потока ). Конструктор без параметров istream_iterator() всегда создаёт итераторный объект конца потокового ввода, являющийся единственым законным итератором, который следует использовать для конечного условия. Результат operator* для конца потока не определён, а для любого другого значения итератора возвращается const T& .

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

Два итератора конец-потока всегда равны. Итератор конец-потока не равен не-конец-потока итератору. Два не-конец-потока итератора равны, когда они созданы из того же самого потока.

Итератор выходного потока (Ostream Iterator)

istream_iterator записывает (используя operator ) последовательные элементы в выходной поток, из которого он был создан. Если он был создан с параметром конструктора char* , эта строка, называемая строкой разделителя ( delimiter string ), записывается в поток после того, как записывается каждое T . Невозможно с помощью выходного итератора получить значение. Его единственное использование — выходной итератор в ситуациях, подобных нижеследующему:

ostream_iterator определён как:

Алгоритмы

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

Для некоторых алгоритмов предусмотрены и оперативные и копирующие версии. Решение, включать ли копирующую версию, было обычно основано на рассмотрении сложности. Когда стоимость выполнения операции доминирует над стоимостью копии, копирующая версия не включена. Например, sort_copy не включена, так как стоимость сортировки намного значительнее, и пользователи могли бы также делать copy перед sort . Когда такая версия предусмотрена для какого-то алгоритма algorithm , он называется algorithm _copy . Алгоритмы, которые берут предикаты, оканчиваются суффиксом _if (который следует за суффиксом _copy ).

Класс Predicate используется всякий раз, когда алгоритм ожидает функциональный объект, при применении которого к результату разыменования соответствующего итератора возвращается значение, обратимое в bool . Другими словами, если алгоритм берёт Predicate pred как свой параметр и first как свой параметр итератора, он должен работать правильно в конструкции if (pred(*first)) <. >. Предполагается, что функциональный объект pred не применяет какую-либо непостоянную функцию для разыменованного итератора.

Класс BinaryPredicate используется всякий раз, когда алгоритм ожидает функциональный объект, который при его применении к результату разыменования двух соответствующих итераторов или к разыменованию итератора и типа T , когда T — часть сигнатуры, возвращает значение, обратимое в bool . Другими словами, если алгоритм берёт BinaryPredicate binary_pred как свой параметр и first1 и first2 как свои параметры итераторов, он должен работать правильно в конструкции if (binary_pred(*first, *first2)) <. >. BinaryPredicate всегда берёт тип первого итератора как свой первый параметр, то есть в тех случаях, когда T value — часть сигнатуры, он должен работать правильно в контексте if (binary_pred (*first, value)) <. >. Ожидается, что binary_pred не будет применять какую-либо непостоянную функцию для разыменованных итераторов.

В описании алгоритмов операторы + и — используются для некоторых категорий итераторов, для которых они не должны быть определены. В этих случаях семантика a+n такая же, как семантика , а семантика a-b такая же, как семантика .

Не меняющие последовательность операции (Non-mutating sequence operations)


Операции с каждым элементом (For each)

for_each применяет f к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f . Принято, что f не применяет какую-то непостоянную функцию к разыменованному итератору. f применяется точно last-first раз. Если f возвращает результат, результат игнорируется.

Найти (Find)

find возвращает первый итератор i в диапазоне [first, last) , для которого соблюдаются следующие соответствующие условия: *i == value , pred (*i) == true . Если такой итератор не найден, возвращается last . Соответствующий предикат применяется точно find(first, last, value) — first раз.

Найти рядом (Аdjacent find)

adjacent_find возвращает первый итератор i такой, что i и i+1 находятся в диапазоне [first, last) и для которого соблюдаются следующие соответствующие условия: *i == *(i + 1) , binary_pred(*i, *(i + 1)) == true . Если такой итератор i не найден, возвращается last . Соответствующий предикат применяется, самое большее, max((last — first) — 1, 0) раз.

Подсчет (Count)

count добавляет к n число итераторов i в диапазоне [first, last) , для которых соблюдаются следующие соответствующие условия: *i == value , pred (*i) == true . Соответствующий предикат применяется точно last-first раз.

count должен сохранять результат в параметре ссылки вместо того, чтобы возвращать его, потому что тип размера не может быть выведен из встроенных типов итераторов, как, например, int* .

Отличие (Mismatch)

mismatch возвращает пару итераторов i и j таких, что j == first2 + (i — first1) и i является первым итератором в диапазоне [first1, last1) , для которого следующие соответствующие условия выполнены: !(*i == *(first2 + (i — first1))) , binary_pred (*i, *(first2 + (i — first1))) == false . Если такой итератор i не найден, пара last1 и first2 + (last1 — first1) возвращается. Соответствующий предикат применяется, самое большее, last1 — first1 раз.

Сравнение на равенство (Equal)

equal возвращает true , если для каждого итератора i в диапазоне [first1, last1) выполнены следующие соответствующие условия: *i == *(first2 + (i — first1)) , binary_pred(*i, *(first2 + (i — first1))) == true . Иначе equal возвращает false . Соответствующий предикат применяется, самое большее, last1 — first1 раз.

Поиск подпоследовательности (Search)

search находит подпоследовательность равных значений в последовательности. search возвращает первый итератор i в диапазоне [first1, last1 — (last2 — first2)) такой, что для любого неотрицательного целого числа n , меньшего чем last2 — first2 , выполнены следующие соответствующие условия: *(i + n) == *(first2 + n) , binary_pred(*(i + n), *(first2 + n)) == true . Если такой итератор не найден, возвращается last1 . Соответствующий предикат применяется, самое большее, (last1 — first1) * (last2 — first2) раз. Квадратичное поведение, однако, является крайне маловероятным.

Меняющие последовательность операции (Mutating sequence operations)


Копировать (Copy)

copy копирует элементы. Для каждого неотрицательного целого числа n выполняется присваивание *( result + n) = *( first + n) . Точно делается last — first присваиваний. Результат copy не определён, если result находится в диапазоне [first, last) .

copy_backward копирует элементы в диапазоне [first, last) в диапазон [result — (last — first), result) , начиная от last-1 и продолжая до first . Его нужно использовать вместо copy , когда last находится в диапазоне [result — (last — first), result) . Для каждого положительного целого числа n выполняется присваивание *(result — n) = *(last — n) . copy_backward возвращает result — (last — first) . Точно делается last — first присваиваний. Результат copy_backward не определён, если result находится в диапазоне [first, last) .

Обменять (Swap)

swap обменивает значения, хранимые в двух местах.

iter_swap обменивает значения, указанные двумя итераторами a и b .

Для каждого неотрицательного целого числа n выполняется перестановка: swap(*(first1 + n), *(first2 + n)) . swap_ranges возвращает first2 + (last1 — first1) . Выполняется точно last1 — first1 перестановок. Результат swap_ranges не определён, если два диапазона [first1, last1) и [first2, first2 + (last1 — first1)) перекрываются.

Преобразовать (Transform)

transform присваивает посредством каждого итератора i в диапазоне [result, result + (last1 — first1)) новое соответствующее значение, равное op(* (first1 + (i — result)) или binary_op(*(first1 + (i — result), *(first2 + (i — result))) . transform возвращает result + (last1 — first1) . Применяются op или binary_op точно last1 — first1 раз. Ожидается, что op и binary_op не имеют каких-либо побочных эффектов. result может быть равен first в случае унарного преобразования или first1 либо first2 в случае бинарного.

Заменить (Replace)

replace заменяет элементы, указанные итератором i в диапазоне [first, last) , значением new_value , когда выполняются следующие соответствующие условия: *i == old_value , pred(*i) == true . Соответствующий предикат применяется точно last — first раз.

replace_copy присваивает каждому итератору i в диапазоне [result, result + (last — first)) значение new_value или *(first + (i — result)) в зависимости от выполнения следующих соответствующих условий: *(first + (i — result)) == old_value , pred(*(first + (i — result))) == true . replace_copy возвращает result + (last — first) . Соответствующий предикат применяется точно last — first раз.

Заполнить (Fill)

fill присваивает значения через все итераторы в диапазоне [first, last) или [first, first + n) . fill_n возвращает first + n . Точно делается last — first (или n ) присваиваний.

Породить (Generate)



generate вызывает функциональный объект gen и присваивает возвращаемое gen значение через все итераторы в диапазоне [first, last) или [first, first + n) . gen не берёт никакие параметры. generate_n возвращает first + n . Точно выполняется last — first (или n ) вызовов gen и присваиваний.

Удалить (Remove)

remove устраняет все элементы, указываемые итератором i в диапазоне [first, last) , для которых выполнены следующие соответствующие условия: *i == value , pred (*i) == true . remove возвращает конец возникающего в результате своей работы диапазона. remove устойчив, то есть относительный порядок элементов, которые не удалены, такой же, как их относительный порядок в первоначальном диапазоне. Соответствующий предикат применяется точно last -first раз.

remove_copy копирует все элементы, указываемые итератором i в диапазоне [first, last) , для которых не выполнены следующие соответствующие условия: *i == value , pred (*i) == true . remove_copy возвращает конец возникающего в результате своей работы диапазона. remove_copy устойчив, то есть относительный порядок элементов в результирующем диапазоне такой же, как их относительный порядок в первоначальном диапазоне. Соответствующий предикат применяется точно last — first раз.

Убрать повторы (Unique)

unique устраняет все, кроме первого, элементы из каждой последовательной группы равных элементов, указываемые итератором i в диапазоне [first, last) , для которых выполнены следующие соответствующие условия: *i == *(i — 1) или binary_pred(*i, *(i — 1)) == true . unique возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last — first) — 1 раз.

unique_copy копирует только первый элемент из каждой последовательной группы равных элементов, указываемых итератором i в диапазоне [first, last) , для которых выполнены следующие соответствующие условия: *i == *(i — 1) или binary_pied(*i, *(i — 1)) == true . unique_copy возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last — first) — 1 раз.

Расположить в обратном порядке (Reverse)

Для каждого неотрицательного целого числа i функция reverse применяет перестановку ко всем парам итераторов first + i , (last — i) — 1 . Выполняется точно (last — first)/2 перестановок.

reverse_copy копирует диапазон [first, last) в диапазон [result, result + (last — first)) такой, что для любого неотрицательного целого числа i происходит следующее присваивание: *(result + (last — first) — i) = *(first + i) . reverse_copy возвращает result + (last — first). Делается точно last — first присваиваний. Результат reverse_copy не определён, если [first, last) и [result, result + (last — first)) перекрываются.

Переместить по кругу (Rotate)

Для каждого неотрицательного целого числа i функция rotate помещает элемент из позиции first + i в позицию first + (i + (last — middle)) % (last — first) . [first, middle) и [middle, last) — допустимые диапазоны. Максимально выполняется last — first перестановок.

rotate_copy копирует диапазон [first, last) в диапазон [result, result + (last — first)) такой, что для каждого неотрицательного целого числа i происходит следующее присваивание: *(result + (i + (last — m >. rotate_copy возвращает result + (last — first) . Делается точно last — first присваиваний. Результат rotate_copy не определён, если [first, last) и [result, result + (last — first)) перекрываются.

Перетасовать (Random shuffle)

random_shuffle переставляет элементы в диапазоне [first, last) с равномерным распределением. Выполняется точно last — first перестановок. random_shuffle может брать в качестве параметра особый генерирующий случайное число функциональный объект rand такой, что rand берёт положительный параметр n типа расстояния RandomAccessIterator и возвращает случайно выбранное значение между 0 и n-1 .

Разделить (Partitions)

partition помещает все элементы в диапазоне [first, last) , которые удовлетворяют pred , перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred (*j) == true , а для любого итератора k в диапазоне [i, last) будет pred(*k) == false . Делается максимально (last — first)/2 перестановок. Предикат применяется точно last — first раз.

stable_partition помещает все элементы в диапазоне [first, last) , которые удовлетворяют pred , перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j) == true , а для любого итератора k в диапазоне [i, last) будет pred(*k) == false . Относительный порядок элементов в обеих группах сохраняется. Делается максимально (last — first) * log(last — first) перестановок, но только линейное число перестановок, если имеется достаточная дополнительная память. Предикат применяется точно last — first раз.

Операции сортировки и отношения (Sorting and related operations)

Все операции в этом разделе имеют две версии: одна берёт в качестве параметра функциональный объект типа Compare , а другая использует operator .

Compare — функциональный объект, который возвращает значение, обратимое в bool . Compare comp используется полностью для алгоритмов, принимающих отношение упорядочения. comp удовлетворяет стандартным аксиомам для полного упорядочения и не применяет никакую непостоянную функцию к разыменованному итератору. Для всех алгоритмов, которые берут Compare , имеется версия, которая использует operator взамен. То есть comp(*i, *j) == true по умолчанию для *i .

Последовательность сортируется относительно компаратора comp , если для любого итератора i , указывающего на элемент в последовательности, и любого неотрицательного целого числе n такого, что i + n является допустимым итератором, указывающим на элемент той же самой последовательности, comp(*( i + n), *i) == false .

В описаниях функций, которые имеют дело с упорядочивающими отношениями, мы часто используем представление равенства, чтобы описать такие понятия, как устойчивость. Равенство, к которому мы обращаемся, не обязательно operator== , а отношение равенства стимулируется полным упорядочением. То есть два элементa a и b считаются равными, если и только если !(a .

Сортировка (Sort)

sort сортирует элементы в диапазоне [first, last) . Делается приблизительно NIogN (где N равняется last — first ) сравнений в среднем. Если режим наихудшего случая важен, должны использоваться stable_sort или partial_sort .

stable_sort сортирует элементы в диапазоне [first, last) . Он устойчив, то есть относительный порядок равных элементов сохраняется. Делается максимум N(logN) 2 (где N равняется last — first ) сравнений; если доступна достаточная дополнительная память, тогда зто — NlogN .

partial_sort помещает первые middle — first сортированных элементов из диапазона [first, last) в диапазон [first, middle) . Остальная часть элементов в диапазоне [middle, last) помещена в неопределённом порядке. Берётся приблизительно (last — first) * log(middle — first) сравнений.

partial_sort_copy помещает первые min(last — first, result_last — result_first) сортированных элементов в диапазон [result_first, result_first + min(last — first, result_last — result_first)) . Возвращается или result_last , или result_first +(last — first) , какой меньше. Берётся приблизительно (last — first) * log(min(last — first, result_last — result_first)) сравнений.

N-й элемент (Nth element)

После операции nth_element элемент в позиции, указанной nth , является элементом, который был бы в той позиции, если бы сортировался целый диапазон. Также для любого итератора i в диапазоне [first, nth) и любого итератора j в диапазоне [nth, last) считается, что !(*i > *j) или comp(*i, *j) == false . Операция линейна в среднем.

Двоичный поиск (Binary search)

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

lower_bound находит первую позицию, в которую value может быть вставлено без нарушения упорядочения. lower_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j или comp(*j, value) == true . Делается максимум log(last — first) + 1 сравнений.

upper_bound находит самую дальнюю позицию, в которую value может быть вставлено без нарушения упорядочения. upper_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value или comp(value, *j) == false . Делается максимум log(last — first) + 1 сравнений.

equal_range находит самый большой поддиапазон [i, j) такой, что значение может быть вставлено по любому итератору k в нём. k удовлетворяет соответствующим условиям: !(*k или comp(*k, value) == false && comp(value, *k) == false . Делается максимум 2 * log(last — first) + 1 сравнений.

binary_search возвращает истину, если в диапазоне [first, last) имеется итератор i , который удовлетворяет соответствующим условиям: !(*i или comp(*i, value) == false && comp(value, *i) == false . Делается максимум log(last — first) + 2 сравнений.

Объединение (Merge)

merge объединяет два сортированных диапазона [first1, last1) и [first2, last2) в диапазон [result, result + (last1 — first1) + (last2 — first2)) . Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. merge возвращает result + (last1 — first1) + (last2 — first2) . Выполняется максимально (last1 — first1) + (last2 — first2) — 1 сравнений. Результат merge не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

inplace_merge объединяет два сортированных последовательных диапазона [first, middle) и [middle, last) , помещая результат объединения в диапазон [first, last) . Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. Когда доступно достаточно дополнительной памяти, выполняется максимально (last — first) — 1 сравнений. Если никакая дополнительная память не доступна, может использоваться алгоритм со сложностью O(NlogN) .

Операции над множеством для сортированных структур (Set operations on sorted structures)

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

includes возвращает true , если каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1) . Иначе возвращается false . Выполняется максимально ((last1 — first1) + (last2 — first2)) * 2 — 1 сравнений.

set_union создаёт сортированное объединение элементов из двух диапазонов. Он возвращает конец созданного диапазона. set_union устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1 — first1) + (last2 — first2)) * 2 — 1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

set_intersection создаёт сортированное пересечение элементов из двух диапазонов. Он возвращает конец созданного диапазона. Гарантируется, что set_intersection устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1 — first1) + (last2 — first2)) * 2 — 1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

set_difference создаёт сортированную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1 — first1) + (last2 — first2)) * 2 — 1 сравнений. Результат set_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

set_symmetric_difference создаёт сортированную симметричную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1 — first1) + (last2 — first2)) * 2 — 1 сравнений. Результат set_symmetric_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

Операции над пирамидами (Heap operations)

Пирамида — специфическая организация элементов в диапазоне между двумя итераторами произвольного доступа [a, b) . Два её ключевые свойства: (1) *a — самый большой элемент в диапазоне, (2) *a может быть удалён с помощью pop_heap или новый элемент добавлен с помощью push_heap за O(logN) время. Эти свойства делают пирамиды полезными для приоритетных очередей. make_heap преобразовывает диапазон в пирамиду, a sort_heap превращает пирамиду в сортированную последовательность.

push_heap полагает, что диапазон [first, last — 1) является соответствующей пирамидой, и надлежащим образом помещает значение с позиции last — 1 в результирующую пирамиду [first, last) . Выполняется максимально log(last — first) сравнений.

pop_heap полагает, что диапазон [first, last) является соответствующей пирамидой, затем обменивает значения в позициях first и last — 1 и превращает [first, last — 1) в пирамиду. Выполняется максимально 2 * log(last — first) сравнений.

make_heap создает пирамиду из диапазона [first, last) . Выполняется максимально 3 * (last — first) сравнений.

sort_heap сортирует элементы в пирамиде [first, last) . Выполняется максимально NlogN сравнений, где N равно last — first . sort_heap не устойчив.

Минимум и максимум (Minimum and maximum)

min возвращает меньшее, а max большее. min и max возвращают первый параметр, когда их параметры равны.

max_element возвращает первый такой итератор i в диапазоне [first, last) , что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*i или comp(*i, *j) == false . Выполняется точно max((last — first) — 1, 0) соответствующих сравнений.

min_element возвращает первый такой итератор i в диапазоне [first, last) , что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*j или comp(*j, *i) == false . Выполняется точно max((last — first) — 1, 0) соответствующих сравнений.

Лексикографическое сравнение (Lexicographical comparison)

lexicographical_compare возвращает true , если последовательность элементов, определённых диапазоном [first1, last1) , лексикографически меньше, чем последовательность элементов, определённых диапазоном [first2, last2) . Иначе он возвращает ложь. Выполняется максимально 2 * min((last1 — first1), (last2 — first2)) сравнений.

Генераторы перестановок (Permutation generators)

next_permutation берёт последовательность, определённую диапазоном [first, last) , и трансформирует её в следующую перестановку. Следующая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator или comp . Если такая перестановка существует, возвращается true . Иначе он трансформирует последовательность в самую маленькую перестановку, то есть сортированную по возрастанию, и возвращает false . Максимально выполняется (last — first)/2 перестановок.

prev_permutation берёт последовательность, определённую диапазоном [first, last) , и трансформирует её в предыдущую перестановку. Предыдущая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator или comp . Если такая перестановка существует, возвращается true . Иначе он трансформирует последовательность в самую большую перестановку, то есть сортированную по убыванию, и возвращает false . Максимально выполняется (last — first)/2 перестановок.

Обобщённые численные операции (Generalized numeric operations)


Накопление (Accumulate)

accumulate подобен оператору APL reduction и функции Common Lisp reduce , но он избегает трудности определения результата уменьшения для пустой последовательности, всегда требуя начальное значение. Накопление выполняется инициализацией сумматора acc начальным значением init и последующим изменением его acc = acc + *i или acc = binary_op(acc, *i) для каждого итератора i в диапазоне [first, last) по порядку. Предполагается, что binary_op не вызывает побочных эффектов.

Скалярное произведение (Inner product)

inner_product вычисляет свой результат, инициализируя сумматор acc начальным значением init и затем изменяя его acc = acc + (*i1) * (*i2) или acc = binary_op1 (acc, binary_op2 (*i1, *i2)) для каждого итератора i1 в диапазоне [first, last) и итератора i2 в диапазоне [first2, first2 + (last — first)) по порядку. Предполагается, что binary_op1 и binary_op2 не вызывают побочных эффектов.

Частичная сумма (Partial sum)

partial_sum присваивает каждому итератору i в диапазоне [result, result + (last — first)) значение, соответственно равное ((. (*first + *(first + 1)) + . ) + *(first + (i — result))) или binary_op(binary_op(. binary_op(*first, *(first + 1)), . ), *(first + (i — result))) . Функция partial_sum возвращает result + (last — first) . Выполняется binary_op точно (last — first) — 1 раз. Ожидается, что binary_op не имеет каких-либо побочных эффектов. result может быть равен first .

Смежная разность (Adjacent difference)

adjacent_difference присваивает каждому элементу, указываемому итератором i в диапазоне [result + 1, result + (last — first)) значение, соответственно равное *(first + (i — result)) — *(first + (i — result) — 1) или binary_op(*(first + (i — result)), *(first + (i — result) — 1)) . Элемент, указываемый result , получает значение *first . Функция adjacent_difference возвращает result + (last — first) . Применяется binary_op точно (last — first) — 1 раз. Ожидается, что binary_op не имеет каких-либо побочных эффектов. result может быть равен first .

Адаптеры

Адаптеры — шаблонные классы, которые обеспечивают отображения интерфейса. Например, insert_iterator обеспечивает контейнер интерфейсом итератора вывода.

Адаптеры контейнеров (Container adaptors)

Часто бывает полезно обеспечить ограниченные интерфейсы контейнеров. Библиотека предоставляет stack , queue и priority_queue через адаптеры, которые могут работать с различными типами последовательностей.

Стек (Stack)

Любая последовательность, поддерживающая операции back , push_back и pop_back , может использоваться для модификации stack . В частности, могут использоваться vector , list и deque .

Например, stack > — целочисленный стек, сделанный из vector , а stack > — символьный стек, сделанный из deque .

Очередь (Queue)

Любая последовательность, поддерживающая операции front , push_back и pop_front , может использоваться для модификации queue . В частности, могут использоваться list и deque .

Очередь с приоритетами (Priority queue)

Любая последовательность, с итератором произвольного доступа и поддерживающая операции front , push_back и pop_front , может использоваться для модификации priority_queue . В частности, могут использоваться vector и deque .

Адаптеры итераторов (Iterator adaptors)


Обратные итераторы (Reverse iterators)

Двунаправленные итераторы и итераторы произвольного доступа имеют соответствующие адаптеры обратных итераторов, которые выполняют итерации через структуру данных в противоположном направлении.Они имеют те же самые сигнатуры, как и соответствующие итераторы. Фундаментальное соотношение между обратным итератором и его соответствующим итератором i установлено тождеством &*(reverse_iterator(i)) == &*(i — 1) . Это отображение продиктовано тем, что, в то время как после конца массива всегда есть указатель, может не быть допустимого указателя перед началом массива.

Итераторы вставки (Insert iterators)

Чтобы было возможно иметь дело с вставкой таким же образом, как с записью в массив, в библиотеке обеспечивается специальный вид адаптеров итераторов, называемых итераторами вставки ( insert iterators ). С обычными классами итераторов
while (first != last) *result++ = *first++;

вызывает копирование диапазона [first, last) в диапазон, начинающийся с result . Тот же самый код с result , являющимся итератором вставки, вставит соответствующие элементы в контейнер. Такой механизм позволяет всем алгоритмам копирования в библиотеке работать в режиме вставки ( insert mode ) вместо обычного режима наложения записей.

Итератор вставки создаётся из контейнера и, возможно, одного из его итераторов, указывающих, где вставка происходит, если это ни в начале, ни в конце контейнера. Итераторы вставки удовлетворяют требованиям итераторов вывода. operator* возвращает непосредственно сам итератор вставки. Присваивание operator=(const T& х) определено для итераторов вставки, чтобы разрешить запись в них, оно вставляет х прямо перед позицией, куда итератор вставки указывает. Другими словами, итератор вставки подобен курсору, указывающему в контейнер, где происходит вставка. back_insert_iterator вставляет элементы в конце контейнера, front_insert_iterator вставляет элементы в начале контейнера, а insert_iterator вставляет элементы, куда итератор указывает в контейнере. back_inserter , front_inserter и inserter — три функции, создающие итераторы вставки из контейнера.

Адаптеры функций (Function adaptors)

Функциональные адаптеры работают только с классами функциональных объектов с определёнными типами параметров и типом результата.

Отрицатели (Negators)

Отрицатели not1 и not2 берут унарный и бинарный предикаты соответственно и возвращают их дополнения.

Привязки (Binders)

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

Например, find_if(v.begin(), v.end(), bind2nd(greater (), 5)) находит первое целое число в векторе v большее, чем 5; find_if(v.begin(), v.end(), bind1st(greater (), 5)) находит первое целое число в v меньшее, чем 5.

Адаптеры указателей на функции (Adaptors for pointers to functions)

Чтобы позволить указателям на (унарные и бинарные) функции работать с функциональными адаптерами, библиотека обеспечивает следующее:

Например, replace_if(v.begin(), v.end(), not1(bind2nd(ptr_fun(strcmp), «C»)), «C++») заменяет все «С» на «C++» в последовательности v .

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

Примитивы управления памятью (Memory Handling Primitives)

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

Размер (в байтах) распределённого буфера — не меньше n*sizeof(T) .

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

Например, если система трансляции поддерживает _huge указатели с типом расстояния long long , обеспечивается следующая шаблонная функция:

Также обеспечиваются следующие функции:

deallocate освобождает буфер, выделенный allocate . Для каждой модели памяти имеются соответствующие шаблоны функций deallocate , construct и destroy , определённые с типом первого параметра, являющимся типом указателя в модели памяти.

get_temporary_buffer ищет наибольший буфер, не больше чем n*sizeof(T) , и возвращает пару, состоящую из адреса и размера (в единицах sizeof(T) ) буфера. return_temporary_buffer возвращает буфер, выделенный get_temporary_buffer .

Примеры программ с шаблонами

Эти примеры демонстрируют использование нового продукта STL ToolKit > от компании ObjectSpace . STL ToolKit > — это самый простой способ использования STL , который работает на большинстве комбинаций платформ/компиляторов, включая cfront , Borland , Visual C++ , Set C++ , ObjectCenter и последние компиляторы от Sun&HP .

Новые возможности С++17 и библиотеки STL

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


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

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

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

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

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

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

  1. Получаем доступ к отдельным значениям std:: pair . Представьте, что у нас есть математическая функция divide_remainder , которая принимает в качестве параметров делимое и делитель и возвращает частное и остаток в std::pair .

Рассмотрим следующий способ получения доступа к отдельным значениям полученной пары.

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

  1. Структурированные привязки работают и для std::tuple . Рассмотрим следу­ющий пример функции, которая возвращает информацию о ценах на акции:

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

  1. Декомпозицию можно применять и для пользовательских структур. В качестве примера создадим следующую структуру.

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

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

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

□ Количество переменных var1 , var2 . должно точно совпадать с количеством переменных в выражении, в отношении которого выполняется присваивание.

  • Элементом должен быть один из следующих объектов:
    • std::pair ;
    • std::tuple ;
    • структура. Все члены должны быть нестатическими и определенными в одном базовом классе. Первый объявленный член присваивается первой переменной, второй член — второй переменной и т. д.;
    • массив фиксированного размера.
  • Тип может иметь модификаторы auto, constauto, constauto& и даже auto&& .

Если в квадратных скобках вы укажете слишком мало или слишком много пере­менных, то компилятор выдаст ошибку.

В этом примере мы пытаемся поместить кортеж с тремя переменными всего в две переменные. Компилятор незамедлительно сообщает нам об ошибке:

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

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

Пример работает потому, что в момент итерации по контейнеру std::map мы получаем узлы std::pair на каждом шаге этого процесса. Именно эти узлы распаковываются с помощью структурированных при­вязок ( key_type представляет собой строку с именем species, а value_type — пере­менную count типа size_t ), что позволяет получить к ним доступ по отдельности в теле цикла.

До появления C++17 аналогичного эффекта можно было достичь с помощью std ::tie :

Здесь показано, как распаковать полученную пару в две переменные. Примене­ние контейнера std::tie не так удобно, как использование декомпозиции, ведь нам надо заранее объявить все переменные, которые мы хотим связать. С другой сто­роны, пример демонстрирует преимущество std::tie перед структурированными привязками: значение std::ignore играет роль переменной-пустышки. В данном случае частное нас не интересует и мы отбрасываем его, связав с std::ignore .

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

Раньше функцию divide_remainder можно было реализовать следующим об­разом, используя выходные параметры:

Получить к ним доступ можно так:

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

Помимо того что аналогичной возможности нет в языке C, возврат сложных структур в качестве выходных параметров долгое время счи­тался медленным, поскольку объект сначала нужно инициализировать в возвращающей функции, а затем скопировать в переменную, которая должна будет содержать возвращаемое значение на вызывающей сторо­не. Современные компиляторы поддерживают оптимизацию возвраща­емых значений ( return value optimization , RVO ), что позволяет избежать создания промежуточных копий.

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

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

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

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

  • Выражение if . Допустим, нужно найти символ в таблице символов с помощью метода findконтейнера std::map :
  • Выражение switch . Так выглядит код получения символа из пользовательско­го ввода и его одновременная проверка в выражении switch для дальнейшего управления персонажем компьютерной игры:

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

Выражения if и switch с инициализаторами по сути являются синтаксическим сахаром. Два следующих фрагмента кода эквивалентны:

То же верно и для выражений switch.

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

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

Еще один интересный вариант — ограниченная область видимости критических секций. Рассмотрим следующий пример:

Сначала создается std::lock_guard . Этот класс принимает мьютекс в каче­стве аргумента конструктора. Он запирает мьютекс в конструкторе, а затем, когда выходит из области видимости, отпирает его в деструкторе. Таким об­разом, невозможно забыть отпереть мьютекс. До появления С++17 требовалась дополнительная пара скобок, чтобы определить область, где мьютекс снова откроется.

Не менее интересный пример — это область видимости слабых указателей. Рас­смотрим следующий фрагмент кода:

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

Выражения if с инициализаторами особенно хороши при работе с устаревшими API, имеющими выходные параметры:

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

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

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

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

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

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

Переменные инициализируются в один прием. При использовании синтаксиса инициализатора могут возникнуть две разные ситуации.

  1. Применение синтаксиса инициализатора с фигурными скобками без выведения типа auto :
  1. Использование синтаксиса инициализатора с фигурными скобками с выведе­нием типа auto :

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

Отдельно от механизма выведения типа auto оператор <> ведет себя предсказуемо, по крайней мере при инициализации обычных типов. При инициализации кон­тейнеров наподобие std::vector , std::list и т. д. инициализатор с фигурными скобками будет соответствовать конструктору std:: initializer_list этого класса контейнера. При этом он не может соответствовать неагрегированным конструкто­рам (таковыми являются обычные конструкторы, в отличие от тех, что принимают список инициализаторов).

std::vector , например, предоставляет конкретный неагрегированный кон­структор, заносящий в некоторое количество элементов одно и то же значение: std::vector v (N, value) . При записи std::vector v

выбирается конструктор initializer_list , инициализирующий вектор с двумя элементами: N и value. Об этом следует помнить.

Есть интересное различие между оператором <> и вызовом конструктора с по­мощью обычных скобок () . В первом случае не выполняется неявных преобразова­ний типа: int x (1.2) ; и int x = 1.2 ; инициализируют переменную x значением 1, округлив в нижнюю сторону число с плавающей точкой и преобразовав его к типу int . А вот выражение int x <1.2>; не скомпилируется, поскольку должно точно соответствовать типу конструктора.

Кто-то может поспорить о том, какой стиль инициализации является лучшим. Любители стиля с фигурными скобками говорят, что последние делают процесс явным, переменная инициализируется при вызове конструктора и эта строка кода ничего не инициализирует повторно. Более того, при использовании фигурных скобок <> будет выбран единственный подходящий конструктор, в то время как в момент применения обычных скобок () — ближайший похожий конструктор, а также выполнится пре­образование типов.

Дополнительное правило, включенное в С++17, касается инициализации с выведением типа auto: несмотря на то что в C++11 тип переменной auto x <123>; ( std::initializer_list с одним элементом) будет определен кор­ректно, скорее всего, это не тот тип, который нужен. В С++17 та же переменная будет типа int .

  • в конструкции autovar_name ; переменная var_nameбудет иметь тот же тип, что и one_element;
  • конструкция autovar_name ; недействительна и не будет скомпилирована;
  • конструкция autovar_name= ; будет иметь тип std::initializer_list , где T — тип всех элементов списка.

В С++17 гораздо сложнее случайно определить список инициализаторов.

Попытка скомпилировать эти примеры в разных компиляторах в режи­ме C++11 или C++14 покажет, что одни компиляторы автоматически выводят тип auto x <123>; как int , а другие — как std::initializer_list . Подобный код может вызвать проблемы с переносимостью!

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

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

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

Данную особенность очень удобно проиллюстрировать на примере создания экзем­пляров типа std::pair и std::tuple . Это можно сделать за один шаг:

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

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

О’кей, это всего лишь еще один класс шаблона. Вот как мы раньше создавали его объект (инстанцировали шаблон):

Теперь же можно опустить специализацию шаблона:

До появления C++17 это было возможно только при реализации вспомогатель­ной функции:

Используя подобные вспомогательные функции, можно было добиться такого же эффекта:

STL предоставляет множество аналогичных инструментов: std::make_ shared , std::make_unique , std::make_tuple и т. д. В C++17 эти функции могут считаться устаревшими. Но, конечно, они все еще будут работать для обеспечения обратной совместимости.

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

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

Эта структура, sum, принимает произвольное количество параметров и сумми­рует их с помощью выражений свертки (пример, связанный с выражениями свертки, мы рассмотрим далее в этой главе). Полученная сумма сохраняется в переменную-член value . Теперь вопрос заключается в том, что за тип — T? Если мы не хотим указывать его явно, то ему следует зависеть от типов значений, переданных в кон­структор. В случае передачи объектов-строк тип должен быть std: :string . При передаче целых чисел тип должен быть int . Если мы передадим целые числа, числа с плавающей точкой и числа с удвоенной точностью, то компилятору следует опре­делить, какой тип подходит всем значениям без потери точности. Для этого мы предоставляем явные правила выведения типов:

Согласно этим правилам компилятор может использовать типаж std::common_ type_t , который способен определить, какой тип данных подходит всем значениям. Посмотрим, как его применить:

В первой строке мы создаем объект типа sum на основе аргументов конструкто­ра, имеющих типы unsigned , double , int и float . Типаж std:: common_type_t возвра­щает тип double , поэтому мы получаем объект типа sum . Во второй строке мы предоставляем экземпляр типа std::string и строку в стиле C. В соответствии с нашими правилами компилятор создает экземпляр типа sum .

При запуске этот код выведет значение 10 как результат сложения чисел и abcdef в качестве результата объединения строк.

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

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

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

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

    1. Напишем обобщенную часть кода. В нашем примере рассматривается простой класс, который добавляет значение типа Uк элементу типа Tс помощью функ­ции add :
  1. Представим, что тип T — это std::vector , а тип U — просто int . Каков смысл выражения «добавить целое число к вектору»? Допустим, нужно добавить данное число к каждому элементу вектора. Это делается в цикле:
  1. Следующий и последний шаг заключается в том, чтобы объединить оба вари­анта. Если T — это вектор, состоящий из элементов типа U , то выполняем цикл. В противном случае выполняем обычное сложение.
  1. Теперь класс можно использовать. Посмотрим, насколько хорошо он мо­жет работать с разными типами, такими как int , float , std::vector и std::vector :


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

Новая конструкция constexpr-if работает точно так же, как и обычные конструк­ции if-else . Разница между ними заключается в том, что значение условного выражения определяется во время компиляции. Весь код завершения, который компилятор сгенерирует из нашей программы, не будет содержать дополнительных ветвлений, относящихся к условиям constexpr-if . Кто-то может сказать, что эти механизмы работают так же, как и макросы препроцессора #if и #else , предназначенные для подстановки текста, но в данном случае всему коду даже не нужно быть синтаксически правильным. Ветвления конструкции constexpr-if должны быть синтаксически правильными, но неиспользованные ветви не обязаны быть семантически корректными.

В одном блоке constexpr-if-else может оказаться несколько условий (обра­тите внимание, что a и b должны зависеть от параметров шаблона, а не только от констант времени компиляции):

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

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

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

Без конструкций constexpr-if этот класс работает для всех необходимых нам типов, но кажется очень сложным. Как же он работает?

Сами реализации двух разных функций add выглядят просто. Все усложняет объявление возвращаемого типа — выражение наподобие std::enable_if_t обращается в тип, если выполняется условие. В противном случае вы­ражение std::enable_if_t ни во что не обращается. Обычно такое положение дел считается ошибкой. Далее мы рассмотрим, почему в нашем случае это не так.

Для второй функции add то же условие используется противоположным обра­зом. Следовательно, условие может иметь значение true только для одной из двух реализаций в любой момент времени.

Когда компилятор видит разные шаблонные функции с одинаковым именем и должен выбрать одну из них, в ход вступает важный принцип: он обозначается аббревиатурой SFINAE, которая расшифровывается как Substitution Failure is not an ErrorСбой при подстановке — не ошибка»). В данном случае это значит, что компилятор не генерирует ошибку, если возвращаемое значение одной из функций нельзя вывести на основе неверного шаблонного выражения (то есть std::enable_if , когда условие имеет значение false ). Он просто продолжит работу и попробует обработать другие реализации функции. Вот и весь секрет.

Столько возни! Радует, что после выхода C++17 делать это стало гораздо проще.

Подключаем библиотеки с помощью встраиваемых переменных

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

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

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

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

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

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

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

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

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

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

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

Рис. 1. Правило одного определения (one definition rule, ODR)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 2. Бинарные свертки

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

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

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

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

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

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

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

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

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

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

В конечном счете функция складывает все результаты и возвращает их вызыва­ющей стороне.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стандартная библиотека шаблонов (Standard Template Library, STL) содержит унифицированные средства для работы с коллекциями с применением современных и эффективных алгоритмов. Благодаря STL программисты могут пользоваться новыми разработками в области структур данных и алгоритмов, не разбираясь в принципах их работы.

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

Компоненты STL

Работа STL основана на взаимодействии разных структурных компонентов, среди которых центральное место занимают контейнеры, итераторы и алгоритмы.

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

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

Интерфейс итераторов имеет много общего с интерфейсом обычных указателей. Увеличение итератора производится оператором ++, а для обращения к значению, на которое ссылается оператор, используется оператор *. Таким образом, итератор можно рассматривать как своего рода умный указатель, который преобразует команду «перейти к следующему элементу» в конкретные действия, необходимые для конкретного типа контейнера.

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

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

Концепция STL основана на разделении данных и операций. Данные находятся под управлением контейнерных классов, а операции определяются адаптируемыми алгоритмами. Итераторы выполняют функции «клея», связывающего эти два компонента. Благодаря им любой алгоритм может работать с любым контейнером (рис. 9.1).

Рис. 9.1. Компоненты STL

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

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

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

Контейнеры

Контёйнерные классы (или проще — контейнеры) управляют коллекциями элементов. Для разных потребностей программиста в STL предусмотрены разные типы контейнеров (рис, 9.2).

Рис. 9.2. Типы контейнеров STL

Контейнеры делятся на две категории.

Последовательные контейнеры представляют собой упорядоченные коллекции, в которых каждый элемент занимает определенную позицию. Позиция зависит от времени и места вставки, но не связана со значением элемента. Например, если последовательно присоединить шесть элементов к концу существующей коллекции, эти элементы будут следовать в порядке их занесения. STL содержит три стандартных класса последовательных контейнеров: vector (вектор), deque (дек) и list (список).

Ассоциативные контейнеры представляют собой отсортированные коллекции, в которых позиция элемента зависит от его значения по определенному критерию сортировки. После занесения шести элементов в коллекцию порядок их следования будет определяться только их значениями. Последовательность вставки значения не имеет. STL содержит три стандартных класса ассоциативных контейнеров: set (множество), mullet (мультимножество), mар (отображение) и multimap (мультиотображение).

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

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

Дата добавления: 2020-10-15 ; просмотров: 193 | Нарушение авторских прав

АйТи бубен

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

Инструменты сайта

Содержание

Шаблоны STL

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

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

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

Справочники по STL

Контейнеры

Алгоритмы

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

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

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

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

for_earch() — выполняет операции для каждого элемента последовательности find() — находит первое вхождение значения в последовательность find_if() — находит первое соответствие предикату в последовательности count() — подсчитывает количество вхождений значения в последовательность count_if() — подсчитывает количество выполнений предиката в последовательности search() — находит первое вхождение последовательности как подпоследовательности search_n()- находит в последовательности подпоследовательность, состоящую из n повторений и возвращает её первое вхождение.

copy() — копирует последовательность, начиная с первого элемента swap() — меняет местами два элемента replace() — заменяет элементы с указанным значением replace_if() — заменяет элементы при выполнении предиката replace_copy() — копирует последовательность, заменяя элементы с указанным значением replace_copy_if() — копирует последовательность, заменяя элементы при выполнении предиката fill() — заменяет все элементы данным значением remove() — удаляет элементы с данным значением remove_if() — удаляет элементы при выполнении предиката remove_copy() — копирует последовательность, удаляя элементы с указанным значением remove_copy_if() — копирует последовательность, удаляя элементы при выполнении предиката reverse() — меняет порядок следования элементов на обратный random_shuffle() — перемещает элементы согласно случайному равномерному распределению («тасует» последовательность) transform() — выполняет заданную операцию над каждым элементом последовательности unique() — удаляет равные соседние элементы unique_copy() — копирует последовательность, удаляя равные соседние элементы

sort() — сортирует последовательность с хорошей средней эффективностью partial_sort() — сортирует часть последовательности stable_sort() — сортирует последовательность, сохраняя порядок следования равных элементов lower_bound() — находит первый элемент, меньший чем заданное значение upper_bound() — находит первый элемент, больший чем заданное значение binary_search() — определяет, есть ли данный элемент в отсортированной последовательности merge() — сливает две отсортированные последовательности

includes() — проверка на вхождение set_union() — объединение множеств set_intersection() — пересечение множеств set_difference() — разность множеств

min() — меньшее из двух max() — большее из двух min_element() — наименьшее значение в последовательности max_element() — наибольшее значение в последовательности Перестановки. next_permutation() — следующая перестановка в лексикографическом порядке prev_permutation() — предыдущая перестановка в лексикографическом порядке

Предикаты

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

Наверное, вы уже догадались, что создать предикат достаточно легко — нужно просто написать функцию которая возвращает тип bool. Рассмотрим пример. Попробуем создать предикат, определяющий четность числа. Если число окажется четным, предикат будет возвращать true.

Мастер Йода рекомендует:  Как создать фантастического пылающего оленя
Добавить комментарий