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

You could use a std::vector<bool> or a std::bitset. std::vector<bool> is specialised precisely for this space optimisation.

Quote:

---

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.

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.

There's also the option of a std::vector of std::bitset<512>

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.

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.

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

Quote:

---

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.

Quote:

---

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.

Quote:

---

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

I would recommend just writing your own class for this. Bitfields aren't that complex to do, I use them all the time.

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

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.

I thought bitset was boost. Sorry.

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::dynamic_bitset, so I can second that suggestion if Boost is an option.

Quote:

---

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.

Quote:

---

Originally Posted by Lindley

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.

---

A 512 x 512 map with each unit being divided into about 4 squares.

So 512 X 512 x 200 X 4 = 209715200 bytes.

Ah. Well, for a space that large, another consideration is how many of those bytes you typically expect to be set. If the percentage is high, then one of the aforementioned approaches will work. But if you are only expecting to actually set a relatively small number of those bits, then you should consider a sparse representation. Something like this:

Code:

---

struct Coordinate
{
    short x, y, r, s;//x,y is [0,511], r is [0,199], s is [0,3].
    bool operator<(const Coordinate &rhs) const
    {
        if (x < rhs.x)
            return true;
        if (x == rhs.x && y < rhs.y)
            return true;
        if (x == rhs.x && r == rhs.y && r < rhs.r)
            return true;
        if (x == rhs.x && r == rhs.y && r == rhs.r && s < rhs.s)
            return true;
        return false;
    }
};

std::map<Coordinate,bool> active;

---

Since each entry will require at least 12 bytes (probably more like 20 after map overhead), this would only represent an improvement over a dynamic_bitset if the percentage of active bits is expected to be is < 1&#37;.