当我使用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

- African_king

---

你是如何编译代码的？确保启用了优化。测量未经优化的构建是没有意义的。 - François Andrieux

你正在比较int[4]和std::vector<int>。这不是std::vector的一个好用例，因为大小是固定的。更好的比较方式是int[4]和std::array<int, 4>，或者比较std::vector<int>和动态分配的数组。 - François Andrieux

std::vector 无法与普通数组或 std::array 相媲美。简单的原因是它需要某种间接方式（即指针）来适应动态大小的更改。这反过来意味着，为了使用向量地址访问第三个元素，您首先需要从向量中读取第一个元素的地址，然后再向前移动三个元素。对于数组，数组的地址就是第一个元素的地址。 - Ulrich Eckhardt

仅为完整起见：每当您考虑使用new T[count]时，您应该考虑使用vector<T>，这可能是您在某些地方阅读并误解的内容。 - Ulrich Eckhardt

@UlrichEckhardt 这个类比非常恰当，现在它在更深层次上有了意义。 - African_king

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::array"是“具有固定大小且其中包含数据”的标准库版本。而 "std::vector" 是一个动态大小的缓冲区。

这里提供了一个实时示例，其中我使用 std::array 替换了 std::vector，并将 C 数组版本更改为动态创建和销毁数组。您会注意到时间的差异。

- Yakk - Adam Nevraumont

---

这太有道理了。谢谢。 - African_king

Answer 2

你在函数中创建了向量，因此每次调用函数都会新分配它们的内存，并在函数结束时销毁它们。相反，数组是永久内嵌于您的程序的。

试着把你的向量移出函数，这样两个函数就一样快了: http://cpp.sh/53t2z

- gexicide

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::array 替换 std::vector，因为这里有固定的大小。

顺便说一下，在http://cpp.sh上，使用 std::array 的版本甚至比原始数组版本略快。

- Jabberwocky

---

将这些向量设为常量，我认为它们不会被修改。同时，将它们设为std::array，因为它们不会被修改。再详细解释一下：如果你不想修改它们并将它们设为常量，编译器会在你意外修改它们时告诉你。相比于链接器错误、运行时错误和仅在客户系统在半夜发生的错误，更喜欢编译器错误。 ;) - Ulrich Eckhardt

@UlrichEckhardt 这只是为了演示而已，不是要跟随的例子。我已经编辑了答案以明确这一点。 - Jabberwocky