In article <8muqua$vsd$1@nnrp1.deja.com>,
  Tom <the_wid@my-deja.com> wrote:
> In article <8mtd2o$t4o$1@nnrp1.deja.com>,
>   assert@my-deja.com wrote:

[snip problem outline]

> > It looks like a stronger promise than what vector<bool>
> > makes, but there still seems to be some wiggle room. It isnt
> > 100% clear to me that a bitset must use 1 bit of storage
> > for each bit it represents to the user. Can a conforming
> > bitset implementation commit 32 bits of true representation
> > for every 31 bits that the user works with.
> > (suppose 1 is for error checking) ?
>
> sizeof(anthing) is an integer, so if CHAR_BIT is 8, then there is no
> way that it can use only 31 bits. In fact, 31 is prime so the only way
> your bitset<31> could possibly occupy only 31 bits is on a platform
> where CHAR_BIT == 31. An unusual platform indeed.

I can commit 1 bit of representation for each bit specified
by the user. It is not a problem. The total allocated space
of any object will occupy (CHAR_BIT * n) bits
but that is a seperate issue and unrelated to
my question.

>
> >
> > how about 8 bits of representation for every 7 used ?
> >
> > how about 1 char to represent one bit ?
> > the ultimate in redundancy :)
>
> I would think that bitset would typically be implemented as an array
or
> unsigned long, so I would expect bitset<1> to have sizeof(unsigned
> long) bytes.


I dont care what you expect. I care about what the
requirements of the standard are.


> Same for bitset<7>. Same for bitset<31> on my platform.
> bitset<33> however uses 2 * sizeof(unsigned long) on my platform.


I dont care about your platform.


> Also, the compiler is allowed to pad Classes and structs to whatever
> size it feels like (I believe). For example:
> struct s {
> int i;
> char c;
> };
>
> My compiler gives sizeof(s) == 8, although adding up the sizeofs of
the
> elements gives only 5. It depends on things like the machine word
size.
>

No, it doesnt depend on machine word size.
Any upper bound on the requirements of bitset storage per
user bit specified is entirely in the hands of the standard
not your compiler. I dont care about your compiler
or anyone elses compiler.

> What exactly do you want to do with your vector<bool> or bitset,
anyway?
>

Maybe I want to implement a very very sloppy
but conforming bitset and do as little work possible.

In reality I don't want to do anything with it.

My question was about the text of the standard.


> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Steven King wrote:
>
> James Kuyper wrote:
>
> > Section 23.3.5.2p2 says that the maximum number of bits in a bitset is
> > CHAR_BIT * sizeof(unsigned long), which caries the clear implication
> > that an entire bitset is stored in a single unsigned integer type. Note:
> > it's not necessarily an unsigned long; bitset<N>, where N
> > <=CHAR_BIT*sizeof(unsigned), might be specialized to use an unsigned
> > int, instead.
>
>   Ah, but the standard doesn't actually say that.  It merely defines how
> a bitset is constructed from an unsigned long and 23.3.5.2/31, which
> defines the inverse conversion, would certainly seem to imply that a
> bitset could be larger than an unsigned long.

You're correct; I misread the requirement. Sorry.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

saroj@bear.com writes:

|>  In article <3993FE4D.B0DE1229@acm.org>,
|>    Pete Becker <petebecker@acm.org> wrote:

|>  Was it a 32-bit machine? In C++ environments(unlike Java), unsigned
|>  long is usually not 64 bits unless the machine is 64-bit. In other
|>  words, unsigned long usually matches the machine word size.

usually !=3D always.  On 16 bit machines, it is still required that
unsigned long be at least 32 bits.  On such machines, using unsigned
long instead of unsigned int could have a similar performance hit.

--=20
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orient=E9e objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh=FCttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Jonathan Lundquist wrote:
>
> On Fri, 11 Aug 2000 17:21:20 GMT, James Kuyper <kuyper@wizard.net>
> wrote:
>
> >
> >Section 23.3.5.2p2 says that the maximum number of bits in a bitset is
> >CHAR_BIT * sizeof(unsigned long), which caries the clear implication
> >that an entire bitset is stored in a single unsigned integer type...
>
> What?  23.2.5.2p2 says that bitset's operator&= returns *this.  That's
> all it says.  The only restriction I can find on N is that it is of
> type size_t.

You're correct, that was my misreading. I read it so fast that I missed
the the fact that the limit only applies to how many bits may be
initialized from an unsigned long, not how many bits there could be in a
bitset.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <8n1ivr$1np$1@nnrp1.deja.com>,
  assert@my-deja.com wrote:
> In article <8muqua$vsd$1@nnrp1.deja.com>,
>   Tom <the_wid@my-deja.com> wrote:
> > In article <8mtd2o$t4o$1@nnrp1.deja.com>,
> >   assert@my-deja.com wrote:
[SNIP]
> No, it doesnt depend on machine word size.
> Any upper bound on the requirements of bitset storage per
> user bit specified is entirely in the hands of the standard
> not your compiler. I dont care about your compiler
> or anyone elses compiler.

No, this a QOI issue. The standard has nothing to say about it, so the
upper bound on bitset storage is entirely in the hands of your
compiler.

>
> > What exactly do you want to do with your vector<bool> or bitset,
> anyway?
> >
>
> Maybe I want to implement a very very sloppy
> but conforming bitset and do as little work possible.

In that case, an array or unsigned long would probably be easiest, to
make the to_ulong member function and ulong constructor easy.

>
> In reality I don't want to do anything with it.
>
> My question was about the text of the standard.

And the standard has nothing to say about the memory requirements of
bitset.

See for yourself (although this is only the CD2 draft):

http://www.fmi.uni-konstanz.de/~kuehl/cd2/lib-
containers.html#lib.template.bitset

Tom


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Tom wrote:
>
> I would think that bitset would typically be implemented as an array or
> unsigned long, so I would expect bitset<1> to have sizeof(unsigned
> long) bytes. Same for bitset<7>. Same for bitset<31> on my platform.
> bitset<33> however uses 2 * sizeof(unsigned long) on my platform.
>

There's a subtle performance issue here: operations on unsigned long can
be enough slower than similar operations on unsigned int that it's
better to go with unsigned int. For Dinkumware's Java library I measured
the speed of BitSet operations using int (32 bits) and long (64 bits) as
the internal storage unit. On the PC, the int version was about 10%
faster than the long version.

--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Contributing Editor, C/C++ Users Journal (http://www.cuj.com)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

<assert@my-deja.com> wrote in message news:8mtd2o$t4o$1@nnrp1.deja.com...
>
>
> I have been reading about
> vector<bool> and bitset in the standard library.
> If a user is very concerned about space usage
> what container is preferable ? when I say concerned
> I mean that they are willing to hand code their own
> bitarray class to ensure that there is aproximately
> a 1 to 1 relationship between bits represented and
> storage space used (there may be some state
> information overhead).

Generally, a bool is represented as a byte.  This is because a byte is the
smallest easily manipulable chunk of memory in C/C++.  It may be that some
compilers use some other representation, but I'm sure that is by far the
most common.  A bitset is just that, a set of bits where one physical bit
represents one addressable bit.

>   23.2.5 Class vector<bool>               [lib.vector.bool]
>
>   1 To optimize space allocation, a specialization of vector for
>   bool elements is provided:

This is interesting.  That sentence implies that some implementations might
actually represent a vector of bools as one bit per bool?

> Suppose an implementation makes bools the same size as int.
> Can a conforming implementation use a vector<char>
> to represent the vector<bool> and consider it a space
> optimization ?

Yes.  But as per above, I'd be willing to bet every implementation of bool
you run across will be a byte (char).

> It would seem like there are no hard requirements placed
> on space usage.  The term "optimize" can be relative.

I would think "optimize" would imply that they would REDUCE space used, not
increase it.  It could very well be that they're actually implementing a
resizable bitset.  Can you trace through the code and see how they're doing
it?

> In the case of bitset, the language of the standard uses
> the words "bits". So things look better.
>
>   from 23.3.5 we have:
>
>   1 The header <bitset> defines a template class and several related
>   functions for representing and manipu   lating
>   fixed   size sequences of bits.

Yes.  A bitset is indeed a bitset.  But you should note the mention of
"fixed size."  The std::bitset requires you to define its size when the
bitset is created and AFAIK cannot be resized.

I'm intrigued by that mention of special "optimized" vectors of bools.  I
had always fallen to implementing my own resizable bitsets so as to ensure
both one bit per "bit" and the ability to alter its size dynamically.

Regarding the fixed-size bitset in the STL....  What is the reasoning behind
this?  Is it merely an effort at efficiency?  I more often encounter
situations where I don't know the size of the bitset I might need beforehand
and allocating a new larger bitset and doing a copy if I need to grow it
seems as if it should not be a necesasary requirement.


Sean

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3993FE4D.B0DE1229@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> Tom wrote:
> >
> > I would think that bitset would typically be implemented as an array
or
> > unsigned long, so I would expect bitset<1> to have sizeof(unsigned
> > long) bytes. Same for bitset<7>. Same for bitset<31> on my platform.
> > bitset<33> however uses 2 * sizeof(unsigned long) on my platform.
> >
>
> There's a subtle performance issue here: operations on unsigned long
can
> be enough slower than similar operations on unsigned int that it's
> better to go with unsigned int. For Dinkumware's Java library I
measured
> the speed of BitSet operations using int (32 bits) and long (64 bits)
as
> the internal storage unit. On the PC, the int version was about 10%
> faster than the long version.

Was it a 32-bit machine? In C++ environments(unlike Java),
unsigned long is usually not 64 bits unless the machine is
64-bit. In other words, unsigned long usually matches the
machine word size.

Thank you,
Saroj Mahapatra


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3993FE4D.B0DE1229@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> Tom wrote:
> >
> > I would think that bitset would typically be implemented as an
array or
> > unsigned long, so I would expect bitset<1> to have sizeof(unsigned
> > long) bytes. Same for bitset<7>. Same for bitset<31> on my platform.
> > bitset<33> however uses 2 * sizeof(unsigned long) on my platform.
> >
>
> There's a subtle performance issue here: operations on unsigned long
can
> be enough slower than similar operations on unsigned int that it's
> better to go with unsigned int. For Dinkumware's Java library I
measured
> the speed of BitSet operations using int (32 bits) and long (64 bits)
as
> the internal storage unit. On the PC, the int version was about 10%
> faster than the long version.

On my platform, sizeof(long)==sizeof(int) so it's not an issue.

However, using unsigned long as the underlying type will allow optimal
efficiency on the unsigned long constructor and the to_ulong member
function.

Tom


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

assert@my-deja.com wrote:
>=20
> I have been reading about
> vector<bool> and bitset in the standard library.
> If a user is very concerned about space usage
> what container is preferable ? when I say concerned
> I mean that they are willing to hand code their own
> bitarray class to ensure that there is aproximately
> a 1 to 1 relationship between bits represented and
> storage space used (there may be some state
> information overhead).
>=20
>   23.2.5 Class vector<bool>               [lib.vector.bool]
>=20
>   1 To optimize space allocation, a specialization of vector for
>   bool elements is provided:
>=20
> Suppose an implementation makes bools the same size as int.
> Can a conforming implementation use a vector<char>
> to represent the vector<bool> and consider it a space
> optimization ?

The standard only specifies the interface for vector<bool>; it places no
requirements on how much space it takes up. That's purely a QoI issue.

> It would seem like there are no hard requirements placed
> on space usage.  The term "optimize" can be relative.
>=20
> In the case of bitset, the language of the standard uses
> the words "bits". So things look better.
>=20
>   from 23.3.5 we have:
>=20
>   1 The header <bitset> defines a template class and several related
>   functions for representing and manipu=ADlating
>   fixed=ADsize sequences of bits.
>=20
> It looks like a stronger promise than what vector<bool>
> makes, but there still seems to be some wiggle room. It isnt

Wiggle room? There's enough room to send a galaxy through. The standard
places no restrictions on the implementation of a bitset, only on it's
interface.

Section 23.3.5.2p2 says that the maximum number of bits in a bitset is
CHAR_BIT * sizeof(unsigned long), which caries the clear implication
that an entire bitset is stored in a single unsigned integer type. Note:
it's not necessarily an unsigned long; bitset<N>, where N
<=3DCHAR_BIT*sizeof(unsigned), might be specialized to use an unsigned
int, instead.

There's a very obvious way to implement bitset that does just that.
However, the standard doesn't actually require such an implementation.

When choosing between a vector<bool> and a bitset<N>, the key
consideration is not the space requirements, which are
implementation-specific, but the interface, which is defined by the
standard. vector<bool> is variable size; bitset<N> is fixed size, and
there's an upper limit on N. Those are the relevant considerations.

If you absolutely need to cover the possibility that the implementors
did a lousy implementation of these two templates, then you must write
your own version. However, the same logic calls for writing your own
iostream, your own vector<int>, your own pair<int,char> classes. You've
got to draw the line somewhere - how much effort are you willing to
expend to cover the possibility of a lousy implementation?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Thanks for the answer.


In article <39935715.78420DE1@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
> assert@my-deja.com wrote:
> >=20
> > I have been reading about
> > vector<bool> and bitset in the standard library.
> > If a user is very concerned about space usage
> > what container is preferable ? when I say concerned
> > I mean that they are willing to hand code their own
> > bitarray class to ensure that there is aproximately
> > a 1 to 1 relationship between bits represented and
> > storage space used (there may be some state
> > information overhead).
> >=20
> >   23.2.5 Class vector<bool>               [lib.vector.bool]
> >=20
> >   1 To optimize space allocation, a specialization of vector for
> >   bool elements is provided:
> >=20
> > Suppose an implementation makes bools the same size as int.
> > Can a conforming implementation use a vector<char>
> > to represent the vector<bool> and consider it a space
> > optimization ?
>
> The standard only specifies the interface for vector<bool>; it places
no
> requirements on how much space it takes up. That's purely a QoI issue.
>
> > It would seem like there are no hard requirements placed
> > on space usage.  The term "optimize" can be relative.
> >=20
> > In the case of bitset, the language of the standard uses
> > the words "bits". So things look better.
> >=20
> >   from 23.3.5 we have:
> >=20
> >   1 The header <bitset> defines a template class and several related
> >   functions for representing and manipu=ADlating
> >   fixed=ADsize sequences of bits.
> >=20
> > It looks like a stronger promise than what vector<bool>
> > makes, but there still seems to be some wiggle room. It isnt
>
> Wiggle room? There's enough room to send a galaxy through. The
standard
> places no restrictions on the implementation of a bitset, only on it's
> interface.
>
> Section 23.3.5.2p2 says that the maximum number of bits in a bitset is
> CHAR_BIT * sizeof(unsigned long), which caries the clear implication
> that an entire bitset is stored in a single unsigned integer type.
Note:
> it's not necessarily an unsigned long; bitset<N>, where N
> <=3DCHAR_BIT*sizeof(unsigned), might be specialized to use an unsigned
> int, instead.
>
> There's a very obvious way to implement bitset that does just that.
> However, the standard doesn't actually require such an implementation.
>
> When choosing between a vector<bool> and a bitset<N>, the key
> consideration is not the space requirements, which are
> implementation-specific, but the interface, which is defined by the
> standard. vector<bool> is variable size; bitset<N> is fixed size, and
> there's an upper limit on N. Those are the relevant considerations.
>
> If you absolutely need to cover the possibility that the implementors
> did a lousy implementation of these two templates, then you must write
> your own version. However, the same logic calls for writing your own
> iostream, your own vector<int>, your own pair<int,char> classes.
You've
> got to draw the line somewhere - how much effort are you willing to
> expend to cover the possibility of a lousy implementation?
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting
with ]
> [ your news-reader.  If that fails, use mailto:std-
c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---
               ]
> [ FAQ: http://reality.sgi.com/austern_mti/std-
c++/faq.html              ]
>
>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

[cc'd to poster]


Sean Kelly <kensai@bellatlantic.net> wrote:
+ Regarding the fixed-size bitset in the STL....  What is the reasoning behind
+ this?  Is it merely an effort at efficiency?  I more often encounter
+ situations where I don't know the size of the bitset I might need beforehand
+ and allocating a new larger bitset and doing a copy if I need to grow it
+ seems as if it should not be a necesasary requirement.

Yes, here it's all about efficiency.  Since the bitset knows exactly how
large it is, there is no need to store bookkeeping information.  In fact,
in the implementations with which I am familiar (IIRC), all the bits are
stored inside the bitset directly, not allocated dynamically.  Thus, if
you declare an instance of bitset<8192> inside a function, you're going to
get a kilobyte of stuff on the stack.  Compare with a vector<> of stuff,
which in that same implementation is always about 12 bytes of bookkeeping
stuff in size and keeps all of the real elements on the heap.

As far as variable-sized bitsets go, I've been trying to collect solutions
and approaches to this problem, mostly from c.s.c++ and c.l.c.m.  Take a
look at

    http://sources.redhat.com/libstdc++/23_containers/howto.html#2

and let me know what you think.


Luck++;
Phil

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:

> Section 23.3.5.2p2 says that the maximum number of bits in a bitset is
> CHAR_BIT * sizeof(unsigned long), which caries the clear implication
> that an entire bitset is stored in a single unsigned integer type. Note:
> it's not necessarily an unsigned long; bitset<N>, where N
> <=CHAR_BIT*sizeof(unsigned), might be specialized to use an unsigned
> int, instead.

  Ah, but the standard doesn't actually say that.  It merely defines how
a bitset is constructed from an unsigned long and 23.3.5.2/31, which
defines the inverse conversion, would certainly seem to imply that a
bitset could be larger than an unsigned long.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Fri, 11 Aug 2000 17:21:20 GMT, James Kuyper <kuyper@wizard.net>
wrote:

>
>Section 23.3.5.2p2 says that the maximum number of bits in a bitset is
>CHAR_BIT * sizeof(unsigned long), which caries the clear implication
>that an entire bitset is stored in a single unsigned integer type...

What?  23.2.5.2p2 says that bitset's operator&= returns *this.  That's
all it says.  The only restriction I can find on N is that it is of
type size_t.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I have been reading about
vector<bool> and bitset in the standard library.
If a user is very concerned about space usage
what container is preferable ? when I say concerned
I mean that they are willing to hand code their own
bitarray class to ensure that there is aproximately
a 1 to 1 relationship between bits represented and
storage space used (there may be some state
information overhead).

  23.2.5 Class vector<bool>               [lib.vector.bool]

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

Suppose an implementation makes bools the same size as int.
Can a conforming implementation use a vector<char>
to represent the vector<bool> and consider it a space
optimization ?

It would seem like there are no hard requirements placed
on space usage.  The term "optimize" can be relative.


In the case of bitset, the language of the standard uses
the words "bits". So things look better.

  from 23.3.5 we have:

  1 The header <bitset> defines a template class and several related
  functions for representing and manipu   lating
  fixed   size sequences of bits.

It looks like a stronger promise than what vector<bool>
makes, but there still seems to be some wiggle room. It isnt
100% clear to me that a bitset must use 1 bit of storage
for each bit it represents to the user. Can a conforming
bitset implementation commit 32 bits of true representation
for every 31 bits that the user works with.
(suppose 1 is for error checking) ?

how about 8 bits of representation for every 7 used ?

how about 1 char to represent one bit ?
the ultimate in redundancy :)

If the answer to one of these questions is "no"
and the answer to anither is "yes"

Then what is the language that distinguishes the two cases ?






Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <8mtd2o$t4o$1@nnrp1.deja.com>,
  assert@my-deja.com wrote:
>
>
> I have been reading about
> vector<bool> and bitset in the standard library.
> If a user is very concerned about space usage
> what container is preferable ? when I say concerned
> I mean that they are willing to hand code their own
> bitarray class to ensure that there is aproximately
> a 1 to 1 relationship between bits represented and
> storage space used (there may be some state
> information overhead).
>
>   23.2.5 Class vector<bool>               [lib.vector.bool]
>
>   1 To optimize space allocation, a specialization of vector for
>   bool elements is provided:
>
> Suppose an implementation makes bools the same size as int.
> Can a conforming implementation use a vector<char>
> to represent the vector<bool> and consider it a space
> optimization ?

I don't think that there is a guarantee that each bool is stored in a
bit, no. OTOH, all implementations will use a bit for each bool padding
up to the nearest byte or word or whatever.

>
> It would seem like there are no hard requirements placed
> on space usage.  The term "optimize" can be relative.
>
> In the case of bitset, the language of the standard uses
> the words "bits". So things look better.
>
>   from 23.3.5 we have:
>
>   1 The header <bitset> defines a template class and several related
>   functions for representing and manipu   lating
>   fixed   size sequences of bits.
>
> It looks like a stronger promise than what vector<bool>
> makes, but there still seems to be some wiggle room. It isnt
> 100% clear to me that a bitset must use 1 bit of storage
> for each bit it represents to the user. Can a conforming
> bitset implementation commit 32 bits of true representation
> for every 31 bits that the user works with.
> (suppose 1 is for error checking) ?

sizeof(anthing) is an integer, so if CHAR_BIT is 8, then there is no
way that it can use only 31 bits. In fact, 31 is prime so the only way
your bitset<31> could possibly occupy only 31 bits is on a platform
where CHAR_BIT == 31. An unusual platform indeed.

>
> how about 8 bits of representation for every 7 used ?
>
> how about 1 char to represent one bit ?
> the ultimate in redundancy :)

I would think that bitset would typically be implemented as an array or
unsigned long, so I would expect bitset<1> to have sizeof(unsigned
long) bytes. Same for bitset<7>. Same for bitset<31> on my platform.
bitset<33> however uses 2 * sizeof(unsigned long) on my platform.

Also, the compiler is allowed to pad Classes and structs to whatever
size it feels like (I believe). For example:
struct s {
int i;
char c;
};

My compiler gives sizeof(s) == 8, although adding up the sizeofs of the
elements gives only 5. It depends on things like the machine word size.

What exactly do you want to do with your vector<bool> or bitset, anyway?

Tom


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]