항목 30 : 알고리즘의 데이터 기록 범위(destination range)는 충분히 크게 잡자

내가 STL에 조예가 깊어서 글을 남기는 것이 아니라, Effecitve STL 을 공부하는 사람들이 이 글을 보고, 도움이 되었으면 하는 생각과, 혹시 내가 틀린것이 있다면 지적해 주시지 않을까 란 생각으로 글을 올리는것임을 미리 밝힙니다.  - 최익필

이제부터 알고리즘(Algorithm)에 대해서 효율적인 사용 방법에 대해서 이야기 한다. STL 에 있어 알고리즘은 .. Containers 만큼이나 중요하다. 기본 제공되는것만도 100가지가 남지만, 이중 제일 많이 쓰이는 부분과 좋은 알고리즘(Algorithm)이지만 소개받지 못했던 부분에 대해서 이야기 한다고 하니, 눈 딱 크게 뜨고, 봐야 할 것같다.


이번 항목의 주제는 "알고리즘을 이용하여 데이터를 넣을 때, 컨테이너의 공간을 크게 잡고 넣는게 더 효율적이다." 란 것에 초점을 두고 있다.

이 이야기는 표준 Sequence Containers 중 vector, string, deque 에만 한정된다. 왜냐하면 이 Containers 는 "용량" 이란 개념이 있기 때문이다.

vector 나 string deque 같은 경우, 항목 13 ~ 항목 18까지 자세하게 설명되어져 있다.(deque 는 없지만 이 범주에 든다.) .. 이러한 특성 때문에 "범위로 기록"하는 알고리즘은 데이터가 많이 들어 간다. 이것은 vector, string, deque 에게 있어, 성능에 영향을 미칠 수 있다는 이야기이다.

미리 reserve() 나 resize() 를 호출하여, 공간을 확보하면, 이 문제는 해결 된다.

그러면, 이제 범위로 기록 Algorithm 중, transform() 에 대해서 알아보자.
transform() 은 오버로딩 되어 두가지가 있는데, 그 원리는 같으니, 하나만 코드로 보여 준다.
// ikpil.com or ikpil.tistory.com #include <iostream> #include <vector> #include <algorithm> typedef std::vector<int> Container; int trans( int in_x ) { return in_x * 3; } int main( void ) { Container Source; Source.reserve( 100 ); for( int i = 0; i < 100; ++i ) Source.push_back( i + 1 ); Container Dest; Dest.resize( Source.size() ); Container::iterator OutIt = // transform 의 반환값을 확인하기 위해서 std::transform( Source.begin(), Source.end(), // Source 범위 지정 Dest.begin(), // Dest 의 시작 범위 지정 trans); // Source 의 값을 변경시켜 반환해주는 함수 // 반환값 확인(OutIt 은 출력 완료된 다음것을 리턴한다) std::cout << *(--OutIt) << std::endl; }

다른 하나(transform()의..)는 Dest의 범위를 지정하는 iterator 가 들어가면 된다. STL 보면, 자세히 나와 있으니 생략하고, 위의 코드 중에 조심해야 할것이 있다.

위의 코드 중에
출력 시작점은 Dest.begin() 으로 iterator 로 넣었는데, 이런 경우 컨테이너는 넣고자 하는 용량만큼 있다는 전제가 깔린다. 그것이 확실하지 않다면, back_inserter() 나 front_inserter(), 혹은 inserter() 를 호출하여, 밀어넣기용 iterator를 만들어서 사용 하면 된다.

이 back_inserter() 는 끝에 밀어 넣는 back_iterator 를 반환해주고 back_iterator 는 push_back() 함수를 호출하여, 넣는다. 그러므로 front_inserter() 는 push_front(), inserter() 는 insert() 를 지원하는 컨테이너에서만 사용 가능하다.

마지막으로 이 transform() 알고리즘은 선형시간 비용을 지불한다.

이것만은 잊지 말자
1. 알고리즘을 이용하여 범위 기록을 할경우, 충분히 크게 잡아 두자.


관련링크
http://www.cplusplus.com/reference/algorithm/ <-- STL Algorithm , 영문이다.
http://blog.naver.com/lhk3832/10013884530 <-- transform 사용 법
http://alones.kr/blog/673 <-- transform 타입 확인 할수 있음(대개 이런 타입이다.)
http://www.winapi.co.kr/clec/cpp4/42-2-5.htm <-- 마찬가지