This is a fairly high level question and I'm not if it can even be answered but I'm hoping that its possible, as it would really help out my code.
I'm coding some AI A* Pathfinding which keeps a map of areas that are accessible. This map is huge (usually 512x512) and has the resolution of about 200.
If the entire thing is coded standardly, using normal bools, it will take about a gig of ram, as a single bool is 4 bytes.
While reading about this I found out that it may be possible to force assign or create a type that is literally one bit, on or off. I would like to know how to do this so that I can create a map of single bits that can be turned on or off and checked like a normal bool (or some semi-complicated method).
Do any of you know how to create such a type? I don't mind it being difficult or complicated as it will be much better than the method I'm using right now.
You could use a std::vector<bool> or a std::bitset. std::vector<bool> is specialised precisely for this space optimisation.
Do you think you could go into a little bit more detail please and show me some sample code of how I would use it?
I am having to create a 2D array to store a 2D grid co-ordinates. If I used the vector, I'm not sure how to create a dynamic 2D vector array. And it seems bitset is fixed so I wouldn't be able to create a dynamic 2D array with it.
The dynamic_bitset is pretty neat but it exists for the scenario where you need to define the number of bits at run-time which is impossible with the std::bitset. As far as whether to use a vector<bool> or a bitset that depends on which user interface suits your needs.
Does std::vector<bool> really use individual bits?
Everything that I have read suggests that it is but nothing is concrete.
Meyers writes in Effective STL, "In a typical implementation, each "bool" stored in the "vector" occupies a single bit, and an eight bit byte holds eight "bools"".
The C++ std doesn't really contain much of a description of this template specialization which seems odd to me. It seems like it was a concept that was abandoned at some point but not removed from the standard. I have read many scathing articles that imply that the vector<bool> is a defective concept and that it should be totally avoided. The problem is that many of the vector user interface functions doesn't work as you might expect for a vector of bool.
As Meyers pointed out, "There are really only two things wrong with a vector<bool>. First, its not an STL container. Second, it doesn't hold bools. Other than that there's not much to object to."
Why on earth would you want to write your own class when the STL provides a perfectly good std::bitset? one of the other code guru links that I posted had a very similar question answered with the suggestion of using a vector of bitset. In this case the OP knows how many bits are needed so I see nothing wrong with using the std::bitset. The vector<bool> is simply a mess to try and figure out how to use correctly.