BitSet

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

Основные особенности

• Размер известен в момент конструирования и далее не меняется (кроме как через присваивающие операторы и сдвиги).
• Компактность: количество памяти, используемое под BitSet, не должно превышать size + C бит, где size — количество хранимых битов, а C — какая-то константа, не зависящая от size.
• Об исключениях и гарантиях, связанных с ними, в этом задании можно не задумываться.
• Поддержка семантики перемещения не требуется.

Вспомогательные классы

Помимо непосредственно класса BitSet, вам понадобится реализовать:

Итераторы

В качестве категории стоит выбрать random-access.

Для итераторов не нужно реализовывать operator-> (всё равно он не имеет смысла для bool). При этом type member pointer у итератора можно оставить равным void.

Из-за этих упрощений получившийся итератор, вероятно, не будет строго удовлетворять требованиям LegacyForwardIterator, однако будет удовлетворять требованиям итераторов нового образца (forward_iterator) из C++20.

Представления (views)

View — это легковесный объект, который ссылается на какой-то диапазон значений (не владея им), и по которому можно итерироваться. Часто он может быть представлен парой итераторов.

View для битсета интересен тем, что над ним тоже может иметь смысл проводить некоторые операции, в том числе побитовые. Для создания View используется BitSet::subview(offset, count) или конструкторы View.

Прокси-объекты для эмуляции ссылок

Поскольку биты хранятся упакованно, возникают проблемы с тем, что возвращать из BitSet::operator[]. Несложно понять, что с учётом этого требования это не сможет быть bool &.

Для решения этой проблемы предлагается в качестве BitSet::Reference использовать вспомогательный класс, который поддерживает следующие операции:

• bs[i] — неявно приводится к bool;
• bs[i] = false — оператор присваивания от bool для изменения бита на заданное значение;
• bs[i].flip() — инвертировать значение бита на обратное (для неконстантной ссылки).

Обратите внимание, что поддержка &bs[i] по понятным причинам не требуется, что даёт некоторую свободу для выбора типов для Reference и ConstReference.

Методы BitSet

Конструкторы

• BitSet() — пустая последовательность битов;
• BitSet(std::size_t size, bool value) — size битов, каждый из которых равен value;
• BitSet(const BitSet& other) — конструктор копирования;
• BitSet(std::string_view str) — на основе строки, состоящей из символов '0' и '1';
• BitSet(const ConstView& other) — копия переданного view;
• BitSet(ConstIterator start, ConstIterator end) — копия последовательности битов заданной двумя итераторами.

Операторы присваивания

• operator=(const BitSet& other) — оператор копирующего присваивания;
• operator=(std::string_view other) — см. аналогичный конструктор;
• operator=(const ConstView& other) — см. аналогичный конструктор.

Изменяющие операции

Здесь и далее для побитовых операций над двумя BitSet-ами (а также View, см. далее) поведение определено лишь при равенстве их размеров (поддержка операций над операндами различной длины не нужна).

• operator&=(const ConstView& other) — применить к каждому биту побитовое "и", где в качестве второго операнда служит соответствующий бит из other;
• operator|=(const ConstView& other) — аналогично operator&=, но с побитовым "или";
• operator^=(const ConstView& other) — аналогично operator&=, но с побитовым "xor";
• operator<<=(std::size_t count) — битовый сдвиг влево на count;
• operator>>=(std::size_t count) — битовый сдвиг вправо на count;
• flip() — инвертировать все биты;
• set() — установить все биты в 1;
• reset() — установить все биты в 0.

Побитовые операции

• BitSet operator&(const BitSet& lhs, const BitSet& rhs) — побитовое "и";
• BitSet operator|(const BitSet& lhs, const BitSet& rhs) — побитовое "или";
• BitSet operator^(const BitSet& lhs, const BitSet& rhs) — побитовый "xor";
• BitSet operator~(const BitSet& bs) — побитовая инверсия;
• BitSet operator<<(const BitSet& bs, std::size_t count) — битовый сдвиг влево bs на count;
• BitSet operator>>(const BitSet& bs, std::size_t count) — битовый сдвиг вправо bs на count.

Операции для доступа к элементам

• Reference operator[](std::size_t index) — возвращает прокси-объект на бит с индексом index (отсчитывая от старшего);
• begin(), end() — итераторы на первый бит и на бит после последнего соответственно;
• bool all() — правда ли, что все биты равны 1;
• bool any() — правда ли, что хотя бы один бит равен 1;
• std::size_t count() — количество битов, равных 1;
• operator==, operator!= — сравнение на равенство.

Обратите внимание, что операции all и any должны поддерживать short circuit evaluation, то есть нужно разбирать не все биты, а только необходимый для ответа префикс.

Прочие методы

• void swap(BitSet& other) — поменять местами состояния текущего BitSet и other;
• std::size_t size() — текущее количество хранимых битов;
• bool empty() — пустой ли это BitSet;
• subview(std::size_t offset = 0, std::size_t count = NPOS) — получить view:
  • пустой, если offset > size();
  • на [offset, offset + count), если offset + count <= size();
  • на [offset, size()), если offset + count > size().

Свободные функции

• void swap(BitSet& lhs, BitSet& rhs) — поменять местами состояния lhs и rhs;
• std::string to_string(const BitSet& bs) — перевод в строку из '0' и '1';
• std::ostream& operator<<(std::ostream& out, const BitSet& bs) — вывод в поток вывода out, возвращает исходный поток.

to_string и operator<< должны выводить непосредственно битовое представление без каких-либо префиксов или особого форматирования:

std::string_view bs_str = "0101";
ct::BitSet bs(bs_str);

std::string str = ct::to_string(bs);
// str == "0101";

std::cout << bs << std::endl;
// prints to standard output:
// 0101

Методы BitSet::View и BitSet::ConstView

Конструирование и операторы присваивания

• Копирующий конструктор;
• Конструктор от двух итераторов;
• Оператор копирующего присваивания;
• Неявное конструирование из ссылки на BitSet.

Остальные методы

Все те же методы, что и у BitSet, если они имеют смысл:

• operator[];
• begin, end;
• all, any, count;
• size, empty;
• swap;
• subview.

Модифицирующие операции над битами в неконстантном случае:

• set, reset, flip;
• операторы &=, |=, ^=.

А также связанные свободные функции:

• operator==, operator!=;
• swap;
• операторы битовых операций: &, |, ^, ~, <<, >>;
• форматирующие функции: to_string, operator<<.

Обратите внимание, что операторы сравнения должны поддерживать как сравнение двух BitSet или двух View между собой, так и сравнение BitSet с View.

Type members

Присутствуют как в BitSet, так и в views:

• Value
• Reference
• ConstReference
• Iterator
• ConstIterator
• View
• ConstView
• Word — тип, использующийся для разрядов (не менее 32 бит)

Рекомендации по выполнению

• При массовом применении операций работа с отдельными битами может оказаться неэффективной, вместо этого лучше оперировать сразу разрядами (Word);
• Разбивайте решение на файлы;
• По возможности (если это не шаблонный код) выносите реализации из хэдера;
• Выносите часто использующиеся конструкции в именованные сущности;
• Подумайте о том, как можно минимизировать количество повторяющегося кода;
• Не пренебрегайте спецификаторами доступа.