Библиотека stl c что это
STL: стандартная библиотека шаблонов С++
Авторизуйтесь
STL: стандартная библиотека шаблонов С++
Механизм шаблонов встроен в компилятор C++, чтобы дать возможность программистам делать свой код короче за счет обобщенного программирования. Естественно, существуют и стандартные библиотеки, реализующие этот механизм. STL является самой эффективной библиотекой C++ на сегодняшний день.
Сейчас существует немало ее реализаций, каждая из которых, хоть и создана в рамках стандарта, обладает собственными расширениями. У подобного подхода есть один недостаток: не всегда код будет работать одинаково с разными компиляторами. Поэтому настоятельно рекомендуем вам максимально придерживаться традиционных приемов, как бы хорошо вы не разбирались в конкретной реализации библиотеки.
Первое знакомство
Для начала рассмотрим самые популярные коллекции из библиотеки. Каждая из них имеет собственный набор шаблонных параметров, чтобы быть максимально удобной для как можно большего спектра решаемых задач.
Коллекции
Для использования коллекции в своем коде используйте следующую директиву:
Итак, наиболее часто используются:
Строки
Строковые потоки
strstream — используются для организации STL-строкового сохранения простых типов данных.
Разбор примеров начнем именно с этого класса.
Итераторы
Очень важное понятие в реализации динамических структур данных — итератор. Неформально итератор можно определить как абстракцию, которая ведет себя как указатель, возможно, с какими-то ограничениями. Строго говоря, итератор — более общее понятие, и является объектной оберткой для указателя, поэтому указатель является итератором. Примерно его устройство может выглядеть так:
Вот несколько формализованных определений итератора:
Существуют три типа итераторов:
Вот пример использования итераторов для удаления половин элементов коллекции:
Важно понимать, что при получении итератора на какой-то элемент коллекции и последующем изменении коллекции итератор может стать непригоден для использования.
8 декабря в 18:00, Онлайн, Беcплатно
Итерация вперед и аналогично назад происходит так:
for (iterator element = begin (); element
При использовании random access iterator, например, так:
for (iterator element = begin (); element
Методы коллекций
Основными методами, присутствующими почти во всех коллекциях являются следующие:
Вместимость коллекции, как было сказано в начале, меняется по мере надобности, т.е. если вся выделенная под коллекцию память уже заполнена, то при добавлении нового элемента вместимость коллекции будет увеличена, а все значения, бывшие в ней до увеличения, будут скопированы в новую область памяти — это довольно «дорогая» операция. Убедиться в том, что размер и вместимость — разные вещи, можно на следующем примере:
Vector
Важно понимать, что вместимость vector’а изменяется динамически. Обычно для увеличения размера используется мультипликативный подход: выделенная под vector память увеличивается при необходимости в константное число раз, т.е. если добавление нового элемента приведет к тому, что размер массива превысит вместимость, то операционной системой для программы будет выделен новый участок памяти, например, в два раза больший, в который будут скопированы все значения из старого участка памяти и к которому будет дописано новое значение.
Алгоритмы
Разработчики библиотеки STL ставили перед собой гораздо более серьезную задачу, чем создание библиотеки с набором шаблонных структур данных. STL содержит огромный набор оптимальных реализаций популярных алгоритмов, позволяющих работать с STL-коллекциями. Все реализованные функции можно поделить на три группы:
Задачей этой статьи является лишь познакомить читателя с богатым набором инструментов, предоставляемых библиотекой STL. Более подробную информацию можно узнать из соответствующей документации.
Предикаты
Для многих алгоритмов STL можно задать условие, посредством которого алгоритм определит, что ему делать с тем или иным членом коллекции. Предикат — это функция, которая принимает несколько параметров и возвращает логическое значение (истина/ложь). Существует и набор стандартных предикатов.
Потокобезопасность
Заключение
STL — кросс-платформенная библиотека. Конечно, не существует абсолютной гарантии, что эта библиотека есть в любой версии компилятора. Например, она редко реализуется на мобильных устройствах, потому что большая часть реализованных структур данных делает выбор в пользу быстродействия, совершенно не экономя память, а ведь именно память является самым ценным ресурсом на мобильных платформах, в то время как на PC ее сейчас в избытке. Поэтому, нередко вам придется создавать свои реализации STL, например, для переноса вашего приложения на мобильную платформу.
Снова про STL: контейнеры
В предыдущей заметке речь шла о массивах как прототипе и прародителе контейнеров. Теперь дошла очередь до собственно контейнерных классов и поддерживающих их библиотек.
Под термином библиотека стандартных шаблонов (STL, Standard Template Library) понимают набор интерфейсов и компонентов, первоначально разработанных Александром Степановым, Менг Ли и другими сотрудниками AT&T Bell Laboratories и Hewlett-Packard Research Laboratories в начале 90-х годов (хотя и позже ещё весьма многие приложили руку к тому, что стало на сегодня стандартным компонентом C++). Далее библиотека STL перешла в собственность компании SGI, а также была включена как компонент в набор библиотек Boost. И наконец библиотека STL вошла в стандарты C++ 1998 и 2003 годов (ISO/IEC 14882:1998 и ISO/IEC 14882:2003) и с тех пор считается одной из составных частей стандартной библиотек C++.
Стандарт не называет эту часть библиотеки STL, но эту хронологию хорошо бы учитывать, разбираясь с какой версией компилятора, языка и литературы вы имеете дело — в процессе сокращения HP STL до размеров, подходящих для стандартизации, часть алгоритмов и функторов выпали из состава библиотеки, а кое-что, со временем, и добавляется (например, расширение набора переопределенных прототипов некоторых методов контейнеров). По тексту будет использоваться традиционное название STL только чтобы было ясно какую часть стандартной библиотеки C++ мы имеем в виду.
Первоначальной целью STL (это хорошо видно из хронологии комментариев в заголовочных файлах) было создание боле гибкой модели регулярных контейнеров по сравнению с массивами и обобщение на них некоторых широко используемых алгоритмов (таких как поиск, сортировка и некоторых других). Но затея оказалась плодотворнее первоначальных намерений, и была существенно расширена. STL вводит ряд понятий и структур данных, которые почти во всех случаях позволяют сильно упростить программный код. Вводятся следующие категории понятий:
Центральным понятием STL, вокруг которого крутится всё остальное, это контейнер (ещё используют термин коллекция). Контейнер — это набор некоторого количества обязательно однотипных элементов, упакованных в контейнер определённым образом. Простейшим прототипом контейнера в классическом языке C++ является массив. Тот способ, которым элементы упаковываются в контейнер и определяет тип контейнера и особенности работы с элементами в таком контейнере. STL вводит целый ряд разнообразных типов контейнеров, основные из них:
элементов типа float. Далее мы видим такие методы класса vector как max_size() — максимально возможная длина векторов вообще (константа реализации), size() — текущий размер (число элементов) вектора, capacity() — текущая ёмкость вектора, максимальное число элементов, которое может быть помещено в вектор в текущем его размещении. Выполнение этого фрагмента даст что-то примерно следующее (детали могут различаться в зависимости от реализации):
Здесь видно достаточно интересное поведение вектора (в этом и его смысл): как только при добавлении очередного элемента вектора его ёмкости становится недостаточно для ещё одного элемента, делается новое размещение вектора, резервируя для него удвоенную ёмкость (с запасом, чтобы следующее же добавление нового элемента не потребовало тут же нового переразмещения).
Примечание: Показанное выше удвоение ёмкости вектора при переразмещении — это характерное поведение для реализации библиотек компилятора GCC. Но точный алгоритм резервирования ёмкости под будущие элементы стандарт оставляет на волю реализатора, поэтому на него нельзя рассчитывать, и описан он здесь только для качественного понимания картины (реализации Visual Studio ведут себя по-другому, резервируя только небольшой избыток… это вы изучите сами).
Отметим на дальнейшее, пока без комментариев, то важное обстоятельство, что операции помещения элементов в контейнер выполняет копирование элемента, что влечёт за собой а).требование наличия копирующего конструктора для типа элементов и б).для структурных элементов это может привести к заметным затратам производительности.
Таким образом мы получили эквивалент массива C++, размер которого (size()) динамически меняется в произвольных пределах от нескольких единиц до миллионов элементов. Обратим внимание (это очень важно), что увеличение размера вектора достигается ни в коем случае не индексацией за пределы его текущего размера, а «заталкиванием» (метод push_back()) нового элемента в конец вектора (симметрично, метод pop_back() выталкивает последний элемент из массива и уменьшает его size()). Другой способ изменить размер вектора — это сразу вызвать методы resize() под нужный размер. Именно потому, что размер вектора, в отличие от массива, может динамически меняться, для вектора предусмотрено 2 разных способа индексации: как операция [ i ] и как метод-функция at( i ). Они различаются: метод at() проверяет текущий размер вектора size(), и при индексации за его границу возбуждает исключение. Напротив, операция индексации не проверяет границу, что небезопасно, но зато это быстрее. Метод at() позволяет нам контролировать выход за границы вектора и либо квалифицировать это как логическую ошибку, либо корректировать текущий размер контейнера под потребность, как в вот таком фрагменте (здесь попыток доступа вдвое больше, чем реально выполненных операций):
Стандарт C++11 привносит дополнительные выразительные средства, такие, например, как списки инициализации и выводимость типов, которые намного упрощают работу с контейнерами (и даже делают ненужными старые привычные приёмы записи). Вот как может описываться матрица, когда одновременно описываются её а). конфигурация (квадратная, хотя может быть прямоугольная и даже треугольная), b). размерность (3х3) и c). инициализирующие значения:
А заодно, здесь же показана работа с векторами (транспонирование квадратной матрицы и вывод в выходной поток) как с псевдо-массивами (пользуясь только индексированием), чем вектора, по существу, и являются (в частности, показано как тип элемента вектор определяется на основании выводимого типа по стандарту C++11):
Примечание: В рамках того, что мы уже знаем о векторах, возникает иногда вопрос: а как строго должен определяться тип возвращаемого size() результата (чтобы избежать зависимости от платформы) и, соответственно, любых переменных циклов, оперирующих с размером вектора? Временами от блюстителей чистоты синтаксиса следует ответ, что это должен быть size_t, и этот ответ — неверный (тем более, что для многих платформ size_t и определяется как unsigned int). Если вы захотите записать абсолютно строгого определение типа size() вектора, то строку в примере выше следует записать вот так:
Или, полагаясь на выводимость типов C++11, вот так:
Отметив здесь этот тонкий нюанс (приняв к сведению), мы не станем его применять далее, во избежания лишней громоздкости примеров, а будем использовать для размерностей просто unsigned.
Использование STL в C++
Собственно сам механизм шаблонов был встроен в компилятор C++ с целью дать возможность программистам C++ создавать эффективные и компактные библиотеки. Естественно, через некоторое время была создана одна из библиотек, которая впоследствии и стала стандартной частью C++. STL это самая эффективная библиотека для C++, существующая на сегодняшний день.
Сегодня существует великое множество реализаций стандартной библиотеки шаблонов, которые следуют стандарту, но при этом предлагают свои расширения, что является с одной стороны плюсом, но, с другой, не очень хорошо, поскольку не всегда можно использовать код повторно с другим компилятором. Поэтому я рекомендую вам все же оставаться в рамках стандарта, даже если вы в дальнейшем очень хорошо разберетесь с реализацией вашей библиотеки.
Начнем рассмотрение с краткого обзора основных коллекций. Каждая STL коллекция имеет собственный набор шаблонных параметров, который необходим ей для того, чтобы на базе шаблона реализовать тот или иной класс, максимально приспособленный для решения конкретных задач. Какой тип коллекции вы будете использовать, зависит от ваших задач, поэтому необходимо знать их внутреннее устройство для наиболее эффективного использования. Рассмотрим наиболее часто используемые типы коллекций. Реально в STL существует несколько большее количество коллекций, но, как показывает практика, нельзя объять необъятное сразу. Поэтому, для начала, рассмотрим наиболее популярные из них, которые с большой вероятностью могут встретиться в чужом коде. Тем более, что этих коллекций более чем достаточно для того, чтобы решить 99% реально возникающих задач.
STL Строки
Строковые потоки
Используются для организации сохранения простых типов данных в STL строки в стиле C++. Практическое знакомство с STL мы начнем именно с этого класса. Ниже приведена простая программа, демонстрирующая возможности использования строковых потоков:
Далее мы производим копирование содержимого буфера в строку и печатаем строку второй раз. На этот раз она печатается без мусора.
Основные методы, которые присутствуют почти во всех STL коллекциях, приведены ниже.
При использовании микрософтовской реализации STL библиотеки (Visual C++ 7.0) у автора получилось 0 и 13 соответственно до и после заполнения вектора.
vector
Каждый клиент также подключается к серверу, но с гораздо большим интервалом, чем приход сообщений от администратора, чтобы просмотреть сообщения, адресованные ему. При этом нам также необходимо знать хронологию прихода сообщений, адресованных разным пользователям (какое сообщение пришло раньше, а какое позже в любой момент времени). Для того, чтобы получить сообщения, клиент должен подключиться к серверу, просмотреть массив common для того, чтобы выбрать сообщения, адресованные ему, и после отключиться.
Для того, чтобы избежать этой ситуации, мы заведем массив сообщений для каждого клиента и вместо того, чтобы просматривать общий массив сообщений три раза, мы будем просматривать его всего лишь один раз с интервалом времени, адекватным периоду подключения одного клиента. При этом скопируем все сообщения в соответствующие массивы. Клиенты же будут просто забирать данные из своих массивов при подключении.
Итераторы
Итераторы обеспечивают доступ к элементам в коллекции
Итераторы для конкретного класса коллекции определяются внутри класса этой коллекции. В STL существует три типа итераторов: iterator, reverse_iterator, и random access iterator. Для обхода коллекции от меньшего индекса к большему, используются обычные или forward итераторы. Для обхода коллекции в обратном направлении используются reverse итераторы. Random access iterator являются итераторами, которые могут обходить коллекцию как вперед, так и назад. Ниже приведен пример использования итераторов для удаления половины элементов вектора:
Важно помнить, что когда вы получаете итератор к коллекции, а после этого модифицируете коллекцию, то этот итератор становится уже непригодным к использованию. Естественно, не все изменения приводят к непригодности итератора для дальнейшего использования, а только изменения структуры коллекции. В случае же, если вы просто измените значения, сохраненные в коллекции, то ничего страшного не произойдет и итератор не испортится.
Итерация по коллекции вперед происходит так:
Итерация по коллекции назад происходит так:
Если вы работаете и с random access iterator итератором, то синтаксис конструкции может быть, например, таким:
Для более эффективного использования контейнеров используйте typedef или наследуйте свой класс от класса коллекции.
Сделать это можно так:
В случае с итератором применима предыдущая техника:
Алгоритмы
Функции для перебора всех членов коллекции и выполнения определенных действий над каждым из них:
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 не потокобезопасная библиотека, но исправить это очень просто. Предположим, вам необходимо сохранять данные в вашу коллекцию в одном потоке, когда другой поток также сохраняет их туда. Тогда просто используйте критическую секцию или Mutex.
Пример реализации потокобезопасной коллекции для WIN32 с использованием критической секции приведен ниже:
Для начала мы создаем объектную обертку для критической секции. Далее создаем класс, который будет потомком двух классов: вектора с целочисленным параметром и нашей обертки и добавляем в него нашу потокобезопасную функцию, внутри которой вызываем метод вектора для добавления нового элемента в коллекцию.
Заключение
Автор постарался выбрать все наиболее ценное для использования на практике. Все примеры были оттестированы в среде VC7++. При создании использовался тип консольного Win32 приложения без поддержки ATL и MFC. Автор надеется, что они также хорошо будут работать при компиляции на других платформах. Естественно, за исключением приложения, демонстрировавшего создание потокобезапасной коллекции, все их можно собрать, скажем на Linux с использованием GCC. Как это делать, было подробно описано в моей предыдущей статье.
Основные понятия стандартной библиотеки С++
Данная статья определяет основные понятия стандартной библиотеки С++. Она приводится для того чтобы на неё ссылаться в дальнейшем.
Наибольшей частью стандартной библиотеки С++ является библиотека STL (Standard Template Library – Стандартная Библиотека Шаблонов). Библиотека STL содержит пять основных видов компонентов:
Из определения контейнера следует, что любая пользовательская структура данных является контейнером. В нашем случае контейнеры есть стандартные структуры данных, такие как список (list), вектор (vector), словарь (map) и многие другие. Формальные требования к контейнерам довольно обширны, но основным является правило доступа к элементам. Доступ к элементам контейнера осуществляется через специальные объекты — итераторы (см. ниже). Вы можете не знать, как располагаются элементы контейнера в памяти, однако вы точно знаете, что итераторы можно перебрать последовательно, и каждый из них предоставит доступ к элементу. Итератор, указывающий на первый элемент, можно получить при помощи метода iterator begin(); контейнера. Итератор, указывающий за последний элемент, можно получить при помощи метода iterator end(); контейнера. Другими словами, итераторы располагаются в полуинтервале (или полуотрезке), что можно формально записать как [begin, end). Пример объявления контейнера:
В ожидаемом стандарте С++20 предложено использовать структуру, инкапсулирующую полуинтервалы — ranges
Итератор — объект, предоставляющий доступ к элементам контейнера и позволяющий их перебирать. Итератор является свойством контейнера. В первых реализациях стандартной библиотеки С++ итератор реализовывался как указатель на элемент контейнера. В современных реализациях это класс, инкапсулирующий указатель на объект контейнера.
Основные требования к итераторам — наличие операторов разыменования и инкремента. Ниже объявление контейнера с итератором.
Я не могу дать лучшего определения алгоритма чем стандартное: алгоритмом называется последовательность действий, приводящая за конечное число шагов к необходимому результату.
В случае STL, алгоритмы реализуются шаблонными функциями, которые в качестве входных параметров принимают полуинтервалы итераторов. Общая сигнатура данных алгоритмов описывается следующим образом:
В объявлении класса можно переопределить оператор (). Если этот оператор в классе переопределен, то объекты этого класса получают свойства функций (их можно использовать как функции). Такие объекты называются функциональными или функторами. Функторы удобно использовать, когда функция должна обладать «памятью», а также, как замена указателей на функции.
Начиная со стандарта С++11 существует возможность краткой записи функторов — лямбда-функции.
Каких-либо специальных требований к функторам нет. Разве что иногда может требоваться наследование от функтора function (до стандарта С++11 — unary_function или binary_function). Небольшой пример реализации функтора:
Также STL предлагает ряд классов и функций (фукнторов), которые преобразуют интерфейс к нужному. В частности, есть адаптер stack, который на основе контейнеров реализует, соответственно, стэк. В качестве примера можно рассмотреть адаптер бинарной функции к унарной (на данный момент эта функция объявлена в стандарте С++ устаревшей):
Введение в библиотеку STL
Практически все современные компиляторы Cи++ содержат библиотеку STL. Изначально она настроена на работу практически с любыми данными, что обеспечивается набором шаблонов функций и классов.
Четыре основных компонента составляют структуру STL:
Итераторы
Итераторы бывают пяти видов:
входные (input); выходные (output); однонаправленные (forward); двунаправленные (bidirectional); произвольного доступа (random access).
Входные итераторы служат для чтения адресуемых данных. Выходные, напротив, адресуют объекты, в которые данные должны быть записаны. Однонаправленные итераторы обладают всеми свойствами входных и выходных, а также могут перемещаться от начала последовательности адресуемых данных в конец. Что касается двунаправленных итераторов, то они не только обладают свойствами однонаправленных, но и способны перемещаться в любом направлении по цепочке данных: как вперед, так и назад. Итераторы произвольного доступа самые универсальные. Они обладают функциональностью всех четырех других итераторов. Кстати говоря, указатели языка Си++ также являются итераторами произвольного доступа.
Библиотека STL построена так, что итератор более старшего типа может быть подставлен вместо младшего. Так, итератор произвольного доступа может заменить двунаправленный, двунаправленный может быть подставлен вместо однонаправленного и т. д.
Применяя итераторы, важно учитывать такой элемент, как индикатор конца диапазона (end-of-range), т. е. элемент, идущий непосредственно за концом цепочки адресуемых итератором данных. Весьма похоже на схему адресации строк в языке Си++, когда признаком конца строки является символ ‘\0’. Но при работе с итераторами индикатором конца диапазона может быть любое число.
Алгоритмы
В библиотеке STL существует группа функций, выполняющих некоторые стандартные действия, например поиск, преобразование, сортировку, копирование и т. д. Они называются алгоритмами. Параметрами для алгоритмов, как правило, служат итераторы. Алгоритму нет никакого дела до типа переданного ему итератора. Главное, чтобы последний подпадал под определенную категорию. К примеру, если параметром алгоритма должен быть однонаправленный итератор, то подставляемый итератор должен быть либо однонаправленным, либо двунаправленным, или же итератором произвольного доступа.
Примером алгоритма может служить equal. Он сравнивает две цепочки данных, адресуемых входными итераторами, и описан следующим образом:
Здесь использованы стандартные методы векторов: begin() возвращает итератор, настроенный на начало цепочки данных, а end() возвращает индикатор выхода за диапазон. Если все элементы векторов попарно равны друг другу, то equal вернет значение «истина» (true).
Отметим, что все алгоритмы можно разделить на две основных категории: те, которые изменяют данные, и те, которые их не изменяют.
Контейнеры
Надо отметить, что все алгоритмы работают с методами контейнеров, не вдаваясь в детали их реализации. Так, если алгоритму нужно определить, равен ли один элемент из контейнера другому, он просто вызывает перегруженный оператор сравнения «operator = = ()», реализованный в контейнере.
Функциональные объекты
Функциональными объектами являются все арифметические операторы: сложения (plus), вычитания (addition), умножения (times), деления (divides), взятия остатка (modulus) и обращения знака (negate). Имеются функциональные объекты для вычисления равенства (equal_to), неравенства (not_equal_to), операции «больше» (greater), операции «меньше» (less), операции «больше или равно» (greater_equal), операции «меньше или равно» (less_equal). Для логических операторов имеются свои функциональные объекты: логическое «и» (logical_and), логическое «или» (logical_or) и логическое «не» (logical_not).
В качестве примера приведена программа (см. листинг) с применением библиотеки STL, входящей в состав пакета Borland C++ Builder. Это маленький телефонный справочник.