For data structures such as persistent segment tree or treaps, is it OK if I submit a solution that DOESN'T delete the pointers I used? Also, is there any method more convenient than recursively delete all the trees at the end of my program?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
For data structures such as persistent segment tree or treaps, is it OK if I submit a solution that DOESN'T delete the pointers I used? Also, is there any method more convenient than recursively delete all the trees at the end of my program?
Название |
---|
As a competative programmer who basically never uses C++, I'm not really qualified to respond, but according to my friend Monogon deleting pointers is a waste of runtime; it will be cleaned up when the program ends anyway.
It's a lot like when you were little and you played with all of your toys in the living room and just left them on the floor when you went to sleep instead of putting them away. Somehow they magically get put away overnight. (Oddly enough when I no longer lived in the same house as my mother, this behavior seemed to have stopped, but I think it's just a bug in the current runtime that should hopefully be patched in the next version)
Not really true if you are working with very limited memory. There are some problems, especially with more test cases per file, where you have to delete pointers. A good alternative, and faster by about two times, is using large arrays and having "custom" pointers. This is faster and uses less memory as an integer occupies 4 bytes and a pointer 8.
SecondThread I thought not deleting pointers would lead to memory leakage? Didn't know programs would automatically clean them up.
It does. It just doesn't usually matter in CP — your code runs only for a short time and often if you use a lot of memory, you will run out of time before you run out of memory.
They do, just not when programming in C++.
A nice way to use pointers without worrying about freeing memory is to just pre-allocate a large global pool of memory beforehand, and allocate memory from that pool.
This allocator from kactl is a good example of an allocator that does precisely this (to use it, just put this before any code you write, and any instance of
new
in your code should use this allocator instead, and you never need to calldelete
). Note that STL containers still allocate memory from the heap (to fix this, there is an STL version of the allocator in the same repo). It also tends to be much faster than the usualnew
ormalloc
for most CP-related usecases (credits to people in the AC Discord server who told me how to actually this allocator).Sorry to ask, do you have a submission where this allocator is actually used? Somehow I couldn't make it work.