библиотека stl c что это
Основные понятия стандартной библиотеки С++
Данная статья определяет основные понятия стандартной библиотеки С++. Она приводится для того чтобы на неё ссылаться в дальнейшем.
Наибольшей частью стандартной библиотеки С++ является библиотека 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, который на основе контейнеров реализует, соответственно, стэк. В качестве примера можно рассмотреть адаптер бинарной функции к унарной (на данный момент эта функция объявлена в стандарте С++ устаревшей):
Урок №196. Стандартная библиотека шаблонов (STL)
Обновл. 15 Сен 2021 |
Поздравляем! Вы прошли основную часть туториала по языку С++! На предыдущих уроках мы рассматривали много особенностей языка C++ (включая и некоторые фишки, которые были добавлены в версиях C++11/14/17).
Закрадывается очевидный вопрос: «Что дальше?». Вы, возможно, уже замечали, что большинство программ используют одни и те же концепции снова и снова: циклы, строки, массивы, способы сортировок и т.д. Вы, вероятно, еще заметили, что написание программ без использования контейнерных классов и общих алгоритмов — дело, которое подвержено многим ошибкам. Хорошей новостью является то, что язык C++ поставляется в комплекте с библиотекой классов (и не только), которую вы можете использовать при создании своих программ. Эта библиотека называется Стандартной библиотекой шаблонов.
Стандартная библиотека шаблонов
Стандартная библиотека шаблонов (сокр. «STL» от «Standard Template Library») — это часть Стандартной библиотеки С++, которая содержит набор шаблонов контейнерных классов (например, std::vector и std::array), алгоритмов и итераторов. Изначально она была сторонней разработкой, но позже была включена в Стандартную библиотеку С++. Если вам нужен какой-нибудь общий класс или алгоритм, то, скорее всего, в Стандартной библиотеке шаблонов он уже есть. Положительным моментом является то, что вы можете использовать эти классы без необходимости писать и отлаживать их самостоятельно (и разбираться в том, как они реализованы). Кроме того, вы получаете достаточно эффективные (и уже много раз протестированные) версии этих классов. Недостатком является то, что не всё так просто/очевидно с функционалом Стандартной библиотеки шаблонов и это может быть несколько непонятно новичку, так как большинство классов на самом деле являются шаблонами классов.
К счастью, вы можете отделить себе кусочек Стандартной библиотеки шаблонов, чтобы его «распробовать» и при этом игнорировать всё остальное до тех пор, пока вы в нем не разберетесь.
На следующих нескольких уроках мы рассмотрим типы контейнерных классов, алгоритмов и итераторов, которые предоставляет Стандартная библиотека шаблонов. Затем мы еще углубимся в изучение некоторых конкретных классов.
BestProg
Библиотека стандартных шаблонов STL (Standard Template Library). Общие понятия. Контейнеры. Алгоритмы. Итераторы. Функторы
Данная тема является началом изучения библиотеки STL языка C++.
Содержание
Поиск на других ресурсах:
1. Библиотека STL. Общие сведения
В языке C ++ был разработан мощный набор инструментов для создания разнообразных программ — библиотека стандартных шаблонов (Standard Template Library, STL). Эта библиотека, фактически, является неотъемлемой составляющей языка C++, что является большим достижением ее разработчиков. Библиотека STL включена в стандарт языка C++ и содержит универсальные шаблонные классы и функции, которые реализуют широкий спектр алгоритмов и структур данных. Эти средства программирования можно применять практически к любым типам данных.
Различают следующие основные составляющие (компоненты) библиотеки STL:
Использование и сочетание этих составляющих позволяет программировать решения очень широкого круга задач программирования.
2. Контейнеры. Общие сведения. Перечень
В программировании контейнер — это объект, который сохраняет другие объекты внутри себя. Объекты, хранящиеся в контейнерах, могут быть как базовых (примитивных) типов так и экземплярами классов с соответствующим необходимым функционалом.
В библиотеке STL реализованы следующие контейнеры:
3. Алгоритмы. Общие сведения
Содержимое контейнеров обрабатывается с помощью алгоритмов. Алгоритмы позволяют обрабатывать контейнеры на любой вкус: инициализировать, сортировать содержимое контейнеров, преобразовывать, реализовывать различные виды поиска и тому подобное.
Для доступа к алгоритмам, нужно подключить соответствующую библиотеку
Все алгоритмы являются шаблонными функциями. Они могут быть применены к любому типу контейнера. Ниже приведен перечень алгоритмов библиотеки STL:
4. Итераторы. Общие сведения
Итераторы — это объекты, которые позволяют перемещаться по содержимому контейнера. Итераторы подобны указателям. Итераторы являются абстракцией указателя. С помощью итераторов можно считывать и изменять значения элементов контейнера.
Чтобы использовать итераторы нужно подключить заголовок iterator
В C++ различают 5 видов итераторов:
В библиотеке определены следующие классы, реализующие итераторы:
5. Функторы. Общие сведения
Чтобы использовать функторы в программе, нужно подключить заголовок functional
В библиотеке STL функторы делятся на две категории:
Библиотека 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. Как это делать, было подробно описано в моей предыдущей статье.