Effective C++/Effective STL

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

김디트 2024. 12. 23. 11:35
728x90

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

 

 

 

알고리즘은 늘 범용적이진 않다.
  • 모든 알고리즘이 어떤 범위든 받아서 잘 동작하는 것은 아니다.
  • remove(항목 32, 항목 33 참조) 알고리즘은 대입 연산이 가능한 순방향 반복자만을 받는다.
  • 정렬 알고리즘(항목 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 참조)
728x90