CODEWITHSUNDEEP
c++vectorstl
bhanu
bhanu

Reputation: 89

Improvement over vector assignment and clear

Many time I deal with this type of code:

vector<int>prev,cur;

for(i=1;i<n;i++){       

    //do some operation on cur based on prev vector

    prev = cur;

    cur.clear();
}

Is there any scope of time complexity improvement? As time complexity of clear is linear in terms of its element (container destructor is called), is there any way to do this operation on O(1) or less time by any other method? Should I use pointer to vectors then change pointer for doing

prev = cur

Upvotes: 2

Views: 145

Answers (2)

David Haim
David Haim

Reputation: 26476

My suggestion is to use move semantics over swap:

for(i=1;i<n;i++){       

    //do some operation on cur based on prev vector

    prev = std::move(cur);

    cur.clear();
}

Upvotes: 0

Christophe
Christophe

Reputation: 73376

1) Your current way of doing it requires a copy of elements (which is O(n)) and the clearing of cur (in principle O(n) calls to destructor, but this shouldn't be a performance issue for basic types such as the int in your example).

2) The swap() recomended by bhzad.nouri in his comment exchanges the elements of the two vectors. From the point of view of performance, you can imagine this somewhat like an exchange of pointers. Regardless how it is really implemented, the swap is done in constant time. After the swap, you nevertheless have data in cur, so you might need to clear() it.

3) pointers to vectors would look ugly. The vector swap comes to the same result in terms of performance and is so much more elegant !

Upvotes: 1

Related Questions