효과적인 컨테이너 요리법 (2)

항목 9 : 데이터를 삭제할 때에도 조심스럽게 선택할 것이 많다

container<int> c;

어떤 표준 컨테이너 c가 있다고 하자. 여기서 어떤 값을 지우고 싶을 때, 컨테이너마다 방법이 다르다.

 

 

◾ 특정 값을 모두 삭제하는 경우

c.erase(std::remove(c.begin(), c.end(), 1963), c.end()); // vector, string, deque
c.remove(1963); // list

연속 메모리(배열 형식) 컨테이너에는 erase-remove가 효과적이다. 단, list는 그냥 멤버 함수로 있는 remove만 해주는것이 더 효율적이다.

 

c.erase(1963);

표준 연관 컨테이너라면 erase밖에 없다. 애초에 멤버 함수로 remove가 없을 뿐더러 remove 알고리즘 사용 시 컨테이너가 변형될 수 있다.

 

 

◾ 특정 조건에 부합하는 값을 삭제하는 경우

bool badValue(int x);
c.erase(std::remove_if(c.begin(), c.end(), badValue), c.end()); // vector, string, deque
c.remove_if(badValue); // list

연속 메모리 컨테이너의 경우 특정 값 대신 bool을 반환하는 함수를 넘겨주면 된다.

 

표준 연관 컨테이너의 경우 두 가지 방법이 있다.

 

AssocContainer<int> c; // 삭제되지 말아야 할 값을 담아 둘 임시 컨테이너
AssocContainer<int> goodValues; // c에서 goodValues로 옮긴다

std::remove_copy_if(c.begin(), c.end(), std::inserter(goodValues, goodValues.end()), badValue);
c.swap(goodValue);

첫 번째는 삭제하지 않을 값을 임시 연관 컨테이너에 보관해 두었다가 원래 컨테이너와 맞바꾸는 비효율적인 방법이다. 복사 비용이 꽤 비싸다.

 

for (auto i = c.begin(); i != c.end();) {
    if (badValue(*i)) c.erase(i++);
    else ++i;
}

두 번째는 반복자 순회로 요소를 하나씩 지우는 것이다.

erase가 이뤄질 때 후위형 증가로 인해 반복자가 무효화되지 않는다.

 

정리

◾ 컨테이너에서 특정한 값을 가진 객체를 모두 없애려면

연속 메모리 컨테이너 : erase-remove

list : list::remove

표준 연관 컨테이너 : container::erase

 

◾ 컨테이너에서 특정 조건을 만족하는 객체를 모두 없애려면

연속 메모리 컨테이너 : erase-remove_if

list : list::remove_if

표준 연관 컨테이너 : remove_copy_if-swap 또는 루프를 돌며 객체를 하나씩 erase

 

◾ 루프 안에서 무엇인가를 하려면(객체 삭제 포함)

표준 시퀀스 컨테이너 : erase의 반환값으로 반복자 업데이트

표준 연관 컨테이너 : erase 할때 같이 하면 됨

 

 

항목 10 : 할당자(allocator)의 일반적인 사항과 제약 사항에 대해 잘 알아두자

C++ 표준안에 의하면 디폴트 할당자와 사용자 정의 할당자는 pointer(T*)와 reference(T&) 타입을 제공해야 한다.

 

같은 타입의 모든 할당자 객체는 동등하며 항상 상등 비교를 수행하는것을 가정해야한다는 제약이 있다.

그 이유는 아래와 같다.

 

template<typename T>
class SpecialAllocator { ... };
typedef SpecialAllocator<Widget> SAW;

std::list<Widget,SAW> L1;
std::list<Widget,SAW> L2;
...
L1.splice(L1.begin(), L2);

위와 같은 코드가 있다고 해보자. L1.splice에 의해 L2의 모든 노드들이 L1으로 복사된다.

이후 L1이 소멸될 때, L1의 할당자는 L2의 할당자에 의해 생성된 노드들을 해제시켜야 한다. (L1에 복사된 L2의 노드들은 L2의 할당자에 의해 생성된것이기 때문)

하지만 둘의 할당자가 서로 동등하지 않다면 문제가 발생하게 된다.

그렇기 때문에 어떤 할당자 객체에 의해 할당된 메모리(L2)는 다른 할당자 객체(L1)로도 안전하게 해제할 수 있어야 하므로 할당자의 타입이 동등해야 한다는 제약이 반드시 필요하다.

 

타입이 동등하다는 제약이 성립되려면 이식이 가능한 할당자 객체는 상태를 가지지 않아야 한다. (=비정적 데이터 멤버를 가지지 않는다.)

상태를 가지고 있는 할당자라고 해서 컴파일이 안되는것은 아니지만 실행 시 의도적인 결과가 나오지 않을 수 있다.

 

 

할당자는 저수준 메모리 할당을 수행한다는 점에서 operator new와 같지만 인터페이스는 전혀 다르게 생겼다.

 

void* operator new(size_t bytes); // 바이트
pointer allocator<T>::allocate(size_type numObjects); // 메모리에 맞는 객체의 수

둘이 무슨 차이인가 하면 sizeof(int)가 4바이트라고 했을 때, new는 4를 넘겨야하지만 allocate는 1을 넘겨야 한다.

반환되는 타입도 다르다. operator new는 메모리 할당은 되었지만 초기화되지 않은 메모리의 포인터(void*)를 반환하는데 반해서 allocator는 반환되는 포인터(T*)가 메모리에 생성조차 안된 상태이다.

 

대부분의 표준 컨테이너는 자신이 생성될 때 같이 붙어온 할당자를 한 번도 호출하지 않는다.

예를 들어 list는 별다른 할당자를 추가로 지정하지 않으면 list<T, allocator<T>>로 정의된다.

 

std::list<int> L; /* std::list<int, allocator<int>> L */

template<typename T, typename Allocator = allocator<T>>
class list {
private:
    Allocator alloc;
    struct ListNode {
        T data;
        ListNode* prev;
        ListNode* next;
    };
...
};

list는 대략 이런식으로 구성되어 있을 것이다. 그런데 노드가 추가될 때, 노드의 타입은 ListNode이지 T가 아니다.

그래서 할당자로 allocator<T>가 넘어가도 쓸모가 없어서 사용하지 않는다.

ListNode에 대한 할당자는 other라는 이름으로 재정의 되어있는데 allocator<T> 안에 rebind라는 구조체 안에 들어있다.

 

template<typename T>
class allocator {
public:
    template<typename U>
    struct rebind {
        typedef allocator<U> other; /* std::allocator<T>::rebind<U>::other */
    };
...
};

 

마지막으로 커스텀 할당자를 작성할 일이 생겼을 때 기억해야 할 것들을 정리한다.

 

◾ 할당자를 템플릿으로 만든다. 템플릿 매개변수는 메모리를 할당하고자 하는 객체 타입 T를 사용한다.

◾ pointer와 reference라는 타입 재정의를 제공하되 항상 pointer는 T*, reference는 T&이도록 한다.

◾ 할당자에는 객체별 상태를 절대로 주지 않는다.

◾ 할당자의 allocate 멤버 함수에는 필요한 바이트 수가 아닌 객체의 개수를 매개 변수로 넘긴다. T* 포인터를 반환하지만 T 객체가 생성되지는 않은 상태임을 명심해야한다.

◾ 표준 컨테이너에서 필요로 하는 rebind 중첩 템플릿을 꼭 제공한다.

 

 

항목 11 : 커스텀 할당자를 제대로 사용하는 방법을 이해하자

◾ 사용 예1)

void* mallocShared(size_t bytesNeeded);
void freeShared(void *ptr);

template<typename T>
class SharedMemoryAllocator {
public:
    ...
    pointer allocate(size_type numObjects, const void* localityHint = 0) {
        return static_cast<pointer>(mallocShared(numObjects * sizeof(T)));
    }
    void deallocate (pointer ptrToMemory, size_type numObjects) {
        freeShared(ptrToMemory);
    }
};

공유 메모리 힙을 관리할 목적으로 malloc과 free함수를 본떠서 만들고 STL 컨테이너에 넣어서 공유 메모리 매커니즘을 쓴다고 가정한다.

 

typedef std::vector<double, SharedMemoryAllocator<double>> SharedDoubleVec;
...
{
    SharedDoubleVec v;
    ...
}

공유 메모리를 위해 커스텀 할당자를 만들고 템플릿 매개변수로 넘겨줬음에도 v는 공유 메모리 안에 위치하지 않는다.

 

void* pVectorMemory = mallocShared(sizeof(SharedDoubleVec)); // 충분한 공유 메모리 할당
SharedDoubleVec* pv = new (pVectorMemory) SharedDoubleVec; // 전용 new를 써서 객체를 메모리에 생성
...
pv->~SharedDoubleVec(); // 객체 소멸
freeShared(pVectorMemory); // 메모리 해제

 

진짜로 공유 메모리에 두려면 수동으로 할당-생성-소멸-해제를 직접 해주어야 한다.

 

◾ 사용 예2)

두 개의 힙에서 메모리를 관리한다.

 

class Heap1 {
public:
    ...
    static void* alloc(size_t numBytes, const void* memoryBlockToBeNear);
    static void dealloc(void* ptr);
    ...
};

class Heap2 { /* Heap1과 동일한 인터페이스 */ };

 

template<typename T, typename Heap>
SpecialHeapAllocator {
public:
    ...
    pointer allocate(size_t numObjects, const void* localityHint = 0) {
        return static_cast<pointer>(Heap::alloc(numObjects * sizeof(T), localityHint));
    }
    void deallocate(pointer ptrToMemory, size_tpe numObjects) {
        Heap::dealloc(ptrToMemory);
    }
    ...
};

STL 컨테이너 몇 개를 종류에 맞춰서 각기 다른 힙에 모아두고 싶다면 Heap1, Heap2를 사용하도록 설계된 할당자를 만든다.

 

std::vector<int, SpecialHeapAllocator<int, Heap1>> v;
std::set<int, SpecialHeapAllocator<int, Heap1>> s;

std::list<Widget, SpecialHeapAllocator<Widget, Heap2>> l;
std::map<int, string, SpecialHeapAllocator<std::pair<int, string>, Heap2>> m;

(항목 11은 이해가 잘 되지 않아서 추가로 더 찾아봐야 할 것 같다.)

 

 

항목 12 : STL 컨테이너의 쓰레드 안전성에 대한 기대는 현실에 맞추어 가지자

std::vector<int> v;

auto first5(std::fint(v.begin(), v.end(), 5));
if (first5 != v.end())
    *first5 = 0;

이 코드는 다중 스레드 환경에서 문제가 될 수 있다. 값을 찾아서 반복자를 반환 받았는데 그사이 v의 값이 변하면 이후 조건식은 쓸모가 없어진다.

이 코드가 스레드 안전성을 가지려면 아래 세줄이 모두 락이 걸린채로 실행되어야 한다.

위와 같은 상황 말고도 많은 상황들이 존재할텐데 모든것을 예측해서 스레드에 안전하게 STL을 구현하는것은 매우 어려운일이다.

그렇기때문에 STL 컨테이너에게 스레드 문제 해결을 전적으로 믿고 맡길 수 없고 직접 스레드 동기화를 제어해주는것이 낫다.

 

STL은 여러 스레드가 하나의 컨테이너를 읽거나 쓰는 일에 대해서는 스레드 안전성을 기대해도 된다. 단, 읽고 쓰기가 동시에 이뤄져서는 안된다.

하지만 동시성 제어의 문제까지 없애주지는 않는다.