Почему вектор & lt; bool & gt; не контейнер STL?

vector<bool> содержит логические значения в сжатом виде, используя только один бит для значения (а не 8, как это делают массивы bool []). Невозможно вернуть ссылку на бит в c ++, поэтому существует специальный тип помощника, «битовая ссылка», который предоставляет вам интерфейс для некоторого бита в памяти и позволяет использовать стандартные операторы и приведение типов.

Проблема в том, что vector<bool> возвращает ссылочный объект прокси вместо истинной ссылки, так что код стиля C ++ 98 bool * p = &v[0]; не скомпилируется. Однако современный C ++ 11 с auto p = &v[0]; может быть сделано для компиляции, если operator& также возвращает указатель на прокси. Говард Хиннант написал сообщение в блоге детализация алгоритмических улучшений при использовании таких прокси-ссылок и указателей.

Скотт Мейерс имеет длинный пункт 30 в Более эффективный C ++ о прокси классах. Вы можете пройти долгий путь почти подражать встроенным типам: для любого данного типа Tпара прокси (например, reference_proxy<T> а также iterator_proxy<T>) могут быть сделаны взаимно согласованными в том смысле, что reference_proxy<T>::operator&() а также iterator_proxy<T>::operator*() обратны друг другу.

Тем не менее, в какой-то момент нужно сопоставить прокси-объекты обратно, чтобы вести себя как T* или же T&, Для итераторов прокси можно перегружать operator->() и получить доступ к шаблону Tинтерфейс без переопределения всей функциональности. Однако для справочных прокси вам потребуется перегрузить operator.()и это не допускается в текущем C ++ (хотя Себастьян Редл представил такое предложение на BoostCon 2013). Вы можете сделать подробный обход как .get() член внутри ссылочного прокси или реализовать все Tинтерфейс внутри ссылки (это то, что сделано для vector<bool>::bit_reference), но это либо утратит встроенный синтаксис, либо введет пользовательские преобразования, которые не имеют встроенной семантики для преобразований типов (вы можете иметь не более одного пользовательского преобразования на аргумент).

TL; DR: нет vector<bool> не является контейнером, потому что Стандарт требует реальной ссылки, но его можно заставить вести себя почти как контейнер, по крайней мере, гораздо ближе к C ++ 11 (авто), чем в C ++ 98.

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

например, посмотрите на STDC ++ реализация Вот.

также интересно, хотя не соответствующий STL битовый вектор является LLVM :: BitVector от Вот.

сущность llvm::BitVector это вложенный класс с именем reference и подходящая перегрузка оператора, чтобы сделать BitVector ведет себя подобно vector с некоторыми ограничениями. Код ниже представляет собой упрощенный интерфейс, чтобы показать, как BitVector скрывает класс с именем reference чтобы реальная реализация почти вела себя как реальный массив bool без использования 1 байта для каждого значения.

class BitVector {
public:
class reference {
reference &operator=(reference t);
reference& operator=(bool t);
operator bool() const;
};
reference operator[](unsigned Idx);
bool operator[](unsigned Idx) const;
};

этот код здесь имеет хорошие свойства:

BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.

Этот код на самом деле имеет недостаток, попробуйте запустить:

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

не будет работать, потому что assert( (&b[5] - &b[3]) == (5 - 3) ); потерпит неудачу (в течение llvm::BitVector)

это очень простая версия llvm. std::vector<bool> также есть рабочие итераторы.
таким образом, вызов for(auto i = b.begin(), e = b.end(); i != e; ++i) буду работать. а также std::vector<bool>::const_iterator,

Однако есть все еще ограничения в std::vector<bool> что заставляет его вести себя по-другому в немного случаев.

Это исходит от http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool Это специализированная версия вектора, которая используется
для элементов типа bool и оптимизирует для пространства.

Он ведет себя как неспециализированная версия вектора, с
следующие изменения:

• Хранилище не обязательно является массивом значений bool, но реализация библиотеки может оптимизировать хранилище так, чтобы каждое значение
  хранится в одном бите.
• Элементы не создаются с использованием объекта распределителя, но их значение напрямую устанавливается на соответствующий бит во внутренней памяти.
• Отражение функции члена и новая подпись для обмена участником.
• Специальный тип члена, ссылка, класс, который обращается к отдельным битам во внутренней памяти контейнера с интерфейсом, который
  эмулирует ссылку bool. И наоборот, тип члена const_reference
  простой бул.
• Типы указателя и итератора, используемые контейнером, не обязательно являются ни указателями, ни соответствующими итераторами, хотя они
  должны моделировать большую часть их ожидаемого поведения.

Эти изменения обеспечивают причудливый интерфейс к этой специализации и
предпочтение оптимизации памяти перед обработкой (что может или не может подойти
твои нужды). В любом случае, невозможно создать экземпляр
Неспециализированный шаблон вектора для bool напрямую. Обходные пути к
избегайте этого диапазона от использования другого типа (char, unsigned char) или
контейнер (например, deque) для использования типов обертки или для дальнейшей специализации
конкретные типы распределителей.

bitset — это класс, который предоставляет аналогичные функциональные возможности для фиксированного размера
массивы битов.

Многие считают vector<bool> Специализация быть ошибкой.

В бумаге «Устаревшие части рудиментарной библиотеки в C ++ 17»
Есть предложение
Пересмотреть вектор частичной специализации.

Существует долгая история частичной специализации bool
std :: vector, не удовлетворяющий требованиям контейнера, и в
в частности, его итераторы, не удовлетворяющие требованиям случайного
Итератор доступа. Предыдущая попытка отказаться от этого контейнера была
отклонено для C ++ 11, N2204.

Одна из причин отказа состоит в том, что не ясно, что это будет
означает, чтобы отказаться от конкретной специализации шаблона. Тот
может быть решено с осторожной формулировкой. Большая проблема в том, что
(упакованный) специализация вектора предлагает важный
оптимизация, которую искренне ищут клиенты стандартной библиотеки, но
больше не будет доступен. Вряд ли мы сможем
не рекомендуется использовать эту часть стандарта до тех пор, пока
предложенный и принятый, такой как N2050. К сожалению, таких нет
пересмотренные предложения, которые в настоящее время предлагаются для Библиотеки Evolution
Рабочая группа.