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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



 

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

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

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

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

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

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

- Stack < T > - стек;

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

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

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

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

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

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

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

begin() указывает на первый элемент

end() указывает на элемент, следующий за последним

rbegin() указывает на первый элемент в обратной последователь-ности

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

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

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

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

const_iterator begin() const

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

const_iterator end () const

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

const_reverse_iterator rbegin() const.

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

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.

Пример1. Написать функцию g() с тремя параметрами:

 - непустой и неизменяемый контейнер-вектор типа vector<float>;

- непустой контейнер-список типа list<float>;

- целое число – шаг по первому контейнеру.

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

# include < iostream >

# include < Vector >

# include < List >

using namespace std; // средства стандартной библиотеки, и, в //частности, STL, определены в пространстве имен std.

typedef vector<float> V;

typedef list<float> L;

int g(const V& vect, L& lst, int step){

V:: const_iterator vp = vect.begin();

L:: reverse_iterator lp = lst.rbegin();

int t = 0;

do{ if (*lp * *vp < 0) *lp = -*lp;

if (vect.end() - vp <= step) break;

++ lp;

vp += step;

} while (lp!= lst.rend());

L::iterator rp = lst.begin();

while (rp!= lst.end()){

cout << *rp << ' ';

if (*rp >= 0) t++;

++rp;

};

cout << endl;

return t;

}

int main (){

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

V vect 1(15,0.0); // вектор чисел типа float

L list 1(15,0.0); //список чисел типа float

int i;

i = g(vect1,list1,1);

cout<< '\n' << "positive elements: " << i << '\n';

return 0;

}

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

#include<iostream.h>

#include<vector.h>

using namespace std;

int main(){

vector<int> v;

int i;

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

v.push_back(i);

cout<< " size= " <<v.size()<< ' \n ';

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

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

cout<<*p<< ' ';

p ++;

}

}

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

#include<iostream.h>

#include<vector.h>

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++;

}

}

Пример 4. Программа для сортировки с использованием алгоритма 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;

}

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

// search. cpp

//Ищем последовательность, заданную одним контейнером, в другом //контейнере

#include<iostream>

#include <algoritm>

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;

}

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

#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;

}

}

 

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

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

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

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

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

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

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

 



Поделиться:


Последнее изменение этой страницы: 2019-05-20; просмотров: 255; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 100.26.35.111 (0.066 с.)