473,708 Members | 2,404 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

vector and bool

1)
is C++ smart enough to automatically use "bits" for bool or will
a bool have the size of a charcter (byte).
2) The index of a vector is it an integer (4 byte) or a "long long"
with 8 bytes or something else?

I ask because I want to use

vector<bool> with a few billion entries exceeding the int32 range for
indexing and I want to use as few memory as possible for the whole
vector<bool>

e.g.
vector<bool> B;
B.resize(2^34);

thanks, daniel
Jul 22 '05 #1
19 3354
"daniel" <da************ @netscape.net> wrote in message
news:b3******** *************** ***@posting.goo gle.com...
1)
is C++ smart enough to automatically use "bits" for bool or will
a bool have the size of a charcter (byte). The standard C++ library is actually required to specialize the
std::vector for bool, and to provide 'compact' storage.
[NB: for many uses, this is actually seen as an inconvenience]
2) The index of a vector is it an integer (4 byte) or a "long long"
with 8 bytes or something else? This depends on the implementation, but it may well be limited
to size_t, or a 4-byte unsigned integer on many platforms.
You can check the return value of vector<bool>::m ax_size() to
find out.
I ask because I want to use

vector<bool> with a few billion entries exceeding the int32 range for
indexing and I want to use as few memory as possible for the whole
vector<bool>

May we ask for what type of application or what kind of data?
In many cases, using some form of compression might be better
that allocating gigabytes of RAM. Does your system have enough
memory?
Regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Jul 22 '05 #2
daniel posted:
1)
is C++ smart enough to automatically use "bits" for bool or will
a bool have the size of a charcter (byte).
I believe that sizeof(bool) must be >= 1, which implies that a "bool" is of
one byte. But that doesn't mean that your particular system might do
something different in the background.

It's to do with the actual CPU of the system, what is the smallest unit of
memory that can be accessed, which is called a "byte", which 9 times out of
10 is equal to "8 bits". Code which would store 8 bools in 1 byte would be
slower and (ironically) more memory consumptive as the code which
manipulates the byte would have to be kept in memory.
2) The index of a vector is it an integer (4 byte) or a "long long"
with 8 bytes or something else?
There is no such intrinsic type "long long".

There is a type "long int", which is guaranteed to be atleast 32-bit on all
systems, but that doesn't guarantee that it'll be 4 bytes long. For
instance:

If "char" were 9-Bit, then although "long" would be atleast 32-Bit, it
wouldn't necessarily be 4 bytes long, as 4 bytes = 36 bits on that system.
I ask because I want to use

vector<bool> with a few billion entries exceeding the int32 range for
indexing and I want to use as few memory as possible for the whole
vector<bool>

e.g.
vector<bool> B;
B.resize(2^34);

thanks, daniel


I'm sure there's people here that've done this before. . .

I'm not one of them!
-JKop

Jul 22 '05 #3
JKop wrote:
daniel posted:
1)
is C++ smart enough to automatically use "bits" for bool or will
a bool have the size of a charcter (byte).
I believe that sizeof(bool) must be >= 1, which implies that a "bool" is
of one byte. But that doesn't mean that your particular system might do
something different in the background.


AFAIK, some systems use even 4 bytes for a bool, because they can access it
faster.
It's to do with the actual CPU of the system, what is the smallest unit of
memory that can be accessed, which is called a "byte", which 9 times out
of 10 is equal to "8 bits".
However, a CPU byte might be different from a C++ byte. I have heared there
are signal processors that have a smallest memory unit of 24 bits and still
the C++ implementation gives you a char with 8 bit. And there are 4 bit
CPUS which would need to combine two bytes to meet the minimum requirement
of 8 bits for char. I guess there might be C implelemntation s, but probably
no C++ ones on such CPUs, but C has the same requirements in that case.
Code which would store 8 bools in 1 byte would be slower and (ironically)
more memory consumptive as the code which manipulates the byte would have
to be kept in memory.
2) The index of a vector is it an integer (4 byte) or a "long long"
with 8 bytes or something else?
There is no such intrinsic type "long long".

There is a type "long int", which is guaranteed to be atleast 32-bit on
all systems, but that doesn't guarantee that it'll be 4 bytes long.


That's right.
For instance:

If "char" were 9-Bit, then although "long" would be atleast 32-Bit, it
wouldn't necessarily be 4 bytes long, as 4 bytes = 36 bits on that system.


That example isn't really chosen very well. 3 bytes would only be 27 bits,
so you would still need 4 bytes to meet the requirement of at least 32
bits.

Jul 22 '05 #4
> Code which would store 8 bools in 1 byte would be
slower and (ironically) more memory consumptive as the code which
manipulates the byte would have to be kept in memory.


Who gives a damn if the code takes 10 or 30 bytes, when the guy wants to
store billions of bool's and the choises are 128 MB vs. 1024 MB for storing
one billion flags. And you cannot be so sure about the performance either,
very often smaller data translates to better performance in the real world
applications.
Jul 22 '05 #5
daniel wrote:
1)
is C++ smart enough to automatically use "bits" for bool or will
a bool have the size of a charcter (byte).

In C++ it is

1 <= sizeof(bool) <= sizeof(long)
However especially for vector<bool> the standard says:
"To optimize space allocation, a specialization of vector for bool
elements is provided:

....
reference is a class that simulates the behaviour of references of a
single bit in vector<bool>."


"The C++ Programming Language 3rd Edition" may help here:
"16.3.11 Vector<bool>

The specialization (§13.5) vector<bool> is provided as a compact vector
of bool. A bool variable is addressable, so it takes up at least one
byte. However, it is easy to implement vector<bool> so that each element
takes up only a bit.
The usual vector operations work for vector<bool> and retain their usual
meanings. In particular, subscripting and iteration work as expected.

For example:
void f(vector<bool>& v)
{
// iterate using subscripting
for (int i = 0; i<v.size() ; ++i) cin >> v[i] ;

typedef vector<bool>: :const_ iterator VI;

// iterate using iterators
for (VI p = v.begin() ; p!=v.end() ; ++p) cout<<*p;
}

To achieve this, an implementation must simulate addressing of a single
bit. Since a pointer cannot address a unit of memory smaller than a
byte, vector<bool>: :iterator cannot be a pointer. In particular,
one cannot rely on bool* as an iterator for a vector<bool>:

void f(vector<bool>& v)
{
bool* p = v.begin() ; // error: type mismatch
// ...
}

A technique for addressing a single bit is outlined in §17.5.3.

The library also provides bitset as a set of Boolean values with Boolean
set operations (§17.5.3)."



2) The index of a vector is it an integer (4 byte) or a "long long"
with 8 bytes or something else?

It is vector<T>::size _type which is some unsigned integer type.
Example:
vector<int> someVec(100);

for(vector<int> ::size_type i=0; i<someVec.size( ); ++i)
// ...



I ask because I want to use

vector<bool> with a few billion entries exceeding the int32 range for
indexing and I want to use as few memory as possible for the whole
vector<bool>

e.g.
vector<bool> B;
B.resize(2^34);


Well, it is not guaranteed that bits will be used, although in most
cases this is what should happen.

You may also want to check bitset which uses bits for sure.

--
Ioannis Vranos

http://www23.brinkster.com/noicys
Jul 22 '05 #6
Ioannis Vranos wrote:
Well, it is not guaranteed that bits will be used, although in most
cases this is what should happen.

You may also want to check bitset which uses bits for sure.

My mistake! It is *guaranteed* that bits are used:
From the standard:

"23.2.5 Class vector<bool>

To optimize space allocation, a specialization of vector for bool
elements is provided:

....

// bit reference:
class reference {
friend class vector;
reference();
public:
˜reference();
operator bool() const;
reference& operator=(const bool x);
reference& operator=(const reference& x);
void flip(); // flips the bit
};

....

void flip(); // flips all bits

....

reference is a class that simulates the behavior of references of a
single bit in vector<bool>."

--
Ioannis Vranos

http://www23.brinkster.com/noicys
Jul 22 '05 #7
JKop wrote:
I believe that sizeof(bool) must be >= 1, which implies that a "bool" is of
one byte.
Actually it implies bool is at least one byte. Many systems
sizeof(bool) == sizeof(int).
But that doesn't mean that your particular system might do
something different in the background.
Actually, for vector it is REQUIRED to do something different. I think
it's stupid but the standard requires vector<bool> to be specialized to
act differently than vectors of anything else. It should have been a
different class.

It's to do with the actual CPU of the system, what is the smallest unit of
memory that can be accessed, which is called a "byte", which 9 times out of
10 is equal to "8 bits".


Actually it has nothing to do with the actual CPU. C++ could just as
easily have bit types. There are machines where the smallest
addressable unit of storage is NOT a byte. A byte is carved up out of
a larger word.

However, getting back on topic, a byte (and it's related C++ type char)
is the smallest unit of memory C++ will address. This unfornuately is
another C/C++ stupidity. There really shouldn't be a hard relationship
between "character" and "atomic memory unit." Of course, this is 30
some years of hindsight speaking.
Jul 22 '05 #8
In message <1097586912.771 988@athnrd02>, Ioannis Vranos
<iv*@guesswh.at .grad.com> writes
Ioannis Vranos wrote:
Well, it is not guaranteed that bits will be used, although in most
cases this is what should happen.
You may also want to check bitset which uses bits for sure.
My mistake! It is *guaranteed* that bits are used:


I don't think so.
From the standard:

"23.2.5 Class vector<bool>

To optimize space allocation, a specialization of vector for bool
elements is provided:

...

// bit reference:
class reference {
friend class vector;
reference();
public:
Ëœreference( );
operator bool() const;
reference& operator=(const bool x);
reference& operator=(const reference& x);
void flip(); // flips the bit
};

...

void flip(); // flips all bits

...

reference is a class that simulates the behavior of references of a
single bit in vector<bool>."

That just redefines the semantics of operator[] etc. to return a proxy
instead of an actual bool &, thus removing the requirement for elements
to have distinct addresses. Nothing there says that it _must_ use only
use one bit per element.

--
Richard Herring
Jul 22 '05 #9

"daniel" <da************ @netscape.net> wrote in message
news:b3******** *************** ***@posting.goo gle.com...
1)
is C++ smart enough to automatically use "bits" for bool or will
a bool have the size of a charcter (byte).
2) The index of a vector is it an integer (4 byte) or a "long long"
with 8 bytes or something else?

I ask because I want to use

vector<bool> with a few billion entries exceeding the int32 range for
indexing and I want to use as few memory as possible for the whole
vector<bool>


Use either std::bitset or boost::dynamic_ bitset. Both "pack" the bits for
better memory usage. You'll most likely have to modify these classes to
account for indices > 32 bit.

Jeff F
Jul 22 '05 #10

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

Similar topics

3
14364
by: Scott Brady Drummonds | last post by:
Hi, everyone, I have a program in which I need to store a series of Boolean values. A vector<bool> would be ideal. However, I'm concerned about this data structure because of Scott Meyers' Effective STL's Item 18: Avoid using vector<bool>. Plus, I'm loath to use bit_vector since SGI's STL implementation says it will soon be dropped on the floor (http://www.sgi.com/tech/stl/bit_vector.html).
4
2432
by: wukexin | last post by:
I try some kind of compiler, my program compile succeeding, but run wrongly. Help me, see my program. If you have free time, please give me some suggestion about process command argument. Thank you very much. // #include <iostream> #include <fstream> #include <list> #include <string> #include <algorithm> #include <vector>
3
4143
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 (Row,Col) in matrix*/ template <class num_type,template <class T> class functor> num_type & matrix<num_type,functor >::operator()(const int Row,const int Col) {if (Row<rows && Col<cols) {vector<num_type> & x=matrix_core; //num_type & y=x;<-is also...
3
3461
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)
4
2948
by: Nomak | last post by:
Hello, With this code: $ cat -n ifs.cc 1 #include <vector> 2 #include <iostream> 3 4 using std::vector; 5 using std::cin;
16
2727
by: Kitty | last post by:
Hi, everyone. Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Kitty
2
3188
by: laniik | last post by:
Hi. For some reason I am getting a crash on pop_back() and Im not sure why. sorry I cant post the whole code because the vector is used in a bunch of places. i have a vector<bool> complete;
0
6134
by: santana | last post by:
Hi I've created a class to be used with stl vector. I'm having a hard time decipher the error message outpout by g++... burlen@quaoar:~/hdf52vtk_dev/src$ g++ junk.cpp GridPoint.o /usr/include/c++/3.3.3/bits/stl_algo.h: In function `_RandomAccessIter std::find(_RandomAccessIter, _RandomAccessIter, const _Tp&, std::random_access_iterator_tag) ': /usr/include/c++/3.3.3/bits/stl_algo.h:298: instantiated from `_InputIter...
6
6818
by: zl2k | last post by:
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
0
8787
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8697
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9158
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9060
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
5939
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4454
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4712
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3151
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2508
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

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.