-
March 29th, 2010, 01:16 AM
#1
Force Assigning A Bool to a Single Bit
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.
Thanks,
Shard
-
March 29th, 2010, 01:39 AM
#2
Re: Force Assigning A Bool to a Single Bit
You could use a std::vector<bool> or a std::bitset. std::vector<bool> is specialised precisely for this space optimisation.
-
March 29th, 2010, 01:54 AM
#3
Re: Force Assigning A Bool to a Single Bit
Originally Posted by laserlight
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.
-
March 29th, 2010, 02:19 AM
#4
Re: Force Assigning A Bool to a Single Bit
Originally Posted by Shard
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?
You know how to use std::vector, right? It has roughly the same interface, except that it provides flip() to toggle bits, and has a few caveats like the data not necessarily being stored contiguously.
Originally Posted by Shard
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.
You might want to use a std::vector<bool> to simulate a 2D array, or just use a std::vector<std::vector<bool> >, except that the latter would impose a space penalty.
Alternatively, if you can tolerate the use of bool being the size of a byte, and yet bool on your system is 4 bytes, you might just use unsigned char instead of bool.
-
March 29th, 2010, 03:57 AM
#5
Re: Force Assigning A Bool to a Single Bit
There's also the option of a std::vector of std::bitset<512>
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman
-
March 29th, 2010, 09:29 AM
#6
Re: Force Assigning A Bool to a Single Bit
I think Boost has a dynamic_bitset class. I'm not sure how it's different than a vector<bool>....it may simply be there since vector<bool> is discouraged due to it not being a true STL container.
-
March 29th, 2010, 10:48 AM
#7
Re: Force Assigning A Bool to a Single Bit
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.
There are plenty of examples at these links for you to compile and run.
http://www.boost.org/doc/libs/1_42_0...ic_bitset.html
http://cplusplus.com/reference/stl/bitset/
http://cplusplus.com/reference/stl/vector/
I'm of the opinion that the bitset classes provide a better user interface. They provide a more complete user interface related to bit operations.
-
March 29th, 2010, 11:54 AM
#8
Re: Force Assigning A Bool to a Single Bit
Does std::vector<bool> really use individual bits?
-
March 29th, 2010, 12:20 PM
#9
Re: Force Assigning A Bool to a Single Bit
Originally Posted by hoxsiew
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."
Do a google search on vector<bool> and you won't find to many praising it as a wonderful solution. The only things that I can find are articles indicating why it is a bad idea to use it and why the concept is defective. Here is another one which makes me wonder, does anyone know if vector<bool> was removed from the 0x std?
http://www.gotw.ca/publications/N1185.pdf
http://www.gotw.ca/publications/N1211.pdf
More interesting links. OP, you can easily google for these yourself.
http://www.linuxtopia.org/online_boo...mming_192.html
http://www.codeguru.com/forum/archiv.../t-463125.html
http://www.codeguru.com/forum/archiv.../t-364791.html
Last edited by kempofighter; March 29th, 2010 at 12:31 PM.
Reason: Added link.
-
March 29th, 2010, 12:33 PM
#10
Re: Force Assigning A Bool to a Single Bit
I would recommend just writing your own class for this. Bitfields aren't that complex to do, I use them all the time.
-
March 29th, 2010, 01:04 PM
#11
Re: Force Assigning A Bool to a Single Bit
That's what I was thinking: a vector of struct with bitfields.
-
March 29th, 2010, 01:23 PM
#12
Re: Force Assigning A Bool to a Single Bit
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.
-
March 29th, 2010, 01:29 PM
#13
Re: Force Assigning A Bool to a Single Bit
I thought bitset was boost. Sorry.
-
March 29th, 2010, 01:31 PM
#14
Re: Force Assigning A Bool to a Single Bit
Originally Posted by kempofighter
Why on earth would you want to write your own class when the STL provides a perfectly good std::bitset?
As the OP replied to my suggestion:
Originally Posted by Shard
And it seems bitset is fixed so I wouldn't be able to create a dynamic 2D array with it.
That said, I recall having a good experience with boost:ynamic_bitset, so I can second that suggestion if Boost is an option.
-
March 29th, 2010, 02:37 PM
#15
Re: Force Assigning A Bool to a Single Bit
Originally Posted by Shard
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.
Might want to re-check your math. While I'm not sure what you mean by "resolution of 200", 512x512 bools of 4 bytes each will only take up 1 megabyte.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|