[Effective STL] 44. 같은 이름의 멤버 함수 vs 알고리즘

항목 44. 같은 이름을 가진 것이 있다면 일반 알고리즘 함수보다 멤버 함수가 더 낫다

 

 

 

알고리즘과 같은 이름의 멤버 함수

• 연관 컨테이너
  • count
  • find
  • lower_bound
  • upper_bound
  • equal_range
• list
  • remove
  • remove_if
  • unique
  • sort
  • merge
  • reverse

 

 

 

멤버 함수가 더 나은 이유

• 멤버 함수가 더 빠르다.
• 멤버 함수가 해당 컨테이너와 더 잘 맞물려 있다.
• 사실, 같은 이름의 알고리즘과 멤버 함수는 대개 정확히 똑같은 동작을 하진 않기 때문에 차이가 난다.

 

 

 

연관 컨테이너 예시

set<int> s;
... // 1,000,000개의 값을 넣는다.

// 멤버 함수 사용
// 로그 시간에 실행된다.
set<int>::iterator i = s.find(727);
if(i != s.end()) ...

// 알고리즘 사용
// 선형 시간에 실행된다.
set<int>::iterator i = find(s.begin(), s.end(), 727);
if(i != s.end()) ...

• 멤버 find
  • 약 40(최악의 경우)에서 약 20(평균)번의 비교
  • 연관 컨테이너이므로 동등성(equivalence)을 기준으로 삼는다. (항목 19 참조)
  • 만일 map류 컨테이너라면 key에 대해서만 비교하여 탐색한다.
• 알고리즘 find
  • 1,000,000(최악의 경우)에서 500,000(평균)번의 비교
  • 범용적이므로 상등성(equality)을 기준으로 삼는다.(항목 19 참조)
  • 만일 map류 컨테이너라도 key, value 모두를 고려한 탐색을 수행한다.(항목 23 참조)

 

 

 

정말 효율을 신경 쓴다면?

• 이진 탐색 트리와 정렬된 벡터 선택에 신경써야 한다.(항목 23 참조)
• 정렬된 벡터라면, 정렬된 범위에 동작하는 알고리즘을 선택한다.(항목 34 참조)

 

 

 

list 멤버 함수

• 알고리즘은 객체를 복사하지만, 멤버 함수는 복사를 전혀 하지 않는다.
  • 리스트 노드를 연결하는 포인터를 조작할 뿐이다.
• 알고리즘과 멤버 함수의 알고리즘적 복잡도는 동일하다.
  • 허나, 포인터 조작이 객체 복사보다 빠르다.
• 멤버 함수와 알고리즘은 다르게 동작하는 경우도 있다.
  • 알고리즘이라면 컨테이너에서 진짜로 객체를 제거하려면 erase-remove를 함께 사용해야 한다.(항목 32 참조)
  • 하지만 멤버 함수는 그렇지 않다.
• 정렬 동작도 차이가 난다.
  • sort 알고리즘
    • list는 양방향 반복자이므로, list를 정렬할 수 없다.
  • merge 알고리즘
    • 작업 대상이 되는 범위를 건드릴 수 없지만, 멤버 함수는 항상 거리낌없이 바꾼다.