Всё для Учёбы — студенческий файлообменник
1 монета
pdf

Студенческий документ № 043124 из НИТУ МИСиС

Объектно-ориентированное программирование

с использованием C++

Полевой Дмитрий Валерьевич

к.т.н., доцент КиК e-mail: oop.misis@gmail.com

Псевдоним типа (typedef)

•typedef OldType NewType;

•определяет псевдоним типа, но не вводит новый тип

• часто используется

- для сокращения кода, в т.ч. за счет подстановки параметров шаблонов

- для сокрытия деталей реализации

Псевдоним типа (примеры)

typedef unsigend int size_t;

typedef basic_string string;

Вложенные типы

• определяются внутри определения типа (класс, структура)

• подчиняются спецификаторам доступа

• доступ с помощью оператора разрешения области видимости

• в т.ч. для typedef

Вложенные типы (пример)

class Container { public: typedef long SizeType; ...

private: class Node {

... Обобщенное программирование

• Остерн М.Г.

Обобщенное программирование и STL. Использование и наращивание стандартной библиотеки шаблонов C++

• Александреску А.

Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования

STL Типы указателей

• обычный

• сингулярный (нулевой)

- нельзя разыменовывать

- можно проверять на равенство

• следующий за последним в массиве

- нельзя разыменовывать

- можно использовать в арифметике указателей и сравнениях

Диапазон (указателей)

• [first, last) состоит из всех указателей (элементов) от first до last, не включая last

• является допустимым

- last достижим из first

- можно разыменовывать все указатели

- пустой диапазон [p, p) является допустимым

Диапазон (объектов)

• [first, last) состоит из всех объектов

(элементов) от *first до *(last-1) включительно

• является допустимым

- last достижим из first

- можно получить адрес каждого объекта

- пустой диапазон [p, p) является допустимым

Свойства диапазонов

• если непустой диапазон [first, last) является допустимым, то [first+1, last) является допустимым

• если [first, last) допустимый и указатель mid достижим из first, last достижим из mid, то

[first, mid) и [mid, last) допустимые

• если [first, mid) и [mid, last) допустимые, то [first, last) допустимые

Массив, как диапазон

• [beg, beg + SIZE)

• число элементов SIZE = last - first • last, как признак конца обработки

пример: for (p = first; p != last; ++p)

{ if (value != *p) ...

} Контейнер

• является регулярным типом

• содержит свои элементы

• предоставляет доступ к элементам

Свойства элемента контейнера

• элемент может принадлежать не более, чем одному контейнеру (семантика значений)

- контейнеры не пересекаются

- ограничение на объекты, а не на значения

• время жизни элемента не превышает время жизни контейнера

- создается не раньше

- уничтожается не позже

Иерархия концепций контейнеров

• Контейнер Произвольного Доступа

• Реверсивный Контейнер

• Однонаправленный Контейнер

• Контейнер

- итератор ввода

Итератор

• интерфейс между алгоритмами и структурами данных

- требования со стороны алгоритмов

• регулярный тип

operator=(), operator==()

• доступ к элементу контейнера

operator*(), operator->()

• навигация по контейнеру

Итератор (пример алгоритма)

template I find(I fst, I lst, const T& val)

{ while (fst != lst && *fst != val)

++first; return first;

} iV = find(b, e, v); if (iV != e)

... Принцип идентичности

• соотношения равенства итераторов и равенства объектов

i1 == i2 - &*i1 == &*i2 i1 == i2 > *i1 == *i2

Константные и изменяемые итераторы

• константный итератор

- доступ к константному объекту

- константный объект (значительно реже)

пример: const int* pData(0);

// !не константный итератор int* const pVariant(&pA);

Итератор Произвольного Доступа

• допускает написание алгоритма с произвольным доступом к контейнеру

• все манипуляции за амортизированное константное время operator++(), operator--() operator+=(int) operator-() operator

OI copy(InpI first, InpI last, OutI res)

{ for (; first != last; ++res, ++first) {

*res = *first; } return res;

} Классы итераторов в STL

•iterator и const_iterator

• являются вложенными классами для классов контейнеров

пример: list::iterator list::const_iterator

Интервал элементов контейнера

• begin()

- первый элемент (начало)

• end() - элемент, следующий за последним (конец) пример:

vector ms; vector::iterator i(ms.begin());

Пример поиска

// C data; C::iterator it(dt.end()); it = find(dt.begin(), dt.end(), k); if (dt.end() != it)

// найден элемент со значением k

{ ... } Контейнеры переменного размера

• Последовательность (Sequence)

• Ассоциативный Контейнер (Associative Container)

Вставка элемента

• в конец -push_back

• в начало

-push_front • в произвольной позиции

-insert Удаление элемента

• из конца pop_back()

• из начала pop_front()

• из произвольной позиции remove()

Вставка и удаление интервала

• из конца pop_back()

• из начала pop_front()

• из произвольной позиции remove()

Последовательности в STL

•vector // массив

- произвольный

•list // список

- последовательный двунаправленный

•deque // дэк

- произвольный

Ассоциативные контейнеры в STL

•set // множество

•multiset // мультимножество

•map // ассоциативный контейнер

•multimap // множетсвенный ассоциативный контейнер

typename (ключевое слово)

• явное указание, что идентификатор является именем типа (в шаблонном коде)

• может использоваться вместо class в описании параметров шаблона

Свойства (traits)

• свойства (ассоциированные типы) - часть концепции

пример: template T

min(const T& lhs, const T& rhs)

{ return (lhs struct iterator_traits

{ typedef typename I::value_type value_type;

}; iterator_traits (для указателей)

template struct iterator_traits

{ typedef I value_type;

}; template struct iterator_traits

{ typedef I value_type;

}; Пример использования свойств

// сумма в непустом диапазоне template

typename iterator_traits::value_type sum(I first, I last)

{ typename iterator_traits::value_type

res(*first++); for (; first != last; ++first)

res += *first;

return res; } Операции над контейнерами и валидность итераторов

• операции над контейнерами могут делать итераторы невалидными

(в зависимости от реализации итераторов и контейнеров)

• всегда следите за валидностью итераторов

• избегайте хранения итераторов

Реверсивные итераторы для контейнеров

•значения интервала в обратном порядке

• специальные свойства и методы reverse_iterator rbegin() rend()

• отличаются от обычных итераторов

reverse_iterator

• класс-адаптер для iterator

•для [f, l) интервал [reverse_iterator(l), reverse_iterator(f)) содержит значения в обратном порядке

• основное тождество

&*(reverse_iterator(i)) == &*(i - 1)

&*r == &*(r.base() - 1)

Заголовочные файлы

• совпадают с именем контейнера

- в т.ч. multiset

- в т.ч. multimap

• вспомогательные

vector<>

• динамический массив

• произвольный доступ

• быстрая вставка/удаление в конец

• медленная вставка/удаление в начало

• изменение числа элементов делает итераторы невалидными

Объявление vector

template > class vector

vector - специализация

Доступ к элементам vector

• через итератор

- обобщенный вариант

• по индексу

- замена встроенным массивам

• с концов

• последовательное расположение в памяти

Доступ к элементам vector через итератор

•iterator begin()

- начало интервала

•iterator end()

- конец интервала

•reverse_iterator rbegin()

•reverse_iterator rend()

Доступ к элементам vector (если контейнер const)

const_iterator begin () const const_iterator end () const

Заполнение массива

•template void

assign(InpI fst, InpI lst)

- скопировать диапазон

•void assign(size_type n, const T& u)

- заполнить значениями u

Очистка массива

•iterator erase(iterator pos)

- удалить элемент

•iterator erase(iterator fst, iterator lst)

- удалить элемент или интервал

list<>

• двусвязный список

• линейный доступ

• быстрая вставка и удаление в любой позиции

• итераторы валидны при вставке и удалении

- кроме удаления текущего элемента

Объявление list<>

template > class list

Доступ к элементам list

• через итератор

- обобщенный вариант

• с концов

• элементы произвольное расположены в памяти

Размеры list

•size - число элементов

•empty - проверка на пустоту

•max_size

- максимальное число элементов (системно)

•resize - изменить число элементов

deque<> • блочно-списочная структура

• произвольный доступ

• быстрая вставка/удаление в конец

• быстрая вставка/удаление в начало

• изменение числа элементов делает итераторы невалидными

pair<>

• хранение пары значений,

м.б. разного типа

• сравнение пар

Определение pair<>

template struct pair

{ typedef T1 first_type; typedef T2 second_type;

T1 first; T2 second; pair() : first(T1()), second(T2()) {} pair(const T1& x, const T2& y)

: first(x), second(y) {} template pair(const pair&p)

: first(p.first), second(p.second) { }

}; Сравнение pair<>

• • определены операторы сравнения

==, , >= и )

- сравнивается first

- если равны, то сравниваются second

map<> • бинарное дерево поиска

• отображение key>value

• итераторы валидны при вставке и удалении

- кроме удаления текущего элемента

Объявление map<>

template, class Allocator = allocator > > class map

Доступ к элементам map

• через итератор

- обобщенный вариант find insert

• через индекс-ключ

T& operator[](const Key& k)

operator[] • если элемент не найден, создает элемент с умолчательным значением • м.б. заменен парой find и insert

пример: m[studentFio] = lastMark; if (m.end() != m.find(k)) ...

14.04.2012 cppNewb.ru 2

14.04.2012 cppNewb.ru 3

Показать полностью…
140 Кб, 21 апреля 2012 в 11:17 - Россия, Москва, НИТУ МИСиС, 2012 г., pdf
Рекомендуемые документы в приложении