vector<bool> problem with VC++ 6.0
| Author |
Message |
|
Esa
#1 / 15
|
 vector<bool> problem with VC++ 6.0 vector<bool> allocates 1 byte of storage for each bool instead of using 1 bit. Header file <vector> does include an implementation of bit vectors that allocate 1 bit per bool but why doesn't vector<bool> use this implementation? #include <vector>
...
std::vector<bool> bits1(100); // Allocates 100 bytes
std::_Bvector bits2(100); // Allocates 16 bytes
In <vector> _Bvector is defines as:
typedef vector<_Bool, _Bool_allocator> _Bvector;
Is this a bug or did I miss something here?
/Esa
|
| Fri, 04 Apr 2003 14:08:19 GMT |
|
 |
|
Code
#2 / 15
|
vector<bool> problem with VC++ 6.0 sizeof(bool) = 1byte there is ya answer, bools are stored as bytes for easy of use, since a byte is the smallest unit a machine can address (you can't address/allocate a bit of memory) Ray.
Quote:
> vector<bool> allocates 1 byte of storage for each bool instead of using 1 > bit. Header file <vector> does include an implementation of bit vectors that > allocate 1 bit per bool but why doesn't vector<bool> use this > implementation? > #include <vector>
> ...
> std::vector<bool> bits1(100); // Allocates 100 bytes
> std::_Bvector bits2(100); // Allocates 16 bytes
> In <vector> _Bvector is defines as:
> typedef vector<_Bool, _Bool_allocator> _Bvector;
> Is this a bug or did I miss something here?
> /Esa
|
| Fri, 04 Apr 2003 03:00:00 GMT |
|
|
|
Jan Bare
#3 / 15
|
vector<bool> problem with VC++ 6.0 Because partial specialization is not supported by VC++, you have to use
_Bvector template for bool vectors. See documentation of vector<bool, A>.
--
Jan Bares
(remove no.spam from my email address)
JPCAD Graphics Engine developer, surf to http://www.antek.cz
Quote:
> vector<bool> allocates 1 byte of storage for each bool instead of using 1 > bit. Header file <vector> does include an implementation of bit vectors that > allocate 1 bit per bool but why doesn't vector<bool> use this > implementation? > #include <vector>
> ...
> std::vector<bool> bits1(100); // Allocates 100 bytes
> std::_Bvector bits2(100); // Allocates 16 bytes
> In <vector> _Bvector is defines as:
> typedef vector<_Bool, _Bool_allocator> _Bvector;
> Is this a bug or did I miss something here?
> /Esa
|
| Fri, 04 Apr 2003 03:00:00 GMT |
|
|
|
Esa
#4 / 15
|
vector<bool> problem with VC++ 6.0 That's not correct! std::_Bvector actaully addresses bits! I was just wondering why vector<bool> does not use std::_Bvector. /Esa
Quote: > sizeof(bool) = 1byte there is ya answer, bools are stored as bytes for easy > of use, since a byte is the smallest unit a machine can address (you can't > address/allocate a bit of memory) > Ray.
> > vector<bool> allocates 1 byte of storage for each bool instead of using
1
> > bit. Header file <vector> does include an implementation of bit vectors
> that
> > allocate 1 bit per bool but why doesn't vector<bool> use this
> > implementation?
> > #include <vector>
> > ...
> > std::vector<bool> bits1(100); // Allocates 100 bytes
> > std::_Bvector bits2(100); // Allocates 16 bytes
> > In <vector> _Bvector is defines as:
> > typedef vector<_Bool, _Bool_allocator> _Bvector;
> > Is this a bug or did I miss something here?
> > /Esa
|
| Fri, 04 Apr 2003 03:00:00 GMT |
|
|
|
Esa
#5 / 15
|
vector<bool> problem with VC++ 6.0 I don't think you are right. I use template specialization all the time with VC++ and it works fine. After studying <vector> header file further I found out that I get hold of the correct vector specialization (i.e. _Bvector) with the following code: #include <vector>
...
std::vector<bool, std::allocator<unsigned int> > bits1(100); // uses
_Bvector
std::vector<bool, std::allocator<bool> > bits2(100); // uses generic
vector
The problem seems to be the allocator which _Bvector defines as
std::allocator<unsigned int> instead of std::allocator<bool>. Looks like a
bug to me!
/Esa
Quote: > Because partial specialization is not supported by VC++, you have to use
> _Bvector template for bool vectors. See documentation of vector<bool, A>.
> --
> Jan Bares
> (remove no.spam from my email address)
> JPCAD Graphics Engine developer, surf to http://www.antek.cz
> > vector<bool> allocates 1 byte of storage for each bool instead of using
1
> > bit. Header file <vector> does include an implementation of bit vectors
> that
> > allocate 1 bit per bool but why doesn't vector<bool> use this
> > implementation?
> > #include <vector>
> > ...
> > std::vector<bool> bits1(100); // Allocates 100 bytes
> > std::_Bvector bits2(100); // Allocates 16 bytes
> > In <vector> _Bvector is defines as:
> > typedef vector<_Bool, _Bool_allocator> _Bvector;
> > Is this a bug or did I miss something here?
> > /Esa
|
| Fri, 04 Apr 2003 03:00:00 GMT |
|
|
|
Reginald Blu
#6 / 15
|
vector<bool> problem with VC++ 6.0 The C++ library (STL) was written by Dinkumware for the 5.0 compiler. Due
to legal problems (which I won't go over here) it has not been updated since
then. The 5.0 compiler didn't support this type of specialization. This is
one example of a work around. There are a ton of others that don't work
right because of this.
They have since resolved their legal issues, but a new version won't by
added by Microsoft to the 6.0 compiler through the service pack mechanism.
(MS policy...don't ask me.)
The new version of their library (available for purchase) has this fixed,
and will work with the 6.0 compiler.
It is very likely, though not guaranteed, that the 7.0 compiler will ship
with the latest set of libraries.
You _could_ fix it yourself.
--
Reginald Blue | Opinions expressed here do not
Natural Language Understanding | necessarily represent those of
Unisys Corporation | my employer.
--------------------------------+-------------------------------
NL technology,speech application| My email address is wrong, you
development training, see: | need to remove the obvious.
http://www.speechdepot.com/ +-------------------------------
Quote:
> I don't think you are right. I use template specialization all the time with > VC++ and it works fine. After studying <vector> header file further I found > out that I get hold of the correct vector specialization (i.e. _Bvector) > with the following code: > #include <vector>
> ...
> std::vector<bool, std::allocator<unsigned int> > bits1(100); // uses
> _Bvector
> std::vector<bool, std::allocator<bool> > bits2(100); // uses generic
> vector
> The problem seems to be the allocator which _Bvector defines as
> std::allocator<unsigned int> instead of std::allocator<bool>. Looks like a
> bug to me!
> /Esa
> > Because partial specialization is not supported by VC++, you have to use
> > _Bvector template for bool vectors. See documentation of vector<bool,
A>.
> > --
> > Jan Bares
> > (remove no.spam from my email address)
> > JPCAD Graphics Engine developer, surf to http://www.antek.cz
> > > vector<bool> allocates 1 byte of storage for each bool instead of
using
> 1
> > > bit. Header file <vector> does include an implementation of bit
vectors
> > that
> > > allocate 1 bit per bool but why doesn't vector<bool> use this
> > > implementation?
> > > #include <vector>
> > > ...
> > > std::vector<bool> bits1(100); // Allocates 100 bytes
> > > std::_Bvector bits2(100); // Allocates 16 bytes
> > > In <vector> _Bvector is defines as:
> > > typedef vector<_Bool, _Bool_allocator> _Bvector;
> > > Is this a bug or did I miss something here?
> > > /Esa
|
| Fri, 04 Apr 2003 03:00:00 GMT |
|
|
|
#7 / 15
|
vector<bool> problem with VC++ 6.0
|
| Fri, 19 Jun 1992 00:00:00 GMT |
|
|
|
Dick Bridge
#8 / 15
|
vector<bool> problem with VC++ 6.0 Just my $.02:
Although <quote>...[t]he bool type participates in integral promotions. An
r-value of type bool can be converted to an r-value of type int, with false
becoming zero and true becoming one.</quote>, a 'bool', can have values of
'true' or 'false' - *NOT* 1 or 0. I believe the spec leaves the actual
implementation of the bool datatype to the people who write the compiler.
Microsoft, for example, changed the definition between versions 4.2 and 5.0.
<quote>In Visual C++4.2, the Standard C++ header files contained a typedef
that equated bool with int. In Visual C++ 5.0 and later, bool is implemented
as a built-in type with a size of 1 byte.</quote>
Now, combine that with the (Microsoft implementation specific?) requirement
that STL-based bit operations take place within the context of a "register's
worth" of memory allocation - 32 bits now, soon to be 64. IMHO, it's
because the Intel architecture would promote char and short to that size in
any case - more efficient to start there (and "performance" is the STL
mantra).
Consequently, the simple, straight-forward, easy-to-read, slightly
less-memory-efficient, slightly faster vector<bool> does exactly what you
asked it to do: it creates a vector of objects that are each sizeof(bool) -
i.e., 1 byte. Simple, easy, and fast to test once it's in a register.
If you use the unsigned int allocator, you create a vector of objects, each
containing ("number of bits in a char" * sizeof(unsigned int)) bits to be
converted back-and-forth to-and-from bool using a *LOT* more code. They've
actually duped some of the <bitset> operations to eliminate dependencies.
Getting the unsigned int that contains the value of interest is only the
beginning of the process of discovering it's state.
Unless you're working under VERY SEVERE memory limitations, most of the
people I work with would opt for the first implementation.
Quote:
> I don't think you are right. I use template specialization all the time with > VC++ and it works fine. After studying <vector> header file further I found > out that I get hold of the correct vector specialization (i.e. _Bvector) > with the following code: > #include <vector>
> ...
> std::vector<bool, std::allocator<unsigned int> > bits1(100); // uses
> _Bvector
> std::vector<bool, std::allocator<bool> > bits2(100); // uses generic
> vector
> The problem seems to be the allocator which _Bvector defines as
> std::allocator<unsigned int> instead of std::allocator<bool>. Looks like a
> bug to me!
> /Esa
> > Because partial specialization is not supported by VC++, you have to use
> > _Bvector template for bool vectors. See documentation of vector<bool,
A>.
> > --
> > Jan Bares
> > (remove no.spam from my email address)
> > JPCAD Graphics Engine developer, surf to http://www.antek.cz
> > > vector<bool> allocates 1 byte of storage for each bool instead of
using
> 1
> > > bit. Header file <vector> does include an implementation of bit
vectors
> > that
> > > allocate 1 bit per bool but why doesn't vector<bool> use this
> > > implementation?
> > > #include <vector>
> > > ...
> > > std::vector<bool> bits1(100); // Allocates 100 bytes
> > > std::_Bvector bits2(100); // Allocates 16 bytes
> > > In <vector> _Bvector is defines as:
> > > typedef vector<_Bool, _Bool_allocator> _Bvector;
> > > Is this a bug or did I miss something here?
> > > /Esa
|
| Fri, 04 Apr 2003 03:00:00 GMT |
|
|
|
Reginald Blu
#9 / 15
|
vector<bool> problem with VC++ 6.0 All of this is quite correct, but, unfortunately, besides the point.
The C++ standard specifies that:
vector<bool>
is a specific and unique type which really isn't the same as a
vector<foobar> at all.
Included in this fact is that it supports more operations than a standard
vector including:
flip()
and
[].flip()
Thus, in MSVC, specifying:
#include <vector>
using namespace std;
...
vector<bool> foo;
foo.push_back(true);
foo.flip();
...
will not compile, but it should.
--
Reginald Blue | Opinions expressed here do not
Natural Language Understanding | necessarily represent those of
Unisys Corporation | my employer.
--------------------------------+-------------------------------
NL technology,speech application| My email address is wrong, you
development training, see: | need to remove the obvious.
http://www.speechdepot.com/ +-------------------------------
Quote: > Just my $.02: > Although <quote>...[t]he bool type participates in integral promotions. An
> r-value of type bool can be converted to an r-value of type int, with
false
> becoming zero and true becoming one.</quote>, a 'bool', can have values of
> 'true' or 'false' - *NOT* 1 or 0. I believe the spec leaves the actual
> implementation of the bool datatype to the people who write the compiler.
> Microsoft, for example, changed the definition between versions 4.2 and
5.0.
> <quote>In Visual C++4.2, the Standard C++ header files contained a typedef
> that equated bool with int. In Visual C++ 5.0 and later, bool is
implemented
> as a built-in type with a size of 1 byte.</quote>
> Now, combine that with the (Microsoft implementation specific?)
requirement
> that STL-based bit operations take place within the context of a
"register's
> worth" of memory allocation - 32 bits now, soon to be 64. IMHO, it's
> because the Intel architecture would promote char and short to that size
in
> any case - more efficient to start there (and "performance" is the STL
> mantra).
> Consequently, the simple, straight-forward, easy-to-read, slightly
> less-memory-efficient, slightly faster vector<bool> does exactly what you
> asked it to do: it creates a vector of objects that are each
sizeof(bool) -
> i.e., 1 byte. Simple, easy, and fast to test once it's in a register.
> If you use the unsigned int allocator, you create a vector of objects,
each
> containing ("number of bits in a char" * sizeof(unsigned int)) bits to be
> converted back-and-forth to-and-from bool using a *LOT* more code.
They've
> actually duped some of the <bitset> operations to eliminate dependencies.
> Getting the unsigned int that contains the value of interest is only the
> beginning of the process of discovering it's state.
> Unless you're working under VERY SEVERE memory limitations, most of the
> people I work with would opt for the first implementation.
|
| Fri, 04 Apr 2003 03:00:00 GMT |
|
|
|
Dick Bridge
#10 / 15
|
vector<bool> problem with VC++ 6.0 Here's the part I was responding to:
Quote:
> > > vector<bool> allocates 1 byte of storage for each bool instead of using > 1 > > > bit. Header file <vector> does include an implementation of bit vectors > > that > > > allocate 1 bit per bool but why doesn't vector<bool> use this > > > implementation? > > > #include <vector>
> > > ...
> > > std::vector<bool> bits1(100); // Allocates 100 bytes
> > > std::_Bvector bits2(100); // Allocates 16 bytes
As far as I'm aware, the spec does not require a specific implementation for the controlled sequence. I'd appreciate it if you'd post the reference for me if I'm wrong. On the other issue (missing flip, swap, etc. for vector<bool>), I have no
idea why MSFT chose the implementation they did. On the other hand, we do
know that DEC had a similar problem and solved it in a similar way: <quote
src="http://wuphys.wustl.edu/cplusplus/using_cxx_on_unix0007.html">The
current STL simulates bool as a typedef of int . Thus, the DEC C++ STL
cannot supply the specialization vector<bool> because it would conflict with
vector<int> . In the interim, DIGITAL supplies a bit_vector class in place
of vector<bool></quote> Maybe MSFT chose the route they did so their "new"
implementation didn't break the existing code base. Just a thought.
This discussion is a little too 'religious' for me. I think I'll skip this
group for awhile. Have a nice day.
Quote: > All of this is quite correct, but, unfortunately, besides the point. > The C++ standard specifies that:
> vector<bool>
> is a specific and unique type which really isn't the same as a
> vector<foobar> at all.
> Included in this fact is that it supports more operations than a standard
> vector including:
> flip()
> and
> [].flip()
> Thus, in MSVC, specifying:
> #include <vector>
> using namespace std;
> ...
> vector<bool> foo;
> foo.push_back(true);
> foo.flip();
> ...
> will not compile, but it should.
> --
> Reginald Blue | Opinions expressed here do not
> Natural Language Understanding | necessarily represent those of
> Unisys Corporation | my employer.
> --------------------------------+-------------------------------
> NL technology,speech application| My email address is wrong, you
> development training, see: | need to remove the obvious.
> http://www.speechdepot.com/ +-------------------------------
> > Just my $.02:
> > Although <quote>...[t]he bool type participates in integral promotions.
An
> > r-value of type bool can be converted to an r-value of type int, with
> false
> > becoming zero and true becoming one.</quote>, a 'bool', can have values
of
> > 'true' or 'false' - *NOT* 1 or 0. I believe the spec leaves the actual
> > implementation of the bool datatype to the people who write the
compiler.
> > Microsoft, for example, changed the definition between versions 4.2 and
> 5.0.
> > <quote>In Visual C++4.2, the Standard C++ header files contained a
typedef
> > that equated bool with int. In Visual C++ 5.0 and later, bool is
> implemented
> > as a built-in type with a size of 1 byte.</quote>
> > Now, combine that with the (Microsoft implementation specific?)
> requirement
> > that STL-based bit operations take place within the context of a
> "register's
> > worth" of memory allocation - 32 bits now, soon to be 64. IMHO, it's
> > because the Intel architecture would promote char and short to that size
> in
> > any case - more efficient to start there (and "performance" is the STL
> > mantra).
> > Consequently, the simple, straight-forward, easy-to-read, slightly
> > less-memory-efficient, slightly faster vector<bool> does exactly what
you
> > asked it to do: it creates a vector of objects that are each
> sizeof(bool) -
> > i.e., 1 byte. Simple, easy, and fast to test once it's in a register.
> > If you use the unsigned int allocator, you create a vector of objects,
> each
> > containing ("number of bits in a char" * sizeof(unsigned int)) bits to
be
> > converted back-and-forth to-and-from bool using a *LOT* more code.
> They've
> > actually duped some of the <bitset> operations to eliminate
dependencies.
> > Getting the unsigned int that contains the value of interest is only the
> > beginning of the process of discovering it's state.
> > Unless you're working under VERY SEVERE memory limitations, most of the
> > people I work with would opt for the first implementation.
|
| Sat, 05 Apr 2003 03:00:00 GMT |
|
|
|
Reginald Blu
#11 / 15
|
vector<bool> problem with VC++ 6.0
Quote: > As far as I'm aware, the spec does not require a specific implementation
for
> the controlled sequence. I'd appreciate it if you'd post the reference
for
> me if I'm wrong.
Okay, you got me. I don't have a copy of the current ISO C++ standard to quote from. I have a copy of The C++ Standard Library by Nicolai M. Josuttis in which chapter 6.2.6 (pg 158) it goes into detail on the <bool> specialization of vector. Also, going to the public review version of the C++ standard
http://anubis.dkuug.dk/jtc1/sc22/open/n2356/ , I see that it at least was
in:
23.2.5 Class vector<bool>
that talked about the specialized version of vector.
But I have no current copy so I have no idea if that's where it still lives.
Presumably it _is_ still in there.
That said, I'm not sure I understand why you said "for the controlled
sequence". Perhaps we're not talking about the same thing after all? Given
the quote you had (which I removed), I'm suspicious that you're referring to
the "why doesn't it allocate 1 bit per..." part. FWIW, the vector<bool>
specialization in the standard indicates "To optimize space allocation, a
specialization of vector for bool elements is provided". You _are_ correct
that it doesn't explicitly state that it's 1 bit per...
Ultimately, the original poster was asking "why doesn't vector<bool> work
right in VC?" and the answer is because the template libraries in there are
old and designed for the "broken" VC5 compiler.
With the newer libraries, vector<bool> WILL do the right thing.
--
Reginald Blue | Opinions expressed here do not
Natural Language Understanding | necessarily represent those of
Unisys Corporation | my employer.
--------------------------------+-------------------------------
NL technology,speech application| My email address is wrong, you
development training, see: | need to remove the obvious.
http://www.speechdepot.com/ +-------------------------------
|
| Sat, 05 Apr 2003 03:00:00 GMT |
|
|
|
#12 / 15
|
vector<bool> problem with VC++ 6.0
|
| Fri, 19 Jun 1992 00:00:00 GMT |
|
|
|
Danny Kale
#13 / 15
|
vector<bool> problem with VC++ 6.0 Maybe the delay in shipping a Standard compliant vector<bool> proved to
be a clever decision after all, as this specialization is heavily
scorned by many C++ gurus these days, as well as the C++ standards
committee itself. The problem with vector<bool> is that it doesn't meet
(actually, it violates) the requirements of a container. In addition, on
most platforms, it incurs significant overhead due to the use of plain
bits rather than addressable types. The best advice you will get from
many gurus (e.g., Herb Sutter) is not to use vector<bool> at all. Maybe
by the time VC++7 ships, they won't need to implement it anymore...
Danny Kalev
"The ANSI/ISO C++ Professional Programmer's Handbook"
http://www.amazon.com/exec/obidos/ASIN/0789720221
|
| Sun, 06 Apr 2003 08:14:16 GMT |
|
|
|
#14 / 15
|
vector<bool> problem with VC++ 6.0
|
| Fri, 19 Jun 1992 00:00:00 GMT |
|
|
|
P.J. Plauge
#15 / 15
|
vector<bool> problem with VC++ 6.0 Quote:
> On the other issue (missing flip, swap, etc. for vector<bool>), I have no
> idea why MSFT chose the implementation they did. On the other hand, we do
> know that DEC had a similar problem and solved it in a similar way: <quote
> src="http://wuphys.wustl.edu/cplusplus/using_cxx_on_unix0007.html">The
> current STL simulates bool as a typedef of int . Thus, the DEC C++ STL
> cannot supply the specialization vector<bool> because it would conflict with
> vector<int> . In the interim, DIGITAL supplies a bit_vector class in place
> of vector<bool></quote> Maybe MSFT chose the route they did so their "new"
> implementation didn't break the existing code base. Just a thought.
vector<bool> doesn't invoke the explicit specialication of template class vector because the (default) allocator argument is not the proper one to do so. The safest thing is to use the type definition _Bvector, which works properly on all Dinkumware libraries, whether or not the compiler supports partial specialization. Please note, however, that _Bvector *does* define flip, swap, etc. as required for the explicit specialization described in the C++ Standard. P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
|
| Sun, 06 Apr 2003 03:00:00 GMT |
|
| |
|
