c++ - 为什么 vector<int> 在以下情况下比 vector<bool> 快

Question

这个现象是我在LeetCode题目N-Queens编程时发现的.

我有两个版本的可接受代码，唯一的区别是我存储哈希表的方式，一个是使用 vector<int>另一个正在使用 vector<bool> .具体来说，两个版本的代码如下:

版本 1，vector<int> , 运行时间:4 毫秒

class Solution {
public:
void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row, vector<int>& mup, vector<int>& m45dgr, vector<int>& m135dgr)
{
    int n = crtrst.size();
    
    if (row == n)
    {
        finalrsts.push_back(crtrst);
        return;
    }
    
    for (int j=0; j<n; j++)
    {
        if (mup[j] && m45dgr[j-row+n-1] && m135dgr[row+j])
        {
            crtrst[row][j] = 'Q';
            mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = 0;
        
            dfs(crtrst,finalrsts,row+1,mup,m45dgr,m135dgr);
        
            crtrst[row][j] = '.';
            mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = 1;
        }
    }
}

vector<vector<string>> solveNQueens(int n) 
{
    vector<vector<string>> finalrsts;
    vector<string> crtrst(n,string(n,'.'));
    vector<int> mup(n,1);
    vector<int> m45dgr(2*n-1,1); // degree 45: '\'
    vector<int> m135dgr(2*n-1,1); // degree 135: '/';
    int row = 0;
    dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr);
    return finalrsts;
}
};

第 2 版，vector<bool> ，运行时间:12毫秒

class Solution {
public:
void dfs(vector<string>& crtrst, vector<vector<string>>& finalrsts, int row, 
    vector<bool>& mup, vector<bool>& m45dgr, vector<bool>& m135dgr)
{
    int n = crtrst.size();
    
    if (row == n)
    {
        finalrsts.push_back(crtrst);
        return;
    }
    
    for (int j=0; j<n; j++)
    {
        if (mup[j] && m45dgr[j-row+n-1] && m135dgr[row+j])
        {
            crtrst[row][j] = 'Q';
            mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = false;
        
            dfs(crtrst,finalrsts,row+1,mup,m45dgr,m135dgr);
        
            crtrst[row][j] = '.';
            mup[j] = m45dgr[j-row+n-1] = m135dgr[row+j] = true;
        }
    }
}

vector<vector<string>> solveNQueens(int n) 
{
    vector<vector<string>> finalrsts;
    vector<string> crtrst(n,string(n,'.'));
    vector<bool> mup(n,true);
    vector<bool> m45dgr(2*n-1,true); // degree 45: '\'
    vector<bool> m135dgr(2*n-1,true); // degree 135: '/';
    int row = 0;
    dfs(crtrst,finalrsts,row,mup,m45dgr,m135dgr);
    return finalrsts;
}
};

据我所知，vector<bool>使用 1 位而不是 bool 存储每个元素变量(可能是 2 个字节)和 vector<int>使用 4 字节存储每个元素。所以vector<bool>似乎比 vector<int> 小.但是，为什么它比 vector<int> 慢？

Answer 1

访问单个位通常比访问完整的可寻址单元(C++ 术语中的字节)慢。例如，要写入一个字节，您只需发出一条写入指令(x86 上为 mov)。要写入一个位，您需要加载包含它的字节，使用按位运算符设置字节中的正确位，然后存储结果字节。

位 vector 的紧凑大小非常适合存储要求，但它会导致速度变慢，除非您的数据变得足够大以至于缓存问题发挥作用。

如果你想要速度并且仍然比每个值 4 个字节更有效，请尝试 vector<unsigned char> .