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 


 

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

55577. Буквы о и а в корне –кос- - -кас- 114 KB
  Оборудование: Доска презентация по теме словообразование презентация Сказка о двух братьях Кос и Кас раздаточный материал. Назовите основные способы образования слов в русском языке с примерами.
55578. Читання як спосіб іншомовної комунікації 38 KB
  Враховуючи ці особливості формування компетенції в читанні та той факт що читання поряд з усним мовленням є найбільш розповсюдженим способом іншомовної комунікації пропоную у якості домашнього читання для учнів...
55579. РІЗНОМАНІТНІСТЬ УРОКІВ ЧИТАННЯ ЯК ШЛЯХ ПІДВИЩЕННЯ ЯКОСТІ ЧИТАННЯ В ПОЧАТКОВИХ КЛАСАХ 105.5 KB
  Всім давно відомо що знання фантазія логіка думки і міркувань любов до рідної мови уміння зв’язно логічно і образно розповідати виховуються читанням. Від учителя початкових класів в значній мірі залежить чи полюблять діти читання...
55580. Шляхи формування самостійного читача в системі позакласного читання 135 KB
  З читання як самостійної діяльності дитини у світі книг починається її самоосвіта самовиховання формування високих художніх смаків розвиток духовних сил. Читання практична діяльність.
55581. READING 104.5 KB
  God blessed the monastery when Ukraine became independent. In 1993 it was opened by the efforts of many people. Mother Superior Vira and nuns of the abode accepted the responsibility to restore the old monastery.
55582. В.Сухомлинський «Усмішка» 139.5 KB
  Що було найгловнішим в житті Сухомлинського Без роздумів він відповідав: любов до дітей. Читаймо казки Василя Сухомлинського – ніжні і мудрі і вони будуть напувати нас чистою джерельною водою.
55583. Виразне читання в початкових класах 79 KB
  І цілком слушно, що одному з провідних предметів початкової ланки школи – читанню і розвитку мовлення приділяється велика увага. Бо що таке читання або уміння дитини читати? Це насамперед наявність інтересу до читання...
55584. ВИВЧЕННЯ СПАДЩИНИ В.О.СУХОМЛИНСЬКОГО В ПОЧАТКОВІЙ ШКОЛІ 128.5 KB
  Розширити знання учнів про слова ввічливості; розвивати навики читання; Вправи на розвиток кута зору: вправи в таблицях дя кую про шу ви бачте про бачте добрий день Діти...
55585. Читання вибудовує долі 43 KB
  В історії розвитку людства читання завжди відігравало важливу роль. Але на жаль нині в українському суспільстві цінність читання знижується. Тож читання сьогодні є основою освіти й самоосвіти неперервною навичкою освіти людини протягом усього життя.