'

Д.з.

Понравилась презентация – покажи это...





Слайд 0

Д.з. 1


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 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


Слайд 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 << "Deleting " << p + 1; delete [] p; } } public: 6


Слайд 6

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 << p+1; } }; // Конец определения класса 7


Слайд 7

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


Слайд 8

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


Слайд 9

Еще про namespace 10


Слайд 10

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


Слайд 11

Еще про STL 12


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

map 16


Слайд 16

map (ассоциативный массив) #include <map> using namespace std; map<double, int> m; m[3.14] = 55; m[2.238] = 73; m[9.0] = 15; cout << m[3.14]; m[9.0]++; 3.14 – ключ 55 - значение Что будет, если написать так?: cout << m[99.9]; Напечатается 0 ! Добавляется новый ключ, значение равно 0 В общем случае – для значения вызывается к-р по умолчанию 17


Слайд 17

Итератор для map Как перебрать все ключи? for (auto p = m.begin(); p != m.end(); p++) cout << p->first << p->second << " "; Итератор указывает на структуру pair (пара) с полями first, second (Кстати: Для итераторов определен оператор ->) Ключи идут в порядке возрастания Можно быстро найти значние по ключу: p = m.find(i); if (p == m.end() ) cout << "Не найдено"; else cout << p->second; поиск – быстро O(log N)


Слайд 18

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


Слайд 19

map – что может быть ключом? М.б. любой тип, для которого задан operator< map<double, int> m1; map<string, int> m2; map<abc, int> m3; // (Если задан abc::operator<) map<complex, int> m; // Ошибка! В принципе, можно задавать свою функцию сравнения Совет: Если строка должна быть ключом – только map<string, …>. Не пытайтесь map<char*, …> или map<char[100], …> и т.д.! Все равно не получится.. 20


Слайд 20

Пример работы с map // Вводим пары чисел и печатаем их в порядке возрастания // первого числа #include <map> using namespace std; ... map<double, int> 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 << p->first << "-" << p->second << "\n"; 21


Слайд 21

Еще пример – телефонная книга #include <iostream> #include <string> #include <map> using namespace std;   // Определим тип phonebook – // телефонная книга typedef map<string, long> phonebook; phonebook pb; // Тел. книга // (вначале она пустая) // Так задаются значения pb["Иванов"] = 3223322;   pb["Петров"] = 2991234; pb["Сидоров"] = 1231231; // Печатаем телефон Петрова cout << pb["Петров"];   // Печатаем все телефоны for (auto p = pb.begin(); p != pb.end(); p++) { cout << p->first << "-" << p->second <<"\n"; }   22


Слайд 22

Tелефонная книга - продолжение // Так можно проверить, есть ли человек в тел.книге if ( pb.find("Smith") != pb.end() ) { cout << "Есть"; } else { cout << "Нет"; }   // Так можно удалить человека из книги pb.erase("Чижиков"); 23


Слайд 23

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


Слайд 24

Пример: шаблон класса "стек" template <class T> 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<int> s1; stack<double> s2; stack<complex> s3; stack<stack<int>> s4; При использовании параметры надо указывать явно 25


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

Д.з. про шаблон для печати - 1 // Вариант 1a template <class T> void print(T& c) { T::iterator p; for (p = c.begin(); p != c.end(); p++) cout << *p << " "; } // Пример вызова list<int> l; vector<string> v; … print(l); print(v); // Вариант 1б - исправленный template <class T> void print(T& c) { typename T::iterator p; for (p = c.begin(); p != c.end(); p++) cout << *p << " "; } 34


Слайд 34

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


Слайд 35

Д.з. про шаблон для печати - 3 // Вариант 2 template <class T> void print(T from, T to) { for (T p = from; p != to; p++) cout << *p << " "; } // Пример вызова vector<int> v; list<string> l; … print(v.begin(), v.end()); print(l.begin(), l.end()); Преимущества: Можно вызывать не только для всего контейнера print(v.begin() +2, v.end()-3); Очень мало требует от T Только *, ++, !=. int a[10]; … print(a, a+10); Недостатки: Дольше писать ? 36


Слайд 36

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


Слайд 37

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


Слайд 38

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


Слайд 39

Д.з. 40


Слайд 40

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


Слайд 41

Д.з. - 2 Шаблон queue - очередь (аналог stack, но first in – first out). // Пример использования queue<int> q; q.push(3); q.push(7); q.push(11); cout << q.pop(); // 3 cout << q.pop(); // 7 Можно считать, что очередь фиксированной длины и реализовать, как массив (примерно как стек в слайдах) Можно реализовать с использованием vector или list (или deque) (И тогда вы можете сказать, что применили шаблон «адаптер»…) 42


Слайд 42

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


×

HTML:





Ссылка: