Stl c что это
Перейти к содержимому

Stl c что это

  • автор:

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

Обложка поста 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, например, для переноса вашего приложения на мобильную платформу.

Следите за новыми постами по любимым темам

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

Stl c что это

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

1. Итераторы ввода (input iterator) поддерживают операции равенства, разыменования и инкремента: ==, !=, *i, ++i, i++, *i++. Специальным случаем итератора ввода является istream_iterator.

2. Итераторы вывода (output iterator) поддерживают операции разыменования, допустимые только с левой стороны присваивания, и инкремента: ++i, i++, *i = t, *i++ = t. Специальным случаем итератора вывода является ostream_iterator.

3. Однонаправленные итераторы (forward iterator) поддерживают все операции итераторов ввода/вывода и, кроме того, позволяют без ограничения применять присваивание: ==, !=, =, *i, ++i, i++, *i.

4. Двунаправленные итераторы (bidirectional iterator) обладают всеми свойствами forward-итераторов, а также имеют дополнительную операцию декремента (--i, i--, *i--), что позволяет им проходить контейнер в обоих направлениях.

5. Итераторы произвольного доступа (random access iterator) обладают всеми свойствами bidirectional-итераторов, а также поддерживают операции сравнения и адресной арифметики, то есть непосредственный доступ к элементу по индексу: i += n, i + n, i -= n, i - n, i1 - i2, i[n], i1 < i2, i1 i2, i1 >= i2.

В STL также поддерживаются обратные итераторы (reverse iterators). Обратными итераторами могут быть либо двунаправленные итераторы, либо итераторы произвольного доступа, проходящие последовательность в обратном направлении.

Кроме контейнеров, алгоритмов и итераторов, в STL поддерживается еще несколько стандартных компонентов.

Главными среди них являются распределители памяти, предикаты и функции сравнения.

У каждого контейнера имеется определенный для него распределитель памяти (allocator), который управляет процессом выделения памяти для контейнера. По умолчанию распределителем памяти является объект класса allocator. Можно определить собственный распределитель.

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

Определен специальный тип бинарного предиката для сравнения двух элементов. Он называется функцией сравнения (comparison function). Функция возвращает истину, если первый элемент меньше второго. Типом функции является тип Comp:

bool myfunction (int i,int j)

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

Пример 1. Удаление строк из списка с помощью функтора.

#include #include #include #include #include using namespace std; class contains : public unary_function  < //наличие подстроки в строке private: string substr_; public: contains(const string & substr) : substr_(substr) < >//конструктор bool operator () (const string& s) const < //благодаря перегрузке этого оператора, //объект класса может "прикидываться" функцией return s.find(substr_) != string::npos; >>; int main() < typedef ostream_iterator string_ostream_iter_t; typedef list string_list_t; string_list_t lst; lst.push_back("one"); //заполняем список lst.push_back("two"); lst.push_back("three"); lst.push_back("four"); lst.push_back("five"); lst.remove_if(contains("o")); //удаляем строки содержащие букву "о" lst.remove_if(not1(contains("r"))); //а так можно удалить строки, не содержащие букву "r" // выводим оставшиеся элементы списка на экран copy (lst.begin(), lst.end(), string_ostream_iter_t(cout, "\n")); cin.get(); return 0; >

Здесь использованы имеющиеся в STL метод push_back и алгоритмы remove_if, copy, они описаны ниже по тексту.

В STL определены два основных типа контейнеров: последовательности и ассоциативные контейнеры. Разница между ними состоит в том, что для последовательностей имеет значение порядок следования элементов (вектор, стек, очередь), а для ассоциативных контейнеров – нет (ассоциативный массив, множество).

Ключевая идея для стандартных контейнеров заключается в том, что они должны быть взаимозаменяемыми, если это разумно для решения задачи. Пользователь может выбирать между контейнерами, основываясь на соображениях эффективности и потребности в специализированных операциях. Например, если часто требуется поиск по ключу, можно воспользоваться ассоциативным массивом map. С другой стороны, если преобладают операции, характерные для списков, можно воспользоваться списочным контейнером list. Если добавление и удаление элементов обычно производится в начало или конец контейнера, уместно применение очереди queue, двусторонней очереди deque или стека stack. По умолчанию пользователь обычно применяет контейнер vector, он реализован, чтобы хорошо работать для широкого диапазона задач.

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

Кратко опишем основные возможности STL, подробнее с ними можно познакомиться в стандартной справке или на сайте cplusplus.com.

Stl c что это

Библиотека stl в языке C++ как понятно из расшифровки названия - это стандартная библиотека шаблонов. То есть внутри нее находятся различные наборы базовых алгоритмов, функций и методов, позволяющих нам работать в C++. Так же именно там находятся различные виды контейнеров, то есть сущностей, позволяющих хранить много однотипных объектов. Примеры контейнеров - vector (массив), set (множество), map и т.д.

Сама библиотека была начата как сторонний проект, и, когда она влилась в основную структуру C++, было множество пересечений и повторений. Даже на данный момент можно найти множество примеров таких совпадений.

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

  1. алгоритмы - описания соответствующих процедур,
  2. контейнеры - описания различных типов контейнеров,
  3. итераторы - сущности, которые указывают на некоторый элемент контейнера и умеют переходить к следующему элементу, фактически это аналог счётчиков,
  4. функциональные объекты, которые нужны, в основном, чтобы изменять поведение алгоритмов, например, делать сортировку по возрастанию или убыванию.

Подобное разделение позволило существенно упростить структуру библиотеки, уменьшив и стандартизировав различные виды компонентов по функционалу. А это означает гибкость и эффективность stl.

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

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

Наибольшей частью стандартной библиотеки С++ является библиотека STL (Standard Template Library – Стандартная Библиотека Шаблонов). Библиотека STL содержит пять основных видов компонентов:

  • контейнер (container): управляет набором объектов в памяти.
  • итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.
  • алгоритм (algorithm): определяет вычислительную процедуру.
  • функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.
  • адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

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

Из определения контейнера следует, что любая пользовательская структура данных является контейнером. В нашем случае контейнеры есть стандартные структуры данных, такие как список (list), вектор (vector), словарь (map) и многие другие. Формальные требования к контейнерам довольно обширны, но основным является правило доступа к элементам. Доступ к элементам контейнера осуществляется через специальные объекты — итераторы (см. ниже). Вы можете не знать, как располагаются элементы контейнера в памяти, однако вы точно знаете, что итераторы можно перебрать последовательно, и каждый из них предоставит доступ к элементу. Итератор, указывающий на первый элемент, можно получить при помощи метода iterator begin(); контейнера. Итератор, указывающий за последний элемент, можно получить при помощи метода iterator end(); контейнера. Другими словами, итераторы располагаются в полуинтервале (или полуотрезке), что можно формально записать как [begin, end). Пример объявления контейнера:

struct a_container < struct an_iterator; an_iterator begin(); an_iterator end(); >;

В ожидаемом стандарте С++20 предложено использовать структуру, инкапсулирующую полуинтервалы — ranges

Итератор — объект, предоставляющий доступ к элементам контейнера и позволяющий их перебирать. Итератор является свойством контейнера. В первых реализациях стандартной библиотеки С++ итератор реализовывался как указатель на элемент контейнера. В современных реализациях это класс, инкапсулирующий указатель на объект контейнера.

Основные требования к итераторам — наличие операторов разыменования и инкремента. Ниже объявление контейнера с итератором.

template struct a_container < struct an_iterator < void operator++(); TYPE& operator*(); >; an_iterator begin(); an_iterator end(); >;

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

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

template RESULT an_algorithm(ITERATOR first, ITERATOR last, . );

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

Начиная со стандарта С++11 существует возможность краткой записи функторов — лямбда-функции.

Каких-либо специальных требований к функторам нет. Разве что иногда может требоваться наследование от функтора function (до стандарта С++11 — unary_function или binary_function). Небольшой пример реализации функтора:

template struct plus < TYPE operator ()(const TYPE& p1, const TYPE& p2) const< return p1 + p2; >>;

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

template class bind1st < BIDIRECTIONAL_FUNCTION _bf; TYPE _first; public: bind1st(BIDIRECTIONAL_FUNCTION bf, TYPE first): _bf(bf), _first(first) <>TYPE operator()(const TYPE& p) const < return _bf(_first, p); >>;
Для самостоятельного чтения
  1. Драфт стандарта С++20 на гитхабе
  2. C++ Reference
  3. Разработка приложений на С++
  4. Range-v3, предложение для стандарта

Добавить комментарий

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