Лабораторная работа №7 (vector)

Содержание

1. Содержание
2. Задание
   1. Гарантии элементов
   2. Поддерживаемые операции
   3. Выделение памяти
   4. Советы
3. Требования к корректности решения
   1. Стандартные требования
   2. Дополнительные требования
   3. Закрытые тесты
4. Бонусное задание
5. Инструкция по сдаче
6. Система оценки
7. Сроки сдачи

Задание

Реализуйте динамический массив vector<T, Alloc = std::allocator<T>>:

• Работает аналогично std::vector<T, Alloc>, если не сказано иное.
  • Некоторые требования строже, чем в стандарте C++ к вектору.
  • Аллокатор Alloc используется для выделения памяти вместо new T[]/delete[] для упрощения тестирования, смотри ниже.
• Владеет всеми находящимися внутри элементами.
• Все элементы хранятся в памяти подряд.
• Память выделяется заранее независимо от создания элементов.
  • Отдельно есть количество элементов (size()), а отдельно — сколько элементов можно создать без перевыделения памяти (capacity()).
  • В частности, это позволяет достичь константной сложности для push_back().
• Все операции предоставляют максимально возможную гарантию исключений.
  • Гарантируется, что необходимые операции над T дают базовую гарантию.
  • В частности, если операция предоставляет строгую гарантию, то при выбрасывании исключения не может измениться ни capacity(), ни адреса лежащих в векторе элементов.
• Требуется делать как можно меньше выделений памяти и операций с T (даже если это просто перемещения), причём не просто асимптотически, а учитывать точное количество.
  • При этом дать максимально возможную гарантию важнее, чем скорость работы или потребляемая память.

Гарантии элементов

Тип T удовлетворяет требованиям MoveConstructible, MoveAssignable, Destructible, причём все три перечисленных специальных метода не бросают исключений (предоставляют nothrow exception safety).

Также тип T может удовлетворять какому-ту подмножеству требований: DefaultConstructible, CopyConstructible, CopyAssignable. В этом случае соответствующие специальные методы предоставляют хотя бы basic exception safety.

В этом задании не требуется думать про неполные (incomplete) типы.

Поддерживаемые операции

Ниже считаем, что:

• В векторе v лежит n элементов, в векторе v2 — m элементов.
• Все операции с индивидуальными элементами работают за O(1).
• Выделение и освобождение памяти работает за O(1).

Асимптотика указана в худшем случае, если не указано иное. Если получилось O(0), то считайте, что это на самом деле O(1).

Пример	Описание	Когда доступна	Время работы
vector v;	Создаёт пустой vector	Всегда	O(1)
vector v(n);	Создаёт vector из n элементов	T — DefaultConstructible	O(n)
vector v(n, t);	Создаёт vector из n элементов-копий t	T — CopyConstructible	O(n)
vector v2 = v;	Копирует v в v2	T — CopyConstructible	O(n)
vector v2 = std::move(v);	Перемещает v в v2, v становится пустым	Всегда	O(1)
v2 = v;	Копирует v в v2	T — и CopyConstructible, и CopyAssignable	O(n + m)
v2 = std::move(v);	Перемещает v в v2, v становится пустым	Всегда	O(m)
v.empty()	Возвращает true если и только если вектор пуст	Всегда	O(1)
v.size()	Возвращает количество элементов	Всегда	O(1)
v.capacity()	Возвращает объём внутреннего буфера	Всегда	O(1)
v[k]	Обращение к k-у элементу	Всегда	O(1)
v.at(k)	Обращение к k-у элементу, выкидывает std::out_of_range при обращении за границы	Всегда	O(1)
v.reserve(k)	Делает capacity() равным или большим k	Всегда	O(n)
v.push_back(t);	Копирование элемента в конец	T — CopyConstructible	O(1) (амортизированно)
v.push_back(T());	Перемещение элемента в конец	Всегда	O(1) (амортизированно)
v.pop_back();	Удаление элемента с конца	Всегда	O(1)
v.resize(k);	Удаляет элементы с конца вектора или добавляет сконструированные по умолчанию в конец	T — DefaultConstructible	O(|k - n|) (амортизированно)
v.resize(k, t);	Удаляет элементы с конца вектора или добавляет копии t в конец	T — CopyConstructible	O(|k - n|) (амортизированно)
v.clear();	Удаление всех элементов	Всегда	O(n)
}	Деструктор	Всегда	O(n)

• Используйте std::size_t для размеров и индексов.
• Все операции с vector<T> должны предоставлять хотя бы строгую гарантию исключений (strong exception safety), а при возможности — отсутствие исключений (nothrow exception safety) и соответствующую пометку noexcept в сигнатуре метода.
  • Вам требуется самостоятельно понять, какую самую строгую гарантию может обеспечить каждая операция.
• Порядок создания и удаления элементов остаётся на ваше усмотрение.
• Все операции не изменяют capacity() или адреса элементов, если только без этого не обойтись для обеспечения нужной асимптотики или гарантии безопасности исключений.
  • Например, при копировании вроде v2 = v; не должно быть перевыделений памяти.
• В любой момент capacity() вектора должно быть либо нулём, либо степенью двойки. При этом методы, увеличивающие или инициализирующие capacity(), должны выбирать минимально возможное значение.

Выделение памяти

В этом задании для выделения памяти без инициализации элементов используйте следующие операции:

using Alloc = std::allocator<int>;  // Переданный в vector<> аллокатор.
// ......
int *memory = Alloc().allocate(10);  // Выделение памяти под 10 элементов.
// ... любые операции с memory ...
Alloc().deallocate(memory, 10);  // Удаление памяти под 10 элементов по адресу memory.

Запрещается использовать любые другие способы выделения памяти: вызовы operator new/operator delete/malloc/free/aligned_alloc. Запрещается вызывать allocate(0), равно как и deallocate(nullptr, 0). Это отличие от operator new. Также запрещается использовать любые другие методы аллокатора или std::allocator_traits.

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

Мы не будем погружаться в дебри аллокаторов, выделения памяти или выравнивания. Предполагаем, что аллокатор уже делает всё правильно.

Советы

• Сначала напишите в качестве разминки вектор, который считает, что исключений нет.
  • Это ~200 строк кода, без длинного копипаста.
  • Такая реализация проходит все открытые тесты, кроме нескольких, содержащих throw.
  • Когда у вас уже есть полное понимание простой версии вектора, добавлять гарантии исключений куда проще.
• Будьте осторожны с оператором копирующего присваивания.
  • В нём можно добиться строгой гарантии исключений, но какой ценой? В этом задании мы готовы заплатить, в отличие от стандартной библиотеки.
• Напишите себе вспомогательных функций на частые операции вроде std::uninitialized_copy/std::destroy. При этом их реализации из стандартной библиотеки нельзя использовать в решении или копировать.
  • Вы можете даже делать шаблонные приватные функции, которые принимают параметр-функтор вроде «как инициализировать элемент». Это уменьшит количество копипаст.
• Некоторые конструкторы должны быть explicit, некоторые операции — const-qualified или ref-qualified, некоторые — noexcept. Иногда в комбинации, иногда есть несколько перегрузок.
  • Даже если в стандартном векторе этих квалификаторов нет (или наоборот) ради обратной совместимости: например, добавление любого ref qualifier в C++11 могло сломать старый код, поэтому так не сделали.
  • Используйте rvalue ref qualifier (&&), чтобы отличить lvalue/rvalue неконстантный *this — он работает в точности как обычный ref-qualifier.
• Будьте осторожны с порядком операций в коде: вам нужна строгая гарантия исключений.
• Вначале закомментируйте почти все открытые тесты и составьте план: какие методы вектора вы реализуете и какие тесты после этого можно запускать.
  • Начните с конструкторов, деструктора и геттеров — они нужны почти везде.
  • Затем сделайте перемещающий push_back — он активно используется в тестах для заполнения вектора.
  • Оставшиеся методы тестируются более-менее независимы.
• Вы сильно упростите себе обработку исключений, если вы будете хранить в векторе не чистый T*, а небольшую обёртку (вроде unique_ptr), которая будет автоматически удалять указатель в своём деструкторе.
  • Таким образом вам потребуется писать меньше кода в каждом catch (...), а некоторые try-блоки можно будет вообще полностью убрать.
  • Этой обёртке даже не надо уметь копироваться или перемещаться: можно всё запретить.
  • А вот swap будет полезен.
  • Также будет полезно сохранить размер выделенной памяти в эту же обёртку, чтобы удобно вызывать deallocate и swap.

Помните, что:

• Исключения могут вылетать:
  • При динамическом выделении памяти.
  • При копировании T любым способом или вызове конструктора по умолчанию, причём даже в середине цикла for.
• Перед освобождением куска памяти обязательно вызвать деструкторы у всех созданных в этой памяти объектов.
• Если исключение вылетело из конструктора объекта obj (в том числе при использовании placement new), то obj считается не созданным: его деструктор не вызывается и вызывать его не надо (будет UB).
• Исключения не могут вылетать при:
  • Вызове деструкторов.
  • Освобождении памяти.
  • Операциях с указателями и целыми числами.
  • Перемещении T любым способом (конкретно в рамках данного задания).
• Если push_back(T v) принимает свой аргумент по значению, то добавление элемента в конец будет требовать либо два перемещения, либо перемещение и копирование. В данном задании считаем, что это слишком долго.

Требования к корректности решения

Стандартные требования

Действуют стандартные требования.

Однако флаги для статических проверок несколько изменены:

• У clang-tidy отключены следующие проверки:
  • cppcoreguidelines-pro-bounds-pointer-arithmetic (какая-то арифметика указателей внутри вектора наверняка возникнет)
  • modernize-use-emplace (для тестов)

Дополнительные требования

• Запрещается использовать функции стандартной библиотеки для работы с неинициализированной памятью вроде std::uninitialized_copy, std::destroy, равно как и копировать их реализации откуда-либо.
• Ваша реализация должна делать минимальное количество выделений памяти.
  • Два вместо одного или одно вместо нуля — это уже плохо.
  • Если без лишнего выделения памяти не обеспечить строгую гарантию исключений, то можно сделать лишнее выделение.
• Количество операций с T должно быть минимально возможным в каждом конкретном случае.
  • Копирование элемента вместо перемещения — это очень плохо.
  • Если есть шанс, что придётся сделать 2*n перемещений элементов при resize — это плохо.
  • Два перемещения вместо одного — это плохо.
  • Удаление элемента и вызов конструктора копирования — это хуже, чем вызвать оператор копирующего присваивания (это потребуется только один раз, там operator= гарантированно существует).
  • Если в случае «вектору не требуется перевыделение памяти» можно сделать что-то оптимальнее — это нужно сделать.
• В остальном все операции должны быть асимптотически оптимальны.

Закрытые тесты

В этом задании много закрытых тестов.

Открытые тесты гарантированно проверяют лишь корректность сигнатур (за исключением наличия/отсутствия noexcept и ref-qualifier) и работу с минимально возможным T. Время работы, количество выделений памяти, операций с T и гарантии исключений проверяются очень поверхностно.

Бонусное задание

Вы можете получить +1 бонусный балл за корректность и +1 бонусный балл за стиль, если ваш оператор копирующего присваивания начнёт работать оптимальнее, когда выражение std::is_nothrow_copy_assignable_v<T> истинно (то есть копирующий оператор присваивания T предоставляет nothrow exception safety).

Вам по-прежнему потребуется обработать оба случая: и старый, и бонусный. Используйте для этого if constexpr вместо обычного if, чтобы заставить компилятор отбросить ненужную ветку на этапе компиляции (тип T-то известен).

Это уже зачатки метапрограммирования :)

Инструкция по сдаче

Как и раньше, вы должны самостоятельно синхронизировать ветку master в своём репозитории, создать новую ветку для задания и новый Pull Request.

Система оценки

• Задание оценивается в 10 баллов: 6 за корректность, 4 за стиль.
  • Если не проходит хотя бы одна автопроверка или неверно назван PR, вы получаете ноль.
  • Вы не можете получить за стиль больше баллов, чем за корректность.
• Вы можете получить ещё +2 балла за бонусное задание, итого 12.

Сроки сдачи

Задание выдано 18 февраля 2021 (четверг). Ниже в каждом случае указано московское время.

• Дедлайн сдачи: 27 февраля 2021 (суббота), 22:59.
• Гарантированный срок проверки: TODO.
• Дедлайн исправлений: TODO.