CODEWITHSUNDEEP
c++arraysvector
Abhinay Pandey
Abhinay Pandey

Reputation: 64

std::vector vs std::array vs normal array

I give online coding contests, where the speed of the program is everything. Over the time I have come across 3 ways to use the concept of array in C++. The questions of the contests usually require us to create a dynamic array of the given size. So its just a one time creation of the dynamic array as per the input and we don't resize the array again.

std::vector

Vectors look the most fancy and everyone tends to love them. But few days back one of the question gave me the TIME_LIMIT_EXCEEDED error when doing it with vectors.
When I implemented the same logic with normal arrays, the program was submitted successfully.
On researching, I found out that using the push_back() function takes a long time as compared to a normal arr[i]=x;

std::array

I don't have much knowledge about its performance. But it looks like a nicer way to handle arrays.

default arrays in C++

I do the dynamic allocation using int *arr=new int[given_size]; and then use the array normally.
Passing an array as argument is not as simple as vectors but its not a big deal.

Apart from this there are also times when I have to work with 2D arrays and I am always unsure about what could be the fastest way. vector<vector<int>> is regarded slow in some forums and so is using multidimensional pointers. So I like to use a 1D array with a typedef function to handle its index but it gets complicated when I have to pass a row to a function.

Most of the answers in forums are based on what the OP was trying to do and this gives different answers. What I want to know is which is the best and long term way to use to have maximum speed/efficiency.

Upvotes: 1

Views: 1971

Answers (1)

john
john

Reputation: 87959

push_back takes a long time compared to arr[i]=x;.

Sorry but you are showing your lack of experience with vectors here, because your examples do two different things.

You are comparing something like this code

vector<int> vec;       // vector created with size zero
for (...)
    vec.push_back(x);  // vector size increases

with this code

int arr[N];
for (...)
    arr[i] = x;

The difference is that in the first case the vector has size 0 and it's size increases as you add items to it (this takes extra time), but in the second case the array starts out at it's final size. With an array this is how it must be, but with vectors you have a choice. If you know what the final size of the vector is you should code it like this

vector<int> vec(N); // vector created at size N, note use () not []
for (...)
    vec[i] = x;

That is the code you should be comparing with the array code for efficiency,

You might also want to research the resize and reserve methods of a vector. Vectors (if nothing else) are much more flexible than arrays.

Upvotes: 6

Related Questions