CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17
  1. #1
    Join Date
    Mar 2010
    Posts
    14

    Exclamation 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

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Mar 2010
    Posts
    14

    Thumbs up Re: Force Assigning A Bool to a Single Bit

    Quote Originally Posted by laserlight View Post
    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.

  4. #4
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Force Assigning A Bool to a Single Bit

    Quote 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.

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  5. #5
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,727

    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

  6. #6
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    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.

  7. #7
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb 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.

  8. #8
    Join Date
    Feb 2005
    Posts
    2,160

    Re: Force Assigning A Bool to a Single Bit

    Does std::vector<bool> really use individual bits?

  9. #9
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: Force Assigning A Bool to a Single Bit

    Quote Originally Posted by hoxsiew View Post
    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.

  10. #10
    Join Date
    Jan 2009
    Posts
    1,689

    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.

  11. #11
    Join Date
    Feb 2005
    Posts
    2,160

    Re: Force Assigning A Bool to a Single Bit

    That's what I was thinking: a vector of struct with bitfields.

  12. #12
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb 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.

  13. #13
    Join Date
    Feb 2005
    Posts
    2,160

    Re: Force Assigning A Bool to a Single Bit

    I thought bitset was boost. Sorry.

  14. #14
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Force Assigning A Bool to a Single Bit

    Quote 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:
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  15. #15
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Force Assigning A Bool to a Single Bit

    Quote Originally Posted by Shard View Post
    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.

Page 1 of 2 12 LastLast

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
  •  





Click Here to Expand Forum to Full Width

Featured