If you've been doing competitive programming for a while, you're probably aware by now that dynamically allocating memory (i.e. using `new` or `malloc`) is pretty expensive in terms of computation time (both because of slow allocation and potential cache misses).↵
↵
What many people do to avoid dynamically allocated memory is implement a "memory cache": a pre-allocated array of elements, from which you can fetch elements at will. In code, this might look like this:↵
↵
↵
~~~~~↵
elem elemCache[MAX_NUMBER_OF_ELEMENTS];↵
int nxtElemCache = 0;↵
↵
elem *fetchElement() {↵
return &elemCache[nxtElemCache++];↵
}↵
~~~~~↵
↵
And instead of using the `new` operator, you just use the `fetchElement` function (you can also override the `new` operator itself, but it's slightly less readable for the purposes of this thread, so we'll leave it at that).↵
↵
The problem arises when you do not know what `MAX_NUMBER_OF_ELEMENTS` is. For example, let's say that you are implementing a data structure (maybe a persistent segment tree) which you are not very familiar with. You can usually approximate this number (let's take the segment tree example: you know that at every step you are creating at most two nodes and you are doing O(log N) steps so maybe 2 * N * log N is a safe upper bound; maybe increase the factor for safety), but maybe since you are not familiar with the structure you don't know of a good upper bound. Maybe you just don't want to waste time thinking about it or maybe you are simply afraid that your calculations are wrong and don't want to take the chance and have wasted submission.↵
↵
An elegant solution is to use std::deque. An example of how this would work in code:↵
↵
↵
~~~~~↵
deque<elem> elemCache;↵
↵
elem *fetchElement() {↵
elemCache.push_back(elem());↵
return &elemCache.back();↵
}↵
~~~~~↵
↵
Simply add an element to the back of your deque cache and return the address of this element.↵
↵
You might be asking what makes std::deque such a good candidate for this job. Well, there are quite a few reasons:↵
↵
- pushing to the end of std::deque takes amortized constant time (similar to std::vector)↵
↵
- unlike something like std::vector, references to elements of a deque are _never_ invalidated (when pushing at the front or back of the structure); this is guaranteed by the standard; this means that once you have allocated an element, it will remain allocated at that address (which is the desired behavior: you don't want the pointers to be invalidated);↵
↵
- unlike something like std::list, it uses very little memory overhead;↵
↵
- cache efficiency is maintained (again, unlike something like std::list) since internally internally std:deque holds contiguous chunks of memory.↵
↵
Here are some submissions for last contest's problem F using persistent segment tree:↵
↵
- using new operator [submission:39729133]↵
- using static array [submission:39729224]↵
- using std::deque [submission:39783231]↵
↵
As a later edit, I will also add that this method also supports deletion (and later re-using the "deleted" memory), with the help of an additional stack. The idea is simple: instead of physically deleting a node, just throw it in a "recycle bin". When wanting to fetch a new node, first check if you have anything in the recycle bin instead. Implementation below:↵
↵
↵
~~~~~↵
stack<elem*> recycleBin;↵
deque<elem> elemCache;↵
↵
elem *fetchElement() {↵
if (!recycleBin.empty()) {↵
elem *temp = recycleBin.top();↵
recycleBin.pop();↵
return temp;↵
}↵
elemCache.push_back(elem());↵
return &elemCache.back();↵
}↵
↵
inline void deleteElement(elem *e) {↵
recycleBin.push(e);↵
}↵
~~~~~↵
↵
↵
What many people do to avoid dynamically allocated memory is implement a "memory cache": a pre-allocated array of elements, from which you can fetch elements at will. In code, this might look like this:↵
↵
↵
~~~~~↵
elem elemCache[MAX_NUMBER_OF_ELEMENTS];↵
int nxtElemCache = 0;↵
↵
elem *fetchElement() {↵
return &elemCache[nxtElemCache++];↵
}↵
~~~~~↵
↵
And instead of using the `new` operator, you just use the `fetchElement` function (you can also override the `new` operator itself, but it's slightly less readable for the purposes of this thread, so we'll leave it at that).↵
↵
The problem arises when you do not know what `MAX_NUMBER_OF_ELEMENTS` is. For example, let's say that you are implementing a data structure (maybe a persistent segment tree) which you are not very familiar with. You can usually approximate this number (let's take the segment tree example: you know that at every step you are creating at most two nodes and you are doing O(log N) steps so maybe 2 * N * log N is a safe upper bound; maybe increase the factor for safety), but maybe since you are not familiar with the structure you don't know of a good upper bound. Maybe you just don't want to waste time thinking about it or maybe you are simply afraid that your calculations are wrong and don't want to take the chance and have wasted submission.↵
↵
An elegant solution is to use std::deque. An example of how this would work in code:↵
↵
↵
~~~~~↵
deque<elem> elemCache;↵
↵
elem *fetchElement() {↵
elemCache.push_back(elem());↵
return &elemCache.back();↵
}↵
~~~~~↵
↵
Simply add an element to the back of your deque cache and return the address of this element.↵
↵
You might be asking what makes std::deque such a good candidate for this job. Well, there are quite a few reasons:↵
↵
- pushing to the end of std::deque takes amortized constant time (similar to std::vector)↵
↵
- unlike something like std::vector, references to elements of a deque are _never_ invalidated (when pushing at the front or back of the structure); this is guaranteed by the standard; this means that once you have allocated an element, it will remain allocated at that address (which is the desired behavior: you don't want the pointers to be invalidated);↵
↵
- unlike something like std::list, it uses very little memory overhead;↵
↵
- cache efficiency is maintained (again, unlike something like std::list) since internally internally std:deque holds contiguous chunks of memory.↵
↵
Here are some submissions for last contest's problem F using persistent segment tree:↵
↵
- using new operator [submission:39729133]↵
- using static array [submission:39729224]↵
- using std::deque [submission:39783231]↵
↵
As a later edit, I will also add that this method also supports deletion (and later re-using the "deleted" memory), with the help of an additional stack. The idea is simple: instead of physically deleting a node, just throw it in a "recycle bin". When wanting to fetch a new node, first check if you have anything in the recycle bin instead. Implementation below:↵
↵
↵
~~~~~↵
stack<elem*> recycleBin;↵
deque<elem> elemCache;↵
↵
elem *fetchElement() {↵
if (!recycleBin.empty()) {↵
elem *temp = recycleBin.top();↵
recycleBin.pop();↵
return temp;↵
}↵
elemCache.push_back(elem());↵
return &elemCache.back();↵
}↵
↵
inline void deleteElement(elem *e) {↵
recycleBin.push(e);↵
}↵
~~~~~↵
↵
