[C++] vector<bool> 보기를 돌같이 해라

서론

 현재 C++에 대한 깊이가 부족하다고 생각해 강제로 깊게 만들어주는 Effective 시리즈의 STL을 읽고 있습니다. 이 이펙티브 시리즈는 나온 지 좀 오래된 시리즈라 현재 C++과는 맞지 않는 이야기들이 몇 있지만 눈여겨볼만한, 아직 해당되는 이야기들이 대부분입니다.

 

 이 중 현재 항목들을 1/3 정도 보면서 2번째로 흥미로웠던 부분인 vector<bool>에 관련한 이야기입니다. 현재 포스트의 제목도 Effective STL에서 가져온 만큼 여기서 다뤘던 이야기들을 잠깐 기록해보려고 합니다.

 

 

 

vector<bool>은 일반 다른 컨테이너와는 사뭇 다르다

#include <iostream>
#include <vector>
using namespace std;

int main(){

    vector<bool> v;

    v.push_back(true);
    v.push_back(false);

    v[0] = false;

    for(int i = 0; i < 2; i++){
        cout << v[i] << " ";
    }
}

 위 코드는 정말 잘 동작합니다. 생각하는 그대로의 vector대로 움직이고 operator []를 통해서 출력도 잘 되는 상태입니다. 그런데 여기서 bool 포인터에 요소 한 개를 담아보겠습니다.

bool* bp = &v[0];

 이 코드를 아래 삽입하면 오류가 납니다.

 나오는 오류를 보아하니 &v[0]의 타입은 std::_Bit_reference로 잡히는 것 같습니다. 이런 타입 확실히 기본 타입은 아닌듯한 느낌이 들게 되는 단어입니다.

 

일단 결론을 이야기하면 vector<bool>은 한 자리에 8비트를 저장하게 됩니다. 다른 int 등의 타입들처럼 메모리의 한 자리에 단순히 bool 하나만 두기에는 공간이 많이 부족하게 됩니다. 때문에 한 공간에 8비트를 저장하게 되는 '비트필드'를 저장하는 것이죠.

이 8비트에 대해서는 Effective STL의 말을 가져왔으나 정확한 수치인지는 잘 모르겠습니다.

 

 그렇다면 공간적 성능을 위해서 bool 대신 비트필드를 넣었다 부분은 이해가 되는데 그러면 어떻게 operator []가 동작하고 있을까요. 이건 바로 프록시 패턴을 적용해 operator []가 가능하게 했기 때문이죠. 프록시 패턴을 간단하게 이야기하면 인터페이스 역할을 해주는 패턴으로 내부에 있는 요소와 상호작용 할 수 있게 해주는 디자인 패턴입니다. 이 프록시 패턴으로 operator [] 를 만들어 내부 요소를 반환하게 해주는 것이죠. 대략 아래 코드 같은 느낌입니다.

template<typename Allocator>
vector<bool, Allocator>
{
public :
	class reference{...}; // 각 비트에 대한 참조자 대신 쓰일 프록시를 만드는 클래스

	reference operator[] (size_type n); // operator[]는 프록시를 반환	
};

 여기서 operator []가 반환하는 타입이 bool* 타입이 아니기에 위에서 요소를 포인터로 받는데 문제가 생기는 것이죠. 때문에 이 operator [] 연산이 프록시 패턴으로 구현되어 있다는 점에서 vector<bool>은 다른 컨테이너와는 다른 길을 걷고 있다는걸 알 수 있습니다. 이제 기존 정렬이라던가 search 등의 알고리즘 사용시 오류가 발생할 수 있게 됩니다!

 

 

 

 

vector<bool> 을 대체하는 것들은

 'Effective STL'에서도 소개되었고 여러 자료들에서도 추천하고 있는 방법입니다. 바로 std::bitset과 deque<bool> 입니다. bitset의 경우 제공되는 멤버 함수들이 많으며 deque<bool>은 자리는 많이 잡아먹지만 실제  bool을 저장하도록 작동하고 있다고 합니다. 그러니 컴파일 타임에 크기를 알 수 있다면 bitset을 알 수 없다면 deque<bool>을 사용하는 걸로 대체해야 합니다. 

 

 

 

Effective STL 외 참고자료

Why isn't vector<bool> a STL container?

vector<bool> 클래스

 

std::vector<bool> - cppreference.com