Stl c что это

Шаблоны STL

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

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

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

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

Алгоритм (algorithm) — специальная функция для работы с данными, содержащимися в контейнере.

Итератор (iterator) — специальный указатель, который позволяет алгоритмам перемещаться по данным конкретного контейнера. Итератор прослойка между контейнерами и алгоритмами. Посредством итератора мы удаляемся от понятия типа контейнера, т.е. к разным контейнерам можно применять одинаковые алгоритмы.

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

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

Аллокатор — распределитель памяти. Такой распределитель памяти имеется у каждого конкретного контейнера. Данная конструкция просто-напросто управляет процессом выделения памяти для контейнера. Следует отметить, что по умолчанию распределителем памяти является объект класса allocator. Однако, можно определить свой собственный распределитель.

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

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

Официальный справочники по STL в Linux

# apt install stl-manual $ firefox file:///usr/share/doc/stl-manual/html/index.html

Контейнеры

STL: Класс auto_ptr C++ (automatic pointer — автоматический указатель)
Класс vector — заменяет динамический массив.
Класс list — рассчитан на поиск. К данным нельзя обратиться через [], только через итератор.

Контейнеры STL: Класс map — быстрый поиск значений по ключу. Map будет игнорировать вставку если пара уже существует. Поддерживает ассоциативный контейнер (т.е. ключ может быть строкой)

Класс multimap — поддерживает повторяющиеся ключи в отличии от map

Алгоритмы

В библиотеке 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 принято решать данную проблему иным способом. А именно, создавать предикаты.

Предикат — специальная функция, которая возвращает логическое значение (true либо false).

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

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

Четность определяется получением остатка от деления на 2.

Затем, заполняется контейнер-список значениями от 1 до 10. (для этого вызывается метод push_back(), который добавляет значение в конец списка)

Затем значения выводятся на экран.
Далее осуществляется поиск и выделение всех четных значений.

Эту задачу решает алгоритм remove_if. Обратите внимания, что многие алгоритмы, оканчивающиеся на _if, в качестве последнего параметра используют предикаты. Алгоритм remove_if сдвигает все подходящие значения в начало контейнера и возвращает итератор, который указывает на элемент, следующий за удаляемыми значениями. По этой причине, мы будем считать, что начиная с адреса, на который ссылается возвращаемый итератор, и до конца области данных контейнера располагаются неудаленные значения, для которых предикат вернул false. Здесь, в нашем примере, мы используем данную особенность следующим образом: все четные значения выводятся на экран (для этого мы копируем их в поток вывода, передав потоковому итератору пару итераторов, которые описывают область удаленных значений.)

#include #include #include using namespace std; // предикат bool isEven(int num) { return bool(num % 2); } void main() { listint> l; listint>::iterator t; for(int i=1; i10; i++) l.push_back(i); copy(l.begin(), l.end(), ostream_iteratorint>(cout," ")); cout<"\n\n"; t=remove_if(l.begin(), l.end(), isEven); copy(l.begin(), t, ostream_iteratorint>(cout," ")); }

Обзор стандартной библиотеки C++ (STL)

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

Стандарт C++ определяет два типа соответствующих библиотек:

• Размещенная реализация, которая поддерживает все необходимые заголовки стандартной библиотеки, описанные стандартом ISO C++.
• Нестандартная реализация, требующая только подмножества заголовков стандартной библиотеки. Обязательный подмножество:

Следующие заголовки устарели, так как C++11: , и .

Другие различия между автономными и размещенными реализациями:

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

Стандартная библиотека Microsoft C++ удовлетворяет требованиям как к стандартной, так и размещенной.

Заголовки библиотек C++ имеют два широких подраздела:

• Соглашения iostreams.
• Справочные соглашения о стандартной библиотеке C++ (STL).

Этот раздел содержит следующие разделы:

• Использование заголовков библиотеки C++
• Соглашения о библиотеке C++
• Соглашения iostreams
• Запуск и завершение программы C++
• библиотеки Сейф: стандартная библиотека C++
• Проверенные итераторы
• Поддержка итератора отладки
• Справочник по стандартной библиотеке C++ (STL)
• Безопасность потоков в стандартной библиотеке C++
• Пространство имен stdext
• Регулярные выражения (C++)

Дополнительные сведения о библиотеках времени выполнения Visual C++ см. в разделе Функции библиотеки CRT.

Реализация стандартной библиотеки C++ майкрософт часто называется библиотекой шаблонов STL или Standard. Хотя стандартная библиотека C++ является официальным именем библиотеки , как определено в ISO 14882, из-за популярного использования STL и «Стандартной библиотеки шаблонов» в поисковых системах, мы иногда используем эти имена, чтобы упростить поиск нашей документации. С исторической точки зрения , «STL» первоначально ссылается на стандартную библиотеку шаблонов, написанную Александром Стефановым. Части этой библиотеки были стандартизированы в стандартной библиотеке C++ вместе с библиотекой среды выполнения ISO C, частями библиотеки Boost и другими функциями. Иногда «STL» также используется для ссылки на контейнеры и алгоритмы стандартной библиотеки C++, адаптированной из STL Стефанова. В этой документации стандартная библиотека шаблонов (STL) ссылается на стандартную библиотеку C++ в целом.

Использование STL в C++

Цель этой статьи ознакомить читателя с библиотекой STL — стандартной библиотекой шаблонов и максимально доступно объяснить принципы использования данной библиотеки а так же показать ее использование на примерах

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

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

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

• vector — коллекция элементов Т, сохраненных в массиве, увеличиваемом по мере необходимости. Для того, чтобы начать использование данной коллекции, включите #include .
• list — коллекция элементов Т, сохраненных, как двунаправленный связанный список. Для того, чтобы начать использование данной коллекции, включите #include .
• map — это коллекция, сохраняющая пары значений pair. Эта коллекция предназначена для быстрого поиска значения T по ключу const Key. В качестве ключа может быть использовано все, что угодно, например, строка или int но при этом необходимо помнить, что главной особенностью ключа является возможность применить к нему операцию сравнения. Быстрый поиск значения по ключу осуществляется благодаря тому, что пары хранятся в отсортированном виде. Эта коллекция имеет соответственно и недостаток — скорость вставки новой пары обратно пропорциональна количеству элементов, сохраненных в коллекции, поскольку просто добавить новое значение в конец коллекции не получится. Еще одна важная вещь, которую необходимо помнить при использовании данной коллекции — ключ должен быть уникальным. Для того, чтобы начать использование данной коллекции, включите #include . Если вы хотите использовать данную коллекцию, чтобы избежать дубликатов, то вы избежите их только по ключу.
• set — это коллекция уникальных значений const Key — каждое из которых является также и ключом — то есть, проще говоря, это отсортированная коллекция, предназначенная для быстрого поиска необходимого значения. К ключу предъявляются те же требования, что и в случае ключа для map. Естественно, использовать ее для этой цели нет смысла, если вы хотите сохранить в ней простые типы данных, по меньшей мере вам необходимо определить свой класс, хранящий пару ключ — значение и определяющий операцию сравнения по ключу. Очень удобно использовать данную коллекцию, если вы хотите избежать повторного сохранения одного и того же значения. Для того, чтобы начать использование данной коллекции, включите #include .
• multimap — это модифицированный map, в котором отсутствует требования уникальности ключа — то есть, если вы произведете поиск по ключу, то вам вернется не одно значение, а набор значений, сохраненных с данным ключом. Для того, чтобы начать использование данной коллекции включите #include .
• multiset — то же самое относится и к этой коллекции, требования уникальности ключа в ней не существует, что приводит к возможности хранения дубликатов значений. Тем не менее, существует возможность быстрого нахождения значений по ключу в случае, если вы определили свой класс. Поскольку все значения в map и set хранятся в отсортированном виде, то получается, что в этих коллекциях мы можем очень быстро отыскать необходимое нам значение по ключу, но при этом операция вставки нового элемента T будет стоить нам несколько дороже, чем например в vector. Для того, чтобы начать использование данной коллекции, включите #include .

STL Строки

Не существует серьезной библиотеки, которая бы не включала в себя свой класс для представления строк или даже несколько подобных классов. STL — строки поддерживают как формат ASCII, так и формат Unicode.

• string — представляет из себя коллекцию, хранящую символы char в формате ASCII. Для того, чтобы использовать данную коллекцию, вам необходимо включить #include .
• wstring — это коллекция для хранения двухбайтных символов wchar_t, которые используются для представления всего набора символов в формате Unicode. Для того, чтобы использовать данную коллекцию, вам необходимо включить #include .

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

Используются для организации сохранения простых типов данных в STL строки в стиле C++. Практическое знакомство с STL мы начнем именно с этого класса. Ниже приведена простая программа, демонстрирующая возможности использования строковых потоков:

//stl.cpp: Defines the entry point for the console application // #include «stdafx.h» #include #include #include using namespace std; int _tmain (int argc, _TCHAR* argv []) < strstream xstr; for (int i = 0; i < 10; i++) < xstr cout

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

Далее мы производим копирование содержимого буфера в строку и печатаем строку второй раз. На этот раз она печатается без мусора.

Основные методы, которые присутствуют почти во всех STL коллекциях, приведены ниже.

• empty — определяет, является ли коллекция пустой.
• size — определяет размер коллекции.
• begin — возвращает прямой итератор, указывающий на начало коллекции.
• end — возвращает прямой итератор, указывающий на конец коллекции. При этом надо учесть, что реально он не указывает на ее последний элемент, а указывает на воображаемый несуществующий элемент, следующий за последним.
• rbegin — возвращает обратный итератор, указывающий на начало коллекции.
• rend — возвращает обратный итератор, указывающий на конец коллекции. При этом надо учесть, что реально он не указывает на ее последний элемент, а указывает на воображаемый несуществующий элемент, следующий за последним.
• clear — удаляет все элементы коллекции, при этом, если в вашей коллекции сохранены указатели, то вы должны не забыть удалить все элементы вручную посредством вызова delete для каждого указателя.
• erase — удаляет элемент или несколько элементов из коллекции.
• capacity — вместимость коллекции определяет реальный размер — то есть размер буфера коллекции, а не то, сколько в нем хранится элементов. Когда вы создаете коллекцию, то выделяется некоторое количество памяти. Как только размер буфера оказывается меньшим, чем размер, необходимый для хранения всех элементов коллекции, происходит выделение памяти для нового буфера, а все элементы старого копируются в новый буфер. При этом размер нового буфера будет в два раза большим, чем размер буфера, выделенного перед этим — такая стратегия позволяет уменьшить количество операций перераспределения памяти, но при этом очень расточительно расходуется память. Причем в некоторых реализациях STL первое выделение памяти происходит не в конструкторе, а как ни странно, при добавлении первого элемента коллекции. Фрагмент программы ниже демонстрирует, что размер и вместимость коллекции — две разные сущности:

vector vec; cout cout 
При использовании микрософтовской реализации STL библиотеки (Visual C++ 7.0) у автора получилось 0 и 13 соответственно до и после заполнения вектора.
vector
Наиболее часто используемая коллекция - это вектор. Как уже было отмечено выше, внутренняя реализация этой коллекции представляет из себя массив и счетчик элементов, сохраненных в нем. Ниже приведена программа, демонстрирующая все основные методы этой коллекции:
Предположим, нам необходимо написать логику клиент - серверного приложения. Администратор сети посылает сообщения на сервер с определенным интервалом, где они сохраняются в одном общем массиве common, при этом каждое сообщение имеет поле To, однозначно идентифицирующее каждого клиента.
Каждый клиент также подключается к серверу, но с гораздо большим интервалом, чем приход сообщений от администратора, чтобы просмотреть сообщения, адресованные ему. При этом нам также необходимо знать хронологию прихода сообщений, адресованных разным пользователям (какое сообщение пришло раньше, а какое позже в любой момент времени). Для того, чтобы получить сообщения, клиент должен подключиться к серверу, просмотреть массив common для того, чтобы выбрать сообщения, адресованные ему, и после отключиться.
В нашем случае, три клиента подключаются к серверу и каждый просматривает общий массив сообщений, при этом мы должны сделать наше приложение поточно - безопасным, поэтому должны использовать код внутри критической секции. Все это рано или поздно приведет к тому, что с увеличением числа клиентов приложение станет очень медленным.
Для того, чтобы избежать этой ситуации, мы заведем массив сообщений для каждого клиента и вместо того, чтобы просматривать общий массив сообщений три раза, мы будем просматривать его всего лишь один раз с интервалом времени, адекватным периоду подключения одного клиента. При этом скопируем все сообщения в соответствующие массивы. Клиенты же будут просто забирать данные из своих массивов при подключении.
На самом деле это немного неправильный подход для решения этой задачи. Скорее всего, нам надо было бы сохранять сообщения в момент их прихода в оба массива, но наша цель - посмотреть возможности использования коллекции vector, поэтому воспользуемся этим подходом и представим упрощенную логику такого приложения:
//stl.cpp: Defines the entry point for the console application // #include "stdafx.h" #include #include #include #include #include using namespace std; class MyMessage < private: string from; string to; string message; int id; public: MyMessage (string from, string to, string message) < this - >from = from; this - >to = to; this - >message = message; > int GetId () < return this - >id; > void SetId (int id) < this - >id = id; > string GetMessage () < return this - >message; > string GetFrom () < return this - >from; > string GetTo () < return this - >to; > >; int _tmain (int argc, _TCHAR* argv []) < vectorcommon; // create pool of messages for 3 users: for (int user = 0; user < 3; user++) < for (int i = 0; i < 10; i++) < strstream messagex; messagex > // create vector for each user: vector user0; vector user1; vector user2; for (int x = 0; x < (int) common.size (); x++) < MyMessage message = common [x]; if (message.GetTo () == "User 0") < user0.push_back (message); >else if (message.GetTo () == "User 1") < user1.push_back (message); >else if (message.GetTo () == "User 2") < user2.push_back (message); >> cout cout cout cout
Теперь у вас есть некоторое представление о том, каким образом писать бизнес - логику приложений с использованием STL. Из этого приложения видно, что кроме перечисленных выше методов, у вектора есть оператор operator [], который позволяет нам пользоваться вектором так же, как обычным массивом. Этот оператор используется также в map, deque, string и wstring.
Итераторы
При перечислении основных методов коллекций упоминались итераторы, при этом не было дано определение этой сущности. Итератор - это абстракция, которая ведет себя, как указатель с некоторыми ограничениями или без них, то есть, сохраняет все свойства своего прародителя. Указатель - это тоже итератор. В действительности, итераторы, в большинстве случаев, это объектные обертки указателей. Вот как примерно может выглядеть внутреннее устройство итератора:
class Iterator < T* pointer; public: T* GetPointer () < return this - >pointer; > void SetPointer (T* pointer) < this - >pointer = pointer; > : >;
Но итератор представляет собой более высокий уровень абстракции, чем указатель, поэтому утверждение, что итератор - это указатель в некоторых случаях может быть неверно. А вот обратное будет верно всегда. Вот несколько формализованных определений для итератора:
Итераторы обеспечивают доступ к элементам в коллекции
Итераторы для конкретного класса коллекции определяются внутри класса этой коллекции. В STL существует три типа итераторов: iterator, reverse_iterator, и random access iterator. Для обхода коллекции от меньшего индекса к большему, используются обычные или forward итераторы. Для обхода коллекции в обратном направлении используются reverse итераторы. Random access iterator являются итераторами, которые могут обходить коллекцию как вперед, так и назад. Ниже приведен пример использования итераторов для удаления половины элементов вектора:
#include "stdafx.h" #include #include #include using namespace std; void printInt (int number); int _tmain (int argc, _TCHAR* argv []) < vectormyVec; vector::iterator first, last; for (long i=0; i first = myVec.begin (); last = myVec.begin () + 5; if (last >= myVec.end ()) < return - 1; >myVec.erase (first, last); for_each (myVec.begin (), myVec.end (), printInt); return 0; > void printInt (int number)
Важно помнить, что когда вы получаете итератор к коллекции, а после этого модифицируете коллекцию, то этот итератор становится уже непригодным к использованию. Естественно, не все изменения приводят к непригодности итератора для дальнейшего использования, а только изменения структуры коллекции. В случае же, если вы просто измените значения, сохраненные в коллекции, то ничего страшного не произойдет и итератор не испортится.
Итерация по коллекции вперед происходит так:
for (iterator element = begin (); element
Итерация по коллекции назад происходит так:
for (reverse_iterator element = rbegin (); element
Если вы работаете и с random access iterator итератором, то синтаксис конструкции может быть, например, таким:
for (iterator element = begin (); element
Для более эффективного использования контейнеров используйте typedef или наследуйте свой класс от класса коллекции.
Сделать это можно так:
typedef vector myVector typedef map myMap typedef deque myQue Или вот такая техника в случае наследования: class myVector: public vector <>;
В случае с итератором применима предыдущая техника:
typedef myVector::iterator vectorIterator typedef myVector::reverse_iterator revVectorIterator
Алгоритмы
До этого мы посмотрели основные приемы использования STL коллекций на примере использования вектора. Это основа STL, но для того, чтобы по - настоящему использовать всю мощь этой библиотеки, придется расширить наши знания. С использованием алгоритмов возможно создание очень мощных и эффективных программ. По компактности такой код превосходит код, написанный на таких современных языках, как Java и С#, и в значительной степени эффективнее последнего.
STL - алгоритмы представляют набор готовых функций, которые могут быть применены к STL коллекциям и могут быть подразделены на три основных группы:
Функции для перебора всех членов коллекции и выполнения определенных действий над каждым из них:
count, count_if, find, find_if, adjacent_find, for_each, mismatch, equal, search copy, copy_backward, swap, iter_swap, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, transform, remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, stable_partition 
Функции для сортировки членов коллекции:
Sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, pop_heap, sort_heap, min, max, min_element, max_element, lexographical_compare, next_permutation, prev_permutation 
Функции для выполнения определенных арифметических действий над членами коллекции:
Accumulate, inner_product, partial_sum, adjacent_difference 
Для того, чтобы использовать все это разнообразие, у вас под рукой должна быть соответствующая документация. Microsoft предлагает достаточно подробную документацию, как часть MSDN для своей реализации STL. Достаточно подробную и обстоятельную документацию предлагает так же SGI. Для того, чтобы использовать ее, вам придется загрузить STLPort библиотеку, представляющую из себя набор из документации и хедер - файлов. Эта библиотека заслуженно считается одной из лучших, Borland уже включил ее как часть своего продукта, так что если вы используете C++ Builder 6.0, то делать это необязательно. При этом вы можете использовать эту библиотеку практически с любыми компиляторами, так что, если вы действительно стремитесь к переносимости своего кода, то это хороший выбор.
Ранее мы уже использовали один из алгоритмов: for_each () для того, чтобы распечатать все значения из вектора. Я думаю, не требует дополнительных объяснений то, что произошло при этом. Единственное, что бы хотелось отметить, что, кроме указателя на функцию в этом случае мы могли бы передать функтор - специальный класс с перегруженным оператором operator (). Для того, чтобы показать, как это делается, ниже приведена простая программа.
#include "stdafx.h" #include #include #include #include #include using namespace std; class MyFunctor < string comment; public: MyFunctor () < comment = "My comment"; >; MyFunctor (string comment) < this - >comment = comment; > void operator ()(int test) < cout ; >; int _tmain (int argc, _TCHAR* argv []) < vectortest; // fill vector: for (int i = 0; i < 5; i++) < test.push_back (i); >// now use our functor: MyFunctor functor (" Test comment"); for_each (test.begin (), test.end (), functor); return 0; >
Преимущество такого подхода заключается в том, что если нам необходимо передать какие - либо параметры для того, чтобы произвести обработку каждого члена коллекции, то мы имеем возможность сделать это в конструкторе функтора или определить дополнительные функции в классе - функторе. Это позволит нам сократить количество переменных в области видимости функции - обработчика членов коллекции для хранения значений, которые впоследствии будут использованы внутри тела этой функции. Если же для работы над членами коллекции нам не нужно передавать параметры, то целесообразнее определить просто функцию.
Еще один небольшой пример использования алгоритмов приведен ниже, мы создаем две коллекции: женскую и мужскую, после чего заполняем каждую из них соответствующими именами мужчин и женщин. Если мы захотим поменять местонахождение членов обоих коллекций - то есть, женщин поместить в мужскую коллекцию и наоборот, то сделать это с использованием алгоритмов очень просто:
#include "stdafx.h" #include #include #include #include #include using namespace std; void printMan (string user); int _tmain (int argc, _TCHAR* argv []) < vectormaleRoom; vector fimaleRoom; maleRoom.push_back ("Vasya"); maleRoom.push_back ("Petya"); maleRoom.push_back ("Sasha"); fimaleRoom.push_back ("Nastya"); fimaleRoom.push_back ("Alena"); fimaleRoom.push_back ("Sveta"); for_each (maleRoom.begin (), maleRoom.end (), printMan); reverse (maleRoom.begin (), maleRoom.end ()); cout void printMan (string man)


Предикаты
Для многих алгоритмов STL необходимо задать условие, посредством которого алгоритм определяет, что ему необходимо делать с тем или иным членом коллекции. По определению, предикат - это функция, принимающая один или более параметров и возвращающая значения истина или ложь. Предикат может быть функцией или функтором. Существует также набор стандартных предикатов. Рассмотрим некоторые способы использования предикатов в библиотеке стандартных шаблонов на примере алгоритмов find_if и sort:
#include "stdafx.h" #include #include #include #include #include #include using namespace std; class Man; ostream& operator Man (string name, string sex, int age) < this - >name = name; this - >sex = sex; this - >age = age; > int GetAge () < return this - >age; > void SetAge (int age) < this - >age = age; > string GetName () < return this - >name; > void SetName (string name) < this - >name = name; > string GetSex () < return this - >sex; > void SetSex (string sex) < this - >sex = sex; > void PrintInfo () < cout >; ostream& operator ; class ManLess < public: bool operator ()(Man& man1, Man& man2) < if (man1.GetAge () < man2.GetAge ()) < return false; >else < return true; >>; >; bool ManOlderThan23(Man& man) < if (man.GetAge () >23) < return true; >else < return false; >>; class ManOlderThan < int m_age; public: ManOlderThan (int age) < m_age = age; >; bool operator ()(Man& man) < if (man.GetAge () >m_age) < return true; >else < return false; >>; >; int _tmain (int argc, _TCHAR* argv []) < // create 3 men Man man1("Dima", "male", 23); Man man2("Sasha", "male", 30); Man man3("Sergey", "male", 32); vectorprogrammers; programmers.push_back (man1); programmers.push_back (man2); programmers.push_back (man3); // find and print all programmers older than 23 cout << "Find all programmers older than 23 " << endl; vector::iterator p = find_if (programmers.begin (), programmers.end (), ManOlderThan23); while (p!= programmers.end ()) < cout // here is the same in more flexible way: cout


На первый взгляд, этот пример выглядит довольно запутанно, но на самом деле все очень просто. Первое, что мы делаем, это включаем упреждающее объявление класса Man, оно необходимо нам для того, чтобы, в свою очередь, использовать его в упреждающем объявлении перегруженного оператора 
Далее описывается предикат - функтор LessMan, необходимый для сортировки членов нашего вектора. Он принимает два параметра типа Man. Он будет использован для сортировки в порядке убывания по возрасту программистов. ManOlderThan23 - это предикат - функция, которая отбирает всех программистов старше 23 лет. После этого мы определяем точно такой же предикат - функтор ManOlder с возможностью устанавливать минимальный возраст человека в момент его создания. Такой подход гораздо гибче предыдущего.
После входа в функцию main () мы создаем вектор programmers и заполняем его программистами: Дима, Саша и Сергей. Далее мы находим и распечатываем всех программистов старше 23 лет двумя способами, после этого сортируем и распечатываем весь список наших программистов в порядке убывания по возрасту.
Стоит отметить, что эта программа будет выполнять два первых действия корректно только в случае, если все программисты отсортированы по возрастанию. Подумайте, как нужно изменить алгоритм так, чтобы они выполнялись корректно всегда.
Еще одной особенностью этого кода является то, что мы получаем указатель на функцию класса с помощью mem_fun_ref. Как видим, иногда это бывает очень полезно. Для того, чтобы воспользоваться этой возможностью, необходимо включить #include .
Потокобезапасность
STL не потокобезопасная библиотека, но исправить это очень просто. Предположим, вам необходимо сохранять данные в вашу коллекцию в одном потоке, когда другой поток также сохраняет их туда. Тогда просто используйте критическую секцию или Mutex.
Пример реализации потокобезопасной коллекции для WIN32 с использованием критической секции приведен ниже:
#include "stdafx.h" #include #include #include #include #include #include using namespace std; void printInt (int number); class MyCriticalSection < private: CRITICAL_SECTION CriticalSection; bool success; public: MyCriticalSection () < success = true; // Initialize the critical section. InitializeCriticalSection (&CriticalSection); >; bool Lock () < // Request ownership of the critical section. __try < EnterCriticalSection (&CriticalSection); return true; >__except (EXCEPTION_EXECUTE_HANDLER) < // Release ownership of the critical section. LeaveCriticalSection (&CriticalSection); // Release resources used by the critical section object. DeleteCriticalSection (&CriticalSection); success = false; return false; >>; void Unlock () < if (success) < // Release ownership of the critical section. LeaveCriticalSection (&CriticalSection); >>; ~MyCriticalSection () < // Release resources used by the critical section object. if (success) < DeleteCriticalSection (&CriticalSection); >>; >; // define thread safe vector of integers class VectorInt: public vector, MyCriticalSection < public: VectorInt (): vector(), MyCriticalSection () <> void safe_push_back (int arg) < Lock (); push_back (arg); Unlock (); >>; int _tmain (int argc, _TCHAR* argv []) < VectorInt vx; for (int i = 0; i < 5; i++) < vx.safe_push_back (i); >for_each (vx.begin (), vx.end (), printInt); return 0; > void printInt (int number)
Для начала мы создаем объектную обертку для критической секции. Далее создаем класс, который будет потомком двух классов: вектора с целочисленным параметром и нашей обертки и добавляем в него нашу потокобезопасную функцию, внутри которой вызываем метод вектора для добавления нового элемента в коллекцию.
Заключение
Достоинство STL - это то, что библиотека действительно является кроссплатформенной. И это не пустая декларация, как происходит со многими другими технологиями. Я думаю, что существует больше платформ, не поддерживающих Java, чем компиляторов C++ для этих же платформ, не поддерживающих STL. Конечно, не существует абсолютной гарантии, что она встроена абсолютно во все компиляторы C++. Например, некоторые компиляторы для мобильных устройств и микроконтроллеров не включают эту библиотеку. Это обусловлено тем, что она является относительно неэффективной в плане использования памяти, поскольку оптимизирована для обеспечения максимальной скорости. В мобильных устройствах, как известно, самый дорогой ресурс - это память, в то время как на вашем PC сегодня его в избытке. Поэтому иногда вам придется писать шаблонные классы, похожие на классы STL, самостоятельно для того, чтобы например перенести приложение, работающее под Windows или Linux на мобильное устройство. Автор этой статьи, например, реализовал класс vector, который более бережно относится к памяти, чем его прототип, именно для такого проекта.
Автор постарался выбрать все наиболее ценное для использования на практике. Все примеры были оттестированы в среде VC7++. При создании использовался тип консольного Win32 приложения без поддержки ATL и MFC. Автор надеется, что они также хорошо будут работать при компиляции на других платформах. Естественно, за исключением приложения, демонстрировавшего создание потокобезапасной коллекции, все их можно собрать, скажем на Linux с использованием GCC. Как это делать, было подробно описано в моей предыдущей статье.
STL: стандартная библиотека шаблонов С++

Механизм шаблонов встроен в компилятор C++, чтобы дать возможность программистам делать свой код короче за счет обобщенного программирования. Естественно, существуют и стандартные библиотеки, реализующие этот механизм. STL является самой эффективной библиотекой C++ на сегодняшний день.
Сейчас существует немало ее реализаций, каждая из которых, хоть и создана в рамках стандарта, обладает собственными расширениями. У подобного подхода есть один недостаток: не всегда код будет работать одинаково с разными компиляторами. Поэтому настоятельно рекомендуем вам максимально придерживаться традиционных приемов, как бы хорошо вы не разбирались в конкретной реализации библиотеки.
Первое знакомство
Для начала рассмотрим самые популярные коллекции из библиотеки. Каждая из них имеет собственный набор шаблонных параметров, чтобы быть максимально удобной для как можно большего спектра решаемых задач.
Коллекции
Для использования коллекции в своем коде используйте следующую директиву:
#include ,
где T — название коллекции
Итак, наиболее часто используются:

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

Строки
Любая серьезная библиотека имеет свои классы для представления строк. В STL строки представляются как в формате ASCII, так и Unicode: 
string — коллекция однобайтных символов в формате ASCII; 
wstring — коллекция двухбайтных символов в формате Unicode; включается командой #include .
Строковые потоки
strstream — используются для организации STL-строкового сохранения простых типов данных.
Разбор примеров начнем именно с этого класса.
//stl.cpp: Defines the entry point for the console application #include "stdafx.h" #include #include #include using namespace std; int _tmain (int argc, _TCHAR* argv []) < strstream xstr; for (int i = 0; i < 10; i++) < xstr cout
Строковый поток — это буфер с нуль-терминатором в конце, поэтому при первой распечатке в конце строки оказывается мусор, т.е. получить реальный конец можно не посредством нуль-терминатора, а получив счетчик: pcount() . Затем “реальная часть” потока копируется в новую строку, и мы получаем распечатку уже без мусора.
Итераторы
Очень важное понятие в реализации динамических структур данных — итератор. Неформально итератор можно определить как абстракцию, которая ведет себя как указатель, возможно, с какими-то ограничениями. Строго говоря, итератор — более общее понятие, и является объектной оберткой для указателя, поэтому указатель является итератором. Примерно его устройство может выглядеть так:
class Iterator < T* pointer; public: T* GetPointer () < return this - >pointer; > void SetPointer (T* pointer) < this - >pointer = pointer; > >; 
Вот несколько формализованных определений итератора:

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

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

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

Вот пример использования итераторов для удаления половин элементов коллекции:
#include "stdafx.h" #include #include #include using namespace std; void printInt (int number); int _tmain (int argc, _TCHAR* argv []) < vectormyVec; vector::iterator first, last; for (long i=0; i first = myVec.begin (); last = myVec.begin () + 5; if (last >= myVec.end ()) < return - 1; >myVec.erase (first, last); for_each (myVec.begin (), myVec.end (), printInt); return 0; > void printInt (int number)
Важно понимать, что при получении итератора на какой-то элемент коллекции и последующем изменении коллекции итератор может стать непригоден для использования.
Итерация вперед и аналогично назад происходит так: 
for (iterator element = begin (); element
При использовании random access iterator, например, так: 
for (iterator element = begin (); element
Методы коллекций
Основными методами, присутствующими почти во всех коллекциях являются следующие:

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

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

Vector
Самая часто используемая коллекция — это вектор. Очень удобно, что у этой коллекции есть такой же оператор operator [] , что и у обычного массива. Такой же оператор есть и у коллекций map , deque , string и wstring .
Важно понимать, что вместимость vector'а изменяется динамически. Обычно для увеличения размера используется мультипликативный подход: выделенная под vector память увеличивается при необходимости в константное число раз, т.е. если добавление нового элемента приведет к тому, что размер массива превысит вместимость, то операционной системой для программы будет выделен новый участок памяти, например, в два раза больший, в который будут скопированы все значения из старого участка памяти и к которому будет дописано новое значение.
Алгоритмы
Разработчики библиотеки STL ставили перед собой гораздо более серьезную задачу, чем создание библиотеки с набором шаблонных структур данных. STL содержит огромный набор оптимальных реализаций популярных алгоритмов, позволяющих работать с STL-коллекциями. Все реализованные функции можно поделить на три группы:

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

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


Похожие публикации:

Как открыть проводник на компьютере
Как поменять язык в настройках
Как посмотреть версию сафари на айфоне
Как создать визитку на айфоне с qr кодом