Here is a very simple statically sized bit vector implementation. It requires C++11 to function since it relies on the <cstdint> header, but this header is fairly commonly found since it's based on a C99 feature. In a pinch you can use the C <stdint.h> header and simply use types in the global namespace instead.
Note: This was typed on-the-fly and isn't tested at all. I didn't even verify it would compile. So, there may be errors.
#include <cstdint> // ::std::uint64_t type
#include <cstddef> // ::std::size_t type
#include <algorithm>
class my_bitvector_base {
protected:
class bitref { // Prevent this class from being used anywhere else.
public:
bitref(::std::uint64_t &an_int, ::std::uint64_t mask)
: an_int_(an_int), mask_(mask)
{
}
const bitref &operator =(bool val) {
if (val) {
an_int_ |= mask_;
} else {
an_int_ &= ~mask_;
}
return *this;
}
const bitref &operator =(const bitref &br) {
return this->operator =(bool(br));
}
operator bool() const {
return ((an_int_ & mask_) != 0) ? true : false;
}
private:
::std::uint64_t &an_int_;
::std::uint64_t mask_;
};
};
template < ::std::size_t Size >
class my_bitvector : public my_bitvector_base {
private:
static constexpr ::std::size_t numints = ((Size + 63) / 64);
public:
my_bitvector() { ::std::fill(array, array + numints, 0); }
bool operator [](::std::size_t bitnum) const {
const ::std::size_t bytenum = bit / 64;
bitnum = bitnum % 64;
return ((ints_[bytenum] & (::std::uint64_t(1) << bitnum)) != 0) ? true : false;
}
bitref operator[](::std::size_t bitnum) {
const ::std::size_t bytenum = bit / 64;
bitnum = bitnum % 64;
::std::uint64_t mask = ::std::uint64_t(1) << bitnum;
return bitref(ints_[bytenum], mask);
}
private:
::std::uint64_t ints_[numints];
};
// Example uses
void test()
{
my_bitvector<70> bits; // A 70 bit long bit vector initialized to all false
bits[1] = true; // Set bit 1 to true
bool abit = bits[1]; // abit should be true.
abit = bits[69]; // abit should be false.
}
The whole my_bitvector_base thing is to create a sort of private type. You can mention it in the interface or implementation for derived classes because it's protected, but you can't mention it other contexts. This prevents people from storing a copy of a bitref. This is important because a bitref only really exists to allow assignment to the result of operator [] because the C++ standards committee, in all their wisdom, has not implemented operator []= or something similar for assigning to an array element.
As you can see, a bit vector is basically an array of bits. Fancier bit vectors will simulate an 'infinite' array of bits all initialized to true or false. They do this by tracking the very last bit that has been set and all bits before it. And if you ask for a bit after that, they just return the initialized value.
A good bit vector will also implement operator & and other such niceties so they behave sort of like a very large unsigned integer with reference to bit manipulation operations.
vector<bool> is a specialization of the vector template. A normal bool variable requires at least one byte, but since a bool only has two states the ideal implementation of vector is such that each bool value only requires one bit. This means the iterator must be specially-defined, and cannot be a bool*.
from Thinking CPP Vol-2 from Bruce Eckel chapter 4: STL Containers & Iterators
发布评论
评论（2）
这是一个非常简单的静态大小的位向量实现。它需要 C++11 才能运行，因为它依赖于
注意：这是即时输入的，根本没有经过测试。我什至没有验证它是否可以编译。所以，可能会有错误。
整个 my_bitvector_base 的事情就是创建一种私有类型。您可以在派生类的接口或实现中提及它，因为它是受保护的，但不能在其他上下文中提及它。这可以防止人们存储
bitref的副本。这很重要，因为bitref真正存在只是为了允许对operator []的结果进行赋值，因为 C++ 标准委员会尽其所能，尚未实现运算符 []=或类似的东西用于分配给数组元素。如您所见，位向量基本上是位数组。更高级的位向量将模拟一个“无限”的位数组，所有位都初始化为 true 或 false。他们通过跟踪已设置的最后一位及其之前的所有位来做到这一点。如果您在此之后要求一点，他们只会返回初始化值。
一个好的位向量还将实现运算符 & 和其他此类细节，因此它们的行为有点像一个非常大的无符号整数，涉及位操作操作。
Here is a very simple statically sized bit vector implementation. It requires C++11 to function since it relies on the
<cstdint>header, but this header is fairly commonly found since it's based on a C99 feature. In a pinch you can use the C<stdint.h>header and simply use types in the global namespace instead.Note: This was typed on-the-fly and isn't tested at all. I didn't even verify it would compile. So, there may be errors.
The whole
my_bitvector_basething is to create a sort of private type. You can mention it in the interface or implementation for derived classes because it'sprotected, but you can't mention it other contexts. This prevents people from storing a copy of abitref. This is important because abitrefonly really exists to allow assignment to the result ofoperator []because the C++ standards committee, in all their wisdom, has not implementedoperator []=or something similar for assigning to an array element.As you can see, a bit vector is basically an array of bits. Fancier bit vectors will simulate an 'infinite' array of bits all initialized to true or false. They do this by tracking the very last bit that has been set and all bits before it. And if you ask for a bit after that, they just return the initialized value.
A good bit vector will also implement
operator &and other such niceties so they behave sort of like a very large unsigned integer with reference to bit manipulation operations.摘自《Thinking CPP Vol-2》，来自 Bruce Eckel
第 4 章：STL 容器和迭代器
这本书可以免费下载：
http://www.mindviewinc.com/Books/downloads.html
它包含有关位和 C++ 的更多信息
from Thinking CPP Vol-2 from Bruce Eckel
chapter 4: STL Containers & Iterators
The book can be downloaded for free at
http://www.mindviewinc.com/Books/downloads.html
and it contains more informations on bits and C++