Конспект лекций доцента и. А. Волковой по курсу «системы программирования»




НазваниеКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница20/20
Дата публикации24.05.2014
Размер0.69 Mb.
ТипКонспект
literature-edu.ru > Лекции > Конспект
1   ...   12   13   14   15   16   17   18   19   20

Лекция 14. 14/05/2004.

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


(Standard Template Library – STL)
Рассмотрим теоретические основы теории библиотеки и её построения.

Ядро библиотеки стандартных шаблонов образуют три компонента: контейнеры, алгоритмы и итераторы. Эти элементы функционируют в тесной взаимосвязи друг с другом.

Контейнеры.


Контейнер – шаблонный класс для хранения объектов какого-либо одного и того же типа. Контейнеры бывают различных типов. Например, в классе vector определяется динамический массив, queue – очередь, list – линейный список. Помимо таких базовых контейнеров, в библиотеке стандартных шаблонов определены и ассоциативные контейнеры, которые позволяют получать хранящиеся в них значения. Например, в классе map определён ассоциативный список, доступ к элементам которого осуществляется с помощью уникальных ключей. Т.е. в таком списке элемент – это пара «значение-ключ».
Контейнеры STL:

Vector – динамический массив.

List – линейный список.

Stack – стек.

Queue – очередь.

Deque – двусторонняя очередь.

Priority_queue – очередь с приоритетом.

Set – множество с уникальными элементами.

Bitset – множество битов.

Multiset – множество не обязательно с уникальными элементами.

Map – ассоциативный список, в котором хранятся пары ключ/значение, с каждым ключом связано одно значение.

Multimap – ассоциативный список, в котором хранятся пары ключ/значение, с каждым ключом связано не обязательно одно значение.
Если сразу создать класс, а в качестве указателя – указатель на базовый класс, тогда фактически эти указатели будут указателями на разные объекты.

Функции.

В каждом контейнере определён некоторый набор функций для работы с тем, что хранится в контейнере.

Схожие функции имеют во всех контейнерах одинаковые названия.

push_back ( ); - положить в конец контейнера

size ( ); - определяет текущую длину контейнера

Таких функций существует приблизительно 15-20.

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

Например, к функции “vector [ ]” можно обращаться по номеру, а к “list ” (списку) – нельзя.
Основные типы.

Следующие типы определены в public-части для каждого контейнера.

value_type

allocator_type - распределитель памяти

size_type

iterator, const_iterator

reverse_iterator, const_reverse_iterator

pointer, const_pointer - указатель на элементы

reference, const_reference - ссылка на элементы
Тела функций скрыты от пользователя, при программировании с помощью STL об их содержимом можно не заботиться.
Распределитель памяти.

У каждого контейнера есть свой распределитель памяти allocator, который управляет процессом выделения памяти для объектов контейнера. По умолчанию распределитель памяти – это объект класса allocator. Также можно написать свой распределитель памяти и использовать его в программах, если STL не используем.
Рассматриваем только интерфейс функций:

template class allocator {

………………………………………

public:

typedef T*pointer;

typedef T&reference;

………………………………………

allocator( ) throw( );

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

………………………………………

pointer allocate (size_type n);

}
По умолчанию берётся стандартный распределитель памяти, он берёт память из области динамической памяти.

Алгоритмы.


В STL имеется 60 алгоритмов.

Алгоритмы реализуют некоторые распространённые операции с контейнерами, которые не включены в контейнер.

Т.е алгоритм – шаблонная функция, поэтому их можно использовать с контейнерами любых типов..



Алгоритмы подразделяются на 3 группы:

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

find ( ); - поиск элемента, выдаёт место, на котором находится элемент.

count ( ); - подсчёт

for_each( );

  • модифицирующие

transform ( );

reverse ( );

copy ( ); - копируется содержимое одного контейнера в другой

  • сортировки

sort ( ); - простая сортировка

stable_sort( ); - сортировка, гарантирующая сохранение относительно порядка

элементов

merge( ); - слияние двух списков.

Итераторы.


Итераторы – это что-то вроде указателей на элементы контейнера.

Типы итераторов перечислены в контейнере. В public-части контейнера есть итераторные функции с одинаковыми именами.

Объекты класса итератора играют роль указателей для контейнера. Итераторы используются для доступа к содержимому контейнера примерно так же, как указатели для доступа к элементам массива.

Итераторный класс определяется внутри контейнера.

Следует обратить внимание, что при использовании нужно писать оператор расширения видимости, чтобы знать, к какому итератору относится написанное:

list :: iterator

Пример.

iterator begin ( ) [const];

iterator end ( ) [const];

или

const_iterator begin ( ) [const];

const_iterator end ( ) [const];

Т.е. возвращается значение либо типа iterator, либо типа const_iterator.

Для итераторов нет константы NULL, обозначающей пустой указатель.

end ( ) – возвращает следующий после этого элемент итератора (т.е. уже элемент следующего итератора).

reverse_iterator rbegin( ) [const];

reverse_iterator rend( ) [const];

или

const_reverse_iterator rbegin( ) [const];

const_reverse_iterator rend( ) [const];

- обратный итератор, выдаёт последовательность в обратном порядке.
Различие между этими итераторами:

begin A B C .




end
rbegin C B A .



rend
Типы итераторов:

Существуют следующие типы операторов, которые позволяют соответствующие функции:

  1. Итераторы вывода.

*p_ , p++

  1. Итераторы ввода.

*=p, ->, ++, ==, !=

  1. Однонаправленные.

*p=, =*p, ->, ++, ==, !=

- положить в контейнер

- взять из контейнера

  1. Двунаправленные.

*p=, =*p, -> , ++, ==, !=, --

  1. C произвольным доступом.

*p=, =*p, -> , ++, ==, !=, --, [ ], +, -, +=, -=, <, >, <=, >=

С 1 до 5 увеличивается мощность итераторов.
Пример. Шаблонная функция find.

Для работы нужны итераторы, которые указывают место начала поиска, место конца поиска, искомый элемент.

Нужно ввести итератор ввода.

template

input Iterator find (InputIterator first,

InputIterator last,

const T& value)

{

while (first!=last && *first != value)

first++;

return first;

}
Используются такие имена шаблонов, чтобы было понятно, к какому итератору он относится.
Пример. Контейнер vector. (схематично)

template > class vector {

- параметр распределения памяти, по умолчанию берётся

стандартный распределитель памяти

……………………………………………..

public:

//типы

//итераторные функции

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

/*const*/reference operator [ ] (size_type n); //доступ без контроля выхода за

диапазон вектора

/*const*/reference at (size_type n); //с контролем

/*const*/reference front ( ); //указатель на первый элемент контейнера

/*const*/reference back ( ); // указатель на последний элемент контейнера

explicit vector (const A& = A( ));

// - здесь опускается имя формального параметра, работает

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

// explicit vector - вектор нулевой длины (когда данные записываются в вектор,

// сначала создаётся такой вектор)

explicit vector (site_type n; const T& value = T( ); const A& = A( ));
………………………… // здесь определён конструктор копирования, оператор

// присваивания и др.

// функции – члены класса, частые в использовании
iterator erase (iterator i);

iterator insert (iterator i, const T& value = T( ));

// - вставка перед этим элементом, возвращает итератор вставленного

элемента

void push_back ( );

void pop_back ( ); // - удаляем последнюю запись вставленного элемента

sizetype size ( ) const;

bool empty ( ) const;

void clear ( ); // - очищаем вектор

………………………….

}

Пример. Контейнер – список.

template > class list {

public:

//типы

//итераторные функции

/*const*/reference front ( ); //указатель на первый элемент контейнера

/*const*/reference back ( ); // указатель на последний элемент контейнера

explicit list (const A& = A( ));

explicit list (site_type n; const T& value = T( ); const A& = A( ));

//explicit – для безопасности, не позволяет делать присваивание векторов.

…………………………
iterator erase (iterator i);

iterator insert (iterator i, const T& value = T( ));

// - вставка перед этим элементом, возвращает итератор вставленного

элемента

void push_back ( );

void pop_back ( ); // - удаляем последнюю запись вставленного элемента

sizetype size ( ) const;

bool empty ( ) const;

void clear ( ); // - очищаем вектор

………………………….

}
Пример. Написать функцию, формирующую вектор.

#include

#include

#include

using name_space std;

void g (vector &v, list lst) {

// - ставить здесь ссылку является хорошим стилем

int i;

for (i=0; i
// функция size для вектора v

if (!(v[i]%2)) lst.push_back (v[i]);

lst :: const_iterator p=lst.begin( );

// - показываем на первый элемент

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

cout << *p << endl;

p++;

}

}

Для этой функции напишем функцию main.

int main ( ) {

vector v (20);

list lst;

//- первый конструктор без параметров, создающий список 0 длины

int i;

for (i=0; i<20; i++) v[i]=i;

g (v,lst);

return 0;

}

1   ...   12   13   14   15   16   17   18   19   20

Похожие:

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconРеспублики Беларусь Учреждение образования «белорусский государственный...
Конспект лекций по курсу «Основы алгоритмизации и программирования» для студентов всех специальностей и всех форм обучения. Мн.:...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций «Логистика. Конспект лекций»
Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций по курсу "Информатика и использование компьютерных...
Конспект лекций предназначен для студентов филологического факультета и факультета гуманитарных и социальных наук рудн. Конспект...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconРабочая программа по курсу «основы Программирования на языке ассемблер»
Программа предназначена для обучения основам программирования на языке низкого уровня Ассемблере учащихся средних школ, учреждений...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconОсновы информатики и вычислительной техники системы программирования
Рассматриваются основные понятия языков программирования. Излагаются процедурный и объектный подходы в программировании. Более подробно...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов специальности 1-25 01 04 «Финансы и...
...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов специальности 1-54 01 01-04 «Метрология,...
Конспект лекций предназначен для студентов специальности 1-54 01 01-04 «Метрология, стандартизация и сертификация (лёгкая промышленность)»...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconАвтор: Медведева Г. В
Курс лекций содержит основные разделы языка программирования t-pascal, предусмотренные образовательным стандартом

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций для студентов пятого курса специальности 220400 Программное...
Данный конспект лекций составлен для студентов четвёртого курса специальности “Программное обеспечение вычислительной техники и автоматизированных...

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconУчебник Толубеевой Т. И., доцента кафедры пти «Основы проектирования крупноузорчатых тканей»
Особенность Декады – 25- летие выхода в свет стандартов исо серии 9000 на системы менеджмента качества

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции