6 - Наследование. Реализация шаблонных классов Container и Set

Лабораторная работа 6 для студентов курса “Программирование на основе классов и шаблонов” 2 семестра кафедры ИУ5 МГТУ им Н.Э. Баумана.

Содержание

• Цель работы
• Начало работы
• Задание
• Указания по выполнению лабораторной работы
  • Класс Container
  • Класс Set

Цель работы

Изучить:

• механизм наследования в C++;
• работу с шаблонными классами;
• реализацию динамических структур данных;
• принципы работы ассоциативных контейнеров (множества).

Начало работы

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

git pull upstream

или

git pull upstream lab_6

Переключитесь на ветку с текущей лабораторной работой:

git checkout lab_6

Свяжите ветку локального репозитория с вашим удаленным репозиторием:

git push --set-upstream origin lab_6

Задание

Необходимо реализовать два шаблонных класса:

• Container — базовый класс (динамический массив);
• Set — производный класс (множество).

Указания по выполнению лабораторной работы

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

Ассоциативные контейнеры отличаются тем, что доступ к элементам осуществляется по ключу, а не по индексу.

Контейнер “множество” (set) хранит уникальные элементы и обеспечивает быстрый поиск.

Для повышения эффективности:

• элементы множества хранятся в отсортированном виде;

• поиск выполняется методом половинного деления (бинарный поиск).

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

Класс Container

Общая характеристика

Класс представляет собой динамический массив с автоматическим изменением размера.

Поля класса

• max_size — текущий размер массива;
• size — количество элементов;
• pdata — указатель на массив элементов.

Изменение размера

Размер массива изменяется автоматически:

• при добавлении:

  • если size >= max_size → max_size *= 2

• при удалении:

  • если size < max_size / 4 → max_size /= 2

, при этом размер не должен становиться меньше значения по умолчанию.

Конструкторы и деструктор

• конструктор с параметром (по умолчанию — создание пустого контейнера);
• конструктор копирования;
• конструктор перемещения;
• деструктор.

Методы

• push — добавление элемента в конец;
• pop — удаление элемента по индексу;
• find(el) — поиск элемента (возвращает индекс или -1);
• resize — изменение размера массива.

Операторы

• operator[] — доступ по индексу;
• оператор присваивания;
• перемещающий оператор присваивания.

Класс Set

Общая характеристика

Класс Set наследуется от Container и реализует множество:

• элементы уникальны;
• элементы отсортированы.

Особенности

• новые поля не добавляются;
• используются методы базового класса.

Методы доступа

• is_element(el) — проверка наличия элемента;
• q_find(el) — бинарный поиск.

Методы изменения

• push — добавляет элемент только если его нет;
  после добавления выполняется сортировка;

pop — удаляет элемент, если он существует.

Операторы

• += — объединение множеств;
• -= — разность;
• *= — пересечение.

Дружественные функции

• оператор вывода <<;

Операторы

• + — объединение;
• - — разность;
• * — пересечение;
• == — сравнение множеств.

Примеры операций

{1, 4, 5, 6} + {1, 2, 3, 4} → {1, 2, 3, 4, 5, 6}
{1, 4, 5, 6} * {1, 2, 3, 4} → {1, 4}
{1, 4, 5, 6} - {1, 2, 3, 4} → {5, 6}

Особые указания

Важно:

• исходный код работает только с char*;
• необходимо:
  • сделать классы шаблонными (template <typename T>);
  • реализовать поддержку различных типов данных;
  • реализовать специализацию для char* (с учётом особенностей сравнения и добавления строк). Запрещено специализировать полностью класс. Необходимо специализировать определённые методы

---

Пример использования

#include <iostream>
#include <string>
#include "containers/Container.h"
#include "containers/Set.h"

int main() {

    // ===== Container =====
    Container v("Hello!");
    v.push("Привет!");
    v.push("World");
    v.push("Test");

    std::cout << "Вектор v: " << v << std::endl;

    // Проверка поиска
    int index = v.find("World");
    std::cout << "Индекс элемента 'World': " << index << std::endl;

    v.push("Another");
    v.push("Example");

    std::cout << "Вектор v после добавления: " << v << std::endl;

    Container v1 = v;
    std::cout << "Копия v1: " << v1 << std::endl;

    v1.pop(2);
    std::cout << "v1 после удаления элемента с индексом 2: " << v1 << std::endl;


    // ===== Set<char*> =====
    Set<char*> s("Yes"), s1("Hello!"), s2;

    s.push("Привет!");
    s.push("No");
    s.push("World");

    std::cout << "\nМножество s: " << s << std::endl;

    // Проверка наличия элемента
    if (s.is_element("No"))
        std::cout << "'No' есть в множестве s\n";

    s1.push("Cat");
    s1.push("Dog");
    s1.push("Привет!");

    std::cout << "Множество s1: " << s1 << std::endl;

    // Разность
    s2 = s1 - s;
    std::cout << "s2 = s1 - s: " << s2 << std::endl;

    // Объединение
    s2 = s1 + s;
    std::cout << "s2 = s1 + s: " << s2 << std::endl;

    // Пересечение
    s2 = s1 * s;
    std::cout << "s2 = s1 * s: " << s2 << std::endl;

    // Сравнение
    Set<char*> s3 = s2;
    std::cout << "s3: " << s3 << std::endl;

    if (s3 == s2)
        std::cout << "s3 == s2\n";
    else
        std::cout << "s3 != s2\n";


    // ===== Set<int> =====
    Set<int> one(1);
    one.push(2);
    one.push(3);
    one.push(5);

    Set<int> two;
    two.push(2);
    two.push(3);
    two.push(10);

    std::cout << "\none: " << one << std::endl;
    std::cout << "two: " << two << std::endl;

    one -= two;
    std::cout << "one -= two: " << one << std::endl;


    // ===== Set<double> =====
    Set<double> one1(1.5);
    one1.push(2.0);
    one1.push(3.99);

    Set<double> two1;
    two1.push(2.0);
    two1.push(3.98);
    two1.push(10.0);

    std::cout << "\none1: " << one1 << std::endl;
    std::cout << "two1: " << two1 << std::endl;

    one1 -= two1;
    std::cout << "one1 -= two1: " << one1 << std::endl;


    // ===== Set<string> =====
    Set<std::string> stroka;
    stroka.push("Привет!");
    stroka.push("Hello");
    stroka.push("Привет!"); // дубликат

    std::cout << "\nStroka: " << stroka << std::endl;

    if (!stroka.is_element("Bye"))
        std::cout << "'Bye' отсутствует в stroka\n";

    return 0;
}