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 


 

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

33018. Метафизический метод познания (мышления) 17.82 KB
  Признает законы логики единственными движущими силами всякого развития. Этому уровню развития науки соответствовал метафизический способ мышления Метафизика. в любой его форме становится препятствием на пути прогрессивного развития научных знаний. стал антропологической интерпретацией идей развития и прогресса сформировавшихся в конце 18 первой половине 19 вв.
33019. Диалектика как метод познания. Принципы и законы диалектики 14.21 KB
  Противоположность черты стороны признаки предмета которые коренным образом отличаются друг от друга и вместе с тем не могут сущ.Противоречие это импульс толчок к изменению и развитию предмета. Внутренние противоречия между противоположными сторонами предмета пр.Основные противоречия между ведущими главными сторонами предмета.
33020. Проблема бытия в истории философии 35.15 KB
  Проблема бытия в истории философии Можно вычленить несколько периодов в трактовке бытия. Первый период мифологическое истолкование бытия. Второй этап связан с рассмотрением бытия самого по себе натуралистическая онтология.
33021. Проблемы сознания в истории философии 25.32 KB
  Философское осмысление сознания начинается тогда когда в ходе развития и усложнения материальнопрактической деятельности расширения познания окружающего мира начинается угасание религиозномифологических представлений. Примерами материалистического подхода к объяснению сознания являются общефилософские концепции Фалеса Анаксимандра Анаксимена Демокрита. Идеалистическое объяснение сознания ярче всего отражено в учении Платона о мире идеальных сущностей этих действительных первоосновах материального бытия.
33022. Проблема познания в истории философии 26.33 KB
  Проблема познания в истории философии. Проблема познания в истории философии имеет большое значение. Проблемы познания в философии Стоит начать с того что под познанием понимается целенаправленное активное отображение окружающей действительности в сознании человека. Проблема познания в философии важна также и по той причине что человек может быть не только субъектом но и его объектом.
33023. Проблема истины в философии 25.44 KB
  Проблема истины в философии и науке является достаточно сложной. Признание истины относительной связано с бесконечностью процесса познания мира его неисчерпаемостью. Проблема истины в философии также заключается в том что знание каждой исторической эпохи содержит в себе элементы абсолютной истины поскольку оно имеет объективно истинное содержание является необходимым этапом познания включается в последующие этапы.
33024. Специфика философского познания социальной действительности 40.09 KB
  Социальному познанию можно дать следующее определение: Познание людьми законов функционирования общества и самих себя своих целей желаний потребностей называется социальным познанием Очерки социальной философии. Истина это адекватность представлений субъекта действительности о чем подробно говорилось в первой части курса философии. Предмет и функции социальной философии История философии насчитывает более двух с половиной тысячелетий. За это время накопилось множество определений философии но до сих пор не утихают споры о том что...
33025. Основные подходы к изучению общества 18.61 KB
  Основные подходы к изучению общества Основные подходы к изучению общества. В процессе развития научных знаний сложилось несколько основных подходов к исследованию и объяснению общества. Этот подход проявляется также в понимании общества как особого живого организма.Культурноисторический подход к изучению общества характерен для конца XIX начала XX в.
33026. Общество как система. Характеристики общества как системы 33.31 KB
  Пушкарева отмечает что общество представляет собой универсальный способ социальной организации социального взаимодействия и социальных связей обеспечивающий удовлетворение всех основных потребно^ стей людей самодостаточный саморегулирующийся и самовоспроизводящийся Во всех этих определениях есть рационально зерно так как общество действительно состоит из активно действующих субъектов связанных между собой достаточно устойчивыми отношениями. Причем эти части и элементы не изолированы друг от друга не обособлены а напротив тесно...