标签: bitvector

我很困惑有点矢量如何工作(不太熟悉位向量).这是给出的代码.有人可以带我走过这个吗？

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

特别是,checker做什么？

Scott Meyers的书第18项有效STL:50改进您对标准模板库的使用的具体方法说避免vector <bool>因为它不是STL容器而且它实际上并不存在bool.

以下代码:

vector <bool> v; 
bool *pb =&v[0];

不会编译,违反STL容器的要求.

错误:

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization

bool返回类型应该是T&,但为什么它是特殊情况vector<T>::operator []？

什么是T&真正组成的呢？

该项目进一步说:

deque<bool> v; // is a STL container and it really contains bools

这可以用作替代品vector<bool>吗？

有人可以解释一下吗？

我注意到在运行以下代码时,向量比bool数组慢得多.

int main() 
{
    int count = 0;
    int n = 1500000;
    // slower with c++ vector<bool>
    /*vector<bool> isPrime;
    isPrime.reserve(n);
    isPrime.assign(n, true);
    */
    // faster with bool array 
    bool* isPrime = new bool[n];

    for (int i = 0; i < n; ++i)
        isPrime[i] = true;


    for (int i = 2; i< n; ++i) {
        if (isPrime[i])
            count++;
        for (int j =2; i*j < n; ++j )
            isPrime[i*j] = false;
    }

    cout <<  count << endl;
    return 0;
}

有什么方法可以让我vector<bool> …

什么是执行按位操作的最佳方法vector<bool>？

据我所知,vector<bool>是一个每布尔使用一位的特化.我选择vector<bool>了节省内存的原因.我知道存在一些问题vector<bool>但是对于我的需要它是合适的.

现在 - 对整个这样的向量进行逐位运算的最高效方法是什么？

如果我在for循环中读取并读出每个bool并将其存储回来,我理解它的方式是在内部执行更多操作以访问实际值.

谢谢!

我有四个比特向量的集合,例如:

b1 = 00001010
b2 = 10100111
b3 = 10010010
b4 = 10111110

我想得到那些在给定位向量的0,1,2,3或4中设置的位的掩码.因此m0将是未在四个位向量中的任何一个中设置的位掩码,m3是在三个位向量中设置的那些位的掩码,等等:

m0 = 01000000
m1 = 00000001
m2 = 00111100
m3 = 10000000
m4 = 00000010

使用按位运算符查找这些掩码的最快方法是什么？

我假设它们对0和4位的操作最少:

m0 = ~(b1 | b2 | b3 | b4)  // 4 ops
m4 = b1 & b2 & b3 & b4     // 3 ops

对于其他选项,我不太确定我的方法操作最少:

m1 = ((b1 ^ b2) & ~(b3 | b4)) | (~(b1 | b2) & (b3 ^ b4)) // 9 operations
m2 = ((b1 ^ …

BitArray和BitVector 32结构有什么区别,BitVector 32结构比BitArray有什么优势？为什么BitVector 32结构比BitArray更有效？

提前致谢.

周杰伦...

John Feminella 在回答这个问题时说:

如果您真的很喜欢,可以通过将每个整数表示为位向量并执行快速傅立叶变换来实现这种子二次方,但这超出了本答案的范围.

解决该问题中描述的问题的渐近最优方法是什么？

在考虑这个问题时,我开始想知道是否std::copy()和/或是std::fill专门的(我真的意味着优化)std::vector<bool>.

这是C++标准所要求的,或者,它是C++ std库供应商的常用方法吗？

简单来说,我想知道以下代码:

std::vector<bool> v(10, false);
std::fill(v.begin(), v.end(), true);

以任何方式更好/不同于:

std::vector<bool> v(10, false);
for (auto it = v.begin(); it != v.end(); ++it) *it = true;

要非常严格 - 可以,可以说:std::fill<std::vector<bool>::iterator>()进入内部表示std::vector<bool>并设置整个字节而不是单个位？我认为交std::fill朋友std::vector<bool>不是图书馆供应商的大问题吗？

[UPDATE]

下一个相关的问题:我可以(或其他任何人)专门研究这样的算法std::vector<bool>,如果不是已经专门化了吗？这是C++标准允许的吗？我知道这将是不可移植的 - 但仅适用于一个选定的std C++库？假设我(或其他任何人)找到了去std::vector<bool>私人部分的方法.

Java中是否存在用于稀疏位向量的任何着名库？

(并且有没有指导稀疏对于使用它们与java.util.BitSet有什么用？)

它是众所周知的是std::vector<bool>不符合标准的容器的需求,主要是因为打包表示防止T* x = &v[i]从一个指针返回一个布尔值.

我的问题是:当reference_proxy重载address-of operator&以返回pointer_proxy 时,这可以得到补救/缓解吗？

在大多数实现中,指针代理可以包含与reference_proxy相同的数据,即指向打包数据的指针和用于隔离指向的块内的特定位的掩码.然后,pointer_proxy的间接将产生reference_proxy.基本上两个代理都是"胖"指针,然而,与基于磁盘的代理容器相比,这些指针仍然相当轻.

而不是T* x = &v[0]一个会然后做auto x = &v[0],并使用x像if(*x)没有问题.我也希望能够写作for(auto b: v) { /* ... */ }

问题:这种多代理方法是否适用于STL的算法？或者某些算法真的依赖于x需要真实的需求bool*？或者是否有太多连续的用户定义转换需要阻止它工作？在尝试完全完成上述实施草图之前,我想知道任何这样的障碍物.

更新(基于@HowardHinnant的回答和关于comp.std.c ++的古老讨论)

你可以在很大程度上模仿内置类型:对于任何给定的类型T,一对代理(例如reference_proxy和iterator_proxy)可以在reference_proxy :: operator&()和iterator_proxy :: operator*的意义上相互一致. ()是彼此相反的.

但是,在某些时候,需要将代理对象映射回来以表现为T*或T&.对于迭代器代理,可以重载operator - >()并访问模板T的接口,而无需重新实现所有功能.但是,对于参考代理,您需要重载operator.(),这在当前C++中是不允许的(尽管Sebastian Redl在BoostCon 2013上提出了这样的提议).您可以像引用代理中的.get()成员一样进行冗长的解决方法,或者在引用中实现所有T的接口(这是对vector :: bit_reference所做的),但这会丢失内置语法或引入用户定义的转换,这些转换没有用于类型转换的内置语义(每个参数最多只能有一个用户定义的转换).