std::bitset woes

[grahamr (work)]

Apparently you can't construct a bitset without a constant value in the constructor and I was wondering if there was a way around that:

Example:

std::cout << std::bitset<50>(123456789) << std::endl; // legal
size_t bits = 50;
std::cout << std::bitset<bits>(123456789) << std::endl; // illegal


Not being able to create a bitset with a variable makes it near useless.

My actual problem is taking place in a loop and I wish to output the bits for huffman code for each one - and since huffman codes are of variable length I need variable length bitsets. I thought bitset's would be ideal for this situation.

Thanks, G.

[Philip Nicoletti]

boost has a dynamic bitset ...

http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html

[Viorel]

I think std::bitset has another limitation: the maximum number of bits is limited to the size of a long integer (32 bits).

Maybe you can consider the std::vector< bool > class, which stores each value in a single bit, and does not limit the size of the bitset.

[Mitsukai]

or.

typedef unsigned char ByteT;

struct CByteT
{
union
{
ByteT Val;

struct
{
ByteT Bit0: 1;
ByteT Bit1: 1;
ByteT Bit2: 1;
ByteT Bit3: 1;
ByteT Bit4: 1;
ByteT Bit5: 1;
ByteT Bit6: 1;
ByteT Bit7: 1;
};
};
};

std::vector<CByteT>

[Hobson]

It seems that lots of people has problem with that std::bitset has fixed size. As suggested above, you can find dynamic bitset in boost library.
bitset is NOT limited to 32 bits.
Before using vector<bool>, read Scott Meyers' Effective STL chapter 18 and consider all points there, maybe they do not affect your case and then you could use this construct.
The most dirty trick I ever heard about making bitset dynamic is to... supply source file, compiler and linker with your app, and recompile program at runtime :D Author claims that it works great :) I cannot find a link now, but I will paste it here as soon as I find it.

Cheers,
Hob

[miteshpandey]

Maybe you can consider the std::vector< bool > class, which stores each value in a single bit, and does not limit the size of the bitset.

Not sure about the exact details but has something to do while using the iterators of vector containing bool, experts advise against it.

[Mitsukai]

recompiling programs at runtime, the beginning of human-like learning computers :)

[grahamr (work)]

Rather not start creating too many dependancies with libraries that others in the company don't have/use. As soon as this program gets in the compile chain and the build machine goes looking for non-existant boost libraries I will have to try to explain it and either argue for it or (most likely) remove the dependancy. Was this one of the problems being addressed in C++0x?

Also my experience (from about a year ago) is that most of the boost library does not compile on MSVC6 - the last time I tried I got hundreds of error messages so I gave up. Maybe I am just lazy but I prefer to simply download a library, double click the .msi and have it ready to use in seconds than to wait a couple of hours to only compile half of it, the other half failing to build.

Also the fact that it is just for debugging purposes means I can live with out it.

[miteshpandey]

Can't you use vector of bitsets?

[Mitsukai]

what is wrong with my code?

[miteshpandey]

what is wrong with my code?

OP wants a variable number of bits while your code has fixed number of bits

[jfaust]

Rather not start creating too many dependancies with libraries that others in the company don't have/use. As soon as this program gets in the compile chain and the build machine goes looking for non-existant boost libraries I will have to try to explain it and either argue for it or (most likely) remove the dependancy. Was this one of the problems being addressed in C++0x?

Also my experience (from about a year ago) is that most of the boost library does not compile on MSVC6 - the last time I tried I got hundreds of error messages so I gave up. Maybe I am just lazy but I prefer to simply download a library, double click the .msi and have it ready to use in seconds than to wait a couple of hours to only compile half of it, the other half failing to build.

Also the fact that it is just for debugging purposes means I can live with out it.

A couple notes:
- most boost libraries do compile with VC6. There are only a few that do not.
- Scott Meyer's includes the boost librariesamong the top five Most Important C++ Software Ever (http://www.artima.com/cppsource/top_cpp_software.html). Considering the other four entries, this is impressive. It's worth getting familiar with it.

Jeff

[Mitsukai]

OP wants a variable number of bits while your code has fixed number of bits
just put it in a vector and you have dynamic number of bits.

[grahamr (work)]

A couple notes:
- most boost libraries do compile with VC6. There are only a few that do not.
- Scott Meyer's includes the boost librariesamong the top five Most Important C++ Software Ever (http://www.artima.com/cppsource/top_cpp_software.html). Considering the other four entries, this is impressive. It's worth getting familiar with it.

Jeff

My experience with Boost is that the last time I tried to compile it I simply saw reams of error messages ('error count exceeds 100 - stopping compilation').

I doesn't really matter if Ghandi listed it among the top five most important C++ Software Ever, if my boss (and only other developer) doesn't want it then it's not going in. I've had to bring in my own reference books (his is just MSDN). He's never read LSC++SD despite my constant urging, nor has he read any of the other bibles (Stroustrop, Josuttis, Alexandrescu, GoF, etc.).

G.

[grahamr (work)]

just put it in a vector and you have dynamic number of bits.

No it won't since I would have a multiple of 8 bits. Not much help when I want to display just 5 bits as a string is it?

[Mitsukai]

just store how much bits u want with the vector class in your own class.
or make a vector of bools but that is 8 times bigger as it has to be

[grahamr (work)]

Would it be possible to format the output using ignore (or similar) to eat the first n bytes?
ie:

std::cout << std::cin.ignore((32 - codelist[i].length))
<< std::bitset<32>(codelist[i].code)
<< std::endl; // doesn't work

[MrViggy]

Apparently you can't construct a bitset without a constant value in the constructor and I was wondering if there was a way around that:

Example:

std::cout << std::bitset<50>(123456789) << std::endl; // legal
size_t bits = 50;
std::cout << std::bitset<bits>(123456789) << std::endl; // illegal


Not being able to create a bitset with a variable makes it near useless.
Just wanted to clarify that in the illegal line of code you are not "constructing a bitset with a constant value in the constructor" here. You need to pass a constant into the template (that's what the value is between the '<' and '>'), so that the compiler can create the concrete bitset class for you. All templates need this kind of compile time information, however in most templates this information is a data type.

Viggy

[grahamr (work)]

I realised after posting that templates are compiletime not runtime - it's easy to forget sometimes.

A dynamic bitset would be extremely useful. Unfortunately by the time the C++ Standards committee gets around to ratifying C++0x and the major vendors get around to supporting it we'll be edging towards 2010:-(

And a quick look down the C++0x list of features they looking to support I didn't see dynamic bitsets.

G.

[SuperKoko]

just store how much bits u want with the vector class in your own class.
or make a vector of bools but that is 8 times bigger as it has to be
AFAIK Most implementations of vector<bool> use an optimal space (which implies that vector<bool> is not a container).
Which means that you can't optimize for space except using compression algorithms, but compressions algorithms, in the general case, can't make you gain space.

So, I suggest you use vector<bool> since each bool use 1 bit on usual implementations.

[grahamr (work)]

I was going to start a new thread on use of vector<bool> versus other methods but since it was brought up here and is related I will continue.

Is vector<bool> still not deprecated?

I know there are articles warning against it's use (Meyers/Sutter) and that it breaks container & iterator rules but while I am aware of these facts I can see a solid use for the type.

As mentioned I am writing a huffman encoder. I can see several possible routes for storing of the bitstream while it is being constructed:
1) Store the bitstream as vector<bool> or
2) as vector<unsigned char> or
3) Create a class called bitstream that will allow me to pop and push bits and handle everything in the background. Because random access isn't necessary this could be based on a queue rather than a vector.

Because I will need eventual access to the stream as-is I am leaning towards 2 & 3.

Thanks, Graham Reeds.

[Viorel]

A possible scenario is creating your own Bitstream class, but implemented in a simple manner, based on std::vector<bool> class. For example, derive it from private std::vector<bool>, or have a member of std::vector<bool> type.

I think it will work fine, since you probably are not going to use some specific features, like iterators, not fully supported by std::vector<bool>. I suppose such operations, like push_back or [ ], offered by std::vector<bool>, are enough.

If some day you will be presumptively convinced that this approach is not good (for instance it is not quick enough), then re-implement it without changing the interface.

I hope this makes sense.