Jerry Coffin (jcoffin@taeus.com) wrote:
: Yes.  vector<bool> is _required_ to be specialized to be efficient in
: its use of space, typically at a considerable expense in speed.

I don't understand this and question its truth in general. If the only
issue is that vector<bool> must shift and mask to index the vector, then
for many codes it will be faster than a vector<int>. I'm assuming a good
optimizing compiler and a fully inlined operator[] used in any loops.
There are two reasons for it being faster. First caches will be better
utilized. Second, inside a loop, fewer loads are needed. (This assumes a
lack of aliasing problems. Which should be easy to guarantee as no external
pointer should point into a vector<bool>, but communicating that to the
compiler might be difficult.)

-Z-


[ 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 <7hrrl0$8mq$1@nnrp1.deja.com>, danny_pav
<danny_pav@my-dejanews.com> wrote:

> Isn't there a limit to the size of the bitset?  Or is that just in some
> implementations?  I recall seeing a limit of 32 so that the bitset is
> just a glorified long.  This, however may have been a specific
> implementation.

Memory should be the only limitation (and the max size of a size_t).  The
standard doesn't mention a max size.  My implementation let me put a
bitset<0xffffffff> on the heap, but I couldn't run with it! :-)

When putting bitset on the stack, I could only get up to bitset<261568>
before I irritated the compiler.  32 seems like a pretty low limit to
have.

-Howard
---
[ 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 <MPG.11a609e065743464989ab7@news.mindspring.com>,
  jcoffin@taeus.com (Jerry Coffin) wrote:
>
> In article <373BE805.6EBF2189@epfl.ch>, kim.allemand@epfl.ch says...
> >
> > Hello,
> > I need an array of boolean values with functions like Set(index),
> > Reset(index) and Test(index). The size of the array or bitset ranges
> > from 10 to 500.
> >
Isn't there a limit to the size of the bitset?  Or is that just in some
implementations?  I recall seeing a limit of 32 so that the bitset is
just a glorified long.  This, however may have been a specific
implementation.


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don'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              ]

Hello,
I need an array of boolean values with functions like Set(index),
Reset(index) and Test(index). The size of the array or bitset ranges
from 10 to 500.

1. Can we assume that bitset is at least as efficient as vector<bool>?
(time speaking)

2. I read that the size if bitset has to be a const, is there a way to
avoid that? I would not like to compile each time the size is different.

Thankx, Kim
--
"Heureux ceux qui louchent, car ils verront Dieu deux fois !"
URL: http://dmawww.epfl.ch/~allemand/


[ 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 14 May 1999 15:04:59 GMT, Kim Allemand <kim.allemand@epfl.ch> wrote:

>I need an array of boolean values with functions like Set(index),
>Reset(index) and Test(index). The size of the array or bitset ranges
>from 10 to 500.
>
>1. Can we assume that bitset is at least as efficient as vector<bool>?
>(time speaking)

Most likely your implementation is such that bitset<N> is more efficient
than vector<bool>(N).  This is because the size of the bitset is known
at compile time, and so the amount of stack space needed is known at
compile time.

>2. I read that the size if bitset has to be a const, is there a way to
>avoid that? I would not like to compile each time the size is different.

In bitset<N>, 'N' must be a compile time constant.  Tough luck!

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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 <373BE805.6EBF2189@epfl.ch>, kim.allemand@epfl.ch says...
>
> Hello,
> I need an array of boolean values with functions like Set(index),
> Reset(index) and Test(index). The size of the array or bitset ranges
> from 10 to 500.
>
> 1. Can we assume that bitset is at least as efficient as vector<bool>?
> (time speaking)

Yes.  vector<bool> is _required_ to be specialized to be efficient in
its use of space, typically at a considerable expense in speed.
Typically a vector<int> will be substantially faster than either.
About the worst case at the present time would be 8-byte ints, in
which case your array of 500 elements would still consume less than
4K.  I can't think of too many 64-bit machines where using 4K is
likely to be a substantial problem.  On smaller machines, less memory
is likely to be available, but int is also likely to be smaller so
your array would consume less memory.

> 2. I read that the size if bitset has to be a const, is there a way to
> avoid that? I would not like to compile each time the size is different.

There's no way to avoid it, but unless you're programming some sort of
microcontroller, it's hard to believe it would be a problem: 500 bits
will fit into 63 bytes.  If you're doing to use a bitset, it's
probably easiest to just leave the size at 500, and use some other
variable to keep track of the largest valid index in a particular run.

Alternatively, you could use vector<bool>, but given its greater
generality, it's likely to use at least 63 bytes of extra code, so
unless you're also using it elsewhere, you're looking at using more
total memory by going this route.

If you're interested in speed, and can live with using a few hundred
bytes more memory, chances are that vector<int> is really your best
bet, and when you add things up, the total cost in memory is likely to
be minimal.


[ 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              ]