Д.з. 1Д.з. 1Числа в обратном порядке - 1 list l; // Вариант с list // Добавляем числа в обратном // порядке for (;;) { cin >> n; // Читаем числа if (n==0) - презентация

1 Д.з. 1

2 Числа в обратном порядке - 1 list l; // Вариант с list // Добавляем числа в обратном // порядке for (;;) { cin >> n; // Читаем числа if (n==0) // до 0 break; l.push_front(n); } // Печатаем for (auto p=l.begin(); p!=l.end(); p++) { cout n; if (n==0) break; v.push_back(n); } // Идем от конца к началу auto p = v.end(); while (p != v.begin() { p--; cout

3 Числа в обратном порядке - 2 Какой вариант лучше? Для больших объёмов list гораздо медленнее! list – только если надо часто добавлять в середину (или удалять) Еще можно было использовать deque (следующее занятие)

4 Шаблон swp template void swp(T& x, T& y) { T tmp = x; x = y; y = tmp; } Замечание: T tmp;// Так хуже, чем T tmp = x; tmp = x; - Немного медленнее - Более существенно, работает только если в классе есть конструктор по умолчанию (определение менее общее). 4

5 Специализация swp для string class string { char* p; int len; public: friend void swp(string& x, string& y); … }; void swp(string& x, string& y) { swp(x.p, y.p); swp(x.len, y.len); } 5

6 shared_string class shared_string { char* p; //len для краткости не используем // Воспомогaтельные методы // Поставить указатель p на // данную строку и увеличить // в ней счетчик. void set_ptr(char * newp) { p = newp; (*newp)++; } // Уменьшить счетчик в строке, // на которую указывает p. // Если надо, удалить строку. void drop_ptr() { (*p)--; if (*p == 0) { cout

7 shared_string - продолжение shared_string(const char* s = "") { p = new char[strlen(s)+2]; *p = 1; strcpy(p + 1, s); } ~shared_string() { drop_ptr(); } shared_string(const shared_string& from) { set_ptr(from.p); } shared_string& operator= (const shared_string& from) { if (p != from.p) { drop_ptr(); set_ptr(from.p); } return *this; } void print() const { cout

8 shared_string - замечания Еще вариант – non-intrusive Называется: reference counting (счетчик ссылок) Похожая вещь: smart pointers (умные указатели). shared_ptr в новой стандартной библиотеке 8

9 Copy on write (Этот слайд на занятии не показывался, но в презентации пусть останется, может кому-то будет интересно посмотреть..) Хотелось бы: shared_string + возможность менять строки Идея: разделять строки перед изменением string s = "abc"; string s1 = s;// s.p и s1.p указывают на одну строку s[i] = '!'; // Создается _отдельная_ копия строки, // и изменения происходят в ней. Недостатки: М.б. получается слишком сложно.. 9

10 Еще про namespace 10

11 Еще возможности Инкрементальное определение namespace abc { … определения … } … что-то вне namespace … namespace abc { … еще определения … } Глобальное пространство имен ::f() – глобальная функция using ::f; M.б. вложенные abc::klm 11

12 Еще про STL 12

13 Еще про итераторы Итераторы для вектора Те же операции p + n p – n p += n p -= n Итераторы и константы const_iterator void f(const vector & v) { // Тут просто итераторы // использовать нельзя vector ::const_iterator p =v.begin(); … Но, еще раз, м.б. лучше не писать тип p явно: auto p = v.begin();

14 Вставка и удаление insert l.insert(p, n); Вставляет перед p Работает быстро (время O(1) (T.е. не зависит от длины списка) Работает и для vector, но для vector время линейно от длины erase l.erase(p); Тоже работает быстро Тоже работает и для vector, но за линейное время 14

15 vector – дополнительные возможности Просто для сведения, на экзамене не будет: reserve v.reserve(1000);// Зарезервировать место присваивание v = v1; сравнение if (v == v1) лексикографическое сравнение if (v < v1) swap swap(v, v1); // Эффективно 15

16 map 16

17 map (ассоциативный массив) #include using namespace std; map m; m[3.14] = 55; m[2.238] = 73; m[9.0] = 15; cout

18 Итератор для map Как перебрать все ключи? for (auto p = m.begin(); p != m.end(); p++) cout first second ) Ключи идут в порядке возрастания Можно быстро найти значние по ключу: p = m.find(i); if (p == m.end() ) cout

19 Еще про map Внутреннее представление: дерево поиска(red-black tree) Удаление m.erase(i); или m.erase(p); Еще добавление: insert Можно добавить пару Чтобы задать пару есть очень простая функция (точнее, шаблон) make_pair m.insert(make_pair(i, x)); 19

20 map – что может быть ключом? М.б. любой тип, для которого задан operator< map m1; map m2; map m3; // (Если задан abc::operator

21 Пример работы с map // Вводим пары чисел и печатаем их в порядке возрастания // первого числа #include using namespace std;... map m; double x; int i; while ( cin >> x >> j ) m[x] = j;// или можно то же записать, как // m.insert(make_pair(x, j)); for (auto p = m.begin(); p != m.end(); p++) cout first second

22 Еще пример – телефонная книга #include using namespace std; // Определим тип phonebook – // телефонная книга typedef map phonebook; phonebook pb;// Тел. книга // (вначале она пустая) // Так задаются значения pb["Иванов"] = ; pb["Петров"] = ; pb["Сидоров"] = ; // Печатаем телефон Петрова cout

23 Tелефонная книга - продолжение // Так можно проверить, есть ли человек в тел.книге if ( pb.find("Smith") != pb.end() ) { cout

24 Шаблоны классов 24

s4; При использова" title="Пример: шаблон класса "стек" template class stack { T stk[100]; int size; public: stack() : size(0) {} void push(const T& x) { size[size++] = x; } T pop { return stk[--size]; } }; Использование stack s1; stack s2; stack s3; stack > s4; При использова" class="link_thumb"> 25 Пример: шаблон класса "стек" template class stack { T stk[100]; int size; public: stack() : size(0) {} void push(const T& x) { size[size++] = x; } T pop { return stk[--size]; } }; Использование stack s1; stack s2; stack s3; stack > s4; При использовании параметры надо указывать явно 25 s4; При использова"> s4; При использовании параметры надо указывать явно 25"> s4; При использова" title="Пример: шаблон класса "стек" template class stack { T stk[100]; int size; public: stack() : size(0) {} void push(const T& x) { size[size++] = x; } T pop { return stk[--size]; } }; Использование stack s1; stack s2; stack s3; stack > s4; При использова">

26 Замечания Методы можно описывать вне класса template void stack ::push(const T& x) {... } В частности, конструктор: template stack ::stack(): size(0) {} 26

27 Еще возможности Не типовые параметры: template class stack { T stk[maxsize]; … }; stack s; Такие параметры м.б. только целые (и в некоторых случаях указатели) При вызове д.б. константы Внутри - как константы Параметры по умолчанию template class stack { … stack s; // To же, что stack 27

28 Специализация Специализация шаблона template class stack { // Что-то особенное }; Реальный пример из STL – vector Специализация метода template void stack :: push(double x) { // Что-то особенное }; 28

29 Частичная специализация template class stack { // Что-то особенное }; М.б. сложная система разных специализаций template class abc { … }; template class abc { … }; template class abc { … }; template class abc { … }; template class abc { … }; 29

30 Шаблон метода class abc { … template void f(T x) { … } … }; abc x; x.f(5);// f x.f(3.14);// f // Пример template class complex { T re, im; … template complex(const T1& from) : re(from.re), im(from.im) {} }; // Хотим задать преобразование // complex -> complex complex c1(1,2); complex c2 = c1; Генерируется конструктор complex (const complex & from) 30

31 Параметры - шаблоны template class T > class abc { T x; T y; T z; … }; abc v; 31

32 Замечание Когда мы пишем шаблоны – это мы пишем код, который работает для разных типов. Называется: полиморфизм Статический полиморфизм 32

33 Как лучше писать шаблоны алгоритмов для работы с контейнерами? 33

34 Д.з. про шаблон для печати - 1 // Вариант 1a template void print(T& c) { T::iterator p; for (p = c.begin(); p != c.end(); p++) cout

35 Д.з. про шаблон для печати - 2 // Вариант 1в – const correctness template void print(const T& c) { typename T::const_iterator p; for (p = c.begin(); p != c.end(); p++) cout

36 Д.з. про шаблон для печати - 3 // Вариант 2 template void print(T from, T to) { for (T p = from; p != to; p++) cout

37 Библиотека MFC. Рисование в Windows программах. Все за 10 минут. 37

38 Создание MFC программы 1. Ряд заклинаний (инструкция на сайте) Получится рабoтающая программа (которая пока ничего не делает). 2. Найти место, куда вписать свой код CAbcView::OnDraw(CDC* pDC) { // TODO 38

39 Рисование в MFC CDC* pDC- device context pDC->Ellipse(x1, y1, x2, y2); pDC->MoveTo(x, y); pDC->LineTo(x, y); 39

40 Д.з. 40

41 Д.з Ввести число n и потом n раз фамилию человека и оценку. Напечатать для каждого человека, сколько пятерок он получил. Например, вводим: 5 Иванов 5 Петров 4 Сидоров 5 Иванов 3 Сидоров 5 И д.б. напечатано: Иванов 1 Петров 0 Сидоров 2 Напоминание – как вводить слова: #include string s; … cin >> s; 2. Описать тип (типы?) для телефонной книги: имя телефон, имя, адрес (день рождения?). Привести пример работы с таким типом. 41

42 Д.з Шаблон queue - очередь (аналог stack, но first in – first out). // Пример использования queue q; q.push(3); q.push(7); q.push(11); cout

43 Д.з MFC - вложенные треугольники (соединяем середины сторон). Сколько треугольников – как хотите, фиксированное количество, или пока очередной не станет очень маленьким. 5. MFC – треугольник Серпинского Замечания: Если сделана задача 5 – задачу 4 можно не делать, она зачтется автоматически Присылать достаточно только тот файл, который вы меняли – в данном случае это …View.cpp Если хотите, можно эту программу написать с помощью любой среды и библиотеки, не обязательно MFC 43