понятие история и характеристика stl

Основные понятия стандартной библиотеки С++

Данная статья определяет основные понятия стандартной библиотеки С++. Она приводится для того чтобы на неё ссылаться в дальнейшем.

Наибольшей частью стандартной библиотеки С++ является библиотека 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: стандартная библиотека шаблонов С++

Авторизуйтесь

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

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

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

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

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

Коллекции

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

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

Строки

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

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

Итераторы

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

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

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

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

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

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

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

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

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

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

Vector

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

Алгоритмы

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

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

Предикаты

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

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

Заключение

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

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Источник

Снова про 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, allocator, его разделяемая память и её особенности

Так и автор однажды задался мыслью, а что если … если произойдёт вырождение адресов сегментов разделяемой памяти в разных процессах. Вообще-то именно это происходит, когда процесс с разделяемой памятью делает fork, а как насчет разных процессов? Кроме того, не во всех системах есть fork.

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

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

Введение

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

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

Рассмотрим несколько примеров использования.

Фиг.1 структура разделяемой памяти PostgreSQL (отсюда)

Из общих соображений, а какой бы мы хотели видеть идеальную разделяемую память? На это легко ответить — желаем, чтобы объекты в ней можно было использовать, как если бы это были объекты, разделяемые между потоками одного процесса. Да, нужна синхронизация (а она в любом случае нужна), но в остальном — просто берёшь и используешь! Пожалуй, … это можно устроить.

Для проверки концепции требуется минимально-осмысленная задача:

Аллокатор STL

Допустим, для работы с разделяемой памятью существуют функции xalloc/xfree как аналоги malloc/free. В этом случае аллокатор выглядит так:

Этого достаточно, чтобы подсадить на него std::map & std::string

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

Разделяемая память

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

Windows

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

Самое важно здесь — hint. Если он не задан (NULL), система подберет адрес на своё усмотрение. Но если значение ненулевое, будет сделана попытка создать сегмент нужного размера с нужным адресом. Именно определяя его значение одинаковым в разных процессах мы и добиваемся вырождения адресов разделяемой памяти. В 32-разрядном режиме найти большой незанятый непрерывный кусок адресного пространства непросто, в 64-разрядном же такой проблемы нет, всегда можно подобрать что-нибудь подходящее.

Linux

Здесь принципиально всё то же самое.

Здесь также важен hint.

Ограничения на подсказку

Что касается подсказки (hint), каковы ограничения на её значение? Вообще-то, есть разные виды ограничений.

Во-первых, архитектурные/аппаратные. Здесь следует сказать несколько слов о том, как виртуальный адрес превращается в физический. При промахе в кэше TLB, приходится обращаться в древовидную структуру под названием “таблица страниц” (page table). Например, в IA-32 это выглядит так:

Фиг.2 случай 4K страниц, взято здесь

Входом в дерево является содержимое регистра CR3, индексы в страницах разных уровней — фрагменты виртуального адреса. В данном случае 32 разряда превращаются в 32 разряда, всё честно.

В AMD64 картина выглядит немного по-другому.

Фиг.3 AMD64, 4K страницы, взято отсюда

В CR3 теперь 40 значимых разрядов вместо 20 ранее, в дереве 4 уровня страниц, физический адрес ограничен 52 разрядами при том, что виртуальный адрес ограничен 48 разрядами.

И лишь в(начиная с) микроархитектуре Ice Lake(Intel) дозволено использовать 57 разрядов виртуального адреса (и по-прежнему 52 физического) при работе с 5-уровневой таблицей страниц.

До сих пор мы говорили лишь об Intel/AMD. Просто для разнообразия, в архитектуре Aarch64 таблица страниц может быть 3 или 4 уровневой, разрешая использование 39 или 48 разрядов в виртуальном адресе соответственно (1).

Во вторых, программные ограничения. Microsoft, в частности, налагает (44 разряда до 8.1/Server12, 48 начиная с) таковые на разные варианты ОС исходя из, в том числе, маркетинговых соображений.

Между прочим, 48 разрядов, это 65 тысяч раз по 4Гб, пожалуй, на таких просторах всегда найдётся уголок, куда можно приткнуться со своим hint-ом.

Аллокатор разделяемой памяти

Во первых. Аллокатор должен жить на выделенной разделяемой памяти, размещая все свои внутренние данные там же.

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

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

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

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

Итого, учитывая всё вышесказанное а так же потому, что под рукой оказался живой аллокатор методом близнецов (любезно предоставленный Александром Артюшиным, слегка переработанный), выбор оказался несложным.

Описание деталей реализации оставим до лучших времён, сейчас интересен публичный интерфейс:

Деструктор тривиальный т.к. никаких посторонних ресурсов BuddyAllocator не захватывает.

Последние приготовления

Раз всё размещено в разделяемой памяти, у этой памяти должен быть заголовок. Для нашего теста этот заголовок выглядит так:

Похоже, можно начинать.

Эксперимент

Сам тест очень прост:

Curid — это номер процесса/потока, процесс, создавший разделяемую память имеет нулевой curid, но для теста это неважно.
Qmap, LOCK/UNLOCK для разных тестов разные.

Проведем несколько тестов

qmap — glob_header_t::pglob_->q_map_

Результаты (тип теста vs. число процессов\потоков):

Эксперимент проводился на двухпроцессорном (48 ядер) компьютере с Xeon® Gold 5118 2.3GHz, Windows Server 2016.

Итого

Вдогонку

Разделяемую память часто используют для передачи больших потоков данных в качестве своеобразной “трубы”, сделанной своими руками. Это отличная идея даже несмотря на необходимость устраивать дорогостоящую синхронизацию между процессами. То, что она не дешевая, мы видели на тесте PRC_MTX, когда работа даже без конкуренции, внутри одного процесса ухудшила производительность в разы.

Объяснение дороговизны простое, если std::(recursive_)mutex (критическая секция под windows) умеет работать как спинлок, то именованный мутекс — это системный вызов, вход в режим ядра с соответствующими издержками. Кроме того, потеря потоком/процессом контекста исполнения это всегда очень дорого.

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

Удобно смешивать две техники — данные в разделяемой памяти, а через межпроцессный канал данных (ex: петля через localhost) отправляют только относительные указатели (от начала разделяемой памяти). Т.к. указатель обычно меньше пакета данных, удаётся сэкономить на синхронизации.

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

Напоследок

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

UPD: исходники BuddyAllocator выложены здесь под BSD лицензией.

Источник