[Effective STL] 34. 정렬된 범위에 동작하는 알고리즘

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

 

 

 

알고리즘은 늘 범용적이진 않다.

• 모든 알고리즘이 어떤 범위든 받아서 잘 동작하는 것은 아니다.
• remove(항목 32, 33 참조) 알고리즘은 대입 연산이 가능한 순방향 반복자만을 받는다.
  • map과 set에는 사용할 수 없다.(항목 22 참조)
• 정렬 알고리즘(항목 31 참조)은 임의 접근 반복자만을 받는다.
  • list에는 사용할 수 없다.
• 이런 규정을 어길 시 컴파일이 되지 않고, 에러 메시지(항목 49 참조)가 발생한다.
• 특히, 정렬된 범위를 넣어야 하는 알고리즘에 정렬되지 않은 범위를 넣는다면
  • 미정의 구현이므로 어떤 결과가 나타날지 모른다.

 

 

정렬된 범위를 넣어야 하는 알고리즘

• 정렬된 범위를 넘겨야 원하는 효율이 나오는 알고리즘
  • binary_search
  • lower_bound
  • upper_bound
  • equal_range
  • set_union
  • set_intersection
  • set_difference
  • set_symmetric_difference
  • merge
  • inplace_merge
  • includes
• 대개 정렬된 범위에 쓰지만, 꼭 그렇지는 않아도 되는 알고리즘
  • unique
  • unique_copy
• 각각에 대해 아래에서 알아보자.

탐색 알고리즘(항목 45 참조) 

1. binary_search
2. lower_bound
3. upper_bound
4. equal_range

• 내부적으로 이진 탐색을 사용하여 값을 찾기 때문에 정렬이 필요하다.
• 로그 시간의 탐색 효율을 보장하지만, 임의 접근 반복자를 사용할 때만 그렇다.
  • 이보다 못한 반복자를 쓰면, 비교 동작은 로그 시간 안에 일어나지만, 실행 시간은 선형 시간 안에 끝난다.

집합(set) 조작 알고리즘

1. set_union
2. set_intersection
3. set_difference
4. set_symmetric_difference

• 선형 시간의 효율을 보인다.
• 정렬되어 있지 않으면 선형시간 안에 동작을 보장할 수 없다.

병합 정렬(merge sort) 알고리즘의 첫 단계(pass)처럼 동작하는 알고리즘

1. merge
2. inplace_merge

• 두 개의 정렬된 범위를 합쳐 정렬된 하나의 범위를 만든다.
• 선형 시간 안에 완료되며, 원래의 두 범위 중 하나라도 정렬되어 있지 않으면 동작하지 않는다.

어떤 범위 안의 값을 탐색하는 알고리즘

1. includes

• 정렬을 가정하고 동작하므로 선형 시간의 효율을 보인다.
  • 그렇지 않으면 수행속도가 느리다.

중복된 요소에 대한 알고리즘

1. unique
2. unique_copy

• unique의 표준안
  • unique는 연속으로 이어진 동일한 요소들(consecutive group of equal elements) 중에서 첫 번째 것만을 남기고 다 없앤다.
• 즉, 중복된 값들이 연속으로 늘어서 있어야 한다.
• unique는 중복된 요소를 지울 때 remove처럼 동작함을 유의할 것.

 

 

 

정렬된 범위(range to be sorted)에 대한 유의점

• STL에서는 정렬에 사용할 비교 함수를 지정할 수 있도록 되어 있으므로, 범위 정렬 방법이 가지각색이다.
  • 오름차순, 내림차순 정렬
  • 어떤 요소를 기준으로 정렬할 것인가 등
• 정렬 오류 예시

vector<int> v;
...
sort(v.begin(), v.end(), greater<int>()); // 내림차순 정렬
...

bool a5Exists = binary_search(v.begin(), v.end(), 5); // 벡터에서 5를 찾는다.
// 하지만, binary_search는 오름차순으로 정렬되어 있을 걸 가정했다!!

bool a5Exists = binary_search(v.begin(), v.end(), 5, greater<int>()); // 비교 함수 지정으로 해결

• 정렬 범위에 대해 동작하는 모든 알고리즘은 동등성(equivalence)를 기준으로 삼는다.
• 반대로 unique와 unique_copy 알고리즘은 상등성(equality)로 판정한다.(항목 19 참조)