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 


 

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

17422. Проектування бази даних в Access 281 KB
  Лабораторна робота №4 Тема: Проектування бази даних в Access Мета: Запроектувати в Microsoft Office Access базу даних і виконати зв’язки Потрібно створити БД призначену для працівників довідкової служби кінотеатрів міста. Така система повинна забезпечувати зберігання відом...
17423. Виконання запитів до побудованої бази даних в Access 110 KB
  Лабораторна робота № 5 Тема: Виконання запитів до побудованої бази даних в Access Мета: Виконати запити до побудованої бази даних кінотеатрів і отримати інформацію про репертуар кінотеатрів тобто про те які фільми коли і де демонструються про ціни на квитки і про кіль
17425. Проектирование системы прерываний микро-ЭВМ на БИС семейства КР580 87 KB
  Проектирование системы прерываний микроЭВМ на БИС семейства КР580 Настоящая работа содержит методические указания по проектированию системы прерываний микроЭВМ на БИС семейства КР580 и написана в помощь студентам специальности при выполнении курсовых и дипломн...
17426. Исследование канала связи методом шумовой загрузки 113.5 KB
  ЛАБОРАТОРНАЯ РАБОТА № 3 по дисциплине: Методы и средства измерений в телекоммуникационных системах на тему: Исследование канала связи методом шумовой загрузки Цель работы Ознакомление с приборами методами и схемами оценки качества каналов тональной частоты ...
17427. Моделирование замкнутой системы управления ДПТ с обратными связями по скорости и по току с отсечкой 357 KB
  ЛАБОРАТОРНАЯ РАБОТА № 3 1 Моделирование замкнутой системы управления ДПТ с обратными связями по скорости и по току с отсечкой 1.1 Цель работы: знакомство с двехконтурной системой подчиннного регулирования и её моделью; особенности моделирования регуляторов; модель уд
17428. ТЕОРИЯ ОПТИМИЗАЦИИ. Конспект лекций 1.22 MB
  ТЕОРИЯ ОПТИМИЗАЦИИ Конспект лекций Приведены программы методические указания по изучению курса контрольные вопросы характеристика лабораторных работ и задание на контрольную работу. Методические указания предназначены для студентов заочного отделения со с...
17429. Создание графического интерфейса программы 47.17 KB
  Цель работы: создание графического интерфейса программы. Программа работы 1. Составить программу рассчитывающую заданное выражение приложение 1. Ввод данных и вывод результатов реализовать с использованием графического пользовательского интерфейса. Прогр...
17430. Работа со строковыми величинами 34.5 KB
  Лабораторная работа №11Работа со строковыми величинами Цель работы: Сформировать понятие величин полусоставного типа. Научиться составлять алгоритмы обработки строковых переменных. Задание 12. Решите две из следющих задач с сайта informatics.mccme.ru дистанционная подготов...