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.

Abhinay Pandey
  • 46
  • 3
  • 15
  • 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. – SHP Feb 24 '21 at 06: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. – Swift - Friday Pie Feb 24 '21 at 06: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>` a good practice? – Abhinay Pandey Feb 24 '21 at 07:03
  • 1
    Starting with a [good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) is much much better than from nonsensical coding contests. – Evg Feb 24 '21 at 07: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. – A M Feb 24 '21 at 07:25
  • Given the confusion that C-style arrays can produce, it might be better to refer to them as "abnormal arrays" rather than "normal arrays". – Pete Becker Feb 24 '21 at 14:03

1 Answers1

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.

john
  • 85,011
  • 4
  • 57
  • 81
  • 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>` a good practice? – Abhinay Pandey Feb 24 '21 at 06:58
  • @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>`, in the kind of coding I do clarity is more important than speed. – john Feb 24 '21 at 07:00
  • `vector 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). – Marc Glisse Feb 24 '21 at 07:06
  • @AbhinayPandey `vector>` is a [jagged matrix](https://stackoverflow.com/q/11535384/995714). It's simple but isn't good for memory or performance at all. [What are the Issues with a vector-of-vectors?](https://stackoverflow.com/q/38244435/995714) – phuclv Feb 24 '21 at 08:21