In article <e4**********@news-int2.gatech.edu>,
ri******@gehennom.invalid says...
[ ... ]
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.
Although the required specialization of vector<bool> has
the _potential_ to reduce speed, the reality is that on
almost any reasonably recent processor, it will generally
_increase_ speed unless the vector involved is _quite_
small.
The situation is pretty simple: on most current
processors, the reduced size also means reduced memory
access and improved cache utilization. Currently, memory
is a lot slower than the processor as a rule (and the
ratio favors processors more strongly all the time). This
means that even if you have to do quite a lot of
computation to avoid a memory access, it's usually worth
it. In this case, there's not really a lot of extra
computation at all, and you're typically reducing memory
references by a ratio of at least 8:1 (and 32:1 isn't
unheard of).
[ ... ]
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.
...unless speed requirements are more important than memory
requirements.
Depending heavily upon your target -- if your target has
a cache, chances are good that vector<bool> actually
improves speed (unless your memory use is so low in
general that even without the reduction in memory usage
it would all fit in the cache).
My own advice would be to use a typedef:
vector<boolean> my_vect;
And then test and profile with both:
typedef char boolean;
and:
typedef bool boolean;
and possibly even:
typedef int boolean;
and see which works better for your situation. The
conversion rules for bool in C++ are loose enough that
this will normally work without any extra work on your
part as to how you use your boolean values. The one place
you're at all likely to run into a problem is if you want
to provide separate overloads (or specializations) for
your booleans and some of the other types mentioned above
-- the typedef only creates a new name, not a new type.
--
Later,
Jerry.
The universe is a figment of its own imagination.
