Д.з. 1

Числа в обратном порядке - 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

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

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

Специализация 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

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

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

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

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

Еще про namespace 10

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

Еще про STL 12

Еще про итераторы Итераторы для вектора Те же операции 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();

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

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

map 16

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

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

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

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

Пример работы с 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

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

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

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

Пример: шаблон класса "стек" 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

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

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

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

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

Шаблон метода 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

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

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

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

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

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

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

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

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

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

Д.з. 40

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

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

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