Перейти к основному содержимому

Приложение 1. Описание программы

Класс MyVector​

Базовый шаблонный класс MyVector является динамическим. Размер вектора max_size должен меняться в процессе выполнения программы следующим образом:

  • если при добавлении элемента число элементов вектора size превысит размер вектора, max_size увеличивается в 2 раза (был 8, станет 16, если size >= 8)
  • если при удалении элемента число элементов вектора size станет меньше max_size/4, max_size уменьшается в 2 раза, но должен быть не меньше значения по умолчанию (был 16, станет 8, если size < 4). Новый элемент добавляется в конец вектора.

Члены - данные​

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

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

  • Конструктор с одним параметром для создания множества размером 1, который имеет значения по умолчанию и поэтому может использоваться для создания пустого множества;
  • Конструктор копирования;
  • Деструктор.

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

Класс MyVector должен реализовывать следующие функции:

  • add_element – вставка элемента в конец вектора;
  • delete_element – удаление элемента из произвольного места;
  • find(el) – возвращает индекс элемента или –1, если элемент не найден;
  • resize – изменение размера вектора max_size при его переполнении или освобождении места;

Операторы​

  • [] - для возврата элемента вектора (доступ по индексу);
  • = - оператор присваивания.

Класс MySet​

Шаблонный класс с именем MySet включает элементы, представленные ниже.

Члены - данные​

Все данные наследуются из класса MyVector (элементы множества хранятся в векторе).

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

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

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

  • is_element, который даёт true , если элемент-параметр есть в множестве, иначе даёт false. Для поиска элементов множества следует использовать метод половинного деления. Для его реализации разработать метод q_find.

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

  • add_element - добавляет элемент в множество, если её там ещё нет. Для ускорения поиска элементов создаваемое множество должно быть отсортировано по возрастанию значения ключа. Для сортировки при добавлении элементов использовать метод sort() базового класса.
  • delete_element для удаления элемента из множества, если она там есть

Операторы​

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

Функции – не члены класса (друзья класса)​

  • Перегруженная операция потокового вывода;

  • Операторы + (объединение), - (разность), * (пересечение) и == (сравнение: истина, если элементы двух множеств совпадают).

    Примеры операций над множествами (приведены для целых чисел):

    {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}

Заготовка программы​

Заготовка программы с описанием классов MyVector и MySet содержится в репозитории по ссылке.

осторожно

Обратите внимание, что заготовка не содержит шаблонов классов и работает только со строками (с элементами char*). Необходимо самостоятельно шаблонизировать описание классов MyVector и MySet и реализовать различные специализации классов.

предупреждение

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