布尔向量实现

有人能告诉我这个向量实际上是如何工作的吗？特别是关于它的operator=和operator boolVecProxy阶级和主要阶级的operator[]。我知道需要减少使用的内存量。就像 bool 是 1 个字节一样，使用这个类，我们可以为每个元素将其减少 7 位。我想VecProxy需要将每一点都分发到它的位置。

所以，这是代码：

template <>
class Vector<bool>
{
private:
typedef unsigned char byte;
size_t _size;
size_t _capacity;
size_t _byte_size;
byte* _data;
public:
Vector(size_t capacity = 0) : _size(0),
_capacity(capacity),
_byte_size(0),
_data(nullptr)
{
if (capacity > 0)
{
_data = new byte[capacity / 8 + (capacity % 8 != 0)];
if (!_data) throw "Out of memory";
}
}
class VecProxy
{
size_t _idx;
byte* _vec_ptr;
public:
VecProxy(size_t idx, byte* vecPtr) : _idx(idx), _vec_ptr(vecPtr) {}
VecProxy& operator=(bool val)
{
size_t char_idx = _idx / 8;
size_t bit_idx = _idx % 8;
if (val)
_vec_ptr[char_idx] |= 1 << bit_idx;
else
_vec_ptr[char_idx] &= ~(1 << bit_idx);
return *this;
}
operator bool()
{
size_t char_idx = _idx / 8;
size_t bit_idx = _idx % 8;
return (_vec_ptr[char_idx] >> char_idx) & 0x01;
}
};
VecProxy operator[](size_t idx)
{
if (idx >= _size) throw "Out of bounds";
return VecProxy(idx, _data);
}
Vector& resize(size_t new_size)
{
_capacity = new_size;
_size = _capacity < _size ? _capacity : _size;
_byte_size = _size / 8 + (_size % 8 != 0);
byte* tmp = new byte[_capacity / 8 + (_capacity % 8 != 0)];
if (!tmp) throw "Out of memory";
for (size_t i = 0; i < _byte_size; ++i)
tmp[i] = _data[i];
if (!_data)
delete[] _data;
_data = tmp;
}
Vector& push_back(bool val)
{
if (_size == _capacity)
{
if (_capacity < 10)
resize(_capacity + 10);
else
resize(_capacity * 1.5);
}
VecProxy(_size++, _data) = val;
return *this;
}
};

我template<>一定有点困惑.但在.h文件的其他部分放置了标准vector的主要实现。

所以，我想具体说明我的问题：

VecProxy课堂上operator=到底发生了什么？我对那个if感到非常困惑.
operator bool()的return声明尚不清楚。
但我实际上对operator[]有所了解.

from

就像 bool 是 1 个字节一样，使用这个类，我们可以为每个元素将其减少 7 位。

我们知道您了解每个位都有不同的含义，每个位代表不同的布尔值，然后将这些位打包到一个字节中以节省空间。

为了再次获取布尔值，您必须找到正确的字节，然后找到该字节中的位。_vec_ptr[char_idx]找到正确的字节。1 << bit_idx生成隔离位的位掩码。

让我们仔细看看VecProxy的operator=：

VecProxy& operator=(bool val)
{
size_t char_idx = _idx / 8; // find byte index
size_t bit_idx = _idx % 8; // find bit index
if (val) // boolean is true, so bit must be set to 1
_vec_ptr[char_idx] |= 1 << bit_idx;
else // boolean false, so bit must be set to 0
_vec_ptr[char_idx] &= ~(1 << bit_idx);
return *this;
}

让我们将函数拆分得更多一点：

VecProxy& operator=(bool val)
{
size_t char_idx = _idx / 8; // find byte index
size_t bit_idx = _idx % 8; // find bit index
byte & loc = _vec_ptr[char_idx]; // reference to byte that must be updated
byte mask = 1 << bit_idx; // mask isolating bit that must be updated
if (val) // boolean is true, so bit must be set to 1
loc |= mask;
else // boolean false, so bit must be set to 0
loc &= ~(mask);
return *this;
}

如果提供的bool为val，则位需要为 1。这很容易，您只需在位掩码中或。假设我们想要第三位

00000100

我们有

10101010

申请或

10101010 OR 00000100 = 10101110

但是如果值为假，我们需要将位设置为零我们不能用OR做到这一点，但我们可以用AND做到这一点。不幸的是，如果你这样做微不足道，你会得到

11111111 AND 00000000 = 00000000

那是没有用的。你想保留其他位。您需要反转蒙版

11111111 AND 11111011 = 11111011

这就是~运营商在loc &= ~(mask);所做的

事实证明，赋值运算符几乎毫无用处。获得VecProxy的唯一方法是通过

VecProxy operator[](size_t idx)

它按值返回。它不能用于在Vector中设置位。您可以在代理中设置一点，仅此而已。此更改无法传播到Vector。

myvec[42] = true;

无法编译，因为它将更新临时副本。

通过引用返回VecProxy以便可以更新vector是一种不平凡的重写。

现在让我们看看运算符布尔值

operator bool()
{
size_t char_idx = _idx / 8;
size_t bit_idx = _idx % 8;
return (_vec_ptr[char_idx] >> char_idx) & 0x01;
}

此函数告诉您是否设置了此代理对象表示的位。它是如何做到的：我们找到带有_vec_ptr[char_idx]的字节，然后将整个字节移过来，将感兴趣的位带入第一个位，并屏蔽除感兴趣的位之外的所有内容。如果设置了该位，则返回 true。

假设我们从

10101010

我们想要第三位：

10101010 >> 2 == 00101010

(注意！注意标志扩展！如果字节是无符号的，你将得到11101010以保持数字负数。在这里无关紧要，但它会在其他情况下得到你。

现在我们使用掩码0x01(00000001(来检查位是否设置。

00101010 & 00000001 = 00000000

C++从那里处理它，将 0 转换为false的返回

相关内容

最新更新

热门标签：