std::vector<bool>를 PS에서는 어떻게 대해야할까

들어가며...

알고리즘 문제를 풀다 보면 `std::vector<bool>` 또는 `std::array<bool, N>` 같은 코드를 사용하곤 합니다.

우리에게는 `bool [N]`이 너무나도 익숙하고, 위와 같이 작성하더라도 별 문제가 발생하지 않기 때문입니다.

 

하지만, 실무적이고 객체지향적인 코드 작성과는 조금 멀리 떨어져있는 PS를 하면서도

`std::vector<bool>`은 사용을 지양하세요~

같은 문구를 종종 보곤합니다.

 

항상 그 이유가 궁금했지만, 그때마다

1. 관련 내용 조금 찾아보기
2. 어려운 내용에 질겁 → 결론 위주로 탐색
3. '아하 그래서 `std::bitset` 쓰라는 거구나?'
4. 막상 `std::bitset` 써보니 불편함
5. 다시 `std::vector<bool>`로 회귀

를 몇 번이고 반복하고 나니 이젠 잘 모르겠더라도 한 번은 정리를 해놔야 속이 시원할 것 같았습니다.

 

참고로 조사해 보면 이 논쟁 아닌 논쟁은 10여 년 전, 오래전부터 계속해서 많은 사람 사이에서 갑론을박이 오갔던 주제인 것 같습니다. 마땅히 '이거다!'라는 정답은 없어 보입니다. 사람마다 어떤 상황에서 이런 고민을 했는지는 천차만별이고, `bool` 타입 배열에 단일 bit에 대한 read만 할 건지, 아니면 modify도 할건지, 대량의 bit에 대한 batch 연산이 많은지 또는 적은 지 등 워크로드에 따라 얼마든지 개인의 의견은 달라질 수 있기 때문입니다. 따라서, 정답을 찾는다기 보다는 간단하게나마 호기심을 충족시키자는 목적으로 가볍게 읽어봅시다.

---

 

 

 

std::vector<bool>이란?

https://en.cppreference.com/w/cpp/container/vector_bool

 

우선 레퍼런스 문서만 봐도 `std::vector<bool>`에 대한 설명이 간략하게 잘 나와있습니다.

형광펜 친 곳 위주로 요약하면,

• `std::vector<bool>`은 공간 효율성과 bit 단위로 접근을 목표로 하는 `std::vector<T>`의 특수화 버전입니다.
• `std::vector<T>`와 달리 메모리 연속성과 동시성을 보장하지 않습니다.
• 특정 bit에 접근하기 위해 `std::vector<bool>::reference` 프록시 객체를 값으로 반환합니다.
• STL 컨테이너 또는 순차컨테이너로서의 모든 필요조건을 만족하지 않습니다. `std::search()`와 같은 함수에 사용한다면, `LegacyForwardIterators`와 관련된 문제로 컴파일타임 또는 런타임 에러가 발생합니다.

왜 쓰지 말라는 걸까?

많은 곳에서 공통적으로 언급된 `std::vector<bool>`의 단점은 일단 느리다는 겁니다. [1][2][3][4]

 

단일 비트에 접근하기 위해서 따로 객체를 이용해서 접근한 뒤 비트연산하고 다시 프록시 객체를 값 반환하기 때문에 느릴 수밖에 없습니다. 1 WORD 단위로 읽는 컴퓨터의 특징상 Byte 단위로 읽어 들이는 것이 훨씬 빠르기 때문에, 단일 bit에 반복해서 접근하려고 한다면, `std::vector<int>`나 `std::vector<uint8_t>`에 비해 상대적으로 더욱 느려질 수밖에 없습니다.

 

벤치마킹 1 - 특정 비트 (단일 원소)에 대한 반복 접근 (위 - 단순 true 값 반영, 아래 - 모듈러 연산)

 

`std::vector<bool>` 입장에서의 최악의 상황입니다.
단순히 모든 인덱스에 접근해 초기화하는 간단한 for문일뿐인데 많은 차이가 발생합니다. (13배~31배)

 

벤치마킹 2 - 에라토스테네스의 체

단일 bit 접근이 조금 덜 하다면, 그나마 형편이 낫습니다.

위 코드의 경우, 가장 처음에 벡터를 초기화할 때 `primes(N, true)` 대량으로 바이트를 읽기 때문에 차이는 없습니다.

그렇지만, 쉽지 않아

그러면, `std::vector<uint8_t>`를 쓰면 될까요? 만능은 아닙니다.

주의 1. 출력

우선, `std::vector<uint8_t>`를 출력하려고 할 때는 주의해야 합니다.

`std::cout` 의 `operator <<` 연산자의 경우에는 `uint8_t`를 `unsigned char`로, 정숫값이 아닌, 문자로 인식합니다. [5]

 

따라서 올바르게 정숫값으로 출력하고자 할 때는 `(unsigned)arr[i]` 또는 `(int)arr[i]` 또는 `static_cast<int>(arr[i])` 또는 `+arr[i]` (`+`부호 기호가 자동으로 `int`형으로 변환해 줌)을 사용해서 캐스팅해 준 뒤 출력해야 합니다.

주의 2. 뺄셈

`unsigned` 타입을 사용할 때는 혹시 코드에 뺄셈이 들어가 있지 않은지 주의합시다.

뺄셈을 하다 보면 자기도 눈치채지 못한 세에 0 미만으로 떨어져 언더플로가 날 수도 있습니다.

 

대표적인 예제로 떠오르는 건 2468번 안전영역이 있습니다.

(아마 그럴 일은 없겠지만) 각 칸에 들어갈 수 있는 수가 1 이상 100 이하의 정수라고 해서 2차원 배열을 `uint8_t` 같은 걸로 설정하면 안 됩니다. 안전영역을 판가름하기 위해 현재 물의 높이보다 큰지 뺄셈을 통해 판단하기 때문에 언더플로가 날 가능성이 큽니다. 100% 틀립니다.

주의 3. 반드시 빠르지 않음

앞서 본 벤치마킹 결과에서도 어떤 타입의 연산 위주냐에 따라 `bool` 타입보다 훨씬 빠를 수도, 거의 차이가 없을 수도 있고, 오히려 느릴 수도 있습니다. 치트키라고 생각하기보다는 어떤 때에 사용하면 효과적일지 알고 사용하는 게 좋겠습니다.

정적배열일 때는 어떤걸 쓸까?

아무래도 PS에서는 배열의 크기를 알고있거나, 모르더라도 문제 범위의 최대크기로 잡는 경우가 많아 정적배열을 쓰곤 합니다.

정적배열이 될 수 있는 3가지 후보 ① `bool [N]` 배열, ② `std::array<bool, N>` ③ `std::bitset<N>` 중 어떤 걸 사용하면 좋을까요?

 

우선 ②는 앞서 살펴본 `std::vector<bool>`과 동일한 단점을 가지고 있습니다. 프록시 객체를 값 반환하고 느리죠. 따라서 ①과 ③ 사이에서 고민해보면 될 것 같습니다.

std::bitset<N> vs bool [N] - 1. 단순 접근 및 초기화

std::bitset<N> vs bool [N] - 2. 에라토스테네스 체

 

벤치마크 결과만 보면 `bool []` 배열이 훨씬 빠른것을 확인할 수 있습니다.

• 특정 단일 bit에 대한 read/write은 일반 `bool []` 배열이 훨씬 나은 성능을 보입니다.
• 그러나 한 번에 대량의 bit를 바꾸는 연산의 경우에는`std::bitset<N>`이 훨씬 빠릅니다.
  • `std::bitset<N>`의 `.set()` 멤버함수를 이용해서 `true`로 초기화 할 때는, 벤치마크 1의 결과가 완전 뒤집힙니다.
  • 벤치마크 2에서는 `.set()` 멤버함수 덕분에 시간을 단축했지만, 단축된 시간보다 더 많은 시간을 단일 bit에 대한 read/write에 사용하는 바람에 일반 `bool []` 배열보다 느려졌습니다.

속도를 희생한 대신 `std::bitset<N>`은 메모리 감축에 아주 탁월합니다.
어쩔 수 없이 단일 bit를 저장하기 위해 1-byte를 할애하는 다른 배열들과는 다르게, bitset은 정말로 1-byte에 8개의 bit를 꽉 채워서 저장합니다.

---

결론적으로 뭘 쓸까?

크기가 정적으로 주어졌다면 (N을 알고 있다면) `bool [N]`을 쓰는 게 맞습니다.
동적배열을 사용해야 한다면 `vector<uint8_t>`를 쓰되, 상단의 주의할 점을 염두하면서 사용합시다.
메모리가 중요하다면 `std::bitset<N>`을 사용하고, 정 도저히 방법이 없다면 `std::vector<bool>` 또는 boost 라이브러리의 dynamic_bitset을 고려합시다.