목차
STL 컨테이너는 연속 메모리 컨테이너와 노드 기반 컨테이너로 나눌 수 있습니다.
연속 메모리 컨테이너는 동적 할당된 하나 이상의 메모리 단위에다가 데이터 요소를 저장해 두는 컨테이너 입니다. 각 메모리 단위는 하나 이상(대개 하나)의 요소를 담고 있지요. 새 요소가 삽입되거나 이미 있던 요소가 지워지면(erase), 같은 메모리 단위에 있던 다른 요소들은 앞 혹은 뒤로 밀려나면서 새 요소가 삽입될 공간을 만들든지, 지워진 공간을 메웁니다. 이러한 "밀어내기" 때문에 수행 성능의 발목을 잡을 수 있고, 예외 안정성에도 영향을 미칩니다. 표준 연속 메모리 컨테이너는 vector, string, deque입니다. 비표준 컨테이너인 rope 역시 연속 메모리 컨테이너입니다.
노드 기반 컨테이너는 동적 할당된 하나의 메모리 단위에다가 하나의 요소만을 저장합니다. 컨테이너 요소를 삽입 혹은 삭제했을 때 노드의 포인터만이 영향을 받지, 노드의 내용은 그대로입니다. 따라서, 삭제나 삽입이 일어났다고 해도 나머지 요소들이 밀려난다든지 하는 일이 없습니다(해당 노드가 없어지고 생기고 하는 것이니까요). 연결 리스트를 나타내는 컨테이너, 즉 list나 slist가 노드 기반이고, 표준 연관 컨테이너(set, multiset, map, multimap) 모두가 노드 기반입니다(이것들은 전형적으로 균형 트리로 구현되어 있습니다). 비표준인 해쉬 컨테이너도 노드 기반으로 구현되어 있습니다.
이제는 "어떤 상황에 어떤 컨테이너를 쓰면 좋을까?"에 관련된 문답을 수월하게 정리할 수 있을 것입니다. STL에 속하지 않은 컨테이너(배열, bitset등)는 논외로 합니다.
컨테이너의 아무 위치에 요소를 삽입할 수 있어야 하나요? 그렇다면, 시퀀스 컨테이너가 필요합니다. 연관 컨테이너는 이것이 불가능합니다.
컨테이너 내의 요소들의 순서 결정에 직접 관여하고 싶나요? 그렇지 않은 경우에는 해쉬 컨테이너가 가장 괜찮은 선택이고, 그렇다면 해쉬 컨테이너는 피해야 합니다.
표준 C++에 포함된 컨테이너를 사용해야 하나요? 그런 경우에는 해쉬 컨테이너, slist, rope는 쓸 수 없습니다.
어떤 타입의 반복자가 필요하십니까? 임의 접근 반복자이어야 한다면 여러분의 선택폭은 vector, deque, string으로 좁아지고요, rope도 고려해 볼 수 있습니다. 양방향 반복자가 필요한 경우에는 slist와 해쉬 컨테이너는 쓸 수 없습니다.
요소 삽입이나 삭제시 다른 컨테이너 요소들이 밀려나는 일이 없어야 한다면요? 그런 경우에는 연속 메모리 컨테이너에 손도 대지 마세요.
컨테이너 내의 데이터가 C의 데이터 타입과 메모리 배열 구조적으로 호환되어야 하나요? 이 때에는 vector 밖에 쓸 것이 없습니다.
탐색 속도가 가장 중요한 관심사인가요? 그렇다면 해쉬 컨테이너, 정렬된 vector, 그리고 표준 연관 컨테이너 중 하나를 택하세요. 이 순서대로 고려하면 될 것입니다.
컨테이너의 참조 카운팅이 신경 쓰이나요? 그렇다면 string 가까이에는 가지 않는 것이 좋습니다. 많은 string 코드가 참조 카운팅이 되도록 구현되었습니다. rope도 피하세요. rope는 확실히 참조 카운팅에 기반하여 구현되었기 때문이죠. 물론 어떻게든 문자열을 나타낼 필요는 있습니다. 이럴 때 vector<char>를 쓰는 것입니다.
삽입과 삭제 동작이 트랜잭션인 의미를 가지고 이루어졌으면 하나요? 즉, 삽입과 삭제 동작을 안정적으로 되돌릴(roll back) 수 있어야 하느냐란 뜻입니다. 만일 그렇다면 노드 기반 컨테이너를 고려해 보기 바랍니다. 트랜잭션인 삽입이 여러 개의 요소(범위로 주어집니다.)에 대해 이루어져야 할 경우에는 list를 선택합니다. 그 요구를 만족할 수 있는 유일한 STL 표준 컨테이너입니다. 트랜잭션인 동작은 코드에 예외 안정성을 추가하고자 하는 프로그래머에게 대단히 중요한 특징입니다(물론 연속 메모리 컨테이너라고 해서 이것이 되지 않는다는 법은 없지만, 수행성능의 비용도 만만치 않고 코드가 간단하지 않습니다).
반복자, 포인터, 참조자가 무효화(포인터가 가리키고 있던 메모리의 실제 내용이 없어지는 일을 뜻한다)되는 일을 최소화해야 하나요? 이런 경우에는 노드 기반 컨테이너를 사용하기 바랍니다. 노드 기반 컨테이너는 노드 삽입과 삭제가 일어나도 기존의 반복자나 포인터 혹은 참조자가 무효화되지 않기 때문입니다(가리키고 있는 요소를 삭제하지 않는 한 말이죠). 반대로, 연속 메모리 컨테이너는 전체적인 메모리 재할당이 일어나기 때문에 반복자나 포인터, 참조자가 무효화되기 쉽습니다.
임의 접근 반복자를 지원하는 시퀀스 컨테이너가 필요한데, 요소 삭제가 일어나지 않고 요소 삽입이 컨테이너의 끝에서만 일어나는 한, 포인터와 참조자가 무효화되지 않는 것이 필요한가요? 아주 특별한 경우이긴 하지만, 어쩌다 이런 경우를 만난다면 deque가 정답입니다(deque는 요소 삽입이 끝에서 일어날 때 반복자만 무효화되는 재미있는 컨테이너입니다. STL 컨테이너 중 포인터와 참조자를 무효화시키지 않고 반복자만 무효화되는 것은 deque가 유일합니다).
STL은 일반화에 기초를 두고 만든 프로그래밍 장치입니다. 컨테이너 타입은 시퀀스와 연관 컨테이너로 일반화 되었고, 각 타입에 속하는 컨테이너는 비슷한 기능을 가지고 있습니다.
일반화의 좋은 개념때문에 여러분은 그냥 상황에 맞는 컨테이너를 사용해도 될 일을 가지고 모든 컨테이너에 대해 쓸수 있도록 코드를 만듭니다. 이를테면 vector를 쓰는 부분을 만들면서 언제든지 vector 대신 deque나 list를 쓸 수 있는 여지를 남겨 놓는 등등 - 코드를 하나도 바꾸지 않고서 - 입니다. 즉, 컨테이너 독립적인 코드를 작성하려고 기를 쓴다는 것입니다. 이러한 종류의 일반화는, 의도는 좋지만 거의 항상 잘못된 이해에서 오는 행동입니다.
시퀀스 컨테이너와 연관 컨테이너 양쪽에 대해 동일하게 동작하는 소프트웨어를 만드는 일은 시도 자체가 무의미하다는 것을 알게 됩니다. 우선, 대다수의 멤버 함수들이 한쪽 부류의 컨테이너에만 치우쳐 들어 있습니다. 예를 들어, push_back과 push_front는 시퀀스 컨테이너에서만 지원되고, count와 lower_bound 등은 연관 컨테이너에서만 지원됩니다. insert나 erase 등의 기본적인 함수는(양쪽에 다 있긴 하지만) 시그너쳐나 동작 원리가 다릅니다.
이런 가정을 해 볼 수도 있습니다. 가장 많이 쓰이는 시퀀스 컨테이너인 vector, deque, list에 대해서만 쓸 수 있는 코드를 만드는 것이죠. 각 컨테이너의 공통된 특징만을 사용하도록 프로그래밍해야 한다는 이야기인데, 이러면 reserve나 capacity 등은 무용지물입니다. 왜냐하면 deque와 list에서 제공하지 않는 것이니까요. list 때문에 operator[]도 쓸 수 없고, 양방향 반복자에 대해 동작하도록 코드를 제한시켜야 합니다. 임의 접근 반복자를 사용하는 알고리즘에는 손도 못 댄다는 결론이 나오죠. sort, stable_sort, partial_sort, nth_element 등의 주옥같은 함수들을요.
간 빼고, 쓸개도 빠지고, 창자도 빠지고 나면 여러분의 "일반화된 시퀀스 컨테이너"는 reserve, capacity, operator[], push_front, pop_front등을 사용할 수 없습니다. 이것이 여러분이 애플리케이션 제작에 쓰려고 한 컨테이너 맞습니까? 아닐 것 같은데요.
시퀀스 컨테이너는 포기하고 연관 컨테이너에 대해서만 독립적으로 동작하는 코드를 만들어야겠다고 생각한 분은 그럼 다행일까요? 상황은 더 좋지 않습니다. 우선, set과 map에 대해 코딩하는 것은 불가능에 가깝습니다. set은 하나이 객체를, map은 객체의 pair를 저장하니까요.
현실을 직시하세요. 독립적인 코드라고 좋은 것은 아닙니다. STL 컨테이너는 각자 자신만의 장점과 약점을 가지고 있습니다. 서로 바꾸어서 쓸 수 있도록 설계되지 않았고, 감싼다고해서 되는 것이 거의 없습니다.
컨테이너의 본분은 객체를 담아 관리하는 것입니다. 어떤 컨테이너에 어떤 객체를 넣을 때나 뽑아낼 때, 여러분이 지정한 그 객체가 복사되어 들어가고, 복사되어 나오죠. 이것이 STL의 방식입니다.
객체의 복사는 해당 클래스의 복사용 멤버 함수를 사용하여 이루어지는데, 특히 복사 생성자와 복사 대입 연산자가 사용됩니다. 임의로 정의한 클래스로 Widget이 있다고 합시다. 복사 관련 함수는 대개 다음과 같이 선언됩니다.
class Widget {
public :
STL에서 복사는 거의 모든 순간에 일어납니다. 이번 항목을 쓰려고 한 동기를 이제 이해하시겠죠? 복사에 드는 비용이 큰 객체를 컨테이너에 넣을 때에는 그냥 단순히 객체를 컨테이너에 넣기만 하면 수행 성능의 병목현상을 일으키고 만다는 것입니다. 컨테이너에 더 많은 객체가 들어갈수록 여러분의 시스템에 몰아치는 메모리 사용량과 CPU 사이클의 폭풍은 더욱 더 거세어 집니다.
상속된 객체의 경우 복사 동작 중에 데이터가 싹둑 베이는 경우도 있습니다. 이것을 슬라이스(slice)라고 하는데, 기본 클래스 객체의 컨테이너를 만들어 놓고 여기다가 파생 클래스 객체를 넣으면, 복사 과정에서 기본 클래스의 복사 생성자가 쓰이면서 파생 클래스 부분에 선언된 데이터는 잘려 나간다는 것입니다.
속도 빠르고, 정확하고, 그리고 슬라이스 문제에도 끄떡없는 복사를 쉽게 하는 방법을 알려드리겠습니다. 바로 객체의 컨테이너가 아닌, 포인터의 컨테이너입니다. 말하자면, Widget의 컨테이너를 생성하지 않고 Widget*의 컨테이너를 작성하는 것입니다. 하지만, 재수 없게도 포인터의 컨테이너는 STL에 관련된 골칫거리를 안고 있습니다. 이것에 대해서는 항목 7과 33에 자리를 따로 마련했습니다. 어찌 되었든 포인터의 컨테이너를 사용해서 복사를 하되 방금 이야기한 골치 거리를 피하는 데에는 스마트 포인터가 괜찮은 한 가지 방밥이란 것을 알게 될 것입니다.
컨테이너 c가 있다고 합시다. 다음의 코드
는 다음의 코드와 본질적으로 똑같습니다.
똑같다고 하는데, 왜 하나는 좋고 하나는 좋지 않다는 것일까요. empty는 size가 0인지의 여부를 반환하는 인라인 함수로 구현되어 있다는 사실까지 알려드리면 더욱 궁금할 것입니다. empty가 들어간 코드가 더 좋은데 empty는 모든 표준 컨테이너에 대해 상수 시간에 수행되지만, 몇몇 제품에서 구현된 list 클래스에서 size가 선형 시간에 수행되기 때문입니다.(이 경우가 꽤 많습니다.)
하지만, 왜 list가 문제되는 것일까요? 왜, list는 상수 시간의 효율을 가진 size를 제공할 수 없는 것일까요? 이 의문에 대한 해답은 list만이 가진 독특한 함수인 splice와 아주 밀접한 관계가 있습니다. list는 다른 표준 컨테이너와 달리 splice란 함수를 제공하여 자신이 관리하고 있는 요소 중 일정 범위의 부분을 복사를 하지 않고 다른 list에 옮겨 놓을 수 있습니다. size를 상수 시간 함수로 만들려면, 리스트의 요소 수에 영향을 주는 다른 멤버 함수 쪽을 모두 고쳐서, 동작할 때마다 리스트의 요소 수를 업데이트하도록 해야 합니다. 그런데 이 멤버 함수 중에 splice가 포함됩니다. 문제는, splice에서는 다른 리스트로 옮겨지는 노드의 개수를 알려면 어쩔 수 없이 "세어야" 한다는 것이고, 이렇게 하면 splice는 상수 시간 동작을 수행할 수 없게 됩니다. 게다가, 리스트의 요소 수를 업데이트하지 않도록 만들면 splice 자체는 상수 시간 동작이 가능할지 몰라도 size는 선형 시간 동작이 되고 맙니다. 다 세어야 하니까요. 아무리 고민을 해도 둘 중 하나는 포기할 수밖에 없습니다. splice와 size 중 하나만이 상수 시간 동작이 될 수 있고, 모두는 될 수 없습니다.
여러 STL 제품에서 list를 다르게 구현해 놓고 있습니다. 구현을 맡은 개발자가 size와 splice 중 어디에 비중을 두고 있는지에 좌우되지요. 지금 사용하는 라이브러리가 이렇지 않다고해도 언제 그런 상황과 만날지 아무도 모르는 일입니다. 다른 플랫폼으로 포팅(소스를 손보지 않고 되는 일이 대부분이지만요) 할 일이 생길 수 있고, 쓰고 있는 라이브러리 대신 다른 것을 설치하기로 결정할 수도 있고요.
여기 두 개의 벡터, v1과 v2가 있습니다. v1의 내용을 v2의 뒤쪽 반과 똑같이 만드는 가장 빠른 방법은 무엇일까요? 답은
이 문제에는 두 가지 의미를 품고 있습니다. 하나는 많은 프로그래머들이 있는 것조차도 모르고 지나가지만 매우 편리한 물건인 assign이란 멤버 함수가 있다는 사실을 여러분들에게 알려주기 위함입니다. 이 함수는 표준 시퀀스 컨테이너(vector, string, deque, list)라면 모두 사용 가능합니다. '컨테이너의 내용을 완전히 교체하고 싶다'라고 한다면 항상 "대입(assignment)"을 머리에 떠올리는 것이 좋습니다. 두 번째 의미는 범위 단위로 동작하는 멤버 함수가 단일 요소에 대해 동작하는 멤버 함수보다 왜 나은지를 실 예를 통해 보여주자는 것이었습니다. 범위 멤버 함수는 STL 알고리즘처럼 의도한 일을 적용할 요소들의 '범위'를 두 개의 반복자를 사용해서 지정합니다. 범위 멤버 함수를 사용하지 않고 이번 항목의 문제를 풀려고 하면, 장담컨대 루프를 쓰지 않을 수가 없습니다. 얼추 다음과 비슷한 코드가 나오지 않을까요?
지금, assign을 호출하지 않고 앞에 코드를 쓰는 일이 훨씬 손이 많이 간다는 것을 확인할 수 있습니다 루프는 효율의 발목을 잡는 요소이지만, 잠깐만 시간을 내어 조금 더 알아보도록 하겠습니다.
이렇게 쓰기는 했지만 assign을 사용했을 때와 비교하면 여전히 타자량이 많습니다. 게다가, 앞의 코드에서는 루프가 눈에 보이지 않을 뿐 copy의 내부에서는 분명히 루프가 숨어 있습니다. 결국, 효율에 묶이 족쇄는 풀리지 않습니다. 삽입 연산자(말하자면 inserter, back_inserter, 혹은 front_inserter)를 사용해서 복사 대상 범위를 지정하는 copy는 거의 모두 범위 멤버 함수로 바꿀 수 있습니다 - 아니, 바꾸어야 합니다. 예를 들어, 다음과 같이 copy는 insert의 범위 함수 버전으로 대체할 수 있습니다.
위의 코드는 무슨 동작이 일어났는지를 몸(?)으로 직접 말하고 있습니다. 데이터가 v1로 삽입되고 있다는 것입니다.
단일 요소 멤버 함수보다 범위 멤버 함수가 더 좋은 이유 두 가지를 확인했습니다.
범위 멤버 함수를 사용한 코드가 대개 짧다.
범위 멤버 함수는 훨씬 명확하고 간결한 의미를 전달한다.
요컨대, 범위 멤버 함수를 쓰면 작성하기도 쉽고 이해하기도 쉬운 코드가 나온다는 이야깁니다.
범위 멤버 함수와 단일 요소 멤버 함수 중 어느 것이 좋은지에 대한 기준이 표준 시퀀스 컨테이너에 대해서는 효율입니다. 단일 요소 멤버 함수에서는 메모리 할당자의 요구도 많고 객체 복사도 빈번하며, 불필요한 연산도 더 자주 일어납니다. 같은 일을 한다고 볼 때 범위 멤버 함수는 이보다 효율적입니다. 예를 들어, 여러분은 int의 배열을 vector의 앞에다가 복사하고 싶습니다(일단 데이터는 벡터가 아니라 배열 쪽에 들어있습니다). vector의 범위 버전의 insert 함수를 사용하면 이 작업은 진짜로 우습게 끝납니다.
이것을 루프에 insert를 넣은 순환 호출로 구현하면 다음과 비슷한 꼴이 될것입니다.
이 코드만 보면 insert의 반환 값을 루프 내의 다음 순환 단계 때 쓰기 위하여 얼머나 조심스럽게 이 값을 저장해 두고 있는 지 아십니까? 매번 insertLoc의 값을 갱신하지 않았다면 문제가 두 가지나 생겼을 것입니다. 첫째는, 루프의 가장 처음을 제외한 나머지에서 예상하지 않은 동작이 수행된다는 것입니다. 이유인즉, insert를 호출하고 나면 매개 변수로 들어간 insertLoc(반복자)는 바로 무효화되기 때문이죠. 둘째는 insertLoc이 운 좋게 유효한 값으로 남았다고 해도 매번 벡터의 앞(즉 v.begin())에다가 값을 넣기(insert) 때문에, int들은 원래의 순서와 반대로 v에 들어가고 만다는 것입니다.
루프를 copy로 바꾸면 다음의 코드를 얻을 수 있을 것입니다.
copy 템플릿이 인스턴스화된 결과를 보면 루프를 직접 사용한 앞의 코드와 거의 동일합니다. 루프에서 쓰이는 단일 요소 버전의 insert가 여러분에게 세 가지의 '수행 성능세'를 부과합니다. 물론 이 세금은 범위 버전의 insert를 사용하면 내지 않아도 될 세금이죠.
첫째 세금은 불필요한 함수 호출입니다. v에다가 numValue개의 요소를 한 번에 하나씩 넣기 때문에, 결국 insert는 numValue번 불리게 됩니다. 범위 버전의 insert를 사용하면 한번의 함수 호출로 끝나기 때문에 호출 회수가 numValue-1 만큼 줄어듭니다. 물론, 인라이닝을 사용했다면 이 세금은 물지 않을 수도 있겠죠.
둘째 세금은 인라이닝으로도 공제가 불가능한 세금입니다. 새로운 요소를 넣기 위해 v에 들어 있던 요소들을 밀어 놓는 데 요구되는 비용은 어떻게 하시겠습니까? 새 값을 v에 넣기 위해 insert가 호출될 때마다, 삽입되는 위치에 있는 모든 기존의 데이터는 한 자리씩 뒤로 이동하여 넣을 공간을 마련해 주어야 합니다. 위치 p에 있는 요소는 p+1로 밀려나는 식이지요. 삽입이 일어나기 전에 있던 벡터 내 요소들은 총 numValues번 만큼 옆으로 이동해야 한다는 것입니다. 또한, insert가 호출될 때마다 각 요소가 꼭 한 자리씩 밀려나기 때문에, 원래 v에 n개의 요소가 (삽입전에) 있었다고 하면 n*numValues번의 이동이 일어나야 합니다. 이와 반대로, 표준안에 의하면 범위 버전의 insert는 컨테이너 안에 들어 있는 요소를 마지막 위치까지 바로 옮기도록 되어 있습니다. 즉, 하나의 데이터를 요소를 옮기는데 한 번이면 끝납니다. 즉, 총 비용은 n번의 이동량 뿐입니다. 컨테이너 안의 객체에 대해 복사 생성자와 대입 연산자를 총 numValue번 호출하지 않아도 됩니다.
셋째 메모리 할당에 관한 것입니다. 메모리가 꽉 찬 벡터에 데이터 요소를 하나 넣으려고 하면 그 벡터는 더 많은 여유 용량을 가진 메모리를 새로 할당하고, 원래의 메모리에 있던 데이터를 모두 새 메모리에 복사한 후에, 원래의 메모리를 해제합니다. 그리고 나서 삽입하려고 했던 요소를 추가하지요. 대부분의 제품에서 벡터는 메모리가 꽉 찰 때마다 자신의 용량을 두 배로 늘리도록 구현되어 있습니다. 즉 numValues개의 새 데이터 요소를 삽입하려고 하면 메모리 할당을 log2numValues번이나 하게 되는 셈입니다. 반면에, 범위 버전의 삽입 함수는 삽입 전에 필요한 메모리량을 예측할 수 있기 때문에, 메모리 할당을 무식하게 여러 번 수행하지 않습니다.
방금까지 보여드린 분석 결과는 vector에 관한 것이지요. 하지만, string도 동일한 양상을 보여줍니다. deque의 경우에는 비슷하긴 하지만 vector와 string과는 다른 메모리 관리 방식을 취하고 있어서 "반복적인 메모리 재할당"에 관한 이야기는 맞지 않습니다. 하지만 불필요하게 빈번한 컨테이너 내 요소의 이동에 관한 이야기와 불필요한 함수 호출에 관한 이야기는 일반적으로 맞습니다.
표준 시퀀스 컨테이너 중에 이제 list만이 남았군요. 하지만 list 역시, 범위 버전의 insert가 단일 요소 버전보다 수행 성능에서 우수합니다. 우선 되풀이되는 함수 호출에 있어서는 역시 범위 버전이 좋습니다. 하지만, 메모리 할당에 관한 사항은 딱 맞지 않습니다. 리스트는 노드 기반으로 동작하기 때문이지요. 그런데, 그 대신에 이상한 문제가 새로 생깁니다. 리스트가 관리하고 있는 노드의 next 포인터와 prev 포인터 값이 필요 없이 되풀이해서 세팅된다는 것입니다.
연결 리스트에 어떤 요소가 추가되면, 그 요소를 담고 있는 노드의 next 포인터와 prev 포인터는 그 리스트가 세팅해 준 값을 가지게 됩니다. 비용 지불을 면하는 열쇠는 list의 범위 버전 insert를 사용하는 것입니다. 이 함수는 최종적으로 삽입될 노드의 개수를 파악할 수 있기 때문에, 불필요한 포인터 세팅을 피해 줍니다. 한 번의 대입만으로 각 포인터가 삽입 후의 노드 주소 값을 가지도록 세팅해 버립니다.
정리 : 다음에 나온 시그너쳐에서, 매개 변수 타입인 iterator는 말 그대로 컨테이너의 반복자 타입, 즉 container::iterator란 뜻입니다. 한편 InputIterator는 어떤 입력 반복자도 받아들일 수 있다는 뜻입니다.
범위 생성 : 모든 표준 컨테이너는 다음과 같은 형태의 생성자를 지원하고 있습니다.
범위 삽입 : 모든 표준 컨테이너는 다음과 같은 형태의 insert를 지원하고 있습니다.
연관 컨테이너는 자신이 가지고 있는 비교 함수를 사용 삽입될 요소가 놓일 위치를 결정하기 때문에, 위치 매개 변수를 가지고 있지 않은 시그너쳐를 제공합니다.
범위 삭제 : 역시 표준 컨테이너에서 범위 버전의 erase를 제공하고 있지만, 반환 타입은 시퀀스 컨테이너와 연관 컨테이너에 대해서 각각 다릅니다. 시퀀스 컨테이너에선 다음과 같은 형태를 쓸 수 있고,
반면에 연관 컨테이너에서는 다음과 같은 형태를 쓸 수 있습니다.
범위 대입 : 모든 표준 시퀀스 컨테이너는 범위 버전의 assign을 제공하고 있습니다.
세 가지 형태의 선언문.
아래의 코드는 double을 매개 변수로 받아 int를 반환하는 함수 f를 선언합니다.
다음 문장을 보죠. 앞의 것과 동일한 동작을 하는 문장입니다. 매개 변수 d를 둘러싸고 있는 괄호는 불필요한 것이기 때문에 컴파일러가 무시해 버립니다.
앞의 문장은 다음과 같이 매개 변수의 이름을 빼고 써도 똑같습니다.
이제 다른 형태의 함수 선언문 세 개를 더 보기로 하지요. 첫째 것은 함수 포인터를 매개변수로 받는 g라는 함수입니다. 매개 변수로 들어가는 함수 포인터는 아무 것도 받아들이지 않고 double을 반환하도록 되어 있습니다.
다음은 다른 방법으로 써본 똑같은 선언문 입니다. 유일한 차이점이라면 pf에 포인터 표시(*)를 하지 않고 선언했다는 점입니다(C와 C++에서 유효한 문법입니다).
늘 그렇듯이 매개 변수의 이름은 뺄 수 있습니다. 따라서 앞의 선언문은 다음과 같이 쓸 수 있습니다. pf가 빠져 있지요.
매개 변수를 둘러싼 괄호는 무시되어도 무방한 것이지만, 그냥 괄호는 함수의 매개 변수 리스트가 있음을 나타내는 것입니다. 즉, 이 그 자체가 함수의 포인터임을 알리는 것이죠.
이상한 코드 입니다.
위의 문장은 리스트 객체가 아니라 data라는 이름의 함수를 선언한 것입니다. list<int>의 반환 타입을 가진 함수 말입니다. 이 함수는 두 개의 매개 변수를 받습니다. 하나씩 설명해 보죠.
첫째 매개 변수는 dataFile이란 이름을 가지고 있습니다. 타입은 istream_iterator<int> 입니다. dataFile를 둘러싸고 있는 괄호는 불필요한 것이므로 컴파일러가 무시해 버립니다.
둘째 매개 변수는 이름을 가지고 있지 않습니다. 타입은 아무 것도 받아들이지 않고 istream_iterator<int>을 반환하는 함수 포인터입니다.
황당하시죠, C++의 컴파일 규칙에 하나도 어긋나지 않습니다. 규칙에 의하면 함수 선언으로 해석될 수 있는 예가 꽤 많습니다.
그렇다면 어떻게 파일의 내용으로 초기화되는 list<int> 객체를 만들 수 있을까요? 컴파일러에 구애받지 않고 쓸 수 있는 좋은 방법을 알려 드리겠습니다. C++(STL) 프로그래머들이 즐겨 사용하는 익명 객체 선언을 istream_iterator에 쓰지 말고, 각 반복자 객체의 이름을 만들어 넣어 주는 것입니다. 다음의 코드가 그 해답이며, 어디서든 사용할 수 있습니다.
이름이 붙은 반복자 객체를 쓰는 이 방법은 STL 프로그래밍 스타일에 거꾸로 가는 것입니다. 하지만, 이 정도는 컴파일러와 프로그래머 모두에게 혼란을 주는 코드 대신에 지불하는 가격이라고 생각할 수 있습니다.
new로 할당된 객체를 가리키는 포인터를 컨테이너에 담는 경우에는 이야기가 다릅니다. 분명히, 포인터의 컨테이너는 자신이 소멸될 때 각 요소 자체를 없애 주기는 합니다. 하지만, 문제는 그게 아니라 포인터의 소멸자가 아무 일도 하지 않는다는 것입니다! 포인터에 대해 delete를 하지 않기 때문입니다.
다음의 코드를 보시죠. 메모리가 줄줄 새는데도 자랑이라고 그냥 있는 코드입니다.
vwp의 각 요소, 포인터 자체는 vwp가 스코프(scope, 변수의 유효 영역)를 벗어날 때 소멸되지만, 이렇다고 해도 new로 만들어진 객체에 대해 delete가 전혀 쓰이지 않았다는 사실은 바뀌지 않습니다. 실제 객체에 대한 delete는 여러분 소관이지, 벡터의 소관이 아니란 이야기입니다.
부스트 라이브러리의 shared_ptr을 사용하면 위의 코드는 다음과 같이 고쳐 쓸 수 있습니다.
여기서 절대로 하지 말아야 할 어리석은 생각이 있습니다. 바로 auto_ptr의 컨테이너를 생성하여 포인터들이 자동으로 삭제되게 할 수도 있지 않을까? 라는 생각입니다. 재앙을 가져오는 무시무시한 생각이니, 꿈에서나 상상하기 바랍니다. 정말로 여러분이 기억해야 할 사실은 STL 컨테이너는 지능적이지만 포인터를 삭제할 수 있는 방법을 알 정도로 지능적이지 않다는 것입니다. 동적 할당된 객체의 포인터를 가진 컨테이너의 메모리 누수를 막기 위해서는 해당 포인터를 참조 카운팅이 가능한 스마트 포인터(부스트 라이브러리의 shared_ptr 같은)로 대체하든지, 컨테이너가 소멸하기 전에 컨테이너 내의 포인터에 대해 직접 delete를 해주셔야 합니다.
auto_ptr의 컨테이너(COAP : Container Of A(a)uto_P(p)tr)는 절대 금지입니다.
표준 STL 컨테이너가 하나 있다고 가정합시다. 이름을 c라고 짓고, int를 담는 컨테이너로 정하죠.
그리고, c에 들어 있는 정수 중에 1963이라는 값을 가진 것은 모두 지우고 싶습니다. 개념상 그리 어려운 일이 아니죠. 하지만, 이 작업을 하는 컨테이너마다 천차만별이라는 사실이 놀랍습니다. 모든 컨테이너에 통하는 한 가지 방법은 없다는 말이죠.
우선, 연속 메모리 컨테이너(vector, deque, string)의 경우를 알아봅시다. 가장 좋은 방법은 erase-remove 합성문입니다.
이 방법은 양방향 반복자를 지원하는 list에도 통하지만, list의 멤버 함수인 remove가 더 효율적입니다.
c가 표준 연관 컨테이너일 때에는(예를 들면 set, multiset, map, 혹은 multimap) remove라는 이름을 가진 어떤 것도 소용이 없습니다. 연관 컨테이너에서 특정한 값을 가진 요소를 지우는 것은 erase입니다.
이렇게 하면 원하는 삭제가 제대로 될 뿐만 아니라 효율적입니다. 로그 시간만큼만 걸리지요(시퀀스 컨테이너에 사용하는 remove 방법은 선형 시간이 걸립니다).
컨테이너에서 특정한 값을 가진 객체를 모두 없애려면:
컨테이너가 vector, string 혹은 deque이면, erase-remove 합성문을 씁니다.
컨테이너가 list이면, list::remove를 씁니다.
컨테이너가 표준 연관 컨테이너이면, erase 멤버 함수를 씁니다.
컨테이너에서 특정한 술어 구문을 만족하는 객체를 모두 없애려면:
컨테이너가 vector, string 혹은 deque이면, erase-remove_if 합성문을 씁니다.
컨테이너가 list이면, list::remove_if를 씁니다.
컨테이너가 표준 연관 컨테이너이면, remove_copy_if 와 swap을 쓰든지, 컨테이너 내부를 도는 루프에서 erase를 호출하면서 erase에 넘기는 반복자를 후위 증가 연산자로 증가시킵니다.
루프 안에서 무엇인가를 하려면(객체 삭제도 포함해서):
컨테이너가 표준 시퀀스 컨테이너이면, 컨테이너 요소를 하나씩 사용하는 루프를 작성합니다. 이때 erase를 호출할 때마다 그 함수의 반환값으로 반복자를 업데이트하는 일을 꼭 해야 합니다.
컨테이너가 표준 연관 컨테이너이면, 역시 컨테이너 요소를 하나씩 사용하는 루프를 작성합니다. 이때 erase를 호출하면서 erase에 넘기는 반복자를 후위 증가 연산자로 증가시킵니다.
여러분이 커스텀 할당자를 작성할 일이 있을 때 기억할 것들
할당자를 템플릿으로 만듭니다. 템플릿 매개 변수에는 여러분이 메모리를 할당하고자하는 객체의 타입을 나타내는 T를 사용합니다.
pointer와 reference라는 typedef 타입을 제공하되, 항상 pointer는 T*, reference는 T&이도록 합니다.
할당자에는 객체별 상태를 절대로 주지 않습니다. 일반적으로, 할당자는 비정적 데이터 멤버를 가질 수 없습니다.
할당자의 allocate 멤버 함수에는 필요한 객체의 개수를 매개 변수로 넘깁니다. 바이트 수가 아닙니다. 또한, 이 함수는 T* 포인터(pointer라는 typedef 타입을 통해)를 반환(비록 T 객체는 아직 생성되지 않앗지만) 한다는 것도 잊지 맙시다.
표준 컨테이너(연관 컨테이너)에서 필요로 하는 rebind라는 중첩 템플릿을 꼭 제공합시다.
할당자는 여러 가지 면에서 유용합니다. "같은 타입의 할당자는 모두 동등해야 한다"는 제약만 잘 지키면, 커스텀 할당자를 사용한 메모리 관리 전략에 에로사항이 꽃피는 일은 없을 것입니다.
STL 컨테이너에게 쓰레딩 문제 해결을 전적으로 믿고 맡길 수 없습니다. 오히려 여러분이 직접 쓰레드 동기화를 제어해 주는 것이 낫습니다.
쓰레드 안정성을 가지기 위한 객체 지향적 해결 방법은 생성자에서 뮤텍스를 잡고 소멸자에서 이 뮤텍스를 해제하는 Lock 클래스 같은 것을 만들 수 있을 것입니다.
여기에 보여 드린 Lock 클래스는 말 그대로 줄기만 남긴 것입니다. 업계에서 쓸 만한 버전이 되려면 살을 아주 많이 붙여야 하지만, 그 작업은 STL과 전혀 관련이 없습니다. 게다가, 다음과 같이 이 Lock이 어떻게 사용될 수 있는지를 확인하는 데에도 충분합니다.
Lock 객체가 컨테이너의 뮤텍스를 해제하는 부분은 Lock의 소멸자이기 때문에, 뮤텍스가 해제되어야 할 때 Lock 객체도 메모리에서 없어진다는 것이 포인트입니다. 이렇게 동작시키려면 Lock 객체를 정의하는 블록을 하나 만들되, 뮤텍스가 더 이상 필요 없는 위치에서 블록을 닫아야 합니다. releaseMutexFor의 호출과 블록 닫기를 맞바꾸는 것이 아니냐고 생각하실 수 있겠지만, 꼭 맞는 생각은 아닙니다. 깜박 잊고 블록을 새로 만들지 않았다고 해도 뮤텍스는 언제가는 해제됩니다. 위의 코드를 감싸고 있는 블록의 끝에 올 때 뮤텍스가 해제될 것입니다. 하지만, (직접 호출하는 경우) 깜박 잊고 releaseMutexFor를 호출하지 않으면 뮤텍스는 해제되지 않습니다.
게다가, Lock 클래스를 사용한 방법은 예외에도 견고하게 동작합니다. C++ 스펙에 의하면 예외가 발생했을 때 지역 객체는 모두 소멸되도록 되어 있기 때문에, Lock 객체를 사용하는 도중에 예외가 발생했다고 해도 Lock 클래스의 소멸자가 안전하게 호출될 수 있습니다.
vector와 string은 자체적으로 메모리 관리를 하기 때문에 프로그래머가 동적 할당시 져야 할 부담을 없애줍니다. 각 메모리는 요소가 추가되어 필요할 때마다 자라나며, vector나 string이 메모리에서 소멸될 때 각 객체의 소멸자를 통해 해당 컨테이너 안의 요소를 모두 없애줌과 동시에 각 요소들이 점유하고 있던 메모리도 해제시킵니다.
또한 vector와 stirng은 STL 시퀀스 컨테이너의 필수사양을 완벽히 가지고 있는 컨테이너이기 때문에, STL에서 지원되는 모든 알고리즘을 그대로 적용할 수 있습니다.
많은 제품들이 string을 참조 카운팅이 동작되도록 구현함으로써, 불필요한 메모리 할당과 문자 복사를 없앰으로써 많은 애플리케이션에서 높은 수행성능을 낼 수 있도록 하고 있습니다. 하지만 참조 카운팅이 되는 string을 다중 쓰레드 환경에서 사용하다가는, 메모리 할당이나 복사에서 절약된 시간을 동시성 제어에 걸리는 오버헤드가 잡아먹는 경우가 생깁니다. 여러분이 사용하고 있는 STL 제품에서 구현된 stirng이 참조 카운팅이 되는 것이냐를 확인하고 싶으시면 해당 라이브러리 문서를 찾아보면 됩니다.
사용하고 계신 string이 참조 카운팅이 되는데 이것을 다중 쓰레드 환경에서 사용하기에는 수행 성능의 저하가 만만치 않다고 생각하셔도, STL을 버리지 않고 선택할 수 있는 길이 세 가지나 있습니다. 첫째는 라이브러리에서 참조 카운팅을 끌 수 있는 방법이 있는지 조사하는 것인데요, 대개 전처리자의 변수 값을 바꿈으로 이것이 가능하게 되어 있습니다. 물론 이렇게 만든 코드는 이식이 되지 않습니다만, 필요한 수작업의 양을 고려한다면 충분히 가치는 있습니다. 둘째는 참조 카운팅을 사용하지 않는 다른 string을 구현하는 것입니다. 셋째는 string 대신에 vector<char>를 고려해 보는 것입니다. vector는 원래부터 참조 카운팅을 하지 않도록 구현되어 있어서 다중 쓰레드 환경에서의 수행 성능 문제가 발생할 틈이 없습니다.
결론은 간단합니다. 배열을 직접 동적으로 할당하려고 하면 쓸데없는 일에 온 신경을 다 써야 한다는 이야기입니다.
vector와 string에 있어서의 메모리 증가는 재할당(realloc)이란 과정을 거쳐서 이루어집니다. 실제로 realloc의 일을 해주는 API가 호출되는 것은 아니고, 다음의 네 단계의 동작이 진행됩니다.
1. 컨테이너의 현재 용량의 몇 배가 되는 메모리 블록을 새로 할당합니다. 대부분의 제품에서는 '2'의 증가율 만큼 용량을 늘리도록 구현하고 있습니다. 즉, 컨테이너의 메모리가 증가되어야 할 필요가 있을 때 용량이 두 배씩 늘어난다는 뜻입니다.
2. 컨테이너가 원래 가지고 있었던 메모리에 저장된 모든 요소 데이터(객체)를 새 메모리에 복사합니다.
3. 원래의 메모리에 저장된 모든 객체를 소멸시킵니다.
4. 원래의 메모리를 해제합니다.
할당 - 복사 - 소멸 - 해제. 여기서 상당한 비용이 들 수 있습니다. 당연히 앞의 4단계의 수행이 덜 빈번하게 이루어졌으면 좋겠지요. 반복자, 포인터, 참조자가 매 단계마다 무효화됩니다. 간단히 말해, vector나 string에 요소 하나를 추가하더라도 그 때까지 반복자, 포인터 혹은 참조자를 사용하고 있던 모든 자료구조를 새로 세팅해야 한다는 말입니다.
reverse 멤버 함수는 사용할 메모리를 미리 할당해 둠으로써 재할당의 회수를 최소화시키고, 아울러 메모리 재할당과 반복자/포인터/참조자의 무효화로 인해 요구되는 비용 부담을 피해갈 수 있도록 해줍니다. vector와 string이 모두 지원하는 STL의 네 개의 함수를 정리해 보도록 하겠습니다.
size() 함수 : 현재 컨테이너에 들어 있는 요소의 개수를 알려 줍니다.
capacity() 함수 : 해당 컨테이너에 할당된 메모리로 담을 수 있는 요소의 개수를 알려 줍니다. 이 개수는 컨테이너의 메모리에 담을 수 있는 총 요소 개수입니다.
resize( size_t n ) 함수 : 컨테이너가 담을 수 있는 요소의 개수를 n개로 무조건 만듭니다. n이 현재의 요소 수보다 작으면 컨테이너의 끝 쪽에 있는 요소는 모두 소멸됩니다.
reserve( size_t n ) 함수 : 컨테이너의 용량을 최소 n개로 맞춥니다. n이 현재의 요소 개수보다 작지 않다는 가정 하에 그렇다는 이야기입니다. 대개 재할당이 일어나는데, 용량이 늘어나야 하기 때문이지요(n이 현재의 용량보다 작을 경우, vector는 아무 일도 하지 않으며 string은 size()의 호출 결과의 n중에 큰 값으로 내부 용량을 줄이기도 합니다. 하지만, string의 요소 개수는 바뀌지 않습니다).
지금까지 네 개의 함수를 정리해 보니, 메모리 재할당(메모리 할당, 데이터 복사, 객체 소멸, 메모리 해제를 모아서 일컫는 말입니다)이란 것은 요소가 새로 삽입되어야 하는데 컨테이너의 용량이 부족할 때 일어난다는 것이 확실해 졌습니다. 즉, 메모리 재할당을 피하는 포인트는 컨테이너가 생성된 바로 직후에 reserve를 써서 컨테이너의 용량을 가능한 충분히 큰 값으로 맞추는 것입니다.
reserve를 써서 불필요한 메모리 재할당을 피하는 방법은 흔히 두 가지로 정리할 수 있습니다. 첫째는 컨테이너에 저장되는 요소의 개수를 정확하게 혹은 대강 파악하고 있을 때 가능한 방법으로, 필요한 양을 예약해 놓는 것입니다. 둘째 방법은 필요한 최대량을 미리 예약해 놓은 후, 나중에 데이터를 모두 넣고 남은 용량을 잘라 내는 것입니다.
string은 거의 모두 다음과 같은 정보를 가지고 있게끔 구현되어 있습니다.
문자열의 크기(size) : 즉, string 객체에 담겨져 있는 실제 문자열의 길이(문자의 개수)
문자를 담아두는 메모리의 용량(capacity)
문자열의 값(value) : 문자열을 이루는 문자들
여기까지가 기본이고, 다음의 정보가 선택적으로 저장될 수 있습니다.
할당자(allocator)의 사본
참조 카운팅을 사용하는 string의 경우 아래의 것을 하나 더 가지고 있습니다.
문자열 값에 대한 참조 카운트(reference count)
string의 문자열 값은 참조 카운팅이 될 수도, 되지 않을 수도 있습니다. 기본적으로 많은 라이브러리에서 참조 카운팅을 사용하고 있습니다만, 이 기능의 동작을 막는 방법(대개 전처리자 매크로롤 통해)도 제공하고 있습니다.
string 객체 자체의 크기는 포인터 크기의 한 배에서 일곱 배까지 다양합니다.
문자열을 새로 생성할 때 필요한 메모리 할당의 회수는 0번, 1번, 또는 2번이 될 수도 있습니다.
둘 이상의 string 객체가 문자열 크기나 용량 정보를 함께 가지고 있을 수도, 가지고 있지 않을 수도 있습니다.
문자 버퍼를 위해 할당하는 메모리의 최소량에 대한 정책은 구현된 라이브러리마다 천차만별입니다.
벡터를 C API에 넘기는 방법
여기서 v[0]라는 표현식은 벡터 내의 첫째 요소에 대한 참조자를 나타내므로 &v[0]은 첫째 요소를 가리키는 포인터입니다. C++ 표준에 의하면 vector 내의 데이터 요소들은 연속 메모리에 저장되도록 정해져 있습니다. 배열과 똑같지요. 한 가지 주의해야 할 포인트는 v가 빈(empty) 벡터일 때입니다. v.size()가 0인 상황에서 &v[0]은 있지도 않은 메모리의 주소값을 만들려고 용을 쓰게 되고, 결국 알 수 없는 동작을 일으키게 됩니다. 따라서 안전하게 코딩하려면 이렇게 합니다.
이 방법은 string에는 통하지 않습니다. 왜일까요? (1) string의 데이터 자체가 연속 메모리에 저장되도록 규정되어 있지 않습니다. 그리고 (2) string의 내부 문자열 값이 널 문자로 끝나지 않는 것도 있습니다. 이런 전차로 string 클래스에는 c_str이란 멤버 함수가 있는 것이지요. 이 함수는 string에 저장된 문자열 값에 대해 C 타입의 문자열 포인터를 만들어 줍니다. 즉, 문자열 s를 다음과 같은 함수에 넘기려면
이렇게 합니다.
이 코드는 문자열의 길이가 0이어도 동작합니다. 이런 경우에는, c_str 함수가 널 문자에 대한 포인터를 반환합니다.
이제 doSomething 두 개를 나란히 놓고 살펴보도록 합시다.
여기서 매개 변수로 넘겨지는 포인터는 모두 const에 대한 포인터입니다. 즉, API로 넘겨지는 vector나 string 데이터는 읽을 수 있으나 변경할 수는 없습니다.
벡터에다가 신청자(contestant) 정보를 넣고 관리하는 코드
처음 출연자 신청자를 받을 때 100,000개의 신청서가 벡터에 들어갔다고 하면, 이후에 그 벡터의 크기가 10으로 줄었다고 해도 용량은 그대로 최소 100,000개인 채로 남게 됩니다.
다음의 코드를 사용하면 contestants 벡터에서 필요 없는 용량을 잘라낼 수 있습니다.
우선 vector<Contestant>(contestants)까지 보죠. 이 표현식은 contestants의 사본인 임시 벡터 객체를 만듭니다. 즉 vector의 복사 생성자가 contestants의 상수 참조자를 매개 변수로 받아 동작하는 거죠. 단, 이 복사 생성자는 요소가 복사되는데 필요한 만큼의 메모리만을 할당하기 때문에, 이렇게 만들어지는 객체는 contestants와 달리 딱 맞는 용량이 잡혀 있습니다. 그 다음 swap 문이 이어지고 있는데요, 이 함수에 의해서 임시 벡터 안의 데이터와 contestants 안의 데이터가 완전히 싹 바뀝니다. 여기까지 오면 contestants는 필요 없는 용량이 제거된 상태가 되고, 임시 객체는 contestants가 사용하고 있던 불필요한 메모리를 가지고 있게 됩니다. 이제 앞의 코드가 끝나면(즉, 문장의 끝에 오면) 임시 객체가 소멸되기 때문에 그 객체가 떠 맡고 있던 메모리도 동시에 해제됩니다.
이 "바꿔치기" 묘소는 string에도 쓸 수 있습니다.
사실, 이 묘소를 썼을 때 완벽하게 불필요한 용량의 메모리가 없어진다는 보장은 없습니다. 왜냐하면, vector나 string을 구현한 개발자가 마음먹기에 따라 용량 설정이 다르기 때문이지요.
언뜻 멀쩡해 보이는 vector<bool>은 사실 STL 컨테이너로서 두 가지가 잘못되어 있습니다. 첫째는 STL 컨테이너가 아니라는 점이고, 둘째는 bool을 담고 있지도 않다는 점입니다.
어떤 객체가 STL 컨테이너의 자격을 갖추려면 C++ 표준안에 수록된 요구사항을 만족해야 합니다. 이 요구사항 중 하나가 "c가 타입 T의 객체를 담는 컨테이너라면 c에서 operator[]가 지원되어야 한다"라는 것입니다. 즉, 다음의 코드가 컴파일 되어야 한다는 말이죠.
다시 말해서, operator[]를 써서 Container<T>에서 T 객체 하나를 얻어낸다면 이 객체의 주소값을 가지고 객체의 포인터를 얻어낼 수 있다는 것입니다(T가 엽기적으로 operator&를 오버로딩 당한 경우가 아니라고 가정할 때 입니다).
vector<bool>은 실제로 bool이 들어 있지 않은 가짜 컨테이너입니다. 공간을 줄이기 위해 bool을 압축(pack)시킨 데이터 표현 방식을 쓰기 때문에 컴파일에 실패합니다. 대개 "vector"에 저장되는 "bool"을 하나의 비트로 나타내어 한 바이트로 여덞 개의 bool을 담을 수 있게 구현하더군요. 즉, vector<bool>은 비트 필드를 써서 bool을 저장하고 있는 것처럼 흉내내는 것일 뿐입니다.
vector<bool>은 컨테이너가 아니니 사용하지 말아야 한다면 정말로 vector<bool>같은 객체가 필요할 때 어떻게 해야 할까요?
표준 라이브러리(STL이 아닙니다)로 할 수 있는, 거의 모든 상황에서 통하는 방법은 두 가지입니다. 첫째는 deque<bool>인데요, deque는 vector가 할 수 있는 거의 모든 것을 할 수 있고( 못 하는 것을 꼽자면 reserve와 capacity가 먼저 떠오르는군요) 진짜 bool을 저장 할 수 있는 STL 컨테이너 입니다. 물론 deque가 사용하는 내부 메모리는 연속 메모리가 아니기 때문에 bool 배열을 받아들이는 C API 등에 넘기지는 못합니다. 하지만 이것은 vector<bool>로도 불가능합니다.
둘째는 bitset(비트셋)입니다. bitset은 STL 컨테이너는 아니지만, 표준 C++ 라이브러리에 속해 있습니다. STL 컨테이너와 달리, 비트셋의 크기(요소의 개수)는 컴파일 타임에 고정되기 때문에 요소를 새로 삽입한다든지 제거하는 작업은 할 수 없습니다. 더욱이 STL 컨테이너가 아니기 때문에 반복자도 지원하지 않습니다. 하지만 비트 하나 하나를 모아 보여주는 클래스답게 비트 조작에 관련된 편리한 멤버 함수를 지원하며, vector<bool>에만 있는 flip 함수도 제공합니다.
주어진 범위 안에서 어떤 값을 가지고 있는 첫째 객체의 위치를 찾아 달라고 find를 호출하면 find 알고리즘은 그 값에 대해 아주 열심히 비교합니다. 또한, set 객체에 어떤 요소를 새로 insert하려고 하면 set::insert는 새로 추가될 요소가 같은 값을 가지고 있는 요소가 이미 저장되어 있는지 알아내야 합니다. find 알고리즘의 경우 상등성, set::insert는 동등성으로 "같다"의 정의를 내리고 있습니다.
동작적인 특징으로 볼 때, 상등성의 개념은 operator==에 뿌리를 두고 있습니다. 어떤 표현식 "x==y"가 참이라고 하면 x와 y는 같으며, 거짓이라고 하면 다르다고 합니다. 하지만 x와 y가 같다고 해서 x와 y의 모든 데이터 멤버가 같은 값이어야 한다는 이야기는 아닙니다.
STL에서 동등성은 정렬된 범위 안에 있는 객체 값들의 상대적인 순서에 준하고 있습니다. 모든 연관 컨테이너(set, multiset, map, multimap)가 내부 데이터 요소를 관리할 때 사용하는 정렬 순서를 생각하면 딱 맞습니다. 컨테이너 c에 저장되어 있는 어떤 객체 x,y가 있다고 할 때, x와 y 모두가 c의 정렬 순서에 대해 서로의 앞에 오지 않는다면 x와 y는 동등하다고 합니다. 일반적으로, 연관 컨테이너에 사용되는 비교 함수는 operator<가 아니라 less 입니다.
string* 포인터로 이루어진 set을 하나 만들고, 여기에 동물 이름을 몇 개 넣기로 합시다.
이제 이 set에 들어 있는 내용을 출력할 생각으로 다음의 코드를 써 보았습니다. 어쨌든 set은 데이터를 정렬하여 관리한다고 알고 있으니, 알파벳 순서대로 출력될 것으로 기대합니다.
알파벳 순서대로 출력되지 않습니다. 대신 16진수 세 개가 한 줄씩 나올 뿐이죠. 이 숫자는 포인터 값입니다. 이 set 객체는 포인터를 담고 있기 때문에, *i는 string 객체가 아니라 string 객체에 대한 포인터 입니다. 이 코드에서 *i를 **i로 바꾸면 아마 결과는 볼 수 있을 것입니다. 하지만 ssp에 들어 있는 요소는 분명히 정렬되어 있습니다만, ssp에는 포인터가 들어 있기 때문에 문자열 값이 아닌 포인터 값에 의해 정렬된 것입니다.
이 문제를 해결하기 위해서 우선 차근차근 짚어 봅시다.
는 아래 선언문에서 둘째 매개 변수를 생략하고 쓴 것입니다.
우리의 관심사는 문자열 값들이 알파벳 순서로 늘어서도록 string* 포인터를 정렬하는 것입니다. 이런 목표 하에서는 기본적으로 주어지는 less<string*>이라는 비교 함수자 클래스를 쓸 수 없습니다. 용도에 맞는 비교 함수자 클래스를 직접 만들어야 하는 것이죠. 어떻게 만드는고 하니, string* 포인터를 매개 변수로 받아, 이 포인터가 가리키는 string끼리 비교하는 것입니다.
이제 이 타입을 ssp의 비교 함수자 타입으로 넣어줍니다.
StringPtrSet ssp; // 문자열 포인터의 set을 만드는데, 이때 StringPtrLess를 써서 정렬합니다.
... // 문자열 포인터의 삽입은 이전과 똑같이 합니다.
이제 루프 코드는 원하는 대로 동작할 것입니다.
알고리즘을 쓰고 싶으세요? string* 포인터를 받아, 이것을 역참조해서 화면에 출력해 주는 함수만 있으면 됩니다. 물론 set은 StringPtrLess를 비교 함수자 타입으로 사용하고 있어야 겠지요. 다음은 for_each 알고리즘으로 코드가 더욱 깔끔해진 모습입니다.
set 객체는 우선 10이 이미 들어 있는지를 파악해야 합니다. 편의상 이미 들어 있는 10은 10A라고 하고, 넣으려고 하는 10은 10B라고 부르기로 하지요.
set 객체는 내부 데이터 구조를 뒤지면서 10B를 삽입할 위치를 찾습니다. 실제로 하는 일은 10B가 10A와 같은(same)지 체크하는 건데요, 연관 컨테이너의 사전에서는 "같다"라는 말은 "동등하다"라는 뜻이니까(항목 19), 결국 10B가 10A와 동등한지를 체크해 가는 것입니다. 이때 해당 set 객체에 지정된 비교 함수를 쓰게 되지요. 이 예제 코드에서는 less_equal을 지정했으므로 operator<=가 비교 함수로 쓰입니다. 따라서, set 객체는 다음의 표현식이 참인지를 검사합니다.
물론 표기만 다를 뿐 이 두 개의 값은 똑같은 10이죠. 따라서 10A<=10B는 명백히 참입니다. 10B <= 10A도 참이고요. 즉, 앞의 표현식은 다음과 같이 간단히 할 수 있습니다.
그리고 결국 이렇게 쓸 수 있습니다.
결과는 false이지요. 즉, 이 set 객체는 10A와 10B는 동등하지 "않다"라는 결론을 내립니다. 10A가 버젓이 있는데 10B를 넣으려고 애쓰는 꼴입니다. 연관 컨테이너에 사용하는 비교 함수는 같은 값에 대해 꼭 false를 반환하게 해야겠다는 생각을 하셨을 것입니다. 하지만 주의해야 할 점은 있습니다.
예를 하나 들겠습니다. 항목 20에서는 string* 포인터를 연관 컨테이너에 저장해서 문자열에 따라 정렬할 수 있는 비교 함수를 만드는 방법을 보여주고 있습니다. 이 비교 함수를 오름차순 정렬에서 내림차순으로 정렬한다고 가정해보죠. 가장 쉬운 방법은 미리 만든 코드를 따다가 고치는 것입니다.
아이디어의 핵심은 비교 함수에 들어 있는 검사 문장에 부정 연산을 취해서 정렬 순서를 뒤집어 보자는 것인데요, 애석하게도 "<"의 반대는 ">"이 아니라 ">="입니다. ">="은 같은 값에 대해 true를 반환하는, 종전과 같은 나쁜 결과를 만든단 말입니다.
여러분이 진짜로 원했던 비교 함수자의 타입은 이것입니다.
STL 프로그래머들이 쉽게 빠지는 이 함정을 피하려면, 비교 함수의 반환값은 어떤 값이 다른 값보다 정렬 순서에서 앞에 오는지의 여부라는 점을 꼭 기억해야 합니다. 두 개의 값이 같다면 절대로 앞서거니 뒤서거니 하는 일이 없기 때문에, 비교 함수 쪽에서는 같은 값에 대해 반드시 false를 반환하도록 해야 합니다.
모든 표준 연관 컨테이너가 그렇듯 set과 multiset은 내부에 저장되어 있는 데이터 요소를 정렬해서 관리하며, 컨테이너의 정상적인 동작은 요소들이 정렬된 상태에서만 가능합니다. 어떤 연관 컨테이너에 들어 있는 어떤 요소의 값을 바꾼다고 합시다. 바뀐 값이 제대로 된 위치에 들어가 있을 리가 만무하므로, 컨테이너의 정렬 상태는 무너지게 됩니다.
표준 연관 컨테이너는 전형적으로 이진 탐색 트리로 구현되어 있습니다. 이 트리는 데이터 노드의 삽입, 삭제, 탐색이 임의대로 아무 때나 이루어지는 상황에 적합하도록 구현된 자료 구조입니다.
많은 애플리케이션이 사용하는 자료구조는 대개 다음의 3단계로 압축되는 순서를 따릅니다.
1. 데이터 셋업(Setup) : 자료 구조를 하나 만들고, 많은 데이터 요소를 여기에 넣습니다. 이때 이루어지는 동작은 데이터 삽입 및 삭제가 대부분이며, 탐색은 거의 일어나지 않습니다.
2. 데이터 탐색(Lookup) : 셋업이 끝난 자료 구조를 사용하여 원하는 정보가 들어 있는지 찾습니다. 이 단계에서 이루어지는 대부분의 동작은 탐색입니다. 삽입 및 삭제는 드물고요.
3. 데이터 재구성(Reorganize) : 자료 구조에 들어 있는 내용물을 바꿉니다. 대개 이때 기존의 데이터를 모두 지우고 새 데이터를 집어넣게 됩니다. 동작상으로 볼 때 단계 1과 흡사합니다. 일단 이 단계가 끝나면, 애플리케이션은 다시 단계 2로 진입합니다.
이러한 방식으로 자료 구조를 사용하는 애플리케이션이라면 벡터가 연관 컨테이너보다 훨씬 나은 수행성능을 제공할 가능성이 높습니다(수행 시간과 메모리 공간 모두). 하지만 이 벡터는 반드시 정렬되어 있어야 한다는 제약이 따르죠. 왜냐하면 벡터의 요소가 정렬된 상태에 있을 때 binary_search, lower_bound, equal_range 등의 탐색 알고리즘을 제대로 적용할 수 있기 때문입니다. 벡터가 이진 탐색 트리에 이진 탐색을 수행하는 것보다 더 나은 이유는 크게 두 부분으로 나눌 수 있습니다. 첫째 이유는 메모리 크기 문제입니다. 또 하나는 1장에서 잠깐 언급한 메모리 참조 위치의 근접성의 문제 때문입니다.
map::operator[]는 "추가 아니면 갱신" 기능을 수행하도록 설계되었습니다. 즉,
이 있다고 할 때, 다음의 표현식
은 우선 해당 맵에 키 k가 들어 있는지 점검합니다. 그렇지 않다면 k와 v가 페어로 묶여서 맵에 새로 '추가'됩니다. k가 맵에 들어 있는 경우에만 k와 매핑(연관)된 값이 v로 갱신됩니다.
이 문장
은 기능적으로 풀어 볼 때 다음의 코드와 동일합니다.
이제 operator[]를 사용하는 것이 수행 성능을 떨어뜨릴 수 있는지 확실히 아시겠죠? 직접 WIdget 객체를 기본 생성자로 만든 다음에 원하는 값을 대입한 것입니다. 만약에, 이렇게 하지 말고 아예 Widget 객체를 원하는 값을 생성자 매개 변수에 넣어 바로 만들어 버리는 것이 효율적이라면 operator[]와 대입 연산자 대신에 다음과 같은 insert 호출 한 번으로 끝낼 수도 있을 것입니다.
이 한 줄은 이전의 긴 코드와 정확히 똑같은 결과를 가져옵니다. 게다가 무려 세 개나 되는 함수 호출을 줄였죠. Widget 객체를 임시로 만드는데 필요한 기본 생성자 함수, 이것을 없애는 데 필요한 소멸자 함수, 그리고 Widget이 대입 연산자 함수가 호출되지 않습니다. 이 각각의 함수의 비용이 크면 클수록 map::operator[] 대신에 map::insert를 썼을 때의 비용 절감 효과는 더 클 것입니다.
이 코드는 모든 표준 컨테이너에서 지원하는 value_type이라는 typedef 타입을 멋지게 이용한 예입니다. map와 multimap에 저장되는 요소의 타입(value_type)은 어찌 되었든 pair라는 점이 핵심 포인트입니다.
"갱신"을 하고자 할 경우, 즉 동등한 키가 이미 map에 들어 있는 경우에는 상황이 바뀝니다. 어째서 그런지 다음을 보도록 합시다.
insert에는 IntWidgetMap::value_type 타입의 매개 변수(즉 pair<int, WIdget>)를 넘겨야 합니다. 따라서 insert를 호출할 때 해당 타입의 객체를 생성했다가 소멸시키는 과정이 필연적으로 따릅니다. 즉 pair의 생성자와 소멸자가 호출되죠. 그 뿐이 아닙니다. pair<int, Widget> 자체에 Widget 객체가 들어 있기 때문에 Widget의 생성자와 소멸자도 덩달아 호출됩니다. 반면, operator[]는 pair 객체를 사용하지 않기 때문에 페어와 Widget 모두에 대해 생성자와 소멸자를 호출할 일이 없습니다.
맵에 "추가"를 할 경우에는 operator[]보다 insert가 효율적으로 낫고, 맵에 저장된 요소에 대한 "갱신"을 할 경우에는 insert보다 operator[]가 효율적으로나 미(美)적으로나 낫습니다.
.bmp "stl(1).bmp")
어떤 형태의 insert와 erase 멤버 함수는 무조건 iterator만을 넘겨야 합니다. 혹시 이런 함수를 호출하려면 iterator 외에 대안이 없습니다.
const_iterator를 iterator로 암묵적으로 변환할 방법은 없으며, 굳이 바꾸려면 항목 27에서 소개하는 방법을 쓰면 되지만 일반성도 떨어지며 효율에 대한 보장도 할 수 없습니다.
reverse_iterator를 iterator로 변환할 수 있으나, 변환한 후에 약간의 조정이 필요합니다. 언제, 그리고 왜 이렇게 하는지에 대해서는 항목 28에서 공부하겠습니다.
const_iterator를 iterator로 안전하고 이식성 있게 바꿀 수 있는 방법. 타입 시스템에 관한 껄끄러운 문제까지 피해 갈 수 있는 방법.
advance(i, distance<ConstIter>(i, ci)); // i와 ci 사이의 거리를 계산(const_iterator로)
// 한후에, 그 거리만큼 i를 옮깁니다.
이 방법은 const_iterator와 동일한 컨테이너 요소를 가리키는 iterator를 얻어내기 위하여, 우선 컨테이너의 첫 요소를 가리키는 iterator를 하나 생성합니다. 그다음 이것을 const_iterator가 있는 곳까지 이동하는 거죠! 이 동작은 advance 템플릿과 distance 템플릿으로 처리됩니다(이 두 템플릿은 <iterator>로 인스턴스화된 것입니다). distance는 같은 컨테이너를 가리키고 있는 두 반복자 사이의 거리를 알려주며, advance는 어떤 반복자를 지정된 거리만큼 이동(전진)시킵니다. i와 ci가 같은 컨테이너를 가리키고 있는 한, advance(i, distance(i,ci)) 표현식이 실행되었을 때 i와 ci는 컨테이너 내의 같은 위치에 있게 됩니다.
진한 부분의 코드는 iterator 타입인 i는 컴파일러에 의해 const_iterator로 저절로 바뀌기 때문에 컴파일됩니다.
reverse_iterator에서 base 멤버 함수를 호출하면 이에 "대응되는" iterator를 얻어낼 수 있다고 합니다. 하지만 문서에 나와있는 대로 정확히 그러한 것은 아니라는 이야기를 하기 위해 이번 항목을 준비했습니다. 이해를 돕기 위해 다음의 예제를 준비했습니다.
이 코드를 실행시키고 난 후의 상황은 다음의 그림처럼 됩니다.
STL 세계에서 요소 삽입은 반복자가 가리키는 위치의 바로 앞에서 이루어집니다.
reverse_iterator 인 ri로 지정된 위치에 대한 요소 삽입을 흉내내려면 ri.base()를 사용합니다. 요소 삽입이 목적이라면 ri와 ri.base()는 동등하며, ri.base()는 ri에 정확히 대응되는 반복자입니다.
reverse_iteartor 인 ri로 지정된 위치에 있는 요소를 삭제하려면 ri.base()의 앞에 있는 위치에서 삭제를 수행해야 합니다. 요소 삭제가 목적이라면 ri와 ri.base()는 동등하지 않으며, ri.base()는 ri에 대응되는 iterator가 아닙니다.
실제로 요소 삭제를 어떻게 하는지 코드를 볼 필요가 있습니다.
v.erase(--ri.base()); // ri.base()의 앞에 있는 요소에 대한 삭제를 시도합니다.
// 그러나 vector에 있어서는 컴파일되는 경우가 거의 없습니다.
v.erase((++ri).base()); // ri가 가리키고 있는 요소를 삭제합니다.
// 이 코드는 언제나 컴파일 됩니다.
모든 표준 컨테이너에서 문제없이 컴파일되고 동작하기 때문에, 역방향 반복자가 가리키는 요소를 삭제할 방법으로 잘 쓰입니다.
istream_iteartor<char> 객체가 coperator>>를 통해 입력 스트림으로부터 문자를 읽어들이는 반면, istreambuf_iterator<char> 객체는 스트림 자체의 버퍼를 직접 건드려서 다음 문자들을 바로 읽어 들입니다(입력 스트림에서 읽기 동작을 수행하는 istreambuf_iterator<char> 객체는 s.rdbuf()->sgetc()를 호출해서 s의 다음 문자를 읽습니다). istreambuf_iterator<char>에서는 skipws 플래그를 "설정해제"할 필요도 없습니다. 스트림 버퍼 안에서 다음 위치에 있는 문자는 어느 것이든 가지고 오는 것이 이 반복자의 특성입니다. istream_iterator와 비교할 때 이 반복자의 속도는 무척 빠릅니다.
istreambuf_iterator의 맛을 한 번 본 분이라면 이에 대응되는 ostreambuf_iterator에도 관심을 주어 보세요. 이 반복자는 istreambuf_iterator에 대응되는, 문자 단위의 비서식화 출력을 수행하는 반복자입니다. ostream_iterator의 오버헤드가 없기 때문에 일반적으로 당연히 빠릅니다.
vector, string, deque, 혹은 C++ 배열에 대해 전체 정렬을 수행할 필요가 있을 때에는 sort나 stable_sort를 사용합니다.
vector, stirng, deque, 혹은 C++ 배열에 대해 상위 n개의 요소만 순서에 맞추어 뽑아내고 싶다면 partial_sort를 사용합니다.
vector, string, deque, 혹은 C++ 배열에 대해 상위 n개의 요소를 뽑되 순서는 고려할 필요가 없다면 nth_element가 적합합니다.
표준 시퀀스 컨테이너가 있고, 이 컨테이너의 요소들을 어떤 기준에 만족하는 것들과 그렇지 않은 것들을 모아 구분하고 싶다면 partition 혹은 stable_partition을 찾으십시오.
사용하고 있는 데이터가 list인 경우에, partition과 stable_partition은 직접 사용할 수 있으며 sort와 stable_sort 알고리즘 대신에 list::sort 멤버 함수를 사용할 수 있습니다. 만일 partial_sort나 nth_element의 기능이 필요하다면 간접적인 방법 밖에는 대안이 없지만 경우에 따라 적절히 선택해서 구현하면 됩니다.
각 정렬 알고리즘의 수행 성능은 작업량이 많은 알고리즘이 시간이 오래 걸리며, 순서를 유지하며 동작하는 알고리즘이 그렇지 않은 것보다 느립니다. 리소스(시간과 메모리)를 적게 먹는 순서대로 정렬해보면
1. partition 2. partial_sort 3. stable_partition 4. sort 5. nth_element 6. stable_sort
remove는 어느 것도 "진짜로" 없애지 않는다. 없앨 수 없기 때문이다.
remove는 주어진 범위 내의 요소를 재배열합니다. 이때 "제거되지 않는" 요소를 범위의 앞쪽에 가져다 놓습니다(원래의 상대적인 위치는 그대로 보존하구요). 그리고 "제거되지 않는" 요소 중 마지막 것의 바로 뒤를 가리키는 반복자를 반환하는 것으로 자신의 동작을 마칩니다. 즉, 이 알고리즘의 반환 값은 그 범위의 "새로운 논리적 끝"이 되는 거죠.
방금 설명드린 이야기를 위의 예제에 맞추면, remove의 수행과정은 다음과 같습니다.
remove는 자신이 제거할 요소의 값에 제거하지 않을 요소의 값을 덮어씁니다. 컨테이너의 요소를 진짜로 제거할 수 있는 장본인은 오직 그 컨테이너의 멤버 함수 뿐이며, 그것이 이번 항목의 전부입니다. 진짜로 요소를 제거하고 싶으면 remove 뒤에 erase를 따라 붙여야 합니다.
erase를 써서 제거할 요소를 판별하는 방법은 아주 쉽습니다. 왜냐하면, remove를 수행해서 얻어낸 주어진 범위의 "새로운 논리적 끝"부터 그 범위의 진짜 끝 사이에 있는 요소들이 이것에 해당하기 때문입니다.
remove와 erase가 너무나 밀접한 나머지, list에서는 이 두 개가 하나로 합쳐진 remove라는 멤버 함수가 제공되고 있을 정도입니다. STL에서 컨테이너의 요소를 없애는 역할을 하는 함수로 remove라는 이름을 가진 것은 이것 하나 뿐입니다.
Widget* 포인터의 리스트가 하나 있고, 웃기는(interesting) 데이터를 가진 Widget 객체를 가리키는 포인터인지 아닌지를 알려 주는 함수가 하나 있다고 합시다.
여기서, 리스트에서 isInteresting 함수가 true를 반환하는 첫째 포인터를 찾고 싶다고 해보죠. 별로 어려운 일이 아닐 것입니다.
그렇다면, 이번에는 웃기지 않은 Widget에 대한 첫째 포인터를 찾으려고 합니다. 그런데, 다음과 같이 하려고 하면 컴파일부터 되지 않습니다.
그 대신, not1을 적용하기 전에 isInteresting 함수에 ptr_fun를 사용하면 되지요.
ptr_fun이 하는 일이란 typedef 타입 몇 개를 쓸 수 있게 만들어 주는 것입니다. not1이 이 typedef 타입들을 필요로 하기 때문에, not1을 ptr_fun에 쓰는 것은 동작하지만 not1을 isInteresting에 직접 쓰면 동작하지 않습니다. 일개 함수 포인터인 isInteresting은 not1이 요구하는 typedef를 가지고 있을 턱이 없지요.
STL 전체의 그림을 놓고 볼 때, not1만이 이런 조건을 필요로 하는 컴포넌트는 아닙니다. STL의 4대 표준 함수 어댑터(not1, not2, bind1st, bind2nd) 모두가 이러한 typedef 타입이 있어야 작동하고, STL과 호환되는 다른 사람들이 만든 비표준 어댑터도 마찬가지입니다. 어댑터 적용이 가능한 함수 객체는 그렇지 않은 것보다 더 많은 경우에 사용할 수 있기 때문에, 여러분의 함수 객체는 할 수 있으면 항상 그렇게 만드셨으면 좋겠습니다. 비용도 전혀 들지 않고, 여러분이 만든 함수자 클래스를 사용하는 분들에게 더 많은 편리함을 드릴 수 있습니다.
f란 이름의 함수와 x란 이름의 객체가 하나 있습니다. 여기서 x에 대해 f를 호출하고 싶으며, 호출하는 위치는 x의 멤버 함수의 바깥쪽입니다. 이런 상황에서 C++가 제공할 수 있는 문법은 다음의 세 가지일 것입니다.
이제, Widget 객체를 검사(test)할 수 있는 함수가 하나 있다고 가정하지요.
하지만, 이렇게 생각해 보세요. test가 보통 함수가 아니고 Widget의 멤버 함수라고요. 즉, Widget에서 자체 검사를 지원한다고 보는 것이죠.
for_each는 함수를 호출할 때 문법 1을 사용합니다. 이 규칙은 STL에서 보편적입니다.
함수와 함수 객체는 항상 '비멤버 함수'에 대한 문법 형태를 통해 호출된다는 것이죠. 그래서 호출 1은 컴파일 되지만 호출 2와 호출 3은 그렇지 못한 것입니다. STL 알고리즘(for_each와 함께)은 문법 1을 사용하도록 만들어져 있는데, 이 문법에 맞는 호출은 호출 1 뿐이니까요.
mem_fun과 mem_fun_ref는 알고리즘이 멤버 함수(문법 2나 문법 3을 사용해서 호출하는 것들)를 호출할 때 문법 1을 사용하도록 해줍니다.
함수 선언문을 살펴보면 mem_fun과 mem_fun_ref가 하는 일은 아주 간단합니다. 이들은 실제로 함수 템플릿이며, 매개 변수의 개수와 멤버 함수의 const 멤버 여부에 따라 약간씩 변경된 mem_fun과 mem_fun_ref의 변이 형태가 몇 가지 더 있습니다.
mem_fun은 멤버 함수의 포인터, pmf를 받아 mem_fun_t 타입의 객체를 반환합니다. 즉, 이것은 멤버 함수 포인터를 가지고 있으면서 operator()에 넘겨진 객체에 대해 멤버 함수를 호출해 주는 (물론 포인터를 통해) operator()를 제공하는 함수자 클래스라고 할 수 있습니다. 예를 하나 들까요? 다음의 코드를 보도록 하죠.
for_each는 Widget::test의 포인터를 가지고 있는 mem_fun_t 타입의 객체를 받습니다. for_each는 lpw내의 Widget* 포인터에 대해 mem_fun_t 객체를 불러오게 되는데, 이때 문법 1을 쓰는 것이죠. 그리고, mem_fun_t 객체는 바로 Widget* 포인터에 대해 Widget::test를 호출합니다. 문법 3을 사용하세요.
전체적으로 놓고 보면 mem_fun은 문법 3, 즉 Widget::test가 Widget* 포인터와 함께 쓰일 때 필요한 문법을 문법 1, 즉 for_each가 사용하는 문법으로 맞추어 주는 어댑터입니다. 이와 비슷한 방식으로, mem_fun_ref는 문법 2를 문법 1에 맞추어 주는 어댑터로서, mem_fun_ref_t 타입의 어댑터 객체를 만들어 냅니다.