4.7. Разбор задач к главе «Идиомы C++»

Вам надо написать класс Date для хранения даты григорианского календаря. Используйте три переменных типа int для хранения дня, месяца и года. В вашем классе должен быть следующий публичный интерфейс:

1. Конструктор, принимающий на вход три числа: день, месяц и год. В случае некорректной даты должна создаваться дата января года.

2. Константные функции GetDay, GetMonth и GetYear.

3. Бинарные операторы + и -, где вторым аргументом является целое число — количество дней. Эти операторы должны вернуть новую дату, отстоящую от заданной на указанное число дней.

4. Бинарный оператор -, вычисляющий разность между двумя датами и возвращающий int – количество дней.

Считайте, что все обрабатываемые даты будут лежать в пределах от января года до декабря года.

Примечания

Сдайте в систему только код класса Date без функции main.

Для начала запишем главное условие — «Используйте три переменных типа int для хранения дня, месяца и года», также определим константы.

const int DEFAULT_DATE_DAY = 1;
const int DEFAULT_DATE_MONTH = 1;
const int DEFAULT_DATE_YEAR = 1970;
const int DAYS_IN_YEAR_WITHOUT_FEB = 337;

class Date {
private:
    int d = DEFAULT_DATE_DAY, m = DEFAULT_DATE_MONTH, y = DEFAULT_DATE_YEAR;

    // Дальше реализуем вспомогательные функции-члены.
    // Нам нужно будет понимать високосный ли перед нами год, корректную ли дату ввели:
    int GetDaysInFeb(int year) const {
        if ((!(year % 4) && (year % 100)) || !(year % 400)) {
            return 29;
        }
        return 28;
    }

    int GetDaysInMonth(int month, int year) const {
        switch (month) {
            case 2:
                return GetDaysInFeb(year);
            case 1:
            case 3:
            case 5:
            case 7:
            case 8:
            case 10:
            case 12:
                return 31;
            default:
                return 30;
        }
    }

    int GetDaysInYear(int year) const {
        return DAYS_IN_YEAR_WITHOUT_FEB + GetDaysInFeb(year);
    }

    bool IsCorrectDate() const {
        return GetMonth() <= 12 && GetMonth() >= 1 && GetDay() <= GetDaysInMonth(GetMonth(), GetYear()) && GetDay() > 0;
    }

    // Помимо прочего будет полезно уметь переводить текущую дату в число — количество дней от 01.01.1970 и обратно.
    int DaysPassedToMonth(int month, int year) const {
        int days = 0;
        for (int i = 1; i < month; ++i) {
            days += GetDaysInMonth(i, year);
        }
        return days;
    }

    int GetDays() const {
        int days = 0;
        for (int i = DEFAULT_DATE_YEAR; i < GetYear(); ++i) {
            days += GetDaysInYear(i);
        }
        return days + DaysPassedToMonth(GetMonth(), GetYear()) + GetDay();
    }

    void SetFromDays(int inp_days) {
        m = DEFAULT_DATE_MONTH;
        y = DEFAULT_DATE_YEAR;

        while (inp_days > GetDaysInYear(GetYear())) {  // сначала определяем год
            inp_days -= GetDaysInYear(GetYear());
            ++y;
        }

        while (inp_days > DaysPassedToMonth(GetMonth() + 1, GetYear())) {  // определяем месяц
            ++m;
        }

        d = inp_days - DaysPassedToMonth(GetMonth(), GetYear());  // остаток в дни
    }

// Когда подготовительная часть закончена, реализуем публичный интерфейс:
public:
    Date(int day, int month, int year)
            : d{day}, m{month}, y{year} {
        if (!IsCorrectDate()) {
            d = DEFAULT_DATE_DAY;
            m = DEFAULT_DATE_MONTH;
            y = DEFAULT_DATE_YEAR;
        }
    }

    int GetDay() const {
        return d;
    }

    int GetMonth() const {
        return m;
    }

    int GetYear() const {
        return y;
    }

    Date operator + (int k) const {
        Date result(*this);
        result.SetFromDays(result.GetDays() + k);
        return result;
    }

    Date operator - (int k) const {
        Date result(*this);
        result.SetFromDays(result.GetDays() - k);
        return result;
    }

    int operator - (const Date& other) const {
        return GetDays() - other.GetDays();
    }
};

Вам надо переделать реализацию класса Date из предыдущей задачи, сохранив публичный интерфейс неизменным. Теперь для хранения даты используйте одну переменную типа int — количество дней, прошедших с некоторого начала отсчёта.

Считайте, что все обрабатываемые даты будут лежать в пределах от января года до декабря года.

Примечания

Сдайте в систему только код класса Date без функции main.

Изменим нашу реализацию из предыдущей задачи. Часть вспомогательных функций-членов не меняется:

#include <tuple>

const int DEFAULT_DATE_DAY = 1;
const int DEFAULT_DATE_MONTH = 1;
const int DEFAULT_DATE_YEAR = 1970;
const int DAYS_IN_YEAR_WITHOUT_FEB = 337;

class Date {
private:
    int days{0};

    int GetDaysInFeb(int year) const {
        if ((!(year % 4) && (year % 100)) || !(year % 400)) {
            return 29;
        }
        return 28;
    }

    int GetDaysInMonth(int month, int year) const {
        switch (month) {
            case 2:
                return GetDaysInFeb(year);
            case 1:
            case 3:
            case 5:
            case 7:
            case 8:
            case 10:
            case 12:
                return 31;
            default:
                return 30;
        }
    }

    int GetDaysInYear(int year) const {
        return DAYS_IN_YEAR_WITHOUT_FEB + GetDaysInFeb(year);
    }

    int DaysPassedToMonth(int month, int year) const {
        int result = 0;
        for (int i = 1; i < month; ++i) {
            result += GetDaysInMonth(i, year);
        }
        return result;
    }

    // Отредактируем перевод из даты в дни и обратно:
    void SetDays(int day, int month, int year) {
        days = 0;
        for (int i = DEFAULT_DATE_YEAR; i < year; ++i) {
            days += GetDaysInYear(i);
        }
        days = days + DaysPassedToMonth(month, year) + day;
    }

    std::tuple<int, int, int> ToDate() const {
        int inp_days = days;
        int month = DEFAULT_DATE_MONTH;
        int year = DEFAULT_DATE_YEAR;

        while (inp_days > GetDaysInYear(year)) {  // сначала определяем год
            inp_days -= GetDaysInYear(year);
            ++year;
        }

        while (inp_days > DaysPassedToMonth(month + 1, year)) {  // определяем месяц
            ++month;
        }

        int day = inp_days - DaysPassedToMonth(month, year);  // остаток в дни
        return {day, month, year};
    }

    void SetFromDays(int inp_days) {
        days = inp_days;
    }

    int GetDays() const {
        return days;
    }

// Осталось поменять публичные интерфейсы.
// Так как в них мы почти не завязывались на тип хранения,
//     правки будут только в функциях-членах чтения и конструкторе:
public:
    Date(int day, int month, int year) {
        if (month > 12 || month < 1 || day > GetDaysInMonth(month, year) || day < 1) {
            days = 0;
        } else {
            SetDays(day, month, year);
        }
    }

    int GetDay() const {
        return std::get<0>(ToDate());
    }

    int GetMonth() const {
        return std::get<1>(ToDate());
    }

    int GetYear() const {
        return std::get<2>(ToDate());
    }

    Date operator + (int k) const {
        Date result(*this);
        result.SetFromDays(result.GetDays() + k);
        return result;
    }

    Date operator - (int k) const {
        Date result(*this);
        result.SetFromDays(result.GetDays() - k);
        return result;
    }

    int operator - (const Date& other) const {
        return GetDays() - other.GetDays();
    }
};

Напишите класс Rational (рациональное число). Конструктор класса должен получать на вход два числа типа int (числитель и знаменатель). Считайте, что по умолчанию числитель равен 0, а знаменатель — 1.

Переопределите бинарные операторы сложения, вычитания, умножения и деления (работающие в том числе и с аргументами типа int), унарные плюс и минус. Предусмотрите функции-члены Numerator и Denominator для получения числителя и знаменателя несократимого представления этой дроби (знаменатель должен быть положительным). Переопределите также операторы +=, -=, *= и /=. Не забудьте определить операторы == и !=.

Примечания

Используйте функцию std::gcd стандартной библиотеки.

Одно и то же число может быть задано разными парами числитель/знаменатель (1/2, 2/4, 3/6, ...). Мы же будем хранить рацинальное число в виде несократимой дроби. Для этого нам потребуется функция std::gcd, которая появилась в C++17. Впрочем, можно написать самостоятельно её реализацию с помощью алгоритма Евклида:

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

Мы введём вспомогательную приватную функцию Reduce, которая будет сокращать дробь и гарантировать, что знаменатель неотрицателен. Эту функцию мы будем вызывать всякий раз, когда при вычислениях дробь могла стать сократимой.

#include <numeric>

class Rational {
private:
    int num;
    int denom;

    void Reduce() {
        int d = std::gcd(num, denom);
        num /= d;
        denom /= d;
        if (denom < 0) {
            num *= -1;
            denom *= -1;
        }
    }

public:
    Rational(int num_ = 0, int denom_ = 1) : num(num_), denom(denom_) {
        Reduce();
    }

    int Numerator() const {
        return num;
    }

    int Denominator() const {
        return denom;
    }

    // унарный плюс (формально ничего не меняет)
    Rational operator + () const {
        return {num, denom};
    }

    // унарный минус
    Rational operator - () const {
        return Rational(-num, denom);
    }

    // rhs - сокращение от right hand side (правый аргумент бинарного оператора)
    Rational& operator += (const Rational& rhs) {
        num = num * rhs.denom + rhs.num * denom;
        denom *= rhs.denom;
        Reduce();
        return *this;
    }

    Rational& operator -= (const Rational& rhs) {
        num = num * rhs.denom - rhs.num * denom;
        denom *= rhs.denom;
        Reduce();
        return *this;
    }

    Rational& operator *= (const Rational& rhs) {
        num *= rhs.num;
        denom *= rhs.denom;
        Reduce();
        return *this;
    }

    Rational& operator /= (const Rational& rhs) {
        // сохраняем старый числитель, чтобы корректно работало выражение q /= q.
        int tmp = rhs.num;
        num *= rhs.denom;
        denom *= tmp;
        Reduce();
        return *this;
    }
};

Rational operator + (const Rational& lhs, const Rational& rhs) {
    Rational result = lhs;
    result += rhs;
    return result;
}

Rational operator - (const Rational& lhs, const Rational& rhs) {
    Rational result = lhs;
    result -= rhs;
    return result;
}

Rational operator * (const Rational& lhs, const Rational& rhs) {
    Rational result = lhs;
    result *= rhs;
    return result;
}

Rational operator / (const Rational& lhs, const Rational& rhs) {
    Rational result = lhs;
    result /= rhs;
    return result;
}

bool operator == (const Rational& lhs, const Rational& rhs) {
    return lhs.Numerator() == rhs.Numerator() && lhs.Denominator() == rhs.Denominator();
}

bool operator != (const Rational& lhs, const Rational& rhs) {
    return !(lhs == rhs);
}

Вася пишет новую структуру данных — дерево. В узлах и листьях дерева хранятся строковые ключи. Каждый путь от корня до какого-нибудь узла можно записать, перечисляя последовательные ключи узлов. Типичный пример — иерархия папок в файловой системе. Вася уже выбрал способ хранения дерева:

#include <map>
#include <string>
#include <vector>

struct Node {
    std::map<std::string, Node> children;
};

class Tree {
private:
    Node root;

public:
    bool Has(const std::vector<std::string>& node) const;
    void Insert(const std::vector<std::string>& node);
    void Delete(const std::vector<std::string>& node);
};

// Ваш код будет вставлен сюда
#include "your_code"

Не будем обсуждать, насколько это эффективно.

Ваша задача — написать реализации функций Has, Insert и Delete для этого класса. В примере с папками в файловой системе функция Has должна проверить, существует ли такая папка, функция Insert должна создать папку (возможно, с промежуточными родительскими папками), а Delete — удалить папку со всеми вложенными подпапками, если такая папка существует.

Можно считать, что вектор, передаваемый на вход этих функций, всегда непустой.

Рассмотрим для начала функцию Has. Её структура должна выглядеть так:

bool Tree::Has(const std::vector<std::string>& node) const {
    // заводим переменную current, «смотрящую» на корень дерева
    for (const auto& item : node) {
        if (/* среди потомков current есть item */) {
            // заменить current на этого потомка
        } else {
            return false;
        }
    }
    return true;
}

Какого типа может быть current? Правильный ответ: это должен быть указатель на Node. При спуске по дереву его можно будет переназначать на вложенный узел:

bool Tree::Has(const std::vector<std::string>& node) const {
    const Node* current = &root;
    for (const auto& item : node) {
        if (!current->children.contains(item)) {
            return false;
        }
        current = &current->children.at(item);
    }
    return true;
}

Мы здесь используем const Node*, потому что функция Has константная, а значит, поле root тоже рассматривается как константное. По этой же причине мы пишем children.at(item), а не children[item]: оператор [] у map не является константным, и его не получится использовать. Вместо children.contains(item) можно было бы взять children.find(item) и сравнить полученный итератор с children.end().

Теперь напишем Insert:

void Tree::Insert(const std::vector<std::string>& node) {
    Node* current = &root;
    for (const auto& item : node) {
        if (!current->children.contains(item)) {
            current->children[item];  // просто вставляем новый ключ с пустым Node в качестве значения
        }
        current = &current->children.at(item);
    }
}

В функции Delete нам не нужно спускаться на самый последний узел: вместо этого его имя надо будет удалить из предпоследнего узла. Поэтому воспользуемся индексами для итерации по списку промежуточных узлов node:

void Tree::Delete(const std::vector<std::string>& node) {
    Node* current = &root;
    for (size_t i = 0; i < node.size(); ++i) {
        const auto& item = node[i];
        if (!current->children.contains(item)) {
            return;
        }
        if (i + 1 == node.size()) {
            current->children.erase(item);
        } else {
            current = &current->children.at(item);
        }
    }
}

Грубая ошибка в этой задаче — пытаться использовать Node current вместо указателя. Смотрите, вот такой Has на первый взгляд даже будет работать:

bool Tree::Has(const std::vector<std::string>& node) const {
    Node current = root;
    for (const auto& item : node) {
        if (!current.children.contains(item)) {
            return false;
        }
        current = current.children.at(item);
    }
    return true;
}

Однако можно заметить, что здесь на каждой итерации происходит полное копирование поддерева. В этом можно убедиться, если определить для struct Node конструктор копирования, печатающий сообщения на экран. Конечно же, при навигации по дереву никаких лишних копирований происходить не должно. Более того, из-за особенностей внутренней реализации std::map выражение current = current.children.at(item) приведет к неопределённому поведению программы (родительское дерево будет разрушено до обращения к поддереву).

Один студент решил написать класс для своей реализации игры «крестики-нолики». Игра ведётся на квадратном поле размера двумя игроками. Игроки должны составить крестиков или ноликов в ряд (по горизонтали, по вертикали или по диагонали).

Класс должен уметь создавать квадратное поле заданных размеров, выполнять очередной ход в пустую клетку, а также проверять, не наступил ли выигрыш. Кроме того, должен быть оператор <<, который печатает поле.

Студент пока не реализовал проверку выигрыша по диагоналям. А ещё его программа почему-то «падает» при попытке напечатать поле. Помогите ему исправить и сдать программу. Вот код студента:

#include <iostream>
#include <vector>

class TicTacToe {
public:
    const size_t N;  // размер игрового поля
    const size_t K;  // сколько фишек нужно поставить в ряд, чтобы выиграть

private:
    // 0 - пусто, 1 - фишка первого игрока (крестик), 2 - фишка второго игрока (нолик)
    std::vector<std::vector<int>> Table;

    // номер текущего игрока (1 или 2)
    int currentPlayer;

public:
    TicTacToe(size_t n, size_t k): N(n), K(k), currentPlayer(1) {
        Table.reserve(N);
        for (size_t i = 0; i != N; ++i) {
            Table[i].reserve(N);
        }
    }

    int operator()(size_t i, size_t j) const {
        return Table[i][j];
    }

    int GetCurrentPlayer() const {
        return currentPlayer;
    }

    bool Set(size_t i, size_t j) {  // возвращает true, если ход завершился выигрышем
        Table[i][j] = currentPlayer;
        currentPlayer = currentPlayer % 2 + 1;
        bool wins = CheckRow(i, j) || CheckColumn(i, j) || CheckDiagonal1(i, j) || CheckDiagonal2(i, j);
        return wins;
    }

private:
    bool CheckRow(size_t i, size_t j) const {
        size_t d1 = 0;
        while (d1 <= j && Table[i][j - d1] == Table[i][j]) {
            ++d1;
        }

        size_t d2 = 0;
        while (j + d2 < N && Table[i][j + d2] == Table[i][j]) {
            ++d2;
        }

        return d1 + d2 > K;
    }

    bool CheckColumn(size_t i, size_t j) const {
        size_t d1 = 0;
        while (d1 <= i && Table[i - d1][j] == Table[i][j]) {
            ++d1;
        }

        size_t d2 = 0;
        while (i + d2 < N && Table[i + d2][j] == Table[i][j]) {
            ++d2;
        }

        return d1 + d2 > K;
    }

    bool CheckDiagonal1(size_t i, size_t j) const;

    bool CheckDiagonal2(size_t i, size_t j) const;
};

    std::ostream& operator << (std::ostream& out, TicTacToe& field) {
    for (size_t i = 0; i != field.N; ++i) {
        for (size_t j = 0; j != field.N; ++j) {
            switch (field(i, j)) {
                case 0:
                    std::cout << '.';
                    break;
                case 1:
                    std::cout << 'X';
                    break;
                case 2:
                    std::cout << 'O';
            }
        }
        std::cout << "\n";
    }
    return out;
}

Примечания

Вам требуется сдать только исправленный (и дополненный для проверки выигрыша по диагоналям) код класса TicTacToe и оператора <<. Функции main в Вашем коде быть не должно. Ваша программа будет автоматически собрана с нашей функцией main примерно такого содержания:

#include <iostream>

#include "tic_tac_toe.correct.h"  // это ваше решение

int main() {
    size_t n, m;
    std::cin >> n >> m;
    TicTacToe game(n, m);
    size_t x, y;
    while (std::cin >> x >> y) {
        int curPlayer = game.GetCurrentPlayer();
        if (game.Set(x, y)) {
            std::cout << "Player #" << curPlayer << " wins!\n";
        }
    }
    std::cout << game;
}

Прежде всего заметим, что неверно написан конструктор. В нём лишь резервируется память для вектора, но не меняется его размер. Перепишем его так:

TicTacToe(size_t n, size_t k): N(n), K(k), currentPlayer(1) {
    Table.resize(N);
    for (size_t i = 0; i != N; ++i) {
        Table[i].resize(N);
    }
}

Во-вторых, в операторе << есть две ошибки: ответ печатается в std::cout вместо out, и второй аргумент принимается по обычной, а не по константной ссылке.

Наконец, нам нужно реализовать функции CheckDiagonal1 и CheckDiagonal2. Вопреки заблуждению некоторых студентов, видимо, много решавших задачи про матрицы, диагональ тут (как в самых обычных крестиках-ноликах) может быть любая, а не только главная или побочная. Рассмотрим, как сделана, например, аналогичная функция CheckRow, проверяющая, образуется ли K подряд идущих фишек по горизонтали после хода в указанную позицию:

bool CheckRow(size_t i, size_t j) const {
    size_t d1 = 0;
    while (d1 <= j && Table[i][j - d1] == Table[i][j]) {  // считаем, сколько слева от нас таких же фишек
        ++d1;
    }

    size_t d2 = 0;
    while (j + d2 < N && Table[i][j + d2] == Table[i][j]) { // считаем, сколько справа от нас таких же фишек
        ++d2;
    }

    return d1 + d2 > K;  // всего мы насчитали d1 + 1 + d2 фишек вместе с текущей, это число должно быть не меньше K
}

Тут важно проверять корректности индексов: они должны быть неотрицательны и меньше N. Напишем по аналогии проверку наличия диагональных выигрышных позиций:

bool CheckDiagonal1(size_t i, size_t j) const {
    size_t d1 = 0;
    while (d1 <= i && d1 <= j && Table[i - d1][j - d1] == Table[i][j]) {
        ++d1;
    }

    size_t d2 = 0;
    while (i + d2 < N && j + d2 < N && Table[i + d2][j + d2] == Table[i][j]) {
        ++d2;
    }

    return d1 + d2 > K;
}

bool CheckDiagonal2(size_t i, size_t j) const {
    size_t d1 = 0;
    while (d1 <= i && j + d1 < N && Table[i - d1][j + d1] == Table[i][j]) {
        ++d1;
    }

    size_t d2 = 0;
    while (i + d2 < N && d2 <= j && Table[i + d2][j - d2] == Table[i][j]) {
        ++d2;
    }

    return d1 + d2 > K;
}

Вы работаете оператором на складе. Время от времени вам привозят новые коробки. Каждая коробка имеет свою грузоподъемность и объем . Получая новую коробку, вы ставите на ней серийный номер, используя все целые неотрицательные числа последовательно, начиная с нуля.

Иногда вас просят выдать коробку минимальной грузоподъемности, чтобы она выдержала предмет весом — или коробку минимальной вместимости, в которую можно насыпать песок объемом . Вам нужно быстро определять серийный номер коробки, которая будет выдана. Коробки обратно на склад не возвращаются. Если подходящих коробок несколько, нужно выбрать ту, которая пролежала на складе меньше.

Нужно реализовать класс Stock, у которого, среди прочих, будет три функции:

1. void Add(int w, int v); — добавить коробку на склад;

2. int GetByW(int min_w); — вернуть номер коробки грузоподъемности, хотя бы ;

3. int GetByV(int min_v); — вернуть номер коробки объема, хотя бы .

Если подходящей коробки нет, соответствующая функция должна вернуть .

Примечания

Обратите внимание, что вам нужно отправить только ваш класс Stock, без функции main. Не забудьте, что необходимые функции-члены должны быть доступны вне класса.

Реализуем три дополнительные структуры:

1. WeightNumber — структура для хранения вместимостей коробок;

2. VolumeNumber — структура для хранения объёмов коробок;

3. Iterators — структура для хранения итераторов на коробки. Сами коробки мы будем хранить в двух std::set, итераторы на эти множества мы и будем хранить в Iterators.

Так как мы планируем хранить данные о коробках в двух разных std::set, то для них нужно реализовать компораторы. Идея простая — сначала сортируем по вместимости / объёму, потом по индексу (порядковому номеру).

Все Iterators будем хранить в std::vector, так мы просто поддержим требуемые от нас «серийные номера» (инексы).

Теперь разберём функци-члены:

1. Add — нам нужно добавить коробку в оба множества и полученные итераторы записать в конец вектора.

2. GetByW — вызовем lower_bound от множества грузоподъёмностей. Если результатом стал end(), то коробок, способных поднять такой вес нет. Иначе — мы получим итератор на нужную нам коробку. Удалим её из обоих множеств и вернём искомый индекс.

3. GetByV — полный аналог GetByW, лишь lower_bound вызываем от множества объёмов.

#include <set>
#include <vector>
#include <cstdint>

class Stock {
private:
    struct WeightNumber {
        int w;
        size_t i;

        bool operator < (const WeightNumber& other) const {
            if (w == other.w) {
                return i > other.i;
            }
            return w < other.w;
        }
    };

    struct VolumeNumber {
        int v;
        size_t i;

        bool operator < (const VolumeNumber& other) const {
            if (v == other.v) {
                return i > other.i;
            }
            return v < other.v;
        }
    };

    struct Iterators {
        std::set<WeightNumber>::iterator byW;
        std::set<VolumeNumber>::iterator byV;
    };

    std::vector<Iterators> boxes;
    std::set<WeightNumber> sortedByW;
    std::set<VolumeNumber> sortedByV;

public:
    void Add(int w, int v) {
        size_t num = boxes.size();
        boxes.push_back({sortedByW.insert({w, num}).first, sortedByV.insert({v, num}).first});
    }

    int GetByW(int min_w) {
        const auto it = sortedByW.lower_bound({min_w, boxes.size()});
        if (it == sortedByW.end()) {
            return -1;
        }

        size_t res = it->i;
        sortedByW.erase(it);
        sortedByV.erase(boxes[res].byV);
        return res;
    }

    int GetByV(int min_v) {
        const auto it = sortedByV.lower_bound({min_v, boxes.size()});
        if (it == sortedByV.end()) {
            return -1;
        }

        size_t res = it->i;
        sortedByV.erase(it);
        sortedByW.erase(boxes[res].byW);
        return res;
    }
};

Явным минус такой реализации — из boxes не удаляются коробки. Рано или поздно, если бы это был реальный продукт, у вас случится переполнение. Но это решение всё равно проходит тесты, мы не требовали от вас лучшей реализации.

Но в большой продуктовой задаче очень важно чистить за собой ненужные данные. Проблему накопления мусора в этой задаче можно решить через std::list, в нём удобное удаление из центра, но нет индексирования.

Чтобы решить проблему с индексированием воспользуемся дополнительным std::unordered_map. Да, если коробки сначала только накапливаются, а потом разбираются, то эффективней будет первое решение, но если коробки можно накапливать постепенно, то сильно лучше второе решение.

Для демонстрации мы специально сделали тест, который последовательно вызывает Add, а за ним один из GetBy*. В первой реализации итоговый boxes будет размером с количество вызовов Add, во второй же он всегда будет размером или .

Это никак не сказывается на времени работы (так как удаление из sortedBy* происходит и там, и там), но сказывается на используемой памяти. Для двух миллионов коробок разница занимаемой памяти составляет 60 раз!

#include <list>
#include <set>
#include <cstdint>
#include <unordered_map>

class Stock {
private:
    struct WeightNumber {
        int w;
        size_t i;

        bool operator < (const WeightNumber& other) const {
            if (w == other.w) {
                return i > other.i;
            }
            return w < other.w;
        }
    };

    struct VolumeNumber {
        int v;
        size_t i;

        bool operator < (const VolumeNumber& other) const {
            if (v == other.v) {
                return i > other.i;
            }
            return v < other.v;
        }
    };

    struct Iterators {
        std::set<WeightNumber>::iterator byW;
        std::set<VolumeNumber>::iterator byV;
    };

    std::list<Iterators> boxes;
    std::set<WeightNumber> sortedByW;
    std::set<VolumeNumber> sortedByV;
    std::unordered_map<size_t, std::list<Iterators>::iterator> indexes;
    size_t current_index{0};

public:
    void Add(int w, int v) {
        boxes.push_front({sortedByW.insert({w, current_index}).first,
                            sortedByV.insert({v, current_index}).first});
        indexes.insert({current_index, boxes.begin()});
        ++current_index;
    }

    int GetByW(int min_w) {
        const auto it = sortedByW.lower_bound({min_w, current_index});
        if (it == sortedByW.end()) {
            return -1;
        }

        size_t res = it->i;
        sortedByW.erase(it);
        sortedByV.erase(indexes[res]->byV);
        boxes.erase(indexes[res]);
        indexes.erase(res);
        return res;
    }

    int GetByV(int min_v) {
        const auto it = sortedByV.lower_bound({min_v, current_index});
        if (it == sortedByV.end()) {
            return -1;
        }

        size_t res = it->i;
        sortedByV.erase(it);
        sortedByW.erase(indexes[res]->byW);
        boxes.erase(indexes[res]);
        indexes.erase(res);
        return res;
    }
};

Вам надо написать шаблонный класс Table для электронной таблицы. Для простоты будем считать, что все ячейки таблицы имеют один и тот же тип данных T. Таблица должна уметь менять свой размер по требованию пользователя. Вновь созданные ячейки должны заполняться значениями по умолчанию типа T.

Требования к классу такие:

1. Класс должен называться Table.

2. У класса должен быть шаблонный параметр T — тип элемента в ячейке.

3. У класса должен быть конструктор, получающий на входе два числа типа size_t, — начальные размеры таблицы.

4. У класса должны быть константная и неконстантная версии оператора [], возвращающего нечто такое, к чему снова можно было бы применить оператор []. То есть, должны работать конструкции вида std::cout << table[i][j]; и table[i][j] = value;. Проверять корректность индексов при этом не нужно.

5. У класса должна быть функция resize, получающая на вход два параметра типа size_t и меняющая размер таблицы. Старые данные, умещающиеся в новый размер, должны при этом сохраниться.

6. У класса должна быть функция size, возвращающая std::pair<size_t, size_t> — размер таблицы (в том же порядке, в котором эти аргументы передавались в конструктор).

#include <vector>
#include <utility>

template <typename T>
class Table {
private:
    std::vector<std::vector<T>> data;

public:
    Table(size_t m, size_t n) {
        resize(m, n);
    }

    // версия для неконстантных таблиц
    std::vector<T>& operator [] (size_t i) {
        return data[i];
    }

    // версия для константных таблиц
    const std::vector<T>& operator [] (size_t i) const {
        return data[i];
    }

    void resize(size_t m, size_t n) {
        data.resize(m);
        for (size_t i = 0; i < m; ++i) {
            data[i].resize(n);
        }
    }

    std::pair<size_t, size_t> size() const {
        if (data.empty()) {
            return {0, 0};
        } else {
            return {data.size(), data[0].size()};
        }
    }
};

Часто задаваемый вопрос — какой индекс в таблице отвечает за строки, а какой — за столбцы. На самом деле это совершенно не важно. Главное, чтобы пара индексов i и j, по которым будут обращаться в таблицу, была бы согласованной с размерами: i должен быть меньше m, а j меньше n.

Другая типичная ошибка — возврат {data.size(), data[0].size()} в функции size() без проверки пустоты вектора. На пустом data тут будет некорректное обращение к памяти в data[0].

Вам требуется реализовать класс Queue, аналогичный адаптеру std::queue. Он является обёрткой над некоторым стандартным контейнером и реализует интерфейс очереди. Класс должен быть шаблонным. Первый шаблонный параметр T — тип хранимых элементов. Второй шаблонный параметр — контейнер, используемый для хранения элементов (по умолчанию — std::deque<T>):

template <typename T, typename Container = std::deque<T>>
class Queue;

Предусмотрите в классе следующее:

1. Конструктор по умолчанию, создающий пустую очередь.

2. Константную функцию front, которая возвращает элемент, стоящий в начале очереди.

3. Неконстантную функцию front, которая возвращает по ссылке элемент, стоящий в начале очереди — тем самым давая возможность его изменить.

4. Функцию pop, которая убирает элемент из начала очереди (и ничего не возвращает)

5. Функцию push, которая кладёт переданный элемент в конец очереди.

6. Функцию size, которая возвращает количество элементов.

7. Функцию empty, которая возвращает true тогда и только тогда, когда очередь пуста

8. Операторы == и != для сравнения двух очередей.

Наш класс будет просто обёрткой над контейнером. Все функции нашего класса будут сводиться к вызову соответствующих функций контейнера. Смысл нашего класса в том, что мы ограничиваем публичный интерфейс, оставляя только функции, специфичные для очереди. Например, у нас не будет оператора [] или функций begin и end, так как для очереди они не нужны. Кроме того, некоторые функции у очереди будут называться иначе (push и pop вместо push_back и pop_front), так как для очереди бессмысленно указывать, с какой стороны в неё поступают элементы, и с какой извлекаются.

Конструктор класса Queue можно не писать, так как компилятор предоставит автоматически конструктор по умолчанию.

#include <deque>

template <typename T, typename Container = std::deque<T>>
class Queue {
private:
    Container data;

public:
    const T& front() const {
        return data.front();
    }

    T& front() {
        return data.front();
    }

    void push(const T& elem) {
        data.push_back(elem);
    }

    void pop() {
        data.pop_front();
    }

    size_t size() const {
        return data.size();
    }

    bool empty() const {
        return data.empty();
    }

    bool operator == (const Queue& other) const {
        return data == other.data;
    }

    bool operator != (const Queue& other) const {
        return !operator==(other);
    }
};

Обратите внимание, что операторы == и !=, а также функции size и empty объявлены константными, так как они не меняют очередь. Это позволяет применять их к константным очередям. Также функция front перегружена по константности: для константных очередей элемент возвращается для чтения, а для неконстантных — для записи.

Вася разрабатывает свою структуру — базу данных «ключ-значение». Эта структура данных должна хранить значение, ассоциированное с ключом, и она будет делать это суперэффективно. Пока для простоты Вася выбрал за основу std::unordered_map, но потом он это переделает.

Какие операции должно поддерживать такое хранилище? Правильно: вставка элемента, удаление элемента и поиск элемента. Вася написал прототипы функций Insert, Remove и Find, но функция Find почему-то не работает. Помогите Васе её исправить. Вот код Васи:

#include <unordered_map>

template <typename Key, typename Value>
class KeyValueStorage {
private:
      std::unordered_map<Key, Value> data;

public:
    void Insert(const Key& key, const Value& value) {
        data[key] = value;
    }

    void Remove(const Key& key) {
        data.erase(key);
    }

    bool Find(const Key& key, Value* const value = nullptr) const;
};


// Почему-то не работает...
//
// template <typename Key, typename Value>
// bool KeyValueStorage<Key, Value>::Find(const Key& key, Value* const value) const {
//     auto it = std::find(data.begin(), data.end(), key);
//     auto val = *it;
//     if (value != nullptr)
//         value = &val;
//     return it != data.end();
// }

// Ваша реализация функции KeyValueStorage::find будет вставлена сюда:
#include "your_version_of_find.h"

Ваша версия функции Find будет вставлена в конце этого кода. Её заголовок должен быть таким же, как в закомментированной части.

Функция Find по задумке должна возвращать true, если ключ был найден, и false в противном случае. Если второй аргумент функции Find отличен от nullptr и ключ найден, то функция должна записать найденное значение в тот объект, на который ссылается этот аргумент (предполагается, что новая структура данных сможет быстро определять наличие ключа, но само значение будет извлекаться дорого, и делать это нужно лишь при необходимости). Использовать эту функцию предполагается примерно так:

#include "key_value_storage.h"

#include <string>

int main() {
    KeyValueStorage<std::string, int> kv;
    kv.Insert("hello", 42);
    kv.Insert("bye", -13);
    int value = 123;
    auto res = kv.Find("wrong", &value);  // должно вернуться false, а value не должен меняться
    res = kv.Find("bye", &value);  // должно вернуться true, в value должно быть -13
    res = kv.Find("hello", nullptr);  // должно вернуться true
}

Наш код будет вставлен после класса. Поэтому для описания тела функции нам потребуется написать шапку template <typename Key, typename Value>, а имя функции предварить префиксом с именем класса - как в закомментированном примере.

template <typename Key, typename Value>
bool KeyValueStorage<Key, Value>::Find(const Key& key, Value* const value) const {
    auto it = data.find(key);
    if (it != data.end() && value != nullptr) {
        *value = it->second;
    }
    return it != data.end();
}

Примечания

Разберём типичные ошибки:

1. Не надо пытаться использовать общий алгоритм std::find или std::find_if. Нужно использовать встроенную функцию find контейнера unordered_map. Во-первых, встроенный find будет работать быстрее (а std::find будет выполнять линейный поиск). Во-вторых, std::find не предназначен для поиска по ключу. Он ищет в контейнере готовый образец, а значит, ему придётся передать пару из ключа и значения (которого мы не знаем).

2. Если значение не найдено, не надо ничего делать с value. Это можно понять по примеру использования. В этом случае надо просто вернуть false.

3. Неправильно писать value = &it->second. Сам указатель value мы поменять не сможем; мы лишь записываем найденное значение в ту ячейку памяти, на которую он указывает (если он не nullptr). По условию мы предполагаем, что он в таком случае указывает на корректный существующий объект.

В этой задаче вам надо будет написать свой дек. Писать его по-честному долго и сложно, поэтому мы пошли вам навстречу: вам нужно написать упрощенную версию дека без итераторов, и умеющую только добавлять элементы в начало и конец. Поддерживать удаление элементов из дека не требуется.

В отличие от стандартного дека возьмите за основу два вектора, растущих каждый в свою сторону. Предлагаем такой прототип — а вам нужно реализовать указанные функции:

#include <cstddef>
#include <vector>

template <typename T>
class Deque {
private:
    std::vector<T> head, tail;

public:
    bool Empty() const;

    size_t Size() const;

    void Clear();

    const T& operator [] (size_t i) const;

    T& operator [] (size_t i);

    const T& At(size_t i) const;  // throws std::out_of_range on incorrect index

    T& At(size_t i);  // throws std::out_of_range on incorrect index

    const T& Front() const;

    T& Front();

    const T& Back() const;

    T& Back();

    void PushFront(const T& elem);

    void PushBack(const T& elem);
};

Примечания

Сдайте в систему класс Deque с написанными функциями.

Дек должен уметь эффективно расти в обе стороны. А вектор умеет эффективно расти только в одну сторону. Поэтому предлагается реализовать решение с помощью двух векторов, смотрящих в разные стороны. По условию удаляться из дека ничего не будет, поэтому в эти векторы будут только добавляться новые элементы в конец. Однако важно помнить, что один из этих векторов может оставаться пустым, если с соответствующей стороны вставок еще не было. Поэтому, например, при вызовe Front мы должны сначала посмотреть на первый вектор, а если он пуст — то на второй.

Часто задаваемые вопросы

Q. Какой из векторов (head или tail) соотвествует началу, а какой — концу дека?
A. На самом деле это детали нашей реализации, никак не связанные с объявленным публичным интерфейсом, который требуется реализовать. Можно выбрать любое соответствие и придерживаться его.

Q. Какой должен быть конструктор дека? Нужен ли конструктор от двух векторов?
A. Заметим, что в представленном публичном интерфейсе конструктора нет. Значит, компилятор предоставит по умолчанию конструктор без аргументов, инициализирующий поля head и tail их дефолтными конструкторами. Конечно, такой конструктор создаёт пустой дек. Другие конструкторы не требуются. Итак, конструктор можно вообще не писать — нам достаточно дефолтного.

Q. Что должны делать функции Front и Back на пустом деке?
A. Как и в std::deque, они не должны делать никаких проверок. То, что эти функции не вызываются на пустом деке, лежит на совести программиста.

Q. Что должна делать функция At?
A. Как и в контейнерах стандартной библиотеки, она аналогична оператору [], но проверяет корректность индекса. В случае некорректного индекса она должна генерировать исключение.

Q. Не получается сгенерировать исключение.
A. Во-первых, надо подключить <stdexcept> — этот заголовочный файл указан в документации std::out_of_range. В конструктор std::out_of_range надо передать текстовую строку с описанием ошибки. Строка может быть любой, мы её не проверяем.

Итоговый класс:

#include <cstddef>
#include <stdexcept>
#include <vector>

template <typename T>
class Deque {
private:
    std::vector<T> head, tail;

    void CheckIndex(size_t i) const {
        if (i >= Size()) {
            throw std::out_of_range("Index is out of range");
        }
    }

public:
    bool Empty() const {
        return head.empty() && tail.empty();
    }

    size_t Size() const {
        return head.size() + tail.size();
    }

    void Clear() {
        head.clear();
        tail.clear();
    }

    const T& operator [] (size_t i) const {
        if (i < head.size()) {
            return head[head.size() - i - 1];
        }
        return tail[i - head.size()];
    }

    T& operator [] (size_t i) {
        if (i < head.size()) {
            return head[head.size() - i - 1];
        }
        return tail[i - head.size()];
    }

    const T& At(size_t i) const {
        CheckIndex(i);
        return (*this)[i];
    }

    T& At(size_t i) {
        CheckIndex(i);
        return (*this)[i];
    }

    const T& Front() const {
        if (head.empty()) {
            return tail.front();
        }
        return head.back();
    }

    T& Front() {
        if (head.empty()) {
            return tail.front();
        }
        return head.back();
    }

    const T& Back() const {
        if (tail.empty()) {
            return head.front();
        }
        return tail.back();
    }

    T& Back() {
        if (tail.empty()) {
            return head.front();
        }
        return tail.back();
    }

    void PushFront(const T& elem) {
        head.push_back(elem);
    }

    void PushBack(const T& elem) {
        tail.push_back(elem);
    }
};

Математический вектор (не путать с std::vector!) – структура линейной алгебры, определяющаяся набором упорядоченных чисел (координат). Обозначается как . Число в таком случае называется размерностью вектора.

В качестве примера можно рассмотреть вектора размерности два с координатами в вещественных числах. В таком случае вектор будет задавать знакомый нам со школы геометрический вектор с началом в координате и концом в .

Также заметим, что координаты вектора необязательно вещественные числа. Это могут быть рациональные, комплексные или любые другие математические объекты, обладающие набором базовых операций сложения и умножения (например математические матрицы).

Над математическим вектором можно проводить две операции:

1. Сложение двух векторов одинаковой размерности: пусть , , тогда ;

2. Умножение вектора на число (тип числа должен быть одинаковым с типом чисел координат у вектора): пусть , - какое-то число, тогда .

Вам дан шаблонный класс MathVector<T>, представляющий собой математический вектор с координатами типа T:

#include <iostream>
#include <vector>

template <typename T>
class MathVector {
 private:
    std::vector<T> data;

 public:
    // Храним в `data` нулевой вектор длины `n`
    MathVector(size_t n) {
        data.resize(n);
    }

    template <typename Iter>
    MathVector(Iter first, Iter last) {
        while (first != last) {
            data.push_back(*first);
        }
    }

    size_t Dimension() const {
         return data.size();
    }

    T& operator [] (size_t i) {
        return data[i];
    }

    const T& operator [] (size_t i) const {
        return data[i];
    }
};

// Output format: (1, 2, 3, 4, 5)
template <typename T>
std::ostream& operator << (std::ostream& out, const MathVector<T>& v) {
    out << '(';
    for (size_t i = 0; i != v.Dimension(); ++i) {
        if (i > 0) {
            out << ", ";
        }
        out << v[i];
    }
    out << ')';
    return out;
}

template <typename T>
MathVector<T>& operator *= (MathVector<T>& v, const T& scalar) {
    for (size_t i = 0; i != v.Dimension(); ++i) {
        v[i] *= scalar;
    }
    return v;
}

template <typename T>
MathVector<T> operator * (const MathVector<T>& v, const T& scalar) {
    auto tmp(v);
    tmp *= scalar;
    return tmp;
}

template <typename T>
MathVector<T> operator * (const T& scalar, const MathVector<T>& v) {
    return v * scalar;
}

Вам требуется исправить ошибки в коде этого класса и дописать операторы += и + для сложения векторов. Считайте, что складываться друг с другом всегда будут только векторы одинаковой размерности.

Для начала исправим существующие в коде ошибки:

Первая ошибка находится в конструкторе вектора по двум итераторам. В цикле while нет инкремента для итератора, из-за чего получается бесконечный цикл. Правильнее всего переписать цикл на for.

Вторая ошибка в константном операторе operator []. Чтобы явно обозначить константное получение элемента из std::vector, необходимо использовать функцию .at.

Когда все ошибки исправлены – остаётся только дописать недостающие функции по аналогии с уже существующими.

Итоговый файл:

#include <iostream>
#include <vector>

template<typename T>
class MathVector {
private:
    std::vector<T> data;

public:
    // Храним в `data` нулевой вектор длины `n`
    MathVector(size_t n) {
        data.resize(n);
    }

    template<typename Iter>
    MathVector(Iter first, Iter last) {
        for (; first != last; ++first) {
            data.push_back(*first);
        }
    }

    size_t Dimension() const {
        return data.size();
    }

    T& operator [] (size_t i) {
        return data[i];
    }

    const T& operator [] (size_t i) const {
        return data.at(i);
    }
};

// Output format: (1, 2, 3, 4, 5)
template<typename T>
std::ostream& operator << (std::ostream& out, const MathVector<T>& v) {
    out << '(';
    for (size_t i = 0; i != v.Dimension(); ++i) {
        if (i > 0) {
            out << ", ";
        }
        out << v[i];
    }
    out << ')';
    return out;
}

template<typename T>
MathVector<T>& operator *= (MathVector<T>& v, const T& scalar) {
    for (size_t i = 0; i != v.Dimension(); ++i) {
        v[i] *= scalar;
    }
    return v;
}

template<typename T>
MathVector<T> operator * (const MathVector<T>& v, const T& scalar) {
    auto tmp(v);
    tmp *= scalar;
    return tmp;
}

template<typename T>
MathVector<T> operator * (const T& scalar, const MathVector<T>& v) {
    return v * scalar;
}


template<typename T>
MathVector<T>& operator += (MathVector<T>& v1, const MathVector<T>& v2) {
    for (size_t i = 0; i != v1.Dimension(); ++i) {
        v1[i] += v2[i];
    }
    return v1;
}


template<typename T>
MathVector<T> operator + (const MathVector<T>& v1, const MathVector<T>& v2) {
    MathVector<T> tmp = v1;
    tmp += v2;
    return tmp;
}

Многочлен от одной переменной – алгебраическое выражение, состоящие из суммы нескольких произведений числовых коэффициентов на переменную в натуральной степени. Пример: . Слагаемыми в многочлене называют одночленами.

Так же как и в задаче о математическом векторе, числами здесь могут являться любые объекты со стандартным набором базовых математических операций (сложение, вычитание, умножение, деление), например дробные, вещественные или комплексные числа, а так же математические матрицы и другие алгебраические объекты.

Реализуйте шаблонный класс Polynomial (многочлен от одной переменной) на основе контейнера std::vector. Тип коэффициентов многочлена передавайте в качестве параметра шаблона. Хранение коэффициентов должно быть плотным (то есть должны храниться все коэффициенты, в том числе и промежуточные нулевые).

Сделайте следующее:

1. Напишите конструкторы, которые

   • создают многочлен по заданному вектору коэффициентов (коэффициенты задаются по возрастанию степени).
   • создают многочлен по заданному коэффициенту (многочлен нулевой степени), который равен значению по умолчанию параметра шаблона.
   • создают многочлен по заданным итераторам на начало и следующий за концом последовательности коэффициентов (аналогично, по возрастанию степени).

2. Перегрузите операторы == и !=. Ваш код должен быть очень простым. Операторы должны работать и в том случае, когда один из аргументов является скалярной величиной.

3. Перегрузите операторы +, - и *, а также соответствующие операторы +=, -= и *=. Учтите, что должны быть определены и такие арифметические операции, в которых один из аргументов является скалярной величиной.

4. Перегрузите оператор [] для получения коэффициента многочлена перед заданной степенью переменной. Достаточно константной версии этого оператора. Оператор должен работать для любых степеней (в том числе больше текущей максимальной). Напишите также метод Degree для вычисления степени многочлена (считайте, что у нулевого многочлена степень равна ).

5. Перегрузите оператор () для вычисления значения многочлена в точке. В качестве аргумента этот оператор принимает значение того типа, от которого создан многочлен. Постарайтесь написать эффективный код.

6. Перегрузите оператор << для печати многочлена в поток вывода. Для простоты будем выводить коэффициенты через пробел от старшей степени к младшей.

7. Предусмотрите методы begin() и end() для доступа к константным итераторам, позволяющим перебрать коэффициенты многочлена (это могут быть просто итераторы вектора). При этом ведущие нули коэффициентами не считаются. Итерация должна происходить по возрастанию степени.

Примечание

В вашем решении должен быть только код класса и не должно быть функции main. При проверке наша программа будет использовать ваш класс Polynomial. Она сама прочитает из входного потока коэффициенты многочленов и выведет их сумму, разность, произведение и т. д.

Обратите внимание, что если какой-то из операторов реализован в вашем решении, но при этом его вызов не компилируется (т. е. реализован неправильно), то вы будете получать не ошибку компиляции, а неправильный ответ, так как тестирующая программа доопределяет те операторы, вызов которых не компилируется.

Вы можете считать, что шаблонный параметр — это числовой тип, для которого реализованы все арифметические операции, операции сравнения и вывод в поток. Также переменную этого типа можно сконструировать от int. Обратите внимание, что наличие неявного конструктора и оператора приведения типа не гарантируется: необходимо вызывать конструктор явно.

Для начала реализуем конструкторы класса:

#include <algorithm>
#include <iostream>
#include <vector>

template <typename T>
class Polynomial {
public:
    using Container = typename std::vector<T>;
    using ConstIterator = typename Container::const_iterator;

private:
    Container coefficients;
    inline static const T valueTypeZero{0};

    void Normalize() {
        while (!coefficients.empty() && coefficients.back() == valueTypeZero) {
            coefficients.pop_back();
        }
    }

    Container& GetCoefficients() {
        return coefficients;
    }

public:
    Polynomial(const Container& coeffs)
        : coefficients{coeffs} {
            Normalize();
        }

    Polynomial(const T& value = {}) {
        if (value != valueTypeZero) {
            coefficients.push_back(value);
        }
    }

    template<typename ForwardIt>
    Polynomial(ForwardIt first, ForwardIt last)
        : coefficients{first, last} {
            Normalize();
    }

    const Container& GetCoefficients() const {
        return coefficients;
    }

Для удобства будем удалять все нулевые коэффициенты с конца вектора. Для этого используем функцию Normalize (см. выше). Чтобы проверять, является ли элемент нулевым, создадим в классе приватное константное поле valueTypeZero типа T равное нулю. Ключевое слово static указывает, что новое поле относится к самому классу, а не к его объектам. Ключевое слово inline позволяет проинициализировать static-поле в момент определения (напоминаем, оно инициализируется нулём).

Хранить же наши коэффициенты будем в векторе, где coefficients[i] будет значить, что мы смотрим на коэффициент перед . У вектора есть конструктор копирования, чем мы воспользуемся при реализации конструктора, который принимает вектор. Аналогично поступим с конструктором, который принимает два итератора. Конструктор, создающий многочлен по заданному коэффициенту будет добавлять в наш вектор этот самый коэффициент, только если он не ноль. Это позволяет лишний раз не вызывать Normalize().

Также реализуем вспомогательные методы, которые будем использовать в дальнейшем: GetCoefficients() и GetCoefficients() const. Будем использовать эти методы для явного обращения к коэффициентам.

Далее реализуем операторы == и !=:

    friend bool operator == (const Polynomial<T>& lhs, const Polynomial<T>& rhs) {
        return lhs.GetCoefficients() == rhs.GetCoefficients();
    }

    friend bool operator != (const Polynomial<T>& lhs, const Polynomial<T>& rhs) {
        return !(lhs == rhs);
    }

У std::vector переопределён operator ==, чем мы и воспользуемся.

Так как при декларации конструктора класса не используется ключевое слово explicit, операторы будут работать и в том случае, когда один из аргументов является скалярной величиной.

Далее реализуем арифметические операции:

    Polynomial<T>& operator += (const Polynomial<T>& other) {
        if (other.Degree() > Degree()) {
            GetCoefficients().resize(other.Degree() + 1);
        }

        for (int i = 0; i <= Degree() && i <= other.Degree(); ++i) {
            GetCoefficients()[i] += other.GetCoefficients()[i];
        }
        Normalize();
        return *this;
    }

    Polynomial<T>& operator -= (const Polynomial<T>& other) {
        if (other.Degree() > Degree()) {
            GetCoefficients().resize(other.Degree() + 1);
        }

        for (int i = 0; i <= Degree() && i <= other.Degree(); ++i) {
            GetCoefficients()[i] -= other.GetCoefficients()[i];
        }
        Normalize();
        return *this;
    }

    Polynomial<T>& operator *= (const Polynomial<T>& other) {
        if (Degree() == -1 || other.Degree() == -1) {
            GetCoefficients().resize(0);
            return *this;
        }

        std::vector<T> tmp(Degree() + other.Degree() + 1);
        for (int i = 0; i <= Degree(); ++i) {
            for (int j = 0; j <= other.Degree(); ++j) {
                tmp[i + j] += GetCoefficients()[i] * other.GetCoefficients()[j];
            }
        }
        GetCoefficients() = std::move(tmp);
        Normalize();
        return *this;
    }

Заметьте, что в реализации этих методов используется ещё нереализованный метод Degree(). Этот метод будет объявлен чуть позже (когда до него дойдёт очередь). Всё что нам надо знать сейчас – он возвращает степень полинома, а если полином равен нулю, то -1.

Все три оператора изначально делают resize(), чтобы избежать неопределённое поведение, и согласно правилам математики складывают, вычитают или умножают два многочлена. При этом в умножении рассматривается отдельно краевой случай, когда один из полиномов равен нулю. После каждой операции вызываем функцию Normalize().

    friend Polynomial<T> operator + (Polynomial<T> lhs, const Polynomial<T>& rhs) {
        return lhs += rhs;
    }

    friend Polynomial<T> operator - (Polynomial<T> lhs, const Polynomial<T>& rhs) {
        return lhs -= rhs;
    }

    friend Polynomial<T> operator * (Polynomial<T> lhs, const Polynomial<T>& rhs) {
        return lhs *= rhs;
    }

lhs будем принимать не по ссылке, а создавать копию на лету. Это позволит нам изменить и сразу же вернуть её, применив соответствующий оператор.

Далее реализуем оператор [] и функцию Degree:

    int Degree() const {
        return static_cast<int>(GetCoefficients().size()) - 1;
    }

    const T& operator [] (size_t power) const {
        if (static_cast<int>(power) > Degree()) {
            return valueTypeZero;
        }
        return GetCoefficients()[power];
    }

Обратите внимание, из-за того что мы в самом начале договорились не хранить незначащие нули в конце вектора, код функции Degree помещается в одну строчку. Действительно, в таком случае степенью многочлена будет являться длина вектора коэффициентов минус один.

Далее реализуем оператор (). Воспользуемся для этого алгоритмом Горнера:

    T operator () (const T& given_value) const {
        T result = valueTypeZero;

        for (auto i = Degree(); i >= 0; --i) {
            result *= given_value;
            result += GetCoefficients()[i];
        }

        return result;
    }

Проще говоря, для многочлена мы вынесем за скобки везде, где это возможно. Получится следующее выражение . Таким образом нужно просто реализовать цикл с умножением на заданную переменную и сложением со следующим коэффициентом.

Реализация методов .begin и .end является тривиальной, поскольку мы можем вернуть итераторы самого вектора коэффициентов:

    ConstIterator begin() const {
        return GetCoefficients().cbegin();
    }

    ConstIterator end() const {
        return GetCoefficients().cend();
    }
};

Оператор << принято реализовывать вне класса. Тут всё просто, пробежим по всем степеням от последней к первой.

template<typename T>
std::ostream& operator<<(std::ostream& out, const Polynomial<T>& polynomial) {
    for (auto i = polynomial.Degree(); i >= 0; --i) {
        out << polynomial[i];
        if (i != 0) {
            out << ' ';
        }
    }
    return out;
}

Вам дан готовый класс Logger, который в своих конструкторах, операторах присваивания и деструкторе печатает соответствующие сообщения:

#include <iostream>

class Logger {
private:
    static int counter;
    const int id;

public:
    Logger(): id(++counter) {
        std::cout << "Logger(): " << id << "\n";
    }

    Logger(const Logger& other): id(++counter) {
        std::cout << "Logger(const Logger&): " << id << " " << other.id << "\n";
    }

    Logger(Logger&& other): id(++counter) {
        std::cout << "Logger(Logger&&): " << id << " " << other.id << "\n";
    }

    Logger& operator = (const Logger& other) {
        std::cout << "Logger& operator = (const Logger&): " << id << " " << other.id << "\n";
        return *this;
    }

    Logger& operator = (Logger&& other) {
        std::cout << "Logger& operator = (Logger&&): " << id << " " << other.id << "\n";
        return *this;
    }

    ~Logger() {
        std::cout << "~Logger(): " << id << "\n";
    }
};

int Logger::counter = 0;

Вам требуется написать программу, которая работает с этим классом и выводит следующий текст:

Logger(): 1
~Logger(): 1
Logger(): 2
~Logger(): 2

Примечания

Не вставляйте код класса в решение. Используйте вместо этого директиву #include "logger.h" в начале программы. Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

Тут нужно создать два объекта и как-то искусственно ограничить жизнь второго. Это можно сделать несколькими способами:

Например, использовать блоки:

#include "logger.h"

int main() {
    { Logger logger; }
    { Logger logger; }
}

Также можно реализовать дополнительную функцию и вызвать её два раза:

#include "logger.h"

void CreateLogger() {
    Logger logger;
}

int main() {
    CreateLogger();
    CreateLogger();
}

В предыдущей задаче вам был дан готовый класс Logger, который в своих конструкторах, операторах присваивания и деструкторе печатает соответствующие сообщения.

Вам требуется написать программу, которая работает с этим классом и выводит следующий текст:

Logger(): 1
Logger(const Logger&): 2 1
~Logger(): 2
~Logger(): 1

Примечания

Не вставляйте код класса в решение. Используйте вместо этого директиву #include "logger.h" в начале программы. Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

В этой задаче так же создаётся два объекта, но в этот раз вызывается конструктор копирования второго объекта от первого.

#include "logger.h"

int main() {
    Logger logger1;
    Logger logger2(logger1);  //  Можно записать иначе: Logger logger2 = logger1;
}

В предыдущей задаче вам был дан готовый класс Logger, который в своих конструкторах, операторах присваивания и деструкторе печатает соответствующие сообщения.

Вам требуется написать программу, которая работает с этим классом и выводит следующий текст:

Logger(): 1
Logger(Logger&&): 2 1
~Logger(): 2
~Logger(): 1

Примечания

Не вставляйте код класса в решение. Используйте вместо этого директиву #include "logger.h" в начале программы. Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

Полный аналог предыдущей задачи за исключением того, что вызывается не конструктор копирования, а move-конструктор:

#include <utility>

#include "logger.h"

int main() {
    Logger logger1;
    Logger logger2(std::move(logger1));  // Можно записать иначе: Logger logger2 = std::move(logger1);
}

В предыдущей задаче вам был дан готовый класс Logger, который в своих конструкторах, операторах присваивания и деструкторе печатает соответствующие сообщения.

Вам требуется написать программу, которая работает с этим классом и выводит следующий текст:

Logger(): 1
Logger(): 2
Logger& operator = (const Logger&): 1 2
Logger& operator = (Logger&&): 1 2
~Logger(): 2
~Logger(): 1

Примечания

Не вставляйте код класса в решение. Используйте вместо этого директиву #include "logger.h" в начале программы. Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

Давайте прочитаем требуемый вывод: создаётся два объекта, в первый копируется второй, в первый «перемещается» второй, вызываются деструкторы.

Теперь давайте тоже самое запишем кодом, буквально слово в слово:

#include <utility>

#include "logger.h"

int main() {
    Logger logger1, logger2;
    logger1 = logger2;
    logger1 = std::move(logger2);
}

В предыдущей задаче вам был дан готовый класс Logger, который в своих конструкторах, операторах присваивания и деструкторе печатает соответствующие сообщения.

Вам требуется написать программу, которая работает с этим классом и выводит следующий текст:

Logger(): 1
Logger(): 2
Logger(): 3
~Logger(): 2
~Logger(): 3
~Logger(): 1

Примечания

Не вставляйте код класса в решение. Используйте вместо этого директиву #include "logger.h" в начале программы. Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

В этой задаче важно было заметить, что второй и третий созданные объекты удаляются в противоположном порядке. Есть много способов получить такой порядок, самый простой, пожалуй, через указатели:

#include "logger.h"

int main() {
    Logger logger1;
    Logger* logger2 = new Logger;
    Logger* logger3 = new Logger;
    delete logger2;
    delete logger3;
}

Так же можно было использовать какой-нибудь контейнер, например, std::list:

#include <list>

#include "logger.h"

int main() {
    Logger logger1;  // создаём первый объект
    std::list<Logger> loggers(2);  // создаём 2 и 3 объекты
    loggers.pop_front();  // уничтожаем второй объект
}

В предыдущей задаче вам был дан готовый класс Logger, который в своих конструкторах, операторах присваивания и деструкторе печатает соответствующие сообщения.

Вам требуется написать программу, которая работает с этим классом и выводит по заданному следующий текст:

Logger(): 1
Logger(): 2
...
Logger(): n
~Logger(): n
...
~Logger(): 2
~Logger(): 1

Примечания

Не вставляйте код класса в решение. Используйте вместо этого директиву #include "logger.h" в начале программы. Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

Тут так же было можно пойти несколькими путями, наилучший, на наш взгляд, был через вектор:

#include <iostream>
#include <vector>

#include "logger.h"

int main() {
    size_t n = 0;
    std::cin >> n;

    std::vector<Logger> loggers(n);
    for (size_t i = 0; i != n; ++i) {
        loggers.pop_back();
    }
}

Некоторые, эксперементируя локально, могли получать искомый ответ при примерно такой версии кода:

#include <iostream>
#include <vector>

#include "logger.h"

int main() {
    size_t n = 0;
    std::cin >> n;
    std::vector<Logger> loggers(n);
}

Но в тесты этот код не проходит. Дело в том, что порядок удаления элементов в векторе в деструкторе не детерминирован и может разниться от реализации к реализации. В контесте это прямой порядок, где-то он может быть обратным (и, вообще говоря, любым).

В предыдущей задаче вам был дан готовый класс Logger, который в своих конструкторах, операторах присваивания и деструкторе печатает соответствующие сообщения.

Вам требуется написать программу, которая работает с этим классом и выводит по заданному следующий текст:

Logger(): 1
Logger(): 2
...
Logger(): n
~Logger(): 1
~Logger(): 2
...
~Logger(): n

Примечания

Не вставляйте код класса в решение. Используйте вместо этого директиву #include "logger.h" в начале программы. Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

Задачу можно было решать через любой известный контейнер двумя способами: через указатели:

#include <iostream>
#include <vector>

#include "logger.h"

int main() {
    size_t n = 0;
    std::cin >> n;

    std::vector<Logger*> pointers(n);
    for (size_t i = 0; i != n; ++i) {
        pointers[i] = new Logger;
    }

    for (size_t i = 0; i != n; ++i) {
        delete pointers[i];
    }
}

Но в указателях особо не было смысла, так как у нас есть контейнеры, которые поддерживают удаление из начала, например, std::list:

#include <iostream>
#include <list>

#include "logger.h"

int main() {
    size_t n = 0;
    std::cin >> n;

    std::list<Logger> loggers(n);
    for (size_t i = 0; i != n; ++i) {
        loggers.pop_front();
    }
}

Вася хочет замерять время работы разных частей своей программы. Сейчас он делает это средствами стандартной библиотеки так:

#include <iostream>
#include <chrono>

#include "some_long_stuff.h"

void SomeFunc() {
    auto start1 = std::chrono::high_resolution_clock::now();
    FirstLongFunction();
    std::chrono::duration<double> diff1 = std::chrono::high_resolution_clock::now() - start1;
    std::cout << "FirstLongFunction elapsed: " << diff1.count() << "\n";

    auto start2 = std::chrono::high_resolution_clock::now();
    SecondLongFunction();
    std::chrono::duration<double> diff2 = std::chrono::high_resolution_clock::now() - start2;
    std::cout << "SecondLongFunction elapsed: " << diff2.count() << "\n";

    auto start3 = std::chrono::high_resolution_clock::now();
    ThirdLongFunction();
    std::chrono::duration<double> diff3 = std::chrono::high_resolution_clock::now() - start3;
    std::cout << "ThirdLongFunction elapsed: " << diff3.count() << "\n";
}

int main() {
    SomeFunc();
    return 0;
}

Но ему очень не удобно каждый раз прописывать начало замера и конец. Помогите ему сделать это удобнее.

Напишите обёртку TimerGuard. Это класс, который создается перед началом вычислений и при выходе из своего scope пишет в поток время работы, которое он существовал. С его помощью Вася сможет писать так:

#include <iostream>
#include <chrono>

#include "some_long_stuff.h"

void SomeFunc() {
    {
        TimerGuard timer("FirstLongFunction elapsed: ", std::cout);
        FirstLongFunction();
    }
    {
        TimerGuard timer("SecondLongFunction elapsed: ", std::cout);
        SecondLongFunction();
    }
    {
        TimerGuard timer("ThirdLongFunction elapsed: ", std::cout);
        ThirdLongFunction();
    }
}

int main() {
    SomeFunc();
    return 0;
}

Класс TimerGuard должен содержать следующий конструктор:

TimerGuard(std::string message = "", std::ostream& out = std::cout);

message — сообщение, печатаемое перед перед временем. out — поток, в который нужно печатать сообщение.

Деструктор класса должен печатать сообщение в формате "{message} {time}" (обратите внимание на пробел).

Примечания

Сдайте в систему только код конструкции TimerGuard без функции main. Подключите необходимые библиотеки.

Обратите внимание, что данный guard очень полезен даже вне этой задачи. Его можно использовать при отладке медленных участков вашей программы!

В блоках Васи TimerGuard дёргается два раза — при создании (конструктор) и при выходе из блока (деструктор). Так что давайте напишем класс, который при создании будет запоминать все необходимые переменные в поля класса, а в деструкторе выводить их:

#include <iostream>
#include <chrono>
#include <string>

class TimerGuard {
    std::chrono::time_point<std::chrono::high_resolution_clock> start;
    std::string outMessage;
    std::ostream& outStream;
public:

    TimerGuard(std::string message = "", std::ostream& out = std::cout):
        start(std::chrono::high_resolution_clock::now()),  // start - вызов конструктора
        outMessage(message),
        outStream(out)
    {
    }

    ~TimerGuard() {
        auto end = std::chrono::high_resolution_clock::now();  // конец - вызов деструктора
        std::chrono::duration<double> diff = end - start;
        outStream << outMessage << " " << diff.count() << "\n";
    }
};

Вам надо написать базовый класс Figure (геометрическая фигура) и унаследованные от него классы Triangle (треугольник) и Rectangle (прямоугольник).

Класс Triangle должен иметь конструктор, принимающий на вход три числа типа int — стороны треугольника. Считайте, что треугольник с такими сторонами всегда существует.

Класс Rectangle должен иметь конструктор, принимающий на вход два числа типа int — стороны прямоугольника.

Класс Figure должен объвлять виртуальную функцию int Perimeter() const, возвращающую периметр фигуры.

Классы-наследники должны переопределить эту функцию правильным образом.

Функцию main писать в вашем коде не надо: она будет в нашей проверяющей программе. Наша программа выглядит так:

#include "figures.h"

#include <vector>
#include <iostream>

int main() {
    std::vector<Figure*> figures;

    std::string type;

    while (std::cin >> type) {
        if (type == "Triangle") {
            int a, b, c;
            std::cin >> a >> b >> c;
            figures.push_back(new Triangle(a, b, c));
        } else if (type == "Rectangle") {
            int a, b;
            std::cin >> a >> b;
            figures.push_back(new Rectangle(a, b));
        }
    }

    for (Figure* f : figures) {
        std::cout << f->Perimeter() << "\n";
    }

    for (Figure* f : figures) {
        delete f;
    }
}

Видно, что работа с объектами будет производиться полиморфно, через указатель на базовый класс Figure. В частности, фигуры будут удаляться через вызов delete f, где f имеет тип Figure*. Чтобы это корректно работало, в базовом классе нужно предусмотреть виртуальный деструктор.

class Figure {
public:
    virtual int Perimeter() const = 0;

    virtual ~Figure() {
    }
};


class Triangle: public Figure {
    int A, B, C;

public:
    Triangle(int x, int y, int z): A(x), B(y), C(z) {
    }

    int Perimeter() const override {
        return A + B + C;
    }
};


class Rectangle: public Figure {
    int A, B;

public:
    Rectangle(int a, int b): A(a), B(b) {
    }

    int Perimeter() const override {
        return 2 * (A + B);
    }
};

Вам даны функции SendSms и SendEmail, которые «умеют» отправлять сообщения:

#include <iostream>
#include <string>

void SendSms(const std::string& number, const std::string& message) {
    std::cout << "Send '" << message << "' to number " << number << std::endl;
}

void SendEmail(const std::string& email, const std::string& message) {
    std::cout << "Send '" << message << "' to e-mail "  << email << std::endl;
}

// Ваш код будет вставлен здесь:
#include "your_solution.h"

// Реализуйте в вашем решении классы NotifierBase, SmsNotifier и EmailNotifier,
// чтобы следующий код заработал как ожидается:

void Notify(const NotifierBase& notifier, const std::string& message) {
    notifier.Notify(message);
}

int main() {
    SmsNotifier sms("+7-495-777-77-77");
    EmailNotifier email("na-derevnyu@dedushke.ru");

    Notify(sms, "Hello! How are you?");
    Notify(email, "Let's learn C++!");
    return 0;
}

Вам нужно написать классы SmsNotifier и EmailNotifier, унаследованные от базового класса NotifierBase и переопределяющие функцию Notify, чтобы приведённый код заработал. Функция Notify в этих классах должна вызывать данные вам функции SendSms или SendEmail.

Примечания

Сдайте в систему только код классов без функции main и без уже написанных функций. Подключите все необходимые для вашей реализации библиотеки.

NotifierBase — родительский абстрактный класс, который не должен содержать функционала, у него должны быть виртуальные метод Notify и деструктор.

SmsNotifier и EmailNotifier наследуются от него и в переопределениях Notify вызывают соответствующие функции:

#include <iostream>
#include <string>

class NotifierBase {
public:
    virtual void Notify(const std::string& message) const = 0;
    virtual ~NotifierBase() {}
};

class SmsNotifier : public NotifierBase {
public:
    SmsNotifier(const std::string& number)
        : Number(number) {}

    virtual void Notify(const std::string& message) const override {
        SendSms(Number, message);
    }

private:
    const std::string Number;
};

class EmailNotifier : public NotifierBase {
public:
    EmailNotifier(const std::string& email)
        : Email(email) {}

    virtual void Notify(const std::string& message) const override {
        SendEmail(Email, message);
    }

private:
    const std::string Email;
};

Данные часто нужно сериализовывать, то есть превращать в строку. Это нужно для сохранения на диске, для отправки по сети, для передачи другому процессу. Часто для этого используются несколько общепринятых форматов данных, таких как JSON, YAML, XML. Поскольку на этапе компиляции не всегда известно, в каком именно формате надо сериализовывать данные, часто приходится прибегать к наследованию. Вам необходимо реализовать класс Serializer с чисто виртуальными методами:

void BeginArray()
void AddArrayItem(const std::string &)
void EndArray()

После этого унаследуйте от него класс JsonSerializer, определив все эти методы.

JsonSerializer должен печатать упрощенную версию JSON (https://ru.wikipedia.org/wiki/JSON), состояющую только из массивов и строк. Массив начинается с квадратной скобки. После каждого элемента, кроме последнего, должна стоять запятая. Заканчивается массив квадратной скобкой. Все строки должны быть взяты в двойные кавычки. Гарантируется, что все строки состоят только из латинских символов и пробелов, поэтому экранировать их не надо.

Сдайте в систему только код классов, без функции main. Для полной ясности формата вывода посмотрите на примеры из условия.

Пример 1

Пример 2

Пример 3

Примечания

Не надо определять для вашего класса operator <<. Печать должна происходить в функциях, указанных в условии. Мы будем работать с экземпляром вашего класса JsonSerializer полиморфно, через указатель на базовый класс Serializer. Поэтому не забудьте про виртуальный деструктор.

Из примеров понятна проблема — она кроется в запятой, которую непонятно когда ставить. Определим приватное поле isFirst. Оно будет указывать, первый ли элемент мы добавляем, и не важно, что тут назвать элементом — Array или Item. Если мы завершаем Array, то isFirst устанавливаем на false, потому что следующий элемент уже не будет первым. Аналогично с AddArrayItem. И лишь в случае BeginArray мы не должны рисовать никаких запятых. Дефолтно поле выставляем на true, так как первый Array действительно будет первым:

#include <vector>
#include <iostream>

class Serializer {
public:
    virtual void BeginArray() = 0;
    virtual void AddArrayItem(const std::string &s) = 0;
    virtual void EndArray() = 0;
    virtual ~Serializer() {}
};

class JsonSerializer : public Serializer {
public:
    void BeginArray() override {
        if (!isFirst) {
            std::cout << ",[";
        } else {
            std::cout << "[";
        }

        isFirst = true;
    }

    void AddArrayItem(const std::string& str) override {
        if (!isFirst) {
            std::cout << ",";
        }
        std::cout << "\"" << str << "\"";
        isFirst = false;
    }

    void EndArray() override {
        std::cout << "]";
        isFirst = false;
    }

private:
    bool isFirst = true;
};

Реализуйте класс AdvancedVector. Продвинутый вектор отличается от обычного тем, что позволяет обращаться по отрицательным индексам к элементам вектора в обратном порядке ( прямо как в Python). Например, vec[-1] возвращает последний элемент, vec[-2] возвращает предпоследний и так далее.

Класс AdvancedVector должен хранить элементы шаблонного типа T. Требуемый функционал не сильно отличается от стандартного std::vector:

1. Класс должен называться AdvancedVector.

2. У класса должен быть шаблонный параметр T — тип элементов.

3. У класса должен быть конструктор по умолчанию.

4. У класса должен быть конструктор копирования (возможно, предоставленный компилятором).

5. У класса должен быть шаблонный конструктор, принимающий два итератора и заполняющий вектор из данного диапазона.

6. У класса должен быть оператор присваивания (возможно, предоставленный компилятором).

7. У класса должны быть операторы сравнения == и !=.

8. У класса должны быть константные функции empty() и size().

9. У класса должны быть функции pop_back() и push_back(const T&).

10. У класса должны быть константная и неконстантная версии оператора [].

В случае положительного индекса нужно вернуть элемент с соответствующим индексом, если он меньше размера вектора. Иначе нужно бросить исключение std::out_of_range. В случае отрицательного индекса нужно вернуть элемент с соответствующим индексом, предполагая, что последний элемент имеет номер , предпоследний и так далее. Но только пока модуль индекса не превосходит size(). Если же std::abs(index) > size, то нужно бросить исключение std::out_of_range.

Формат ввода

Гарантируется, что передаваемый в operator [] индекс лежит в отрезке .

Примечания

Сдайте в систему только код класса AdvancedVector без функции main. Подключите все необходимые для вашей реализации библиотеки.

Можно было бы написать класс, в котором будет использоваться композиция со стандартным вектором:

#include <vector>

template <typename T>
class AdvancedVector {
private:
    std::vector<T> data;

public:
    // ...
};

Однако в таком классе пришлось бы заново определять все публичные операторы и функции, такие как size, empty, push_back и т. д. Попробуем поступить иначе: воспользуемся наследованием от std::vector<T>. В таком случае будет достаточно переопределить лишь оператор [], а также шаблонный конструктор и конструктор по умолчанию. Все остальные операторы и функции будут автоматически унаследованы от вектора.

#include <cstdint>
#include <vector>

template <typename T>
class AdvancedVector: public std::vector<T> {
public:
    AdvancedVector() = default;

    template <typename Iter>
    AdvancedVector(Iter first, Iter last): std::vector<T>(first, last) {
    }

    const T& operator [](std::int64_t i) const {
        if (i < 0) {
            i += this->size();
        }
        return this->at(i);
    }

    T& operator [](std::int64_t i) {
        if (i < 0) {
            i += this->size();
        }
        return this->at(i);
    }
};

В этом решении есть одна особенность. Базовый класс зависит от неизвестного заренее шаблонного параметра. Поэтому вызов функций базового класса требуется явно предварять либо префиксом с именем базового класса std::vector<T>::, либо конструкцией this->. Это позволит компилятору отложить поиск этого имени до момента инстранцирования шаблона с конкретным типом T.

Обратите внимание на реализацию оператора []. Идея в том, чтобы получить настоящий индекс элемента, а затем вызвать унаследованную от вектора функцию at. Эта функция делает проверку корректности аргумента: он должен быть меньше размера контейнера. В случае некорректного значения она сама сгенерирует требуемое исключение std::out_of_range.

Функция at принимает беззнаковый аргумент типа size_t. Если в неё передать знаковый тип, то произойдёт неявное преобразование. Например, если size_t занимает 8 байт (64 бита), то отрицательный аргумент i будет преобразован в . Покажите самостоятельно, что если после прибавления size() индекс i остался отрицательным, то аргумент функции at всё равно будет некорректным.

В решении реализованы две версии оператора [] — константная и неконстантная. Они отличаются лишь версиями функции at, которая в векторе тоже перегружена по константности.

Вам дан класс A, который в своих конструкторах и деструкторе печатает соответствующие сообщения, а так же main:

#include <iostream>

class A {
public:
    A(int x) {
        std::cout << "Constructor(int): " << x << "\n";
    }
    A(const A&) {
        std::cout << "Copy constructor\n";
    }
    virtual ~A() {
        std::cout << "Destructor\n";
    }
    virtual void foo() const = 0;
};

#include "your_code.h"

int main() {
    B b;
    const A& a = b;
    a.foo();
}

Вам требуется написать код класса B, чтобы функция main, работающая с этим классом, вывела бы следующие сообщения:

Constructor(int): 42
Destructor

Примечания

Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

Для начала давайте поймём, что происходит в main: создаётся объект типа B, константный указатель типа A на этот объект и вызывается виртуальный метод foo.

Итого имеем, класс B должен наследоваться от класса A и переопределять метод foo, так же у класса B должен быть дефолтный конструктор:

class B: public A {
public:

    B(): A(42) {}

    void foo() const override {}
};

Самой сложной задачей, что при всех этих условиях A(42) должен вызываться в конструкторе B. Но написав B () { A(42); } ничего не выходило бы. Перед входом в тело конструктора все переменные в классе должны быть инициализированы. Если вы не укажете элемент в списке инициализации конструктора, элементы будут сконструированы по умолчанию, но так как у A нет дефолтного конструктора, сделать это в теле класса нельзя.

Алексею поручили написать программу, обрабатывающую почтовые адреса.

Дана структура Address и несколько работающих с ней функций:

#include <string>

struct Address {
    std::string Country;
    std::string City;
    std::string Street;
    std::string House;
};

void Parse(const std::string& line, Address* const address);
void Unify(Address* const address);
std::string Format(const Address& address);

Функция Parse принимает на вход текстовую строчку и пытается выделить из неё компоненты адреса.

Функция Unify пытается привести компоненты адреса к каноническому виду (например, вместо «пр-д Кочновский» записать «Кочновский проезд»).

Функция Format возвращает текстовое представление адреса.

Функции Parse и Unify, в духе Google C++ style guide, принимают на вход изменяемые параметры через указатели. Предполагается, что соотвествующие объекты типа Address уже созданы.

В случае ошибок обработки адреса функции Parse и Unify могут сгенерировать исключения.

Алексей написал код обработки, но он почему-то не работает:

#include "address.h"
#include <iostream>
#include <string>

int main() {
    std::string line;
    Address* address;
    while (getline(std::cin, line)) {
        Parse(line, address);
        Unify(address);
        std::cout << Format(*address) << "\n";
    }
}

Предполагалось, что эта программа будет читать поступающие на вход строки, извлекать из них адреса и печатать их обработанные текстовые представления. В случае исключений при обработке строки программа должна напечатать просто “exception” (с переводом строки) и перейти к обработке следующих строк.

Примечания

Вам нужно исправить ошибки в коде и сдать его в систему. Код структуры Address и функций переписывать не надо: просто подключите в своей программе заголовочный файл address.h. Утечек памяти в вашей программе быть не должно.

Давайте сначала поймём, в чём фундаментальная ошибка в приведённом неправильном коде обработки. В нём декларируется указатель address, но на какое место в памяти он указывает? Указатель является примитивным базовым типом. Локальная переменная address никак не инициализируется, и в ней лежит «мусор». Она не указывает на адрес реального объекта типа Address в памяти. Но функции Parse и Unify предполагают, что переданный указатель ссылается на существующий объект.

Вторая ошибка связана с тем, что в приведённом коде никак не проверяются исключения, которые могут вылететь из функций.

Первый способ решения — создать соответствующую переменную типа Address в динамической памяти. В этом случае мы должны будем вручную следить за её временем жизни и в нужный момент удалить. Правильнее будет создавать такую переменную всякий раз перед очередным разбором адреса (хотя в условии это не требуется). Однако вот такой код не будет работать:

#include "address.h"
#include <iostream>
#include <string>

int main() {
    std::string line;
    while (getline(std::cin, line)) {
        try {
            Address* address = new Address;
            Parse(line, address);
            Unify(address);
            std::cout << Format(*address) << "\n";
            delete address;
        } catch (...) {
            std::cout << "exception\n";
        }
    }
}

Здесь при возникновении исключения мы не дойдём до вызова delete, и выделенная память утечёт. Исправим его так:

#include "address.h"
#include <iostream>
#include <string>

int main() {
    std::string line;
    while (getline(std::cin, line)) {
        Address* address = new Address;
        try {
            Parse(line, address);
            Unify(address);
            std::cout << Format(*address) << "\n";
        } catch (...) {
            std::cout << "exception\n";
        }
        delete address;
    }
}

Однако есть решение проще. Нет никакой необходимости создавать переменную именно в динамической памяти.

Вполне может подойти переменная, созданная просто на стеке. Тогда в функции Parse и Unify надо будет передать её адрес, а в функцию Format просто саму эту переменную.

#include "address.h"
#include <iostream>
#include <string>

int main() {
    std::string line;
    while (getline(std::cin, line)) {
        try {
            Address address;
            Parse(line, &address);
            Unify(&address);
            std::cout << Format(address) << "\n";
        } catch (...) {
            std::cout << "exception\n";
        }
    }
}

Здесь нам не нужно следить за временем жизни переменной: как бы мы ни покинули блок кода, локальная стековая переменная будет корректно автоматически уничтожена.

Иногда некоторые действия не получается выполнить с первого раза. Например, обращение по сети в сторонний сервис может обернуться неудачей из-за сетевых проблем или перегрузки сервиса. В таких случаях иногда пишут код, который пытается повторить такое действие несколько раз подряд.

Вам надо написать реализацию функции DoWithRetry с таким заголовком:

#include <exception>
#include <functional>
#include <optional>

template <typename Result, typename Exception = std::exception>
std::optional<Result> DoWithRetry(std::function<Result()> func,
                                  int retryCount, int sleepTime, bool throwLast);

Функция принимает на вход другую функцию без аргументов, возвращающую значение типа Result, количество повторов, таймаут между повторами и флажок throwLast.

Одним из шаблонных параметров функции является тип исключения, на которое функция реагирует. Функция должна вызвать func, и если произошло исключение указанного типа, то вызвать нашу функцию Sleep с параметром sleepTime, а затем повторить попытку (если попытки еще остались). Максимальное количество вызовов func, которое может получиться, равно retryCount + 1. Если на последней попытке происходит исключение указанного типа, и throwLast истинно, этот же объект исключения должен проброситься дальше из функции. Если же throwLast ложно, то надо просто вернуть пустой объект std::optional. Если же вызов func закончился успешно, то надо просто вернуть результат func.

Примечания

Про std::optional можно прочитать здесь. Если исключение произошло на последней попытке, то после неё «спать» не надо.

#include <exception>
#include <functional>
#include <optional>

template <typename Result, typename Exception = std::exception>
std::optional<Result> DoWithRetry(std::function<Result()> func, int retryCount, int sleepTime, bool throwLast) {
    for (int i = 0; i < retryCount + 1; ++i) {
        try {
            return func();
        } catch (const Exception&) {
            if (i == retryCount) {
                if (throwLast) {
                    throw;
                }
            } else {
                Sleep(sleepTime);
            }
        }
    }
    return {};
}

Здесь мы перехватываем потенциальные исключения, приводящиеся к типу Exception (важно ловить именно их, а не писать catch (...)). При этом сам объект исключения нам не нужен, поэтому мы его имя не указываем. При необходимости (после последней попытки при возведённом throwLast) мы перекидываем пойманное исключение дальше с помощью throw без аргументов.

Все вы знаете контейнер std::map, который сопоставляет уникальным ключам значение. Представим теперь, что мы работаем с данными, у которых бывает два типа ключей. Например, студента можно задать номером студенческого билета или логином в системе. При этом не обязательно заданы оба ключа: например, у студента может ещё не быть логина.

Вам надо написать класс BiMap, к которому можно обратиться за значением по одному из двух типов ключей. Вот заготовка для вашего класса:

#include <stdexcept>
#include <optional>

template <typename Key1, typename Key2, typename Value>
class BiMap {
public:
    // Вставить значение, указав один или оба ключа.
    // Генерирует исключение std::invalid_argument("some text") в случае,
    // если оба ключа пусты, либо один из ключей уже имеется в хранилище.
    void Insert(const std::optional<Key1>& key1, const std::optional<Key2>& key2, const Value& value);

    // Получить значение по ключу первого типа.
    // Генерирует исключение std::out_of_range("some text")
    // в случае отсутствия ключа (как и функция at в std::map).
    Value& GetByPrimaryKey(const Key1& key);
    const Value& GetByPrimaryKey(const Key1& key) const;

    // Аналогичная функция для ключа второго типа.
    Value& GetBySecondaryKey(const Key2& key);
    const Value& GetBySecondaryKey(const Key2& key) const;
};

Функция Insert пытается вставить новое значение в хранилище. Ей могут быть указаны один или оба ключа (поэтому ключи передаются через std::optional). Если оба ключа не заданы, или если один из ключей уже есть в хранилище, функция должна сгенерировать исключение std::invalid_argument с каким-либо текстовым параметром.

Функции GetByPrimaryKey и GetBySecondaryKey должны вернуть значение по ключу соответствующего типа. Они очень похожи на функцию at в std::map: в случае отстутствия ключа должна генерироваться ошибка std::out_of_range.

Вот пример тестовой программы, демонстрирующей работу этих функций:

#include "bimap.h"

#include <iostream>
#include <string>

using namespace std;

struct Student {
    string Surname, Name;
};

ostream& operator << (ostream& out, const Student& s) {
    return out << s.Surname << " " << s.Name;
}

int main() {
    BiMap<int, string, Student> bimap;  // студента можно определить либо по номеру, либо по логину
    bimap.Insert(42, {}, {"Ivanov", "Ivan"});
    bimap.Insert({}, "cshse-ami-512", {"Petrov", "Petr"});
    bimap.Insert(13, "cshse-ami-999", {"Fedorov", "Fedor"});

    cout << bimap.GetByPrimaryKey(42) << "\n";  // Ivanov Ivan

    cout << bimap.GetBySecondaryKey("cshse-ami-512") << "\n";  // Petrov Petr

    cout << bimap.GetByPrimaryKey(13) << "\n";  // Fedorov Fedor
    cout << bimap.GetBySecondaryKey("cshse-ami-999") << "\n";  // Fedorov Fedor

    // меняем значение по первичному ключу - по вторичному оно тоже должно измениться
    bimap.GetByPrimaryKey(13).Name = "Oleg";

    cout << bimap.GetByPrimaryKey(13) << "\n";  // Fedorov Oleg
    cout << bimap.GetBySecondaryKey("cshse-ami-999") << "\n";  // Fedorov Oleg
    return 0;
}

Примечания

Вы можете воспользоваться контейнером std::map для реализации класса (в частности, можно считать, что на ключах определён operator <).

Сдайте в систему только код класса BiMap без функции main. Подключите все необходимые для вашей реализации библиотеки.

Давайте заметим, что вот такое решение нам не подойдёт:

template <typename Key1, typename Key2, typename Value>
class BiMap {
    std::map<Key1, Value> map1;
    std::map<Key2, Value> map2;
};

В этом решении значения в map1 и map2 никак не зависят друг от друга. Если мы обратимся к значению по первому ключу и поменяем его, а потом прочитаем значение по второму ключу, то мы не увидим изменений.

Поэтому нужно, чтобы значения хранились где-то отдельно в одном экземпляре, а отображения из ключей ссылались бы на них. Например, можно сохранять значения в контейнере, а ключи отображать в индексы:

template <typename Key1, typename Key2, typename Value>
class BiMap {
    std::deque<Value> values;
    std::map<Key1, size_t> map1;
    std::map<Key2, size_t> map2;
};

Индексы можно было бы заменить на итераторы, если выбраны контейнеры deque или list, но для контейнера vector итераторы использовать не получится: при добавлении новых элементов в вектор может произойти реаллокация, и старые итераторы будут инвалидированы.

Другое решение не использует отдельного хранилища значений. Вместо этого значения создаются в динамической памяти. Чтобы не думать о том, кто и в какой момент должен освобождать эту память, можно обернуть их в умный указатель. Так как на значение может быть две ссылки, то нужно использовать умный указатель shared_ptr. Рассмотрим это решение подробнее.

#include <map>
#include <memory>
#include <optional>
#include <stdexcept>

template <typename Key1, typename Key2, typename Value>
class BiMap {
private:
    std::map<Key1, std::shared_ptr<Value>> map1;
    std::map<Key2, std::shared_ptr<Value>> map2;

public:
    void Insert(
        const std::optional<Key1>& key1,
        const std::optional<Key2>& key2,
        const Value& value
    ) {
        if (!key1.has_value() && !key2.has_value()) {
            throw std::invalid_argument("Both keys are empty");
        }

        auto shared = std::make_shared<Value>(value);

        if (key1.has_value() && map1.find(*key1) != map1.end()) {
            throw std::invalid_argument("Key already exists");
        }

        if (key2.has_value() && map2.find(*key2) != map2.end()) {
            throw std::invalid_argument("Key already exists");
        }

        if (key1.has_value()) {
            map1[*key1] = shared;
        }

        if (key2.has_value()) {
            map2[*key2] = shared;
        }
    }

    Value& GetByPrimaryKey(const Key1& key) {
        return *map1.at(key);
    }

    const Value& GetByPrimaryKey(const Key1& key) const {
        return *map1.at(key);
    }

    Value& GetBySecondaryKey(const Key2& key) {
        return *map2.at(key);
    }

    const Value& GetBySecondaryKey(const Key2& key) const {
        return *map2.at(key);
    }
};

Здесь вместо if (key.has_value()) можно было бы просто написать if (key). В Get-функциях мы не проверяем наличие ключа: при его отсутствии вызываемая функция at сама сгенерирует исключение нужного типа.

Также обратите внимание на порядок проверок и присваивания. Писать map1[*key1] = shared; сразу после того, как мы проверили map1.find(*key1) нельзя, ведь ошибка может встретиться в key2.

Вася хочет иметь возможность в конце работы своей функции выводить сообщение, что функция завершила работу. На практике исполнение функции может завершиться разными способами:

• Может быть несколько операторов return.

• Может вылететь исключение из какой-нибудь вызываемой функции.

С учетом этих обстоятельств у Василия получается раздутый код:

#include <iostream>

int Function() {
    int value = 1;
    try {
        value = SomeFunction();
        if (value == 0) {
            std::cout << "Function completed\n";
            return value;
        }

        value = SomeOtherFunction();
        if (value == 0) {
            std::cout << "Function completed\n";
            return value;
        }

        value = FinalFunction();  // might throw an exception
    } catch (...) {
        std::cout << "Function completed\n";
        throw;  // throws the exception further.
    }

    std::cout << "Function completed\n";
    return value;
}

Вместо этого Василий хотел бы не заниматься копированием одного и тоже же кода. Помогите Василию и реализуйте класс LoggerGuard, который принимает строку и печатает её во время выхода из функции. С использованием этого класса код Василия станет таким:

#include <iostream>

int Function() {
    LoggerGuard logger("Function completed");

    int value = 1;
    try {
        value = SomeFunction();
        if (value == 0) {
            return value;
        }

        value = SomeOtherFunction();
        if (value == 0) {
            return value;
        }

        value = FinalFunction();  // might throw an exception
    } catch (...) {
        throw;  // throws the exception further.
    }

    return value;
}

Класс LoggerGuard должен содержать следующий конструктор:

LoggerGuard(const std::string& message, std::ostream& out = std::cout);

Здесь message — сообщение, печатаемое перед выходом из функции, а out — поток, в который надо печатать сообщение. Учтите, что это сообщение не обязано содержать символ перевода строки и вам нужно всегда при выводе самим добавлять \n в конце.

LoggerGuard должен быть классом, в конструкторе которого запоминается сообщение и поток, а в деструкторе оно печатается. Тогда для печати сообщения при любом выходе из функции достаточно будет создать локальную переменную типа LoggerGuard. Как бы мы ни покинули функцию, её деструктор будет вызван автоматически. Эта идея повсеместно используется в C++.

#include <iostream>
#include <string>

class LoggerGuard {
private:
    std::string Message;
    std::ostream& Out;
public:
    LoggerGuard(const std::string& message, std::ostream& out = std::cout):
        Message(message), Out(out)
    {
    }

    ~LoggerGuard() {
        Out << Message << "\n";
    }
};

Мы не можем скопировать поток вывода в новую переменную (у класса std::ostream нет конструктора копирования). Для этого мы запоминаем поток по ссылке. Так как ссылка должна быть сразу же проинициализирована при создании объекта, то мы пользуемся специальным синтаксисом для инициализации полей класса до входа в тело конструктора.

Другой способ — хранить в классе указатель на поток:

#include <iostream>
#include <string>

class LoggerGuard {
private:
    std::string Message;
    std::ostream* Out;
public:
    LoggerGuard(const std::string& message, std::ostream& out = std::cout) {
        Message = message;
        Out = &out;
    }

    ~LoggerGuard() {
        *Out << Message << "\n";
    }
};

Коля пишет класс «Дерево». Узел дерева может хранить целое число, а также знает о своём родителе и о своих потомках. У узла есть функция AddChild для добавления потомка с заданным числовым значением, а также функция Print для красивой печати поддерева начиная с этого узла.

Вот что получилось у Коли:

#include <iostream>
#include <vector>

class TreeNode {
private:
    int value;
    TreeNode* root = nullptr;
    std::vector<TreeNode*> children;

public:
    TreeNode(int val): value(val) {
    }

    TreeNode(const TreeNode&) = delete;
    TreeNode& operator=(const TreeNode&) = delete;

    TreeNode* AddChild(int child_value) {
        auto node = new TreeNode(child_value);
        node->root = this;
        children.push_back(node);
        return node;
    }

    void Print(int depth = 0) const {
        for (int i = 0; i < depth; ++i) {
            std::cout << " ";
        }
        std::cout << "- " << value << "\n";
        for (const auto& child : children) {
            child->Print(depth + 1);
        }
    }
};

Использоваться этот класс будет примерно так:

#include "tree.h"

int main() {
    TreeNode root(1);

    auto left_son = root.AddChild(10);
    auto middle_son = root.AddChild(20);
    auto right_son = root.AddChild(30);

    left_son->AddChild(100);
    left_son->AddChild(200);

    root.Print();
}

Однако эта работающая на первый взгляд тестовая программа падает, если её собрать с адресным санитайзером. Исправьте код класса TreeNode, чтобы решить эту проблему.

Примечания

Сдайте в систему только код класса TreeNode без функции main. Подключите все необходимые для вашей реализации библиотеки.

В решении Коли утекает память. В этом легко убедиться: узлы дерева создаются с помощью new, но нигде не удаляются.

Самым простым решением было бы дописать деструктор в конце класса:

~TreeNode() {
    for (TreeNode* child : children) {
        delete child;
    }
}

Этот деструктор будет работать рекурсивно: вызов delete child приведёт к вызову деструктора для child и последующему освобождению памяти.

Рассмотрим другое решение, использующее unique_ptr вместо голого указателя для хранения дочерних узлов. Тут важно не перестараться: типичная ошибка новичка — обернуть в unique_ptr ещё и поле root. Здесь родитель владеет дочерними узлами, а не наоборот.

#include <iostream>
#include <memory>
#include <string>
#include <vector>

struct TreeNode {
private:
    int value;
    TreeNode* root = nullptr;
    std::vector<std::unique_ptr<TreeNode>> children;

public:
    TreeNode(int val): value(val) {
    }

    TreeNode(const TreeNode&) = delete;
    TreeNode& operator=(const TreeNode&) = delete;

    TreeNode* AddChild(int child_value) {
        children.push_back(std::make_unique<TreeNode>(child_value));
        children.back()->root = this;
        return children.back().get();
    }

    void Print(int depth = 0) const {
        for (int i = 0; i < depth; ++i) {
            std::cout << " ";
        }
        std::cout << "- " << value << "\n";
        for (const auto& child : children) {
            child->Print(depth + 1);
        }
    }
};

В таком решении деструктор уже не нужен: в любом случае будет автоматически вызван деструктор для вектора children, который вызовет деструкторы для своих элементов типа unique_ptr<TreeNode>, которые, в свою очередь, и вызовут delete.

Вася разрабатывает новую систему для проведения олимпиад по программированию. Ему поручено разработать класс Monitor, хранящий результаты участников по каждой задаче. Этот класс должен уметь очень быстро возвращать текущие результаты отдельного участника, команды и общие результаты — ведь во время финального этапа на сервис будет приходить большая нагрузка. Каждый может наблюдать в мониторе только за интересующим его срезом — например, только за одной командой.

Васе уже дан готовый класс ParticipantResults, описывающий результаты одного участника:

#include <map>
#include <string>

struct ParticipantResults {
    std::string login;
    std::string team;
    std::map<std::string, int> scores;  // номер задачи -> баллы

    // ...

    ParticipantResults(const std::string& l, const std::string& te): login(l), team(te) {
    }

    ParticipantResults(const ParticipantResults&) = delete;
    ParticipantResults& operator = (const ParticipantResults&) = delete;
};

Его изменить вы не можете. Класс может быть «тяжёлым» в инициализации и копировании. Чтобы не создавались лишние копии этого класса, его конструктор копирования и оператор присваивания вообще удалены.

В классе Monitor, который пишет Вася, должны быть следующие функции:

1. RegisterParticipant(const std::string& login, const std::string& team) — регистрирует участника в указанной команде и возвращает (в каком-то виде) созданный для него ParticipantResults. Если участник с таким логином уже зарегистрирован, то выбрасывает исключение std::invalid_argument.

2. GetParticipantResults(const std::string& login) — получает (в каком-то виде) ParticipantResults для данного участника. Если такого логина нет, выкидывает std::out_of_range. Должна быть константная версия (для отрисовки результатов) и неконстантная (для обновлений результатов после очередной посылки).

3. GetTeamResults(const std::string& team) const — возвращает (в каком-то виде) контейнер из ParticipantResults для данной команды. Если такой команды нет, выкидывает std::out_of_range.

4. GetAllResults() const — возвращает (в каком-то виде) контейнер всех результатов.

Использоваться этот класс будет примерно так:

#include "participant_results.h"
#include "monitor.h"

#include <iostream>

int main() {
    Monitor monitor;

    {
        auto ptr = monitor.RegisterParticipant("Ivanov Ivan", "201-1");
        ptr->scores["A"] = 10;
        ptr->scores["B"] = 8;
    }

    {
        auto ptr = monitor.RegisterParticipant("Petrov Petr", "201-2");
        ptr->scores["A"] = 5;
        ptr->scores["C"] = 10;
    }

    auto ptr = monitor.GetParticipantResults("Ivanov Ivan");
    ptr->scores["Q"] = 100;

    // тут может быть аналогичный вызов monitor.GetTeamResults(team)
    for (const auto& result : monitor.GetAllResults()) {
        std::cout << result->login << "\t" << result->team << "\t";
        for (const auto& [problemId, score] : result->scores) {
            std::cout << problemId << ": " << score << "\t";
        }
        std::cout << "\n";
    }
}

Вася решил, что будет хранить вектор указателей на результаты для каждой команды и общие результаты. Указатели позволят ему сделать результаты «общими» в каждом из этих векторов и не составлять такие векторы заново при каждом вызове функций GetTeamResults или GetAllResults. Вот заготовка Васи:

#include <map>
#include <stdexcept>
#include <string>
#include <vector>

class Monitor {
private:
    // удобные псевдонимы типов для краткости:
    using Ptr = ParticipantResults*;
    using ConstPtr = const ParticipantResults*;

    std::map<std::string, Ptr> byParticipant;
    std::map<std::string, std::vector<ConstPtr>> byTeam;
    std::vector<ConstPtr> allResults;

public:
    Monitor() = default;
    Monitor(const Monitor&) = delete;
    Monitor& operator=(const Monitor&) = delete;

    Ptr RegisterParticipant(const std::string& login, const std::string& team) {
        if (byParticipant.contains(login)) {
            throw std::invalid_argument("Participant is already registered");
        }
        // Добавить новую запись об участнике и вернуть её
    }

    Ptr GetParticipantResults(const std::string& login) {
        return byParticipant.at(login);
    }

    ConstPtr GetParticipantResults(const std::string& login) const {
        return byParticipant.at(login);
    }

    std::vector<ConstPtr> GetTeamResults(const std::string& team) const {
        return byTeam.at(team);
    }

    std::vector<ConstPtr> GetAllResults() const {
        return allResults;
    }
};

Сдайте свою версию класса Monitor. Вам нужно дописать функцию RegisterParticipant и, если потребуется, ещё что-то. Вы можете выбрать реализацию Васи, а можете заменить её на свою, если хотите.

Примечания

В вашей программе не должно быть функции main. Сдайте в систему только код класса Monitor. Подключите необходимые заголовочные файлы. Класс ParticipantResults подключать или объявлять не нужно: мы его подключим сами. Напоминаем, что обычный указатель можно всегда передать туда, где ожидается указатель на константу, но не наоборот.

Заметим сразу, что необходимые исключения из функций GetParticipantResults и GetTeamResults и так уже пробрасываются: при отсутствии ключа std::map::at сгенерирует исключение std::out_of_range. Поэтому никаких проверок тут дописывать не надо.

Самое простое решение — создавать объекты класса ParticipantResults в динамической памяти и класть в контейнеры указатели.

Ptr RegisterParticipant(const std::string& login, const std::string& team) {
    if (byParticipant.contains(login)) {
        throw std::invalid_argument("Participant is already registered");
    }

    ParticipantResults* ptr = new ParticipantResults(login, team);
    allResults.push_back(ptr);
    byParticipant[login] = ptr;
    byTeam[team].push_back(ptr);
}

При таком подходе получится утечка памяти, так как деструктор вектора allResults ничего не будет делать с голыми указателями. Поэтому здесь необходимо реализовать ещё и свой собственный деструктор:

~Monitor() {
    for (auto ptr : allResults) {
        delete ptr;
    }
}

Более правильное и безопасное решение — использовать умные указатели. Так как на один и тот же объект ParticipantResults мы будем ссылаться из разных мест, то std::unique_ptr нам не подойдёт, и нужно использовать std::shared_ptr (не забудем подключить заголовочный файл <memory>). Меняем псевдонимы типов Ptr и ConstPtr:

using Ptr = std::shared_ptr<ParticipantResults>;
using ConstPtr = std::shared_ptr<const ParticipantResults>;

Важно не спутать умный указатель на константу и const std::shared_ptr<ParticipantResults>.

Дописываем функцию RegisterParticipant:

Ptr RegisterParticipant(const std::string& login, const std::string& team) {
    if (byParticipant.contains(login)) {
        throw std::invalid_argument("Participant is already registered");
    }

    Ptr ptr = std::make_shared<ParticipantResults>(login, team);
    allResults.push_back(ptr);
    byParticipant[login] = ptr;
    byTeam[team].push_back(ptr);
    return ptr;
}

Всю работу по очистке памяти shared_ptr сделает за нас, поэтому деструктор тут не нужен. Когда объект типа Monitor будет умирать, то будут автоматически вызваны деструкторы вектора и map'ов, каждый из которых позовёт деструктор для хранящихся там shared_ptr. Деструктор shared_ptr будет уменьшать счётчик ссылок на объект, и когда этот счётчик дойдёт до нуля — автоматически вызовет delete.

Вам дан класс A и функция main():

#include <iostream>
#include <memory>

class A {
public:
    A(int x) {
        std::cout << "Constructor(int): " << x << "\n";
    }
    A(const A&) {
        std::cout << "Copy constructor\n";
    }
    virtual ~A() {
        std::cout << "Destructor\n";
    }
    virtual void foo() const {
        std::cout << "A::foo()\n";
    }
};

#include "your_code.h"

int main() {
    std::unique_ptr<A> ptr(new B);
    ptr->foo();
}

Напишите такой код класса B, чтобы функция main() вывела бы сообщения:

Constructor(int): 42
Constructor(int): 17
A::foo()
Destructor
Destructor

Примечания

Не пытайтесь вывести нужный текст с помощью непосредственной печати: мы при проверке всё равно заменяем отладочные сообщения в классе на свои.

Из строчки std::unique_ptr<A> ptr(new B) становится понятно, что тип B* должен приводиться к типу A*. Это возможно, если, например, B является наследником класса A.

Ещё мы видим, что при инициализации объекта типа B должны сконструироваться два объекта типа A с аргументами 42 и 17. Про один из них мы знаем: это должен быть подобъект базового класса, который неявно вкладывается в B при наследовании. А вот второй объект можно принести, например, в виде композиции. В конструкторе класса B важно проинициализировать объекты нужными аргументами: сначала подобъект базового класса, затем — поле.

class B: public A {
    A field;
public:
    B(): A(42), field(17) {
    }
};

Вы работаете с иерархией классов, описывающих животных:

#include <string>

class Animal {
public:
    virtual std::string Voice() const {
        return "Not implemented yet";
    }
    virtual ~Animal() {
    }
};

class Tiger: public Animal {
    std::string Voice() const override {
        return "Rrrr";
    }
};

class Wolf: public Animal {
    std::string Voice() const override {
        return "Wooo";
    }
};

class Fox: public Animal {
    std::string Voice() const override {
        return "Tyaf";
    }
};

Вам нужно определить тип Zoo, представляющий из себя набор различных животных, и написать две функции: Zoo CreateZoo() и void Process(const Zoo& zoo).

Функция CreateZoo должна читать слова из стандартного ввода. Если на вход поступают слова Tiger, Wolf или Fox, она должна поместить соответствующего зверя в зоопарк. Если на вход поступает другое слово, она должна прекратить чтение и сгенерировать исключение std::runtime_error.

Функция Process должна перебрать всех зверей в зоопарке в порядке создания и напечатать для каждого из них результат работы виртуальной функции Voice.

Ваш коллега написал вот такой код, но он почему-то не работает:

#include <iostream>
#include <stdexcept>
#include <vector>

#include "animals.h"

using Zoo = std::vector<Animal>;

Zoo CreateZoo() {
    Zoo zoo;
    std::string word;
    while (std::cin >> word) {
        if (word == "Tiger") {
            Tiger t;
            zoo.push_back(t);
        } else if (word == "Wolf") {
            Wolf w;
            zoo.push_back(w);
        } else if (word == "Fox") {
            Fox f;
            zoo.push_back(f);
        } else
            throw std::runtime_error("Unknown animal!");
    }
    return zoo;
}

void Process(const Zoo& zoo) {
    for (const auto& animal : zoo) {
        std::cout << animal.Voice() << "\n";
    }
}

Исправьте его и сдайте в систему.

Примечания

Код классов из файла animals.h переписывать не надо, просто подключите заголовочный файл animals.h. Обратите внимание, что в нашей версии файла animals.h голоса зверей могут отличаться от того, что приведено в примере. Разумеется, в вашей программе не должно быть утечек памяти. Экземпляр каждого зверя надо создавать ровно один раз (если вам на входе даны два волка, то надо создать ровно два объекта типа Wolf, не больше и не меньше).

Давайте поймём, почему использовать std::vector<Animal> в качестве Zoo неправильно. Вектор хранит копии элементов, которые мы туда кладём. Эти копии будут иметь базовый тип Animal и ничего не будут знать про исходный тип объекта.

Поэтому в конструкции

Tiger t;
zoo.push_back(t);

будет взята так называемая срезка: от тигра скопируется только подобъект базового класса Animal. Конечно же, вызов Voice для таких элементов вектора приведёт к вызову функции Animal::Voice, которая напечатает Not implemented yet.

Использовать вектор ссылок нельзя, так как ссылка с самого начала должна быть к чему-то привязана. Можно воспользоваться вектором указателей на Animal и создавать объекты в динамической памяти. Но тогда придётся вручную следить за их временем жизни. Самым правильным вариантом было бы создать вектор умных указателей std::unique_ptr<Animal>: при уничтожении самого вектора автоматически вызвались бы деструкторы для его элементов, которые освободили бы занимаемую динамическую память.

Для создания нового объекта в динамической памяти и оборачивания указателя на него в unique_ptr удобно использовать функцию make_unique:

#include <string>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <vector>

#include "animals.h"

using Zoo = std::vector<std::unique_ptr<Animal>>;

Zoo CreateZoo() {
    Zoo zoo;
    std::string word;
    while (std::cin >> word) {
        if (word == "Tiger") {
            zoo.push_back(std::make_unique<Tiger>());
        } else if (word == "Wolf") {
            zoo.push_back(std::make_unique<Wolf>());
        } else if (word == "Fox") {
            zoo.push_back(std::make_unique<Fox>());
        } else {
            throw std::runtime_error("Unknown animal!");
        }
    }
    return zoo;
}

void Process(const Zoo& zoo) {
    for (const auto& animal : zoo) {
        std::cout << animal->Voice() << "\n";
    }
}

Представим арифметическое выражение, содержащее числовые константы и операции сложения и умножения, в виде дерева. В листьях этого дерева будут находиться константы, а в промежуточных узлах — операции. Вам дан абстрактный базовый класс Expression, представляющий из себя такое дерево:

#include <iostream>
#include <memory>
#include <string>

class Expression {
public:
    virtual int Evaluate() const = 0;
    virtual std::string ToString() const = 0;
    virtual ~Expression() {}
};

using ExpressionPtr = std::shared_ptr<Expression>;

#include "your_code.h"

int main() {
    ExpressionPtr ex1 = Sum(Product(Const(3), Const(4)), Const(5));
    std::cout << ex1->ToString() << "\n";  // 3 * 4 + 5
    std::cout << ex1->Evaluate() << "\n";  // 17

    ExpressionPtr ex2 = Product(Const(6), ex1);
    std::cout << ex2->ToString() << "\n";  // 6 * (3 * 4 + 5)
    std::cout << ex2->Evaluate() << "\n";  // 102
}

Вам надо унаследовать от него классы-наследники для констант, операции сложения и операции умножения так, чтобы приведённый в функции main код (и аналогичные примеры) заработали.

Функции базового класса Evaluate и ToString должны переопределяться в классах-наследниках. Evaluate должна вычислять выражение, а ToString возвращать его текстовую запись (как в примере). При умножении на сумму запись суммы должна браться в скобки. Никаких особых специальных правил оформления нулевых или единичных множителей писать не нужно.

Примечания

Кроме классов-наследников, Вам надо будет определить функции Const, Sum и Product, которые используются в функции main в примере. Лишних копирований дерева быть не должно: мы будем проверять, что создано ровно столько экземпляров классов, сколько требуется для построения дерева. Разумеется, утечек памяти тоже не должно быть.

Для преобразования чисел в строки используете функцию std::to_string.

class ConstExpr: public Expression {
private:
    int value;

public:
    ConstExpr(int v): value(v) {}

    int Evaluate() const override {
        return value;
    }
    std::string ToString() const override {
        return std::to_string(value);
    }
};

class BinaryOperation: public Expression {
protected:
    ExpressionPtr left;
    ExpressionPtr right;

public:
    BinaryOperation(ExpressionPtr l, ExpressionPtr r): left(l), right(r) {}
};

class SumExpr: public BinaryOperation {
public:
    SumExpr(ExpressionPtr l, ExpressionPtr r): BinaryOperation(l, r) {}

    int Evaluate() const override {
        return left->Evaluate() + right->Evaluate();
    }

    std::string ToString() const override {
        return left->ToString() + " + " + right->ToString();
    }
};

class ProductExpr: public BinaryOperation {
private:
    static std::string Parentheses(ExpressionPtr ex) {
        if (dynamic_cast<SumExpr*>(ex.get())) {
            return std::string("(") + ex->ToString() + ")";
        } else {
            return ex->ToString();
        }
    }
public:
    ProductExpr(ExpressionPtr l, ExpressionPtr r): BinaryOperation(l, r) {}

    int Evaluate() const override {
        return left->Evaluate() * right->Evaluate();
    }

    std::string ToString() const override {
        return Parentheses(left) + " * " + Parentheses(right);
    }
};

ExpressionPtr Const(int x) {
    return ExpressionPtr(new ConstExpr(x));
}

ExpressionPtr Sum(ExpressionPtr l, ExpressionPtr r) {
    return ExpressionPtr(new SumExpr(l, r));
}

ExpressionPtr Product(ExpressionPtr l, ExpressionPtr r) {
    return ExpressionPtr(new ProductExpr(l, r));
}

Главная сложность здесь — понять, когда надо ставить скобки вокруг суммы в произведении. Для этого надо понять, является ли подвыражение именно суммой. К сожалению, базовый класс Expression нам недоступен для изменений (иначе можно было бы внести в него виртуальную функцию NeedParantheses). Поэтому можно воспользоваться конструкцией dynamic_cast, которая в runtime пытается привести указатель на базовый класс к указателю на производный тип (и возвращает nullptr, если это невозможно).

Эта конструкция работает только для иерархий с виртуальными функциями в базовом классе. В нашем примере она используется в функции ProductExpr::Parentheses.

Вам дан класс Document, от которого унаследованы два класса( PlainTextDocument и HTMLDocument), определён тип DocumentCollection, и написаны две функции (AddDocument и PrintCollection):

#include <iostream>
#include <string>
#include <vector>

class Document {
private:
    const std::string Content;
public:
    Document(const std::string& s): Content(s) {}
    void Save() const {
    }
};

class PlainTextDocument: public Document {
public:
    PlainTextDocument(const std::string& s): Document(s) {}
    virtual void Save() {
        std::cout << Content << "\n";
    }
};

class HTMLDocument: public Document {
public:
    HTMLDocument(const std::string& s): Document(s) {}
    virtual void Save() {
        std::cout << "<HTML><BODY>" << Content << "</BODY></HTML>\n";
    }
};

using DocumentCollection = std::vector<Document>;

void AddDocument(const std::string& content, const std::string& type, DocumentCollection& collection) {
    if (type == "plain") {
        collection.push_back(PlainTextDocument(content));
    } else if (type == "html") {
        collection.push_back(HTMLDocument(content));
    }
}

void PrintCollection(const DocumentCollection& collection) {
    for (const auto& doc : collection) {
        doc.Save();
    }
}

Однако этот код не компилируется, а если исправить ошибки компиляции, то эти функции почему-то работают совсем не так, как задумано. Вам надо исправить этот код. Требования к нему такие:

• Иерархия классов должна сохраниться: PlainTextDocument и HTMLDocument должны быть наследникамии Document.

• Функциия Save в классе Document должна вести себя полиморфно.

• Тип DocumentCollection должен быть вектором (какого-то типа).

• Сигнатуры функций AddDocument и PrintCollection должны сохраниться. Второй параметр функции AddDocument может принимать значения "plain" или "html".

• Утечек памяти быть не должно.

Для начала найдём ошибки: virtual ставится у переопределяемого метода в родительском классе, также у родительского класса должен быть виртуальный деструктор.

Если мы хотим хранить объекты разных типов в одном контейнере, то надо хранить указатель на их родительский класс. Воспользуемся умным указателем std::unique_ptr, в таком случае нам дополнительно не надо думать про удаление объектов из нашего вектора и утечек не будет:

#include <iostream>
#include <memory>
#include <string>
#include <vector>

class Document {
protected:
    const std::string Content;
public:
    Document(const std::string& s): Content(s) {}
    virtual void Save() const {}
    virtual ~Document() {}
};

class PlainTextDocument: public Document {
public:
    PlainTextDocument(const std::string& s): Document(s) {}
    void Save() const override {
        std::cout << Content << "\n";
    }
};

class HTMLDocument: public Document {
public:
    HTMLDocument(const std::string& s): Document(s) {}
    void Save() const override {
        std::cout << "<HTML><BODY>" << Content << "</BODY></HTML>\n";
    }
};

using DocumentCollection = std::vector<std::unique_ptr<Document>>;

void AddDocument(const std::string& content, const std::string& type, DocumentCollection& collection) {
    if (type == "plain") {
        collection.emplace_back(new PlainTextDocument(content));
    } else if (type == "html") {
        collection.emplace_back(new HTMLDocument(content));
    }
}

void PrintCollection(const DocumentCollection& collection) {
    for (const auto& doc : collection) {
        doc->Save();
    }
}

Ваш друг пишет свою реализацию шаблонного класса «Матрица»:

#include <iostream>

template <typename T>
class Matrix {
private:
    T** data;
    size_t rows, columns;

public:
    Matrix(size_t m, size_t n): rows(m), columns(n) {
        data = new T * [rows];
        size_t i = 0;
        try {
            for (; i != rows; ++i) {
                data[i] = new T[columns];
            }
        } catch (...) {
            for (size_t k = 0; k != i; ++k) {
                delete [] data[k];
            }
            delete [] data;
            throw;
        }
    }

    T* operator [](size_t i) {
        return data[i];
    }
    const T* operator [](size_t i) const {
        return data[i];
    }

    size_t GetRows() const {
        return rows;
    }

    size_t GetColumns() const {
        return columns;
    }

    ~Matrix() {
        for (size_t i = 0; i != rows; ++i) {
            delete [] data[i];
        }
        delete [] data;
    }

    // Сюда можно будет вставить ваш код
    #include "your_code.h"
};

template <typename T>
Matrix<T> FillMatrix(size_t m, size_t n) {
    Matrix<T> A(m, n);
    for (size_t i = 0; i != m; ++i) {
        for (size_t j = 0; j != n; ++j) {
            A[i][j] = i + j;
        }
    }
    return A;
}

template <typename T>
std::ostream& operator << (std::ostream& out, const Matrix<T>& A) {
    for (size_t i = 0; i != A.GetRows(); ++i) {
        for (size_t j = 0; j != A.GetColumns(); ++j) {
            out << A[i][j] << " ";
        }
        out << "\n";
    }
    return out;
}

Правда, он зачем-то выбрал очень странную реализацию матрицы на основе двумерного динамического массива, а не вектора. Однако вы можете быть уверенными, что инициализацию и освобождение динамической памяти для отдельно взятой матрицы ваш друг написал правильно.

Пока в классе есть только конструктор, деструктор и оператор []. Ещё ваш друг написал функцию FillMatrix, возвращающую матрицу, заполненную особым образом, а также оператор << для печати матрицы на экране.

Но почему-то вот такой простой код не работает:

#include "matrix.h"
#include <iostream>

int main() {
    size_t m, n;
    std::cin >> m >> n;
    Matrix<int> A(m, n);
    // ...
    A = FillMatrix<int>(m, n);
    std::cout << A << "\n";
}

Вам нужно добиться, чтобы он заработал. Вы можете только дописывать что-то к классу Matrix в месте #include "your_code.h".

Примечания

Мы компилируем эту программу с дополнительной опцией компилятора %%-fno-elide-constructors%%, которая отменяет copy elision и требует вызова конструктора при возврате значения из функции.

В классе Matrix не написан оператор присваивания. Поэтому компилятор неявно предоставил по умолчанию свою версию этого оператора. Эта версия просто копирует все поля как есть. Она могла бы выглядеть так:

Matrix& operator = (const Matrix& other) {
    data = other.data;
    rows = other.rows;
    columns = other.columns;
    return *this;
}

Видно, что здесь происходит неглубокое копирование: копируется просто сам указатель data, но не копируются сами данные.

Этот оператор вызывается в строке A = FillMatrix<int>(m, n);. В результате получается, что два объекта типа Matrix<int> содержат указатель на одни и те же данные: это временный объект с результатом работы функции, и изменённый A. Каждый из них уверен, что является ответственным за удаление памяти. Сначала умирает временный объект и в своём деструкторе освобождает память, на которую ссылается data. Далее либо A попытается использовать эту память, либо сам умрёт и попытается освободить её повторно. В любом случае это приведёт к неопределённому поведению программы.

Рассмотрим способы решения проблемы.

1. Можно было бы хранить данные матрицы в подходящем контейнере (например, векторе векторов). Тогда при копировании или присваивании матрицы будет вызван конструктор копирования вектора, который сделает глубокую копию. Этот способ предпочтителен, но мы не можем им воспользоваться: по условию задачи мы можем лишь дописывать новые функции в классе.

2. Можно было бы сделать глубокие конструктор копирования и оператор присваивания, выделяющие память под новую матрицу и копирующие туда элементы старой матрицы. На самом деле это сложно и не нужно, потому что есть третий способ.

3. Можно запретить копирование и присваивание матриц в общем случае! Но чтобы пример заработал, можно разрешить его только для случаев, когда справа стоит временный (безымянный) объект. Например, таковым является результат, возвращаемый из функции. Такой объект живёт только пока вычисляется выражение с присваиванием, а потом сразу умирает. Поэтому у него можно просто отобрать владение матрицей, оставив его в согласованном, но пустом состоянии.

Напишем реализацию третьего способа. Нам было бы достаточно определить только оператор присваивания для временного объекта, но всегда следует переопределять в паре с ним и конструктор.

Начнём с конструктора. Запрещаем автогенерацию конструктора копирования в общем случае, но делаем особую версию для случая, когда на вход приходит временный объект:

Matrix(const Matrix&) = delete;

Matrix(Matrix&& other) {
    data = other.data;
    rows = other.rows;
    columns = other.columns;
    other.data = nullptr;
    other.rows = 0;
    other.columns = 0;
}

Теперь сделаем то же самое для оператора присваивания. В отличие от конструктора, здесь левая часть (текущий объект) уже существует. Проще всего будет обменяться содержимым с временным объектом. Тогда этот временный объект в своём деструкторе как раз похоронит эти данные.

Matrix& operator = (const Matrix&) = delete;

Matrix& operator = (Matrix&& other) {
    std::swap(data, other.data);
    std::swap(rows, other.rows);
    std::swap(columns, other.columns);
    return *this;
}

Заметки

В этой задаче прошло бы и решение с глубоким копированием данных. Но его дольше писать, и в нём проще ошибиться.

Давайте разберёмся, например, почему приведённый в условии конструктор выглядит так сложно. С аналогичными сложностями придётся столкнуться и при написании глубокого конструктора копирования.

Почему, например, конструктор из условия не написан просто так?

Matrix(size_t m, size_t n): rows(m), columns(n) {
    data = new T * [rows];
    for (size_t i = 0; i != rows; ++i) {
        data[i] = new T[columns];
    }
}

Если из конструктора вылетает исключение, то объект не считается созданным, и к нему не будет применяться деструктор (но он будет применяться ко всем полям создаваемого объекта). Все выделенные к этому моменту ресурсы код конструктора должен подчистить сам. Исключение может произойти в следующих местах:

1. Его может сгенерировать new, если не хватит памяти;

2. Его может сгенерировать конструктор неизвестного нам типа T, который вызывается внутри new;

В первом new проблем не возникает: сам new действует как транзакция, и если в нём произойдёт сбой, то утечки не будет. Проблема будет, если сбой произойдёт в последующих new. Память, выделенную ранее, придётся подчистить, а исключение перебросить дальше, чтобы объект матрицы не был создан. Это делается в блоке catch просто с помощью throw:

Matrix(size_t m, size_t n): rows(m), columns(n) {
    data = new T * [rows];
    size_t i = 0;
    try {
        for (; i != rows; ++i) {
            data[i] = new T[columns];
        }
    } catch (...) {
        for (size_t k = 0; k != i; ++k) {
            delete [] data[k];
        }
        delete [] data;
        throw;
    }
}

Заметим, что проблема возникает из-за того, что наш класс владеет сразу несколькими низкоуровневыми массивами. Идиома RAII предлагает каждый из таких ресурсов оборачивать в отдельный класс-обёртку. Нам в качестве такой обёртки подошел бы просто std::vector.