Библиотека стандартных шаблонов SLT

 

Стандартная библиотека шаблонов(STL) обеспечивает общецелевые, стандартные классы и функции, которые реализуют наиболее популярные и широко используемые алгоритмы и структуры данных. STL строится на основе шаблонов классов, и поэтому входящие в неё алгоритмы и структуры применимы почти ко всем типам данных. STL была разработанаАлександромСтепановым иМенгЛивHewlett-PackardLab.Она был выпущена в1994 году и впоследствиипринятавС++98.

Ядро библиотеки образуют три элемента: контейнеры, алгоритмы и итераторы.

Контейнеры (containers) – это объекты, предназначенные для хранения других элементов. Например, вектор, линейный список, множество.

Стандартные контейнеры библиотеки STL:

- Vector < T > - динамическиймассив;

- List < T > - линейныйсписок;

- Stack < T > - стек;

- Queue < T > - очередь;

- Set< T > - множество(ассоциативный контейнер, содержащий упорядоченный набор уникальных объектов. При добавлении нового элемента в множество он сразу становится на свое место так, чтобы не нарушать порядка сортировки).

- Map < T > - отсортированный ассоциативный контейнер, который содержит пары ключ-значение с неповторяющимися ключами.

Алгоритмы (algorithms) – функции, которые выполняют операции над содержимым контейнера. Существуют алгоритмы для инициализации, сортировки, поиска, замены содержимого контейнеров. Многие алгоритмы предназначены для работы с последовательностью (sequence), которая представляет собой линейный список элементов внутри контейнера.

Для работы с контейнерами необходимо с помощью директивы include подключить соответствующий заголовочный файл (<vector>, <list>, <deque>, <queue>, <stack>, <map>, <set>, <bitset>, <forward_list>).

Итераторы (iterators) – указатели на элементы контейнера. Они позволяют получить доступ к содержимому контейнера подобно, как указатели используются для доступа к элементам массива. С итераторами можно работать также, как с указателями. К ним применимы операции *, ++,--. Итератор имеет тип iterator.

Классы итераторов и функции, предназначенные для работы с ними, находятся в библиотечном файле < iterator >. Примеры итераторов:

Каждый контейнер содержит ряд ключевых методов, позволяющих найти концы последовательности элементов в виде соответствующих значений итераторов:

- iterator begin() – возвращает итератор, который указывает на первыйэлемент последовательности.

const_iterator begin() const

- iterator end() – возвращает итератор, который указывает на элемент,следующий за последним элементом последовательности (используется при оформлении циклов).

const_iterator end () const

- reverse_iterator rbegin() – возвращает итератор, указывающий напервый элемент в обратной последовательности (используетсядля работы с элементами последовательности в обратном порядке).

const_reverse_iterator rbegin() const.

reverse_iterator rend() – указывает на элемент, следующий за последним в обратной последовательности.

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

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. Двунаправленные итераторы (biderectional_iterator) обладают всеми свойствами forward-итераторов, а также имеют дополнительную операцию декремента (--i, i--, *i--), что позволяет им проходить контейнер в обоих направлениях.

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

В каждом классе определяется набор функций для работы с этим контейнером.

Включение элементов

insert( p,x ) – добавлениехпередэлементом,накоторыйуказываетр

insert( p,n,x ) – добавление nкопийхпередр

insert( p,first,last ) – добавление элементов из [first:last]перед р

push_back( x ) – добавлениехвконец

push_front( x ) – добавлениеновогопервогоэлемента(толькодлясписковиочередейсдвумяконцами)

Удалениеэлементов

pop_back() – удалениепоследнегоэлемента

pop_front() – удаление – первогоэлемента(толькодлясписковиочередейсдвумяконцами)

erase( p ) – удалениеэлементавпозициир

erase( first,last ) удалениеэлементовиз [first:last]

clear() удалениевсехэлементов

Другие операции

size() – числоэлементов

empty() – контейнерпуст?

capacity() – память,выделеннаяподвектор(толькодлявекторов)

reserve( n ) выделяетпамятьдляконтейнерапод n элементов

resize( n ) изменяет размерконтейнера(толькодлявекторов, списковиочередейсдвумяконцами)

swap( x ) обменместамидвухконтейнеров

==, !=, < операциисравнения

Операции присваивания

operator=( x ) контейнеруприсваиваютсяэлементыконтейнерах

assign( n,x ) присваиваниеконтейнеруnкопийэлементовх(недляассоциативныхконтейнеров)

assign( first,last )    присваиваниеэлементовиздиапазона[first:last]

Ассоциативные операции

operator[]( k ) – доступкэлементусключомk

find ( k ) – находит элемент с ключом k

lower _ bound ( k ) – находит первый элемент с ключом k

upper_bound( k ) – находит первый элемент с ключом, большимk equal_range( k ) – находитlower_bound(нижнююграницу)иupper_bound (верхнююграницу) элементовсключом k

Пример 1.Доступ к вектору через итератор.

#include<iostream>

#include<vector>

using namespace std;

intmain (){

vector < int > v;//объявить вектор v для хранения и обработки целых чисел

inti;

//заполнить вектор элементами

for (i =0; i <10; i ++)

v.push_back(i);

cout<< " size= " <<v.size()<< ' \n ';// вывестиразмервектора

/*объявить итератор p для перемещения по элементам вектораиз целых чисел и установить его на начало вектора v */

vector<int>::iteratorp=v.begin();

//вывестиэлементы вектора v

while (p!= v. end ()){

cout <<* p <<'';//вывести элемент

p ++;//передвинуть указатель

}

}

Пример 2. Вставка и удаление элементов в вектор.

#include<iostream>

#include<vector>

using namespace std;

int main(){

vector<int> v(5,1);

int i;

//вывод

for(i=0;i<5;i++)cout<<v[i]<< '';

cout<<endl;

vector<int>::iterator p=v.begin();

p +=2;

//вставить 10 элементов со значением 9

v.insert(p,10,9);

//вывод

p=v.begin();

while(p!=v.end()){

cout<<*p<<'';

p ++;

}

//удалить вставленные элементы

p = v. begin ();

p+=2;

v.erase(p,p+10);

//вывод

p=v.begin();

while(p!=v.end()){

cout<<*p<<'';

p++;

}

}

Пример 3. Программа для сортировки с использованием алгоритма sort.

// сортирует массив целых чисел

# include < iostream >

#include <algoritm>

using namespace std;

int arr[] = {45, 2, 22, -17, 0, -30, 25, 55};

int main (){

sort (arr, arr+8); // сортировка

for (intj =0; j <8; j ++) // вывести отсортированный массив

cout<< arr[j]<<'';

cout << endl;

return 0;

}

Пример 4.Программа для поиска вхождения подпоследовательности в последовательность с использованием алгоритма

#include<iostream>

#include <algorithm>

using namespace std;

int source[] = {11, 44, 33, 11, 22, 33, 11, 22, 44};

int pattern[] = {11, 22, 33};

int main (){

int* ptr;

ptr=search(source,source+9,pattern, pattern+3);

if (ptr== source+9)

cout<<"Совпадения не найдено\n";

else

cout<<" Совпадаениевпозиции "<<(ptr-source)<<endl;

return 0;

}

Пример 5. Поиск первого четного элемента в списке.

#include <list>

#include <algorithm>

#include <iostream>

int main(){

using namespace std;

// создаеть список из целых чисел.

list<int> numbers;

numbers.push_back(13); numbers.push_back(17);

numbers.push_back(42); numbers.push_back(46);

numbers. push _ back (99);

// Используетсяфункция find _ if и лямбда-выражение.

const list<int>::const_iterator result =

   find_if(numbers.begin(), numbers.end(),[](int n) { return (n % 2) == 0; });

// Print the result.

if (result!= numbers.end()) {

   cout << "The first even number in the list is " << *result << "." << endl;

} else {

   cout << "The list contains no even numbers." << endl;

}

}

Пример 6. Сортировка и поиск элементов вектора, которые являются объектами типа fraction

#include <iostream>

using namespace std;

#include <vector>

#include <algorithm>

class fraction{

intm; // числитель

intn; // знаменатель

public:

fraction(){}

fraction(int m, int n){

     this->m=m;

     this->n=n;

}

int getN(){return n;}

bool operator<(fraction ob2); // переопределение оператора<

booloperator ==(fractionob 2); // переопределение оператора ==

// переопределение операторов ввода/вывода

friend istream &operator>>(istream&stream, fraction &ob);

friend ostream &operator<<(ostream&stream, fraction ob);

};

bool fraction::operator <(fraction ob2){

if(m*ob2.n<n*ob2.m) return true;

else return false;

}

bool fraction::operator ==(fraction ob2){

if(m==ob2.m&&n==ob2.n) return true;

else return false;

}

ostream&operator<<(ostream&stream, fraction ob){

stream<<ob.m<<"/"<<ob.n;

return stream; 

};

istream&operator>>(istream&stream, fraction &ob){

cout<< "Числитель";

cin>>ob.m;

cout << "Знаменатель";

cin >> ob. n;

return stream;

}

int main(){

vector<fraction> fractions;//вектор дробей

//заполнение вектора дробей

fractions.push_back({4,5}); fractions.push_back({3,5});

fractions.push_back({2,6}); fractions.push_back({2,5});

fractions. push _ back ({5,6});

//создать итератор и установить его на начало вектора

vector<fraction>::iterator p=fractions.begin();

sort(fractions.begin(),fractions.end());//отсортировать вектор

//вывести элементы вектора

p = fractions. begin ();

while(p!=fractions.end()){

cout<<*p<<' ';//вывести элемент

 p ++;//передвинуть указатель

}

//посчитать сколько раз встречается дробь А в векторе

fraction A(5,6);// дробьА

cout<<endl<<A<<" встречается "<<count(fractions.begin(), fractions.end(), A)<<" раз"<<endl;

//поиск дроби со знаменателем 5

p = fractions. begin ();

while(p!=fractions.end()){

p = find_if (p, fractions.end(), [](fraction obj) { return (obj.getN() == 5);});

/*критерий поиска задается через лямбда-выражение*/

if (p!= fractions.end()) {

cout << "Element found: " << *p << '\n';

p ++;

}

}

//конец поиска дроби со знаменателем 5

}

В данном примере используется лямбда-выражение [](fractionobj) { return (obj. getN () == 5);} для проверки условия поиска (возвращает true, если знаменатель равен 5). Данное выражением передается функции find _ if () в качестве критерия поиска.

Многие языки программирования поддерживают понятие анонимной функции, т.е. функции, у которой есть тело, но нет имени. Лямбда-выражение – метод программирования, связанный с анонимными функциями.Лямбда-выражение неявно определяет класс объекта функции и создает объект функции этого типа класса.Непосредственное объявление лямбда-функции [](){ cout << "Hello, lambda!" << endl; } состоит из трех частей. Первая часть (квадратные скобки []) позволяет привязывать переменные, доступные в текущей области видимости (т.е. переменные в программе). Вторая часть (круглые скобки ()) указывает список принимаемых параметров лямбда-функции. Третья часть (в фигурных скобках {}) содержит тело лямбда-функции.

Контрольные вопросы и задания

 

1. Для чего используется библиотека стандартных шаблонов (STL)?

2. Какие основные виды компонентов содержит библиотека стандартных шаблонов (STL)?

3. Для чего используется контейнер STL?

4. Что такое алгоритм STL?

5. Для чего используются итераторы STL?

6. С использованием контейнера Stack, разработать программу, которая будет зашифровывать поступивший ей на обработку текст, записывая каждое слово в обратном порядке.