В этом задании необходимо реализовать класс, аналогичный std::vector, но имеющий small-object и copy-on-write оптимизации.
Small Object Optimization предполагает, что вектор умеет хранить небольшое число элементов без динамической аллокации памяти.
Copy-on-write предполагает, что копирование/присваивание больших векторов не копирует все элементы само, а откладывает копирование элементов до момента, когда к объекту применят модифицирующую операцию.
Реализуемый класс должен называться SocowVector и лежать в заголовочном файле socow-vector.h. Он должен иметь два шаблонных параметра: тип хранимых объектов и размер маленького буффера (в количестве элементов).
template <typename T, std::size_t SMALL_SIZE>
class SocowVector;Из-за наличия small-object и copy-on-write оптимизаций, некоторые операции имеют другую вычислительную сложность и/или предоставляют другую гарантию безопасности исключений:
- Конструктор копирования должнен работать за
O(SMALL_SIZE), а не заO(other.size()). - Оператор копирующего присваивания должнен работать за
O(SMALL_SIZE + this->size()), а не заO(other.size() + this->size()). - Конструктор перемещения должен работать за
O(SMALL_SIZE). - Оператор перемещающего присваивания должен работать за
O(SMALL_SIZE + this->size()). - Если в
bхранится small object, копирующийa = bдолжен предоставлять сильную гарантию безопасности исключений, иначе nothrow. - Неконстантные операции
operator[],data(),front(),back(),begin(),end()должны работать заO(size)и удовлетворять сильной гарантии безопасности исключений, если требуется копирование для copy-on-write, и заO(1)и nothrow иначе. - Как и со стандартным вектором,
reserveдолжен гарантировать, что после выполненияreserve(n)вставки в вектор не будут приводить к переаллокациям, пока размер не достигнетn(если между вызовомreserveи вставкой не создавались копии).
Вы можете полагаться, что конструктор перемещения, оператор перемещающего присваивания и swap для T существуют и не бросают исключения, и что существуют конструктор копирования и оператор копирующего присваивания. Вы также можете полагаться, что SMALL_SIZE не равен нулю.
При наивной реализации техники COW может оказаться, что вы делаете больше одной аллокации на вектор, а к элементам обращаетесь через череду индирекций. Во избежание этого можно воспользоваться одним из следующих подходов:
- Пока ещё не стандартное расширение flexible array member (FAM). Про него был хороший доклад на CppCon — правда, часть описанных проблем с временами жизни более неактуальна для C++20 и выше (тем вам проще). В зависимости от компилятора, FAM обычно требует от типа элементов массива некоторые свойства (в частности, тривиальный деструктор и наличие конструктора по умолчанию). Также есть расширение, использующееся для схожих целей, в виде массива размера 0, которое не обладает указанными ограничениями.
- Реализовать аналог вышеописанного расширения самостоятельно. Для этого вам придётся руками разграничивать использование единого блока аллоцированной памяти под мета-информацию и массив, не забывая про требования к выравниванию всех вовлечённых в процесс объектов.
- Конструктор по умолчанию;
- Конструктор копирования;
- Конструктор перемещения;
- Оператор копирующего присваивания;
- Оператор перемещающего присваивания;
swap(SocowVector& other)— поменять состояния текущего вектора иotherместами;size()— размер вектора;capacity()— вместимость вектора;empty()— является ли вектор пустым;operator[](std::size_t index); — обращение к элементу вектора;front(),back()— обращение к первому/последнему элементу вектора;data()— указатель на начало вектора;begin(),end()— итераторы;push_back(...)— вставить элемент в конец вектора (аргументом может быть lvalue или rvalue);insert(ConstIterator pos, ...)— вставить элемент передpos(аргументом может быть lvalue или rvalue);pop_back()— удалить элемент из конца вектора;erase(ConstIterator pos)— удалить элемент по итератору;erase(ConstIterator first, ConstIterator last)— удалить все элементы в диапазоне[first, last);clear()— очистить вектор от всех элементов;reserve(std::size_t new_capacity)— установить вместимость вектора, если текущая меньше;shrink_to_fit()— сжать вместимость вектора до текущего размера.
- Уделите особое внимание обеспечению гарантий безопасности исключений;
- Ручным управлению ресурсов и обработке исключений предпочитайте RAII и семейство функций
std::unitialized_*; - Где это имеет смысл, используйте семантику перемещения;
- Не делайте лишних копирований и перемещений;
- Выносите часто использующиеся конструкции в именованные сущности;
- Не пренебрегайте спецификаторами доступа.