List & Memory Pool

List로 stack, queue(, priority queue)를 구현할 수 있다.

 

 

 

Memory pool (PS에 도움이 되는 technique)

 

예를 들어 Apple이라는 struct의 instance가 최대 100개까지만 필요하다면 (문제에 명시되어 있다면),

필요할 때마다 메모리를 할당했다 지우는 것보다 미리 할당해놓고 계속해서 재사용하자는 것이 memory pool의 핵심.

 

struct Apple {
  int age;
} apple[100];

int apple_idx;

void init() {
  apple_idx = 0;
}

Apple* make_apple(int age) {
  apple[apple_idx].age = age;
  return &apple[apple_idx++];
}

int main() {

  int T, apple_idx;
  cin >> T;
  
  for (int test_case = 1; test_case <= T; test_case++) {
    init();
    ...
    Apple *a1 = make_apple(1);
    Apple *a2 = make_apple(2);
    ... 
  } 
  return 0;
}