C++ 배열 탐구와 배열로 이루어진 queue 만들기

하반기 채용 준비를 위한 여러가지 (임베디드/펌웨어 공부, OS/기조직 복습, STM32 보드 갖고 놀기 등등)을 하고 있는데... 그 중 하나가 코테 대비를 위한 알고리즘 풀이다.

하이닉스가 C++만 허용한다고 하고, C/C++을 안 다뤄본 것도 아니고 (오히려 가장 많이 다뤘다), 펌웨어 분야에 일단 집중하기로 결정했기에 C++로 백준을 풀고 있었다.

그 와중에 예전에 분명 다뤘던 내용 같은데 기록한 것이 없고, 오늘 또 마주하게 되어서 글로 남기게 되었다.

C++ 배열

C++에는 다양한 배열이 존재한다. std::vector도 메모리 상 연속적인 것을 보장하기 때문에 배열이라고 볼 수 있지만... 이번에 중점적으로 다룰 배열은 바로 static array와 std::array<T, N>이다.

이 둘의 공통점은

• new를 안 쓰고 스택에 저장하는 것이 가능하다. (참고로 std::vector은 new없이 선언해도 실제 value를 담는 container이 힙에 저장된다. 이 경우 vector 객체 자체는 스택에 저장된다.)

• 메모리 상에 연속적으로 저장이 된다.

즉 성능적, 기능적인 면에서 둘이 가지는 차이는 없다

다만 그 외적인 부부에서 약간 차이점을 가지는데

• std::array는 *, 즉 pointer로 자동 변환이 안 된다. 예를들어 std::array<int, N>은 int *로 자동 변환이 안 된다.

• std::array는 Container 요구사항의 대부분을 만족한다. 만족하지 않는 부분은

  • default initialization이 empty하지 않음. 기본적으로 N개의 element를 포함하고 항상 그렇다.

  • swapping 시간이 linear. (다만 이건 C++11보다 상위 버전에서만 강요되는 조건이라는 것도 참고.)

Container은 named requirement이다. named requirement 무슨 type이나 class같은 것은 아니고 특정 요구사항을 만족하는 것들은 그렇게 부르겠다고 명시하는 cpp 개념이다.

여기서 중요한건 std::array가 Container로 취급된다는 것이다. 보통 Container들은

• 자기 크기가 얼마인지 알고 있다.

• assignment/random access iterator 등을 지원

등의 특징을 가지고 있다. 한마디로 C++에 친화적인 형태로 만들어졌다는 것이다.

하지만 static array는 Container이 아니고 그냥 순수 C 배열이기 때문에, C++의 몇몇 STL 제공 class들이랑 제대로 호환이 안되고, 오류를 일으킬 수 있다.

queue

그리고 이 차이가 두드러지는 경우 중 하나가 queue element를 배열로 구성할 때 나타난다.

이번 글을 쓰게 된 사례를 봐보도록 하자. 백준 문제에서 BFS를 구현할 필요가 생겨서 queue를 만들었는데, 2개의 요소를 가진 element를 queue에 저장하려고 배열을 저장하기로 마음 먹었다.

참고로, 2개의 요소로 이루어진 element를 queue에 저장할거면 그냥 std::pair<T1, T2>을 쓰는게 편하고 결국엔 이렇게 풀었는데 일단은 넘어가자 (...)

static array로 만들어본다고 치자. 그러면 다음과 같이 해야 한다.

queue<int*> q;
...
q.push(new int[2]{S, 0});

힙에 배열이 저장되는 것이 싫으면 좀 더 번거로워진다.

queue<int*> q;
...
int elem[2] = { S, 0 };
q.push(elem);

참고로 밑은 안된다.

queue<int[]> q;
...
q.push(new int[2]{S, 0});

왜냐하면 new로 반환하는 type이 int *이어서 int[]로 취급이 안되기 때문 (...) 벌써부터 불편함이 스물스물 올라온다.

그리고 밑도 안된다.

queue<int[]> q; //queue<int*>도 마찬가지.
...
q.push({S, 0});

C 배열 초기화시 {}을 사용하는 문법이 있는것을 알텐데 저렇게 단독으로 사용하는 것은 또 안된다.

밑의 이거 2개도 안된다.

queue<int[]> q;
...
int elem[2] = { S, 0 };
q.push(elem);

queue<int[2]> q;
...
int elem[2] = { S, 0 };
q.push(elem);

맨 위는 int[]랑 int[2]가 다르다면서 오류를 내뱉는다 (...)
그 다음은 실행은 되는데, 오류가 나온다. 오류 메세지 자체는 희한하다 : 배열은 괄호로 묶인 이니셜라이저로 초기화할 수 없습니다.

이처럼 C-style array를 C++의 객체에다가 집어넣으려고 하는 과정, 혹은 상호작용하는 과정은 매우 골치아프다. C++가 [] 형태의 static array를 직접 다루는 것을 전혀 고려하지 않고, 사용을 하더라도 int *의 형태로 취급을 하기 때문이다.

이 때문에 위의 되는/되지 않는 코드의 케이스를 보면 되는 코드는 전부 int *를 기준으로 queue를 만든 것이고, 되지 않는 케이스는 (int *인 경우도 있지만) int []를 가지고 queue를 만들려고 할 때 생기고 있다.

그럼 int *로 만들면 되지 않냐고 할 수 있지만... 분명 저장하려는 것은 int 배열인데... queue<int*> 선언만 보면 int 배열인지 int 가리키는 포인터인지 가늠이 안된다. 실행이야 되겠지만 별로 좋지 않은 상황. 게다가 힙을 안 쓰려고 하면 코드가 많이 너저분해진다.

하지만 std::array를 사용하면 많이 편해진다. (#include <array>를 꼭 포함해야 한다는 점 유의)

queue<array<int, 2>> q;
...
q.push({S, 0});

일단 push 부분이 많이 짧아졌다. std::array는 {}를 기반으로 정의하는 것을 지원해주기 때문. 저 배열이 스택에 저장되는 것은 덤.

게다가 queue가 배열을 저장한다는 것도 선언 만으로 확인이 가능하다.

뭣보다 위 세가지 장점을 제쳐도, C++ STL에서 전달받은 element가 배열임을 인지하는데 도움이 되니 가급적 배열은, std::array를 사용하도록 하자.

언제나 유용하다고 하긴 애매한게, static array랑 std::array가 생성하는 어셈블리가 다른 시스템이 있다고 한다. 다만 알고리즘 문제 풀면서 거기까지 도달할 일은 별로 없으니까... 크게 문제는 없다고 생각한다.

그리고 힙에 element 저장이 되는 것이 상관 없으면 vector을 써도 괜찮다. 특히 동적 배열을 저장해야 하는 경우 이거 말고 선택 사항이 딱히 없다.