Cpp3sort

1.

Практика Инф Тех
Стандартные Классы С++ коллекции
• Структура проекта
• Командой DIR
• В папку проекта переходите
командой CD
• Находите в папке Debug\..EXE
• Приводите в отчете только
нужные файлы из DIR текстом
• EXE приводите полным
именем (папки+exe) в отчете

2. Динамические массивы С++

• Динамический массив экономит память, автоматический еще и
освобождает ресурсы по окончании использования
• Шаблон классов динамических массивов std::vector <T>, где Т – тип
данных которые хранит массив.
• библиотеку нужно подключать заголовками, как обычно:
#include <vector>
• В языке С++ шаблон - это возможность описать действия над
неопределенным типом данных, а компилятор сам допишет нужный
код с учетом конкретного типа данных, который передается в шаблон
как параметр. Шаблон использует для определения типа синтаксис
угловых скобок <T>
• Вектор назван так, поскольку представляет собой одномерный массив.
Вектор векторов масштабирует функционал в два измерения

3. Вектор, конструкторы, полиморфизм

• Конструктор без параметров – создает объекта этого типа в коде
• vector<CMyPhRec> phBook; - без параметров вводится
переменная и компилятором вызывается конструктор без
параметров, то есть phBook - пустой массив, длинной 0;
• vector<int> vecInt(vecIntOther); - копирующий вводится переменная и компилятором записывается вектор
копией другого вектора, можно не целиком а в диапазоне;
• vector<int> vecInt(100, 1); - заполняющий конструктор вводится переменная и компилятором заполняется
единицами массив;
• Когда переменная выходит из области видимости память вектора
освобождается автоматически

4. Векторы и функции-операторы

• Векторы поддерживают функции, которые синтаксически
тождественны операциям
• vector<int> A,B(5,1); два объекта и A=B; - вызывает ОПЕРАТОР
‘=‘ класса vector , этот оператор – такая же функция – элемент
класса как и прочие, но имя у него – оператор знак равенства
operator=(const vector<int> &src). Похоже на присваивание в С.
Будет скопировано содержимое B в A
• Есть оператор «[]» и B [0] конечно будет числом 1, т.е. наши
привычные действия с вектором, как с массивом, работают через
эту функцию-оператор
• Важнейшая функция – добавление в вектор нового значения, и
можно добавлять в хвост push_back( значение ); и стирать из
хвоста pop_back( ); - размер вектора size() в первом случае
увеличится а во втором – уменьшится на 1

5. Векторы : функции и итераторы

Полезные функции
• vector::size() – возвращает количество элементов вектора
• vector::empty() – возвращает true для пустого вектора
• vector::clear() – удаляет все из вектора
• Для векторов и других классов коллекций определен класс
перебора элементов вектора, который называется итератором
vector<T>::iterator. Значение этого оператора – адрес
соответствующего элемента, то есть указатель на элемент с типом
T*
• У вектора есть итераторы начала vector::begin()который
указывает на первый элемент вектора и конца vector::end(),
который указывает за пределы вектора

6. Векторы : операторы цикла

• Простая аналогия с циклом перебора С:
for( int i = 0; i < phBook.size(); i++ )
CMyPhRec rc = phBook[i];
• То же с использованием итератора:
for( auto i = phBook.begin(); i != phBook.end(); i++ )
CMyPhRec rc = *i;
• У итератора есть тип, который длинно называется
std::vector<T>::iterator i в нашем тексте auto i – синоним из С++ 11, то
есть компилятор подставит автоматически этот длинный тип
переменной
• У итератора есть унарные операторы *, &, ++, и операторы сравнения
==, !=
• Использовать больше и меньше не рекомендуется, хотя данные в
массиве должны строго находится в непрерывной области памяти
чтобы арифметика указателей работала

7. Векторы : инкапсуляция и наследование

• В классе вектор хранятся данные, и функция data() предоставит
доступ к данным начиная с 1 элемента массива,
• Кроме того, очевидно в классе хранится длина вектора, но эта
переменная защищена ( вот для чего нужен protected) и доступна
нам через функцию size().
• Перечисленные операторы и функции работают с нашими
векторами объектов используя эти данные и переменные в коде
непосредственно, как с локальными переменными.
• У класса строк есть базовый класс vector и как видно из
излженного строки наследуют функции векторов.

8. Векторы: доступ к элементам

• Доступ к элементам класса vector<CMyPhRec> phBook
производится по имени переменной с индексом (эл-т есть):
• phBook[0].Number = 79219222222; – для компилятора в
переменную типа int64_t, которая расположена в начале памяти,
занятой переменной phBook[0] записать 79219222222. Адрес
этой переменной &( phBook[0].Number )
• Заполнить строку имени : phBook[0].Nik = “Peter”; - Доступ к
элементам класса, переданного итератором СMyPhRec * prec =
phBook.begin(); :
• phBook.begin() ->Number = 79219222222;
• phBook.push_back(СMyPhRec(7921,1,”ABC”)); сконструирует
объект из параметров в списке и запишет его в конец вектора
автоматически увеличив его размер

9. Сортировка методом парных перестановок («метод пузырька»)

• Для вывода телефонной книжки в алфавитном порядке нужно
упорядочить записи при выводе, так, чтобы имена абонентов
следовали по возрастанию ( ведь B > A).
1. Начинаем с самого низа нашего вектора: сравниваем i =
phBook.end()--; i-> Nik и i-- -> Nik; Это удобно
определить оператром bool operator< (const
CMyPhRec & other) в классе CMyPhRec
2. Если предыдущее имя больше следующего, то сразу меняем эту
запись со предыдущей местами (swap).
3. Повторяем 1 -2 начиная с предыдущего элемента и так не
доходя на 1 позицию до начала массива.
4. После 1-3 утверждается, что самое верхнее по алфавиту имя
находится в начале массива и его больше проверять не нужно.

10. Сортировка методом «пузырька» 2

• Повторяем 1-3 для нижних N-2 элементов, потом для N-3…пока не
останется один элемент, у которого нет пары, и он остается на месте
• Важно: если при каком-либо проходе не было ни одной перестановки,
то массив УЖЕ ОТСОРТИРОВАН. Останавливаем цикл 1-3.
• Меняем две записи в массиве местами (swap), используя временную
переменную так (метод трех стаканов):
1. Заводим временную переменную с типом записи Temp
2. Копируем в Temp содержимое первого неупорядоченного элемента
3. Копируем в первый неупорядоченный элемент найденный нами
наименьший из оставшихся
4. На место наименьшего копируем Temp

11. Выравнивание в таблице при выводе

• Вывести записи с выравниванием в таблице можно так:
• По списку имен находим наибольшую длину имени MaxLength
• MaxLength += 1 – получаем отступ для начала телефонных
номеров
• Имена, которые короче дополняем пробелами до максимума
• Nik += std::string( MaxLength - Nik.size(), ‘ ‘) – конструктор строки
из N символов пригодился! Иначе пришлось бы в цикле
дописывать
• Выводим телефонную книгу построчно в цикле последовательно
в std::cout << PhBook[i].Nik << ( PhBook[i].Plus ? “+” : “ “) <<
PhBook[i]. PhoneNo << endl;

12. Лаб раб 6

1. С использованием двух классов создать консольное
приложение для записи телефонной книжки
2. Ввод записей осуществлять пока не будет введен телефонный
номер 0
3. Выводить записи телефонной книжки в таблицу в алфавитном
порядке, сортировка методом «пузырька»:
• Порядковый номер
• Ник
• Телефон
4. Таблицу выводить построчно.
5. Использовать библиотеку и общее с лаб 3, 4 и 5 решение

13. Полезные источники

• http://www.cplusplus.com/reference/vector/vector