473,249 Members | 1,900 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,249 software developers and data experts.

how much memory does vector<bool> take?

hi, there
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?
Thanks ahead.
zl2k

May 19 '06 #1
6 6733
zl2k wrote:
hi, there
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?
No, supposedly std::vector<bool> is a proper specialisation of std::vector
and each element only takes one 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?


You can always roll your own...

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
May 19 '06 #2
zl2k <kd*******@gmail.com> wrote:
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?


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

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.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
May 19 '06 #3

Marcus Kwok wrote:
zl2k <kd*******@gmail.com> wrote:
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?
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


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.
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.


Why? 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.

Greg

May 20 '06 #4
Greg <gr****@pacbell.net> wrote:
Marcus Kwok wrote:
zl2k <kd*******@gmail.com> wrote:
> 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?
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


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.


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.
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.


Why?


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.
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.

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
May 22 '06 #5
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.
May 22 '06 #6
Jerry Coffin <jc*****@taeus.com> wrote:
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.


Yes, I will agree that performance claims can only truly be determined
through profiling. Maybe even include tests with std::map<int, boolean>
(for the various types of "boolean" above) to see how they compare too
(assuming that the map satisfies the OP's requirements).

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
May 22 '06 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: klaas | last post by:
the following code gives rise to the beneath error message, only when a matrix object is instantiated as matrix<bool>, not with matrix<float>: /*returns a reference to the object at position...
3
by: Alexandros | last post by:
Hi. How can I create a vector<bool> efficiently from a char* or a vector<char> ? For example, if char* c == (8,10) I want vector<bool> v to be: (0000100000001010)
11
by: Michael | last post by:
Righty, 1: Is there a standard library that contain matrices and complex numbers. I need to find eigen values of a 3x3 matrix. 2: Is there a way of getting the pointer to the start of an...
1
by: Alex Vinokur | last post by:
------ foo.cpp ------ #include <vector> using namespace std; int main() { const vector<int> v1 (10); const vector<bool> v2 (10); &v1;
8
by: Bo Peng | last post by:
Dear list, I am using std::vector<bool> (bit_vector) to store my bit sequence. To access the same sequence from C (to expose to a python module), I need to know the pointer and offset of...
12
by: Piotr | last post by:
In effective STL, it said one should not use vector<bool> but use dequeue<bool> instead. But can dequeue<bool> has random access iterator? and I do this? dequeue<bool> myboolarray; if...
2
by: huomingxu | last post by:
in gdb, when print an element of vector<bool>, it returns the offset of the bi t instead of the value. e.g: (visible is of type vector<bool>) (gdb) p layout._visible $15 = {_M_p = 0x9817d00,...
8
by: Lionel B | last post by:
On my platform I find that the std::vector<boolspecialisation incurs a significant performance hit in some circumstances (when compared, say, to std::vector<intprogrammed analagously). Is it...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.