Creating vectors in Recursive Function C++

Question

I have a recursive function where I have an vector of object being passed. I need to traverse this vector and take out elements based on some condition. Which is a more efficient way of doing this -

a) Declaring a temporary vector in the body of the function

function(vector<obj> &arr,int l,int r){
some other stuff
vector<obj> temp;
adding elements based on some condition and operating
}

b) Declaring something like a global temporary vector (or passing it through the functions by reference), and then clearing it inside the function body and performing the required steps.

function(vector<obj> &arr,vector<obj> &temp,int l,int r){
some other stuff
temp.clear();
adding elements based on some condition and operating
}

I agree it might not cause significant improvement in performance, but just want to understand which is a better practice. Do include some other methods if you think it is more efficient.

Yea, that is a viable option but I was looking for why exactly one is better compared to the other. — Ayush
– Ayush, Commented Jun 1, 2020 at 18:21
Why do you need recursion to traverse the vector? Recursion is good if it involves back-tracking, but "traversing a vector" is not something that makes use of that. — Dialecticus
– Dialecticus, Commented Jun 1, 2020 at 18:29
I think your question right now is too general and can't be answered properly. We need more information about your exact problem. — Dialecticus
– Dialecticus, Commented Jun 1, 2020 at 18:30
@Dialecticus sorry I guess I should have explained more, for example in link, a divide and conquer paradigm, the points which are at a certain distance from the mid point are added to a separate list and then operated upon, I would like to do something similar. Filtering is just a part of the recursive process. — Ayush
– Ayush, Commented Jun 1, 2020 at 18:34

Dialecticus · Accepted Answer · 2020-06-01 18:23:33Z

1

If vector is really big then there is a third option.

Create a new vector, set its capacity to input vector, and add stuff to it instead of removing stuff from original vector.

When you remove one item from a big vector then all other items after it must move by one place. This is a wasteful thing to do, so better avoid it.

When you set a capacity to a vector then the space for it is taken in advance, and when you add new items to it it will not gradually grow in size and the underlying code will not have to copy existing items when vector's current capacity is reached, which may happen a lot.

But there is more. You can use your input vector as output. As you iterate the vector you would copy items to places that you want removed. There would be a "moving hole" in the vector that would grow every time some items should be removed, and items would be just copied from the end of the "hole" to the beginning, moving the hole in effect. When the hole reaches the end you just cut it off from the vector, and that's your output.

edited Jun 1, 2020 at 18:23

answered Jun 1, 2020 at 18:14

Dialecticus

16.8k7 gold badges47 silver badges108 bronze badges

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

1 Comment

Ayush Over a year ago

Wouldn't it actually be a bad idea since the storage space used would be so much more than actually required. Also, say I used the clear() function, in that case would this still be recommended?

Collectives™ on Stack Overflow

Creating vectors in Recursive Function C++

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related