Почему vector не является контейнером STL?

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

проблема в том, что vector<bool> возвращает a прокси-объект ссылки вместо истинной ссылки, так что код стиля 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's интерфейс внутри ссылки (это то, что делается для vector<bool>::bit_reference), но это либо потеряет встроенный синтаксис, либо введет пользовательские преобразования, которые не имеют встроенной семантики для преобразований типов (вы можете иметь не более одного пользовательского преобразования на аргумент).

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

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

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

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

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

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

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

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

многие считают vector<bool> специализация будет ошибкой.

в статье "удаление рудиментарных частей библиотеки в C++17"
Есть предложение пересмотреть вектор частичной специализации.

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

---

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