САОД 2 Основы С++

1.

САОД. Лекция 2.
Основы С++
А.М. Задорожный

2.

Содержание
1. Объекты с динамическими данными
a) Конструктор копирования
b) Присваивание
2. Шаблоны
3. Стандартная библиотека
4. Контейнеры STL

3.

Контрольные вопросы
1. Из каких шагов состоит построение программы на C++?
2. Что размещают в заголовочных файлах?
3. Какие 2 способа передачи параметров в функци. Имеются в
C++?
4. Можно ли вызвать void foo(int & a) следующим образом:
foo(x+y); Почему?
5. Может ли функция foo из предыдущего вопроса изменить
значение переменной, переданной в качестве параметра?
6. Сколько операций умножения в операторе *p = *p * 2?
5. Какие 3 различных смысла в C++ имеет символ &?
6. Какие 3 различных смысла в C++ имеет символ *?

4.

Контрольные вопросы
7. Можно ли сделать так, чтобы первый элемент C-массива имел
индекс 2?
А 0?
8. Если массив w проинициализирован значениями 1, 2, 3. Чему
равно значение выражения *w?
9. Чему равна величина p + i, где p – указатель на массив, а i –
целое число?
10.Чему равна величина p – d, где p и d – указатели на величины
типа double?

5.

Контрольные вопросы
1. Опишите время жизни локальных и глобальных
переменных.
2. Что такое “динамическая память”?
3. Как выделить блок динамической памяти под N чисел
типа double?
N – целое положительное число.
4. Как освободить блок памяти выделенный new?
5. Что такое Конструктор? Когда вызывается?
6. Что такое деструктор? Когда вызывается?
7. Как обнаружить деструктор в объявлении класса?

6.

Где мы
Довольно много знаем о построении и выполнении
программы на C++.
Из каких файлов состоит, препроцессор, компиляция,
сборка. Указатели, ссылки, передача параметров…
Познакомились с классами. Получили небольшую
практику по их созданию и применению.
Конструкторы, деструкторы, операторы + … (класс
Complex), локальные и динамические объекты …
Но кое-что важное еще предстоит узнать!

7.

Объекты с динамическими данными
Класс String
class String {
char* data;
public:
String(const char* s = NULL) {
if (s) {
data = new char[strlen(s) + 1];
strcpy_s(data, strlen(s) + 1, s);
}
else data = NULL;
}
~String() { delete [] data; }
};
operator char* () const {
if (data) return data;
else return (char* ) "";
}

8.

Объекты с динамическими данными
Класс String
class String {
char* data;
public:
String(const char* s = NULL) {
…
}
~String() { delete [] data; }
};
1234
s
operator char* () const { … }
Копирование.
String s = "123";
String t = s;
// Это не присваивание, а копирование
Память объекта s скопируется в новый объект t.

9.

Варианты использования Str
Неправильное копирование*
Это же при передачи параметра!
void Test1 (String sz)
{}
1234
s
Создается копия s
sz
Копия разрушается
int main(){
String s = “1234”;
Test1(s);
}
sz
1234
s
Сработал деструктор и…
Исходный объект не валиден!

10.

Конструктор копирования*
String (const String &s) //Константная ссылка на объект
{
if (s.data) {
data = new char [strlen(s.data) + 1];
strcpy_s (data, strlen(s.data) + 1, s.data);
}
else data = NULL;
}
Конструктор, у которого есть единственный параметр – константная
ссылка на объект того же типа, называется конструктором
копирования.
Он, если задан, будет вызываться во всех случаях создания копии
объекта.

11.

Создание копии*
Теперь есть “Правила
Копирования”
1234
s
В результате получаем:
1234
sz
“Правильные” копии можно создавать и
использовать без ограничений!

12.

Варианты использования String
Неправильное присваивание*
s
int main(){
String s = “1234”, s1=“56”; s1
s = s1;
s
}
s1
1234
56
1234
56
В результате присваивания память s1 (включая
указатель) была скопирована в s:
• Блок “1234” остался “висеть”;
• Оба объекта “владеют” одним блоком.

13.

Операция присваивания*
const String& operator = (const String &s) //Константная ссылка на объект
{
if(&s == this) return *this;
delete [] data;
//Освобождаем текущие данные
//Дальше просто копирование
if (s.data != NULL) {
data = new char [strlen(s.data) + 1];
strcpy_s (data, strlen(s.data) + 1, s.data);
}
else data = NULL;
return *this;
}
Теперь объекты класса Str можно без проблем присваивать друг другу.

14.

Операция +=
еще пример манипулирования данными
Операция += изменяет объект - добавляет к строке строку,
указанную справа.
String& operator += (const String &s) //Константная ссылка на
объект
{
if (s.data != NULL) {
int newLen = data? strlen(data): 0;
newLen += strlen(s.data) + 1;
char *p = new char [newLen];
strcpy_s (p, newLen, data);
strcat_s (p, newLen , s.data);
delete [] data;
data = p;
}
return *this;
}
За сценой все происходит явно. Выделяется, копируется и
освобождается память.

15.

На практике
Посмотрим, как работают конструкторы
копирования.

16.

Контрольные вопросы
1. Перечислите виды конструкторов применяемых в C++.
2. Почему для Date не нужен деструктор и конструктор копии, а для String
нужны?
3. Почему в конструктор копии передают ссылку на объект, а не копию объекта?
4. Зачем при передаче ссылок и указателей применяется слово const?
5. Приведите примеры, когда копии объектов возникают без явного вызова
конструктора.
6. Что в C++ методе означает слово this? Чем оно отличается от this в C#?
7. Что произойдет, если выполнить следующий код:
String s = “abcd”;
s = “1234”;
Имеется соответствующий конструктор инициализации и оператор
присваивания объектов Str.

17.

Шаблоны
Шаблон – абстракция алгоритма или типа данных.
Ранее рассматривали функцию Swap. Параметры
передаются по ссылке.
void Swap(int &a, int &b){
int t = a;
a = b;
b = t;
}
Значит для каждого типа данных (int, char, double,
string… ) придется написать свою функцию!
Очень неэффективно с т.з. программиста!

18.

Шаблоны
Объявим шаблон Swap.
template <typename T> void Swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
Начинаем с template – шаблон. Затем в угловых скобках ключевое
слово typename (имя типа) и T – имя параметра шаблона, как
заместитель конкретного типа (шаблоны параметризуются
типами данных).
Далее определение функции, где вместо конкретного типа данных
используется параметр шаблона (T).
Компилятор не будет строить функцию при определении шаблона.
Но при обращении к Swap определит T по тексту и самостоятельно
сгенерирует функцию с необходимым типом данных!

19.

Шаблоны
int a = 3, b = 5;
double x = 0.5, y = 2.5;
string s = "123", t = "abc";
Можно:
Swap(a,b);
Swap(x, y);
Swap(s, t);
Компилятор для каждого случая определит
тип аргументов, сгенерирует нужную
функцию и вызовет ее!
Очень удобно и эффективно!

20.

Шаблоны
Объявим шаблон класса vect. Это массив фиксированного
размера.
template <typename T, int N> class vect{
T data[N]={0};
public:
int size = N;
T &operator [](int i) {if (i < 0) i = -i; i %=size; return data[i];}
};
Начинаем с template – шаблон. Затем в угловых скобках typename
– имя типа и T, как заместитель конкретного типа.
Можно и константы – int N – у нас будет размер массива.
Далее определение класса, где вместо конкретных типов данных
используется T, а вместо постоянных значений можно
использовать N. Теперь компилятор определит T в коде, где
происходит обращение к vector и самостоятельно сгенерирует
класс нужного типа и с заданными константами!

21.

Шаблоны
Пример шаблона класса.
template <typename T, int N> class vect{
T data[N]={0};
public:
int size = N;
T &operator [](int i) {if (i < 0) i = -i; i %=size;
return data[i];}
};
vect<int, 16> vi16;
vect<double, 128> vd128;
vect<string, 4> vs4;
Теперь можно:
Компилятор в каждом случае использует нужный тип данных и
параметр-константу и сгенерирует необходимый класс!
Часто применяемому типу можно дать имя. Например,
typedef vect<double, 128> vd128 vDbl128;

22.

На практике
Как заработал шаблон Swap

23.

Контрольные вопросы
1. Что такое шаблон в C++?
2. Почему мы говорим, что шаблоны – это абстракции?
3. Как объявить шаблон?
4. Как использовать шаблон функции (метода) в коде?
5. Как использовать шаблон класса в коде?
6. Что еще может быть параметром шаблона, кроме типа
данных?
7. Как вы думаете, где должны располагаться шаблоны, в hили в cpp-файлах? Почему?

24.

STL – стандартная библиотека
(шаблонов)
STL - Standard Template Library
Набор абстрактных типов данных и алгоритмов.
Основное содержание в заголовочных файлах.
Для использования модуля библиотеки нужно подключить
соответствующий заголовок.
Соглашение: Заголовочные файлы не имеют расширения.
Все имена определены в пространстве имен std. Если используем
много имен из STL, то удобно
using namespace std;
Не понадобится перед каждым именем std::cout, std::endl, …
24

25.

Потоки (STL)
#include <iostream> - Обобщенный способ организации
ввода/вывода.
– Потоки ввода (istream),
– Потоки вывода (ostream),
– И потоки ввода-вывода (iostream).
Дают общий способ для работы с данными в файлах, памяти,
поступающих по сети или из другого источника.
С консолью пробовали и применяем. Кроме cin, cout имеются cerr
и clog – оба потоки вывода. Это т.н. стандартные потоки.
Коротко коснемся работы с файлами. Больше будет в
упражнениях.
25

26.

Файловые потоки
Для работы с файловыми потоками нужно использовать заголовок
#include <fstream>.
#include <iostream>
#include <fstream>
using namespace std;
int main(){
…
ifstream ifs;
ifs.open(fName);
…
}
См. пример далее…
26

27.

Файловые потоки
int main(){
char fName[128];
cout << "File name ? : "; cin.getline(fName, 127);
cout << fName << endl;
ifstream ifs;
ifs.open(fName);
// (fName, ios_base::binary);
if (ifs.is_open()) {
char tmp[1024];
ifs >> tmp;
cout << tmp << endl;
ifs.close();
}
else
cout << fName << " - does not exist" << endl;
return 0;
}
27

28.

Файловые потоки
Пример в бинарной моде*
int main(){
char fName[128];
cout << "File name ? : "; cin.getline(fName, 127);
cout << fName << endl;
char c = ‘0’;
int n=5;
double d = 7;
ofstream ofs;
ofs.open (fName, ios_base::binary);
}
//Открыт в бинарной моде
if (ofs.is_open()) {
ofs.put(c);
ofs.write((char*)&n, sizeof(n));
ofs.write((char*)&d, sizeof(d));
ofs.close();
}
else
cout << fName << " – can not create or open." << endl;
return 0;
28

29.

Строки
Стандартная библиотека предоставляет класс работы со
строками – заголовок <string>.
Теперь вместо:
char fName[128];
cout << "File name ? : "; cin.getline(fName, 127);
cout << fName << endl;
можно использовать:
string fName;
cout << "File name ? : "; cin >> fName;
cout << fName << endl;
29

30.

Строки
Минимальный набор
• Конструкторы: string(), string (const char *p) и string(const string
&s) и др.
• Операции: length(), [], =, +, +=, <, >, …
• string substr(int Offset, int Length)
• int find(const string &s, int Offset) - возвращает индекс
ближайшего появления подстроки начиная с Offset и -1 если
нет.
• Можно получить и указатель на z-строку:
const char * c_str() const;
Всего несколько десятков методов.
30

31.

Контрольные вопросы
1.
Какие стандартные потоки определены в STL?
2.
Чем отличается работа с потоком в текстовой и
бинарной моде?
3.
Назовите несколько операций над строками в STL?
31

32.

Контейнеры в STL
Важная часть STL – шаблоны контейнеров.
Контейнеры – классы для хранения объектов других
классов. Реализуют все базовые структуры данных:
deque (queue, stack), - очередь с двумя концами
list,
- связный список
vector (priority_queue) – динамический массив
Словари
hash_map, hash_set, hash_multimap, hash_multiset
map, set, multimap, multiset
32

33.

Общие свойства контейнеров
• Контейнеры STL можно параметризовать
любыми типами, для которых определены
операции: копирования, =, == и <.
• При включении в контейнер всегда создается
копия объекта.
Нельзя включить в контейнер объект по
ссылке.
• Универсальный способ для доступа к
элементам любого контейнера – итераторы.
33

34.

Итераторы
итераторы как понятие
Итераторы - типы, позволяющие двигаться по контейнеру
• <TYPE NAME>::iterator i = obj.begin();
• <TYPE NAME>::iterator i = obj.end(); //сразу за последним
Метафора итератора – указатель.
for(<TYPE NAME>::iterator i = obj.begin();
i != obj.end();
i++)
{
// Делаем что хотели с элементами,
//используя *i;
}
34

35.

Итераторы
Начиная с C++11 можно:
for (auto &v : obj) {
// Делаем что хотели с элементами,
//используя v;
}
Auto просит компилятор самостоятельно установить тип.
! Внимание на & - амперсанд перед v. Если объект большой, то он
не будет копироваться. Если его нужно изменить, то по ссылке
можно и изменить!
Как и ожидается, изменять сам контейнер (добавлять или удалять
элементы) так нельзя!
35

36.

Итераторы и .Net
• Как правило, использование итераторов
позволяет более эффективно пройти по всему
контейнеру, чем другие способы;
• Аналогией в .Net является применение
оператора foreach
foreach(var p in Lst)
{
//… обработка элемента контейнера p
}
36

37.

Последовательные контейнеры
Последовательными называются
контейнеры, в которых имеет смысл
(определен) порядок элементов.
Очередь, массив, список – примеры таких
контейнеров.
37

38.

Последовательные контейнеры
Список
typedef list<string> LSTSTR;
//Создание
LSTSTR lst1, lst2(5, “abc”);
LSTSTR lst3(lst2), lst4(lst2.begin(), --lst2.end());
//Проверка на пустоту
cout << lst1.empty() << endl; //true
//Количество элементов
cout << lst2.size() << endl; //5
38

39.

Список
//Добавление элементов
lst1.push_back(“2”);
// {2}
lst1.push_front(“1”);
// {1,2}
lst1.insert(--lst1.end(), “a”);
// list is {1,a,2}
cout << lst1.size() << endl;
// 3
//Изменить элемент
*lst1.begin() = “3”;
// {3,a,2}
//Получить первый/последний
cout << lst1.front() << endl;
//3
cout << lst1.back() << endl;
//2
39

40.

Список
//Присваивание
lst2 = lst1;
//Удаление элементов
lst1.remove(“a”);
// {3,2}
lst1.erase(lst1.begin())
// {2}
lst1.erase(lst1.end())
// empty
//Отсортировать список методом sort.
lst2.sort()
// {2, 3, a}
Sort “знает как устроен список”! Поэтому он более
эффективно выполняет сортировку.
40

41.

Последовательные контейнеры
Динамический массив
В принципе, другие контейнеры рассматриваем аналогично:
как создать, какие операции и свойства, как получать доступ к
элементам, как добавлять или удалять.
typedef vector<int> VINT;
//Создание
VINT v1, v2(100);
VINT v3(v2.begin(), --v2.end());
//Присваивание
v3 = v1;
//Доступ к элементам
v2[i] = 10;
41

42.

Последовательные контейнеры
Динамический массив
// добавляем элемент в конец массива
v2.push_back(11);
cout << v2.size() << endl;
// 101
// Можно и v2.insert(v2.begin(), x);
Отсортировать массив можно функцией STL sort.
//sort vector
sort(v.begin(), v.end());
Для сортировки указывается диапазон итераторов. Можно
отсортировать только часть массива!
Функция sort размещена в модуле <algorithm>.
42

43.

Последовательные контейнеры
Динамический массив
В дополнение к списку vector (как и string) имеет 2
характеристики размера:
• size() – количество элементов (есть и у списка);
• capacity () – количество элементов, которые может
включать без расширения памяти;
Очевидно, size() <= capacity()!
При добавлении/удалении элементов size изменяется
соответствующим образом.
За capacity отвечает сам контейнер.
43

44.

Последовательные контейнеры
Очереди и стеки
<deque> - Double ended queue, двусторонняя очередь
(сокращенно Дек).
Позволяет помещать и получать объекты в порядке
поступления как в начало, так и в конец.
Основные операции:
push_back(<…>), push_front (<…>)
<…> pop_back(), <…> pop_front ()
Ограничивая функционал дека можно прийти к
очереди (queue) и стеку (stack).
44

45.

Ассоциативные контейнеры
В ассоциативных контейнерах порядок
элементов не играет значения (это вопрос
реализации).
Получаем или изменяем элементы по ключу!
(ассоциации - связи)
B set и map допускают ТОЛЬКО уникальные
ключи (два элемента с одинаковым ключом
добавить в них нельзя).
45

46.

Ассоциативные контейнеры
Множество
typedef set<string> SETSTR;
//Создание
SETSTR s, s2;
//Пустой
cout << s.empty() << endl;
//true
//Добавление элементов
s.insert (“abc”); s.insert (“123”);
// s.size() == 2
s2 = s;
// s2 == s
//Поиск элемента
SETSTR::iterator i = s.find(“abc”);
//i != s.end(), *i == “abc”
i = s.find(“efd”);
//i == s.end(), т.к. “efd” нет
//Удаление элементов
s.erase (“abc”); s.erase(s.begin());
// s is empty
46

47.

Пары
pair – удобная абстракция <ключ, значение>
pair<int, string> pr; //ключом является int, значение –
string.
pr.first = 1;
pr.second = “123”;
Можно
pair<int, string> pr1 = make_pair(2, “abc”);
Пары можно копировать, присваивать, сравнивать
(сравнивается ключ и значение!)*
47

48.

Ассоциативные контейнеры
Словари
Словарь (map), содержат пары: <ключ>-<значение>
typedef map<string, int> STR2INT;
//Создание
STR2INT m;
//Пустой
cout << m.empty() << endl;
//true
//Добавить и изменить
m.insert(STR2INT::value_type(“a”,1));
// m.size() == 1
m[“b”] = 2;
// m.size() == 2
m[“a”] = 3;
// m.size() == 2, т.к. ключ “а” уже был
48

49.

Ассоциативные контейнеры
Словари
Словарь (map), содержат пары: <ключ>-<значение>
typedef map<string, int> STR2INT;
//Поиск
STR2INT::iterator i = m.find(“a”); // i != m.end(),
// (*i).first == “a” или i->first
// (*i).second == 3 или i->second
m[“b”] == 2;
int n = m.count(“b”);
// 0 или 1.
Для ‘b’ 1
49

50.

Словари*
int n = m.count(“a”);
STR2INT::iterator i = m.find(“ab”);
// 1 или 0
//i == m.end()
//Содержат пары!
for (STR2INT::iterator i= m.begin(); i != m.end(); i++)
cout << i->first << “\t” << i->second << endl;
//или!
for (auto &p: m)
cout << p.first << “\t” << p.second << endl;
//Удаление элементов
m.erase(“a”); m.erase(m.begin());
// m is empty
50

51.

Прочие шаблоны
Иногда полезно иметь контейнер для хранения нескольких элементов с
одинаковым ключом.
В STL это multiset и multimap.
Определены multi-контейнеры в тех же заголовочных файлах <set> и <map>.
Методы multi-контейнеров практически совпадают с методами set и map, за
исключением того, что для multimap не определен оператор [] – выбора
элемента по ключу.
STL имеет набор стандартных алгоритмов.
Описаны в заголовочном файле <algorithm>.
В частности, метод sort, который применялся для вектора,
расположен именно в <algorithm>.
Общий совет:
Прежде чем изобретать собственные контейнеры поищите полезные
возможности стандартной библиотеки.
51

52.

Сложность алгоритма
Сложность алгоритма – зависимость числа операций
от объема данных (N).
Выражается сложность с использованием символа O(x) –
“о большое”.
O(f(N)) - означает, что асимптотика поведения (N->∞) не
превосходит f(N) с некоторым коэффициентом.
Например, y(N) = 5*N3 + 1000*N2 описывается как O(N3) асимптотически не превосходит, например, 6*N3.
Т.е. достаточно учесть ТОЛЬКО старшую зависимость от
N.
В теории сложности выделяют несколько классов
сложности. Задачи, сложность которых выражается
полиномом от N, называются P-сложными (polynomial).

53.

Сложность алгоритма
Для понимания сути других классов сложности – NP, NPComplete, NP-Hard нужно начинать с машины Тьюринга.
Теория сложности алгоритмов интересная область, в которой
много нерешенных вопросов, но это
ЧИСТАЯ МАТЕМАТИКА!
И все же с точки зрения программирования полезно знать, что
для ряда задач не известно алгоритма P-сложности.
Таких задач много среди задач оптимизации в комбинаторике,
например, “Задача коммивояжера”.
Зачем это программисту?
Если известно время решения задачи для N = 100, каково будет
время для N= 1000? Понять это и поможет оценка сложности.

54.

Зачем столько контейнеров?
1.
Сложность изменения списка O(1), а чтения элемента с
заданным номером O(N);
2.
Сложность изменения массива O(N), а сложность чтения
элемента с заданным номером O(1);
3.
Сложность изменения и чтения ассоциативных контейнеров
O(Ln(N)).
4.
Сложность изменения и чтения hash-контейнеров O(1), но
безусловно выбор по ключу медленнее чем по номеру в
vector.
5.
Битовые наборы позволяют эффективно работать с битами.
54

55.

Примеры применения контейнеров.
Задача. Найти N самых частых слов в тексте.
Задачу можно решить в 2 этапа:
1. Посчитать сколько раз каждое слово
встречалось в тексте и
2. Найти N наиболее частых.
55

56.

Примеры применения контейнеров.
typedef map<string, int> STR2INT;
Предположим, что все слова в верхнем регистре, т.е. “Hello” и
“HELLO” будут поступать как “HELLO”.
STR2INT m;
string s;
cin>>s;
//Объявили контейнер
//Читаем слово*
while (!cin.eof()){
//пока не конец
m[s]++; // вставить, если не было и увеличить счетчик
cin>>s;
//Читаем следующее слово
}
cout << m.size() << endl; //количество различных слов
56

57.

Примеры применения контейнеров
int N=16;
//подготовили множество пар <целое - строка>
typedef set<pair<int, string>> SET_OF_N_STR;
SET_OF_N_STR mostFriquent;
for (auto &p : m)
mostFriquent.insert(SET_OF_N_STR::value_type(p.second, p.first));
//Пары в set располагаются в порядке возрастания (меньшая впереди)
for (auto it = mostFriquent.end()-N; it != mostFriquent.end(); it++)
cout << it->second << "\t" << it->first << endl;
57

58.

Контрольные вопросы
1. Почему контейнеры называются абстрактными типами
данных?
2. Что такое последовательные и ассоциативные
контейнеры? Приведите примеры из STL.
3. Что такое итератор в STL?
4. Какие операции должны быть определены для
объектов, вставляемых в контейнеры STL?
5. Если в программе используется глобальный
контейнер, а в него помещается локальный объект, не
нарушится ли контейнер, когда локальный объект
будет разрушен? Почему?
6. Дайте рекомендации, для каких целей хорошо
использовать каждый из рассмотренных в лекции
контейнеров. (string, vector, list, set, map)
58

59.

На практике
Приступим к изучению Времени жизни
объектов.