In certain problems we can use an array of integers to solve the problem. But those can also be solved by using array of vectors.
On which factors should I decide whether to use plain array of integers or array of vectors? If vectors, then what are the advantages?
1 Like
It depends the constraints of the problem. Let’s consider a simple graph implementation.
If the constraints are small and the graph is dense:
2-d array: PRO: O(1) access of elements CON: Extra space
If the constraints are high and graph is sparse:
array of vector: PRO: Efficient space CON:O(n) access of elements
where n is the max number of neighbors of a particular node.
1 Like
It depends on the space and time constraints.
For example: If your are given no information about the number of elements an input array can have, better use vector. And in a way, vector<> works like a linked list with O(1) access like an array.
You can use various STL functions, push_back(), back(), end(), clear, erase() to make use of vector. And array of vector, vector name[max_size]; , is preferred over 2D array when you need to have a header nodes like data structure, or rather adjacency list.
Bottom line: Use both arrays and vectors so as to get experience about both.
2 Likes
Advantages of using vector over arrays are:
- First of all, it saves a lot of space .This makes the difference between being able to solve a problem or not. Like for example a graph problem having 10^5 nodes and 10^5 edges.
The array would make us store edges in 2-D matrix but the size of matrix would exceed the total memory provided by the compiler. - It’s clean and efficient. The variety of functions that come with vector offer a lot more flexibility than array in terms of memory usage.
But some times arrays prevail:
- Like in order to reuse a vector you have to clear it using clear() function. But in array you just start from index 0.(It may lead to frustration as this leads to unnecessary WA in questions which are easy and we overlook such small mistakes )
As for query about SGARDEN problem on codechef the vector usage helps as the number in the cycle itself are not important but the length of the cycle is hence same vector can reused and the size can be accessed in one go with size() function rather than keeping a count of the elements till now.
I personally prefer vector because they offer a level of abstraction to the coder as in the programmer can use the template of vector without caring about the unnecessary details about it’s working.
2 Likes
I have another question, what if the problem is not about graph. What about problem SGARDEN of JULY14 long contest?
Here we can use array of structures. What advantage can we get using array of vectors?
Thanks @abcdexter24 ,previously I used only arrays, but from now on I will try to use vectors wherever possible.
