为什么当我用 stl 向量替换数组时我的代码变慢，在 C++ 中，数组比向量更快？

Question

下面是我用来比较的代码：

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <chrono>
using namespace std::chrono;
using namespace std;
            
bool existHelperArrayVersion(string &word, int i, int u_i, int u_j, vector<vector<char>>& Board)
{
    if(i>=word.length())
    {
        return true;
    }
    else
    {
        bool answer  = false;      
        if(Board[u_i][u_j] == word[i])
        {
            char temp             = Board[u_i][u_j];
            Board[u_i][u_j]       = '?';
            int row_len           = Board.size();  
            int col_len           = Board[0].size();

            // Uses Array
            int row_offset[4]={0,  0, 1, -1};
            int col_offset[4]={1, -1, 0,  0};
            
            for(int k=0; k<4; k++)
            {
                int v_i = u_i + row_offset[k];
                int v_j = u_j + col_offset[k];
                
                if( !(0 >v_i || v_i >= row_len || 0>v_j || v_j >= col_len)  && (Board[v_i][v_j] != '?'))
                    answer |= existHelperArrayVersion(word, i+1, v_i, v_j, Board);
            }
               
            if(i+1 == word.length())
                answer |= true;
            Board[u_i][u_j] = temp;
        }
        return answer;
    }
}

bool existHelperVectorVersion(string &word, int i, int u_i, int u_j, vector<vector<char>>& Board)
{
    if(i>=word.length())
    {
        return true;
    }
    else
    {
        bool answer  = false;
        if(Board[u_i][u_j] == word[i])
        {
            char temp             = Board[u_i][u_j];
            Board[u_i][u_j]       = '?';
            int row_len           = Board.size();  
            int col_len           = Board[0].size();

            //Uses Vectors
            vector<int> row_offset = {0,  0, 1, -1};
            vector<int> col_offset = {1, -1, 0,  0};
            
            for(int k=0; k<4; k++)
            {
                int v_i = u_i + row_offset[k];
                int v_j = u_j + col_offset[k];
                
                if( !(0 >v_i || v_i >= row_len || 0>v_j || v_j >= col_len)  && (Board[v_i][v_j] != '?'))
                    answer |= existHelperVectorVersion(word, i+1, v_i, v_j, Board);
            }
               
            if(i+1 == word.length())
                answer |= true;
            Board[u_i][u_j] = temp;
        }
        return answer;
    }
}

bool exist(vector<vector<char>>& board, string word, int option) 
{
    if(option == 0)
        cout << "----ARRAY------\n";
    else if(option == 1)
        cout << "---VECTOR-----\n";
        
    bool answer   = false;
    for(int i=0; i<board.size(); i++)
    {
        for(int j=0; j<board[i].size(); j++)
        {
            if(option == 0)
                answer |= existHelperArrayVersion( word, 0, i, j, board);
            else if(option == 1)
                answer |= existHelperVectorVersion( word, 0, i, j, board);
                
            if(answer)
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    
    string word                 =   "AAAAAAAAAAAAAAB";
    vector<vector<char>> board  =   {{'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'},
                                     {'A','A','A','A','A','A'}};

    auto start    = high_resolution_clock::now();
    bool answer   = exist(board, word, 0);
    auto stop     = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cout << "Time taken when Using C-style Array : " << duration.count() << " microseconds" << endl;
    
    start         = high_resolution_clock::now();
    answer        = exist(board, word, 1);
    stop          = high_resolution_clock::now();
    duration      = duration_cast<microseconds>(stop - start);
    cout << "Time taken when Using STL vector    : " << duration.count() << " microseconds" << endl;
    
}

输出

----ARRAY------
Time taken when Using C-style Array : 112931 microseconds
---VECTOR-----
Time taken when Using STL vector    : 330641 microseconds

如您所见，我函数的数组版本的执行速度平均比向量版本快 3 倍。（我运行它多次并得到类似的结果）
问题：
与数组相比，向量真的那么慢吗？
我认为他们的表现应该是相当的。
这是URL我运行它上了一个在线环境http://cpp.sh/2ubur

Answer 1

        vector<int> row_offset = {0,  0, 1, -1};
        vector<int> col_offset = {1, -1, 0,  0};

这会导致每次调用该函数时（几乎）进行 2 次堆数据分配。

        int row_offset[4]={0,  0, 1, -1};
        int col_offset[4]={1, -1, 0,  0};

这不会导致每次调用该函数时（几乎）进行 2 次堆数据分配。

std::vector<int> foo = {1,2,3} 类似于 int* foo = new int[]{1,2,3}，而不是 int foo[] = {1,2,3} 创建成本。

std::array<int, 3> foo={1,2,3}

是“其中包含数据的固定大小缓冲区”的标准库版本。 std::vector 是一个动态大小的缓冲区。

Here 是一个实例，我将 std::vector 换成了 std::array，并更改了 C 数组版本以动态创建和销毁数组。您会注意到时间互换。

Answer 2

您在函数中创建向量，因此每次函数调用都会重新分配它们的内存并在函数结束时销毁它们。相反，数组会不断融入您的程序中。

尝试将向量移出函数，然后两个函数都同样快：http://cpp.sh/53t2z

Answer 3

如果替换：

  vector<int> row_offset = { 0,  0, 1, -1 };
  vector<int> col_offset = { 1, -1, 0,  0 };

与：

  static vector<int> row_offset; row_offset  = { 0,  0, 1, -1 };
  static vector<int> col_offset; col_offset = { 1, -1, 0,  0 };

差异会小很多。对于第二个版本，向量不会每次都从头开始构建。

这仅用于演示目的，并非可遵循的示例。

无论如何，这里最好的方法是将 std::vector 替换为 std::array，因为这里的尺寸是固定的。

顺便说一下 http://cpp.sh std::array 的版本甚至似乎比原始数组版本快一些。

为什么当我用 stl 向量替换数组时我的代码变慢，在 C++ 中，数组比向量更快？

Why does my code slow down when i replace arrays with stl vectors, in c++, are arrays more faster than vectors?

c++

arrays

performance

heap-memory

stdvector