Greg <greghe@pacbell.net> wrote:[color=blue]
> Marcus Kwok wrote:[color=green]
>> zl2k <kdsfinger@gmail.com> wrote:[color=darkred]
>> > I am using a big, sparse binary array (size of 256^3). The size may be
>> > changed in run time. I first thought about using the bitset but found
>> > its size is unchangeable. If I use the vector<bool>, does each element
>> > takes 4 bytes instead of 1 bit? I am using gcc3.4.4. There is a
>> > bit_vector which is kind of old so I wont use that. Any other choices?[/color]
>>
>> Since vector<bool> is required to be a specialization, you should read
>> the following articles by Herb Sutter before deciding on using it:
>>
>> vector<bool> Is Nonconforming, and Forces Optimization Choice
>>
http://www.gotw.ca/publications/N1185.pdf
>>
>> vector<bool>: More Problems, Better Solutions
>>
http://www.gotw.ca/publications/N1211.pdf[/color]
>
> Neither of the quoted articles presents an argument against using
> vector<bool>. They are merely criticisms of vector<bool>'s
> classification as a vector - an issue of interest only to those
> designing the C++ standard library.[/color]
From the first article:
2. vector<bool>::iterator does not meet the requirements of a
forward, bidirectional, or random-access iterator, although the
last is strongly implied by the specialization's naming and
position. This means that it may not work with a conforming
implementation of a standard library algorithm.
The possibility of not being able to use a vector<bool> with standard
library algorithms is an argument against using it in my book.
5. vector<bool>'s name is misleading because the things inside aren't
bools.
// Example 1: Works for every T except bool
//
template<class T>
void g( vector<T>& v ) {
T& r = v.front();
T* p = &*v.begin();
// ... do something with r and *p ...
}
If something is explicitly stated as being a vector, is it unreasonable
to assume that it should behave as a vector?
6. vector<bool> forces a specific optimization choice on all users by
enshrining it in the standard. That's probably not a good idea,
even if the actual performance overhead turns out to be negligible
for a given compiler for most applications; different users have
different requirements.
In this case, vector<bool> forces the "favour less space at the
expense of potentially slower speed" optimization choice on all
programs. The implicit assumption is that virtually all users of
a vector of bools will prefer "less space" at the expense of
"potentially slower speed," that they will be more
space-constrained than performance-constrained. This is clearly
untrue.
[color=blue][color=green]
>> Technically, even though vector<bool> is mentioned in the Standard,
>> its use is unspecified. Quoting from the second article:
>>
>> Curiously, vector<bool> is not actually specified, so no current use
>> of it invokes well specified behavior. Its declaration appears in
>> the standard, but not a single function is specified. Note that the
>> argument "it's just the same as vector" fails because a vector<bool>
>> is demonstrably not a vector: it has a different interface (i.e.,
>> flip()), a different structure (e.g., reference is a class, not a
>> typedef for T&), does not meet the same requirements (e.g., container
>> and iterator requirements), etc.
>>
>> Since you are dealing with a sparse array, maybe you could use a
>> std::map<int, bool> or something.[/color]
>
> Why?[/color]
The key word that triggered my response was "sparse". If it is known
that the data is sparse, then it may not be necessary to store all 256^3
entries.
[color=blue]
> Whether vector<bool> should be called a "vector" or not - makes no
> difference to the issue of how well it can solve a particular problem.
> The only question that the programmer needs to decide is whether a
> std:vector<bool> can do what the program needs it to do. And if that
> task is to store a dynamically-resizable container of one-bit boolean
> values - then the answer is clearly "yes." And there would no reason
> for a program not to use a std::vector<bool> in that case.[/color]
....unless speed requirements are more important than memory
requirements.
Since vector<bool> uses a proxy class instead of storing true bools,
there is some additional overhead associated with every element access.
If these values are accessed in a tight loop, performance considerations
can be substantial.
I'm not saying not to use vector<bool> at all or that vector<bool> won't
meet the OP's requirements; I'm just saying that the OP should be aware
of the issues with it before deciding that he should "clearly" use it.
--
Marcus Kwok
Replace 'invalid' with 'net' to reply
