게임 프로그래머

vector<bool>은 STL 컨테이너가 아님

STL 컨테이너의 자격을 갖추려면 operator[]가 지원돼야 하므로 아래 코드가 컴파일 돼야 하지만 vector<bool>은 컴파일 되지 않음

T* p = &c[0];
bool* p = &c[0];

vector<bool> 구조

bool이 들어 있지 않고 공간을 줄이기 위해 비트 필드를 써서 bool을 저장하고 있는 것처럼 흉내내어 한 개의 비트에 한 개의 bool 값을 저장

std::vector<bool>::reference

비트에 대한 참조자처럼 동작하는 프록시 객체

비트 필드를 조작할 수 있도록 설계되어 있으며, bool 값을 읽고 쓸 수 있도록 해줌

template <typename Allocator>
class vector<bool, Allocator>
{
public:
    class reference { ... };
    
    reference operator[](size_type n);
};

복사 및 할당

복사 및 할당이 가능하며, operator=를 통해 값을 할당할 수 있음

할당 연산자는 실제로는 해당 비트를 설정하거나 변경하는 함수

암시적 변환

bool로 암시적으로 변환될 수 있음, 즉, 마치 bool처럼 사용할 수 있지만, 이는 내부적으로 프록시 객체를 통해 해당 비트 값을 가져오는 과정

특징

bool을 하나의 비트로 나타내어 한 바이트로 8개의 bool을 담을 수 있게 구현함

bool은 포인터와 참조자를 만들 수 있지만 비트 필드의 각 비트에 대한 포인터와 참조자를 만들 수 없음

표준안에 속해 있고, STL 컨테이너 요구사항을 거의 만족하지만 템플릿을 설계할 때 제대로 동작하지 않을 수 있음

메모리 측면에서 최적화되었지만, 비트 단위로 조작하기 때문에 성능이 일반적인 std::vector보다 떨어질 수 있음

각 비트에 대한 간접적인 접근 방식을 사용하므로, 다중 스레드 환경에서는 주의 필요

대안

deque<bool>

reserve, capacity를 제외한 vector의 거의 모든 것을 할 수 있음

deque가 사용하는 내부 메모리는 연속 메모리가 아님

bitset

비트 조작에 관련된 편리한 멤버 함수 제공

STL 컨테이너는 아니지만 표준 C++ 라이브러리에 속함

STL 컨테이너와 달리 비트셋의 크기(요소의 개수)는 컴파일 타임에 고정되기 때문에 삽입하거나 제거할 수 없음

STL 컨테이너가 아니므로 반복자를 지원하지 않음

배열과 char*를 사용하는 C API를 지원할 때 vector는 &v[0], string은 s.c_str()을 사용

vector

vector가 비어있을 때 &v[0]은 있지 않는 메모리 주소 값을 전달하므로 미정의 동작을 방지하기 위해 empty 체크

&v[0] 대신 v.begin()로 반환하는 반복자는 실제로 포인터이지만 정확히는 포인터가 아닌 반복자이므로 사용하면 안됨

만약 사용한다면 &*v.begin()으로 사용해야 함

void doSomething(const int* pInts, size_t numInts);

if(v.empty() == false)
{
    doSomething(&v[0], v.size());
}

const int*가 아닌 int*로 전달하여 요소를 변경할 수 있지만 벡터의 요소 개수를 변경하려고 하면 안됨

남은 메모리 용량으로 새 요소를 만들면 내부 데이터의 일관성이 깨지고 만약 size == capacity 상태에서 요소를 추가한다면 포인터 무효화 발생

특수한 제약을 가지고 있는 벡터를 전달한다면 API에서도 제약 사항을 만족해야 함

예를 들면 벡터의 정렬 상태를 유지해야 한다면 API에서도 정렬 상태를 유지해야 함

vector를 C API를 통해 초기화

size_t fillArray(double* pArray, size_t arraySize);

vector<double> vd(maxNumDoubles);
vd.resize(fillArray(&vd[0], fd.size()));

string

string의 데이터가 연속 메모리에 저장되지 않고, 내부 문자열 값이 널 문자로 끝나지 않을 수 있으므로 vector의 방법을 사용할 수 없음

c_str()은 문자열의 길이가 0이어도 널 문자에 대한 포인터를 반환하므로 안전

c_str()은 문자열 데이터의 사본의 포인터를 반환

void doSomething(const char* pString);

doSomething(s.c_str());

string을 C API를 통해 초기화

size_t fillString(char* pArray, size_t arraySize);

vector<char> vc(maxNumChars);
size_t charsWritten = fillString(&vc[0], fc.size());
string s(vc.begin(), vc.begin() + charsWritten);

vector나 string이 아닌 다른 STL 컨테이너의 데이터를 C API로 전달

void doSomething(const int* pInts, size_t numInts);

set<int> intSet;
vector<int> v(intSet.begin(), intSet.end());
if(v.empty() == false)
{
    doSomething(&v[0], v.size());
}

string의 크기가 char*의 크기와 같을 수도, 7배까지 될수도 있음(현재 std::string은 char*의 5배)

string이 가지고 있는 데이터 멤버

size

capacity 

데이터를 가리키는 포인터

allocator의 사본이 있을 수도 있음

참조 카운팅을 사용하는 string의 경우 reference count

네 가지 string 구현 방법

string 구현 타입 A

문자열의 크기와 용량, 할당자 사본, 참조 카운트와 문자열 값을 담는 동적 할당 버퍼를 가리키는 포인터가 들어 있음

기본 할당자를 사용할 경우 string의 크기는 포인터의 네 배

string 구현 타입 B

기본 할당자를 사용한다고 가정하고 동적 할당된 메모리를 가리키는 포인터 외에는 없음

포인터가 가리키는 메모리 블록에는 문자열의 크기와 용량, 참조 카운트, 문자열 값을 가지는 동적 할당 버퍼에 대한 포인터, 멀티 스레드 환경에서 동시성 제어와 관련된 데이터 몇 개(Other)가 들어 있음

동시성 제어용 데이터는 포인터 크기의 6배

string 구현 타입 C

string 구현 타입 D(std::string과 유사)

참조 카운팅을 전혀 지원하지 않음

small string optimization : 15개의 문자를 담을 수 있는 내부 버퍼가 들어 있음

capacity가 15개를 넘으면 버퍼의 앞부분을 동적 할당 버퍼를 가리키는 포인터로 사용

아래 코드는 D 타입에서 메모리 할당이 발생하지 않고, A와 C에서는 한 번, B에서는 두 번의 할당이 일어남

string s("Perse");

결론

메모리 할당 비용이 중요하다면 B 타입은 제외

멀티스레드 환경에서는 B가 A나 C보다 더 좋을 수 있고, D는 참조 카운팅을 지원하지 않으므로 제외

string 객체가 가리키고 있는 모든 정보는 동일한 값일 때 여러 개의 string 객체들이 공유할 수 있으므로 A가 B와 C보다 공유 가능 데이터가 적음

특히 B와 C는 size, capacity까지 공유하므로 데이터를 저장하는 비용이 줄어듦

C는 객체마다 할당자를 따로 쓸 수 있도록 지원하지 않으므로 할당자까지 공유

D는 string 객체 사이에 공유가 없음

A, C, D는 짧은 문자열에 대한 메모리 할당을 하지 않음

A는 최소 할당 크기가 32 문자(널 문자 포함), C와 D는 16 문자(널 문자 비포함)

짧은 문자열을 많이 사용할 때 매우 적은 메모리만 허용되거나 참조 지역성을 고려하여 관련된 문자열을 몇 개의 페이지 별로 모아서 관리하는 경우 고려

정리

string의 문자열 값은 참조 카운팅이 될 수도, 되지 않을 수도 있음

동일한 문자열이 자주 복사될 때 참조 카운팅이 효과적

string 객체 자체의 크기는 포인터 크기의 1배 ~ 7배까지 다양

문자열을 새로 생성할 때 필요한 메모리 할당의 횟수는 0 ~ 2번

둘 이상의 string 객체가 size, capacity를 공유할 수도, 하지 않을 수도 있음

문자 버퍼를 위해 할당하는 메모리의 최소량에 대한 정책은 라이브러리마다 다르므로 현재 사용하는 string이 어떻게 구현돼있는지 알 필요가 있음

STL 컨테이너는 새로 삽입하면 메모리가 최대 크기(max_size)까지 자동으로 늘어남

vector와 string은 삽입할 때 capacity가 부족하면 realloc 과정을 거침

1. 컨테이너의 현재 capacity의 몇 배(일반적으로 2배)의 메모리 블록을 새로 할당

2. 컨테이너가 가지고 있던 메모리의 요소를 새 메모리에 이동/복사

3. 원래 메모리에 저장된 모든 객체를 소멸시킴

4. 원래 메모리를 해제

새 메모리를 할당할 때의 단점

할당, 이동/복사, 소멸, 해제의 비용이 발생

반복자, 포인터, 참조자가 무효화됨

메모리 관련 멤버 함수

size()

현재 컨테이너에 들어 있는 요소의 개수를 반환

capacity()

컨테이너에 할당된 메모리로 담을 수 있는 요소의 개수를 반환

resize(size_t n)

컨테이너가 담을 수 있는 요소의 개수를 n개로 설정

n이 현재의 size보다 작으면 컨테이너의 끝 쪽에 있는 요소는 모두 소멸됨

n이 현재의 size보다 크면 기본 생성자에 의해 생성된 빈 요소가 컨테이너의 끝에 추가됨

n이 capacity보다 크면 realloc이 일어난 후에 기본 생성 요소가 추가됨

reserve(size_t n)

n이 capacity보다 클 때 capacity를 n으로 늘림

string은 n이 현재 capacity보다 작을 경우 size와 n 중 큰 값으로 capacity를 줄이기도 하지만 요소 개수는 변하지 않음

string은 reserve를 써서 string의 남는 메모리를 자르는 방식보다 swap이 더 확실

reserve의 장점

사용할 메모리를 미리 할당하여 realloc의 횟수를 줄이고 비용을 최소화함

따라서 컨테이너가 생성된 바로 직후에 reserve를 써서 불필요한 realloc 비용을 감소해야 함

아래 코드에서 reserve를 하지 않았을 경우 1000이 약 2의 10제곱이므로 최대 10번의 realloc이 일어남

vector<int> v;
v.reserve(1000);

for(int i = 1; i <= 1000; ++i)
{
    v.push_back(i);
}

결론(불필요한 realloc 감소하는 방법)

컨테이너의 요소 수를 정확하게 혹은 대강 파악하고 있을 때 reserve를 사용

필요한 최대량을 미리 reserve하고, 나중에 남은 capacity를 자르는 방법을 사용

vector와 string은 기존 배열을 대신할 목적으로 설계됨

new 연산자를 써서 동적 배열을 만들 경우 고려해야 하는 사항

동적 배열을 메모리 해제해야 함

하나의 객체일 경우 delete, 배열일 경우 delete []를 사용하여 메모리를 해제해야 함

잘못 사용할 경우 미정의 동작

delete를 한 번만 호출해야 하고 두 번 이상 호출할 경우 미정의 동작

이미 해제된 메모리를 다시 해제하면 내부 데이터 구조가 손상될 수 있고, 첫 번째 delete 호출 후 해당 메모리 블록을 free 상태로 표시하고 재사용할 수 있기 때문

delete는 소멸자도 호출하는데, 이미 소멸된 객체의 소멸자를 다시 호출하면 해제된 메모리에 접근하게 되어 프로그램이 비정상 종료될 수 있음

vector와 string의 장점

위의 세 가지 부담을 없애줘서 요소가 추가되어 필요한 메모리를 할당하고, 소멸될 때 소멸자를 통해 요소를 모두 소멸시키고 메모리를 해제

시퀀스 컨테이너의 필수 사양을 완벽히 보유하여 STL의 알고리즘을 적용할 수 있음

begin/end/size 같은 멤버 함수를 지원하고, iterator/reserve_iterator 같은 반복자를 지원하고, value_type 등의 nested typedef 타입을 가짐

string은 참조 카운팅으로 동작하여 불필요한 메모리 할당과 문자 복사를 없애서 수행 성능 향상

하지만 멀티 스레드 환경에서는 참조 카운팅이 메모리 할당이나 복사에 절약된 시간을 동시성 제어에 걸리는 오버헤드가 더 걸리는 경우도 있음

1. 일반적으로 전처리자의 변수 값으로 참조 카운팅 기능을 끄는 방법

2. 참조 카운팅을 사용하지 않는 다른 string 혹은 부분만 구현

3. string 대신 vector<char> 고려

string은 basic_string<char>의 typedef 타입이고, wstring은 basic_string<w_char>의 typedef 타입

멀티스레드 환경에서 STL이 보장하는 사항

여러 스레드에서 쓰는 작업이 없다면 동시에 STL을 읽는 것은 안전

여러 스레드에서 각각 다른 컨테이너를 쓰는 것은 안전

컨테이너의 완벽한 스레드 안전성을 구현하기 위해 고려해야 하는 사항

멀티스레드 환경에서는 v.begin(), v.end(), find, if 구문, 반복자 접근 구문/함수 사이사이에 다른 스레드가 vector를 수정하게 되면 반복자가 무효화되어 미정의 동작 발생

각각의 구문을 STL이 락을 제공해도 구문/함수 사이에 락을 보장하지 못함

vector<int> v;
vector<int>::iterator first5(find(v.begin(), v.end(), 5));
if(first5 != v.end())
{
    *first5 = 0;
}

따라서 계속 락이 걸린채로 있어야 하지만 STL 제작자는 이런 경우를 예측해서 구현하기란 매우 어려우므로 사용자가 직접 스레드 동기화하는 것이 바람직

뮤텍스 락을 수동으로 획득하고 해제하는 것이 아닌 RAII 객체를 사용하여 자동으로 하는 것이 바람직

뮤텍스가 해제되어야 할 때 블록을 닫아 Locker를 소멸시키면 자동으로 해제되는 장점

예외가 발생하면 지역 객체는 모두 소멸되기 때문에 Locker 객체를 사용하는 도중에 예외가 발생해도 소멸자가 안전하게 호출하여 예외에도 안전

template <typename Container>
class Locker
{
public:
    Locker(const Container& container)
        : c(container)
    {
        getMutextFor(c);
    }

    ~Locker()
    {
        releaseMutextFor(c);
    }

private:
    const Container& c;
};

{
    Locker<vector<int>> lock(v);
    vector<int>::iterator first5(find(v.begin(), v.end(), 5));
    if(first5 != v.end())
    {
        *first5 = 0;
    }
}

결론

STL은 여러 스레드에서 쓰는 작업이 없다면 동시에 STL을 읽는 것은 안전하고, 여러 스레드에서 각각 다른 컨테이너를 쓰는 것은 안전하지만 동시성 제어 보장까지는 해주지 않고 사용자가 RAII 객체를 사용하여 직접 제어해야 함