im reading through data structures for game programmers and im on the chapter for bitvectors. its pretty much frying my brain right now. So what is the point of a bitvector? So far I know you look into the 32 bits of an integer , and that integer is within an array of whatever size. So I want to retrieve on bit from one of the integers, what woukld be its value? 1 or 0? okay, so then what am i trying to accomplish here? someone enlighten me

[source lang="cpp"]#pragma once
#include <iostream>
using namespace std;

class Bitvector
{
protected:
unsigned long int *m_array; //declare a pointer to an usigned(from 0 to positives) long integer array
int m_size; //keeps track of the size of the array

Bitvector(int p_size) //the constructor. pass in what size you want the bitvector to be
{
m_array = 0; //pointer points to nothing
m_size = 0; //the size is zero
Resize(p_size); //calls the resize function to acutally set the size of the array
}

~Bitvector() //the destructor
{
if(m_array != 0) //if the array actually has something inside it
{
delete[] m_array; //delete whatever is inside the array
m_array = 0; //point the array pointer to zero
}
}

void Resize(int p_size) //resize function. pass in the size you want to resize the vector to
{
unsigned long int *newvector = 0; //declaring a an unsigned long int pointer

if(p_size % 32 == 0) //if p_size is perfectly divisible by 32
{
p_size = p_size / 32; //then divide and set p_value to that value
}
else // if its not perfectly divivsible by 32
{
p_size = (p_size / 32) + 1; //than add one to the result
}
newvector = new unsigned long int[p_size]; //now make the newvector array pointer allocate the memory passed in by the user
if(newvector == 0) //if newvector did not successfully allocate memory
{
return; //quit the function
}

int min; //the minimum value

if(p_size < m_size) //if the passed in size is less than the original size of the array
{
min = p_size; // than the minimum value is equivalent to the passed in value
}
else //if the passed in size is greater than the original size of the array
{
min = m_size; //then the minimum value is equivalent to the original size
}

int index; //declare an index int that will loop through the array

for(index = 0; index < min; index++)
{
newvector[index] = m_array[index]; //copy the contents from the old array to new new array
}
m_size = p_size; //m_size now equal the new size of the array
if(m_array != 0) //if m_array pointer is pointing to an array
{
delete[] m_array; //delete the contents of the array
}
m_array = newvector; //than make m_array point to the newvector
}

bool operator[] (int p_index)
{
int cell = p_index / 32;
int bit = p_index % 32;
return (m_array[cell] & (1 << bit)) >> bit;
}[/source]

Out of curiosity are you really using a one space indent or is the source block mangling your code so it looks that way?

i like messy code

If you need a large vector of bits, this representation is much more compact than an array of bools, because each bool will need to take up at least one full byte in memory. If you don't need a large vector of bits, there is no point whatsoever.

but in what situation would i need a large vector of bits over an array of booleans. and in general what situation would i need either of these?

Interestingly, [font=courier new,courier,monospace]std::vector<bool>[/font] is required by the standard to be a specialization that packs the [font=courier new,courier,monospace]bool[/font]s into single bits for the very reason of saving space. It was included in the standard as an example of how to write proxying containers. I believe many committee members later regretted that.

The [font=courier new,courier,monospace]std::bitset[/font] container also provides a bit-oriented container, complete with boolean operations and a cunning string-serialization interface. Guaranteed to take only one bit per bit, and when compiled with release-level optimization generates the same code as C-style bitmask operations for smaller-sized sets.

Since the C++ standard library has provided these appropriate containers for about a generation, perhaps the book include the bitvector class as exposition?

Interestingly, [font=courier new,courier,monospace]std::vector<bool>[/font] is required by the standard to be a specialization that packs the [font=courier new,courier,monospace]bool[/font]s into single bits for the very reason of saving space. It was included in the standard as an example of how to write proxying containers. I believe many committee members later regretted that.

The [font=courier new,courier,monospace]std::bitset[/font] container also provides a bit-oriented container, complete with boolean operations and a cunning string-serialization interface. Guaranteed to take only one bit per bit, and when compiled with release-level optimization generates the same code as C-style bitmask operations for smaller-sized sets.

Since the C++ standard library has provided these appropriate containers for about a generation, perhaps the book include the bitvector class as exposition?

pretty much. i like it since it gets ur hands dirty and lets you see the the process of how these actually work rather than just hand you a stl function.