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




НазваниеКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
страница20/20
Дата публикации28.06.2013
Размер0.69 Mb.
ТипКонспект
lit-yaz.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Конспект лекций по курсу «Объектно-ориентированное программирование»
Б. Страуструп. Язык программирования C++, 3-е изд./Пер с англ. – Спб.; М.: «Невский диалект» – «Издательство бином», 1999 г. – 991...

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

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconВ. Г. Баула Введение в архитектуру ЭВМ и системы программирования
Мгу им. М. В. Ломоносова. По данному курсу существует достаточно обширная литература, посвящённая программированию на Ассемблере,...

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

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

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

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

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

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций по дисциплине вгипу, 2009 Конспект лекций по дисциплине «Управление персоналом»
Крупица В. В., Яшкова Е. В., Егоров Е. Е. Управление персоналом: Конспект лекций по дисциплине – вгипу, 2009

Конспект лекций доцента и. А. Волковой по курсу «системы программирования» iconКонспект лекций. (Электронный учебник) Минск: бгэу, 2010. Тема 1...
Короленок Г. А. Менеджмент в торговле. Конспект лекций. (Электронный учебник) Минск: бгэу, 2010



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница