rgnerdplayer's blog

Problem with data structures that are (possibly) implemented by pointers
By rgnerdplayer, 4 years ago, In English

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?

  • Vote: I like it
  • +29
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +87 Vote: I do not like it

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)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    SecondThread I thought not deleting pointers would lead to memory leakage? Didn't know programs would automatically clean them up.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I thought not deleting pointers would lead to memory leakage?

      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.

      Didn't know programs would automatically clean them up.

      They do, just not when programming in C++.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 call delete). 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 usual new or malloc for most CP-related usecases (credits to people in the AC Discord server who told me how to actually this allocator).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry to ask, do you have a submission where this allocator is actually used? Somehow I couldn't make it work.

    → Reply