STL에는 auto_ptr라는 스마트 포인터가 있지만 할당하면 소멸식 복사(destructive copy)로 자원에 대한 소유권을 넘겨주는 동작을 한다. STL 알고리즘은 값에 의한 복사가 기본 동작이라서 컨테이너에 못 넣는 스마트 포인터가 되겠다. 이게 이슈가 많이 돼서 이름도 있다. COAP(Container Of Auto_Ptr).
shared_ptr은 TR1(Technical Report 1)에서 추가된 스마트 포인터이다. 소유권을 넘겨주는 동작이 아니라 소유권을 나눠 가지는 스마트 포인터다. 우리가 흔히 스마트 포인터라 부르는 것처럼 동작한다. 자원 관리로는 아주 친근한 우리 친구 레퍼런스 카운터(reference counter)를 사용한다. 자원을 소유한 객체가 늘어나면 레퍼런스 카운터를 증가시키고 그 객체가 삭제되면 레퍼런스 카운터를 감소시켜서 결국 0이 되면 이 자원은 이제 사용하지 않으니깐 삭제한다.
처음에는 라이브러리를 배우게 되고 이후에는 어떻게 하면 효율적으로 사용할 수 있는지 배우게 된다. 이 세상에 효율성을 따지지 않고 맘 편하게 쓸 수 있는 라이브러리가 과연 있을까? 그런 라이브러리가 있으면 얼마나 좋겠냐 만은 그런 거 없다. 효율적으로 쓰려면 어떻게 구현되어 있는지 알아야 한다. 특히 범용적으로 사용할 수 있게 설계된 STL은 더하다. 다른 라이브러리와 비교해 알아야 할 게 많아서 더 미움을 받는지도 모르겠다. 경험이나 소스 분석을 통해서 배우게 되는 과정을 다이렉트로 배울 수 있는 고마운 책이다.
예전에 본 책인데, 최근에 다시 한번 펼쳐보게 됐다. 그냥 읽어보는 것과 내 것으로 만드는 것은 역시 다르긴 다르다. 이번에는 읽었지만 지나치고 사용하지 않았던 것들과 유용한 데 사용하지 않은 것들을 다시 한번 정리해봤다. 역시 읽는 것보다 정리하는데 시간이 더 들었다.
이게 전부가 아니라 빙산의 일각일 뿐이라는 게 문제다. 뭐~ 평생 배우는 수밖에 없지.
사용자 입력은 서식화된 입력(공백 문자 무시 등)이 필요하지만 파일 입출력에서는 서식화된(formatted) 입력이 필요 없는 경우가 대부분이다. 서식화된 입출력은 쌩 입출력보다 처리를 하는 게 많아서 속도가 느린 게 당연하다. 공백 문자 무시 옵션을 켜도 되지만 이런 서식화 입출력 때문에 이걸 사용하는 건데, 이럴 바에는 서식화 처리를 하지 않는 istreambuf_iterator, ostreambuf_iterator를 사용하자. 당연히 속도 면에서 상대가 안 된다. 바이너리 읽기 쓰기에 적합하다.
두 값이 같은가를 판단하는 두 가지 방법이 존재한다. 첫 번째 방법은 두 값이 같은지를 바로 판단하는 것이고 두 번째 방법은 작지도 않고 크지도 않다는 것을 확인해서 두 값이 같은지를 판단한다. 이 첫 번째 방법은 operator == 로 판단하는데, A == B 이면 두 값이 같다고 판단한다. 반면 두 번째 방법은 operator< 로 판단하는데, !(A < B) && !(A > B) 이면 두 값이 같다고 판단한다.
상등 관계와 동등 관계는 수학적인 개념인데, 동등 관계(equivalence relation)에서 반대칭 관계(antisymmetric releation)를 만족하면 상등(equality)하다고 한다. 동등 관계에 대칭 관계(Symmetric relation)가 포함되므로 결국 상등 하려면 대칭 관계와 반대칭 관계 둘 다 만족해야 하는데, 이 관계를 만족하는 연산은 같다(=) 연산밖에 없다.
상등 관계와 동등 관계가 이렇다. 이게 왜 STL과 관련지어서 나오냐면 같은 값을 가졌는지 판단할 때, find()류는 operator== 로 하고 std::insert()류는 operator< 로 하기 때문이다. 하나만 쓰지! 참 원망스럽다. 하지만 이해가 가기도 한다. 연관 컨테이너(set, multiset, map, multimap)는 정렬된 순서로 내부 데이터를 관리하는데, 이때 정렬 기준으로 operator< 를 사용한다. 이 연산으로 동등 관계를 파악할 수 있는데, 구태여 상등 관계를 밝히는 operator== 연산을 추가로 정의할 필요가 없고 만약 쓴다면 더욱 혼란스러울 것 같다.
transform(), copy() 알고리즘과 같이 연산을 하거나 단순 복사를 하는 알고리즘을 사용할 때, 결과물을 쓰기 위한 반복자(iterator)를 함수 인자로 받는다. = operator로 값을 쓰기 때문에 결과물을 특정 컨테이너 뒤에 삽입하려면 귀찮은 과정을 거쳐야 한다. 이럴 때 쓰라고 만들어 놓은 게 반복자 어댑터이다. 내부 구현을 보면 = operator 를 오버로딩해서 push_back(), push_front(), insert() 를 호출한다.
// 벡터 정의
int arr1[] = { 0, 1, 2, 3, 4 };
int arr2[] = { 5, 6, 7, 8, 9 };
typedef std::vector<int> IntegerVector;
IntegerVector v1(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
IntegerVector v2(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]));
// v1 벡터의 원소를 v2 벡터에 append한다.
v2.resize(v1.size() + v2.size());
std::copy(v1.begin(), v1.end(), v2.end() - v1.size());
// 콘솔 출력
std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, " "));
반복자 어댑터를 사용 안 하면 resize()와 반복자 연산을 해야 한다.
O(logN)으로 수행되는 바이너리 검색(binary search) 이다. 물론 바이너리 검색 알고리즘의 전제 조건인 정렬된 순서를 보장해야 하므로 원소들이 정렬된 컨테이너에서만 제대로 동작한다.
binary_search()는 리턴값이 bool인 함수여서 원소가 컨테이너에 있는지 확인하는 용도로 사용한다. 확인만 하려는 경우에 반복자(iterator) 비교가 필요 없어서 간단하게 사용할 수 있다. 하지만 컨테이너에서 원소를 검색할 때 찾아낸 원소로 작업을 하는 게 대부분이라서 그닥 많이 사용할 것 같지는 않다.
// 컨테이너 정의
static const int arr[] = { 1, 2, 2, 2, 3, 3, 4, 5, 7, 7 };
typedef std::vector<int> IntVector;
IntVector v(arr, arr + sizeof(arr) / sizeof(arr[0]));
// 원소 출력
std::cout << "elements in container" << std::endl;
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
// 검색
std::cout << "# binary_search : 3 - " <<
(std::binary_search(v.begin(), v.end(), 3) ? "true" : "false") << std::endl;
std::cout << "# binary_search : 6 - " <<
(std::binary_search(v.begin(), v.end(), 6) ? "true" : "false") << std::endl;
bool IsOdd(int num)
{
return num % 2 == 1;
}
int main()
{
int numArr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
typedef std::vector<int> IntegerVector;
IntegerVector v(numArr, numArr + sizeof(numArr) / sizeof(numArr[0]));
IntegerVector::iterator iter = std::find_if(v.begin(), v.end(), IsOdd);
if (iter != v.end())
{
std::cout <<
"std::find_if(v.begin(), v.end(), IsOdd) : " << *iter << std::endl;
}
return 0;
}
이런 코드로 컨테이너에 있는 원소 중 첫 번째 홀수를 찾을 수 있다. 만약 첫 번째 짝수를 찾으려고 한다면? IsEven 함수를 만들어도 되는데, 함수 어댑터를 사용하면 not1(IsOdd)로 기존 코드를 재사용 할 수 있다. (물론 바로 어댑터를 쓸 수 있는 건 아니고 어댑터를 붙일 수 있게 IsOdd()를 수정해야 한다.) 이처럼 함수 어댑터는 기존 코드의 재사용을 도와줘서 생산성을 향상시킬 수 있게 한다.
Effective STL 항목 15에서 string이 여러 가지 방식으로 구현되어 있다는 걸 상기시키고 있다. 구현 방법까지 표준 문서에 정의하지 않았기 때문에 당연한 결과이기도 하다. VS 2005에 포함된 딩컴웨어 STL은 어떻게 구현되었나 궁금해서 찾아봤다.
책에서는 4가지 타입의 구현 방법을 설명해놨는데, 딩컴웨어의 string 구현을 보고 D 타입을 적었던 거 같다. 짧은 문자는 동적 할당을 하지 않고 내부 버퍼를 사용하는 단문자열 최적화(small string optimization) 구현이 되어 있었다.
STL 알고리즘 이름의 _if 접미사는 술어 함수(predicate)를 인자로 받는 것을 의미한다. 이 술어 함수를 알고리즘 안에서 호출해서 돌려받은 반환 값에 따라 동작을 수행할지 말지를 결정하게 된다. 예를 들면 count_if()는 술어 함수 호출결과가 true인 원소들의 개수를 세는 알고리즘이고 remove_if()는 술어 함수 호출 결과가 true인 원소들을 제거하는 알고리즘이다.
시퀀스(Sequences – vector, list, deque) 알고리즘 중에 _if 가 있을만한 알고리즘인데 없는 알고리즘이 있다. 가장 단순한 형태인 복사를 수행하는 copy() 알고리즘이 주인공인데, 정말 있을법한데 없는 알고리즘이다. Effective STL 항목 36에서 이 사실을 알게 됐는데, 혹시나 싶어서 TC++PL을 보니 이 책에도 copy_if()에 대한 언급이 있었다. 표준 위원회가 STL 명세를 결정할 때 제거한 알고리즘이다. Where is copy_if (was: STL question: where is find_first_not_of?)에서 비야네 스트롭스트룹의 답변을 볼 수 있다.
컨테이너 정렬이 필요할 때, sort를 사용하고 순서가 유지돼야 하면 stable_sort를 사용했다. partial_sort와 nth_element는 한 번도 사용해본 적이 없는데, 일부분만 정렬이 필요하거나 몇 번째 원소를 뽑을 때 유용하게 사용할 수 있을 것 같다. 예를 들면 최고 작은 수 10개만 차례대로 혹은 차례 상관없이 뽑는다던지, 9번째로 작은 수만 뽑는다던지 할 때에 사용하면 좋을 거 같다. 구현하는데 시간을 추가로 쓰는 것도 아니고 이미 구현되어 있는데, 딱 필요한 만큼만 정렬해서 시간을 절약할 수 있다. 아무리 작은 시간이라 하더라도 그냥 낭비하는 건 죄를 짓는 거.
nth_element는 정렬 기준에 따라 몇 번째 원소만 정확히 뽑아준다. 원소를 기준으로 정렬 기준에 맞게 좌우를 나눠주기는 하는데, 그 원소들 사이에 정렬은 되어 있지 않은 상태이다. partial_sort는 시작점부터 지정한 위치까지만 정렬해준다. 나머지는 정렬되지 않은 상태로 놔둔다. sort와 stable_sort는 시작점에서 끝점까지 정렬하는데, 정렬되고 난 뒤 stable을 보장 여부가 다르다. 동일한 정렬 기준을 가진 녀석들의 순서가 정렬 후에도 바뀌지 않으면 stable하다고 하는데, 뒤에 소스 코드 예를 보면 단박에 이해된다. 참고로 merge sort, insertion sort가 대표적인 stable sort 알고리즘이고 unstable sort의 대표적인 알고리즘은 quicksort 이다.
수행 시간은 nth_element < partial_sort < sort < stable_sort 이다.