항목 34 : 정렬된 범위에 대해 동작하는 알고리즘이 어떤 것들인지 파악해 두자

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

 

이번 한목은 Container 내부가 정렬되어 있어야지만 정상적으로 동작하는 알고리즘이 있기 때문에, 어떤 알고리즘인지 알아보자 라는 취지에서 필자가 글을 쓴 것으로 보인다.

정렬된 데이터를 넘겨야지만 정상적으로 동작하는 알고리즘 리스트에 대해서 알아보자.

이진 탐색을 사용하는 알고리즘
binary_search
lower_bound
upper_bound
equal_range

집합(set) 조작 알고리즘
set_union
set_intersection
set_difference
set_symmetric_difference

병합(merge sort) 정렬 알고리즘
merge
inplace_merge

includes

가 있고, 추가로 정렬되지 않은 데이터라도 사용 가능한것은

unique
unique_copy

가 있다.

그렇다면 정렬된 데이터를 넘겨야지만 정상적으로 동작하는 알고리즘이 왜 그래야만 하는지? 알아보자.

첫째, binary_search, lower_bound, upper_bound, equal_range 는 이진 탐색을 사용하기 때이다. 이 때문에 로그시간안에 값을 찾을 수 있다.(임의 접근 반복자일 때만...)

둘째,set_union, set_intersection, set_difference, set_symmetric_difference 는 정렬된 범위를 지정할 경우, 선형시간안에 원하는 값을 이터레이터로 지정된 곳에 값을 출력해주는 알고리즘이다. 만약 정렬된 범위를 지정하지 않을 경우, 되긴 되나 선형시간 조차 보장하지 않는다.

셋째, merge와 inplace_merge 는 두 Container를 합치면서 정렬해 주는 알고리즘이다. 시간은 선형시간! 만약 두 Container 중 한 Container 라고 정렬되어 있지 않는다면, 동작하지 않는다.

넷째, includes 는 원하는 범위에서 원하는 값이 있으면 TRUE 를 없으면 FALSE 를 리턴하는 알고리즘으로 정렬되지 않아도 실행은 되나, 그 속도가 선행시간 조차 보장받지 못한다.

부수적으로 unique 와 unique_copy 알고리즘은 정렬되어진 상태여야지만 정상적인 동작을 하며, remove 알고리즘과 같이 값을 제거하는게 아니라 이동하고 그 끝을 이터레이터로 리턴하는 알고리즘이다.

각 알고리즘의 사용법을 인터넷 조사해서 알아보면 더 자세히 나올것 같아 여기서 정리를 끝맞치고 결론을 말하자면, 정렬된 데이터를 사용하여 위의 알고리즘을 사용할 경우, 더 효과적인 성능을 얻을수 있다.