Почему вектор <bool> не контейнер STL?

Question

Пункт 18 книги Скотта Мейерса Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов говорит, чтобы избежать vector <bool>, поскольку он не является контейнером STL и на самом деле он не держит bools.

Следующий код:

vector <bool> v; 
bool *pb =&v[0]; 

не компилируется, нарушив требование STL контейнеров.

Ошибка:

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization 

vector<T>::operator [] тип возвращаемого значения должен быть T &, но почему это особый случай vector<bool>?

В чем состоит vector<bool>?

Деталь далее говорит:

deque<bool> v; // is a STL container and it really contains bools 

Может ли это быть использовано в качестве альтернативы vector<bool>?

Может кто-нибудь объяснить это?

Answer 1

В целях пространственно-оптимизации, С ++ стандарт (еще в C++ 98) явно взывает vector<bool> как специальный стандартный контейнер, где каждый BOOL использует только один бит пространства, а не одного байта, как обычный bool (реализация своего рода «динамического бита»). В обмен на эту оптимизацию он не предлагает все возможности и интерфейс обычного стандартного контейнера.

В этом случае, поскольку вы не можете принять адрес бита в байте, такие вещи, как operator[], не могут вернуть bool&, но вместо этого возвращают прокси-объект, который позволяет манипулировать конкретным битом, о котором идет речь. Поскольку этот прокси-объект не является bool&, вы не можете назначить его адрес bool*, как вы могли бы, в результате такого вызова оператора в «нормальном» контейнере. В свою очередь это означает, что bool *pb =&v[0]; является недопустимым кодом.

С другой стороны, deque не имеет такой специализации, так что каждый bool принимает байт, и вы можете взять адрес значения, возвращаемого с operator[].

Наконец, обратите внимание, что реализация стандартной библиотеки MS является (возможно) субоптимальной в том смысле, что она использует небольшой размер куска для deques, а это означает, что использование deque в качестве замены не всегда является правильным ответом.

Answer 2

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

Answer 3

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

Vector of bool This is a specialized version of vector, which is used for elements of type bool and optimizes for space.

It behaves like the unspecialized version of vector, with the following changes:

• The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is
  stored in a single bit.
• Elements are not constructed using the allocator object, but their value is directly set on the proper bit in the internal storage.
• Member function flip and a new signature for member swap.
• A special member type, reference, a class that accesses individual bits in the container's internal storage with an interface that
  emulates a bool reference. Conversely, member type const_reference is a plain bool.
• The pointer and iterator types used by the container are not necessarily neither pointers nor conforming iterators, although they
  shall simulate most of their expected behavior.

These changes provide a quirky interface to this specialization and favor memory optimization over processing (which may or may not suit your needs). In any case, it is not possible to instantiate the unspecialized template of vector for bool directly. Workarounds to avoid this range from using a different type (char, unsigned char) or container (like deque) to use wrapper types or further specialize for specific allocator types.

bitset is a class that provides a similar functionality for fixed-size arrays of bits.

Answer 4

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

например, посмотрите на stdC++ внедрение here.

также интересен, хотя не соответствует вектору бит stl, соответствует llvm :: BitVector от here.

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

Answer 5

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

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

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

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

Answer 6

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

В статье "Deprecating Vestigial Library Parts in C++17"
Существует предложение по Пересмотрите вектор частичной специализации.

There has been a long history of the bool partial specialization of std::vector not satisfying the container requirements, and in particular, its iterators not satisfying the requirements of a random access iterator. A previous attempt to deprecate this container was rejected for C++11, N2204 .

---

One of the reasons for rejection is that it is not clear what it would mean to deprecate a particular specialization of a template. That could be addressed with careful wording. The larger issue is that the (packed) specialization of vector offers an important optimization that clients of the standard library genuinely seek, but would not longer be available. It is unlikely that we would be able to deprecate this part of the standard until a replacement facility is proposed and accepted, such as N2050 . Unfortunately, there are no such revised proposals currently being offered to the Library Evolution Working Group.