<分区>
编辑:我将原来的问题留在下面,但转换并不像我声称的那么慢。我的原始程序中存在一个错误,导致调用该函数的输入比我预期的要长得多。实际上,从 string
转换而来有点vector
只需要大约 1.5 倍的时间来转换其他方式。
我需要将字符串转换为 vector<bool>
.但是,转换非常慢。我明白 vector<bool>
是 vector 的特化。我尝试使用 vector<char>
相反,但这同样慢。
这是我的代码:
std::vector<bool> frombytes(const std::string &bytes)
{
std::vector<bool> output;
for (unsigned int i = 0; i < bytes.length(); i++)
{
unsigned char byte = bytes[i];
for (unsigned int j = 0; j < 8; j++)
{
output.push_back(byte >> (7 - j) & 1);
}
}
}
我在想,也许通过一次写入 8 位,我可以让它更快。但是,我想不出这样做的方法。任何的意见都将会有帮助。谢谢!
更多信息:
- 我试过
vector::reserve
,但这并没有太大的区别。
- 我正在使用带有“
-O3
”标志的 g++ 编译程序。
我不确定这种转换是否必要。您可以使用简单的访问器函数来获取单个位,并且可以编写简单的自定义迭代器,将字符串中的位公开为单个 bool 值。这完全回避了转换成本。转换非常浪费,因为在内部 vector<bool>
通常将实现为无符号字符或整数的 vector ,并带有特殊的访问器,可以旋转其中的位。 vector<bool>
中数据的内存表示很可能和 std::string
将与可能的位和/或字节顺序异常(exception)相同。因此,如果您似乎非常关心性能,那么跳过整个喧嚣是最有意义的。
访问器非常简单:
bool getBit(size_t index, const std::string &str)
{
assert(index/8 < str.size());
return (str[index/8] >> (index%8)) & 1;
}
void setBit(size_t const index, bool const val, std::string &str)
{
assert(index/8 < str.size());
char c = str[index/8];
c &= ~(1 << (index%8));
c |= char(val) << (index % 8);
str[index/8] = c;
}
如果您想将字符串迭代为位,您可以使用以下迭代器适配器(未测试):
template <typename Container>
class const_bit_iterator {
using c_value_type = const Container::value_type;
using iterator = Container::const_iterator;
static constexpr size_t modulus = 8u * sizeof(c_value_type );
size_t index = 0;
iterator it = {};
constexpr c_value_type bitmask() const { return c_value_type (1) << (index % modulus); }
public:
using value_type = const bool;
struct end_tag_t {};
static constexpr end_tag_t end_tag = {};
explicit bit_iterator(const Container &container) : it(container.begin()) {}
explicit bit_iterator(end_tag_t, const Container &container) :
index(modulus * container.size()), it(container.end()) {}
bool operator*() const { return get(); }
bool get() const { return (*it) & bitmask(); }
bit_iterator &operator++() {
++ index;
if (!(index % modulus)) ++ it;
return *this;
}
bit_iterator operator++(int) {
auto it = *this;
++ *this;
return it;
}
bit_iterator &operator--() {
-- index;
if ((index % modulus) == (modulus - 1)) -- it;
return *this;
}
bit_iterator operator--(int) {
auto it = *this;
-- *this;
return it;
}
bool operator==(const bit_iterator &o) const { return index == o.index; }
bool operator!=(const bit_iterator &o) const { return index != o.index; }
bool operator<(const bit_iterator &o) const { return index < o.index; }
};
template <typename Container>
class const_bit_adapter
{
const Container &ref;
public:
const_bit_adapter(const Container &container) : ref(container) {}
const_bit_iterator begin() const { return const_bit_iterator(ref); }
const_bit_iterator end() const { return const_bit_iterator(const_bit_iterator::end_tag, ref); }
};
template <typename Container>
const_bit_adapter<Container> as_const_bits(const Container &container)
{ return {container}; }
template <typename Container>
const_bit_adapter<Container> as_bits(const Container &container)
{ return {container}; }
使用示例:
std::vector<int> bits(32);
size_t n = 0;
for (bool b : as_const_bits(bits))
++n;
assert(n == bits.size() * 8u * sizeof(decltype(bits)::value_type));