항목 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가 이뤄질 때 후위형 증가로 인해 반복자가 무효화되지 않는다.

항목 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 */
    };
...
};

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

항목 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은 여러 스레드가 하나의 컨테이너를 읽거나 쓰는 일에 대해서는 스레드 안전성을 기대해도 된다. 단, 읽고 쓰기가 동시에 이뤄져서는 안된다.

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

항목 1 : 적재적소에 알맞은 컨테이너를 사용하자

◾ 표준 STL 시퀀스 컨테이너 : vector, string, deque, list

◾ 표준 STL 연관 컨테이너 : set, multiset, map, multimap

vector는 일반적, list는 시퀀스의 중간에 삽입/삭제가 빈번하게 일어날 때, deque는 시퀀스의 끝에서 삽입/삭제가 빈번하게 일어날 때 사용된다.

◾ 연속 메모리(배열 기반) 컨테이너 : vector, string, deque

요소가 삽입되거나 삭제될 때 발생하는 밀어내기로 인해 수행 성능이 떨어지거나 예외 안전성에 영향을 미친다.

◾ 노드 기반 컨테이너 : list 및 표준 연관 컨테이너

요소의 삽입이나 삭제가 이루어져도 밀어내기가 발생하지 않는다.

항목 2 : "컨테이너에 독립적인 코드"라는 환상을 조심하자

각 컨테이너를 모두 지원하는 코드 작성은 무의미한 행동이다. STL의 컨테이너는 서로 바꾸어서 쓸 수 있도록 설계되어 있지 않기 때문이다.

항목 3 : 복사는 컨테이너 안의 객체에 맞게 비용은 최소화하며, 동작은 정확하게 하자

컨테이너에 객체를 담을때는 원본이 아닌 복사본이 들어가고 객체를 꺼낼때는 참조자를 얻어서 복사되어 꺼내진다.

복사되어 들어가고, 복사되어 나오는 것이 STL의 방식이다.

배열 기반 컨테이너에 insert, erase, next_permutation 등의 함수를 호출하면 내부적으로 복사를 통해 위치가 바뀐다.

이 때 객체들의 복사는 해당 클래스의 복사 멤버 함수를 사용하게 된다.

상속된 객체의 경우 복사중에 데이터가 슬라이스 되는 경우도 발생한다.

객체 대신 포인터를 컨테이너에 저장하면 슬라이스도 발생하지 않고 성능 이점이 생긴다.

STL은 복사를 많이 하긴 하지만 불필요한 복사는 피하도록 설계되어있다.

Widget w[maxNumWidgets]; // maxNumWidgets만큼 기본 생성자 호출

vector<Widget> vw;
vw.reserve(maxNumWidgets); // maxNumWidgets만큼의 크기만 미리 할당

항목 4 : size()의 결과를 0과 비교할 생각이라면 차라리 empty를 호출하자

if (c.size() == 0)
if (c.empty())

두 코드는 본질적으로 같다.

하지만 empty는 모든 컨테이너에서 상수 시간에 수행되는 반면에 size는 선형 시간에 수행되는 컨테이너가 존재한다.

예를 들어 list의 size()와 splice()는 둘 중 하나가 반드시 선형 시간이어야 한다. 그리고 보통 splice가 상수 시간으로 구현되어있다.

항목 5 : 단일 요소를 단위로 동작하는 멤버 함수보다 요소의 범위를 단위로 동작하는 멤버 함수가 더 낫다

v1.assign(v2.begin() + v2.size() / 2, v2.end()); // v2의 뒤쪽 절반 복사

iterator를 사용한 범위 단위 동작이 아니라 단일 요소 단위로 같은 동작을 하려면 필연적으로 반복문을 사용할 수 밖에 없다.

범위 단위 멤버 함수가 코드도 더 간결해지고 가독성도 높아진다.

/* data: 배열, numValues: 배열크기 */
std::copy(data, data + numValues, std::inserter(v, v.begin()));

배열의 복사를 위와 같이 구현하는 경우 시퀀스 컨테이너의 성능에 있어서 발목을 붙잡는 요소들이 몇 가지 발생한다.

첫 번째, inserter는 배열 요소 개수만큼 호출된다.

두 번째, inserter가 호출될때마다 기존에 삽입된 v의 요소가 한칸씩 뒤로 계속 밀린다. (복사가 빈번하게 일어남) 범위 단위 멤버 함수인 insert라면 한 번에 마지막 위치까지 옮긴다.

세 번째, vector의 경우 복사되는 요소의 갯수가 많다면 크기 확장이 빈번하게 일어나서 메모리 할당의 횟수가 많아진다.

string, deque, list의 경우에는 조금씩 다르지만 어쨌든 공통적으로 범위 단위 insert가 성능면에서 우수하다.

연관 컨테이너에서는 단일 요소 버전과 범위 멤버 함수의 효율성을 따지기 어렵다.

다만 범위 멤버 함수는 간결한 코드와 가독성에 있어서 확실하게 이점이 있다.

/* 범위 생성 */
container::container(iterator begin, iterator end);

/* 범위 삽입 */
void container::insert(iterator position, iterator begin, iterator end);

모든 표준 컨테이너는 begin, end를 인자로 갖는 생성자와 동일한 형태의 insert 멤버 함수를 지원한다.

(추가: 책에서는 시퀀스 컨테이너와 연관 컨테이너의 erase 반환값이 달랐지만 모던 C++은 동일하다.)

void container::assign(iterator begin, iterator end);

모든 표준 시퀀스 컨테이너는 동일한 범위 버전의 assign 멤버 함수를 지원한다.

최종적으로 정리하자면 범위 멤버 함수는 작성이 쉽고, 가독성이 좋고, 성능도 월등히 좋다.

항목 6 : C++ 컴파일러의 어이없는 분석 결과를 조심하자

std::ifstream dataFile("ints.dat");
std::list<int> data(std::istream_iterator<int>(dataFile), std::istream_iterator<int>());

위의 코드는 컴파일은 되지만 런타임에 아무 일도 하지 않는다. 그 이유는 리스트가 아닌 함수의 선언으로 분석하기 때문이다. 반환타입이 std::list<int>이고 매개변수가 두개인 함수 data의 선언이다.

해결 방법은 익명 객체가 아니라 각 반복자 객체를 정의해서 인자로 넘겨주는 것이다.

std::ifstream dataFile("ints.dat");
std::istream_iterator<int> dataBegin(dataFile);
std::istream_iterator<int> dataEnd;
std::list<int> data(dataBegin, dataEnd);

익명 객체를 사용하지 않는 것은 프로그래밍 스타일에 적합하다고 볼 수 없지만 혼란을 주지 않기 위해서는 어쩔 수 없다.

항목 7 : new로 생성한 포인터의 컨테이너를 사용할 때에는 컨테이너가 소멸되기 전에 포인터를 delete하는 일을 잊지 말자

컨테이너는 자신이 소멸할 때 각 요소 자체를 없애주기는 하지만 요소가 포인터인 경우 포인터에 대해 delete를 수행하지 않기 때문에 소멸자가 호출되지 않는다.

struct DeleteObject {
    template<typename T>
    void operator()(const T* ptr) const { delete ptr; }
};

std::for_each(dssp.begin(), dssp.end(), DeleteObject()); // 자동으로 타입이 추론된다

이런 방식은 타입 안전성은 있지만 예외 안전성이 없기 때문에 스마트 포인터를 사용해 주어야 한다.

void doSomeThing() {
    typedef std::shared_ptr<Widget> SPW;
    std::vector<SPW> vwp;
    for (int i = 0; i < SOME_MAGIC_NUMBER; ++i)
        vwp.push_back(SPW(new Widget));
}

스마트 포인터는 유효 범위를 벗어날 때 참조 횟수가 줄어들고 0이 되면 소멸자를 호출하기 때문에 예외 안전성이 보장된다.

(추가: auto_ptr의 컨테이너는 사용하지 말라고 한다. 하지만 요즘은 auto_ptr이 삭제되었다.)

항목 8 : auto_ptr의 컨테이너는 절대로 만들지 말자

(추가: 우선 언급하자면 auto_ptr은 C++11부터 사용 자제 권고가 계속 내려졌고 C++17부터 아예 제거되었다.)

auto_ptr이 담긴 컨테이너는 컴파일 조차 되어서는 안된다. auto_ptr은 복사가 허용되지 않기 때문이다.

예를 들어 auto_ptr이 담긴 컨테이너를 정렬한다고 했을 때, sort함수 내부적으로 요소를 임시 지역 변수로 '복사' 하는 과정이 있다. 이 때 소유권이 이동되기 때문에 컨테이너의 값이 소실된다.