5. Структурные типы данных Динамическая структура данных

5. Структурные типы данных
5.1. Написать структурный тип данных Complex, представляющий комплексное число. Реализуйте:
 функцию с двумя параметрами, возвращающую комплексное число Complex по
вещественной и мнимой части;
 операцию комплексного сопряжения;
 функцию, печатающую комплексное число (в стандартном виде, т.е. вещественная часть +
мнимая часть i);
 перегрузите арифметические операторы;
 перегрузите операторы сравнения, если порядок комплексных чисел определяется
следующим образом: x1 + iy1 ≤ x2 + iy2, если либо x1 < x2, либо x1 = x2 и y1 ≤ y2.
В основной программе проверьте работу арифметических операторов и операции комплексного
сопряжения. Создайте массив комплексных чисел. Заполните массив случайными значениями
(вещественные и мнимые части должны лежать в промежутке *-100;100+), отсортируйте данный
массив. Для сортировки используйте любую шаблонную функцию, реализованную в задачах 4.1 –
4.4. Выведите отсортированный массив на экран.
Динамическая структура данных стек
5.2. Пользователь вводит строку, символами которой могут быть скобки вида “(“, “)”, “*“, “+” и “,“, “-”.
Будем назвать последовательность скобок правильной, если она получена по таким правилам:
 пустая последовательность правильная;
 если А и В правильные последовательности, то АВ тоже правильна;
 если А правильна, то *A], (A) и {A} тоже правильны.
Реализовать структуру данных стек и функции pop (взять элемент из стека), push (добавить
элемент в стек) и clean (очистить стек) для работы с ним. С помощью стека определить, является
ли введенная пользователем последовательность скобок правильной.
Пример входных данных
{()[({})()]}
([})
{[]})
Пример выходных данных
correct
not correct
not correct
5.3. Напишите программу expr, интерпретирующую обратную польскую запись выражения, задаваемого командной строкой, в которой каждый оператор и операнд представлены отдельным
аргументом. Для решения задачи реализуйте и используйте структуру данных стек.
Пример входных данных
expr.exe 2 3 4 + *
expr.exe 9 15 + 2 3 * /
Пример выходных данных
14
4
Введение в классы
5.4. Создайте класс who с закрытым полем char ch. Конструктор who должен иметь один
символьный аргумент, который будет использоваться для идентификации объекта через поле ch.
При создании объекта конструктор должен выводить на экран сообщение:
Creating object who <ch>,
где <ch> - это значение поля ch.
При удалении объекта на экран должно выводиться сообщение: Deleting object who <ch>.
a) Создайте функцию (не член класса) make_who(), которая возвращает объект who.
Создайте три пустые функции (тоже не члены класса) f_value, f_address и
f_pointer, которым передается объект типа who по значению, по ссылке и по
указателю соответственно. В основной программе создайте четыре объекта класса who,
первые три задайте через конструктор, четвертый – через вызов функции make_who().
Присвойте каждому объекту уникальное имя. Для первых трех объектов вызовите
функции f_value, f_address и f_pointer соответственно. Проанализируйте
выводимый на экран результат!
b) Для класса who добавьте открытый метод get_ch(), возвращающий значение ch.
Создайте массив из 10 элементов типа who и инициализируйте его значениями от A до J
(то есть поле ch первого элемента массива должно быть равным A, второго элемента – В
и так далее). Покажите, что массив на самом деле содержит эти значения.
5.5. Реализуйте класс Polynomial, хранящий многочлены степени не выше Max (Max – целочисленная глобальная константа). Массив коэффициентов многочлена должен быть закрытым
полем класса. Класс должен содержать конструктор (по умолчанию коэффициенты полинома
должны быть равны 0), открытый метод value, вычисляющий значение многочлена в точке,
передаваемой в качестве параметра, открытый метод set_coef, принимающий в качестве
параметров степень и значение коэффициента и устанавливающий этот коэффициент при
указанной степени. Для класса должны быть перегружены операторы, вычисляющие сумму,
разность и произведение (члены степени выше Max игнорируются) двух многочленов. В основной
программе проверить правильность работы всех описанных методов и операторов.
Реализация очереди с помощью массива
5.6. Реализуйте структуру данных очередь, хранящую числа типа int, на основе массива.
Определите глобальную константу Max, которая будет задавать максимальный размер очереди.
Создайте класс Queue; опишите массив, хранящий элементы очереди, и индексы начала (first)
и следующего свободного элемента (next) как закрытые члены класса. Реализуйте конструктор
по умолчанию и следующие методы для работы с очередью:
 bool empty() – метод, возвращающий true, если очередь пуста, и false в противном
случае;
 bool full() – метод, возвращающий true, если очередь целиком заполнена, и false в
противном случае;
 int size() – метод возвращающий размер очереди;
 int front() – метод, возвращающий значение первого элемента очереди;
 void push(int x) – метод, добавляющий элемент x в конец очереди;
 void pop() – метод, удаляющий элемент из начала очереди.
С помощью реализованной очереди решите следующую задачу. Пользователь вводит два целых
положительных числа n и m (n, m < 150). Требуется симулировать игру “Hot Potato” со
следующими правилами. Все n игроков нумеруются числами от 1 до n и в соответствии со своими
номерами становятся в круг по часовой стрелке. Далее, начиная с 1-го игрока, по часовой стрелке
они начинают вести счет, и каждый m-ый игрок выбывает из круга. Побеждает тот, кто остается
последним. Выведите на экран номера игроков в порядке их выбывания из круга.
Пример входных данных
Пример выходных данных
10 3
3 6 9 2 7 1 8 5 10 4
4 4
4 1 3 2
Параметры по умолчанию, операторы инкремента и декремента,
дружественные функции
Параметры по умолчанию
Аргумент по умолчанию позволяет присвоить параметру значение по умолчанию, если при
вызове функции соответствующий аргумент не задан. Применение аргумента по умолчанию
является скрытой формой перегрузки функции.
Чтобы передать параметру аргумент по умолчанию, нужно в инструкции определения функции
приравнять параметр тому значению, которое вы хотите передать, когда при вызове функции
соответствующий аргумент не будет указан. В следующей функции двум параметрам по
умолчанию присваиваются значения 0 и 1 соответственно.
void f(int a = 0, double b = 1.0);
Таким образом, все следующие вызовы функции f() правильны:
f(); // а по умолчанию равно 0, b равно
f(3); // a = 3, b по умолчанию равно 1
f(1, 2); // a = 1, b = 2
1
Все параметры, задаваемые по умолчанию, должны указываться правее параметров, передаваемых обычным путём. Аргументы по умолчанию должны указываться только один раз: либо в
прототипе функции, либо в её определении, если определение предшествует первому использованию функции. Аргументы по умолчанию нельзя задавать одновременно в определении и в
прототипе функции.
Передавать конструкторам аргументы по умолчанию тоже возможно. Конструктор
перегружается для того, чтобы могли создаваться как инициализируемые, так и
неинициализируемые объекты. Во многих случаях можно избежать перегрузки конструктора
путем передачи ему одного или более аргументов по умолчанию.
Перегрузка операторов
Для перегрузки оператора создается оператор-функция (operator function). Чаще всего, операторфункция является членом класса или дружественной классу, для которого определена. Основная
форма оператор-функции – члена класса следующая:
возвращаемый_тип class_name::operator#(список_аргументов) {…},
где class_name это имя класса, а вместо # нужно подставить перегружаемый оператор.
Например, бинарный оператор (функция от двух параметров, параметрами которой являются
левый и правый операнды) можно перегрузить следующим образом:
class_name operator+(const class_name &a, const class_name &b) {...}
Оператор можно также задать как функцию-член класса:
class_name operator+(const class_name &b) {...}
В таком случае первым операндом будет являться объект данного класса, для которого
вызывается оператор +, а b будет вторым операндом.
Унарный оператор (функция от одного параметра) можно перегрузить так:
class_name operator++(const class_name &a) {...}
Как метод класса:
class_name operator++() {...}
Перегрузка оператора сравнения:
bool operator<=(const class_name &a, const class_name &b) {...}
Как метод класса:
bool operator<=(const class_name &b) {...}
Большинство операторов С++ можно перегружать, ниже представлены те несколько операторов,
которые перегружать нельзя:
.
::
.*
?
Дружественные функции
Чтобы получить доступ к закрытым членам класса из функций (или операторов), не являющихся
членами этого класса, используются дружественные функции. Дружественная функция не
является членом класса, однако она имеет доступ к его закрытым элементам. Дружественная
функция задается как обычная, не являющаяся членом класса, функция. Но в объявлении класса,
для которого функция будет дружественной, необходимо включить её прототип, перед которым
ставится ключевое слово friend.
Функция может быть членом одного класса и дружественной другому. В таком случае при
включении прототипа функции-члена первого класса во второй следует после типа функции
указывать имя первого класса и оператор расширения:
class A {
public:
void func();
};
class B {
public:
friend void A::func();
};
Перегрузка операторов инкремента и декремента
Для того, чтобы различать, какая именно версия оператора ++ перегружается, используются
разные прототипы операторов. Для определения префиксной версии (++a) оператор
описывается как обычный унарный оператор:
Double operator++(Double& obj) {
//...
}
Для задания постфиксной версии (a++) к параметрам функции добавляется переменная типа int
Double operator++(Double& obj, int notused) {
//...
}
При вызове оператора переменной notused будет передаваться значение 0.
Как и прежде, если операторы инкремента или декремента задаются как функции-члены класса,
то в качестве первого операнда используется сам объект, и при перегрузки операторов задавать
параметр Double &obj не надо.
5.7. Создайте класс Int с закрытым(!) полем int num. По умолчанию num равен 0, объект класса
Int также можно инициализировать с помощью целого числа или с помощью строки, которая
должна быть преобразована в число. При этом строка может описывать число в любой системе
счисления base (2 ≤ base ≤ 20), по умолчанию base = 10, значение base должно
передаваться вторым параметром в конструктор Int. Таким образом, необходимо описать
только два конструктора, используя параметры по умолчанию. Реализуйте метод print(),
печатающий значение поля num. Проверьте работу конструкторов в основной программе.
Для класса Int перегрузите унарный и бинарный оператор -, постфиксный и префиксный
операторы -- и проверьте их работу в основной программе.
Создайте класс Double с закрытым(!) полем double num. Определите конструктор по
умолчанию и по числу типа double. Перегрузите оператор % как функцию-член класса Double.
Первым операндом оператора % является объект класса Double, а вторым операндом может
быть целое число или объект класса Int, оператор % должен возвращать остаток (типа Double)
от деления числа с плавающей точкой на целое число. При этом знак остатка должен совпадать
со знаком первого операнда, то есть 12.34%5 = 2.34, а -12.34%5 = -2.34.
Для класса Double реализуйте метод print(), печатающий значение поля num. Проверьте
работу оператора % в основной программе.
Конструктор копирования, оператор присваивания и перегрузка оператора []
Конструктор копии
Когда объект передается в функцию по значению, делается поразрядная (т.е. точная) копия этого
объекта и передается тому параметру функции, который получает объект. Но бывают ситуации, в
которых такая точная копия объекта нежелательна. Например, если объект содержит указатель
на выделенную область памяти, то в копии указатель будет ссылаться на ту же самую область
памяти, на которую ссылается исходный указатель. Следовательно, если копия меняет
содержимое области памяти, то эти изменения коснутся также и исходного объекта! Кроме того,
когда выполнение функции завершается, копия удаляется, что приводит к вызову деструктора
этой копии. Вызов деструктора может привести к нежелательным побочным эффектам, которые
в дальнейшем повлияют на исходный объект. Похожая ситуация имеет место, когда объект
является возвращаемым значением функции.
Контролировать процесс образования копии объекта можно с помощью конструктора копии (его
также называют конструктором копирования).
Важно различать ситуации, в которых значение одного объекта передается другому. Первая
ситуация – это присваивание. Вторая – инициализация, которая имеет место в трех случаях:



когда в инструкции объявления объекта один объект используется для инициализации
другого;
когда объект передается в функцию в качестве параметра по значению;
когда в качестве возвращаемого значения функции создается временный объект.
Конструктор копий употребляется только для инициализации, но никак не влияет на операции
присваивания! Конструктор копий задается следующим образом:
имя_класса (const имя_класса &obj) {
// тело конструктора
}
Где obj – это ссылка на объект, предназначенный для инициализации другого объекта.
Присваивание объектов
Если тип двух объектов одинаков, то один объект можно присвоить другому. По умолчанию,
когда один объект присваивается другому, делается поразрядная копия всех данных-членов
копируемого объекта. Это относится и к сложным данным, таким как массив. Однако если одним
из полей объекта является указатель, для которого в конструкторе или при вызове какого-либо
метода класса выделяется память, то при присваивании двух объектов скопируются только
указатели, при этом область памяти, на которую они указывают, не копируется.
Для того чтобы контролировать копирование данных объекта при присваивании, надо перегрузить оператор присваивания. Чтобы оператор присваивания не создавал лишних объектов и
работал для любого способа вызова оператора= (например, двойное присваивание a=b=c;), его
перегружают таким образом, чтобы он возвращал по ссылке объект, генерирующий вызов.
Например, для упоминавшегося класса Int перегрузка оператора присваивания будет выглядеть
следующим образом:
Int &operator=(const Int &b) {
num = b.num;
return *this;
}
Обратите внимание, что в некоторых ситуациях случай равенства обоих операндов оператора =
(при вызове a = a;) следует рассматривать отдельно.
Для перегрузки оператора присваивания нельзя использовать дружественную функцию.
Оператор присваивания можно перегружать только как оператор-функцию – член класса.
Перегрузка оператора [] – обращения к массиву по индексу
В С++ при перегрузке оператор [] рассматривается как бинарный, его можно перегружать только
как функцию-член класса. Основная форма оператора-функции – члена класса operator[]():
тип имя_класса::operator[](int индекс) {…}
При этом тип параметра не обязательно должен быть целым. Чтобы перегрузить функцию
operator[]() так, чтобы в инструкции присваивания оператор [] можно было располагать как
слева, так и справа от оператора=, следует возвращать ссылку на индексируемый элемент.
Правило трех
Большой тройкой в С++ называются особые методы класса:



Деструктор
Конструктор копирования
Оператор присваивания
Эти методы являются особыми членами-функциями, автоматически создаваемыми компилятором в случае отсутствия их явного объявления в классе.
Правило трех (или Закон большой тройки) утверждает, что если при реализации класса один из
методов большой тройки определен программистом, то это значит, что явным образом должны
быть определены и остальные два метода.
5.8. В условиях задачи 5.4 определите для класса who конструктор копирования, при вызове которого
на экран должна выводится строка «Сopying object who <x>», и оператор=, при вызове
которого на экран должна выводиться строка «Assignment of object who <x>». Код
функции main оставьте тем же, что был описан в пункте a) задачи 5.4. Что будет выведено на
экран? Объясните.
Шаблонные классы
В С++ возможно создание шаблонных классов, что позволяет определять классы без привязки к
конкретным типам данных. Как и для функций, описание шаблонного класса начинается со
слова template, после которого идут угловые скобки < >, в которых перечисляется список
параметров шаблона. Каждому параметру должно предшествовать зарезервированное
слово class или typename. Например:
template <class T1, class T2>
class Pair {
public:
Pair(T1 first_, T2 second_);
T1 get_first();
T2 get_second();
private:
T1 first;
T2 second;
};
При определении методов класса необходимо объявлять шаблон, точно такой же, как и перед
классом, и далее использовать бинарный оператор разрешения области действия ”::” с именем
шаблона класса - Pair<T1, T2>::
template <class T1, class T2>
Pair<T1, T2>::Pair(T1 first_, T2 second_) {
first = first_; second = second_;
}
template <class T1, class T2>
T1 Pair<T1, T2>::get_first() {
return first;
}
При объявлении объекта шаблонного класса в угловых скобках необходимо явно указывать
используемые типы данных:
int main()
{
Pair<double, bool> p(12.34, false);
cout << p.get_first() << endl;
//...
Обратите внимание, что если вы хотите поместить описание шаблонного класса в отдельный
заголовочный файл, то и его реализация должна полностью содержаться в том же файле.
5.9. Создайте шаблонный класс Array, который должен осуществлять автоматический контроль
границ массива (не давать читать и записывать данные в несуществующие ячейки массива). В
данном классе будет два закрытых поля: размер массива int size и указатель T *p.
Определите следующие методы
 конструктор по умолчанию;
 конструктор по целому числу, задающему размер массива, при этом по указателю p должна
быть выделена память для хранения массива указанного размера;
 деструктор;
 конструктор копирования;
 оператор присваивания;
 метод get_size(), возвращающий длину массива.
 оператор[], возвращающий ссылку на индексируемый элемент типа Т, при этом
необходимо осуществлять контроль границ массива: при попытке записи или чтения
элемента за границами массива программа должна завершаться с ошибкой (используйте
функцию exit(..) с параметром EXIT_FAILURE).
В функции main создайте объект x класса Array<int> длины 10. Заполните массив x случайными целыми числами. Выведите массив на экран. Создайте объект y того же типа и инициализируйте его через объект x (Array<int> y = x;). Выведите массив y на экран. Создайте объект
z того же типа, но размера 5, заполните его нулями. Присвойте объекту z объект y (z = y;).
Выведите массив z на экран. Присвойте объект x самому себе (х = х;), выведите массив х на
экран.
Динамическая структура данных двусвязный список
5.10. Определите класс List, описывающий двусвязный список, хранящий числа типа int. Внутри
класса List в разделе private определите структуру Element, описывающую элемент
двусвязного списка. У элемента списка будет три поля: данные int data, указатель на следующий элемент Element *next и указатель на предыдущий элемент Element *prev. У класса
List будет три закрытых поля: размер int size, Element *head (указатель на начало
списка) и Element *tail (указатель на конец списка). Определите для списка следующие
методы:
 конструктор по умолчанию;
 void push_front(const int &x) – метод, добавляющий элемент x в начало
списка;
 void push_back(const int &x) – метод, добавляющий элемент х в конец списка;
 void pop_front() – метод, удаляющий элемент из начала списка;
 void pop_back() – метод, удаляющий элемент из конца списка;
 int &front() – метод, возвращающий ссылку на элемент, хранящийся в начале списка;
 int &back() – метод, возвращающий ссылку на элемент, хранящийся в конце списка;
 bool empty() – метод, возвращающий true, если список пуст;
 int size() – метод, возвращающий длину списка;
 void reverse() – метод, переворачивающий список так, что начало списка становится
его концом, а конец – началом;
 void clear() – метод, очищающий список;
 деструктор;
 запретите использование конструктора копирования и оператора присваивания, описав их
как “пустые” private методы класса List.
С помощью структуры данных List решите следующую задачу. Пользователь вводит последовательность целых чисел <a1 , a2 , . . . , a2n, 0>, оканчивающуюся нулем. 0 < |ai| ≤ 30000 при 1 ≤ i ≤ n,
n ≥ 2 и значение n заранее неизвестно. Вычислите a1 a2n + a2 a2n-1 + . . . + an an+1 .
Пример входных данных
Пример выходных данных
1 2 3 4 5 6 0
28
-10 11 -2 1 3 -3 1 2 0
0
Перегрузка операторов cin >> и cout <<
Система ввода/вывода С++ действует через потоки (streams). Поток ввода/вывода – это
логическое устройство, которое выдает и принимает пользовательскую информацию. Поток
связан с физическим устройством с помощью системы ввода/вывода. Поскольку все потоки
ввода/вывода действуют одинаково, система ввода/вывода предоставляет единый удобный
интерфейс для работы с совершенно разными устройствами. Например, функция, которая
используется для записи информации на экран монитора, вполне подойдёт как для записи в
файл, так и для вывода на принтер.
Частью стандартной библиотеки C++ является библиотека iostream – объектно-ориентированная
иерархия классов, в которой реализована поддержка ввода/вывода данных встроенных типов. И
эту библиотеку можно расширять для чтения и записи новых типов данных.
Операции ввода/вывода выполняются с помощью классов istream (потоковый ввод) и ostream
(потоковый вывод). В библиотеке iostream определены четыре стандартных объекта-потока,
рассмотрим два из них

cin – объект класса istream, ассоциированный со стандартным вводом;

cout – объект класса ostream, соответствующий стандартному выводу.
По умолчанию стандартные потоки С++ привязаны к консоли, но программа может перенаправить их на другие устройства или файлы.
Вывод осуществляется, как правило, с помощью перегруженного оператора сдвига влево (<<), а
ввод – с помощью оператора сдвига вправо (>>). То есть при выполнении
int a;
cout << a;
вызывается перегруженный бинарный оператор << для класса ostream и типа int. Очевидно,
оператор можно перегрузить и для вывода нестандартных типов. Основная форма
пользовательских (то есть перегружаемых) функций вывода следующая:
ostream &operator<<(ostream &stram, имя_класса объект) {
...
return stream;
}
Первый параметр - это ссылка на объект типа ostream, это означает, что поток stream должен
быть потоком вывода. Второй параметр получает вводимый объект (может быть и параметромссылкой). Функция вывода возвращает ссылку на поток stream, это необходимо, если
перегруженный оператор << должен использоваться в ряде последовательных выражений
вывода:
cout << a << b << c;
Внутри пользовательской функции вывода можно выполнять любые операции, но в соответствии
с хорошим стилем лучше ограничиться только вставкой информации в поток. Пользовательская
функция вывода не может быть функцией-членом класса.
Основная форма пользовательской функции ввода следующая:
istream &operator>>(istream &stream, имя_класса &объект);
{
…
return stream;
}
Обратите внимание, что второй параметр - это всегда ссылка на объект, получающий вводимую
информацию. Пользовательская функция ввода также не может быть функцией-членом класса.
Ниже приведен пример перегрузки операторов ввода и вывода для класса point, описывающего
точку на плоскости:
#include <iostream>
using namespace std;
class point {
public:
point(int a = 0, int b = 0) : x(a), y(b) {}
friend ostream &operator<<(ostream &stream, const point &p);
friend istream &operator>>(istream &stream, point &p);
private:
int x, y;
};
ostream &operator<<(ostream &stream, const point &p) {
// в поток stream вставляются символы “(“, ”,”, ”)” и значения p.x и p.y
stream << "(" << p.x << ", " << p.y << ")";
// этот же поток возвращается из функции
return stream;
}
istream &operator>>(istream &stream, point &p) {
stream >> p.x >> p.y;
return stream;
}
int main() {
point p1(7, 8), p2(-5);
cout << p1 << " " << p2 << endl;
cout << "Enter x and y coordinates:\n";
cin >> p1;
cout << p1;
return 0;
}
В результате будет выведено следующее:
(7, 8) (-5, 0)
Enter x and y coordinates:
1 2
(1, 2)
// - числа, введенные пользователем
Реализация контейнера строка
5.11. Реализуйте контейнер String для работы со строками. При этом описание интерфейса
(описание полей и методов) класса String должно содержаться в файле string.h, а вся
реализация – в файле string.cpp, функция main – в файле main.cpp. В классе String
опишите три закрытых поля:
 char *my_str – указатель на блок памяти, хранящий строку;
 int my_size – размер строки, то есть символы, непосредственно входящие в строку;
 int my_capacity –
емкость блока памяти, содержащего символы строки
(поскольку строка всегда завершается символом конца строки ‘\0’, то
my_capacity ≥ my_size + 1).
При добавлении или удалении символов из строки должно осуществляться автоматическое
наращивание памяти в соответствии с объемом внесенных данных по следующим правилам.
 Значение my_capacity никогда не может быть меньше MinCapacity (где
MinCapacity – это постоянная глобальная переменная, чье значение равно 4).
 Если при добавлении n новых элементов в строку получается, что
my_capacity ≤ my_size + n + 1,
то должно происходить увеличение блока памяти, при этом должен выделяться новый
блок размера 2k· my_capacity, где k – это наименьшее число, для которого
2k· my_capacity ≥ my_size + n + 1,
данные из старого блока и добавляемые элементы копируются в новый блок памяти,
после чего старый блок удаляется.
 Если при удалении n элементов из строки получается, что
my_capacity ≥ 2(my_size – n + 1),
то должно происходить уменьшение блока памяти, при этом должен выделяться новый
блок размера my_capacity /2k, где k – это наибольшее число, для которого
my_capacity /2k ≥ max(my_size – n + 1, MinCapacity),
данные из старого блока, за исключением удаляемых элементов, копируются в новый
блок памяти, после чего старый блок удаляется.
Для класса String реализуйте следующие методы:
 конструктор по умолчанию (my_size = 0, но my_capacity = MinCapacity);
 String(const char *str) – конструктор по строке в стиле С, при этом память
выделяется по описанным выше правилам, считая, что к пустой строке добавляется
strlen(str) символов.








деструктор, конструктор копирования, оператор присваивания;
int size() – метод, возвращающий длину строки;
int capacity() – метод, возвращающий емкость блока памяти;
bool emty() – метод, возвращающий true, если строка пуста;
void clear() – метод, удаляющий все символы из строки, то есть строка становится
пустой;
void push_back(char c) – метод, добавляющий символ в конец строки;
void pop_back() – метод, удаляющий символ из конца строки;
void insert(int pos, const char *str) – метод, вставляющий все символы
строки str в текущую строку перед символом с индексом pos;

void erase(int pos, int len = 1) – метод, удаляющий из строки len
символов, начиная с индекса pos.
 оператор + конкатенации двух строк;
 оператор +=, при выполнении которого к строке, переданной первым операндом,
присоединяется строка, переданная вторым операндом.
 оператор [];
 оператор вывода <<;
 перегрузите оператор ввода >> в предположении, что пользователь не вводит строки
длиннее 100 символов.
В функции main проверьте работу всех описанных методов и операторов. Используя методы
insert, erase, size, capacity, проверьте, что уменьшение/увеличение объема памяти
происходит в соответствии с описанными правилами.
Теоретическая задача: пусть сначала создается пустая строка типа String. Далее последовательно с помощью метода push_back в строку добавляются n символов. Подумайте, какова будет
трудоемкость метода push_back для каждого из добавляемых элементов. Например, добавлеk
k+1
ние первых трех элементов стоит O(1), добавление 2 -го элемента стоит O(2 ). Рассчитайте
“среднее” время работы метода push_back: просуммируйте стоимости добавления элементов
для всех i = 1..n, разделите эту сумму на n. Ответ напишите в комментарии к методу push_back.
Итераторы
5.12. В файле iterator.cpp приведен пример неполной реализации очереди с итератором. Руководствуясь этим примером, реализуйте итератор для класса List (см. задачу 5.10). Кроме того,
должна быть возможность не только увеличивать (оператор++), но и уменьшать (оператор--)
итератор.
В основной программе заполните список случайными числами, попеременно используя методы
push_front() и push_back(). Используя итератор, выведите элементы списка на экран.
Удалите половину элементов из списка, используя методы pop_front() и pop_back().
Выведите количество оставшихся элементов на экран. Используя итераторы, выведите элементы
в порядке, обратном прядку их хранения в списке, найдите максимальный элемент в списке и
выведите его значение на экран.
К классу List добавьте два метода:
 iterator insert(iterator position, const int &x) – метод, вставляющий
новый элемент x в список перед элементом, на который указывает position, и
возвращающий итератор, который указывает на только что добавленный элемент.
 iterator erase(iterator position) – метод, удаляющий из списка элемент, на
который указывает position, и возвращающий итератор, который указывает на
следующий (за удаленным) элемент списка.
В основной программе, используя метод insert, перед каждым четным элементом списка
добавьте в список элемент, на единицу меньший данного. Выведите список на экран. Используя
метод erase, удалите из списка все элементы, кратные трем. Выведите список на экран.