Below is the code I used for comparing:
// 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;
}
output
----ARRAY------
Time taken when Using C-style Array : 112931 microseconds
---VECTOR-----
Time taken when Using STL vector : 330641 microseconds
As you can see the array version of my function performs on average 3 times faster than that of its Vector version. (I ran it multiple times and got similar results)
Question:
Are vectors really that slow compared to arrays?
I thought their performance was supposed to be on par.
This is the URL I run it on an online environment http://cpp.sh/2ubur
vector<int> row_offset = {0, 0, 1, -1};
vector<int> col_offset = {1, -1, 0, 0};
this causes 2 heap allocations of data (almost) every time the function is called.
int row_offset[4]={0, 0, 1, -1};
int col_offset[4]={1, -1, 0, 0};
this does not cause 2 heap allocations of data (almost) every time the function is called.
std::vector<int> foo = {1,2,3}
is similar to int* foo = new int[]{1,2,3}
, not int foo[] = {1,2,3}
in creation costs.
std::array<int, 3> foo={1,2,3}
is the std library version of "fixed size buffer with data in it". std::vector
is a dynamically sized buffer.
Here is a live example where I swapped std::vector
for std::array
, and changed the C-array version to dynamically create and destroy the arrays. You'll notice the time swaps.