Неудаляющий аллокатор

Программы на C могут выделять память под объекты двумя способами: на стэке (stack allocation) и на куче (heap allocation).

В первом случае поддеживается указатель на конец памяти, который при создании объекта увеличивается на нужное число байт, а при удалении — уменьшается. Как в стэке. Этот способ используется, например, когда вы создаете временные переменные внутри функции или тела цикла — когда они исчезают из области видимости, компилятор автоматически генерируют инстрикции для их удаления.

Во втором подходе программа вежливо просит операционную систему выделить сколько-то байт памяти как ей удобно и вернуть на них указатель, а также гарантировать, что другие процессы не будут иметь к ней никакого доступа (хотя компьютер — вещь сложная, и это не всегда получается). В этом случае программист сам должен думать об удалении объектов, когда они становятся не нужны. Для создания объектов таким образом нужно вызвать оператор new, а при удалении вызывать оператор delete.

Низкоуровневая работа с памятью — это, пожалуй, основная причина, почему люди любят и ненавидят C и C++. Если не удалять объекты, выделенные на куче, то возникает утечка памяти, но в условиях олимпиады это нам не важно — за несколько секунд времени редко удается выделить больше памяти, чем доступно.

Пожертвовав «правильным» освобождением памяти, можно значительно ускорить — иногда в полтора-два раза — скорость работы работы структур данных, которые используют delete (в частности, большинство контейнеров STL).

Для этого можно глобально переопределить new и delete:

const int max_memory = 1e8;

int pos_memory = 0;
char memory[max_memory];

void* operator new(size_t n) {
    char *res = memory + pos_memory;
    pos_memory += n;
    assert(pos_memory <= max_memory);
    return (void*) res;
}
void operator delete(void *){}

Оператор new принимает количество байт памяти, которые требуется выделить, и возвращает указатель на выделенную память — у нас он возвращает и увеличивает конец «стэка».

Оператор delete принимает указатель на начало памяти и освобождает её. В нашем случае, он просто не делает ничего.