close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
11.05.2014
Программирование
с использованием C++11
Полевой Дмитрий Валерьевич
к.т.н., доцент КиК
e-mail: [email protected]
1
11.05.2014
Псевдоним типа (typedef)
• typedef OldType NewType;
• определяет псевдоним типа, но не вводит
новый тип
• часто используется
– для сокращения кода, в т.ч. за счет подстановки
параметров шаблонов
– для сокрытия деталей реализации
30.04.2014
2
2
11.05.2014
Псевдоним типа (примеры)
typedef unsigend int size_t;
typedef basic_string<char> string;
30.04.2014
3
3
11.05.2014
Вложенные типы
• определяются внутри определения типа
(класс, структура)
• подчиняются спецификаторам доступа
• доступ с помощью оператора разрешения
области видимости
• в т.ч. для typedef
30.04.2014
4
4
11.05.2014
Вложенные типы (пример)
class Container
{
public:
typedef long SizeType;
...
private:
class Node
{
...
30.04.2014
5
5
11.05.2014
Обобщенное программирование
• Остерн М.Г.
Обобщенное программирование и STL.
Использование и наращивание
стандартной библиотеки шаблонов C++
• Александреску А.
Современное проектирование на С++:
Обобщенное программирование и
прикладные шаблоны проектирования STL
30.04.2014
6
6
11.05.2014
Типы указателей
• обычный
• сингулярный (нулевой)
– нельзя разыменовывать
– можно проверять на равенство
• следующий за последним в массиве
– нельзя разыменовывать
– можно использовать в арифметике указателей
и сравнениях
30.04.2014
7
7
11.05.2014
Диапазон (указателей)
• [first, last) состоит из всех указателей
(элементов) от first до last, не включая last
• является допустимым
– last достижим из first
– можно разыменовывать все указатели
– пустой диапазон [p, p) является допустимым
30.04.2014
8
8
11.05.2014
Диапазон (объектов)
• [first, last) состоит из всех объектов
(элементов) от *first до *(last-1)
включительно
• является допустимым
– last достижим из first
– можно получить адрес каждого объекта
– пустой диапазон [p, p) является допустимым
30.04.2014
9
9
11.05.2014
Свойства диапазонов
• если непустой диапазон [first, last) является
допустимым, то [first+1, last) является
допустимым
• если [first, last) допустимый и указатель mid
достижим из first, last достижим из mid, то
[first, mid) и [mid, last) допустимые
• если [first, mid) и [mid, last) допустимые, то
[first, last) допустимые
30.04.2014
10
10
11.05.2014
Массив, как диапазон
• [beg, beg + SIZE)
• число элементов SIZE = last – first
• last, как признак конца обработки
пример:
for (p = first; p != last; ++p)
{
if (value != *p)
...
}
30.04.2014
11
11
11.05.2014
Контейнер
• является регулярным типом
• содержит свои элементы
• предоставляет доступ к элементам
30.04.2014
12
12
11.05.2014
Свойства элемента контейнера
• элемент может принадлежать не более,
чем одному контейнеру (семантика
значений)
– контейнеры не пересекаются
– ограничение на объекты, а не на значения
• время жизни элемента не превышает
время жизни контейнера
– создается не раньше
– уничтожается не позже
30.04.2014
13
13
11.05.2014
Иерархия концепций контейнеров
• Контейнер Произвольного Доступа
• Реверсивный Контейнер
• Однонаправленный Контейнер
• Контейнер
– итератор ввода
30.04.2014
14
14
11.05.2014
Итератор
• интерфейс между алгоритмами и
структурами данных
– требования со стороны алгоритмов
• регулярный тип
operator=(), operator==()
• доступ к элементу контейнера
operator*(), operator->()
• навигация по контейнеру
30.04.2014
15
15
11.05.2014
Итератор (пример алгоритма)
template<class I, class T>
I find(I fst, I lst, const T& val)
{
while (fst != lst && *fst != val)
++fst;
return fst;
}
iV = find(b, e, v);
if (iV != e)
...
30.04.2014
16
16
11.05.2014
Принцип идентичности
• соотношения равенства итераторов и
равенства объектов
i1 == i2
i1 == i2
30.04.2014
↔
→
&*i1 == &*i2
*i1 == *i2
17
17
11.05.2014
Константные и изменяемые итераторы
• константный итератор
– доступ к константному объекту
– константный объект (значительно реже)
пример:
const int* pData{nullptr};
// !не константный итератор
int* const pVariant{&pA};
30.04.2014
18
18
11.05.2014
Итератор Произвольного Доступа
• допускает написание алгоритма с
произвольным доступом к контейнеру
• все манипуляции за амортизированное
константное время
operator++(), operator--()
operator+=(int)
operator-()
operator<()
operator[](int)
30.04.2014
19
19
11.05.2014
Двунаправленный Итератор
• допускает написание многопроходного
алгоритма
operator++(), operator--()
30.04.2014
20
20
11.05.2014
Однонаправленный Итератор
• допускает написание однопроходного
алгоритма
operator++()
• возможно существование более одного
итератора для интервала
30.04.2014
21
21
11.05.2014
Итератор Вывода
• однопроходное чтение (извлечение)
элементов
– не изменяет элементы
– единственный итератор для диапазона
– по диапазону нельзя пройти более одного раза
operator++()
30.04.2014
22
22
11.05.2014
Итератор Ввода
• однопроходная запись элементов
– единственный итератор для диапазона
– по диапазону нельзя пройти более одного раза
– не сравниваются (конец задан неявно)
operator++()
пример:
*iV = x;
30.04.2014
23
23
11.05.2014
Пример алгоритма (copy)
template<class InpI, class OutI>
OI copy(InpI first, InpI last, OutI res)
{
for (; first != last; ++res, ++first)
{
*res = *first;
}
return res;
}
30.04.2014
24
24
11.05.2014
Классы итераторов в STL
• iterator и const_iterator
• являются вложенными классами для
классов контейнеров
пример:
list<int>::iterator
list<int>::const_iterator
30.04.2014
25
25
11.05.2014
Интервал элементов контейнера
• begin()
– первый элемент (начало)
• end()
– элемент, следующий за последним (конец)
пример:
vector<int> ms;
vector<int>::iterator i{ms.begin()};
30.04.2014
26
26
11.05.2014
Пример поиска
// C data;
C::iterator it{dt.end()};
it = find(dt.begin(), dt.end(), k);
if (dt.end() != it)
// найден элемент со значением k
{
...
}
30.04.2014
27
27
11.05.2014
Контейнеры переменного размера
• Последовательность (Sequence)
• Ассоциативный Контейнер
(Associative Container)
30.04.2014
28
28
11.05.2014
Вставка элемента
• в конец
– push_back
• в начало
– push_front
• в произвольной позиции
– insert
30.04.2014
29
29
11.05.2014
Удаление элемента
• из конца
pop_back
• из начала
pop_front
• из произвольной позиции
remove
30.04.2014
30
30
11.05.2014
Вставка и удаление интервала
• из конца
pop_back
• из начала
pop_front
• из произвольной позиции
remove
30.04.2014
31
31
11.05.2014
Последовательности в STL
• array // массив
– произвольный
• vector // массив
– произвольный
• list // двусвязный список
– последовательный двунаправленный
• forward_list // одновязный список
– последовательный однонаправленный
• deque // дэк
– произвольный
30.04.2014
32
32
11.05.2014
Ассоциативные контейнеры в STL
(упорядоченные)
• set // множество
• multiset // мультимножество
• map // ассоциативный контейнер
• multimap
// множетсвенный ассоциативный
контейнер
30.04.2014
33
33
11.05.2014
Ассоциативные контейнеры в STL
(неупорядоченные)
• unordered_set
• unordered_multiset
• unordered_map
• unordered_multimap
30.04.2014
34
34
11.05.2014
typename (ключевое слово)
• явное указание, что идентификатор
является именем типа (в шаблонном коде)
• может использоваться вместо class в
описании параметров шаблона
30.04.2014
35
35
11.05.2014
Свойства (traits)
• свойства (ассоциированные типы) – часть
концепции
пример:
template<class T>
T
min(const T& lhs, const T& rhs)
{
return (lhs < rhs) ? lhs : rhs;
}
30.04.2014
36
36
11.05.2014
iterator_traits (для классов)
template<class I>
struct iterator_traits
{
typedef typename I::value_type value_type;
};
30.04.2014
37
37
11.05.2014
iterator_traits (для указателей)
template<typename I>
struct iterator_traits<typename I*>
{
typedef I value_type;
};
template<typename I>
struct iterator_traits<typename const I*>
{
typedef I value_type;
};
30.04.2014
38
38
11.05.2014
Пример использования свойств
// сумма в непустом диапазоне
template<class I>
typename iterator_traits<I>::value_type
sum(I first, I last)
{
typename iterator_traits<I>::value_type
res(*first++);
for (; first != last; ++first)
res += *first;
return res;
}
30.04.2014
39
39
11.05.2014
Операции над контейнерами и
валидность итераторов
• операции над контейнерами могут делать
итераторы невалидными
(в зависимости от реализации итераторов и
контейнеров)
• всегда следите за валидностью итераторов
• избегайте хранения итераторов
30.04.2014
40
40
11.05.2014
Реверсивные итераторы для
контейнеров
• значения интервала в обратном порядке
• специальные свойства и методы
reverse_iterator
rbegin()
rend()
• отличаются от обычных итераторов
30.04.2014
41
41
11.05.2014
reverse_iterator
• класс-адаптер для iterator
• для [f, l) интервал
[reverse_iterator(l),
reverse_iterator(f)) содержит
значения в обратном порядке
• основное тождество
&*(reverse_iterator(i)) == &*(i - 1)
&*r == &*(r.base() - 1)
30.04.2014
42
42
11.05.2014
Заголовочные файлы
• совпадают с именем контейнера
<array>
<vector>
<list>
<deque>
<set> - в т.ч. multiset
<map> - в т.ч. multimap
• вспомогательные
<utility>
<iterator>
30.04.2014
43
43
11.05.2014
vector<>
• динамический массив
• произвольный доступ
• быстрая вставка/удаление в конец
• медленная вставка/удаление в начало
• изменение числа элементов делает
итераторы невалидными
30.04.2014
44
44
11.05.2014
Объявление vector
template
<class T,
class Allocator = allocator<T> >
class vector
vector<bool> - специализация
30.04.2014
45
45
11.05.2014
Доступ к элементам vector
• через итератор
– обобщенный вариант
• по индексу
– замена встроенным массивам
• с концов
• последовательное расположение в памяти
30.04.2014
46
46
11.05.2014
Доступ к элементам vector
через итератор
• iterator begin()
– начало интервала
• iterator end()
– конец интервала
• reverse_iterator rbegin()
• reverse_iterator rend()
30.04.2014
47
47
11.05.2014
Доступ к элементам vector
(если контейнер const)
const_iterator begin() const
const_iterator end() const
30.04.2014
48
48
11.05.2014
Заполнение массива
• template<class InpI>
void
assign(InpI fst, InpI lst)
– скопировать диапазон
• void
assign(size_type n, const T& u)
– заполнить значениями u
30.04.2014
49
49
11.05.2014
Очистка массива
• iterator erase(iterator pos)
– удалить элемент
• iterator
erase(iterator fst, iterator lst)
– удалить элемент или интервал
30.04.2014
50
50
11.05.2014
list<>
• двусвязный список
• линейный доступ
• быстрая вставка и удаление в любой
позиции
• итераторы валидны при вставке и удалении
– кроме удаления текущего элемента
30.04.2014
51
51
11.05.2014
Объявление list<>
template
<class T,
class Allocator = allocator<T> >
class list
30.04.2014
52
52
11.05.2014
Доступ к элементам list
• через итератор
– обобщенный вариант
• с концов
• элементы произвольное расположены в
памяти
30.04.2014
53
53
11.05.2014
Размеры list
• size
– число элементов
• empty
– проверка на пустоту
• max_size
– максимальное число элементов (системно)
• resize
– изменить число элементов
30.04.2014
54
54
11.05.2014
deque<>
• блочно-списочная структура
• произвольный доступ
• быстрая вставка/удаление в конец
• быстрая вставка/удаление в начало
• изменение числа элементов делает
итераторы невалидными
30.04.2014
55
55
11.05.2014
pair<>
• хранение пары значений,
м.б. разного типа
• сравнение пар
30.04.2014
56
56
11.05.2014
Определение pair<>
template<class T1, class T2> 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 <class U, class V>
pair(const pair<U, V>&p)
: first{p.first}, second{p.second} { }
};
30.04.2014
57
57
11.05.2014
Сравнение pair<>
• <utility>
• определены операторы сравнения
==, <, !=, >, >= и <=
• (lhs == rhs) означает
(lhs.first == rhs.first) &&
(lhs.second == rhs.second)
• в сравнении на неравенство (<, >)
– сравнивается first
– если равны, то сравниваются second
30.04.2014
58
58
11.05.2014
map<>
• бинарное дерево поиска
• отображение key→value
• итераторы валидны при вставке и удалении
– кроме удаления текущего элемента
30.04.2014
59
59
11.05.2014
Объявление map<>
template<class Key, class T,
class Compare = less<Key>,
class Allocator =
allocator<pair<const Key,T> > >
class map
30.04.2014
60
60
11.05.2014
Доступ к элементам map
• через итератор
– обобщенный вариант
find
insert
• через индекс-ключ
T& operator[](const Key& k)
30.04.2014
61
61
11.05.2014
operator[]
• если элемент не найден, создает элемент с
умолчательным значением
• м.б. заменен парой find и insert
пример:
m[studentFio] = lastMark;
if (m.end() != m.find(k))
...
30.04.2014
62
62
11.05.2014
Где почитать
http://ru.cppreference.com/w/cpp/container
30.04.2014
63
63
1/--страниц
Пожаловаться на содержимое документа