Hi , I was solving this problem https://www.codechef.com/problems/PRMQ and used Persistent Segment Tree for this.
However, one of my implementation using vector to store versions was giving error :
The implementation is:
Vector based version tracking
Another error free implementation was :
Pointer Array based version tracking
Error :
Error last lines
Full Error Data : https://pastebin.com/S8QWp0bF
Full No-Error Code : https://www.codechef.com/viewsolution/47320824
Full Error Code : https://www.codechef.com/viewsolution/47320876
Build Flags : g++ -std=c++17 -Wshadow -Wextra -Wall -DZoro ${file} -ggdb3 -fsanitize=address,undefined -D_GLIBCXX_DEBUG -D_GLIBCXX_ASSERTIONS
Although it didn't affect the final verdict of the solution, I want to know if it's something serious I should be concerned about for future contests?
Error reason found. The error was showing because I wasn't explicitly deleting the allocated memory.
In the array version, the array was globally declared so the allocated memory had a pointer pointing to them all the time. So, till program termination they showed no error.
For some reason, vector didn't behave in same way even when declared globally. But if we manually "delete" the pointers of the tree stored in vector and other variables, the error vanishes.
Does anyone know why global array allocation didn't leak the memory till the end of runtime but vector did? Does vector get cleared before program ends? Any C++ experts?
Even for a global vector the destructor gets called at some point when the program is exiting. An array isn't an object and a global one just stays in memory until the end.
You allocate the nodes with "new" but never "delete" them, so that can lead to memory leaks. (A memory leak is when you lose all pointers to some memory you allocated but didn't free yet.) In the version where you got the address sanitizer error, you store the pointers in a vector, which gets destroyed when the Onigiri() function is done. So after that the pointers aren't accessible anymore, meaning the memory is leaked (It's an "indirect leak" because the vector's memory was still holding the pointers when it itself got freed. A "direct" leak is when the pointers to the leaked memory directly get overwritten/go out of scope.). In the non-error version you write the pointers to the nodes into a global array, meaning they stay accessible until the program exits. That's by definition not a memory leak.
If you're only calling the function once I guess you don't need to care about the memory leak. If you called it for 100 test cases though, all 100 segtrees would stay in memory, meaning you might unnecessarily run into MLE. (You'd have a leak with both of your versions, since the global array one just overwrites what's there from the previous call.)
Thanks for confirming this. I was thinking that there must be no downsides to this, but that MLE threat sure looks scary.
Do you know any efficient way of de-allocating all these at once? Or do I have to go through the entire tree again and delete one by one?
I don't think there's an alternative to deleting them one by one. Unless you use std::unique_ptr which does it automatically but has some performance overhead (small enough that some people use it even in competitive programming).
Instead of using
newto create nodes, you can push node objects onto a deque and return a pointer to the location in the deque. When the persistent segtree goes out of scope, the objects on the deque will be cleared as well. One implementation where I use this can be found here. The code could be written better, but the general idea should work.Any special reason to use deque instead of vector? That code only has push_back() and back() calls. So, vector should also do the job, right?
If you use pointers to items of vector then after push_back vector can be reallocated, so pointers to items would be invalid. Deque on the other hand never reallocates items, so you can use pointers to deque items there.
Upd: You can use vector too but with
reserve(max_possible_items). Then push_back won't reallocate items and pointers will be remain valid.Oh, I didn't know about this reallocation thing. Thanks for sharing this. :)
Instead of using
newto create nodes, you can create a static array of nodes and maintain a counter. Let's call that arrayobject_pool. Every time you want to create a new node, you initialize all the fields ofobject_pool[counter]. After creating that node, increment the counter. You can then use the counter values to refer to nodes that you create. What's the point of using the heap in competitive programming, LOL.So, let's say you already finished processing the current test. You can reset the counter to 0, this way the old nodes of the previous test are overwritten if needed to make room for the new nodes.