Vector со small-object и copy-on-write оптимизациями

В этом задании необходимо реализовать класс, аналогичный 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 не равен нулю.

Эффективная реализация copy-on-write

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

1. Пока ещё не стандартное расширение flexible array member (FAM). Про него был хороший доклад на CppCon — правда, часть описанных проблем с временами жизни более неактуальна для C++20 и выше (тем вам проще). В зависимости от компилятора, FAM обычно требует от типа элементов массива некоторые свойства (в частности, тривиальный деструктор и наличие конструктора по умолчанию). Также есть расширение, использующееся для схожих целей, в виде массива размера 0, которое не обладает указанными ограничениями.
2. Реализовать аналог вышеописанного расширения самостоятельно. Для этого вам придётся руками разграничивать использование единого блока аллоцированной памяти под мета-информацию и массив, не забывая про требования к выравниванию всех вовлечённых в процесс объектов.

Методы SocowVector

• Конструктор по умолчанию;
• Конструктор копирования;
• Конструктор перемещения;
• Оператор копирующего присваивания;
• Оператор перемещающего присваивания;
• 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_*;
• Где это имеет смысл, используйте семантику перемещения;
• Не делайте лишних копирований и перемещений;
• Выносите часто использующиеся конструкции в именованные сущности;
• Не пренебрегайте спецификаторами доступа.