Разработать 4 простых класса для студенческого домашнего задания C++
Ниже будет представлены требования для каждого из классов. 1) Vector std::vector Интерфейс и реализация std::vector во многом похожи на std::string. Ключевым отличием является семантика работы метода reserve (и остальных методов, которые приводят к увеличению capacity). При резервировании памяти под большее число объектов, выделяется "сырая" (неинициализированная) память достаточная для хранения нужного числа дополнительных объектов. Пустые ячейки заполняются лениво по мере необходимости. То есть, если size < capacity, то это значит, что первые size * sizeof(T) байт реально заняты объектами, а последние (capacity - size) * sizeof(T) байт пусты - объектов там не создано. Это нужно, например, для того, чтобы можно было создавать вектор из объектов, у которых нет конструктора по умолчанию (а как бы тогда нужно было инициализировать неиспользуемые ячейки?): struct A { int x;
A() = delete;
explicit A(int x_param) : x(x_param) {
}
};
std::vector v;
v.reserve(1000); // объекты A не создаются! Выделяется "сырая" память размера 1000 * sizeof(A)
for (int i = 0; i < 1000; ++i) {
v.push_back(A(i));
// а лучше v.emplace_back(i);
} Подробности на лекциях, семинарах, в чатах, на заборе, а также в справочнике. Детали реализации От вас требуется реализовать шаблонный класс Vector с единственным шаблонным параметром - типом хранящихся элементов. При реализации можно (и даже нужно) пользоваться обобщенными алгоритмами из STL (std::copy, std::fill и т.п.), но нельзя использовать стандартные контейнеры. Будет проверяться корректность мультипликативной схемы расширения массива с коэффициентом 2. В базовой версии ручное управление временем жизни объектов не требуется (см. доп. задание). Класс должен поддерживать следующий функционал:Конструктор по умолчанию - создает пустой массив;Явный конструктор от числа - создает массив заданного размера заполненный объектами, сконструированными по умолчанию;Конструктор, принимающий size и value (именно в этом порядке) - создает массив длины size, заполненный элементами со значением value;Шаблонный конструктор, принимающий пару итераторов - создает копию переданного диапазона;Важно: объявление этого конструктора должно иметь видtemplate ::iterator_category>>>Vector(Iterator first, Iterator last)Это делает конструктор доступным только в случае, когда на вход приходят два Forward итератора.Конструктор от std::initializer_list;Правило "пяти";Методы Size, Capacity, Empty;Константный и неконстантный оператор доступа по индексу []. Неконстантный должен позволять изменять полученный элемент;Константный и неконстантный метод доступа по индексу At. При выходе за границы массива должен бросать исключение std::out_of_range;Методы Front() и Back()доступ к первому и последнему элементам (тоже по две версии).Метод Data()возвращает указатель на начало массива.Метод Swap(other)обменивает содержимое с другим массивом other;Метод Resize(new_size)изменяет размер на new_size. Если вместимость не позволяет хранить столько элементов, то выделяется новый буфер с вместимостью new_size. Недостающие элементы конструируются по умолчанию.Метод Resize(new_size, value)то же, что и Resize(new_size), но в случае new_size > size заполняет недостающие элементы значением value.Метод Reserve(new_cap)изменяет вместимость на max(new_cap, текущая вместимость). Размер при этом не изменяется.Метод ShrinkToFit()уменьшает capacity до size.Метод Clear()устанавливает размер в 0, очищения выделенной памяти при этом НЕ происходит.Методы PushBack(const T&) и PushBack(T&&)добавляет новый элемент в конец массива.Метод PopBack()удаляет последний элемент.Операции сравнения (<, >, <=, >=, ==, !=), задающие лексикографический порядок.Также реализуйте поддержку итераторов и методы для работы с ними: begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), crend(). begin()-end(), rbegin()-rend() должны иметь две версии, возвращающие константные и неконстантные итераторы. Для того, чтобы codestyle не ругался на написание методов с маленькой буквы, напишите в данной строке комментарий // NOLINTВнутри класса Vector определите типы-члены ValueType, Pointer, ConstPointer, Reference, ConstReference, SizeType, Iterator, ConstIterator. Гарантии безопасности Спроектируйте класс так, чтобы при возникновении исключений (нехватка памяти, ошибка при копировании объектов и т.п.) методы удовлетворяли строгой гарантии безопасности. То есть все методы должны работать атомарно: либо работать без сбоев, либо не изменять исходного состояния вектора. Исключение: копирующее присваивание может давать лишь базовую гарантию безопасности.При решении можно предполагать, что конструкторы перемещения, перемещающие присваивания и деструкторы объектов никогда не бросают исключений!2) Itertools.Range Itertools Одним из минусов языка C++ является отсутствие удобного интерфейса работы с последовательностями и промежутками значений, который, по большому счету сводится к ручному написанию циклов и работе со встроенными итераторами. С введением библиотеки в C++20 ситуация заметно улучшилась. В этом цикле задач мы попытаемся решить заявленную проблему средствами C++17. Range Для написания цикла по целым значениям в C++ необходимо написать следующий код:
for (int i = 0; i < end; ++i) {
// ...
}
for (int i = begin; i < end; ++i) {
// ...
}
for (int i = begin; i < end; i += step) {
// ...
}
Сравните, например, с языком Python:
for i in range(end):
# ...
for i in range(begin, end):
# ...
for i in range(begin, end, step):
# ...
Хотелось бы иметь подобный лаконичный код и в C++ (благо range-based for завезли в C++11):
for (int i : range(end)) {
// ...
}
for (int i : range(begin, end)) {
// ...
}
for (int i : range(begin, end, step)) {
// ...
}
Проблема в том, что в стандартной библиотеке (до C++20) нет сущности range, которую можно было использовать в подобном контексте. Ну а раз так - надо ее реализовать самостоятельно! Детали реализации Необходимо реализовать Range (класс или функцию), который возвращает объект некоторого класса (вам нужно его реализовать) с определенными методами begin и end. Эти методы должны возвращать итератор (его тоже нужно реализовать), который при разыменовывании возвращает соответствующее целое значение, а при инкрементировании увеличивает свое состояние на step (по умолчанию step == 1).Примеры: (больше примеров см. в тестах)
for (int i : Range(3)) { ... } // i in [0, 1, 2]
for (int i : Range(3, 6)) { ... } // i in [3, 4, 5]
for (int i : Range(3, 6, 2)) { ... } // i in [3, 5]
for (int i : Range(6, 1, -2)) { ... } // i in [6, 4, 2]
Указание: вспомните как работает range-based for в C++- Поддержать обратные итераторы (см. примеры в тестах). 3) Реализуйте шаблонный класс UnorderedSet, аналог std::unordered_set, который основан на хешировании методом цепочек с динамическим увеличением числа корзин.Метод цепочек предполагает хранение массива, в каждой ячейке которого лежит корзина - список вставленных элементов с одинаковыми хеш-значениями. Среднее время операций над такой структурой пропорционально степени загруженности таблицы (load_factor = n_elements / n_buckets). При превышении load_factor некоторого значения (в задании = 1) происходит перехеширование - создание нового массива корзин в, например, 2 раза большего размера и перенос старых элементов в новые корзины.В простейшем варианте достаточно хранить вектор (std::vector) списков (std::list / std::forward_list) и выполнять операции над ним. Более эффективные техники описаны ниже в дополнительных заданиях. Базовая часть Шаблонный класс UnorderedSet должен быть параметризован типом ключа KeyT. Стратегия расширения такая же как в задаче String - при добавлении элемента в пустую таблицу число корзин становится равным 1, при добавлении элемента в полную таблицу число корзин увеличивается в 2 раза (таблица считается полной, если число корзин совпадает с числом элементов, то есть load_factor == 1). В качестве хеш-функции воспользуйтесь std::hash. std::hash отображает объекты в диапазон size_t, чтобы получить индекс корзины, возьмите остаток от деления полученного числа на количество корзин.Набор методов включает:Конструктор по умолчанию. Создает пустую хеш-таблицу.Конструктор от числа корзин count. Создает хеш-таблицу с count пустыми корзинами.Конструктор от промежутка заданного двумя Forward итераторами. Создает хеш-таблицу с числом корзин равным числу элементов в последовательности, а затем вставляет элементы в таблицу.Конструкторы копирования, перемещения, а также присваивания должны работать корректно.Методы Size, Empty, Clear с привычной семантикой.Методы вставки Insert(const KeyT&), Insert(KeyT&&).Метод удаления Erase(const KeyT&).Метод поиска bool Find(const KeyT&).Метод Rehash(new_bucket_count). Изменяет число корзин в хеш-таблице с перехешированием. Если new_bucket_count совпадает с текущим количеством корзин или меньше числа элементов (load_factor становится больше 1), то ничего делать не нужно.Метод Reserve(new_bucket_count). То же, что и Rehash, но не уменьшает число корзин, то есть срабатывает, если new_bucket_count превышает текущее количество корзин.Методы BucketCount (возвращает число корзин в таблице), BucketSize(id) (возвращает размер корзины с номером id), Bucket(key) (возвращает номер корзины, в которую попадает объект key), LoadFactor() (возвращает степень заполненности таблицы).Обратите внимание, что каждый раз создавать новые узлы списков при перехешировании может быть неэффективно. Для переиспользования старых узлов (перебрасывания указателей старых списков) рассмотрите возможность использования метода std::list::splice.4) BigInteger Условие В C++ в отличие от, например, Python нет встроенных возможностей для работы с длинной арифметикой - вычислениями над величинами превосходящими по размеру базовые типы. Несмотря на то, что типы long long и unsigned long long(~10191019) покрывают большую часть практических вычислений, иногда бывает необходимо повысить точность выполняемых операций.В этом задании необходимо реализовать класс BigInteger для работы с большими целыми числами, которые вмещают в себя значения от −N−N до NN, где N=1030,000N=1030,000 Детали реализации В качестве решения ожидается описание класса BigInteger. Для этого класса необходимо реализовать все требуемые арифметические операции и сопутствующие методы, упрощающие работу с ним.Длинное число можно представлять в памяти в виде массива цифр из некоторой системы счисления. Например, если в качестве системы счисления взять 1000, то каждый элемент массива будет представлять собой целое число из промежутка [0,...,999][0,...,999]. Рекомендуется в качестве основания брать некоторую степень 10 для удобства ввода и вывода числа в десятичной системе счисления (иначе придется выполнять перевод из одной системы в другую).Пример:Пусть число представляется в виде массива 5 цифр из 1000-й системы счисления. Тогда десятичное число 1,234,567,890 будет представляться в памяти массивом [890, 567, 234, 1, 0] (сначала младшие разряды, затем старшие).При таком подходе достаточно просто реализовать операции сложения, вычитания и умножения над массивами "в столбик", последовательно выполняя операции над цифрами.Недостатком данного метода является неэффективное расходование памяти, выделяемое под число. Допустим, основание системы счисления равно 10'000, а цифра представляет собой беззнаковое 16-битное число, которое может вместить в себя 65'536 значений. Получается, что в каждый момент времени, как минимум 2 бита расходуется в пустую.Кроме того, при реализации сложения и умножения следует помнить, что результат их применения к цифрам может не помещаться в заданный тип (9'999 * 9'999 не влезает в 16-битное число). Для решения этой проблемы можно было бы взять тип "с большим запасом" - хранить цифры в 32-битных целых числах. Но это только усугубляет проблему, описанную в предыдущем абзаце. В качестве альтернативы предлагается использование приведения целых типов к более широкому в момент умножения, для получения корректного результата.Пример: using DigitType = uint16_t; // тип цифры - 16 битное число
using DoubleDigitType = uint32_t; // тип цифры с удвоенной шириной
digits_[i] * digits_[j]; // результат uint16_t - возможно переполнение
static_cast(digits_[i]) * digits_[j]; // результат uint32_t - нет переполнения Для поддержки отрицательных чисел достаточно хранить булевский флаг "отрицательности" числа и соответствующим образом корректировать операции в случае, когда он имеет значение true.Полный набор операций, который необходимо поддержать:Создание на основе целого числа (конструктор от целых чисел) и на основе си-строки с десятеричным представлением числа.IsNegative()true, если число отрицательное.Унарные + и -.Сложение, вычитание, умножение с присваивающими аналогами.Те же операции со встроенными целыми числами.Префиксные и постфиксные инкремент и декремент.Оператор приведения к bool.Операции сравнения.Операции ввода из потока и вывода в поток.При переполнении длинного числа, то есть если в результате операции количество десятичных цифр числа превосходит N (формально в тестах разрешается погрешность в 9 цифр), то нужно бросать исключение типа BigIntegerOverflow.Замечания.Решение должно состоять из файла интерфейса big_integer.h и файла реализации big_integer.cpp.В задаче есть открытые и закрытые тесты. Перед отправкой решения проверяйте его на открытых тестах (чуда не будет, если есть ошибка в публичных тестах, то она проявится и на более сложных приватных).Операции можно тестировать независимо на соответствующих задачах из Я.Контест.Решение необязательно должно быть оптимальным. Сосредоточьтесь на корректности реализаций. Решения "столбиком" будет достаточно."Бросить исключение типа E" значит - написать строку throw E{};. В этот момент выполнение функции прекращается и, если исключение не будет обработано, программа завершится аварийно. Тестирующий код корректно обработает эту ошибку, вам этого делать не нужно.Реализуйте операции целочисленного деления и взятия остатка от деления. Заметьте, правила деления отрицательных чисел в математике и C++ отличаются. От вас требуется реализация деления по правилам C++.Решение необязательно должно быть оптимальным, но в меру. Подойдет решение "уголком", но линейный поиск делителя на каждом шаге эффективным точно не назвать.
Other
