Чем плох vector <bool>

vector <bool> - это пример неудачной стандартизации контейнера. Что представляет собой vector <bool> согласно стандарту? На его примере решили показать как можно использовать проксированный контейнер. Это контейнер, к объектам которого нет прямого доступа. Работать с ними нужно через специальные прокси-объекты. Под один так называемый bool здесь отводится один бит, что не соответствует реальному типу bool, под который обычно отводится 8 бит (возможно больше). Для доступа к этим битам есть прокси-класс по имени reference, который, как утверждается, ведет себя как ссылка на бит. Нужен он потому, что типа бит не существует, а работать с отдельными элементами vector <bool>'а как-то надо. reference же позволяет написать выражение вида v[0] = true.
С первого взгляда такой подход к реализации vector <bool> выглядит неплохо, так как экономится память, но при внимательном рассмотрении возникают проблемы. Поскольку vector <bool>::reference не является обычной ссылкой, а лишь ведет себя похоже, не будет компилироваться код, который верен для всех векторов, кроме vector <bool>:

vector <bool> myVBool;
...
bool *pBool = &myVBool[0];
Итераторам для работы тоже нужна обычная ссылка, а не ее имитация.

Также для работы с vector <bool> были добавлены специфичные функции, которых нет у других векторов. Например flip(), которая инвертирует значение битов вектора.
В итоге получается, что vector <bool>, это и не vector, поскольку в нем отсутствуют стандартные возможности векторов и добавлены некоторые новые. И не bool, потому что его составными элементами являются отдельные биты, а не объекты типа bool. Более того, это решение фактически заставляет программиста использовать оптимизацию памяти, которая зачастую не нужна, зато это потенциально медленнее. Не для всех 1 килобайт - это страшная потеря, а экономия памяти будет в таких порядках.

В итоге тем, что получилось из vector <bool>, лучше не пользоваться. А что если он очень нужен? Вместо него можно использовать vector <char>, vector <int>, deque <bool>, bitset. bitset, правда не контейнер, к нему нельзя добавлять и из него удалять элементы, но он также использует 1 бит на bool.

Несколько слов о реализации vector <bool>. Как правило, его реализовывают согласно стандарту. Так сделано в популярной мультиплатформенной реализации STLPort. А что в родной реализации Visual C++?
В VC++5.0 vector <bool> был реализован не согласно стандарту и эта реализация перекочевала в 6.0. bool тут - обычный bool, никакого проксирования.
Вот этот код там успешно компиляется
vector <bool> myVBool;
...
bool *pBool = &myVBool[0];

Зато вот этот - уже нет:

vector <bool> myVBool;
myVBool.push_back(true);
myVBool.flip();
Хотя по стандарту должен.

Проблема с vector <bool> была замечена в конце 96-го года, Bill (PJ) Plauger (кстати, он президент той самой компании Dinkumware, которая писала реализацию STL для Visual C++ 5.0) упомянул о ней в статье C/C++ Users Journal. В конце 96-го, начале 97-го этот вопрос активно обсуждался в comp.lang.c++.moderated и comp.std.c++. После долгих разговоров, в 1999 году Herb Sutter направил в ISO два письма с описанием проблемы и предложениями по поводу ее устранения, пока никаких изменений внесено не было.

Ссылки по теме:
Стандарт на реализацию контейнеров. О vector <bool> сказано в пункте 23.2.5.
When Is a Container Not a Container?
vector <bool> Is Nonconforming, and Forces Optimization Choice
vector <bool>: More Problems, Better Solutions

Technorati tag: C++