Hello guys, today I will do a tutorial on how to clean a vector, structure or something else in c++ really fast.
Naive Approach
-A newbie may see this problem and try to solve it in linear time, for that we could just use the resources the C++ libraries offer us. In this particular case, the function clear()
would do it. However, it is an $$$ O(length) $$$ function and considering N can be very big, until $$$ 10^9 $$$, for an example, it cannot solve every problem of this type.
Smart Approach
-A more experienced coder, like Errichto, will see this problem and immediately think about the smart approach. This approch consists of doing the following:
Boom!, the complexity fell from ~$$$O(N)$$$ to ~$$$O(1)$$$. On my machine clearing vector of size $$$10⁸$$$ with the dumb approach took $$$0,789s$$$ and with the smart approach it took $$$0,438s$$$. Thus, in the next time you need to clear a lot of vectors, use the smart approach, your code will be much faster.
P.S: this idea can easily be expanded for other structures, just substitute the 'vector' in the code for the structure you want and make the necessary changes to it.
defnotmee, you need to see this amazing trick
Little do you know defnotmee and pikamonstruosa are the same person
This is not true
Amazing tricks! No idea why this blog is downvoted ??? T_T ???
This works because we don't actually free the underlying memory, we just exchange the memory handled by the vector we use with a new (empty) vector. And when our program terminates, the time the OS take to free the memory isn't counted toward our execution time.
Most of the time this is fine, we will have enough memory for the whole test case anyway, however most of the time we don't need to get the extra time either. Use at your own risk.
Right?? Well, this is a silly trick and has little to no use, but it acually works lol.
I might not be taking your sarcasm, but if it's not the case, I argue that the trick is absolutely useless.
The memory should be freed anyways. In case you are using this
aux
vector trick, it will be freed at the time theaux
's destructor is called. This is counted toward the execution time, so you save time in one place to spend it in another.Moreover, the constant factors for memory use are so much weird, that I wouldn't argue anything without testing. The blog author states, that swapping vector of size 1e8 halves (not divides by 1e8, halves!) the execution time. I don't know, what code did he use for testing, but this one
UPD: the following part is changed, the previous version of the code worked not as intended.
shows that the printed times are basically the same (for different
N
andK
combinations) for(1)
being commented out versus for(2)
being commented out. (The times printed withcout
should not count time foraux
's destructor to be called, you can ignore them — I actually used CF's messages from customtest)Therefore, I would be really surprised, if anyone could show a real example, where one benefits from using the trick — I think that this is the case where the most straightforward way is the fatest.
I did a bit of trolling.
But to be fair, I'm not so sure about this topic, because it depend on lots of things. Theoretically, you're totally right, there's no different where you free the memory.
In practice, it can be argued that when the vector is freed by the dtor (after main), the system free all the memory at once, so it can do it more efficiently.
But it can also be argued that if you are actually going to do things with the vector (i.e. emplace/push back), then .clear() is superior because you don't pay for the vector growth unless the max size actually increase.
So you create a useless
std::vector<std::vector<int>>
to save all thestd::vector
that you ever used?Dont you think it is silly lol
By the way,
clear()
is O(1), but not O(len) I remember.Lol, yes it is a little silly, but
clear()
is linear in size : reference