пятница, июня 17, 2005

Чем плох 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:

10 коммент.:

raymond комментирует...

Я, конечно, в программировании 3d да ещё и C++ слабо, что понимаю. Но блог мне ваш, Аленка, нравится, читаю с удовольствием... И учусь помаленьку.

Alena комментирует...

:-)
Приятно знать, что не зря стараешься.

Анонимный комментирует...

IMHO na primere vector< bool > my vidim, kak vazhno sledovat' ISO Standartu do poslednei bykvy. Na samom dele, esli podhodit' formal'no, sleduyuschii kod NEVEREN "dlya vseh vektorov":

vector< T > v;
...
T *p = &v[0];

V strogom sootvetstvii so Standartom, kod dolzhen vyglyadet' vot tak:

vector< T > v;
...
vector< T >::pointer p = &v[0];

Odnako, tut my (v ocherednoi raz) stalkivaemsya s situatsiei, kogda STL zagonyaet sam sebya v ugol: dazhe esli realizovat' __Bit_pointer naryadu s __Bit_reference, ot "taking address of temporary" v poslednei stroke nikuda ne dent'sa -- "operator &" ne peregruzhaetsa :-) Hotya rabotat' v obschem-to budet...

A v tselom ya s tochkoi zreniya soglasen -- pered tem, kak klassifitsirovat' del'fina kak rybu na osnovanii vneshnih priznakov, stoit vnimatel'no razobrat'sa s tem, kak del'fin rabotaet :-)

J0hnny комментирует...

"На его примере решили показать как можно использовать проксированный контейнер"
Откуда такая информация? В смысле почему именно "пример"? Если у Вас никогда не было потребности в vector, это не значит что его включили в стандарт только как пример. Стандарт это не "C++ for Dummies".
Короче коротко и ясно, ISO:
"To optimize space allocation, a specialization of vector for bool elements is provided".

"не будет компилироваться код, который верен для всех векторов, кроме vector :
...
bool *pBool = &myVBool[0]"
Для каких целей вообще это делается?
для того чтобы работать как с обычным указателем(++pBool/etc)? Стандарт 1998 года вообще не гарантировал что в векторе все элементы должны хранится подряд.
Стандарт 2003 года гарантирует это. Но, там чётко написано
"where T is some type other than bool"


"vector - это пример неудачной стандартизации контейнера. "
Ну да, люди работали, старались, совещались, пришла Алёна и смешала их работу с грязью..

Alena комментирует...

J0hnny
Откуда такая информация?

Источники указаны в конце поста

Анонимный комментирует...

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

Shtirlic комментирует...

Уважаемый J0hnny Вы написали "Ну да, люди работали, старались, совещались, пришла Алёна и смешала их работу с грязью.."

Люди которые работали над STL безусловно умные и уважаемые. Но зачем так категорично высказываться. Алена высказала недостатки которые она увидела и если Вы не согласны с этими недостатками то вполне могли бы ограничиться высказываниями только по ним.

на счет vector,и названия vector
http://www.rsdn.ru/forum/cpp/2095037.flat.aspx
цитата:
8. vector
8.1. Странное название у этого контейнера. В математике вектор содежит фиксированное количество элементов. Поэтому математический вектор похож на Pascal-евский массив, для которого "размер массива является частью его типа". Поначалу слово 'vector' может сбить с толку.
В MFC соответствующий контейнер называется 'CArray'.
Проблему упомянул LaptevVV здесь.
8.2. Динамический "массив битов" лучше было бы оформить как отдельный класс (например, dyn_bit_array), а не как специализацию vector. Нынешнее решение нарушает обобщённость vector-а. В будущем, возможно, динамический "массив битов" выделят в отдельный класс и обобщённость vector-а будет восстановлена.
Проблему упомянули Mazay здесь, Шебеко Евгений здесь.
Всё это странно, так как Страуструп в книге "Дизайн и эволюция языка C++" пишет (в самом конце 8-ой главы):
Одобрен также класс динамического массива dynarray [Stal, 1993], шаблон класса bits для битовых множеств фиксированного размера, класс bitstring для битовых множеств с изменяемым размером. Кроме того, комитет принял классы комплексных чисел (предшественник — первоначальный класс complex, см. раздел 3.3), обсуждается вопрос, следует ли принять класс вектора для поддержки численных расчётов и научных приложений. О наборе стандартных классов, их спецификациях и даже названиях всё ещё ведутся оживлённые споры.

Дизайн и эволюция языка C++, стр 201. 8.5.Стандартная библиотека
Извините что получилось много, но не хотелось упускать интересные моменты

Alena комментирует...

Shtirlic
Алена высказала недостатки которые она увидела

Не совсем. Это был скорее вольный перевод работ Герба Саттера и обсуждений в comp.lang.c++.moderated.

Владимир Семенякин комментирует...

Наткнулся на этот пост в 2016 году. Делаю враппер вокруг массива, проксирование оператора [] вызовом:

Type &operator [](DIndex inIndex) { return _implementation[inIndex]; }

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

Анонимный комментирует...

Стандарт есть стандарт, специализация для bool есть и её не отключить. Есть boost::vector, отличающийся от оного из std отсутствием этой специализации (правда, помимо этого, насколько я знаю, он в ряде случаев предоставляет менее строгие гарантии exception-safety, что может оказаться проблемой — с другой стороны, это позволяет увеличить эффективность благодаря move-semantics).