Модель аллокатора с использованием кучи и двусвязного списка

В распоряжении у менеджера памяти находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера - обрабатывать запросы приложений на выделение и освобождение памяти. Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом наш менеджер выделяет память из самого длинного свободного блока, а если таких несколько, то из них он выбирает тот, у которого номер первой ячейки - наименьший. После этого выделенный ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется. Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T - запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется. Требуется написать симуляцию менеджера памяти, удовлетворяющую приведенным критериям.
Количество ячеек 1<=N<=2^(31)-1, количество запросов 1<=m<=10^5. На вход подаются числа N и M, а затем M чисел, если число положительное - выделение памяти, отрицательное - освобождение. Для каждого запроса на выделение памяти в выход выводится одно число на отдельной строке с результатом выполнения запроса. Если память была выделена, выводится номер первой ячейки памяти в выделенном блоке, иначе выводится -1.
Для хранения свободных отрезков используется куча с итераторами на отрезки из двусвязного списка, в котором хранятся все отрезки. Приведенное решение имеет асимптотику O(m log(m)).

#include <vector>
#include <list>
#include <algorithm>
#include <cstdio>

using std::vector;
using std::list;
using std::swap;

struct Chunk {
  int start_;
  int length_;
  bool is_free_;
  int index_;

  Chunk(int start = 0, int length = 0, bool is_free = false, int index = 0):
      start_(start), length_(length), is_free_(is_free), index_(index) {}

  bool operator <(const Chunk& other) const {
    if (length_ < other.length_) {
      return true;
    }
    if (length_ == other.length_) {
      return start_ > other.start_;
    }
    return false;
  }

  bool operator ==(const Chunk& other) const {
    return start_ == other.start_ && length_ == other.length_ &&
        is_free_ == other.is_free_ && index_ == other.index_;
  }

  bool operator >(const Chunk& other) const {
    return other < *this;
  }
};

class MaxChunkHeap {
private:
  vector<list<Chunk>::iterator> array;
public:
  bool empty() const {
    return array.empty();
  }

  void Heapify(int root_index) {
    int left_son_index, right_son_index, largest_index;
    left_son_index = 2 * root_index + 1;
    right_son_index = 2 * root_index + 2;
    largest_index = root_index;
    if (left_son_index < array.size() &&
        *(array[left_son_index]) > *(array[largest_index])) {
      largest_index = left_son_index;
    }
    if (right_son_index < array.size() &&
        *(array[right_son_index]) > *(array[largest_index])) {
      largest_index = right_son_index;
    }
    if (largest_index != root_index) {
      swap(array[root_index]->index_, array[largest_index]->index_);
      swap(array[root_index], array[largest_index]);
      Heapify(largest_index);
    }
  }

  void ChangeKey(int index, list<Chunk>::iterator new_key) {
    array[index] = new_key;
    new_key->index_ = index;
    Heapify(index);
    while (index > 0 && *(array[(index - 1) / 2]) < *(array[index])) {
      swap(array[(index - 1) / 2]->index_, array[index]->index_);
      swap(array[(index - 1) / 2], array[index]);
      index = (index - 1) / 2;
    }
  }

  void Insert(list<Chunk>::iterator new_key) {
    array.push_back(new_key);
    ChangeKey(array.size() - 1, new_key);
  }

  list<Chunk>::iterator GetMax() {
    return array[0];
  }

  list<Chunk>::iterator ExtractMax() {
    list<Chunk>::iterator max_element = array[0];
    array[0] = array[array.size() - 1];
    array[0]->index_ = 0;
    array.pop_back();
    Heapify(0);
    return max_element;
  }

  void Remove(int index) {
    if (array.empty())
      return;
    array[index] = array[array.size() - 1];
    array[index]->index_ = index;
    array.pop_back();
    ChangeKey(index, array[index]);
  }

  MaxChunkHeap() {}
};

class Allocator {
private:
  MaxChunkHeap memory_heap_;
  list<Chunk> chunks_list_;
  vector<list<Chunk>::iterator> allocated_chunks_;
  int operations_counter_;
public:
  Allocator(int size_of_memory) {
    chunks_list_.push_back(Chunk(1, size_of_memory , true, 0));
    memory_heap_.Insert(chunks_list_.begin());
    operations_counter_ = 0;
  }

  int allocateMemory(int size) {
    ++operations_counter_;
    allocated_chunks_.resize(operations_counter_, chunks_list_.end());

    if (memory_heap_.empty()) {
      return -1;
    }

    if (memory_heap_.GetMax()->length_ < size) {
      return -1;
    }

    list<Chunk>::iterator free_chunk = memory_heap_.ExtractMax();
    Chunk new_chunk(free_chunk->start_, size, false);
    allocated_chunks_[operations_counter_ - 1] =
        chunks_list_.insert(free_chunk, new_chunk);

    if (free_chunk->length_ == size) {
      chunks_list_.erase(free_chunk);
      return allocated_chunks_[operations_counter_ - 1]->start_;
    }

    free_chunk->length_ -= size;
    free_chunk->start_ += size;
    memory_heap_.Insert(free_chunk);
    return allocated_chunks_[operations_counter_ - 1]->start_;
  }

  void deallocateMemory(int num) {
    ++operations_counter_;
    if (allocated_chunks_[num - 1] == chunks_list_.end()) {
      return;
    }

    allocated_chunks_[num - 1]->is_free_ = true;

    // Merge with prev
    if (allocated_chunks_[num - 1] != chunks_list_.begin()) {
      list<Chunk>::iterator prev_chunk = allocated_chunks_[num - 1];
      --prev_chunk;
      if (prev_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += prev_chunk->length_;
        allocated_chunks_[num - 1]->start_ = prev_chunk->start_;
        memory_heap_.Remove(prev_chunk->index_);
        chunks_list_.erase(prev_chunk);
      }
    }
    // Merge with next
    if (allocated_chunks_[num - 1] != --(chunks_list_.end())) {
      list<Chunk>::iterator next_chunk = allocated_chunks_[num - 1];
      ++next_chunk;
      if (next_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += next_chunk->length_;
        memory_heap_.Remove(next_chunk->index_);
        chunks_list_.erase(next_chunk);
      }
    }

    memory_heap_.Insert(allocated_chunks_[num - 1]);
  }
};


void readInputToVector(vector<int> *vec) {
  int number_of_numbers, cur_number;
  scanf("%d", &number_of_numbers);
  for (int i = 0; i < number_of_numbers; ++i) {
    scanf("%d", &cur_number);
    vec->push_back(cur_number);
  }
}

void performRequests(const vector<int> &requests, vector<int> *output_vec,
                     Allocator *allocator) {
  for (vector<int>::const_iterator it = requests.begin(); it != requests.end();
  ++it) {
    if (*it > 0) {
      output_vec->push_back(allocator->allocateMemory(*it));
    }
    if (*it < 0) {
      allocator->deallocateMemory(-(*it));
    }
  }
}

void writeOutput(const vector<int> &vec) {
  for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    printf("%d\n", *it);
  }
}

int main() {
  int size_of_memory;
  scanf("%d", &size_of_memory);
  Allocator allocator(size_of_memory);
  vector<int> requests;
  readInputToVector(&requests);
  vector<int> output_vec;
  performRequests(requests, &output_vec, &allocator);
  writeOutput(output_vec);
  return 0;
}