89784

Стандартная библиотека шаблонов STL (Standard Template Library)

Лекция

Информатика, кибернетика и программирование

Стандартная библиотека шаблонов STL (Standard Template Library). Эта библиотека предоставляет возможность обобщенного программирования для многих стандартных структур и алгоритмов.

Русский

2015-05-13

243.01 KB

4 чел.

Стандартная библиотека шаблонов STL (Standard Template Library)

Содержание

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

  •  контейнеры и их адаптеры
  •  последовательные
  •  ассоциативные
  •  итераторы и их адаптеры
  •  алгоритмы
  •  алгоритмы сортировки и численные алгоритмы
  •  изменяющие и не изменяющие последовательность алгоритмы
  •  объекты-функции и их адаптеры

Стандартная библиотека шаблонов STL (Standard Template Library)

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

ЕЕ компонентами являются:

  •  контейнеры
  •  итераторы
  •  алгоритмы

Пример #15. Списочный контейнер на основе STL

#include <iostream.h>

#include <list.h>// контейнер список

#include <numeric.h>//алгоритм accumulate

using namespace std;//пространство имен

void print(const list<double> &lst)

{//используем итератор для прохода по lst

list<double>::const_iterator p;

for (p=lst.begin();p!=lst.end();++p)

cout<<*p<<‘\t’; cout<<endl;

}

int main()

{

double w[4]={0.9, 0.8, 88,-99.99};

list<double> z;

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;

return 0;

}

Контейнеры STL

Контейнеры подразделяются на два основных семейства:

последовательные контейнеры

векторы vector

списки list

двусторонние очереди deque

ассоциативные контейнеры

множества set

мультимножества multiset

отображения map и операция сравнения

мультиотображения multimap

ключи для поиска элементов

Интерфейсы контейнеров STL

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

доступ к элементу

вставка элемента

удаление элемента

деструктор

итераторы

Таблица 1. Интерфейсы контейнеров (СAN) STL

CAN::value_type

что содержит CAN

CAN::reference

тип-ссылка на значение

CAN::const_reference

константная ссылка

CAN::pointer

указатель на значение

CAN::iterator

тип-итератор

CAN::const_iterator

константный итератор

CAN::reverse_iterator

обратный итератор

CAN::const_revers_iterator

константный обратный итератор

CAN::difference_type

разница между двумя значениями CAN::iterator

CAN::size_type

размер CAN

Таблица 2. Члены контейнера STL

CAN::CAN()

конструктор по умолчанию

CAN::CAN(c)

копирующий конструктор

c::begin()

начальная позиция контейнера с

c::end()

конечная позиция контейнера с

c::rbegin()

начало для обратного итератора

c::rend()

коней для обратного итератора

c::size()

число элементов в CAN

c.max_size()

наибольший размер

c.empty()

истина, если CAN пуст

c.swap(d)

обмен элементами двух CAN

Таблица 3. Члены последовательных контейнеров (SEQ) STL

SEQ::SEQ(n,v)

n элементов со значением v

SEQ::SEQ(b_it,e_it)

от b_it до e_it-1

c::insert(w_it, v)

вставка 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

c::erase(w_it)

стирает элемент, прописанный в w_it

c::erase(b_it, e_it

стирает от b_it до e_it-1

Пример #16. Использование членов последовательных контейнеров VECTOR и DEQUE

#include <iostream.h>

#include <vector.h>// контейнер список

#include <numeric.h>//алгоритм accumulate

using namespace std;//пространство имен

int main()

{

double w[6]={1.1,1.2,2.2,2.3,3.3,4.4};

vector<double> 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]);

//вставляет w[3]

return 0;

}

Таблица 4. Определение ассоциативных контейнеров (ASSOC) STL и их конструкторов

ASSOC::key_type

тип ключа поиска

ASSOC::key_compare

тип сравнивающего объекта

ASSOC::value_compare

тип для сравнения ASSOC::value_type

ASSOC()

конструктор по умолчанию

ASSOC(cmp)

конструктор, использующий cmp как сравнивающий объект

ASSOC(b_it, e_it)

использует элементы от b_it до e_it для сравнения

ASSOC(b_it, e_it, cmp)

использует элементы от b_it до e_it и cmp как сравнивающий объект

Таблица 5. Функции-члены ассоциативных контейнеров STL

c::insert(t)

если ни один из элементов не равен t, то вставляет его 

c::insert(w_it, е)

вставляет t c w_it в качестве начальной позиции поиска

c::insert(b_it, e_it)

вставляет диапазон элементов

c::erase(k)

стирает элемент, ключевое значение которых равно k

c::erase(w_it)

стирает указываемый элемент

c::erase(b_it, e_it)

стирает диапазон элементов

Пример #17. Использование членов ассоциативного контейнера SET

#include <iostream.h>

#include <set.h>// контейнер список

#include <numeric.h>//алгоритм accumulate

using namespace std;//пространство имен

int main()

{

int m[4]={1,2,3,4};

set<int, less<int>> s;

//множество целых, упорядоченное

//c помощью less 

set<int, less<int>> t(m,m+4);

// вставит 1,2,3,4

s.insert(3);// вставит 3

t.insert(3);// не вставит 3

s.erase(2);// такого элемента нет в s

t.erase(4);

return 0;

}

Адаптеры контейнеров STL

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

  •  стек stack
  •  очередь queue
  •  приоритетная очередь priority_queue

Стек (последний вошел - первый вышел)

Стек может быть получен (адаптирован) из вектора, списка и двусторонней очереди. 

Он нуждается в реализации операций:

  •  push поместить в стек
  •  pop вытолкнуть из стека 
  •  top вернуть верхний элемент из стека
  •  empty вернуть истину, если стек пуст
  •  size вернуть число элементов в стеке

Очередь (первый вошел - последний вышел)

Очередь может быть получена из списка и двусторонней очереди. 

Она нуждается дополнительно в реализации операций:

  •  front возвращает первый элемент из очереди
  •  back возвращает последний элемент из очереди
  •  push_back помещает элемент в конец очереди
  •  pop_front выталкивает первый элемент из очереди 
  •  empty вернуть истину, если очередь пуста
  •  size вернуть число элементов в очереди

Пример #18.  Использование стека из вектора

#include <iostream.h>

#include <stack.h>

#include <vector.h>

#include <string.h>

using namespace std;

int main()

{ stack<string, vector<string> > str_stack;

string quote[3]={“Природа\n,Родина\n,Земля\n”};

for (int i=0; i<3;++i)

str_stack.push(quote[i]);

while (!str_stack.empty())

{ cout<<str_stack.top();

str_stack.pop();

}

return 0;

}

Итераторы STL

Перемещение по контейнеру производиться с помощью итераторов.

Итератор может рассматриваться как усовершенствованный тип указателей.

Итератор является шаблоном, который инстанцируется типом контейнерного класса, итерируемого им.

Типы итераторов STL

Итератор ввода, поддерживающий операции равенства, разыменования и автоинкримента. Например, istream_iterator.

Итератор вывода, поддерживающий операции разыменования, допустимое только с левой стороны присваивания, и автоинкримента. Например, ostream_iteartor.

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

Двусторонние итераторы, поддерживающий все операции итераторов прохода вперед, автоинкримента и автодекремента.

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

Комментарии:

С помощью двусторонних итераторов и итераторов произвольного типа можно организовать алгоритмы вычисления или сортировки.

Контейнерные классы и алгоритмы диктуют выбор категории доступного или необходимого итератора.

Например:

  •  Вектор допускает итератор произвольного доступа, а списокнет.
  •  Для сортировки нужен итератор произвольного доступа, а для поиска лишь итератор ввода.  

Пример #19.  Использование итератора ввода-вывода

#include <iterator.h>

#include <iostream.h>

using namespace std;

int main()

{

vector<int> d(5);

int I, sum;

istream_iterator<int, ptrdiff_t> in(cin);

ostream_iterator<int> out(cout,”\t”);

cout<<“введите 5 чисел”<<endl;

sum=d[0]=*in;//ввод первого значения

for (i=1; i<5; ++i)

{d[i]=*++in;//ввод остальных значений

sum+=d[i];

}

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

*out=d[i];//вывод значений

cout<<“ Сумма=”<<sum<<endl;

return 0;

}

Адаптеры итераторов

Итераторы могут быть адаптированы для обеспечения обратного просмотра и просмотра со вставкой. Обратные итераторы изменяют порядок итерации на противоположный. С помощью итераторов вставки вместо обычного режима перезаписи выполняется вставка.

Пример #20.  Адаптирование итераторов

#include <iostream.h>

#include <vector.h>

using namespace std;

template <class ForwIter>

void print (ForwIter first, ForwIter last, const char* title)

{

cout<<title<<endl;

while(first!=last) cout<<*first++<<‘\t’;

cout<<endl;

}

int main()

{ int data[3]={9, 10, 11}

vector<int> d(data, data+3);

vector<int>::reverse_iterator    p=d.rbegin();

print(d.begin(), d.end(),Исходный”);

print(p, d.rend(),Обращенный”);

return 0;

}

Алгоритмы STL

Библиотека алгоритмов STL содержит четыре категории алгоритмов:

  •  алгоритмы сортировки
  •  не изменяющие последовательность алгоритмы 
  •  изменяющие последовательность алгоритмы 
  •  численные алгоритмы

Алгоритмы сортировки

Используются следующие алгоритмы:

  •  общая сортировка
  •  слияние
  •  лексикографическое сравнение
  •  перестановка
  •  двоичный поиск

Они используют: 

  •  operator<(), 
  •  объект Compare, 
  •  итераторы произвольного доступа

Пример #21. Использование SORT() из STL

#include <iostream.h>

#include <algorithm.h>

using namespace std;

const int N=5;

int main()

{

int d[N], I,*e=d+N;

for (i=0; i<N; ++i) d[i]=rand();

sort(d, e);

for (i=0; i<N; ++i) cout<<d[i]<<‘\t’;

return 0;

}

Не изменяющие последовательности алгоритмы

Не изменяющие алгоритмы не модифицируют содержимое контейнеров, с которыми они работают. Например, поиск в контейнере конкретного элемента и возвращение его позиции.

Пример #22. Использование функции поиска FIND()

#include <iostream.h>

#include <algorithm.h>

using namespace std;

int main()

{ string word[5]={“мой,мир,май,твой,труд”};

string* where;

where=find(word, word+5,мир”);

cout<<*++where<<endl;// май

sort(word, word+5);

where=find(word, word+5,мир”);

cout<<*++where<<endl;// мой

return 0;

}

Изменяющие последовательности алгоритмы

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

Пример #23.  Использование изменяющих функций REVERSE и COPY

#include <iostream.h>

#include <algorithm.h>

#include <string.h>

#include <vector.h>

using namespace std;

int main()

{string first_name[5]={“айра,бьерн,галина,вадим,рим”};

string last_name[5]={“пол,страуструп,иванова,подбельский,пал”};

vector<string> names (first_name, first_name+5);

vector<string> names2 (10);

vector<string>::iterator p;

copy(last_name, last_name+5, names2.begin());

copy(names.begin(), names_end(), names.begin()+5);

reverse(names2.begin(), names.end());

for (p=names2.begin(); p!=names2.end();++p) cout<<*p<<‘\t’;

return 0;

}

Численные алгоритмы

Численные алгоритмы включают

  •  суммирование accumulate()
  •  скалярное произведение inner_product()
  •  смежная разность adjacent_difference()
  •  частичная сумма partial_sum()

Пример #24.  Суммирование и перемножение векторов

#include <iostream.h>

#include <numeric.h>

using namespace std;

int main()

{double v1[3]={1.0, 2.5, 4.6},

v2[3]={1.0, 2.0, -3.5};

double sum, inner_p;

sum=accumulate(v1,v1+3,0.0);

inner_p=inner_product(v1,v1+3, v2, 0.0);

cout<<“Сумма=”<<sum << “Скалярное произведение=” << inner_p <<endl;

return 0;

}

Функции STL

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

Виды объектов-функций:

Арифметические объекты

Сравнивающие объекты

Логические объекты

Пример #25. Использование объекта-функции MINUS

#include <iostream.h>

#include <numeric.h>

using namespace std;

int main()

{double v1[3]={1.0, 2.5, 4.6}, sum;

sum=accumulate(v1,v1+3, 0.0, minus<int>);

cout<<“Сумма=”<<sum <<endl; //-7

return 0;

}

Адаптеры-функций

Адаптеры функций делают возможным создание объектов-функций с помощью адаптирования. 

Адаптеры-функций:

  •  отрицающий адаптер для отрицания предикативных объектов
  •  связывающий адаптер для связывания аргументов функции
  •  адаптеры для указателя на функцию

Пример #26. Использование адаптера функции BIND2ND для удвоения значений последовательности

#include <iostream.h>

#include <algorithm.h>

#include <functional.h>

#include <string.h>

using namespace std;

template <class ForwIter>

void print (ForwIter first, ForwIter last, const char* title)

{  cout<<title<<endl;

while(first!=last) cout<<*first++<<‘\t’;

cout<<endl;

}

int main()

{ int data[3]={9, 10, 11}

print (data, data+3,Исходные значения”);

transform(data, data+3, data, bind2nd(times<int>(),2));

print(data, data+3,Новые значения”);

return 0;

}

Полезные ссылки:

  1.  http://it.kgsu.ru/C_STL/oglav.html 
  2.  http://www.rsdn.ru/article/cpp/stl.xml 


 

А также другие работы, которые могут Вас заинтересовать

78399. Защита системы от пробоя изоляции и короткого замыкания 2.33 MB
  Защита и сигнализацию при пробое на корпус в любой точке силовой цепи электропередачи обеспечивает специальная схема, в которую входят реле заземления РЖД с двумя согласно включенными обмотками (рабочей и содержащей)
78400. Защита системы от буксировки колесных пар тепловоза 2ТЭ116 4.02 MB
  Обусловлен их незначительной разницей ток проходящий от выхода блока по проводу 776 через запертую контакты контактора В7 резисторы СРБ1 и СРБ2 катушки реле буксования РБ1 РБ2 не может вызвать их срабатывания. При боксовании потенциал вывода тягового электродвигателя пробуксовки колесной пары уменьшается и разность потенциалов сравниваемых в блоке порождает ток который проходя через катушки реле приводит к их включения. Контакты реле боксования размыкают цепи питания катушек реле рис.51 Электрическая схема управления...
78402. Ремонт дизеля. Ремонт коленчатых валов 105.34 KB
  Исправная работа коленчатого вала с подшипниками зависит от правильности укладки коленчатого вала состояния поверхности его шеек и вкладышей подачи смазки в нужном количестве и необходимого качества и других условий. Основными неисправностями коленчатых валов являются: излом вала по шейкам или щекам рис. трещины в шейках вала чаще по галтели задир шеек вала повышенная овальность коренных или шатунных шеек повреждения элементов соединения вала с антивибратором приводом насосов и распределительных валов изгиб вала. Причинами излома...
78403. КОРЕННЫЕ И ШАТУННЫЕ ПОДШИПНИКИ 59.58 KB
  Контроль состояния подшипников коленчатого вала осуществляют двумя методами: осмотром их состояния при техническом обслуживании и текущих ремонтах ТР; с помощью спектрального анализа масла. Увеличение содержания в масле свинца обнаруженное при спектральном анализе проб масла отбираемых на каждом текущем обслуживании ТО3 укажет на повышенный износ или выкрашивание баббита вкладышей коленчатого вала. На текущих ремонтах ТР2 производят внешний осмотр подшипников нижнего коленчатого вала с измерением щупом зазоров на масло и провисания...
78404. ЦИЛИНДРОВЫЕ КРЫШКИ И КЛАПАНЫ 61.76 KB
  При текущих ремонтах ТР2 и ТР3 крышки цилиндров снимают разбирают очищают от нагара и накипи и ремонтируют. Перед снятием крышки измеряют линейные размеры камеры сжатия с помощью приспособления рис 33 н зазор между крышкой и блоком по щупу у дизеля Д50 снимают форсунку н вместо нее устанавливают приспособление при положении поршня в нижней мертвой точке. Камеру сжатия регулируют толщиной прокладки между втулкой и крышкой цилиндра дизель 11Д45 или подрезкой торца крышки цилиндра дизель Д50.
78405. Неисправности насосов. Ремонт масляного насоса дизеля и его привода 138.18 KB
  В топливоподкачивающих насосах нарушается плотность сальникового уплотнения снижается подача из-за износа втулки вала возникают трещины в корпусе крышке и др. Ремонт масляного насоса дизеля и его привода Для снятия насоса с дизеля отсоединяют всасывающий и нагнетательный трубопроводы выпрессовывают конические штифты отворачивают гайки шпилек и снимают насос. Чтобы судить о степени износа зубьев зубчатых колес корпуса и подшипниковых планок перед разборкой насоса измеряют радиальный зазор между зубьями колес и корпусом насоса и осевой...
78406. Ремонт холодильников и теплообменников 176.34 KB
  Неисправностями секций холодильника являются течь по трубкам при обрыве и нарушении пайки загрязнение наружной и внутренней поверхностей секций. Течь трубок по месту пайки в коробку возникает при неправильном креплении секций колебании давлений и температуры воды и масла и размораживании секций зимой при резком открывании жалюзи. Снаружи секции покрываются пылью и грязью внутри масляных секций отлагаются механические частицы нагар и продукты окисления масла на водяных секциях накипь. Загрязнение секций ухудшает теплопередачу от трубок...