Библиотека стандартных шаблонов stl реферат
Обновлено: 05.07.2024
Данная тема является началом изучения библиотеки STL языка C++.
Содержание
Поиск на других ресурсах:
1. Библиотека STL. Общие сведения
В языке C ++ был разработан мощный набор инструментов для создания разнообразных программ — библиотека стандартных шаблонов (Standard Template Library, STL). Эта библиотека, фактически, является неотъемлемой составляющей языка C++, что является большим достижением ее разработчиков. Библиотека STL включена в стандарт языка C++ и содержит универсальные шаблонные классы и функции, которые реализуют широкий спектр алгоритмов и структур данных. Эти средства программирования можно применять практически к любым типам данных.
Различают следующие основные составляющие (компоненты) библиотеки STL:
- контейнеры (container)
- алгоритмы (algorithm)
- итераторы (iterator)
- функциональные объекты или функторы (functor).
Использование и сочетание этих составляющих позволяет программировать решения очень широкого круга задач программирования.
2. Контейнеры. Общие сведения. Перечень
В программировании контейнер — это объект, который сохраняет другие объекты внутри себя. Объекты, хранящиеся в контейнерах, могут быть как базовых (примитивных) типов так и экземплярами классов с соответствующим необходимым функционалом.
В библиотеке STL реализованы следующие контейнеры:
- bitset — набор битов;
- deque — двухсторонняя очередь;
- list — линейный список;
- map — ассоциативный контейнер, построенный по принципу key : value , в котором каждому ключу key соответствует значение value ;
- multimap — ассоциативный контейнер, в котором одному значению ( key ) соответствует несколько значений ( value1 , value2 , …, valueN );
- multiset — множество, в котором один и тот же элемент может встречаться несколько раз;
- priority_queue — очередь с приоритетами;
- queue — очередь;
- set — множество, в котором каждый элемент встречается только один раз;
- stack — стек;
- vector — динамический массив.
3. Алгоритмы. Общие сведения
Содержимое контейнеров обрабатывается с помощью алгоритмов. Алгоритмы позволяют обрабатывать контейнеры на любой вкус: инициализировать, сортировать содержимое контейнеров, преобразовывать, реализовывать различные виды поиска и тому подобное.
Для доступа к алгоритмам, нужно подключить соответствующую библиотеку
Все алгоритмы являются шаблонными функциями. Они могут быть применены к любому типу контейнера. Ниже приведен перечень алгоритмов библиотеки STL:
4. Итераторы. Общие сведения
Итераторы — это объекты, которые позволяют перемещаться по содержимому контейнера. Итераторы подобны указателям. Итераторы являются абстракцией указателя. С помощью итераторов можно считывать и изменять значения элементов контейнера.
Чтобы использовать итераторы нужно подключить заголовок iterator
В C++ различают 5 видов итераторов:
- RandIter — итератор произвольного доступа — записывает и извлекает значение из контейнера. Обеспечивает произвольный доступ к элементам контейнера;
- BiIter — двунаправленный итератор — записывает и извлекает значения. Перемещается вперед и назад;
- ForIter — прямой итератор — перемещается только вперед. Записывает и извлекает значения;
- InIter — итератор ввода — только извлекает значения. Перемещается только вперед;
- OutIter — итератор вывода — только записывает значения. Перемещается только вперед.
В библиотеке определены следующие классы, реализующие итераторы:
- iterator — базовый класс для всех итераторов;
- iterator_traits — представляет различные типы, определенные итератором;
- insert_iterator — обеспечивает работу итераторов вывода, которые вставляют объекты в контейнеры;
- back_insert_iterator — обеспечивает работу итераторов вывода, которые вставляют объекты в конец контейнера;
- front_insert_iterator — обеспечивает работу итераторов вывода, которые вставляют объекты на начало контейнера;
- reverse_iterator — поддерживает работу обратных итераторов;
- istream_iterator — поддерживает работу потоковых итераторов ввода;
- istreambuf_iterator — поддерживает работу потоковых итераторов ввода символов;
- ostream_iterator — поддерживает работу потоковых итераторов вывода;
- ostreambuf_iterator — поддерживает работу потоковых итераторов вывода символов.
5. Функторы. Общие сведения
Для обеспечения гибкого взаимодействия между итераторами, контейнерами и алгоритмами, используются функторы. Функтор — это класс, в котором реализована операторная функция operator() . Благодаря функторам объект класса представляется как функция.
Чтобы использовать функторы в программе, нужно подключить заголовок functional
С помощью конечных автоматов (далее просто автомат) можно успешно решать обширный класс задач. Это обстоятельство подмечено давно, поэтому в литературе по проектированию программного обеспечения часто приводятся рассуждения на тему применения автоматов ([2], [5], [8]). Однако в процессе моделирования автомат рассматривается с более высокого уровня, нежели это делается в момент его реализации с использованием конкретного языка программирования.
Последний раз журнал C / C++ User’s Journal обращался к проблеме проектирования конечных автоматов (Finite State Machine) в майском выпуске 2000 года ([1]). В этом номере была напечатана статья Дэвида Лафренье (David Lafreniere), где автор описывал использованный им подход. С тех пор прошло много времени, и в данной статье будет сделана попытка применить другой подход к проектированию конечного автомата с учетом современных тенденций в проектировании программного обеспечения.
Для удобства рассмотрим простой пример, который будет использоваться далее. Допустим, что необходимо определить, является ли входная последовательность символов целым числом, допустимым идентификатором, или недопустимой строкой. Под допустимыми идентификаторами будем понимать такие идентификаторы, которые начинаются с буквы и далее содержат буквы и "/", или цифры. Автомат, который поможет решить задачу, показан на рисунке 1. На рисунке используется нотация UML (Unified Modeling Language).
Рисунок 1. Автомат, позволяющий выяснить, что представляет собой входная строка.
Следует отметить, что различные источники наделяют подобный автомат различными атрибутами. Чемпионом по их количеству, наверное, является UML ([2]). Здесь можно найти отложенные события (deferred events), внутренние переходы (internal transitions), параметризованные триггеры событий (event triggers with parameters), дополнительные условия переходов (guard conditions), входные функции (entry action), выходные функции (exit action), события, генерируемые по таймеру (time events) и т.д. Однако здесь мы для простоты изложения опустим дополнительные атрибуты (к некоторым из них мы вернемся позже) и сосредоточимся на простой модели, где есть состояния, события и переходы между состояниями.
На данный момент все, что мы имеем – это наглядная и удобная для внесения изменений модель. Как теперь перейти от нее к коду на языке С++? Самый простой из способов реализации – это набор операторов if в том или ином виде. Например:
case State1: if ( CurrentEvent == Event1 )
if ( CurrentEvent == Event2 )
Не слишком наглядно, не так ли? А теперь представим себе, что мы имеем десятки событий и десятки состояний. Такой код просматривать трудно. Особенно тяжкие проблемы возникают при сопровождении кода, когда к нему надо вернуться через несколько месяцев и внести исправления.
Другая возможная реализация состоит в наборе функций, каждая из которых представляет собой состояние. Такая функция сможет возвратить указатель на ту функцию, которая соответствует новому состоянию автомата. Такая реализация также не облегчает поддержку кода.
Подойдем к проблеме немного с другой стороны. Картинка – это хорошо, но в исходном виде она никаким образом не может быть перенесена в исходный текст. Значит, даже, если решение будет найдено, то это будет нечто промежуточное между картинкой и обычным текстом.
Подход к реализации автомата
Таким промежуточным вариантом представления автомата может быть таблица. Этот способ известен давно, например [5]. Составим таблицу переходов для нашего автомата (таблица 1).
| События / состояния | Пусто | число | идентификатор | недопустимая строка |
| буква | идентификатор | недопустимая строка | идентификатор | недопустимая строка |
| цифра | Число | число | идентификатор | недопустимая строка |
Здесь в первой строке перечислены возможные состояния, а в первом столбце – возможные события. На пересечениях указаны состояния, в которые должен осуществиться переход.
Представление автомата в виде таблицы гораздо нагляднее, чем “размазанное” представление того же автомата в виде условных операторов или функций переходов. Таблицу уже можно попытаться переложить на код.
Предположим, что удалось переложить таблицу на код. Каким бы хотелось видеть этот код? Сформулируем требования к нему ([7]):
Описание автомата (читай – таблица) должно быть сконцентрировано в одном месте. Это даст легкость чтения, понимания и модификации автомата.
Представление автомата должно быть типобезопасным.
Не должно быть ограничений на количество состояний и событий.
События и состояния хотелось бы представить в виде абстрактных типов, определяемых пользователем.
По возможности, автомат хотелось бы сделать гибким и легко расширяемым.
По возможности, хотелось бы проверять описание автомата.
По возможности, хотелось бы исключить неправильное использование автомата.
Требования 1 и 7 означают, что все описание автомата хорошо бы поместить в конструктор. В конструкторе же надо проверять правильность описания – требование 6.
Механизм шаблонов встроен в компилятор C++, чтобы дать возможность программистам делать свой код короче за счет обобщенного программирования. Естественно, существуют и стандартные библиотеки, реализующие этот механизм. STL является самой эффективной библиотекой C++ на сегодняшний день.
Сейчас существует немало ее реализаций, каждая из которых, хоть и создана в рамках стандарта, обладает собственными расширениями. У подобного подхода есть один недостаток: не всегда код будет работать одинаково с разными компиляторами. Поэтому настоятельно рекомендуем вам максимально придерживаться традиционных приемов, как бы хорошо вы не разбирались в конкретной реализации библиотеки.
Первое знакомство
Для начала рассмотрим самые популярные коллекции из библиотеки. Каждая из них имеет собственный набор шаблонных параметров, чтобы быть максимально удобной для как можно большего спектра решаемых задач.
Коллекции
Для использования коллекции в своем коде используйте следующую директиву:
Итак, наиболее часто используются:
Строки
Строковые потоки
strstream — используются для организации STL-строкового сохранения простых типов данных.
Разбор примеров начнем именно с этого класса.
Итераторы
Очень важное понятие в реализации динамических структур данных — итератор. Неформально итератор можно определить как абстракцию, которая ведет себя как указатель, возможно, с какими-то ограничениями. Строго говоря, итератор — более общее понятие, и является объектной оберткой для указателя, поэтому указатель является итератором. Примерно его устройство может выглядеть так:
Вот несколько формализованных определений итератора:
- Итераторы обеспечивают доступ к элементам коллекции
- Для каждого конкретного класса STL итераторы определяются отдельно внутри класса этой коллекции.
Существуют три типа итераторов:
- (forward) iterator — для обхода коллекции от меньшего индекса к большему;
- reverse iterator — для обхода коллекции от большего индекс к меньшему;
- random access iterator — для обхода коллекции в любом направлении.
Вот пример использования итераторов для удаления половин элементов коллекции:
Важно понимать, что при получении итератора на какой-то элемент коллекции и последующем изменении коллекции итератор может стать непригоден для использования.
Итерация вперед и аналогично назад происходит так:
for (iterator element = begin (); element
При использовании random access iterator, например, так:
for (iterator element = begin (); element
Методы коллекций
Основными методами, присутствующими почти во всех коллекциях являются следующие:
- empty — определяет, пуста ли коллекция;
- size — возвращает размер коллекции;
- begin — возвращает прямой итератор, указывающий на начало коллекции;
- end — возвращает прямой итератор, указывающий на конец коллекции, т.е. на несуществующий элемент, идущий после последнего;
- rbegin — возвращает обратный итератор на начало коллекции;
- rend — возвращает обратный итератор на конец коллекции;
- clear — очищает коллекцию, т.е. удаляет все ее элементы;
- erase — удаляет определенные элементы из коллекции;
- capacity — возвращает вместимость коллекции, т.е. количество элементов, которое может вместить эта коллекция (фактически, сколько памяти под коллекцию выделено);
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, например, для переноса вашего приложения на мобильную платформу.
Эта библиотека предоставляет возможность обобщенного программирования для многих стандартных структур и алгоритмов.
ЕЕ компонентами являются:
- контейнеры
- итераторы
- алгоритмы
using namespace std ; // пространство имен
void print(const list > & lst )
list > ::const_iterator p ;
for ( p=lst.begin (); p != lst.end (); ++p )
cout p t ; cout endl ;
for ( int i = 0 ; i 4 ; ++i ) z.push_front(w[i ]);
print(z ); z.sort (); print(z );
cout сумма равна ” accumulate(z.begin () , z.end () , 0.0 ) endl ;
Контейнеры подразделяются на два основных семейства:
двусторонние очереди deque
отображения map и операция сравнения
ключи для поиска элементов
конструкторы, включая конструкторы по умолчанию и копирующие конструкторы
доступ к элементу
Таблица 1 . Интерфейсы контейнеров ( С AN ) STL
что содержит CAN
тип-ссылка на значение
указатель на значение
константный обратный итератор
разница между двумя значениями CAN :: iterator
Таблица 2 . Члены контейнера STL
конструктор по умолчанию
начальная позиция контейнера с
конечная позиция контейнера с
начало для обратного итератора
коней для обратного итератора
число элементов в CAN
истина, если CAN пуст
обмен элементами двух CAN
Таблица 3 . Члены последовательных контейнеров ( SEQ ) STL
n элементов со значением v
от b_it до e_it-1
вставка v перед w _ it
c::insert(w_it, v, n )
вставка n копий v перед w _ it
c::insert(w_it, b_it, e_it )
вставка значений от b _ it до e _ it -1 перед w _ it
стирает элемент, прописанный в w _ it
стирает от b _ it до e _ it -1
using namespace std ; // пространство имен
vector > v ( 15, 1.5 );
//15 элементов со значением 1.5
deque double > d ( w +2, w +6 ); //использует от 2.2 до 4.4
d . erase ( d . begin () +2 ); //стирает 3-ий
v.insert(v.begin () +1,w [ 3 ]);
Таблица 4 . Определение ассоциативных контейнеров ( ASSOC ) STL и их конструкторов
тип ключа поиска
тип сравнивающего объекта
тип для сравнения ASSOC :: value _ type
конструктор по умолчанию
конструктор, использующий cmp как сравнивающий объект
использует элементы от b _ it до e _ it для сравнения
ASSOC(b_it, e_it, cmp )
использует элементы от b _ it до e _ it и cmp как сравнивающий объект
Таблица 5 . Функции-члены ассоциативных контейнеров STL
если ни один из элементов не равен t , то вставляет его
вставляет t c w _ it в качестве начальной позиции поиска
вставляет диапазон элементов
стирает элемент, ключевое значение которых равно k
стирает указываемый элемент
стирает диапазон элементов
using namespace std ; // пространство имен
//множество целых, упорядоченное
s . insert ( 3 ); // вставит 3
t . insert ( 3 ); // не вставит 3
s . erase ( 2 ); // такого элемента нет в s
Это контейнерные классы, которые изменяют имеющиеся контейнеры с тем, чтобы обеспечить иное открытое поведение на основе существующей реализации:
- стек stack
- очередь queue
- приоритетная очередь priority _ queue
Стек может быть получен ( адаптирован ) из вектора, списка и двусторонней очереди.
Он нуждается в реализации операций:
- push поместить в стек
- pop вытолкнуть из стека
- top вернуть верхний элемент из стека
- empty вернуть истину, если стек пуст
- size вернуть число элементов в стеке
Очередь может быть получена из списка и двусторонней очереди.
Она нуждается дополнительно в реализации операций:
- front возвращает первый элемент из очереди
- back возвращает последний элемент из очереди
- push _ back помещает элемент в конец очереди
- pop _ front выталкивает первый элемент из очереди
- empty вернуть истину, если очередь пуста
- size вернуть число элементов в очереди
using namespace std ;
for ( int i = 0 ; i 3 ; ++i )
Перемещение по контейнеру производиться с помощью итераторов.
Итератор может рассматриваться как усовершенствованный тип указателей.
Итератор является шаблоном, который инстанцируется типом контейнерного класса, итерируемого им.
Итератор ввода , поддерживающий операции равенства, разыменования и автоинкримента. Например, istream _ iterator .
Итератор вывода , поддерживающий операции разыменования, допустимое только с левой стороны присваивания, и автоинкримента. Например, ostream _ iteartor .
Итераторы прохода вперед , поддерживающий все операции итератора ввода-вывода и позволяет применять присваивание без ограничений.
Двусторонние итераторы , поддерживающий все операции итераторов прохода вперед, автоинкримента и автодекремента.
Итераторы произвольного доступа , поддерживающий все операции двусторонних итераторов, операции сравнения и арифметические адресные операции, такие как индексирование.
С помощью двусторонних итераторов и итераторов произвольного типа можно организовать алгоритмы вычисления или сортировки.
Контейнерные классы и алгоритмы диктуют выбор категории доступного или необходимого итератора.
- Вектор допускает итератор произвольного доступа, а список нет.
- Для сортировки нужен итератор произвольного доступа, а для поиска лишь итератор ввода.
using namespace std ;
istream_iterator ptrdiff_t > in(cin );
ostream_iterator > out(cout, ”\ t ”);
cout введите 5 чисел ” endl ;
sum = d [ 0 ]=* in ; // ввод первого значения
for ( i = 1 ; i 5 ; ++i )
for ( i = 0 ; i 5 ; ++i )
*out=d[i ]; // вывод значений
cout Сумма =” sum endl ;
Итераторы могут быть адаптированы для обеспечения обратного просмотра и просмотра со вставкой. Обратные итераторы изменяют порядок итерации на противоположный. С помощью итераторов вставки вместо обычного режима перезаписи выполняется вставка.
using namespace std ;
template class ForwIter >
void print ( ForwIter first, ForwIter last, const char * title )
cout title endl ;
while(first != last ) cout first++ t ;
vector > d(data, data+3 );
vector > ::reverse_iterator p=d.rbegin ();
print(d.begin () , d.end () , “ Исходный ”);
print ( p , d . rend () , “ Обращенный ”);
Библиотека алгоритмов STL содержит четыре категории алгоритмов:
- алгоритмы сортировки
- не изменяющие последовательность алгоритмы
- изменяющие последовательность алгоритмы
- численные алгоритмы
Используются следующие алгоритмы:
- общая сортировка
- слияние
- лексикографическое сравнение
- перестановка
- двоичный поиск
- operator ,
- объект Compare ,
- итераторы произвольного доступа
using namespace std ;
int d[N ] , I, * e=d+N ;
for ( i = 0 ; i ; ++i ) d[i ]= rand ();
for ( i = 0 ; i ; ++i ) cout d[i ] t ;
Не изменяющие алгоритмы не модифицируют содержимое контейнеров, с которыми они работают. Например, поиск в контейнере конкретного элемента и возвращение его позиции.
using namespace std ;
where=find(word, word+5, ” мир ”);
cout ++where endl ; // май
where=find(word, word+5, ” мир ”);
cout ++where endl ; // мой
Изменяющие алгоритмы могут модифицировать содержимое контейнеров, с которыми они работают. Например, обращение содержимого контейнера.
using namespace std ;
vector > names ( first_name, first_name+5 );
vector > names2 ( 10 );
vector > ::iterator p ;
copy(last_name, last_name+5, names2.begin ());
copy(names.begin () , names_end () , names.begin () +5 );
for ( p=names2.begin (); p != names2.end (); ++p ) cout p t ;
Численные алгоритмы включают
- суммирование accumulate ()
- скалярное произведение inner _ product ()
- смежная разность adjacent_difference ()
- частичная сумма partial_sum ()
using namespace std ;
double sum, inner_p ;
inner_p=inner_product(v1,v1+3, v2, 0.0 );
cout Сумма =” sum Скалярное произведение =” inner _ p endl ;
Объекты-функции это классы, в которых определен operator () . Они размещены в библиотеке function . Они являются встроенными и компилируются так, чтобы получить эффективный код.
using namespace std ;
sum=accumulate(v1,v1+3, 0.0, minus >);
cout Сумма =” sum endl ; //-7
Адаптеры функций делают возможным создание объектов-функций с помощью адаптирования.
- отрицающий адаптер для отрицания предикативных объектов
- связывающий адаптер для связывания аргументов функции
- адаптеры для указателя на функцию
using namespace std ;
template class ForwIter >
void print ( ForwIter first, ForwIter last, const char * title )
while(first != last ) cout first++ t ;
print ( data , data +3, “ Исходные значения ”);
transform(data, data+3, data, bind2nd(times >() ,2 ));
print(data, data+3, “ Новые значения ”);
А также другие работы, которые могут Вас заинтересовать
Читайте также: