1

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.

Improve this question
6
  • Actually you can try using classical global C array, where upper-bound of the size can be inferred by problem data range. std::vector is slowlier, but very easy to use when sometimes array size varies. But std::vector can be simulated with global array like int arr[maxn].std::array have few differences in online programming contests. New a dynamic array is offen considered useless or not effective. Commented Feb 24, 2021 at 6:50
  • You're comparing apples to oranges. Vector is a wrapper around relocatable storage. arr[i]=x; is analog of vector's operator[] by function. std::array is a structure containing a statically sized array, easy to copy by assignment and can be returned from a function (array cannot be). And with int *arr=new int[given_size]; you do what vector does, only manually. Commented Feb 24, 2021 at 6:54
  • @Swift-FridayPie Thanks for the explanation. So using the operator[] of vector we can achieve the similar performance to arrays? And does passing and returning vectors affect performance in any way, compared to passing the pointer? Also can you throw some light on using 2D arrays. Is vector<vector<int>> a good practice? Commented Feb 24, 2021 at 7:03
  • 1
    Starting with a good C++ book is much much better than from nonsensical coding contests. Commented Feb 24, 2021 at 7:23
  • 2
    Basically there is no need to discuss. Online contests are not about serious software development. Every dirt can be and is put there. Nothing from there can be used to learn the C++ language or good coding styles. The only things that you may learn are to implement an algorithm in a quick and dirty way. So, you should simply continue to use VLAs, raw pointers for owned memory, new and macros and all these things that a serious C++ developer will never do. So, please do and enjoy. Seriously. The only caveat is that if you want to become a professional software developer, then do not do. Commented Feb 24, 2021 at 7:25

1 Answer 1

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I apologize for my lack of experience. So if we pre-allocate vector size, it is going to give the same performance? Also can you throw some light on using 2D arrays. is vector<vector<int>> a good practice?
@AbhinayPandey It's certainly going to give better performance because you don't have to keep reallocating the vector as it's size increases. I'm afraid I have no particular knowledge concerning vector<vector<int>>, in the kind of coding I do clarity is more important than speed.
vector<int> vec(N); will fill the array with 0s, so it is still a bit more work (there are Q&A on this site about avoiding this initialization).
@AbhinayPandey vector<vector<int>> is a jagged matrix. It's simple but isn't good for memory or performance at all. What are the Issues with a vector-of-vectors?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.